1.1,1.2,...,2.0と四則演算の組合せ、最大値は？

こんなお題がtwitterに

http://twitter.com/oneb/status/21395051716:twitter
ちなみにいわなちゃんってのは自分じゃなくて@xcirのことです。

とりあえず総当たりプログラムを書いてみた

とても現実的な時間じゃ終わらなそうだし、ちょっとバグありそう。
なにか思いついたら直すやも。

#!/usr/bin/perl
use strict;
#use warnings;
use Math::Combinatorics;

my @stack = ();

my %operator = (
  '+' => \&plus, '-' => \&minus, '*' => \&multiply, '/' => \&division,
);

sub plus {
  my $n2 = pop @stack;
  my $n1 = pop @stack;
  push @stack, $n1 + $n2;
}

sub minus {
  my $n2 = pop @stack;
  my $n1 = pop @stack;
  push @stack, $n1 - $n2;
}

sub multiply {
  my $n2 = pop @stack;
  my $n1 = pop @stack;
  push @stack, $n1 * $n2;
}

sub division {
  my $n2 = pop @stack;
  my $n1 = pop @stack;
  push @stack, $n1 / $n2;
}

sub calc_rpn {
  my @ops = @_;
  foreach my $item ( @ops ) {
    my $op = $operator{$item};
    if( $op ){
      die "stack underflow: $item [@stack]\n" if @stack < 2;
      &$op;
    } else {
      push @stack, $item;
    }
  }
  die "expression error: [@stack]\n" if @stack != 1;
  pop @stack;
}

sub is_num { $_[0] != 0 }

#my @nums = (1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0);
my @nums = (1.1, 1.2, 1.3, 1.4, 1.5);
my @ops  = qw(+ - * /);
my $max = 0;
my @max_items;
my $end_num = 0;

my $comb1 = Math::Combinatorics->new(
  count => @nums - 1,
  data  => [qw(+ - * /)] ,
  frequency => [map {@nums-1} 0..3]
);
while ( my @op = $comb1->next_multiset ) {
  my $comb2 = Math::Combinatorics->new(
    data => [@nums, @op],
    frequency=>[map {1} (@nums, @op)]
  );
  while ( my @items = $comb2->next_string) {
    next if !is_num($items[0]) || !is_num($items[1]) || is_num($items[-1]);
#    print join(",", @items).":";
    my $ret = eval{ calc_rpn(@items)};
    if($@){
#      print $@;
#      print "\n";
      @stack = ();
    }else{
#      print "$ret\n";
      if($ret > $max){
         $max = $ret;
         @max_items = @items;
      }
      unless(++$end_num % 10000){
        print "$end_num\t";
	print  join(" ",@items)."\t";
	print  join(" ",@max_items).":$max\n";
      }
    }
  }
}
print "MAX:".join(" ",@max_items).":$max\n";