Project Euler - Problem 43

問題

• 原文

  Let d₁ be the 1^st digit, d₂ be the 2^nd digit, and so on. In this way, we note the following:

  • d₂d₃d₄=406 is divisible by 2
  • d₃d₄d₅=063 is divisible by 3
  • d₄d₅d₆=635 is divisible by 5
  • d₅d₆d₇=357 is divisible by 7
  • d₆d₇d₈=572 is divisible by 11
  • d₇d₈d₉=728 is divisible by 13
  • d₈d₉d₁₀=289 is divisible by 17

  Find the sum of all 0 to 9 pandigital numbers with this property.

• 日本語訳

  d₁を1桁目, d₂を2桁目の数とし, 以下順にd_nを定義する. この記法を用いると次のことが分かる.

  • d₂d₃d₄=406は2で割り切れる
  • d₃d₄d₅=063は3で割り切れる
  • d₄d₅d₆=635は5で割り切れる
  • d₅d₆d₇=357は7で割り切れる
  • d₆d₇d₈=572は11で割り切れる
  • d₇d₈d₉=728は13で割り切れる
  • d₈d₉d₁₀=289は17で割り切れる

  このような性質をもつ0から9のPandigital数の総和を求めよ.

解答

Problem 41と同様にPandigital数を作るだけです。途中で枝切りして無駄な計算を省いています。

除数を保持する配列は一応定数にしてみました。定数の宣言には標準プラグマにconstantがありますが、コードが分かり易いAttribute::ConstantというCPANモジュールを使っています。

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/say/;
use Attribute::Constant;
use List::Util qw/sum/;
use Set::Object qw/set/;

my @divisors : Constant(2, 3, 5, 7, 11, 13, 17);
sub solutions(;$$);
sub solutions(;$$) {
  my ($num, $rest_digits) = @_;
  $num //= '';
  $rest_digits //= set(0 .. 9);
  my $len = length $num;
  return () if $len >= 4 and substr($num, -3, 3) % $divisors[$len - 4] != 0;
  return () if $num =~ /^0/;
  return ('') if $rest_digits->is_null;

  my @solutions;
  for my $n ($rest_digits->members) {
    $rest_digits->remove($n);
    push @solutions, map { $n . $_ } solutions($num . $n, $rest_digits);
    $rest_digits->insert($n);
  }
  return @solutions;
}

say sum solutions;