adventOfCode2016/advent_of_code_19.py at master · 4gn3s/adventOfCode2016 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def get_next_elf(elves, current, total):
    if len(elves) == 1:
        return -1
    next_candidate = current + 1
    while next_candidate not in elves:
        next_candidate += 1
        if next_candidate >= total + 1:
            next_candidate = 1
    return next_candidate

def circular_elves(number_of_elves):
    elves = {i: 1 for i in range(1, number_of_elves + 1)}
    current = 1
    while True:
        if len(elves) <= 1:
            break
        next_elf = get_next_elf(elves, current, number_of_elves)
        elves[current] += elves[next_elf]
        del elves[next_elf]
        current = get_next_elf(elves, current, number_of_elves)

    print(elves)


# circular_elves(5)
# circular_elves(3004953)


class Node:
    def __init__(self, eid):
        self.id = eid
        self.next = None
        self.prev = None

    def delete(self):
        self.prev.next = self.next
        self.next.prev = self.prev


def circular_elves_smarter(number_of_elves):
    elves = [Node(i) for i in range(number_of_elves)]
    for i in range(number_of_elves):
        elves[i].prev = elves[(i - 1) % number_of_elves]
        elves[i].next = elves[(i + 1) % number_of_elves]

    start = elves[0]
    mid = elves[number_of_elves / 2]

    for i in range(number_of_elves - 1):
        tmp = mid
        mid.delete()
        mid = tmp.next
        if (number_of_elves - i) % 2 == 1:
            mid = mid.next
        start = start.next

    return start.id + 1 # elves numbered from 0


assert circular_elves_smarter(5) == 2
print circular_elves_smarter(3004953)