advent_of_code_2022_day_12.nim

import tables, sets, deques, strformat, sugar

type Point = tuple[x: int, y: int]

proc loadMap(filename: string): (Table[Point, int], Point, Point) =
    var y: int
    var map: Table[Point, int]
    var source: Point
    var destination: Point
    for line in filename.lines:
        for (x, cell) in line.pairs:
            if cell == 'S':
                source = (x, y)
                map[source] = ord('a')
            elif cell == 'E':
                destination = (x, y)
                map[destination] = ord('z')
            else:
                map[(x, y)] = ord(cell)
        inc(y)
    (map, source, destination)

proc getNeighbours(map: Table[Point, int], at: Point, cmpFun: (int, int) -> bool): seq[Point] =
    let current = map[at]
    for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        let x = at.x + dx
        let y = at.y + dy
        if map.hasKey((x, y)) and cmpFun(current, map[(x, y)]): 
            result.add((x, y))

proc shortestPath(map: Table[Point, int], start: Point, stop: Point, cmpFun: (int, int) -> bool): (int, Table[Point, Point]) =
    var previous: Table[Point, Point]
    var visited: HashSet[Point]
    var queue: Deque[tuple[point: Point, distance: int]]
    queue.addLast((start, 0))
    visited.incl(start)

    while queue.len > 0:
        let (point, distance) = queue.popFirst()

        if (point == stop): return (distance, previous)

        for neighbour in getNeighbours(map, point, cmpFun):
            if not visited.contains(neighbour):
                previous[neighbour] = point
                queue.addLast((neighbour, distance + 1))
                visited.incl(neighbour)

    return (-1, previous)

let (map, source, destination) =  loadMap("day-12/input.txt") 

let (distance, path) = shortestPath(map, source, destination, (current, next) => next - current <= 1)
assert path.len > 0
assert distance > 0

echo fmt"Shortest path length: {distance}"

let (failedDistance, allPath) = shortestPath(map, destination, (-1, -1), (current, next) => current - next <= 1)
assert failedDistance == -1

var minDistance = high(int)
for key in map.keys:
    if map[key] == ord('a') and allPath.hasKey(key):
        var distance: int
        var curPoint = key
        while allPath.hasKey(curPoint):
            curPoint = allPath[curPoint]
            distance.inc
        if distance < minDistance:
            minDistance = distance

echo fmt"Shortest path length from any 'a' point: {minDistance}"