diff options
author | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-06-15 22:20:32 -0600 |
commit | 8e313e2614c7a0fe5af924febdbacc650e33835e (patch) | |
tree | 63426b6942ceebe17708140c972a7d7451bd2f74 /23_2021.py | |
download | aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.tar.gz aoc-8e313e2614c7a0fe5af924febdbacc650e33835e.zip |
intial
Diffstat (limited to '23_2021.py')
-rw-r--r-- | 23_2021.py | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/23_2021.py b/23_2021.py new file mode 100644 index 0000000..46eed5c --- /dev/null +++ b/23_2021.py @@ -0,0 +1,130 @@ +import re +import functools + + +def run(filename): + inp = re.findall(r"[A-Z]+", open(filename).read()) + + def solve(part2=False): + A = [inp[0], inp[4]] if not part2 else [inp[0], "D", "D", inp[4]] + B = [inp[1], inp[5]] if not part2 else [inp[1], "C", "B", inp[5]] + C = [inp[2], inp[6]] if not part2 else [inp[2], "B", "A", inp[6]] + D = [inp[3], inp[7]] if not part2 else [inp[3], "A", "C", inp[7]] + well_len = 3 if not part2 else 5 + b = tuple([*A, "A", *B, "B", *C, "C", *D, "D"]) + t = tuple(["E" for i in range(11)]) + cost = {"A": 1, "B": 10, "C": 100, "D": 1000} + botTop = {"A": 2, "B": 4, "C": 6, "D": 8} + + @functools.lru_cache(None) + def moveTop(top, i, j): + return all(top[k] == "E" for k in range(min(i, j), max(i, j) + 1) if k != i) + + def frontBot(bot): + for c, i, j in [ + ("A", 0, well_len - 1), + ("B", well_len, well_len * 2 - 1), + ("C", well_len * 2, well_len * 3 - 1), + ("D", well_len * 3, well_len * 4 - 1), + ]: + for k in range(i, j): + if bot[k] != "E": + if not safeBot(bot, c): + yield (botTop[c], k) + break + + def safeBot(bot, char): + return all( + k == char or k == "E" + for k in bot[ + well_len * botTop[char] // 2 + - well_len : well_len * botTop[char] // 2 + ] + ) + + @functools.lru_cache(None) + def brute(bot, top): + if part2 and bot == ( + "A", + "A", + "A", + "A", + "A", + "B", + "B", + "B", + "B", + "B", + "C", + "C", + "C", + "C", + "C", + "D", + "D", + "D", + "D", + "D", + ): + return 0 + if not part2 and bot == ( + "A", + "A", + "A", + "B", + "B", + "B", + "C", + "C", + "C", + "D", + "D", + "D", + ): + return 0 + for i in range(len(top)): + char = top[i] + if char == "E": + continue + j = botTop[char] + if j and moveTop(top, i, j) and safeBot(bot, char): + idx = ( + well_len * botTop[char] // 2 + - well_len + + bot[ + well_len * botTop[char] // 2 + - well_len : well_len * botTop[char] // 2 + ].index(char) + - 1 + ) + return cost[char] * (abs(j - i) + (idx % well_len) + 1) + brute( + bot[:idx] + tuple(top[i]) + bot[idx + 1 :], + top[:i] + tuple("E") + top[i + 1 :], + ) + ans = float("inf") + moves = 0 + for c, i in frontBot(bot): + for j in range(len(top)): + if j in [2, 4, 6, 8] or top[j] != "E" or not moveTop(top, c, j): + continue + moves += 1 + ans = min( + ans, + cost[bot[i]] * (i % well_len + 1 + abs(c - j)) + + brute( + bot[:i] + tuple("E") + bot[i + 1 :], + top[:j] + tuple(bot[i]) + top[j + 1 :], + ), + ) + if moves == 0: + return float("inf") + else: + return ans + + print(brute(b, t)) + + solve(part2=False) + solve(part2=True) + + +run("day23data.txt") |