From ff03dafbae6f53027a1e79e1a60678afc31ebbdf Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Fri, 20 Dec 2024 07:32:59 +0100 Subject: Add 2024 day 20 solutions --- 2024/20/.gitignore | 1 + 2024/20/Makefile | 1 + 2024/20/puzzles.py | 42 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 44 insertions(+) create mode 100644 2024/20/.gitignore create mode 100644 2024/20/Makefile create mode 100644 2024/20/puzzles.py (limited to '2024/20') diff --git a/2024/20/.gitignore b/2024/20/.gitignore new file mode 100644 index 0000000..8931d44 --- /dev/null +++ b/2024/20/.gitignore @@ -0,0 +1 @@ +puzzle-[12].py \ No newline at end of file diff --git a/2024/20/Makefile b/2024/20/Makefile new file mode 100644 index 0000000..6e58a9d --- /dev/null +++ b/2024/20/Makefile @@ -0,0 +1 @@ +include ../../Makefiles/py.mk \ No newline at end of file diff --git a/2024/20/puzzles.py b/2024/20/puzzles.py new file mode 100644 index 0000000..8727f6e --- /dev/null +++ b/2024/20/puzzles.py @@ -0,0 +1,42 @@ +#!/usr/bin/python3 + +def main() -> None: + points: set[complex] = set() + + with open("input", "r") as f: + for i, line in enumerate(f.readlines()): + for j, char in enumerate(line): + if char in "#\n": + continue + points.add(pos := complex(j, i)) + if char == 'S': + start = pos + + print(solve(start, points, 100, 2 if PUZZLE_PART == 1 else 20)) + +def solve( + pos: complex, + points: set[complex], + minsave: int, + maxcheat: int, +) -> int: + path: list[complex] = [] + while points: + path.append(pos) + for v⃗ in [1, -1, 1j, -1j]: + if (p := pos + v⃗) in points: + break + points.remove(pos) + pos = p + + cnt = 0 + for i, p1 in enumerate(path): + off = i + minsave + for j, p2 in enumerate(path[off + 2:], off + 2): + d = p1 - p2 + if abs(d.real) + abs(d.imag) <= min(j - off, maxcheat): + cnt += 1 + return cnt + +if __name__ == "__main__": + main() \ No newline at end of file -- cgit v1.2.3