Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Stepping Stones Puzzle by freeman_lex
def stepping_stones(n: int, ones: list[tuple[int, int]]) -> int:
def count_neighbor_ones(r: int, c: int, data: list[list[int]]) -> int:
return sum(data[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)))
# Initialize the grid with stones and empty cells
grid = [[int((r, c) in ones)
for c in range(n)]
for r in range(n)]
# Initialize the result with 1 as the minimum number of steps
max_steps = 1
# List to store the grid and the next stone value for future exploration
variants = [(grid, 2)]
# Explore the variants until there are no more available moves
while variants:
grid_var, next_stone = variants.pop(0)
# Find available cells to place the next stone
available_cells = [(r, c)
for c in range(n)
for r in range(n)
if not grid_var[r][c] and count_neighbor_ones(r, c, grid_var) == next_stone]
if not available_cells:
# No available cells to place the next stone, update the maximum steps and continue exploring
max_steps = max(max_steps, next_stone - 1)
continue
# Try placing the next stone in each available cell and add new variants for exploration
for r, c in available_cells:
new_grid = [row[:] for row in grid_var] # Create a copy of the grid
new_grid[r][c] = next_stone
variants.append((new_grid, next_stone + 1))
return max_steps
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
