Graphs that are never built

The nodes are states and the edges are moves. Nothing is stored; the neighbors are computed on demand.

Key idea

The graph is implied by the rules

Not every graph arrives as a list of edges. Often the problem describes states and legal moves between them, and the graph exists only in the sense that the rules define it.

Breadth-first search does not care. It needs a starting state, a way to recognize the goal, and a function producing the neighbors of a state. Where those neighbors come from is irrelevant to the search.

1from collections import deque2 3def fewest_steps(start, goal, limit):4    """Reach the goal using: add one, or double. Stay within limit."""5    queue = deque([(start, 0)])6    seen = {start}7    while queue:8        value, steps = queue.popleft()9        if value == goal:10            return steps11        for nxt in (value + 1, value * 2):12            if 0 < nxt <= limit and nxt not in seen:13                seen.add(nxt)14                queue.append((nxt, steps + 1))15    return -116 17print(fewest_steps(1, 10, 20))18print(fewest_steps(1, 7, 20))

Key idea

Generating neighbors efficiently

The expensive part is usually producing the neighbors. Comparing the current state against every other candidate state is the obvious approach and it costs the whole state space per step.

The alternative is to generate the neighbors directly from the state by applying each legal transformation. For string problems that means changing one position at a time to each possible character, which costs the string length times the alphabet size rather than the dictionary size.

1def one_letter_apart(word, allowed):2    """Words in allowed that differ from word in exactly one position."""3    out = []4    for index in range(len(word)):5        for letter in "abcdefghijklmnopqrstuvwxyz":6            if letter == word[index]:7                continue8            candidate = word[:index] + letter + word[index + 1:]9            if candidate in allowed:10                out.append(candidate)11    return out12 13print(one_letter_apart("hot", {"dot", "lot", "hit", "hog", "cog"}))

Position 0 finds dot and lot, position 1 finds hit, position 2 finds hog. cog differs in two places and is not a neighbor

Predict the output· 5 min

Predict the output: generating neighbors instead of storing them

The graph is never built. A word's neighbors are produced on demand by changing one character at a time and keeping whatever the dictionary contains. Type the two lines it prints.

Python

1from string import ascii_lowercase2 3words = {"hot", "dot", "dog", "lot", "log", "cog"}4word = "hot"5 6neighbors = []7for index in range(len(word)):8    for letter in ascii_lowercase:9        candidate = word[:index] + letter + word[index + 1:]10        if candidate != word and candidate in words:11            neighbors.append(candidate)12 13print(sorted(neighbors))14print("candidates built to find them:", len(word) * len(ascii_lowercase))

Printed output

Problem· 35 min

Word Ladder

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1from collections import deque2 3def fewest_steps(start, goal, limit):4 """Reach the goal using: add one, or double. Stay within limit."""5 queue = deque([(start, 0)])6 seen = {start}7 while queue:8 value, steps = queue.popleft()9 if value == goal:10 return steps11 for nxt in (value + 1, value * 2):12 if 0 < nxt <= limit and nxt not in seen:13 seen.add(nxt)14 queue.append((nxt, steps + 1))15 return -116 17print(fewest_steps(1, 10, 20))18print(fewest_steps(1, 7, 20))

1def one_letter_apart(word, allowed):2 """Words in allowed that differ from word in exactly one position."""3 out = []4 for index in range(len(word)):5 for letter in "abcdefghijklmnopqrstuvwxyz":6 if letter == word[index]:7 continue8 candidate = word[:index] + letter + word[index + 1:]9 if candidate in allowed:10 out.append(candidate)11 return out12 13print(one_letter_apart("hot", {"dot", "lot", "hit", "hog", "cog"}))

1from string import ascii_lowercase2 3words = {"hot", "dot", "dog", "lot", "log", "cog"}4word = "hot"5 6neighbors = []7for index in range(len(word)):8 for letter in ascii_lowercase:9 candidate = word[:index] + letter + word[index + 1:]10 if candidate != word and candidate in words:11 neighbors.append(candidate)12 13print(sorted(neighbors))14print("candidates built to find them:", len(word) * len(ascii_lowercase))