Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
no recursion with deque solution in Speedy category for Stepping Stones Puzzle by roman.bratishchev
# field is (row,col) mapped to stone_number to place
# if stone_number<0 then the position is occupied by either a stone or a border
#
# initial field is the borders + update of vicinities of '1' spots
# new_vicinity(field,rc,stone) - provides 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]]) -> int:
NEIGHBOURS,NA=set(product((-1,0,1),repeat=2))-{(0,0)},-10000
field={rc:NA for rc in product(range(-1,n+1),(-1,n)) for rc in (rc,rc[::-1])}
def new_vicinity(field,rc,stone):
vicinity={vrc:field.get(vrc,0)+stone for dr,dc in NEIGHBOURS for vrc in ((rc[0]+dr,rc[1]+dc),)}
vicinity[rc]=NA
return vicinity
for rc in ones: field.update(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 15, 2025
