Advent of Code 2022: Day 12

There are a few considerations needed for Icon collections: it is convenient to store coordinates in a record type, but these cannot be directly tested for membership, e.g. when using a set/list to store the visited positions. However, generators can help:

  if not equal_posn(!visited_nodes, current_posn) then {
    # ...
  }

will check that there is no visited node which is equal (according to equal_posn) to the current_posn.

However, for optimal performance, make the record a value type, meaning that there is only one instance for each value, so they can be compared using ===. As our world has limited dimensions, we can create an instance for each coordinate when we load the dataset:

  posn_list := list()                           # <1>
  every i := 1 to *world.heights do {
    row := list()
    every j := 1 to *world.heights[i] do {
      put(row, posn(i, j))                      # <2>
    }
    put(posn_list, row)
  }

1. global variable stores each pre-computed posn instance
2. precomputes each posn instance

Then, instead of creating a new instance using posn(x, y), we use posn_new, which looks up the precomputed value:

procedure posn_new(x, y)
  return posn_list[x][y]
end

This improvement takes effect when testing if a posn has been visited before: with the value type, we can use a set and member will test if our record instance is a member of the set using ===. Making this change dramatically improves the speed of the code.

For part 2, it is convenient to start from the end point and find all paths to the required elevation (a point equalling "S" or "a"). The find_path procedure from part 1 was extended to take parameters for the end condition and steps, and generates possible paths.

Possible improvement:

• remove steps/steps_backward duplication with a single incidence matrix

Final Program

global posn_list

procedure main(inputs)
  local filename

  if *inputs = 1 then {
    filename := inputs[1]

    # Part 1 solution
    write("Part 1: ", part_1(filename))
    # Part 2 solution 
    write("Part 2: ", part_2(filename))
  } else {
    write("Provide a filename of data")
  }
end

procedure part_1(filename)
  local shortest_path, world

  world := read_data(filename)
  if shortest_path := find_path(world, world.start_posn, world.steps, is_end) then
    return *shortest_path-1 # number of steps
  else
    stop("Could not find a path")
end

procedure part_2(filename)
  local path, shortest_overall, world

  world := read_data(filename)
  shortest_overall := *world.heights * *world.heights[1]
  every path := find_path(world, world.end_posn, world.steps_backward, desired_elevation) do {
    if *path - 1 < shortest_overall then
      shortest_overall := *path - 1
  }

  return shortest_overall
end

# Read in data as a list of strings, returning heightmap instance
procedure read_data(filename)
  local file, i, j, neighbour, pts, pts_backward, row, row_backward, world

  world := heightmap(list(), &null, &null, list(), list())
  file := open(filename, "r") | stop("Cannot open ", filename)
  every put(world.heights, !file)
  close(file)

  # create posn instance for each location
  posn_list := list()
  every i := 1 to *world.heights do {
    row := list()
    every j := 1 to *world.heights[i] do {
      put(row, posn(i, j))
    }
    put(posn_list, row)
  }

  # find end and start positions
  every i := 1 to *world.heights do 
    every j := 1 to *world.heights[i] do
      case world.heights[i][j] of {
        "E": world.end_posn := posn_new(i, j)
        "S": world.start_posn := posn_new(i, j)
      }

  # create valid steps
  every i := 1 to *world.heights do {
    row := list()
    row_backward := list()
    every j := 1 to *world.heights[i] do {
      pts := list()
      pts_backward := list()
      every neighbour := neighbours(world, posn_new(i, j)) do {
        if valid_height_step(world, posn_new(i, j), neighbour) then 
          put(pts, neighbour)
        if valid_height_step(world, neighbour, posn_new(i, j)) then 
          put(pts_backward, neighbour)
      }
      put(row, pts)
      put(row_backward, pts_backward)
    }
    put(world.steps, row)
    put(world.steps_backward, row_backward)
  }

  return world
end

# Uses breadth-first search to find the shortest path 
#
# [world] is an instance of heightmap record
# [start_posn] is the starting position, as a posn instance
# [steps] is a 2d array linking to a list of candidate moves
# [end_condition] is a procedure succeeding at the target end position
procedure find_path(world, start_posn, steps, end_condition)
  local current_path, paths, step, visited_posns

  visited_posns := set()
  paths := [[start_posn]] # initial path at start position
  while *paths > 0 do {
    current_path := pop(paths) # consider the shortest path
    if end_condition(world, current_path[1]) then { # is this the end state?
      suspend current_path # success
    } else { # try to extend the path
      every step := !steps[current_path[1].x, current_path[1].y] do {
        if not member(visited_posns, step) then {
          put(paths, push(copy(current_path), step))
          insert(visited_posns, step)
        }
      }
    }
  }
  fail
end

# Goal state for part 1 is the node at elevation "E"
procedure is_end(world, current_posn)
  return world.heights[current_posn.x, current_posn.y] == "E"
end

# Goal state for part 2 is a backwards search to a position of elevation "a" or "S"
procedure desired_elevation(world, current_posn)
  return world.heights[current_posn.x, current_posn.y] == ("S" | "a")
end

# Generates the geographic neighbours of current position
procedure neighbours(world, current_posn)
  if current_posn.x > 1 then
    suspend posn_new(current_posn.x - 1, current_posn.y)
  if current_posn.x < *world.heights then
    suspend posn_new(current_posn.x + 1, current_posn.y)
  if current_posn.y > 1 then
    suspend posn_new(current_posn.x, current_posn.y - 1)
  if current_posn.y < *world.heights[1] then
    suspend posn_new(current_posn.x, current_posn.y + 1)
end

# End position must be at most one step above start position
procedure valid_height_step(world, start_posn, end_posn)
  local end_height, start_height

  start_height := world.heights[start_posn.x, start_posn.y]
  start_height := if "S" == start_height then ord("a") else ord(start_height)
  end_height := world.heights[end_posn.x, end_posn.y]
  end_height := if "E" == end_height then ord("z") else ord(end_height)

  return start_height >= end_height - 1
end

# Positions are stored in posn record
record posn(x, y)

# Retrieves pre-created posn instance
procedure posn_new(x, y)
  return posn_list[x][y]
end

# Heightmap structure records height map, valid steps, start and end
record heightmap(heights, start_posn, end_posn, steps, steps_backward)

# Writes an individual path
procedure write_path(path)
  writes("Path: ")
  every position := !path do
    writes("(", position.x, ",", position.y, ") ")
  write()
end