TypeScript: a generic breadth-first search solves the water-jug puzzle

The concept

State-space search separates the problem from the algorithm. The problem supplies a start state, a goal test, and a function that lists the next states. The search supplies the order of exploration. With generics, one breadth-first search works for any state type S, as long as the caller gives a key function that turns a state into a string so visited states can be remembered.

The puzzle has a 3-litre jug and a 5-litre jug and no markings. The goal is to have exactly 4 litres in one of them. A move fills a jug, empties a jug, or pours one into the other until the target is full or the source is empty. Because BFS expands states by number of moves, the first solution it finds uses the fewest moves.

Code example

function bfs<S>(start: S, isGoal: (s: S) => boolean, next: (s: S) => S[], key: (s: S) => string): S[] | null {
  const queue: S[][] = [[start]];
  const seen = new Set<string>([key(start)]);
  while (queue.length > 0) {
    const path = queue.shift()!;
    const state = path[path.length - 1];
    if (isGoal(state)) {
      return path;
    }
    for (const candidate of next(state)) {
      if (!seen.has(key(candidate))) {
        seen.add(key(candidate));
        queue.push([...path, candidate]);
      }
    }
  }
  return null;
}

type Jugs = [number, number];
const capacity: Jugs = [3, 5];

function moves([a, b]: Jugs): Jugs[] {
  const pourAB = Math.min(a, capacity[1] - b);
  const pourBA = Math.min(b, capacity[0] - a);
  return [
    [capacity[0], b],
    [a, capacity[1]],
    [0, b],
    [a, 0],
    [a - pourAB, b + pourAB],
    [a + pourBA, b - pourBA],
  ];
}

const path = bfs<Jugs>([0, 0], ([a, b]) => a === 4 || b === 4, moves, ([a, b]) => a + "," + b);
console.log(path!.map(([a, b]) => "(" + a + "," + b + ")").join(" "));
console.log("moves: " + (path!.length - 1));

(0,0) (0,5) (3,2) (0,2) (2,0) (2,5) (3,4)
moves: 6

Follow the code

Open the walkthrough to inspect the example one step at a time.

—

—

—

(0,0) (0,5) (3,2) (0,2) (2,0) (2,5) (3,4)

(0,0) (0,5) (3,2) (0,2) (2,0) (2,5) (3,4)
moves: 6

Behind the scenes

Cost and common mistakes

O(S) states visited; there are at most 4 × 6 = 24 states here.

• Without the visited set, the search would loop forever, refilling and emptying the same jugs.
• The puzzle has a solution only when the target is a multiple of the greatest common divisor of the two capacities and fits in the larger jug.
• queue.shift() is O(n) for long arrays. A real queue (or an index pointer) is better for large state spaces.

Try it yourself

Is 4 litres reachable with jugs of 2 and 6 litres?

Further reading

• TypeScript Handbook (external)
• Node.js API documentation (external)
• Artificial Intelligence: A Modern Approach (Russell, Norvig) (external)