adventofcode day 24

day_24_part1.py

class Solution:
    def day24(self, input: str) -> int:
        
        def input_to_state(input):
            input = input.strip()
            grid = []
            for line in input.split("\n"):
                row = []
                for c in line:
                    if c == '.':
                        row.append(set())
                    else:
                        row.append(set([c]))
                grid.append(row)
            return grid

        state = input_to_state(input)
        nr, nc = len(state), len(state[0])

        def next_state(state):
            state_new = [[set() for _ in range(nc)] for _ in range(nr)]
            for ir in range(nr):
                for ic in range(nc):
                    for c in state[ir][ic]:
                        if c == "#":
                            state_new[ir][ic].add(c)
                            continue
                        if c == ">":
                            ir_new = ir
                            ic_new = ic+1 if ic+1 <= nc-2 else 1
                        elif c == "<":
                            ir_new = ir
                            ic_new = ic-1 if ic-1 >= 1 else nc-2
                        elif c == "v":
                            ir_new = ir+1 if ir+1 <= nr-2 else 1
                            ic_new = ic
                        elif c == "^":
                            ir_new = ir-1 if ir-1 >= 1 else nr-2
                            ic_new = ic
                        state_new[ir_new][ic_new].add(c)

            return state_new

        def get_next_pos(pos_prev, state):
            poss = []
            ir, ic = pos_prev
            for ir_nx, ic_nx in ((ir,ic),(ir+1,ic),(ir-1,ic),(ir,ic+1),(ir,ic-1)):
                if 0 <= ir_nx <= nr-1 and 0 <= ir_nx <= nr-1 and len(state[ir_nx][ic_nx]) == 0:
                    yield (ir_nx,ic_nx)

        start = (0,1)
        end = (nr-1, nc-2)
        # print(state)
        poss_prev = {start}
        step = 0
        while step <= 10000000:
            step += 1
            state = next_state(state)
            # print(f"step:{step}, state:\n{state}")
            poss_new = set()
            for pos_prev in poss_prev:
                for pos in get_next_pos(pos_prev, state):
                    if pos == end:
                        return step
                    poss_new.add(pos)
            poss_prev = poss_new

# test
input = """
#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
"""
print(Solution().day24(input))

day_24_part2.py

class Solution:
    def day24(self, input: str) -> int:
        
        def input_to_state(input):
            input = input.strip()
            grid = []
            for line in input.split("\n"):
                row = []
                for c in line:
                    if c == '.':
                        row.append(set())
                    else:
                        row.append(set([c]))
                grid.append(row)
            return grid

        state = input_to_state(input)
        nr, nc = len(state), len(state[0])

        def next_state(state):
            state_new = [[set() for _ in range(nc)] for _ in range(nr)]
            for ir in range(nr):
                for ic in range(nc):
                    for c in state[ir][ic]:
                        if c == "#":
                            state_new[ir][ic].add(c)
                            continue
                        if c == ">":
                            ir_new = ir
                            ic_new = ic+1 if ic+1 <= nc-2 else 1
                        elif c == "<":
                            ir_new = ir
                            ic_new = ic-1 if ic-1 >= 1 else nc-2
                        elif c == "v":
                            ir_new = ir+1 if ir+1 <= nr-2 else 1
                            ic_new = ic
                        elif c == "^":
                            ir_new = ir-1 if ir-1 >= 1 else nr-2
                            ic_new = ic
                        state_new[ir_new][ic_new].add(c)

            return state_new

        def get_next_pos(pos_prev, state):
            poss = []
            ir, ic = pos_prev
            for ir_nx, ic_nx in ((ir,ic),(ir+1,ic),(ir-1,ic),(ir,ic+1),(ir,ic-1)):
                if 0 <= ir_nx <= nr-1 and 0 <= ir_nx <= nr-1 and len(state[ir_nx][ic_nx]) == 0:
                    yield (ir_nx,ic_nx)

        def get_steps(state, start, end):
            poss_prev = {start}
            step = 0
            while step <= 10000000:
                step += 1
                state = next_state(state)
                # print(f"step:{step}, state:\n{state}")
                poss_new = set()
                for pos_prev in poss_prev:
                    for pos in get_next_pos(pos_prev, state):
                        if pos == end:
                            return step, state
                        poss_new.add(pos)
                poss_prev = poss_new

        # main
        start = (0,1)
        end = (nr-1, nc-2)
        # print(state)
        step = 0
        step_new, state_new = get_steps(state, start, end)
        print(f"step_new:{step_new}")
        step += step_new
        step_new, state_new = get_steps(state_new, end, start)
        print(f"step_new:{step_new}")
        step += step_new
        step_new, state_new = get_steps(state_new, start, end)
        print(f"step_new:{step_new}")
        step += step_new
        return step

# test
input = """
#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
"""
print(Solution().day24(input))