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

  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