CodeIQ:ボーリングの最高点、最低点は?

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ボーリングの最高点、最低点は?」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
東京オリンピックの追加種目の候補に挙がりながら、落選したボーリング。
それでも若い人から年配の人まで、幅広く楽しめるゲームとして人気です。

このボーリングの点数を計算してみます。
ただし、各フレームのスコアが与えられるのではなく、ストライクとスペアの回数が与えられます。
指定された回数だけストライクとスペアが出た場合の最高点と最低点との差を求めてください。

例えば、ストライクとスペアが5回ずつの場合、以下の図のような場合に最低点110点と最高点235点になります。
そこで、この差である125を出力します。

fig.1

同様に、ストライクが12回、スペアが0回のときは最低点、最高点ともに300点ですので差は0、ストライクが0回、スペアが0回のときは最低点が0点、最高点が90点ですので差は90になります。

標準入力からストライクとスペアの回数がスペース区切りで与えられます。
最高点と最低点の差を標準出力に出力してください。
なお、ありえない回数が入力されることはないものとします。

【入出力サンプル】
標準入力
5 5

標準出力
125

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Min = 1000
$Max = 0

def calcMin(ptn)
	ret = 0

	for i in 0...10
		if ptn[i] == "a" then
			if ptn[i+1] == "a" then
				if ptn[i+2] == "a" then ret += 30
				else ret += 20
				end
			elsif ptn[i+1] == "b" then ret += 20
			else ret += 10
			end
		elsif ptn[i] == "b" then
			if ptn[i+1] == "a" then ret += 20
			else ret += 10
			end
		else
			ret += 0
		end
	end

	return ret
end

def calcMax(ptn)
	ret = 0

	for i in 0...10
		if ptn[i] == "a" then
			if ptn[i+1] == "a" then
				if ptn[i+2] == "a" then ret += 30
				else ret += 29
				end
			elsif ptn[i+1] == "b" then ret += 20
			else ret += 19
			end
		elsif ptn[i] == "b" then
			if ptn[i+1] == "a" then ret += 20
			else ret += 19
			end
		else
			ret += 9
		end
	end

	return ret
end

def solve(f, a, b, c, ptn)
	if f == 10 then
		# 10フレーム目のパターン
		#    a*3			XXX : OK
		#    a*2 b*1		XX/ : NG	X/X : NG	/XX : NG
		#    a*2 c*1		XXn : OK	XnX : NG	nXX : NG
		#    a*1 b*2		X// : NG	/X/ : NG	//X : NG
		#    a*1 b*1 c*1	X/	: OK	Xn/ : NG	/X  : OK	/nX : NG	nX/ : NG	n/X : NG
		#    a*1 c*2		Xn	: OK	nXn : NG	nnX : NG
		#    b*3			/// : NG
		#    b*2 c*1		//n : NG	/n/ : NG	n// : NG
		#    b*1 c*2		/n	: OK	n/	: NG
		#    c*3			n	: OK
		ptn1 = nil
		ptn2 = nil
		if (a == 3) then ptn1 = ptn + "aaa"
		elsif (a == 2) && (c == 1) then ptn1 = ptn + "aac"
		elsif (a == 1) && (b == 1) && (c == 1) then
			ptn1 = ptn + "ab"
			ptn2 = ptn + "ba"
		elsif (a == 1) && (c == 2) then ptn1 = ptn + "ac"
		elsif (b == 1) && (c == 2) then ptn1 = ptn + "bc"
		elsif (c == 3) then ptn1 = ptn + "c"
		end

		if ptn1 != nil then
			mn = calcMin(ptn1)
			$Min = mn if $Min > mn

			mx = calcMax(ptn1)
			$Max = mx if $Max < mx
		end

		if ptn2 != nil then
			mn = calcMin(ptn2)
			$Min = mn if $Min > mn

			mx = calcMax(ptn2)
			$Max = mx if $Max < mx
		end

		return
	end

	solve(f+1, a-1, b, c, ptn + "a") if a > 0
	solve(f+1, a, b-1, c, ptn + "b") if b > 0
	solve(f+1, a, b, c-1, ptn + "c") if c > 0
