Skip to content

Palindrome Products

Find the smallest and the largest palindrome that is a product of two numbers in a range, with every pair of factors that makes it.

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

// FILE: palindrome_products.nomi
//# The smallest and largest palindromes that are products of two numbers in
//# a range, and their factors.

/// A palindrome and every pair of factors in the range that makes it, the
/// smaller factor first in each pair.
pub struct Product
    value:   Int
    factors: List<(Int, Int)>
end

/// Why a range has no products to search.
pub enum Error
    MinAboveMax
end

/// Which end of the products a search starts from.
enum Direction
    Ascending
    Descending
end

/// The smallest palindrome that is a product of two factors from `min` to
/// `max`, or `None` when no product in the range is a palindrome.
pub fn smallest(min: Int, max: Int) -> Result<Maybe<Product>, Error>
    search(min, max, .Ascending)
end

/// The largest palindrome that is a product of two factors from `min` to
/// `max`, or `None` when no product in the range is a palindrome.
pub fn largest(min: Int, max: Int) -> Result<Maybe<Product>, Error>
    search(min, max, .Descending)
end

/// The first palindrome from the `direction` end with a pair of factors
/// from `min` to `max`. The palindromes come in order, so the ones outside
/// the products' range are dropped from the near end and the walk stops at
/// the far one.
fn search(min: Int, max: Int, direction: Direction) -> Result<Maybe<Product>, Error>
    if min > max then return Err(.MinAboveMax)

    low = min * min
    high = max * max
    outside = fn p: Int -> not p in low..=high

    in_order(digit_count(low), digit_count(high), direction)
    |> Iter.flat_map(fn length ->
        (first, last) = halves(length)
        in_order(first, last, direction) |> Iter.map(&mirror(&1, length))
    end)
    |> Iter.drop_while(outside)
    |> Iter.take_while(&(not outside(&1)))
    |> first_product(min, max)
    |> Ok()
end

/// The numbers from `first` to `last`, both included, from the `direction`
/// end: the range itself, or the range stepped down from `last`. The two
/// are different Iters, which the declared result joins.
fn in_order(first: Int, last: Int, direction: Direction) -> Iter<Int>
    case direction
        .Ascending  -> first..=last
        .Descending -> Range.step_by(last..=first, -1)
    end
end

/// The first of `candidates` with a pair of factors from `min` to `max`.
fn first_product(candidates: Iter<Int>, min: Int, max: Int) -> Maybe<Product>
    candidates
    |> Iter.map(fn value -> Product{value:, factors: factors(value, min, max)})
    |> Iter.find(fn product -> product.factors != [])
end

/// Each pair `(a, b)` with `a <= b`, both from `min` to `max`, whose product
/// is `value`. `b = value / a` is at most `max` once `a` is at least
/// `value / max`, and at least `a` while `a` is at most the square root.
fn factors(value: Int, min: Int, max: Int) -> List<(Int, Int)>
    // A palindrome here is at least 1 and at most `max * max`, with `min`
    // at most `max`, so `max` is at least 1.
    if max < 1 then return []

    // A factor of a palindrome here is at least 1.
    from = Int.max(1, Int.max(min, (value + max - 1) / max))
    // A product of the factors is never negative.
    to = Int.min(max, Int.sqrt(NonNegativeInt.try_from(value)!))

    from..=to
    |> Iter.filter(&(value % &1 == 0))
    |> Iter.map(fn a -> (a, value / a))
    |> Iter.to_list()
end

/// The first and last of the first halves of the palindromes of `length`
/// digits: `100` and `999` for five or six digits.
fn halves(length: Int) -> (Int, Int)
    // A palindrome has at least one digit.
    half_length = NonNegativeInt.try_from((length + 1) / 2 - 1)!
    low = Int.pow(10, half_length)
    (low, low * 10 - 1)
end

/// The palindrome of `length` digits whose first half is `half`: `half`
/// followed by its own digits reversed, without its last digit when
/// `length` is odd. `123` makes `12321` for five digits and `123321` for six.
fn mirror(half: Int, length: Int) -> Int
    rest = if length % 2 == 1 then half / 10 else half

    rest
    |> Iter.iterate(&(&1 / 10))
    |> Iter.take_while(&(&1 > 0))
    |> Iter.reduce(half, fn palindrome, r -> palindrome * 10 + r % 10)
