Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS - while loop solution in Clear category for The Stones by kudinov.feodor
def stones(pile, moves):
# DFS - depth first analysis
to_check = {pile} # which states to check
# where I need to stand to win, where I need to move to lose
safe_state = set()
# where I need to stand to lose, where I need to move to win
unsafe_state = {min(moves)}
while to_check:
state = min(to_check)
my_moves = sorted(state - i for i in moves if state > i) # where I can move
# if no moves available to continue game, it is totally unsafe_state
if not my_moves:
to_check.remove(state)
unsafe_state.add(state)
continue
# if any move is ok, vertex is safe_to_visit
unsafe_moves = 0
for my_move in my_moves:
# check enemy moves
enemy_moves = {my_move - i for i in moves if my_move - i > 0}
# totally safe
if enemy_moves <= safe_state:
safe_state.add(state)
to_check.remove(state)
break # no need to check other children
# totally unsafe move
if enemy_moves.intersection(unsafe_state):
unsafe_moves += 1
continue # go to next child
# did not find a single unsafe move, but some moves need to be explored
to_check.update(enemy_moves - safe_state)
break # since we explore DFS, break to continue exploring from children
# if all children are not safe moves, remove state from to_visit
if len(my_moves) == unsafe_moves:
to_check.remove(state)
unsafe_state.add(state)
return 1 if pile in safe_state else 2
if __name__ == '__main__':
print("Example:")
print(stones(17, [1, 3, 4]))
#These "asserts" using only for self-checking and not necessary for auto-testing
assert stones(17, [1, 3, 4]) == 2
assert stones(17, [1, 3, 4, 6, 9]) == 1
assert stones(99, [1]) == 2
print("Coding complete? Click 'Check' to earn cool rewards!")
April 2, 2024
