TL;DR: We solve the classic “frog leap” puzzle with Depth-First Search (DFS) by generating next boards around teh blank and trying jumps before steps. This trick finds the minimal soluton in exactly N^2+2N moves.
The classic frog puzzle looks like this, when 3 frogs from side are used:
The picture is from the site data.bangtech.com/algorithm/switch_frogs_to_the_opposite_side, and the game actually works pretty well there 🙂
The core idea is to try to find a way to map all the frogs around the blank rock (_ in the code) and to run DFS on it. These frogs are maximum 4, thus it is not that tough. In the code, these are b-2, b-1, b+1, b+2 correspondingly:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
def neighbours_research(state): “”” >*_._*> _*<.<*_ >_._> _<._< “””
s = list(state) b = s.index(“_”) result = []
# >*_._*> if b–2 >= 0 and s[b–2] == “>” and s[b–1] in “<>”: t = s[:] t[b], t[b – 2] = t[b–2], t[b] result.append(“”.join(t))
# _*<.<*_ if b+2 < len(s) and s[b+2] == “<“ and s[b+1] in “<>”: t = s[:] t[b], t[b+2] = t[b+2], t[b] result.append(“”.join(t))
# >_._> if b–1 >= 0 and s[b–1] == “>”: t = s[:] t[b], t[b–1] = t[b–1], t[b] result.append(“”.join(t))
# _<._< if b+1 < len(s) and s[b+1] == “<“: t = s[:] t[b], t[b+1] = t[b+1], t[b] result.append(“”.join(t))
return result |
The 4 results from the starting state look like that:
The _ is the rock. > is a frog facing right, < is a frog facing left.
The magic of the code is that it uses DFS approach, trying each new move first, as a stack (or LIFO). If it is stuck, then the built-in functionality of the stack backtracks and tries the next one. We keep visited set and path. The idea is that the visited is a set, so thus a repetition and endless loop is avoided. The path is the current route from teh start, and with python we append on enter and pop on backtrack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
def solve_frogs_dfs(n): start = start_state(n) goal = goal_state(n) visited = set() path = []
def dfs(state: str) -> bool: if state in visited: return False visited.add(state) path.append(state) if state == goal: return True
for nxt in neighbours_research(state): if dfs(nxt): return True path.pop() return False
dfs(start) return path |
In the GitHub example and the YouTube video, I am printing a bit more, but the minimal is the code above. This is a working result from it for 3 frogs per side:
After the first deadend is removed, the second deadend is also removed, as it only leads to the first one. The “magic” of stack, LIFO, BFS and recursion working together as a team 🙂
To make the code complete, these are start_state() and goal_state() functions, referred in the dfs() above:
|
|
def start_state(n): return “>”*n+“_”+“<“*n
def goal_state(n): return “<“*n+“_”+“>”*n
def print_path(path): for row in path: print(row) |
The complete result with 3 frogs looks like that:
Actually it is achieved only with 34 states, which is quite ok.
The YT video is here:
https://www.youtube.com/watch?v=DVgqA8-c1oI
The GitHub link is here: https://github.com/Vitosh/Python_personal/tree/master/YouTube/045_Python_Frog_Jump
Enjoy it 🙂
دیدگاهتان را بنویسید