aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2022/nim/day12/src/main.nim73
1 files changed, 73 insertions, 0 deletions
diff --git a/2022/nim/day12/src/main.nim b/2022/nim/day12/src/main.nim
new file mode 100644
index 0000000..b6bcc41
--- /dev/null
+++ b/2022/nim/day12/src/main.nim
@@ -0,0 +1,73 @@
+# Day 12: Hill Climbing Algorithm
+import std/[os, strutils, sequtils, sets, terminal]
+
+type Cell = tuple[x: int, y: int]
+
+# slow slow slow
+let input = paramStr(1).readFile().strip().split("\n")
+var grid = input.mapIt(it.toSeq())
+
+proc calc_start(): Cell = # slow
+ for i, line in grid:
+ for j, elevation in line:
+ if elevation == 'S':
+ grid[i][j] = '`'
+ return (i, j)
+
+proc calc_goal(): Cell = # slow
+ for i, line in grid:
+ for j, elevation in line:
+ if elevation == 'E':
+ grid[i][j] = '{' # lol
+ return (i, j)
+
+proc valid(fr, to: Cell, visited: HashSet[Cell], desc: bool): (bool, bool) =
+ if (to.x >= 0) and (to.y >= 0) and (to.x < grid.len) and (to.y < grid[0].len):
+ if to notin visited:
+ let sign = if desc: -1 else: 1
+ if sign * (grid[to.x][to.y].ord - grid[fr.x][fr.y].ord) < 2:
+ if not desc and grid[to.x][to.y] == '{':
+ return (true, true)
+ if desc and grid[to.x][to.y] == 'a':
+ return (true, true)
+ return (true, false)
+ return (false, false)
+
+proc print(cells: HashSet[Cell]) =
+ eraseScreen()
+ for i, line in grid:
+ for j, ele in line:
+ if (i, j) in cells:
+ stdout.write("█")
+ else:
+ stdout.write(ele)
+ stdout.write("\n")
+ sleep(100)
+
+proc search(start: Cell, desc: bool): int =
+ var current = @[start].toHashSet()
+ var visited: HashSet[Cell]
+
+ var steps = 0
+ while true:
+ steps += 1
+ var temp: HashSet[Cell]
+ for c in current:
+ var neighbors: HashSet[Cell]
+ let cells: array[4, Cell] = [(c.x+1, c.y), (c.x-1, c.y), (c.x, c.y+1), (c.x, c.y-1)]
+ for cell in cells:
+ let (valid, success) = valid(c, cell, visited, desc)
+ if success:
+ return steps
+ if valid:
+ neighbors.incl(cell)
+ visited.incl(c)
+ temp.incl(neighbors)
+ current = temp
+ # print(visited)
+
+let start = calc_start()
+let goal = calc_goal()
+
+echo search(start, false)
+echo search(goal, true)