Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
no recursion documented solution in Creative category for Stepping Stones Puzzle by roman.bratishchev
# field is (row,col)->stone_to_place
# if stone_to_place==float('nan'), then the position is occupied either by stone or by border
#
# initialize the field with borders
# new_vicinity(field,rc,stone) - how the 'field' should be updated if a 'stone' is placed at 'rc' position
# 'queue' entry is (next_stone_to_place, going_field)
from collections import deque
from itertools import product
def stepping_stones(n:int, ones:list[tuple[int, int]], NA=float('nan')) -> int:
field={rc:NA for rc in product(range(-1,n+1),(-1,n)) for rc in (rc,rc[::-1])}
new_vicinity=lambda field,rc,stone:{vrc:field.get(vrc,0)+val for vrc,val in zip(product(*map(lambda i:(i-1,i,i+1),rc)),[stone]*4+[NA]+[stone]*4)}
for rc in ones: field|=new_vicinity(field,rc,1)
queue=deque([(2,field)])
while queue:
max_stone,stone,field=queue[-1][0]-1,*queue.popleft()
queue.extend((stone+1,field|new_vicinity(field,rc,stone)) for rc,val in field.items() if val==stone)
return max_stone
March 14, 2025
