Advent of Code 2015, Day 3 – In Ruby

It’s time to solve the puzzle for day 3 of 2015!

The first half of the puzzle

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

For example:

> delivers presents to 2 houses: one at the starting location, and one to the east.

^>v< delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

^v^v^v^v^v delivers a bunch of presents to some very lucky children at only 2 houses.

We need to collect the {x, y} positions of the houses that Santa visits. Our initial thought could be to use an array for the positions, but we don’t know the dimensions of the grid, and even if we knew them, we’d need to allocate space for the full two-dimensional grid, most of which could be unused.

So, instead of an array, we’ll use a hash. Its key will be the {x, y} position of the house, its value the number of times Santa visited it.

The solution:

#!/usr/bin/env ruby

f = File.read(ARGV.first)

presents = Hash.new(0)
x = 0
y = 0

presents[{x:, y:}] += 1

f.each_char do |c|
  case c
  when '^'
    x += 1
  when 'v'
    x -= 1
  when '>'
    y += 1
  when '<'
    y -= 1
  end
  presents[{x:, y:}] += 1
end

puts "Number of houses that receive at least one present: #{presents.length}"

We create an empty hash and set its default value to 0 instead of nil. This way we can simply increase the value once Santa visits the house. We track the current position in the x and y variables. Then we simply iterate over the input character-by-character, adjust the current position and record the visit in the hash. At last, we calculate the length of the hash, which will be the number of entries in it, hence the number of houses visited.

The second half of the puzzle

The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.

Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.

This year, how many houses receive at least one present?

For example:

^v delivers presents to 3 houses, because Santa goes north, and then Robo-Santa goes south.

^>v< now delivers presents to 3 houses, and Santa and Robo-Santa end up back where they started.

^v^v^v^v^v now delivers presents to 11 houses, with Santa going one direction and Robo-Santa going the other.

This is a bit trickier: we have to track two sets of coordinates: one for Santa, and another for Robo-Santa. We also have to split the input in two.

The solution:

#!/usr/bin/env ruby

f = File.read(ARGV.first)

presents = Hash.new(0)
santa = 0
positions = [{x: 0, y: 0}, {x: 0, y: 0}]

presents[positions[santa].clone] += 1

f.each_char do |c|
  case c
  when '^'
    positions[santa][:x] += 1
  when 'v'
    positions[santa][:x] -= 1
  when '>'
    positions[santa][:y] += 1
  when '<'
    positions[santa][:y] -= 1
  end
  presents[positions[santa].clone] += 1
  santa ^= 1
end

puts "Number of houses that receive at least one present: #{presents.length}"

The trick here is to use the santa variable as a toggle: it’ll be 0 initially (the first character is a direction for Santa), then after each loop, we XOR it with 1, so it’ll change from 0 to 1 (to indicate that it’s a direction for Robo-Santa), then in the next loop, from 1 back to 0. We use it to select the appropriate index in the positions array: positions[0] for Santa, positions[1] for Robo-Santa. It’s also important to .clone the position hash before using it as a key in the presents hash: otherwise, we’d change the position of the previously saved presents retroactively.

The code with my input text is available in the GitHub repo.

Thanks for reading! If you have any comments, additions, or corrections, feel free to reach me via e-mail.