end

# main
while line = gets
	line.strip!
	next if line.empty?

	a, b = line.split.map{|v| v.to_i}
	solve(1, a, b, 12-(a+b), "")
	p $Max - $Min
end

解説

それほど難しい問題ではないと思いますが結構面倒です。
もっとうまい方法があるかもしれませんが。

考え方

私は入力値のスペア、ストライクのパターンを全て列挙してそれぞれについて最大値、最小値を計算して結果を求めました。
具体的なやり方は次の通りです。

まず、ストライクを'a'、スペアを'b'、それ以外を'c'で表します。
'a'と'b'回数は入力値から、'c'の回数は12-(ストライク回数+スペア回数)とします。これと過去の履歴(文字列)、フレーム数を引数に取り、'a'〜'c'のどれかを履歴に追加し、カウントダウンする関数を用意します。これを再帰的に呼び出すことでパターンを生成できます。ただし、10フレーム目だけは扱いが特殊なので手でどのようなパターンになるかを求め、'a'〜'c'の残り回数に従って条件文で生成しました。

この方法だとパターン数は310以下なので全列挙しても時間的に間に合います。

次に点数の計算方法です。
最低点はストライクでもスペアでもなければ[0,0]、ストライクかスペアの次がスペアなら[0,10]だったとし、ストライクかスペアの隣がストライクでもスペアでもなかったら[0,0]だったとして扱えば最低点になります。
最低点はストライクでもスペアでもなければ[9,0]、ストライクかスペアの次がスペアなら[9,1]だったとし、ストライクかスペアの隣がストライクでもスペアでもなかったら[9,0]だったとして扱えば最低点になります。

後は、全パターンに対して計算した最高点と最低点の中で最高のものから最低のものを引いた値を結果として印字すればOKです。

main

入力値を数値にしてsolve()に渡し、パターンを列挙してそれぞれの最低点、最高点を大域変数$Minと$Maxに記録します。
$Minは1000、$Maxは0(多分最高点は330くらい? なので適当にそれより十分大きな値)を初期値とし、$Minより計算結果が小さければ、$Maxより計算結果が大きければ更新します。
solve()の第4引数cが12-(a+b)なのはストライクでもスペアでもないフレームの回数の最大値です。
最終的に$max-$minを印字します。

solve(f, a, b, c, ptn)

考え方の通りにパターンを生成します。
fはフレーム数で1から始まり関数が再帰呼び出しされるごとに10までカウントアップします。
aはストライクの残り回数、bはスペアの残り回数、cはストライクでもスペアでもないフレームの残り回数です。
ptnは各フレームの結果('a'〜'c'で構成される文字列)です。

69〜77行目は10フレーム目のパターン生成と終了条件です。a〜cの残り回数から求めていて、X:ストライク、/:スペア、n:ストライクでもスペアでもないとすると次のパターンがあります。
XXX、XXn、X/、/X、Xn、/n、n
いずれの場合も、引数aとbは10フレーム目に割り当てた時点でちょうど0にならないとダメなのでそれを条件としてif文でチェックし、それ以外の場合は無視します。

79〜85行目、87〜93行目はそれぞれパターンに対して最小得点を計算(calcMin())、最大得点を計算(calcMax())しています。
また、$Minと$Maxが更新可能なら更新します。

calcMin(ptn)

考え方に書いた通り、最小得点を計算します。
引数ptnは10〜12文字で構成されていて、10フレーム目だけが最大3文字(ストライク、ストライク、ストライク)になります。
ループで1フレーム目から順にチェックし、ストライクやスペアなら+1、+2フレーム目もみてチェックします。

calcMax(ptn)

最大得点を計算します。
基本的に最小得点と同じで点数だけが異なります。

雑感

calcMin()とcalcMax()は一つの関数にまとめられました。
もっとうまい方法があるかもしれませんが、まずまずの方法と思います。