General, Linked Lists
This is a classic algorithm problem, based on a Biblical-era tale.
Imagine a group of 10 people in a circle, numbered 1 to 10. If we started at the first person (#1) and killed every three people, it would look like this:
1 2 3 4 5 6 7 8 9 10 ! ! !
This continues, though, looping around again, starting with where we left of at #10 (we’ll mark the freshly-removed as red/! and the previously-removed in striked-out gray/X):
1 2 3 4 5 6 7 8 9 10 ! X X ! X
And again, starting where that left off, at #8, and continuing:
1 2 3 4 5 6 7 8 9 10 ! X X X X ! X 1 2 3 4 5 6 7 8 9 10 X X X ! X X X X 1 2 3 4 5 6 7 8 9 10 X X X X X X X X !
At this point, only #4 remains, so that person would be our “survivor”.
Write an algorithm that, given a number of people, and the “skip”, which person will be the survivor.
For example:
>>> find_survivor(10, 3)
4
We’ve provided a file, josephus.py, with a function, find_survivor:
def find_survivor(num_people, kill_every):
"""Given num_people in circle, kill [kill_every]th person, return survivor."""
Implement this function.
Linked List
You could solve this in other ways, but using a linked list (or a doubly-linked list) is often a good way to solve this problem. You can do so by making the list “circular”—having the last item in the linked list point back to the first item.
This will let you traverse the list, removing items until one remains.
If you want to try it this way, you may find this node class helpful:
class Node(object):
"""Doubly-linked node."""
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
def __repr__(self):
return "<Node prev=%s data=%s next=%s>" % (
self.prev.data, self.data, self.next.data)