aoc_2023_12.py

name = 'test0'
name = 'input'
lines = list(open(name).read().splitlines())
data = [line.split() for line in lines]
data = [(a, [int(x) for x in b.split(',')]) for (a,b) in data]

def unfold(data):
    return [('?'.join([a]*5), b+b+b+b+b) for (a,b) in data]

def place_centermost(string, runs):
    """yields (i,j)

    where
        i is the index of the run to place
        j is the position in the string"""

    if len(runs) == 0:  # should not happen
        return 1/0
    i = len(runs)//2
    length = runs[i]
    to_the_left = sum(runs[:i]) + i
    to_the_right = sum(runs[i+1:]) + len(runs)-i-1
    #print(f'{to_the_left=} {to_the_right=} {len(string)-to_the_right-length+1=}')
    for j in range(to_the_left, len(string)-to_the_right-length+1):
        #print(string)
        #print(' '*j + '^'*length, j)
        if set(ss := string[j:j+length]) <= {'#', '?'}:
            if j>0 and string[j-1] == '#':
                #print('nope: # to the left')
                continue
            if j+length<len(string) and string[j+length] == '#':
                #print(f'nope: # to the right at {j+length}')
                continue
            #print('yep')
            yield i, j
        else:
            #print('nope:', ss)
            pass


def recurse(string, runs, offset=0):
    """returns the number of ways you can place runs in string"""

    print = lambda *_: None
    
    indent=" "*offset
    if len(runs) == 0:
        result = int(set(string) <= {'.', '?'})
        print(f'{indent}{string} {runs} no more runs to place: {result}')
        return result

    accu = 0
    for i, j in place_centermost(string, runs):
        print(f'{indent}{string[:j]}[{string[j:j+runs[i]]}]{string[j+runs[i]:]} '
              f'{",".join(str(x) for x in runs[:i])},[{runs[i]}],{",".join(str(x) for x in runs[i+1:])}')
        # if we place run #i at positions j,j+1,...,j+length(run #i)
        # then how many ways can we place the rest of the runs?
        left = string[:j]
        if i > 0:
            # we need to fit at least one more piece
            # so take one cell away to delimit
            if len(left) == 0:
                # out of space on the left
                continue
            left = left[:-1]
        right = string[j+runs[i]:]
        if i < len(runs)-1:
            # we need to fit at least one more piece
            if len(right) == 0:
                # out of space on the right
                continue
            right = right[1:]

        inc = recurse(left, runs[:i], offset+1) * recurse(right, runs[i+1:], offset+1)
        print(f'{indent}->{inc}')
        accu += inc
    print(f'{indent}return {accu}')
    return accu
        
accu = 0
for string, runs in unfold(data):
    #print(string, runs)
    x = recurse(string, runs)
    #print('->', x)
    accu += x
print('total', accu)