レッツ・チャレンジパソコン甲子園第12回の問題を解いてみた

lisp algorithm

日経ソフトウェア2008年4月号のパソコン甲子園の問題を解く連載．今回はブラックジャックの手札が与えられた際に点数を返すというもの．


とても時間がかかりました．けれど，解法にはそれなりに満足．

ブラックジャックルール説明

ブラックジャックは，1〜13の数が書かれたカードを使う．

  • 1は1点，あるいは11点
  • 2から9までは書かれている数通りの点数
  • 10から13までは10点

手札の合計で点数を決める．手札による合計点の算出方法は以下の通り

  • カードの点数の合計が21より大きくなるときは0点
  • 1は1点と計算しても11点と計算してもよいが，手の点数が最大となるほうを選ぶこととする（ただし21を超えない範囲で）

問題

配られたカード情報を入力とし，手の点数を出力するプログラムを作成せよ．
ただし，ひとつの手に含まれるカードの枚数nは1以上21以下とし，同じ数を何枚も含むことができるものとする．



どうやらこの問題は高めの50点問題，そして正答率が40%．ぱっと見の難易度を考えたらなんでこんなに点数が高くて，そして正答率が低いんだろう，と思った．けれど気がついて納得（？）．問題の最後の条件から，ひとつの手札に21枚1が含まれていることがある，という場合にきちんと21点を返せないんじゃないかなと思ったりする．


この問題のポイントは，1を11点と数えるか1点と数えるか，というロジック．問題が簡単だからLispで書こうと思ったのだけれど，ロジックが思い浮かばず10分で諦める．


正直悔しかったので，他の作業をしながら考えていたら思いついた．

1の点数を11点とする．
手札に含まれる1の枚数をk枚とする．
手札の合計をtとする．

tが21を超えており，かつkが1枚以上あれば
tにt-10を代入し，kにk-1を代入する

わかりづらッ！
こゆことです．なんとなくRubyスタイル

while t > 21 and k > 0
  t = t - 10
  k = k - 1
end

1の点数を11点に固定しておいて21を超えたら引く，というad-hocなアプローチ．
というわけで問題が一気に簡単になり，与えられた手札の中に何枚1が含まれているかを数えれば解けるようになった．


Lispで実装してみた．whileが便利すぎるのでEmacs-lispまたはXyzzy-lispで．
black-jack関数内で1の数を数えて，black-jack-sub関数で上述のロジックを計算している．

(defun black-jack (lis)
  (let ((count-of-1 0))
    (dolist (x lis)
      (if (= x 1) (setq count-of-1 (1+ count-of-1))))
    (black-jack-sub lis count-of-1)))

(defun black-jack-sub (lis count)
  (let ((total 0) (tmpcount count))
    (dolist (card lis)
      (setq total (+ total (bj-score card)))
      (while (and (> total 21) (>= tmpcount 1))
	(progn
	  (setq total (- total 10))
	  (setq tmpcount (1- tmpcount)))))
    (if (> total 21) 0 total)))

(defun bj-score (card)
  (cond ((= 1 card) 11)
	((>= card 10) 10)
	(t card)))

(black-jack '(1))
=> 11
(black-jack '(7 7 7))
=> 21
(black-jack '(7 7 8))
=> 0
(black-jack '(12 1))
=> 21
(black-jack '(10 1 1))
=> 12
; こんなパターンもありうる
(black-jack '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1))
=> 21

ちゃんと解けた！
高校3年生に比べて4/3倍生きている面子が保てた？