# 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.
• 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
``````