Advent of Code 2016, Day 13: A Maze of Twisty Little Cubicles

Part A

On Day 13 we have another graph problem. We need to find the shortest path from point A and B on some office floor. But we don’t have a map of this office floor. Instead we have a simple system that can be used to generate office floor map. For given position x, y:

• Find xx + 3x + 2xy + y + y*y.
• Add the office designer’s favorite number (your puzzle input).
• Find the binary representation of that sum; count the number of bits that are 1.
  • If the number of bits that are 1 is even, it’s an open space.
  • If the number of bits that are 1 is odd, it’s a wall.

This is actually quite nice as we don’t need to store this anywhere. It will be possible to just calculate it on the fly when checking if given position is wall or open space.

To find out what is the shortest path we can use BFS. Below is my solution:

@favorite = 1364
start = [1, 1]
destination = [31, 39]

def getNeighbors(x, y)
  neighbors = [
    [x - 1, y],
    [x + 1, y],
    [x, y - 1],
    [x, y + 1]
  ]

  neighbors.select do |(x, y)|
    value = x * x + 3 * x + 2 * x * y + y + y * y
    value += @favorite
    value = value.to_s(2)
    x >= 0 && y >= 0 && value.chars.select { |char| char == "1" }.size.even?
  end
end

visited = { start => true }
distances = { start => 0 }
queue = Queue.new

queue.enq(start)

while !queue.empty?
  current = queue.deq
  distance = distances[current]

  if current == destination
    puts "Arrived at destination in #{distance} steps"
    break
  end

  getNeighbors(*current).each do |neighbor|
    if !visited[neighbor]
      visited[neighbor] = true
      distances[neighbor] = distance + 1
      queue.enq(neighbor)
    end
  end
end

You can see that our getNeighbors method is calculating if neighbors are walls or open spaces and if it is possible to move there.

Part B

In second part we need to answer how many positions you can reach in at most 50 steps. That is also trivial to answer with BFS as this algorithm is actually exploring the graph in all directions at the same pace. Here is slightly modified solution from Part A:

@favorite = 1364
start = [1, 1]
destination = [31, 39]

def getNeighbors(x, y)
  neighbors = [
    [x - 1, y],
    [x + 1, y],
    [x, y - 1],
    [x, y + 1]
  ]

  neighbors.select do |(x, y)|
    value = x * x + 3 * x + 2 * x * y + y + y * y
    value += @favorite
    value = value.to_s(2)
    x >= 0 && y >= 0 && value.chars.select { |char| char == "1" }.size.even?
  end
end

visited = { start => true }
distances = { start => 0 }
queue = Queue.new

queue.enq(start)

destinations = []

while !queue.empty?
  current = queue.deq
  distance = distances[current]

  getNeighbors(*current).each do |neighbor|
    if !visited[neighbor] && distance < 50
      visited[neighbor] = true
      distances[neighbor] = distance + 1
      queue.enq(neighbor)
    end
  end
end

puts distances.size