Skip to content

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
end
  • This is the exercise’s second level: chain returns 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 a typealias: 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 extend tries every stone left, either way round, whose first half matches the free end, and recurses. The candidates are a lazy pipeline ended by Iter.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.
  • picks pairs each stone with the stones other than it, the list with that stone taken out by List.remove_at(...)!, whose index comes from Iter.with_index over 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 subtests tables, the seven that chain and the six that do not, since they assert different things.