*iroi*

mechairoi の Blog

Project Euler Problem61

Perlの練習ということで

#!/usr/bin/perl
use strict;
use warnings;

my @paths;
$paths[$_] = [] for(0..99);
push(@{$paths[target($_)]}, [{8 => 1}, [source($_), target($_)]]) for (polygonals(8));

for(3..7)
{
  my @prev = @paths;
  $paths[$_] = [] for(0..99);
  foreach my $n (3..7)
  {
    foreach my $p (polygonals($n))
    {
      foreach (@{$prev[source($p)]})
      {
	unless($_->[0]->{$n})
	{
	  push (@{$paths[target($p)]}, [{%{$_->[0]}, $n => 1} , [@{$_->[1]}, target($p)]]);
	}
      }
    }
  }
}

foreach (@paths)
{
  foreach (@$_)
  {
    if ($_->[1]->[0] == $_->[1]->[6])
    {
      my $ans = 0;
      for (my $i = 0; $i < 6; $i++) {$ans += 101 * $_->[1]->[$i];}
      print "$ans\n";
    }
  }
}

sub polygonals
{
  my $n = shift;
  my @ret;
  my $p = 0; my $k = 0;
  while($p < 10000)
  {
    push @ret, $p if $p >= 1000 and source($p) >= 10 and target($p) >= 10;
    $p = polygonal($n, $k++);
  }
  return @ret
}

sub source
{
  return int($_[0] / 100);
}

sub target
{
  return $_[0] % 100;
}

sub polygonal
{
  my $k = shift;
  my $n = shift;
  return $n*(($k-2)*$n-$k+4)/2;
}

なんか気持ち悪い.
明日Perlの本借りる.