Print path to node in a 2D dictionary-structured graph

Question

This question is slightly inspired by the Infinite Craft neal.fun game. I've managed to build a graph structure representing the alchemy additions. For example, { "Water": { "Fire": "Steam" }} means Water + Fire = Steam. Given some destination, I want to print the path to it from the starting elements. Of note, this graph does contain cycles.

My approach is to work backwards from the destination, looking for pairs of elements that add up to it. If we find one, we immediately recurse and try constructing the elements that led to that. At times, we will hit dead ends (via cycles, mostly), at which point we need to backtrack. I cannot seem to get this to work correctly. I seem to have two key problems:

• I seem to backtrack too much at times
• Having backtracked the right amount, my code does not seem to want to continue searching.

What am I doing wrong?

SOURCES = ["Wind", "Fire", "Water", "Earth"]
visited = {}
banned = []


def print_sum(primary, secondary, result):
    if primary in SOURCES:
        primary = Fore.GREEN + primary + Fore.RESET
    if secondary in SOURCES:
        secondary = Fore.GREEN + secondary + Fore.RESET
    print(f"{primary} + {secondary} = {result}")


def find_path(graph, dst):
    visited[dst] = visited.get(dst, 0) + 1
    path = []

    for key, subgraph in graph.items():
        for subkey, val in subgraph.items():
            if val == dst:
                if key in visited or subkey in visited or (key, subkey) in banned or (subkey, key) in banned:
                    print(f"Skipping {key} + {subkey} = {val}")
                    continue

                path.append((key, subkey, val))
                print_sum(key, subkey, val)

                if key not in SOURCES:
                    visited[key] = visited.get(key, 0) + 1
                if subkey not in SOURCES:
                    visited[subkey] = visited.get(subkey, 0) + 1

                # Now find key and subkey
                if key not in SOURCES:
                    subpath = find_path(graph, key)

                    if subpath:
                        path.extend(subpath)
                    else:
                        print(f"Could not find path for {key}")
                        # Backtrack
                        path.pop()
                        visited[key] -= 1
                        if visited[key] == 0:
                            visited.pop(key)
                        banned.append((key, subkey))
                        print(f"Backtracking {key} + {subkey} = {val}")
                        continue
                if subkey not in SOURCES:
                    subpath = find_path(graph, subkey)

                    if subpath:
                        path.extend(subpath)
                    else:
                        print(f"Could not find path for {subkey}")
                        # Backtrack
                        path.pop()
                        visited[subkey] -= 1
                        if visited[subkey] == 0:
                            visited.pop(subkey)
                        banned.append((key, subkey))
                        print(f"Backtracking {key} + {subkey} = {val}")

                return path
    return None

Below is a small subgraph for which I encounter this issue:

{'Dust': {'Fish': 'Starfish', 'Ocean': 'Sand', 'Tsunami': 'Sand'},
 'Earth': {'Fish': 'Whale',
           'Ocean': 'Island',
           'Tsunami': 'Island',
           'Wave': 'Sand'},
 'Fire': {'Fish': 'Sushi',
          'Ocean': 'Steam',
          'Tsunami': 'Volcano',
          'Wave': 'Steam',
          'Wind': 'Smoke'},
 'Smoke': {'Fish': 'Sushi', 'Ocean': 'Fog', 'Tsunami': 'Volcano'},
 'Steam': {'Fish': 'Sushi',
           'Ocean': 'Cloud',
           'Tsunami': 'Titanic',
           'Wave': 'Surf'},
 'Tornado': {'Fish': 'Sharknado', 'Ocean': 'Tsunami', 'Tsunami': 'Destruction'},
 'Volcano': {'Fish': 'Sushi', 'Ocean': 'Island', 'Tsunami': 'Earthquake'},
 'Water': {'Fish': 'Fishbowl',
           'Ocean': 'Fish',
           'Tsunami': 'Ocean',
           'Wave': 'Tsunami',
           'Wind': 'Wave'},
 'Wave': {'Dust': 'Sand',
          'Fish': 'Surf',
          'Ocean': 'Tsunami',
          'Smoke': 'Surf',
          'Steam': 'Surf',
          'Tornado': 'Tsunami',
          'Tsunami': 'Tsunami',
          'Wave': 'Tsunami'},
 'Wind': {'Cloud': 'Storm',
          'Dust': 'Sandstorm',
          'Earth': 'Dust',
          'Fish': 'Flying Fish',
          'Ocean': 'Storm',
          'Smoke': 'Cloud',
          'Storm': 'Tornado',
          'Tornado': 'Tornado',
          'Tsunami': 'Hurricane',
          'Wave': 'Storm',
          'Wind': 'Tornado'}}

On searching for "Earthquake", I get

Volcano + Tsunami = Earthquake
Skipping Fire + Tsunami = Volcano
Skipping Smoke + Tsunami = Volcano
Could not find path for Volcano
Backtracking Volcano + Tsunami = Earthquake
Skipping Volcano + Tsunami = Earthquake
[]

However, the answer is:

Volcano + Tsunami = Earthquake
Fire + Tsunami = Volcano
Water + Wave = Tsunami
Water + Wind = Wave

Answer 1

Answering my own question since I finally figured it out after another hour or so.

The reason the approach in the question doesn't work is in the example--you don't know if you will eventually find "Tsunami" or if it will end in a cycle, so the code in the question eliminates it as an option.

A better, easier approach is a modified BFS like so:

def find_path(graph, dst, path=None):
    if path is None:
        path = []

    if dst in SOURCES:
        return path

    nodes = [(None, None, "Wind", 0), (None, None, "Fire", 0), (None, None, "Water", 0), (None, None, "Earth", 0)]
    nodes_only = [node for _, _, node, _ in nodes]

    while True:
        for p1, p2, node, depth in nodes:
            if node == dst:
                path.append((p1, p2, node))
                return path
            for key, subgraph in graph.items():
                for subkey, val in subgraph.items():
                    if val == dst and (key == node or subkey == node) and key in nodes_only and subkey in nodes_only:
                        path.append((key, subkey, val))
                        path.extend(find_path(graph, key))
                        path.extend(find_path(graph, subkey))
                        return path
                    if val and (key == node or subkey == node) and key in nodes_only and subkey in nodes_only:
                        nodes.append((key, subkey, val, depth + 1))
                        nodes_only.append(val)
            nodes.pop(0)

The only issue with this is that it's very inefficient. I'll likely update this answer once I fix that.