Advent of Code 2022, Day 12: Hill Climbing Algorithm

#ruby #advent of code 2022

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:

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

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