# Advent of Code 2022, Day 12: Hill Climbing Algorithm

## Part A

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:

• Create an empty queue and a hash of visited nodes
• Add starting node to the queue and mark it as visited
• While queue is not empty:
• Get first element from the queue
• If it is our target, stop
• Add all not visited neighbors to the queue

``````@start = nil
@destination = nil

@data = File.
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.
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
``````

## Part B

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