LL2006 君ならどう書く ROUND2 [Perl]

| コメント(0)
Round2はCollatz予想というものらしい. で、早速

#!perl
#

use strict;

sub f;
sub g;
sub h;

use Time::HiRes;

my $t = Time::HiRes::time;
print h(100), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub f {
  my $n = shift;
  if ( $n == 1 ) {
    1;
  }
  elsif ( $n % 2 ) {
    3 * $n + 1;
  }
  else {
    $n / 2;
  }
}

sub g {
  my $n = shift;
  my $cnt;
  do {
    ++$cnt;
  } until ( ($n = f($n)) == 1 );
  ++$cnt;
}

sub h {
  my $n = shift;

  my $k;
  my $max_g;
  for ( 1 .. $n ) {
    my $g = g($_);
    if ( $g > $max_g ) {
      $k = $_;
      $max_g = $g;
    }
  }
  $k;
}
うむぅ、エレガントでない..
では、Language::Functionalモジュールを使ってみて、

#!perl
#

use strict;

use Language::Functional qw(:all);
use Time::HiRes;

my $t = Time::HiRes::time;
print h(100), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub f {
  my $n = shift;
  if ( $n == 1 ) {
    1;
  }
  elsif ( $n % 2 ) {
    $n*3+1;
  }
  else {
    $n/2;
  }
}

sub g {
  my $n = shift;
  my $c;
  Until { ++$c && shift() == 1; } \&f, $n;
  $c;
}

sub h {
  my $n = shift;
  my $max = maximum([map {g($_)} (1..$n)]);
  
  head(filter sub {g(shift) ==  $max}, [1..$n]);
}
....変わらねー T_T .
.
[追記]
よく考えたら f()は

sub f{
  my $n = shift;
  ($n % 2) ? $n*3+1 : $n/2;
}
で十分ですな。

[さらに追記]
もっと短くなった。わぁい(っても速度は変わらない(h(100000)で17.5秒くらい)けど)

#!perl
#

use strict;

sub g;
sub h;

use Time::HiRes;

my $t = Time::HiRes::time;
print h(100000), "\n";
printf "%-10.2f ms elapsed\n", (Time::HiRes::time - $t)*1000;

sub g {
  my $n = shift;
  $n == 1 ? 1 : 1 + g(($n%2) ? $n*3+1 : $n/2)
}

sub h {
  scalar((
    sort { $b->[1] <=> $a->[1] } 
    map { [$_, g($_)] } 1 .. shift
  )[0])->[0];
}

コメントする

AUTHOR

  • turugina (虎王 剱奈)
  • E-mail: turugina {at} floralcompany.jp
  • pixiv
  • ニジエ

2014年5月

        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

アーカイブ

OpenID対応しています OpenIDについて
Powered by Movable Type 5.2.10

- 警 告 -

本サイトにはいわゆる「18禁画像」(イラスト)へのリンクが存在します。 未成年の方や、その手の画像に不快感を覚える方は、 該当記事(「えちぃの」及び「ちょっとえちぃの」カテゴリ) をご覧にならないようお願いいたします。

上記を理解した上で非表示のブログパーツを表示する
あわせて読みたいブログパーツ
ついった
drawr/pixiv/twitpic