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) }

- global variable stores each pre-computed posn instance
- 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

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