Round 2の続き。[Perl6を追記しました]

LLR2006
 キミならどう書く 2.0 - ROUND 2 - ? Lightweight Language Ring
このとき
h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))
について h(100) を求めよ．

javascript

お約束。アルゴリズムはこちらと変わらず。速度は遅い。

h() = where g() = [Elapsed Time: seconds] 

function Collatz(){
  this.timer = 0; this.hmax = 0; this.gmax = 0;
  this.g = function(num){
    var n = num;
    for (step = 1; n > 1; step++) 
      n = (n & 1) ? (3 * n + 1) : (n >> 1);
      // n = (n % 2) ? (3 * n + 1) : (n / 2); // no difference in speeed
    if (n != 1) alert('g(' + num + ') got ' + n + '!!');
    return step;
  }
  this.h = function(n){
    for (var i = 1; i <= n; i++){
      var gnext = this.g(i);
      if (gnext > this.gmax){
        this.hmax = i; this.gmax = gnext;
      }
    }
  }
  this.run = function(n){
    var start  = (new Date()).getTime();
    this.h(n);
    this.timer = ((new Date()).getTime() - start)/1000;
  }
}

Golfing

西尾泰和のブログ: Pythonで75文字でCollatz角谷問題の(以下略
f = lambda x: x == 2 and 1 or f(x % 2 and x * 3 + 1 or x / 2) + 1; max(map(f, range(2, 101)))

これなのだが、h(100)ではなくg(h(100))を解いてしまう。

以下、perlでgolfしてみた例。

% perl -e '$m=shift;printf"h($m)=%d,g=%d\n",@{(sort{$b->[1]<=>$a->[1]}map{$n=$_;$s=0;while($n>1){$n=$n&1?3*$n+1:$n>>1;$s++}[$_=>$s]}(1..$m))[0]};' 100
h(100)=97,g=118

18禁正規表現

こんなのいかが?

sub g{local($_)=$_[0];$_==1?1:1+g(m/^(1+)\1$/?$1:"1$_$_$_")}
sub h{@{(sort{$$b[1]<=>$$a[1]}map{[$_=>g(1x$_)]}1..shift)[0]}}
$n=shift||100;printf"h($n)=%d,g=%d\n",h($n)

Dan the Terminated Man

追記:Perl6

なるべくPerl6らしさを詰め込みました。&?BLOCK()の使い方に注目!

my $n = @*ARGS.shift || 100;
my @v = (1..$n).map:{[
    $^i, {$^n==1 ?? 1 !! 1 + &?BLOCK($^n +& 1 ?? $^n*3+1 !! $^n +> 1)}($^i)
]}.sort:{ 
    $^b[1] <=> $^a[1] 
}[0];

Pugsだとまだまだ遅いけど。

% /usr/bin/time pugs cool.p6 
h(100)=97 where g(97) = 119
        5.29 real         5.16 user         0.08 sys