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
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
answer = 0
adder = 1
(b - a).times do |number|
sum += 1
answer += adder
if answer >= a
adder = 2
end
if sum == elfs
puts answer
break
end
end
power += 1
end