summaryrefslogtreecommitdiff
path: root/23_2021.py
diff options
context:
space:
mode:
Diffstat (limited to '23_2021.py')
-rw-r--r--23_2021.py130
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")