On Day 12 we need to implement pathfinding algorithm, so you can guess some graphs algorithms are necessary.
Our input is map like this:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Each character represents the height of that position. ‘a’ is the lowest point and ‘z’ is the highest. ‘S’ represents starting point (and lowest height) and ‘E’ represents our target point (and highest height). We need to find what is the shortest path (how many steps), but we can only move to the nearby point if it’s height is no more that 1 unit higher. When going down you can move to any field if it is lower.
Here is example path for the above input:
v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^
To solve this task we can implement Breadth-first search (BFS) algorithm, which goes like this:
Let’s start with reading and parsing input data:
@start = nil
@destination = nil
@data = File.
readlines("12.txt", chomp: true).
map.with_index do |row, y|
row.strip.split("").map.with_index do |cell, x|
if cell == "S"
@start = [x, y]
cell = "a"
elsif cell == "E"
@destination = [x, y]
cell = "z"
end
cell = cell.ord - 'a'.ord
end
end
After reading we are converting characters into numbers for easier calculations. This cell = cell.ord - 'a'.ord converts a to z into 0 to 25. We can also replace ‘S’ into ‘a’ and ‘E’ into ‘z’.
Now we can use some helper methods:
def getHeight(x, y)
@data[y][x]
end
def validNeighbor?(x, y)
x >= 0 && x < @data[0].size && y >= 0 && y < @data.size
end
def getNeighbors(x, y)
height = getHeight(x, y)
neighbors = [
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
]
neighbors.map do |neighbor|
if validNeighbor?(*neighbor) && (getHeight(*neighbor) - height) <= 1
neighbor
end
end.compact
end
validNeighbor? checks if neighbor is within map limits, getNeighbors returns all neighbors for given node, it first lists all possible neighbors (left, right, up and down) and then removes those that are outside of the map or if they are more than 1 unit higher.
And now BFS:
queue = Queue.new
visited = { @start => true }
distances = { @start => 0 }
queue.enq(@start)
while !queue.empty?
x, y = queue.deq
distance = distances[[x, y]]
if [x, y] == @destination
puts "Arrived at destination in #{distance} steps"
break
end
neighbors = getNeighbors(x, y)
neighbors.each do |neighbor|
if !visited[neighbor]
visited[neighbor] = true
distances[neighbor] = distance + 1
queue.enq(neighbor)
end
end
end
We are also maintaining the distances to each node from the start. Here is the full code:
@start = nil
@destination = nil
@data = File.
readlines("12.txt", chomp: true).
map.with_index do |row, y|
row.strip.split("").map.with_index do |cell, x|
if cell == "S"
@start = [x, y]
cell = "a"
elsif cell == "E"
@destination = [x, y]
cell = "z"
end
cell = cell.ord - 'a'.ord
end
end
def getHeight(x, y)
@data[y][x]
end
def validNeighbor?(x, y)
x >= 0 && x < @data[0].size && y >= 0 && y < @data.size
end
def getNeighbors(x, y)
height = getHeight(x, y)
neighbors = [
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
]
neighbors.map do |neighbor|
if validNeighbor?(*neighbor) && (getHeight(*neighbor) - height) <= 1
neighbor
end
end.compact
end
queue = Queue.new
visited = { @start => true }
distances = { @start => 0 }
queue.enq(@start)
while !queue.empty?
x, y = queue.deq
distance = distances[[x, y]]
if [x, y] == @destination
puts "Arrived at destination in #{distance} steps"
break
end
neighbors = getNeighbors(x, y)
neighbors.each do |neighbor|
if !visited[neighbor]
visited[neighbor] = true
distances[neighbor] = distance + 1
queue.enq(neighbor)
end
end
end
In Part B we can start from any node that is at the lowest level. So all the code is the same, we just need to add all starting points to the queue with distance 0. Below is the full code:
@start = []
@destination = nil
@data = File.
readlines("12.txt", chomp: true).
map.with_index do |row, y|
row.strip.split("").map.with_index do |cell, x|
if cell == "S"
cell = "a"
elsif cell == "E"
@destination = [x, y]
cell = "z"
end
if cell == "a"
@start.push([x, y])
end
cell = cell.ord - 'a'.ord
end
end
def getHeight(x, y)
@data[y][x]
end
def validNeighbor?(x, y)
x >= 0 && x < @data[0].size && y >= 0 && y < @data.size
end
def getNeighbors(x, y)
height = getHeight(x, y)
neighbors = [
[x - 1, y],
[x + 1, y],
[x, y - 1],
[x, y + 1]
]
neighbors.map do |neighbor|
if validNeighbor?(*neighbor) && (getHeight(*neighbor) - height) <= 1
neighbor
end
end.compact
end
queue = Queue.new
visited = { }
distances = { }
@start.each do |start|
visited[start] = true
distances[start] = 0
queue.enq(start)
end
while !queue.empty?
x, y = queue.deq
distance = distances[[x, y]]
if [x, y] == @destination
puts "Arrived at destination in #{distance} steps"
break
end
neighbors = getNeighbors(x, y)
neighbors.each do |neighbor|
if !visited[neighbor]
visited[neighbor] = true
distances[neighbor] = distance + 1
queue.enq(neighbor)
end
end
end