DSA Factory
Free Graphs lessonsGraphs · Stage 2 · Breadth-first · Step 4

A graph you never draw

Treat every state of a puzzle as a place and every move as a road, then use the same ripple search. About 15 minutes.

Puzzles are graphs in disguise

A broken calculator shows a number and has only two buttons: double it, or subtract one. How few presses turn the display 3 into 10?

Picture every number as a place. A button press is a road from one number to another: from 3 you can reach 6 or 2. You never draw this graph, because you can always work out the roads from a number just by doing the presses. Then it is the fewest-roads question again, and the ripple search answers it.

State: is a place; a move is a road.
Neighbours: come from applying each move.
In code
limit = 2 * max(start, target)
dist = {start: 0}
queue = deque([start])
while queue:
    cur = queue.popleft()
    if cur == target:
        return dist[cur]
    for nxt in (cur * 2, cur - 1):
        if nxt < 1 or nxt > limit:
            continue
        if nxt not in dist:
            dist[nxt] = dist[cur] + 1
            queue.append(nxt)
Fewest presses to turn 3 into 10 (double, or subtract one).
30621254110
queue
[3]

The display shows 3. That is our starting place, with zero presses so far.

Move 1 of 4

Keep the states in check

Two things stop an unseen graph from running away. First, remember the states you have visited, in a dictionary or an array, so that you never enter one twice. Without that, doubling and subtracting could cycle forever.

Second, put a sensible bound on the states. Numbers that grow without limit would never end, so pick a ceiling that you can argue is high enough. Here, going past twice the bigger of the two numbers is never useful.

Remember states: or the same ones are explored again and again.
Bound them: a ceiling stops a search that could grow forever.
Quick check

Why does the search remember which numbers it has already reached?

  1. ADifferent sequences of presses can land on the same number, and re-exploring it would repeat work or loop forever
  2. BTo make sure it finds the longest sequence of presses
  3. CBecause the display can only show each number once
Show the answer

Different sequences of presses can land on the same number, and re-exploring it would repeat work or loop forever. A visited record keeps each state to a single visit, just like a mark on a graph's node.

Your problem

Fewest presses

A broken calculator shows a whole number and has two buttons: one doubles the number, the other subtracts 1. Starting from start, return the fewest presses needed to make the display show target. The display must stay at least 1 at all times.

Example
start = 3, target = 10 → 3

1 ≤ start ≤ 100,000 · 1 ≤ target ≤ 100,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve