読者です 読者をやめる 読者になる 読者になる

オフトゥン大好き

惰眠系プログラマの作業ログで( ˘ω˘ ) スヤァ…

No.227 簡単ポーカー 解法

プログラミング 解説 アルゴリズム 有限オートマトン yukicoder

No.227 簡単ポーカー - yukicoderを解いた。

手札の役を作る処理は決定性有限オートマトンに置き換えられる。

開始状態はNO HANDとし、空のスタックを用意してソートした入力リストを先頭から順に積んでいく。ソートは同じ値をグループ化するために行なっているので昇順でも降順でも構わない。

  • 入力リストから取り出した値がスタックtopと同じならそのまま積む
  • 入力リストから取り出した値がスタックtopと異なるならスタックサイズを入力として状態遷移し、スタックを空にしてから値を積む

状態遷移表は次のようになる。TWO PAIRが必要ないのは入力リストから取り出した値がスタックtopと同じであるかぎり積んでいくのでTWO PAIR => FULL HOUSEという遷移はあり得ないため。

# \ s NO HAND ONE PAIR THREE CARD
2 ONE PAIR TWO PAIR FULL HOUSE
3 THREE CARD FULL HOUSE -

(#:スタックサイズ, s:現在の状態)

これを元にパスを作っていくと次のような状態遷移図が出来上がる。

f:id:nukosuke:20161023162936p:plain:w320

これをPerlで実装した。

sub trans {
  my ($state, $stack_size) = @_;
  if    ($state eq "NO HAND"    && $stack_size == 2) { return "ONE PAIR";   }
  elsif ($state eq "NO HAND"    && $stack_size == 3) { return "THREE CARD"; }
  elsif ($state eq "ONE PAIR"   && $stack_size == 2) { return "TWO PAIR";   }
  elsif ($state eq "ONE PAIR"   && $stack_size == 3) { return "FULL HOUSE"; }
  elsif ($state eq "THREE CARD" && $stack_size == 2) { return "FULL HOUSE"; }
  else  { return $state; }
}

my @A = sort { $a <=> $b } map { $_ + 0 } split ' ', <>;
my $state = "NO HAND";
my @stack = ();

foreach (@A) {
  if ($#stack >= 0 && $_ != $stack[$#stack]) {
    $state = trans($state, $#stack+1);
    @stack = ();
  }
  push @stack, $_;
}
print(trans($state, $#stack+1) . "\n");

関連記事