Project Euler - Problem 34

問題

• 原文

  Find the sum of all numbers which are equal to the sum of the factorial of their digits.

• 日本語訳

  各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.

解答

Problem 30とほぼ同じ問題なので、その時の解答を基にして考えます。

前回の問題と違うのは、0! = 1なので0を含む数字を含まない数字と同一視できない点です。 そこで正規化の際に0を省くのをやめて、例えば251と2501はそれぞれ125と0125として別に扱うことにします。

また0! = 1!なので、例えば110と100のように各桁の階乗の和が同じになる数が存在し、これを重複して数えないようにしなければなりません。 既に数えた値を連想配列で覚えておいてもいいのですが、List::MoreUtilsのuniq関数で重複要素を前もって削除する方が高速でした。

#!/usr/bin/env perl;

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/sum reduce/;
use List::MoreUtils qw/uniq/;

sub factorial($) {
  our ($a, $b);
  my $n = shift;
  return 1 if $n == 0;
  return reduce { $a * $b } 1 .. $n;
}

my @facts = map { factorial $_ } 0 .. 9;
my $max_digits;
for ($max_digits = 1;
     10 ** $max_digits <= $max_digits * $facts[9];
     $max_digits++) {}

my @sum_dicts = ({}, { map { ($_ => $facts[$_]) } 0 .. 9 });
until ($#sum_dicts == $max_digits) {
  push @sum_dicts, { map {
    my $prev_key = $_;
    my $last_digit = substr $prev_key, -1, 1;
    map {
      ("$prev_key$_" => $sum_dicts[-1]{$prev_key} + $facts[$_])
    } $last_digit .. 9;
  } keys %{ $sum_dicts[-1] } };
}

say sum grep {
  my $sorted = join '', sort split //;
  $_ == $sum_dicts[length $sorted]{$sorted} and $_ != 1 and $_ != 2;
} uniq map { values %$_ } @sum_dicts;