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 x
*x + 3*x + 2*x*y + 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.

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
```