みずぴー日記

Problem43

Perl 30分プログラム

30分プログラム、その316。Problem43 - Project Euler。

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.
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数の総和を求めよ.

2の倍数、3の倍数、...、17の倍数をあらかじめ用意しておいて、それの組み合せで作れるPandigital数を求めるようにした。
そのために、倍数をリストにいれるようにしたんだけれども、Perlでリスト操作はやるもんじゃないね。入れ子のリストが使えないのは本当に不便だ。

使い方

$ perl problem43.pl
Name "main::b" used only once: possible typo at problem43.pl line 81.
Name "main::a" used only once: possible typo at problem43.pl line 81.
16695334890

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# problem43.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/06/01 21:01:18
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
use strict;
use warnings;
use List::Util qw(reduce sum);
use Data::Dumper;

sub make($){
    my ($n) = @_;
    my @xs = ();

    for(my $i = 0; $i < 1000/$n;$i++){
	my $m = $n*$i;
	if($m =~ /\A(\d)(\d)(\d)\Z/ and ($1 != $2 and
					 $2 != $3 and
					 $2 != $3)){
	    @xs = (@xs,[$1,$2,$3]);
	}elsif($m =~ /\A(\d)(\d)\Z/ and ($1 != $2)){
	    @xs = (@xs,[0,$1,$2]);
	}
    }
    @xs;
}

sub is_connect($$){
    my ($x,$y) = @_;
    @$x[-2] == @$y[0] and @$x[-1] == @$y[1];
}

sub conn(@){
    if(@_ > 1){
	my ($x,@xs) = @_;
	my $y = &conn(@xs);

	my @ys = ();
	for my $n (@$x){
	    for my $m (@$y){
		if(is_connect($n,$m)){
		    @ys = (@ys,[@$n[0],@$m])
		}
	    }
	}
	[@ys];
    }else{
	$_[0];
    }
}

sub is_pandigital(@){
    my %xs = ();
    for(@_){
	if(defined $xs{$_}){
	    return 0;
	}else{
	    $xs{$_} = 1;
	}
    }
    defined $xs{0};
}

sub make_pandigital(@){
    my %xs = ();
    for(@_){
	$xs{$_} = 1;
    }
    for(1..9){
	unless(defined $xs{$_}){
	    return reduce {$a * 10 + $b } ($_,@_);
	}
    }
}

my @ds = map { [ make($_) ] } (2,3,5,7,11,13,17);
my @xs = @{conn(@ds)};
my @ys = grep { is_pandigital @$_ } @xs;
my @zs = map { make_pandigital @$_ } @ys;

print sum(@zs),"\n";

参考