aoc-2022/day12/task2.nim
2022-12-12 17:14:57 +02:00

94 lines
1.9 KiB
Nim

import system/io
import strutils
import sequtils
import tables
import sugar
const
SYM_START = 'S'
SYM_END = 'E'
SYM_LOWEST = 'a'
type
Coords = tuple
x, y: int
proc diff(a, b: int): int =
if a > b: a - b
else: b - a
proc height(i: char): int =
(
case i:
of SYM_START:
'a'
of SYM_END:
'z'
else:
i
).ord
var startPoint: Coords
var endPoint: Coords
var lowestPoints = newSeq[Coords]()
var adjacents = initTable[Coords, seq[Coords]]()
let heightMap = collect(
for line in stdin.readAll.split:
if line != "": line
)
for x in 0 .. heightMap.len - 1:
for y in 0 .. heightMap[x].len - 1:
var adjs = newSeq[Coords](0)
let h = heightMap[x][y].height
case heightMap[x][y]:
of SYM_START:
startPoint = (x, y)
of SYM_END:
endPoint = (x, y)
of SYM_LOWEST:
lowestPoints.add((x, y))
else: discard
if y > 0 and h - heightMap[x][y - 1].height < 2:
adjs.add((x, y - 1))
if y < heightMap[x].len - 1 and h - heightMap[x][y + 1].height < 2:
adjs.add((x, y + 1))
if x > 0 and h - heightMap[x - 1][y].height < 2:
adjs.add((x - 1, y))
if x < heightMap.len - 1 and h - heightMap[x + 1][y].height < 2:
adjs.add((x + 1, y))
adjacents[(x, y)] = adjs
var unvisited = adjacents.keys.toSeq
var shortest = collect(initTable()):
for node in unvisited:
{node: high(int) - 1}
shortest[endPoint] = 0
while unvisited.len != 0:
var current_min: Coords = (-1, -1)
for node in unvisited:
if current_min.x == -1 or shortest[node] < shortest[current_min]:
current_min = node
for adj in adjacents[current_min]:
let t = shortest[current_min] + 1
if t < shortest[adj]:
shortest[adj] = t
unvisited.del(unvisited.find(current_min))
var min = high(int)
for node in lowestPoints:
if shortest[node] < min:
min = shortest[node]
echo min