day13_part2.py

day13_part2.py

#!/usr/bin/env python3

def solve(pattern: list[str]) -> int:
    n = len(pattern)
    m = len(pattern[0])

    rows = []
    repeated_rows = []
    for i in range(n):
        x = 0
        for j in range(m):
            if pattern[i][j] == '#':
                x |= 1 << j
        if i > 0 and (x ^ rows[-1]).bit_count() < 2:
            repeated_rows.append((i, (x ^ rows[-1]).bit_count()))
        rows.append(x)
    
    columns = []
    repeated_columns = []
    for j in range(m):
        x = 0
        for i in range(n):
            if pattern[i][j] == '#':
                x |= 1 << i
        if j > 0 and (x ^ columns[-1]).bit_count() < 2:
            repeated_columns.append((j, (x ^ columns[-1]).bit_count()))
        columns.append(x)

    ans = 0
    for column, bit_count in repeated_columns:
        left = column - 2
        right = column + 1
        while left >= 0 and right < m and (columns[left] == columns[right] or (not bit_count and (columns[left] ^ columns[right]).bit_count() == 1)):
            bit_count += (columns[left] ^ columns[right]).bit_count()
            left -= 1
            right += 1

        if (left < 0 or right == m) and bit_count == 1:
            ans += column
    
    for row, bit_count in repeated_rows:
        left = row - 2
        right = row + 1
        while left >= 0 and right < n and (rows[left] == rows[right] or (not bit_count and (rows[left] ^ rows[right]).bit_count() == 1)):
            bit_count += (rows[left] ^ rows[right]).bit_count()
            left -= 1
            right += 1
        
        if (left < 0 or right == n) and bit_count == 1:
            ans += 100 * row

    return ans


with open("input.txt") as f:
    pattern = []
    ans = 0
    for line in f:
        line = line.strip()
        if not line:
            ans += solve(pattern)
            pattern = []
        else:
            pattern.append(line)
    ans += solve(pattern)

    print(ans)