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")