Problem 32 "Pandigital products"

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

問 32 「パンデジタル積」

すべての桁に 1 から n が一度だけ使われている数を n桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.

7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.

HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

use std::ops::RangeInclusive;

fn is_pandigital(a: u32, b: u32, ab: u32) -> bool {
    let mut bits = 0u16;
    for n in [a, b, ab].iter_mut() {
        while *n > 0 {
            let d = *n % 10;
            bits |= 1 << d;
            *n /= 10;
        }
    }
    bits == 0b1111111110u16
}

fn sum_distinct(arr: &mut [u32]) -> u32 {
    arr.sort();
    let mut sum = 0u32;
    if let Some(&n) = arr.get(0) {
        sum += n;
    }
    for i in 1..arr.len() {
        if arr[i - 1] != arr[i] {
            sum += arr[i];
        }
    }
    sum
}

fn explore_pandigital_combinations(
    a: RangeInclusive<u32>,
    b: RangeInclusive<u32>,
    products: &mut Vec<u32>,
) {
    for a in a {
        for b in b.clone() {
            let ab = a * b;
            if ab > 9876 {
                break;
            }
            if is_pandigital(a, b, ab) {
                products.push(ab);
            }
        }
    }
}

fn main() {
    let mut products = Vec::<u32>::new();
    explore_pandigital_combinations(2..=9, 1234..=9876, &mut products);
    explore_pandigital_combinations(12..=98, 123..=987, &mut products);
    let sum = sum_distinct(&mut products);

    println!("{}", sum);
    assert_eq!(sum, 45228);
}