Skip to content

Instantly share code, notes, and snippets.

@jkseppan
Created December 13, 2023 09:37
Show Gist options
  • Save jkseppan/e95c5f35f4e8697a2aedee6c24745ef1 to your computer and use it in GitHub Desktop.
Save jkseppan/e95c5f35f4e8697a2aedee6c24745ef1 to your computer and use it in GitHub Desktop.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment