# Advent of Code 2016, Day 19: An Elephant Named Joseph

#ruby #advent of code 2016

## Part A

On Day 19 we are playing a game with elves. They sit in the circle and steal each other presents. Each elf on this turn steals presents from the elf on the left. Elf that lost his presents leaves the game.

Our input is the number of elves playing and we need to output which elf will end up with all the presents.

For 5 elves, second elf will end up with all presents. You can check the puzzle page for some visualization of this game.

We can implement a naive solution that will simulate this game:

``````def naive(elfs)
array = []

elfs.times do |i|
array.push(i + 1)
end

index = 0
while array.size > 1
if index < array.size - 1
array.delete_at(index + 1)
index += 1
elsif index == array.size - 1
array.delete_at(0)
index = 0
else
index = 0
end
end

puts [elfs, array[0]].inspect
end
``````

We have `naive` method that takes number of elves as an argument. We create and array keeping track of elves in the game. And then we iterate over array and remove elves that sit on the left of our current index (that will be the next index). We stop when there is only one item in this array.

This method works, but there is an obvious performance problem. Our real input asks us to simulate over 3000000 elves playing.

While the naive solution is no good to get the answer for 3 million elves, we can use it to find a pattern in answers. Let’s call our `naive` method for 1-100 elves playing.

``````100.times do |i|
naive(i + 1)
end
``````

It will output:

``````[1, 1]
[2, 1]
[3, 3]
[4, 1]
[5, 3]
[6, 5]
[7, 7]
[8, 1]
[9, 3]
[10, 5]
[11, 7]
[12, 9]
[13, 11]
[14, 13]
[15, 15]
[16, 1]
[17, 3]
[18, 5]
[19, 7]
[20, 9]
[21, 11]
[22, 13]
[23, 15]
[24, 17]
[25, 19]
[26, 21]
[27, 23]
[28, 25]
[29, 27]
[30, 29]
[31, 31]
[32, 1]
[33, 3]
[34, 5]
[35, 7]
[36, 9]
[37, 11]
[38, 13]
[39, 15]
[40, 17]
[41, 19]
[42, 21]
[43, 23]
[44, 25]
[45, 27]
[46, 29]
[47, 31]
[48, 33]
[49, 35]
[50, 37]
[51, 39]
[52, 41]
[53, 43]
[54, 45]
[55, 47]
[56, 49]
[57, 51]
[58, 53]
[59, 55]
[60, 57]
[61, 59]
[62, 61]
[63, 63]
[64, 1]
[65, 3]
[66, 5]
[67, 7]
[68, 9]
[69, 11]
[70, 13]
[71, 15]
[72, 17]
[73, 19]
[74, 21]
[75, 23]
[76, 25]
[77, 27]
[78, 29]
[79, 31]
[80, 33]
[81, 35]
[82, 37]
[83, 39]
[84, 41]
[85, 43]
[86, 45]
[87, 47]
[88, 49]
[89, 51]
[90, 53]
[91, 55]
[92, 57]
[93, 59]
[94, 61]
[95, 63]
[96, 65]
[97, 67]
[98, 69]
[99, 71]
[100, 73]
``````

First column is the number of elves and second is the winning elf. I hope the pattern is clearly visible. We can actually divide our answers into groups. First group is just one element (1), second two elements (1, 3), then (1, 3, 5, 7), (1, 3, 5, 7, 9, 11, 13, 15) and so on. Each group is twice as big as the previous one. Also each group starts when number of elves is a power of 2. In such case always the first elf wins.

To calculate the answer we need first find out which group it should be, then calculate the offset within this group and the answer is offset multiplied by 2 minus 1. For example, if we have 12 elves it will be the fourth group:

``````[8, 1]
[9, 3]
[10, 5]
[11, 7]
[12, 9]
[13, 11]
[14, 13]
[15, 15]
``````

12 is on position 5 (counting from 1). We multiply it by 2 and subtract 1, 5 * 2 - 1 = 9. And 9 is the answer. You can check for other numbers. Here is the final solution:

``````power = 0
sum = 0
elfs = 3000000

while sum < elfs
1.upto(2 ** power) do |number|
sum += 1

if sum == elfs
puts 2 * number - 1
end
end
power += 1
end
``````

## Part B

In second part rules of the game are different. This time elves still presents from elf sitting across the circle. If there are two elves, then he steals from the left one.

We can do similar thing. Write naive solution simulating the game and look for patterns:

``````def naive(elfs)
array = []

elfs.times do |i|
array.push(i + 1)
end

index = 0
while array.size > 1
across_index = (index + array.size / 2) % array.size
array.delete_at(across_index)

if across_index < index
index = index % array.size
else
index = (index + 1) % array.size
end
end

puts [elfs, array[0]].inspect
end

100.times do |i|
naive(i + 1)
end
``````

Output looks like this:

``````[1, 1]
[2, 1]
[3, 3]
[4, 1]
[5, 2]
[6, 3]
[7, 5]
[8, 7]
[9, 9]
[10, 1]
[11, 2]
[12, 3]
[13, 4]
[14, 5]
[15, 6]
[16, 7]
[17, 8]
[18, 9]
[19, 11]
[20, 13]
[21, 15]
[22, 17]
[23, 19]
[24, 21]
[25, 23]
[26, 25]
[27, 27]
[28, 1]
[29, 2]
[30, 3]
[31, 4]
[32, 5]
[33, 6]
[34, 7]
[35, 8]
[36, 9]
[37, 10]
[38, 11]
[39, 12]
[40, 13]
[41, 14]
[42, 15]
[43, 16]
[44, 17]
[45, 18]
[46, 19]
[47, 20]
[48, 21]
[49, 22]
[50, 23]
[51, 24]
[52, 25]
[53, 26]
[54, 27]
[55, 29]
[56, 31]
[57, 33]
[58, 35]
[59, 37]
[60, 39]
[61, 41]
[62, 43]
[63, 45]
[64, 47]
[65, 49]
[66, 51]
[67, 53]
[68, 55]
[69, 57]
[70, 59]
[71, 61]
[72, 63]
[73, 65]
[74, 67]
[75, 69]
[76, 71]
[77, 73]
[78, 75]
[79, 77]
[80, 79]
[81, 81]
[82, 1]
[83, 2]
[84, 3]
[85, 4]
[86, 5]
[87, 6]
[88, 7]
[89, 8]
[90, 9]
[91, 10]
[92, 11]
[93, 12]
[94, 13]
[95, 14]
[96, 15]
[97, 16]
[98, 17]
[99, 18]
[100, 19]
``````

This time there is still a pattern, but a little more complex. Groups start at numbers 1, 2, 4, 10, 28, 82. And answers first are consecutive numbers and then they increase by two (1, 2, 3, 5, 7, 9).

Well, the numbers that groups start at look like powers of 3 plus 1. 1, 2, 4, 10, 28, 82 is actually 3 ^ 0 + 1 = 1, 3 ^ 1 + 1 = 4, 3 ^ 2 + 1 = 10, 3 ^ 3 + 1 = 28, 3 ^ 4 + 1 = 82. And answers first increase by one and then when they reach half of a group they increase by 2. Here is my implementation:

``````elfs = 3000000
power = 0
sum = 0

while sum < elfs
a = power > 0 ? 3 ** (power - 1) : 0
b = 3 ** power

(b - a).times do |number|
sum += 1