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
endok smallest (7 cases)
ok largest (6 cases)
test result: ok. 13 passed, 0 failed
How it’s written
Section titled “How it’s written”- The search runs over palindromes, not over products.
halvesandmirrorbuild every palindrome of a digit count from its first half (123makes12321and123321), 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 before99000099, where a walk down the products would test close to a million numbers for being palindromes. factorstries only the smaller factor, fromvalue / 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.smallestandlargestare onesearchfrom either end, picked by aDirection.in_ordergives the numbers between two bounds from that end: the rangefirst..=last, orRange.step_by(last..=first, -1), which counts down lazily. The two branches are different Iters, which join as one becausein_orderdeclares its result asIter<Int>. The search drops the palindromes outsidemin²tomax²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” (anullvalue with no factors), and aProductstruct holding the value and its factor pairs otherwise. AProductwith an empty factor list cannot be built by the search, soMaybesays “none” instead. first_producttakes anIter<Int>, so both directions share it.- The canonical cases are two
subteststables, one per property, named by the description column. Each table’s error row writesError.MinAboveMax, which settles the error type theOkrows leave open, so neither table needs an annotation.