In Python, create a recursive depth-first search algorithm that traverses a directed…
- User
In Python, create a recursive depth-first search algorithm that traverses a directed acyclic graph (DAG), where each node represents a word from a given dictionary, and each edge connects words with a single letter difference between them. The goal is to find a path from a start node (a given word) to an end node (another given word) while maximizing the total score associated with each edge on the path. Each edge has a non-negative integer weight assigned to it. The final output should be the maximum possible score achievable by following this constrainted path through the DAG.
- Assistant
To implement recursive depth-first search for finding a path with maximum score in a directed acyclic graph with word nodes and single letter difference edges, we need to keep track of the start node, end node, weight function, and parent dictionary while traversing. Here's a possible solution in Python:
from typing import DefaultDict, Dict, List class Node: def __init__(self, word: str): self.word = word self.children: Dict[str, Node] = {} self.score: int = 0 self.parent: Node = None self.visited: bool = False class Edge: def __init__(self, from_node: Node, to_node: Node, weight: int): self.from_node = from_node self.to_node = to_node self.weight = weight class DAG: def __init__(self, words: List[str], edges: List[Edge]): self.words: List[Node] = [Node(w) for w in set(words)] for I, w1 in enumerate(words): for w2 in words[i+1:]: if w1[0] != w2[0]: continue self.connect_words(w1, w2) for edge in edges: self.connect_words(edge.from_node, edge.to_node, edge.weight) self.nodes = set(self.words) def connect_words(self, word1: str, word2: str, weight: int = 0): node1, node2 = self.get_nodes(word1, word2) Edge(node1, node2, weight) node1.children[node2.word] = node2 def get_nodes(self, word1: str, word2: str): for node in self.words: if node.word == word1 or node.word == word2: return node, self.get_node(node, word2) raise ValueError(f"{word1} and {word2} not in DAG.") def get_node(self, start: Node, end: Node) -> Node: visited = set() stack = [start] visited.add(start) while stack: node = stack.pop() if node == end: path = [] while node is not None: path.append(node.word) node = node.parent path.reverse() score = 0 for I in range(len(path)-1): score += self.get_edge(path[i], path[i+1]).weight return score for child in node.children.values(): if child not in visited: stack.append(child) visited.add(child) return 0 def get_edge(self, from_node: Node, to_node: Node) -> Edge: for edge in from_node.children.values(): if edge.to_node == to_node: return edge raise ValueError("No edge found between nodes.") def dfs(self, node: Node, dict: DefaultDict[Node, List[Node]], path: List[Node], prev_weight: int): if node.visited: return path[-1].score - prev_weight for child in node.children.values(): path.append(child) weight = self.dfs(child, dict, path, node.score) score = path[-1].score + weight - prev_weight path.pop() if weight > prev_weight: dict[child] = list(reversed(path)) prev_weight = max(prev_weight, weight) path.pop() return node.score - prev_weight def max_score_path(self, start: Node, end: Node) -> int: stack = [start]
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.