Skip to content

Piecing It Together

Fill in the details of a jigsaw puzzle from some of them (its pieces, border and inside pieces, rows, columns, aspect ratio and format), or say that the details given are too few or contradict each other.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: piecing_it_together.nomi
//# Works out a jigsaw puzzle's shape and piece counts from partial clues.

/// The shape of a puzzle of square pieces: taller than wide, square, or
/// wider than tall.
pub enum Format
    Portrait
    Square
    Landscape
end

/// Everything about a jigsaw puzzle.
pub struct Jigsaw
    pieces:       Int
    border:       Int
    inside:       Int
    rows:         Int
    columns:      Int
    aspect_ratio: Float
    format:       Format
end

/// What is known about a puzzle: any of its parts, each `None` when unknown.
pub struct Clues
    pieces:       Maybe<Int> = None
    border:       Maybe<Int> = None
    inside:       Maybe<Int> = None
    rows:         Maybe<Int> = None
    columns:      Maybe<Int> = None
    aspect_ratio: Maybe<Float> = None
    format:       Maybe<Format> = None
end

/// Why the clues do not describe exactly one puzzle.
pub enum Error
    InsufficientData
    ContradictoryData
end

/// The one puzzle `clues` describe: `InsufficientData` when more than one
/// fits them, and `ContradictoryData` when none does.
//! assert jigsaw_data({pieces: Some(6), rows: Some(3)}) |> Result.map(.columns) == Ok(2)
//
pub fn jigsaw_data(clues: Clues) -> Result<Jigsaw, Error>
    Some(rows) = row_candidates(clues) else return Err(.InsufficientData)

    Some(columns_for) = column_rule(clues) else return Err(.InsufficientData)

    fitting =
        rows
        |> Iter.flat_map(fn rows ->
            columns_for(rows)
            |> Iter.filter(&(&1 >= 1))
            |> Iter.map(&puzzle(rows, &1))
        end)
        |> Iter.filter(&fits(clues, &1))
        |> Iter.take(2)
        |> Iter.to_list()

    case fitting
        []       -> Err(.ContradictoryData)
        [jigsaw] -> Ok(jigsaw)
        _        -> Err(.InsufficientData)
    end
end

/// The puzzle of `rows` rows and `columns` columns.
fn puzzle(rows: Int, columns: Int) -> Jigsaw
    pieces = rows * columns
    inside = Int.max(rows - 2, 0) * Int.max(columns - 2, 0)
    aspect_ratio = Int.to_float(columns) / Int.to_float(rows)

    format = case Int.compare(columns, rows)
        .Less    -> Format.Portrait
        .Equal   -> .Square
        .Greater -> .Landscape
    end

    {pieces:, border: pieces - inside, inside:, rows:, columns:, aspect_ratio:, format:}
end

/// Whether `jigsaw` agrees with every part `clues` knows.
fn fits(clues: Clues, jigsaw: Jigsaw) -> Bool
    counts_agree =
        [
            (clues.pieces,  jigsaw.pieces),
            (clues.border,  jigsaw.border),
            (clues.inside,  jigsaw.inside),
            (clues.rows,    jigsaw.rows),
            (clues.columns, jigsaw.columns),
        ]
        |> Iter.all_match(fn (known, actual) -> agrees(known, actual))

    ratio_agrees = Iter.all_match(
        clues.aspect_ratio,
        &Float.equal_within(&1, jigsaw.aspect_ratio, 1e-9),
    )

    counts_agree and ratio_agrees and agrees(clues.format, jigsaw.format)
end

/// Whether `actual` is the `known` value, when there is one.
fn agrees<T>(known: Maybe<T>, actual: T) -> Bool where T: Equatable
    Iter.all_match(known, &(&1 == actual))
end

/// The row counts worth trying: the known one, or every count up to a bound
/// that a known part sets. `None` when nothing bounds the rows, so that
/// endlessly many puzzles fit.
fn row_candidates(clues: Clues) -> Maybe<List<Int>>
    case clues
        {rows: Some(rows)} ->
            Some([rows])

        {pieces: Some(pieces)} ->
            Some(up_to(pieces))

        {border: Some(border)} ->
            Some(up_to(border))

        {inside: Some(inside)} ->
            Some(up_to(inside + 2))

        {columns: Some(columns), aspect_ratio: Some(ratio)} ->
            nearest(Int.to_float(columns) / ratio) |> Maybe.map(up_to)

        {columns: Some(columns), format: Some(.Square or .Landscape)} ->
            Some(up_to(columns))

        _ ->
            None
    end
end

fn up_to(bound: Int) -> List<Int>
    Iter.to_list(1..=bound)
end

