TypeScript: a generic breadth-first search solves the water-jug puzzle
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.
TypeScript
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));