From 1cb3dcd5ee41d5ce3646c1165cb875629cc4d6e2 Mon Sep 17 00:00:00 2001 From: An0nSaiko Date: Mon, 12 Dec 2022 16:32:32 +0200 Subject: Day 12 --- day12/example.txt | 5 ++++ day12/input.txt | 41 ++++++++++++++++++++++++++++ day12/solution.nim | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 126 insertions(+) create mode 100644 day12/example.txt create mode 100644 day12/input.txt create mode 100644 day12/solution.nim (limited to 'day12') diff --git a/day12/example.txt b/day12/example.txt new file mode 100644 index 0000000..86e9cac --- /dev/null +++ b/day12/example.txt @@ -0,0 +1,5 @@ +Sabqponm +abcryxxl +accszExk +acctuvwj +abdefghi diff --git a/day12/input.txt b/day12/input.txt new file mode 100644 index 0000000..bac8753 --- /dev/null +++ b/day12/input.txt @@ -0,0 +1,41 @@ +abccccccccccccccccccaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaa +abcccccccccccccccaaaaaaaaaaacccccccccccccccccccccccccccccccccccccaaaaa +abcaaccaacccccccccaaaaaaaaaacccccccccccccccccccccaaacccccccccccccaaaaa +abcaaaaaaccccccccaaaaaaaaaaaaacccccccccccccccccccaacccccccccccccaaaaaa +abcaaaaaacccaaacccccaaaaaaaaaaaccccccccccccccccccaaaccccccccccccccccaa +abaaaaaaacccaaaaccccaaaaaacaaaacccccccccccaaaacjjjacccccccccccccccccca +abaaaaaaaaccaaaaccccaaaaaaccccccaccccccccccaajjjjjkkcccccccccccccccccc +abaaaaaaaaccaaacccccccaaaccccccaaccccccccccajjjjjjkkkaaacccaaaccaccccc +abccaaacccccccccccccccaaccccaaaaaaaacccccccjjjjoookkkkaacccaaaaaaccccc +abcccaacccccccccccccccccccccaaaaaaaaccccccjjjjoooookkkkcccccaaaaaccccc +abcccccccaacccccccccccccccccccaaaacccccccijjjoooooookkkkccaaaaaaaccccc +abccaaccaaaccccccccccccccccccaaaaacccccciijjooouuuoppkkkkkaaaaaaaacccc +abccaaaaaaaccccccccccaaaaacccaacaaaccciiiiiooouuuuupppkkklllaaaaaacccc +abccaaaaaacccccccccccaaaaacccacccaaciiiiiiqooouuuuuupppkllllllacaccccc +abcccaaaaaaaacccccccaaaaaaccccaacaiiiiiqqqqoouuuxuuupppppplllllccccccc +abccaaaaaaaaaccaaaccaaaaaaccccaaaaiiiiqqqqqqttuxxxuuuppppppplllccccccc +abccaaaaaaaacccaaaaaaaaaaacccaaaahiiiqqqttttttuxxxxuuuvvpppplllccccccc +abcaaaaaaacccaaaaaaaaaaacccccaaaahhhqqqqtttttttxxxxuuvvvvvqqlllccccccc +abcccccaaaccaaaaaaaaaccccccccacaahhhqqqttttxxxxxxxyyyyyvvvqqlllccccccc +abcccccaaaccaaaaaaaacccccccccccaahhhqqqtttxxxxxxxyyyyyyvvqqqlllccccccc +SbcccccccccccaaaaaaaaaccccccccccchhhqqqtttxxxxEzzzyyyyvvvqqqmmlccccccc +abcccccccccccaaaaaaaacccaacccccccchhhppptttxxxxyyyyyvvvvqqqmmmcccccccc +abccccccccccaaaaaaaaaaccaacccccccchhhpppptttsxxyyyyyvvvqqqmmmccccccccc +abcaacccccccaaaaaaacaaaaaaccccccccchhhppppsswwyyyyyyyvvqqmmmmccccccccc +abaaaacccccccaccaaaccaaaaaaacccccccchhhpppsswwyywwyyyvvqqmmmddcccccccc +abaaaaccccccccccaaaccaaaaaaacccccccchhhpppsswwwwwwwwwvvqqqmmdddccccccc +abaaaacccccccccaaaccaaaaaaccccccccccgggpppsswwwwrrwwwwvrqqmmdddccccccc +abccccccaaaaaccaaaacaaaaaaccccccaacccggpppssswwsrrrwwwvrrqmmdddacccccc +abccccccaaaaaccaaaacccccaaccccaaaaaacggpppssssssrrrrrrrrrnmmdddaaccccc +abcccccaaaaaaccaaaccccccccccccaaaaaacggppossssssoorrrrrrrnnmdddacccccc +abcccccaaaaaaccccccccaaaaccccccaaaaacgggoooossoooonnnrrnnnnmddaaaacccc +abccccccaaaaaccccccccaaaacccccaaaaaccgggoooooooooonnnnnnnnndddaaaacccc +abccccccaaaccccccccccaaaacccccaaaaacccgggoooooooffennnnnnnedddaaaacccc +abcccccccccccccccccccaaacccccccaacccccggggffffffffeeeeeeeeeedaaacccccc +abccccccccccccccccccaaacccccaccaaccccccggfffffffffeeeeeeeeeecaaacccccc +abccccccccccccccccccaaaacccaaaaaaaaaccccfffffffaaaaaeeeeeecccccccccccc +abccccccccaacaaccccaaaaaacaaaaaaaaaaccccccccccaaaccaaaaccccccccccccccc +abccccccccaaaaacccaaaaaaaaaaacaaaaccccccccccccaaaccccaaccccccccccaaaca +abcccccccaaaaaccccaaaaaaaaaaacaaaaacccccccccccaaaccccccccccccccccaaaaa +abcccccccaaaaaacccaaaaaaaaaacaaaaaacccccccccccaaccccccccccccccccccaaaa +abcccccccccaaaaccaaaaaaaaaaaaaaccaaccccccccccccccccccccccccccccccaaaaa diff --git a/day12/solution.nim b/day12/solution.nim new file mode 100644 index 0000000..20f42b3 --- /dev/null +++ b/day12/solution.nim @@ -0,0 +1,80 @@ +import strutils +import sequtils +import sugar +import sets + +type + Position = tuple + row: int + col: int + + Input = tuple + grid: seq[seq[int]] + S: Position + E: Position + +proc parseFile(content: seq[string]): Input = + var content = content + for r, row in content: + for c, e in row: + case e: + of 'S': + result.S = (r, c) + content[r][c] = chr(ord('a') - 1) + of 'E': + result.E = (r, c) + content[r][c] = chr(ord('z') + 1) + else: + discard + + result.grid = map( + content, + (line) => map( + line, + (ch) => ord(ch) - ord('a') + ) + ) + +let dpos = [[0, 1], [1, 0], [0, -1], [-1, 0]] +var part1 = true +proc bfs(input: Input): int = + var q: seq[(Position, int)] + var visited: HashSet[Position] + if part1: + q = @[(input.S, 0)] + visited = toHashSet(@[input.S]) + else: + q = @[(input.E, 0)] + visited = toHashSet(@[input.E]) + + let H = input.grid.len() + let W = input.grid[0].len() + + while q.len() > 0: + let cur = q[0][0] + let pathLen = q[0][1] + let curH = input.grid[cur.row][cur.col] + q.delete(0) + + if part1: + if cur == input.E: + return pathLen + else: + if curH == 0: + return pathLen + + for d in dpos: + let next = Position((cur.row + d[0], cur.col + d[1])) + if next.row < 0 or next.row >= H or next.col < 0 or next.col >= W: + continue + let nextH = input.grid[next.row][next.col] + let gap = if part1: (nextH - curH) else: (curH - nextH) + if gap <= 1 and next notin visited: + q.add((next, pathLen+1)) + visited.incl(next) + +let content = readFile("./input.txt").strip().splitLines() +let input = parseFile(content) +echo bfs(input) +part1 = false +echo bfs(input) -- cgit v1.2.3