Dominoes
Lay a set of domino stones in a ring, turning each as needed, so that touching halves match and the two free ends match each other.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: dominoes.nomi
//# Lays a set of dominoes in a closed chain, where touching halves match.
/// The `stones`, each the dots on its two halves, laid in a chain, each
/// turned as it must be, where touching halves match and the two free ends
/// match each other; `None` when no order makes one.
pub fn chain(stones: List<(Int, Int)>) -> Maybe<List<(Int, Int)>>
case stones
[] -> Some([])
[(start, stop) as first, ..rest] -> extend(start, stop, [first], rest)
end
end
/// Lays the stones `left` after `laid`, which runs from `start` to `end`
/// and is held last stone first, trying each stone that fits, either way
/// round, and backing out of any that leads nowhere.
fn extend(
start: Int,
stop: Int,
laid: List<(Int, Int)>,
left: List<(Int, Int)>,
) -> Maybe<List<(Int, Int)>>
if left == [] and start == stop then return Some(Iter.reverse(laid))
left
|> picks()
|> Iter.flat_map(fn ((a, b), others) -> [((a, b), others), ((b, a), others)])
|> Iter.filter(fn ((a, _b), _others) -> a == stop)
|> Iter.find_map(fn ((a, b), others) -> extend(start, b, [(a, b), ..laid], others))
end
/// Each stone of `stones` with the stones other than it.
fn picks(stones: List<(Int, Int)>) -> Iter<((Int, Int), List<(Int, Int)>)>
stones
|> Iter.with_index()
|> Iter.map(fn (index, stone) -> (stone, List.remove_at(stones, index)!))
end
// FILE: dominoes_test.nomi
import dominoes
/// Whether `chain` is a chain of exactly `stones`: each stone's second half
/// matches the next one's first, the last stone's matches the first's, and
/// it holds each stone as often as `stones` does, either way round.
fn is_chain_of(chain: List<(Int, Int)>, stones: List<(Int, Int)>) -> Bool
next = chain |> Iter.drop(1) |> Iter.concat(Iter.take(chain, 1))
linked = Iter.zip(chain, next) |> Iter.all_match(fn ((_a, b), (c, _d)) -> b == c)
linked and has_same_stones(chain, stones)
end
fn has_same_stones(a: List<(Int, Int)>, b: List<(Int, Int)>) -> Bool
a |> Iter.map(unturned) |> Iter.frequencies() == b |> Iter.map(unturned) |> Iter.frequencies()
end
fn unturned((a, b): (Int, Int)) -> (Int, Int)
(Int.min(a, b), Int.max(a, b))
end
test "can chain"
[
("empty input = empty output", []),
("singleton input = singleton output", [(1, 1)]),
("three elements", [(1, 2), (3, 1), (2, 3)]),
("can reverse dominoes", [(1, 2), (1, 3), (2, 3)]),
("need backtrack", [(1, 2), (2, 3), (3, 1), (2, 4), (2, 4)]),
("separate loops", [(1, 2), (2, 3), (3, 1), (1, 1), (2, 2), (3, 3)]),
(
"nine elements",
[(1, 2), (5, 3), (3, 1), (1, 2), (2, 4), (1, 6), (2, 3), (3, 4), (5, 6)],
),
]
|> subtests (description, stones), description
assert Some(chain) = dominoes.chain(stones)
assert is_chain_of(chain, stones)
end
end
test "cannot chain"
[
("singleton that can't be chained", [(1, 2)]),
("can't be chained", [(1, 2), (4, 1), (2, 3)]),
("disconnected - simple", [(1, 1), (2, 2)]),
("disconnected - double loop", [(1, 2), (2, 1), (3, 4), (4, 3)]),
("disconnected - single isolated", [(1, 2), (2, 3), (3, 1), (4, 4)]),
("separate three-domino loops", [(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)]),
]
|> subtests (description, stones), description
assert dominoes.chain(stones) == None
end
endok can chain (7 cases)
ok cannot chain (6 cases)
test result: ok. 13 passed, 0 failed
How it’s written
Section titled “How it’s written”- This is the exercise’s second level:
chainreturns the chain itself,Maybe<List<Stone>>, not only whether one exists. A stone is a(Int, Int), as the canonical comments suggest for a language with pairs. It is written out rather than named with atypealias: an alias is for shortening a long anonymous shape, and a pair is short. - The search is a depth-first backtrack. The first stone starts the chain, and
extendtries every stone left, either way round, whose first half matches the free end, and recurses. The candidates are a lazy pipeline ended byIter.find_map, so the search stops at the first chain that closes and backs out of a dead end by moving on to the next candidate. A chain that uses every stone closes when its two ends match. - The chain is built last stone first, with
[stone, ..laid], and reversed once at the end, so each step is a cons. pickspairs each stone with the stones other than it, the list with that stone taken out byList.remove_at(...)!, whose index comes fromIter.with_indexover the same list.- The canonical data lists only whether a chain exists, since a set has many chains. The test file checks a found chain with
is_chain_of, the four properties the canonical comments give: each stone’s second half matches the next one’s first and the last one’s matches the first’s (one zip of the chain with itself rotated by one), and it holds the same stones as often as the input, either way round (the frequencies of each stone with its smaller half first). Matching frequencies make the counts equal too. - The cases are two
subteststables, the seven that chain and the six that do not, since they assert different things.