/// How the first known part that settles the columns gives them for a
/// puzzle of so many rows, or `None` when no known part settles them.
fn column_rule(clues: Clues) -> Maybe<(Int) -> List<Int>>
    case clues
        {columns: Some(columns)} ->
            Some(fn _rows -> [columns])

        {pieces: Some(pieces)} ->
            Some(fn rows ->
                if rows != 0 and pieces % rows == 0 then [pieces / rows] else []
            end)

        {aspect_ratio: Some(ratio)} ->
            Some(fn rows -> Iter.to_list(nearest(Int.to_float(rows) * ratio)))

        {format: Some(.Square)} ->
            Some(fn rows -> [rows])

        {border: Some(border)} ->
            Some(fn rows ->
                if rows == 1 then
                    [border]
                else
                    [(border + 4) / 2 - rows]
                end
            end)

        {inside: Some(inside)} ->
            Some(fn rows ->
                if rows > 2 and inside % (rows - 2) == 0 then [inside / (rows - 2) + 2] else []
            end)

        _ ->
            None
    end
end

/// The whole number nearest `x`.
fn nearest(x: Float) -> Maybe<Int>
    x |> Float.round() |> Float.to_int()
end

// FILE: piecing_it_together_test.nomi
import piecing_it_together.{Clues, Jigsaw, jigsaw_data}

test "jigsaw data"
    cases: List<(String, Clues, Jigsaw)> = [
        (
            "1000 pieces puzzle with 1.6 aspect ratio",
            {pieces: Some(1000), aspect_ratio: Some(1.6)},
            {
                pieces:       1000,
                border:       126,
                inside:       874,
                rows:         25,
                columns:      40,
                aspect_ratio: 1.6,
                format:       .Landscape,
            },
        ),
        (
            "square puzzle with 32 rows",
            {rows: Some(32), format: Some(.Square)},
            {
                pieces:       1024,
                border:       124,
                inside:       900,
                rows:         32,
                columns:      32,
                aspect_ratio: 1.0,
                format:       .Square,
            },
        ),
        (
            "400 pieces square puzzle with only inside pieces and aspect ratio",
            {inside: Some(324), aspect_ratio: Some(1.0)},
            {
                pieces:       400,
                border:       76,
                inside:       324,
                rows:         20,
                columns:      20,
                aspect_ratio: 1.0,
                format:       .Square,
            },
        ),
        (
            "1500 pieces landscape puzzle with 30 rows and 1.6 aspect ratio",
            {rows: Some(30), aspect_ratio: Some(1.6666666666666667)},
            {
                pieces:       1500,
                border:       156,
                inside:       1344,
                rows:         30,
                columns:      50,
                aspect_ratio: 1.6666666666666667,
                format:       .Landscape,
            },
        ),
        (
            "300 pieces portrait puzzle with 70 border pieces",
            {pieces: Some(300), border: Some(70), format: Some(.Portrait)},
            {
                pieces:       300,
                border:       70,
                inside:       230,
                rows:         25,
                columns:      12,
                aspect_ratio: 0.48,
                format:       .Portrait,
            },
        ),
    ]

    subtests cases, (description, clues, expected), description
        assert jigsaw_data(clues) == Ok(expected)
    end
end

test "puzzle with insufficient data"
    clues = Clues{pieces: Some(1500), format: Some(.Landscape)}

    assert jigsaw_data(clues) == Err(.InsufficientData)
end

test "puzzle with contradictory data"
    clues = Clues{rows: Some(100), columns: Some(1000), format: Some(.Square)}

    assert jigsaw_data(clues) == Err(.ContradictoryData)
end
  • What is known is a Clues struct whose seven fields are Maybes that default to None, so a case writes only what it knows: {rows: Some(32), format: Some(.Square)}. The answer is a Jigsaw with every field filled, or Error.InsufficientData or Error.ContradictoryData.
  • A puzzle is settled by its rows and columns, so jigsaw_data searches them rather than solving each combination of clues by its own formula. row_candidates gives the known row count, or every count up to a bound some known part sets (the pieces, the border, the inside pieces plus two, or the columns with a ratio or a format that keeps the rows at most the columns). column_rule answers a function from a row count to the column counts worth trying, from the first known part that settles the columns. puzzle builds the whole puzzle from rows and columns, and fits keeps those that agree with every clue. A clue agrees when it is None or matches, which is Iter.all_match over the Maybe, an Iter of none or one value.
  • The search stops at the second fitting puzzle with Iter.take(2): none is a contradiction, one is the answer, two are too many. When nothing bounds the rows or settles the columns, endlessly many puzzles fit and the answer is InsufficientData before any search.
  • The aspect ratio is compared within 1e-9, since it is a Float computed as columns over rows and the canonical data writes 5/3 as 1.6666666666666667.
  • The five complete puzzles are one subtests table named by the description column; the two errors are plain tests.