The Elves contact you over a highly secure emergency channel. Back at the North Pole, the Elves are busy misunderstanding White Elephant parties.
Each Elf brings a present. They all sit in a circle, numbered starting with position 1. Then, starting with the first Elf, they take turns stealing all the presents from the Elf to their left. An Elf with no presents is removed from the circle and does not take turns.
For example, with five Elves (numbered 1 to 5):
1
5 2
4 3
So, with five Elves, the Elf that sits starting in position 3 gets all the presents.
With the number of Elves given in your puzzle input, which Elf gets all the presents?
In [1]:
no_elves = 5
elves = [elf for elf in range(1, no_elves + 1)]
print(elves)
To simulate one round, we define the function play_round that takes an elf, then skips one over while iterating over the list. If the number of elves are odd, then the first elf's presents are stolen by the last elf, and therefore, we drop the first elf from the list.
In [2]:
def play_round(elves):
_elves = []
elf = 0
while elf < len(elves):
_elves.append(elves[elf])
elf += 2
if len(elves) % 2 == 1:
_elves.pop(0)
return _elves
In [3]:
while len(elves) > 1:
elves = play_round(elves)
print(elves[0])
In [4]:
with open('../inputs/day19.txt', 'r') as f:
input_data = int(f.readline())
In [5]:
elves = [elf for elf in range(1, input_data + 1)]
In [6]:
while len(elves) > 1:
elves = play_round(elves)
print('answer', elves[0])
The problem statement is actually quite well known as the Josephus problem which can be generalized to a counting out problem. The solution to solve the Josephus problem is given as:
f(n) = f(n - 2) + k - 1) % n + 1
Where n is the number of players, k is the skip count where k-1 people are skipped and the k-th is executed. (in this case, k = 2).
In [7]:
n = 2
k = 2
j = [1]
while n <= input_data:
j.append((j[n - 2] + k - 1) % n + 1)
n += 1
print('answer', j[-1])
Realizing the folly of their present-exchange rules, the Elves agree to instead steal presents from the Elf directly across the circle. If two Elves are across the circle, the one on the left (from the perspective of the stealer) is stolen from. The other rules remain unchanged: Elves with no presents are removed from the circle entirely, and the other elves move in slightly to keep the circle evenly spaced.
For example, with five Elves (again numbered 1 to 5):
The Elves sit in a circle; Elf 1 goes first: 1 5 2 4 3
Elves 3 and 4 are across the circle; Elf 3's present is stolen, being the one to the left. Elf 3 leaves the circle, and the rest of the Elves move in:
1 1
5 2 --> 5 2
4 - 4
Elf 2 steals from the Elf directly across the circle, Elf 5:
1 1
- 2 --> 2
4 4
Next is Elf 4 who, choosing between Elves 1 and 2, steals from Elf 1:
- 2
2 -->
4 4
Finally, Elf 2 steals from Elf 4:
2
--> 2
-
So, with five Elves, the Elf that sits starting in position 2 gets all the presents.
With the number of Elves given in your puzzle input, which Elf now gets all the presents?
We need to redefine our play_round function, where instead of only skipping over the next elf, we need to remove the middle elf from the list. Which one is the middle elf depends on the length of the list at that time. So at each turn (and not round), the length of the list changes. Since we are implmenting the naive solution, we will iterate over the list once in the loop instead of optimizing the index access.
Since we need to eliminate the middle elf at each turn, we must find the middle elf. Let us start by seeing what the pattern is by plotting the number of elfs with the middle elf (the one to be eliminated) for each arrangement.
n 0-indexed array
1 -
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 4
We can see that the element to remove is given by n/2 where n is the total number of elves in the list at that time. Taking this into account, we must now account for the fact that the list mutates after every turn.
turn list play eliminated effective-list
0 1, 2, 3, 4, 5 - - -
1 1, 2, X, 4, 5 1 3 1, 2, 3, 4, 5
2 1, 2, X, 4, X 2 5 2, 4, 5, 1
3 X, 2, X, 4, X 4 1 4, 1, 2
4 X, 2, X, X, X 2 4 2, 4
If we compare the eliminated index and re-list such that the elf currently playing is always at the top/front/start of the array, we get the effective-list. It it, the resultant array at each turn is left-shifted by one. We exploit this to create the resultant array. Thus our strategy becomes -
remove the elf at index n/2
left the list by 1 - pop the first element and add it to the end
Continue this approach until only 1 elf is left.
Note that the simulation takes a LOT of time. Being
n^2, it is very inefficient. Which is why I don't actually run it here. It'll take time. Seriously.
In [8]:
# DO NOT RUN
def do_not_run():
elves = [elf for elf in range(1, input_data + 1)]
while len(elves) > 1:
elves.pop(len(elves)//2)
elves = elves[1:] + elves[:1]
print(elves[0])
We use the concept of balanced trees, where we split the elves into two different lists. In one list, we add the first half elements, and in the second list, we add the other half in the reverse order, i.e. append to the front. Since the elves are always removed from the middle of the list, we can do this easily in a tree, as the middle is always the root. After removal, we need to balance the tree by moving elements from the top of the left branch (the starting elves) to the top of the right branch (the last elves), and then move the elements from the bottom of the right branch (the middle elves) to the bottom of the left branch (the middle elves).
left branch --> first half of elements, normal order
right branch --> second half of elements, reverse order
while length of tree (left + right) > 1:
if left tree has more nodes:
remove node from end of left branch
else:
remove node from end of right branch
remove node from top of left branch and append to top of right branch
remove node from bottom of right branch and append to bottom of left branch
In python, lists are great data structures, but they are not performant when it comes to removing things from the front. Since we need to remove things from both ends, we will use dequeue which is a double ended queue and is performant for insertions and removals at both ends, but will perform badly for other operations such as splicing and random removals (which we do not require).
In [9]:
from collections import deque
left = deque(i for i in range(1, input_data//2 + 1))
right = deque(i for i in range(input_data, input_data//2, -1))
print('tree left->', len(left), '1:', left[0], 'last:', left[-1])
print('tree right->', len(right), '1:', right[0], 'last:', right[-1])
In [10]:
while left and right:
if len(left) > len(right):
left.pop()
else:
right.pop()
right.appendleft(left.popleft())
left.append(right.pop())
Since we do not know which of the left or right branches might contain the final element, we need to check which of the queues are not empty and then retrieve the answer from that.
In [11]:
if left:
print('answer', left[0])
else:
print('answer', right[0])
I received a link to a pastebin containing the following code that gives the answer, though I don't know why or even how it works. I suspect that if I drill enough, I'll find that it is a summarization of the operations done on a balanced binary tree.
p = 3 ** int(log(elves - 1, 3))
return elves - p + max(elves - 2 * p, 0)== END ==