Two Bucket
Find the fewest actions that measure an exact number of liters with two buckets, starting by filling a given one, and never leaving the starting bucket empty with the other full.
Adapted from Exercism’s problem specification (MIT). Listed under Games & Simulation.
// FILE: two_bucket.nomi
//# Measures an amount of water with two buckets of given sizes.
/// One of the two buckets.
pub enum Bucket
One
Two
end
/// How the goal is reached: in how many actions, in which bucket, and how
/// much is left in the other.
pub struct Outcome
moves: Int
goal_bucket: Bucket
other_bucket: Int
end
/// Why the goal cannot be measured.
pub enum Error
Impossible
end
/// The fewest actions that measure `goal` liters with buckets of `one` and
/// `two` liters, filling `start` first. No action may leave `start` empty
/// and the other bucket full.
pub fn measure(one: Int, two: Int, goal: Int, start: Bucket) -> Result<Outcome, Error>
(first, forbidden) = case start
.One -> ((one, 0), (0, two))
.Two -> ((0, two), (one, 0))
end
search([first], [first, forbidden], 1, (one, two), goal)
end
/// A breadth-first search over states, the liters in bucket one and bucket
/// two: `frontier` is every state `moves` actions reach
/// that no fewer actions do, and `seen` every state reached so far, with the
/// forbidden one, so no action leads back to them.
fn search(
frontier: List<(Int, Int)>,
seen: Set<(Int, Int)>,
moves: Int,
sizes: (Int, Int),
goal: Int,
) -> Result<Outcome, Error>
case Iter.find(frontier, fn (one, two) -> one == goal or two == goal)
Some((one, two)) when one == goal ->
Ok({moves:, goal_bucket: .One, other_bucket: two})
Some((one, _two)) ->
Ok({moves:, goal_bucket: .Two, other_bucket: one})
None ->
next =
frontier
|> Iter.flat_map(&actions(&1, sizes))
|> Iter.reject(&(&1 in seen))
|> Iter.to_set()
if Iter.is_empty(next) then
Err(.Impossible)
else
search(Iter.to_list(next), Set.union(seen, next), moves + 1, sizes, goal)
end
end
end
/// The states one action leads to from `(one, two)`: fill a bucket, empty
/// one, or pour one into the other until it is empty or the other is full.
fn actions((one, two): (Int, Int), (size_one, size_two): (Int, Int)) -> List<(Int, Int)>
into_two = Int.min(one, size_two - two)
into_one = Int.min(two, size_one - one)
[
(size_one, two),
(one, size_two),
(0, two),
(one, 0),
(one - into_two, two + into_two),
(one + into_one, two - into_one),
]
end
// FILE: two_bucket_test.nomi
import two_bucket.{self, Bucket, Error, Outcome}
test "measure"
cases: List<(String, (Int, Int), Int, Bucket, Result<Outcome, Error>)> = [
(
"Measure using bucket one of size 3 and bucket two of size 5 - start with bucket one",
(3, 5),
1,
.One,
Ok({moves: 4, goal_bucket: .One, other_bucket: 5}),
),
(
"Measure using bucket one of size 3 and bucket two of size 5 - start with bucket two",
(3, 5),
1,
.Two,
Ok({moves: 8, goal_bucket: .Two, other_bucket: 3}),
),
(
"Measure using bucket one of size 7 and bucket two of size 11 - start with bucket one",
(7, 11),
2,
.One,
Ok({moves: 14, goal_bucket: .One, other_bucket: 11}),
),
(
"Measure using bucket one of size 7 and bucket two of size 11 - start with bucket two",
(7, 11),
2,
.Two,
Ok({moves: 18, goal_bucket: .Two, other_bucket: 7}),
),
(
"Measure one step using bucket one of size 1 and bucket two of size 3 - start with bucket two",
(1, 3),
3,
.Two,
Ok({moves: 1, goal_bucket: .Two, other_bucket: 0}),
),
(
"Measure using bucket one of size 2 and bucket two of size 3 - start with bucket one and end with bucket two",
(2, 3),
3,
.One,
Ok({moves: 2, goal_bucket: .Two, other_bucket: 2}),
),
(
"Measure using bucket one much bigger than bucket two",
(5, 1),
2,
.One,
Ok({moves: 6, goal_bucket: .One, other_bucket: 1}),
),
(
"Measure using bucket one much smaller than bucket two",
(3, 15),
9,
.One,
Ok({moves: 6, goal_bucket: .Two, other_bucket: 0}),
),
("Not possible to reach the goal", (6, 15), 5, .One, Err(.Impossible)),
(
"With the same buckets but a different goal, then it is possible",
(6, 15),
9,
.One,
Ok({moves: 10, goal_bucket: .Two, other_bucket: 0}),
),
("Goal larger than both buckets is impossible", (5, 7), 8, .One, Err(.Impossible)),
]
subtests cases, (description, (one, two), goal, start, expected), description
assert two_bucket.measure(one, two, goal, start) == expected
end
endok measure (11 cases)
test result: ok. 11 passed, 0 failed
How it’s written
Section titled “How it’s written”measurereturnsResult<Outcome, Error>.Outcomeis a struct of the three canonical answers, the number of actions, the bucket that holds the goal and the liters in the other, andError.Impossibleis the canonical error.- A state is the liters in each bucket, a
(Int, Int). The buckets are positions in the tuple, so filling, emptying and pouring are tuple arithmetic inactions. searchis a breadth-first search, written as a tail-recursive function over three values: the frontier of states the current number of actions reaches first, the set of states seen so far, and the number of actions. Breadth first, the first frontier with the goal in either bucket is reached in the fewest actions.- The forbidden state, the starting bucket empty and the other full, goes into the seen set before the search starts, so no action ever leads to it, with no check of its own.
- A frontier that adds no new state means the goal cannot be reached, which is
Error.Impossible; that covers a goal larger than both buckets with no case of its own. - The answer reads the bucket from the state that reaches the goal, with a guard,
Some((one, two)) when one == goal, and a second arm for bucket two. Iter.loopwould not do here: a loop breaks with a value of its state’s type, and the search ends with aResult.- The 11 canonical cases are one
subteststable, annotated so each expectedOk({...})is anOutcome; the bucket sizes are one(one, two)column, taken apart in the row pattern.