end

fn digit_count(n: Int) -> Int
    NonNegativeInt.try_from(n)! |> Int.to_digits() |> Iter.count()
end

// FILE: palindrome_products_test.nomi
import palindrome_products.{self, Error, Product}

test "smallest"
    [
        (
            "find the smallest palindrome from single digit factors",
            1,
            9,
            Ok(Some(Product{value: 1, factors: [(1, 1)]})),
        ),
        (
            "find the smallest palindrome from double digit factors",
            10,
            99,
            Ok(Some(Product{value: 121, factors: [(11, 11)]})),
        ),
        (
            "find the smallest palindrome from triple digit factors",
            100,
            999,
            Ok(Some(Product{value: 10201, factors: [(101, 101)]})),
        ),
        (
            "find the smallest palindrome from four digit factors",
            1000,
            9999,
            Ok(Some(Product{value: 1002001, factors: [(1001, 1001)]})),
        ),
        ("empty result for smallest if no palindrome in the range", 1002, 1003, Ok(None)),
        ("error result for smallest if min is more than max", 10000, 1, Err(Error.MinAboveMax)),
        (
            "smallest product does not use the smallest factor",
            3215,
            4000,
            Ok(Some(Product{value: 10988901, factors: [(3297, 3333)]})),
        ),
    ]
    |> subtests (description, min, max, expected), description
        assert palindrome_products.smallest(min, max) == expected
    end
end

test "largest"
    [
        (
            "find the largest palindrome from single digit factors",
            1,
            9,
            Ok(Some(Product{value: 9, factors: [(1, 9), (3, 3)]})),
        ),
        (
            "find the largest palindrome from double digit factors",
            10,
            99,
            Ok(Some(Product{value: 9009, factors: [(91, 99)]})),
        ),
        (
            "find the largest palindrome from triple digit factors",
            100,
            999,
            Ok(Some(Product{value: 906609, factors: [(913, 993)]})),
        ),
        (
            "find the largest palindrome from four digit factors",
            1000,
            9999,
            Ok(Some(Product{value: 99000099, factors: [(9901, 9999)]})),
        ),
        ("empty result for largest if no palindrome in the range", 15, 15, Ok(None)),
        ("error result for largest if min is more than max",       2,  1,  Err(Error.MinAboveMax)),
    ]
    |> subtests (description, min, max, expected), description
        assert palindrome_products.largest(min, max) == expected
    end
end
  • The search runs over palindromes, not over products. halves and mirror build every palindrome of a digit count from its first half (123 makes 12321 and 123321), in order, and the first one in the range of products that has a pair of factors in range is the answer. For the four-digit largest case the search tries 98 palindromes before 99000099, where a walk down the products would test close to a million numbers for being palindromes.
  • factors tries only the smaller factor, from value / max (rounded up) to the square root, so the larger one, value / a, is in range by construction. That is at most a few dozen divisions for the four-digit cases.
  • smallest and largest are one search from either end, picked by a Direction. in_order gives the numbers between two bounds from that end: the range first..=last, or Range.step_by(last..=first, -1), which counts down lazily. The two branches are different Iters, which join as one because in_order declares its result as Iter<Int>. The search drops the palindromes outside min² to max² from the near end and stops at the far one, so the same two steps serve both directions. The pipeline is lazy, so the search stops at the first palindrome with factors.
  • A result is Result<Maybe<Product>, Error>: Err(.MinAboveMax) for the canonical error, Ok(None) for the canonical “empty result” (a null value with no factors), and a Product struct holding the value and its factor pairs otherwise. A Product with an empty factor list cannot be built by the search, so Maybe says “none” instead.
  • first_product takes an Iter<Int>, so both directions share it.
  • The canonical cases are two subtests tables, one per property, named by the description column. Each table’s error row writes Error.MinAboveMax, which settles the error type the Ok rows leave open, so neither table needs an annotation.