Problem 61 "Cyclical figurate numbers"

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
Square P4,n=n2 1, 4, 9, 16, 25, ...
Pentagonal P5,n=n(3n−1)/2 1, 5, 12, 22, 35, ...
Hexagonal P6,n=n(2n−1) 1, 6, 15, 28, 45, ...
Heptagonal P7,n=n(5n−3)/2 1, 7, 18, 34, 55, ...
Octagonal P8,n=n(3n−2) 1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

  1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
  2. Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.
  3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

問 61 「巡回図形数」

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

  • この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
  • それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
  • 4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

#[derive(Debug)]
struct PolyNum {
    left: u8,
    right: u8,
    side_ident: u8,
}

fn next(filter: u8, polynums: &[PolyNum], chain: &[&PolyNum]) -> Option<u32> {
    if filter == 0b11111100 {
        if chain[chain.len() - 1].right != chain[0].left {
            return None;
        }
        println!("{:#?}", chain);
        let sum = chain
            .iter()
            .map(|&pn| pn.left as u32 * 100 + pn.right as u32)
            .sum();
        return Some(sum);
    }
    let oks = polynums
        .iter()
        .filter(|&pn| pn.left == chain[chain.len() - 1].right)
        .filter(|&pn| pn.side_ident & filter == 0)
        .collect::<Vec<&PolyNum>>();
    for pn in oks {
        let chain = chain
            .iter()
            .map(|&p| p)
            .chain(std::iter::once(pn))
            .collect::<Vec<&PolyNum>>();
        let child = next(filter | pn.side_ident, polynums, &chain);
        if child.is_some() {
            return child;
        }
    }
    None
}

fn generate_four_digit_polygonal_numbers(side: u32) -> Vec<PolyNum> {
    let polygonal_number_genenerator_builder =
        |side: u32| move |n: u32| (side - 2) * n * (n - 1) / 2 + n;

    let gen = polygonal_number_genenerator_builder(side);
    let mut polynums = vec![];
    for n in 1u32.. {
        let x = gen(n);
        if x > 9999 {
            break;
        }
        if x < 1000 {
            continue;
        }
        polynums.push(PolyNum {
            left: (x / 100) as u8,
            right: (x % 100) as u8,
            side_ident: 1 << (side - 1),
        });
    }
    polynums
}

fn cyclical_figurate_numbers() -> u32 {
    let octs = generate_four_digit_polygonal_numbers(8);

    let mut polynums = vec![];
    for s in 3u32..=7 {
        polynums.extend(generate_four_digit_polygonal_numbers(s).into_iter());
    }

    for oct in &octs {
        if let Some(sum) = next(oct.side_ident, &polynums, &vec![oct]) {
            return sum;
        }
    }
    unreachable!();
}

fn main() {
   let ans = cyclical_figurate_numbers();
   println!("{}", ans);
   assert_eq!(ans, 28684);
}