diff options
| author | Marvin Borner | 2022-12-12 07:10:21 +0100 |
|---|---|---|
| committer | Marvin Borner | 2022-12-12 07:10:21 +0100 |
| commit | f81b753df8edf2219772dde7bf6d80215640a594 (patch) | |
| tree | b804b1bb6ddeaf6db46c37263eb039d0c2fa3c87 /2022/12 | |
| parent | 4af6738bb5665a299d590d6f04d9bf61944b9a28 (diff) | |
hm
Diffstat (limited to '2022/12')
| -rw-r--r-- | 2022/12/input | 41 | ||||
| -rw-r--r-- | 2022/12/solve.py | 46 |
2 files changed, 87 insertions, 0 deletions
diff --git a/2022/12/input b/2022/12/input new file mode 100644 index 0000000..ce89a91 --- /dev/null +++ b/2022/12/input @@ -0,0 +1,41 @@ +abaccccccccccccccaaaccccaaaaaaaaaaaaaccccccaacccccccccccccccccccccccccccccaaaaaa +abaaccaacccccccccaaaaaccccaaaaaaaaaaaaaccccaaacccccccccccccccccccccccccccccaaaaa +abaaccaaacccccccaaaaaacccaaaaaaaaaaaaaacaaaaaaaaccccccccaacccccccccccccccccccaaa +abcaaaaaaaacccccaaaaaacccaaaaaaaaaaaaaacaaaaaaaacccccccaaaacccccccccccccccccaaaa +abcaaaaaaaaccccccaaaaaccaaaaaaaaccaaaaaccaaaaaaccccccccaaaaccaaaccccccccccccaaac +abccaaaaaacccccccaaaaccaaaaaaaaaacaaaacccaaaaaacccccccccakkaaaaaacccccccccccaacc +abccaaaaaacccccccccccccaaaaaaaaaaccccccccaaaaaaccccccckkkkkkkaaacccccccccccccccc +abccaaaaaaccccccccccccccccaaaaaaaaaccccccaacaaacccccckkkkkkkkkaccccccaccaaaccccc +abccaacaaacccccaaccccccccaaacacaaaacaaccccccccccccccakkkoppkkkkicccccaaaaaaccccc +abccccccccccccaaaccccccccaacccccaaaaaaccccccccccccccjkkooppppkiicccccccaaaaccccc +abccccccccccaaaaaaaaccccccccccaaaaaaaccccccccccccccjjjooopppppiiiicccccccaaacccc +abaaacccccccaaaaaaaacccccccaacaaaaaaccccccccccccccjjjjooouuppppiiiiiicccccaacccc +abaaaccccccccaaaaaaccccccccaaaccaaaaacccccccccccjjjjjooouuuupppiiiiiiiiccccacccc +abaaaaaacccccaaaaaacccccaaaaaaaaaacaaaccccccccjjjjjjooouuuuuupppppiiiiiicccccccc +abaaaaaacccccaaaaaacccccaaaaaaaaaacccccccccccjjjjjooooouuxxuupppppqqqijjjccccccc +abaaaacccccaaaaccaaccccccaaaaaaccccccccccccciijjnooooouuuxxxuuupqqqqqqjjjdddcccc +abaaaaaccaaaaaaccacccccccaaaaaaccccccccccaaiiiinnootttuuxxxxuuvvvvvqqqjjjdddcccc +abaaaaaccaaaaaacaaaccaaccaaaaaaccccccccccaaiiinnnntttttuxxxxxvvvvvvqqqjjjdddcccc +abaaccacccaaaaacaaaaaaaccaaccaaccccccccccaaiiinnnttttxxxxxxxyyyyyvvqqqjjjdddcccc +abcccccccaaaaacccaaaaaaccccccaaaaacccccccaaiiinnntttxxxxxxxyyyyyvvvqqqjjjddccccc +SbcccccccaaaaacaaaaaaaaccccccaaaaaccccccccciiinnntttxxxEzzzzyyyyvvqqqjjjdddccccc +abcccccccccccccaaaaaaaaaccccaaaaaaccccccccciiinnnntttxxxxyyyyyvvvvqqjjjdddcccccc +abcccccccccccccaaaaaaaaaacccaaaaaacccccccccciiinnnttttxxxyyyyyvvvqqqjjjdddcccccc +abccccccccccccccccaaaaaaacccaaaaaaccccccccccciiinnnntttwyyywyyyvvrrrkkjdddcccccc +abcccccccccccccccaaaaaaaaccccaaaccccccccccccciiihnnnttwwwywwyyywvrrrkkkeeccccccc +abcccccccccccccccaaaaaaaaccccccccccccccccccccchhhmmmsswwwwwwwwwwwvrrkkkeeccccccc +abcccccccaacccccccacaaacccccccccccccccccccaacchhhhmmsswwwwwswwwwwrrrkkkeeccccccc +abcccccccaaaccacccccaaacccccccccccccccaaccaaccchhhmmssswwwssrrwwwrrrkkkeeccccccc +abcccccccaaaaaaacccccccccccaaaccccccccaaaaaaccchhhmmssssssssrrrrrrrrkkkeeaaacccc +abcccccaaaaaaaaccccccccccccaaaaccccccccaaaaaaachhhmmmssssssllrrrrrrkkkeeeaaacccc +abccccaaaaaaaaaccccccccccccaaaacccccccccaaaaacchhhmmmmsssllllllllkkkkkeeeaaacccc +abccccaaaaaaaaaccccccccccccaaacccccccccaaaaacccchhhmmmmmlllllllllkkkkeeeeaaccccc +abcccccccaaaaaaccccccccccaacccccccaaccaaacaacccchhhmmmmmlllgfflllkkffeeeaaaacccc +abccccccaaaaaaaccccccccccaaaaaaaaaaaaaccccaacccchhhggmmmggggffffffffffeaaaaacccc +abccaacccaacccaaaaccaccccaaaaaaaaaaaaacccccccccccgggggggggggffffffffffaacccccccc +abaaaaccaaaccccaaaaaaccccaaaaaacaaaaaaccccccccccccgggggggggaaaaccffccccccccccccc +abaaaacccccccccaaaaaaccaaaaaaaaaaaaaacccccccccccccccgggaaaaaaaacccccccccccccccca +abaaaaacccccccaaaaaaaccaaaaaaaaaaaaaacccccccccccccccccaaacccaaaaccccccccccccccaa +abaaaaacaaaaccaaaaaaaacaaaaaaaaaaaccccccccccccccccccccaaaccccaaaccccccccccaaacaa +abaaaaacaaaaccaaaaaaaaaaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaaa +abaaacccaaaaccccaaaccccaaaaaaaaaaacccccccccccccccccccccccccccccccccccccccccaaaaa diff --git a/2022/12/solve.py b/2022/12/solve.py new file mode 100644 index 0000000..e6a839e --- /dev/null +++ b/2022/12/solve.py @@ -0,0 +1,46 @@ +import collections +import math + +data = [ + [ord(x) - ord("a") for x in list(dat.strip())] + for dat in open("input").readlines() + if dat != "" +] + + +# literally straight out of my lecture +def bfs(grid, start, target): + steps = [[math.inf] * len(grid[0]) for row in range(len(grid))] + steps[start[0]][start[1]] = 0 + Q = collections.deque([start]) + while Q: + prev = Q.popleft() + for dest in [(-1, 0), (1, 0), (0, -1), (0, 1)]: + # WHY CAN'T PYTHON ADD TUPLES?! + new = (prev[0] + dest[0], prev[1] + dest[1]) + if ( + 0 <= new[0] < len(grid) + and 0 <= new[1] < len(grid[0]) + and steps[new[0]][new[1]] == math.inf + and grid[new[0]][new[1]] - grid[prev[0]][prev[1]] <= 1 + ): + steps[new[0]][new[1]] = steps[prev[0]][prev[1]] + 1 + Q.append(new) + return steps[target[0]][target[1]] + + +def solve(): + S = [x for x in data if -14 in x][0] + E = [x for x in data if -28 in x][0] + S = (data.index(S), S.index(-14)) + E = (data.index(E), E.index(-28)) + data[S[0]][S[1]] = 0 + data[E[0]][E[1]] = 25 + print(f"Part 1: {bfs(data, S, E)}") + # inefficient solutions are quite effective + print( + f"Part 2: {min(sum([[bfs(data, (y, x), E) for x in range(len(data[y])) if data[y][x] == 0] for y in range(len(data))], []))}" + ) + + +solve() |