Josephus problem.

Josephus.py

# link node
class LinkNode:
    def __init__(self, x):
        self.value = x
        self.next = None

# build link list
def build_link_list(nodes):
    if not nodes:
        head = None
    else:
        head = LinkNode(nodes[0])
        pre = head
        for i in range(1, len(nodes)):
            node = LinkNode(nodes[i])
            pre.next = node
            pre = pre.next

        pre.next = head

    return head

# naive
def basic_list(n, step, offset):
    link = list(range(n))
    index = 0
    while len(link) > 1:
        count = 1
        while count < step:
            count += 1
            index = (index + 1) % len(link)
        print('Kill {}'.format(link[index]))
        link.pop(index)

    print('{} live.'.format(link[0]))
    winner = (link[0] + offset) % n
    print('Basic list: {} win.'.format(winner))

# dynamic programming
def dp(n, step, offset):
    j = 0
    for i in range(2, n + 1):
        j = (j + step) % i
    winner = (j + offset) % n
    print('DP: {} win.'.format(winner))

# link list
def link_list(n, step, offset):
    link = build_link_list(range(n))
    # move to offset
    offset = offset % n
    while offset > 0:
        link = link.next
        offset -= 1

    pre, cur = None, link
    while cur.next != cur:
        for _ in range(step-1):
            pre = cur
            cur = cur.next
        print('kill {}'.format(cur.value))

        # delete node
        pre.next = cur.next
        del cur
        cur = pre.next

    print('LinkList: {} win.'.format(cur.value))


if __name__ == '__main__':
    n = 5
    step = 2
    offset = 2

    basic_list(n, step, offset)
    dp(n, step, offset)
    link_list(n, step, offset)