ペプシ算クラス

ペプシ算 - 永字八法の続き
ペプシ算のクラスを作ってみた。
※書き直した！

サンプルスクリプト

use Pepsi;
# 問題設定をする。
my $pepsi = Pepsi->new(
	kind=>5,	# 5種類のおまけつきを
	bottle=>12	# １ダース買う
);
$pepsi->calc; # 計算する

my $result = $pepsi->total; # 計算結果を得る
# 計算結果は、何種類そろったかをキーとして確率を格納したハッシュリファレンス

# 計算結果を表示する。
print 'buy '.$pepsi->bottle." bottles.\n";
foreach my $get_kind ( sort { $a <=> $b } keys %{$result} ) {
	print 'get '.$get_kind.' kind(s) : %'.($result->{$get_kind}*100)."\n";
}

モジュール

package Pepsi;
use strict;
use bignum;
use base qw ( Class::Accessor );
__PACKAGE__->mk_accessors(qw(
	open_bottle
	bottle
	kind
	get_kind
	patern
));
sub new {
	my $invocant = shift;
	my $class = ref $invocant;
	$class ||= $invocant;
	my $self = bless {patern=>1, @_}=>$class;
	
	return $self;
}
sub rest_kind {
	my $self = shift;
	my $rest = $self->kind - $self->get_kind;
	return $rest;
}
sub calc {
	my $self = shift;
	$self->is_end and return;
	my @child = ();
	push @child, $self->new(
		open_bottle=>(1+$self->open_bottle),
		bottle=>$self->bottle,
		kind=>$self->kind,
		get_kind=>(1+$self->get_kind),
		patern=>($self->rest_kind * $self->patern)
	); # 新種が出た場合＆最初の一本は必ず新種
	if ( $self->open_bottle > 0 ) {
		push @child, $self->new(
			open_bottle=>(1+$self->open_bottle),
			bottle=>$self->bottle,
			kind=>$self->kind,
			get_kind=>$self->get_kind,
			patern=>($self->get_kind * $self->patern)
		); # 新種が出なかった場合
	}
	$self->{child} = \@child;
	map { $_->calc } @child;
	return 1;
}
sub is_end {
	my $self = shift;
	$self->get_kind < $self->kind or return 1;
	$self->open_bottle < $self->bottle or return 1;
	return undef;
}
sub is_live {
	return shift->is_end ? undef : 1;
}
sub ends {
	my $self = shift;
	my $result = shift;
	$result ||= [];
	if ( $self->{child} ) {
		map { $_->ends($result) } @{$self->{child}};
	} else {
		push @{$result}, $self;
#		print "End!\n";
	}
	return $result;
}
sub fraction {
	my $self = shift;
	my $patern = $self->patern;
	my $open_bottle = $self->open_bottle;
	while ( $open_bottle < $self->bottle ) {
		$patern *= $self->kind;
		++ $open_bottle;
	}
	return $patern;
}
sub total_child {
	my $self = shift;
	my %hash = ();
	map { $hash{$_->get_kind} += $_->fraction } @{$self->ends};
	return \%hash;
}
sub total_mother {
	my $self = shift;
	return $self->kind ** $self->bottle;
}
sub total {
	my $self = shift;
	my $child = $self->total_child;
	my $mother = $self->total_mother;
	foreach my $num ( keys %{$child} ) {
		$child->{$num} /= $mother;
	}
	return $child;
}
1;

考え方

まず、0種類の食玩がそろっているとする。
最初のボトルをあけると、0が1になる。
次のボトルをあけると、この1が1のままか2になるか、分岐が発生する。
ボトルがそろうか、全部開けてしまうかするまで、このツリーを全て調べる。

やってみた感想

再帰を使っているので、ちょっと数が大きくなると死ぬほど時間がかかるようになります。
なので、今度は再帰を使わない方法を思いついたのでそれを実装中。