Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Set version solution in Clear category for Stepping Stones Puzzle by freeman_lex
def stepping_stones(n: int, ones: list[tuple[int, int]]) -> int:
def get_neib(r: int, c: int) -> set[tuple[int, int]]:
return {(x, y)
for x in range(max(0, r - 1), min(n, r + 2))
for y in range(max(0, c - 1), min(n, c + 2))}
filled = {cell: 1 for cell in ones}
neib = set()
for r, c in ones:
neib |= get_neib(r, c)
neib -= set(ones)
res = 1
variants = [(filled, neib, 2)]
while variants:
fil, nei, st = variants.pop(0)
avail = {cell
for cell in nei
if sum(fil.get(cell2, 0) for cell2 in get_neib(*cell)) == st}
if not avail:
res = max(res, st - 1)
continue
for r, c in avail:
(fil1 := dict(fil))[(r, c)] = st
nei1 = nei.copy() | get_neib(r, c)
nei1 -= set(fil1.keys())
variants.append((fil1, nei1, st + 1))
return res
print("Example:")
print(stepping_stones(4, [(0, 0), (3, 3)]))
# These "asserts" are used for self-checking
assert stepping_stones(4, [(0, 0), (3, 3)]) == 1
assert stepping_stones(5, [(0, 1), (1, 1), (2, 2)]) == 10
assert stepping_stones(6, [(2, 0), (5, 3), (1, 3), (0, 0)]) == 19
print("The mission is done! Click 'Check Solution' to earn rewards!")
Aug. 3, 2023
