CodeIQ:カードを使って数を作ろう(両面編)

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カードを使って数を作ろう(両面編)」(CodeIQ)を参照してください。

問題の概要

問題を引用します。

【概要】
カードが何枚かあります。
カードには両方の面に、一桁の数字が書いてあります。同じ数字のこともあれば、異なる数字のこともあります。
カードをn枚選んで並べて数を作ります。並べる際には、カードのどちらの面を使っても構いません(もちろん、両面同時には使えません)。
作れる数のうち、ある数 m にもっとも近い数を答えてください。

【入出力】

入力は
4,1234,17/82/72/83/98/97/98
のような感じです。
コンマ区切りで、n(カードの枚数)、m(この値に近い数を作る)、カード列 が並んでいます。
カード列は、カードに書いてある数字をスラッシュ区切りで並べたものです。
カードの情報は、表の数字と裏の数字を区切り文字なしで並べたものです。 例えば上記の例は

n( 使うカードの枚数 )4
m(この値に近い数を作る)1234
1枚目のカード表が1で裏が7
2枚目のカード表が8で裏が2
3枚目のカード表が7で裏が2
4枚目のカード表が8で裏が3
5枚目のカード表が8で裏が9
6枚目のカード表が9で裏が7
7枚目のカード表が9で裏が8
ということを意味しています。

出力は、
1232
のような感じです。最も近い数が2つある場合は、小さい順に両方共出力してください。
1233,1235
のような感じです。
末尾の改行はあってもなくても構いません。
作れる数がひとつもない場合には、-を出力してください。

【補足】
「01」のような、「0」で始まる二桁以上の数は作れません。一桁の「0」はOKです。
カードの枚数は8枚以下です。
n は 1以上で、カードの枚数を超えることはありません。
m は 0以上、10の9乗以下です。
6 のカードを逆さにして 9 として使ったりすることはできません。
不正な入力に対処する必要はありません。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def toNum(m, ptn)
	ret = [0]
	ptn.each_with_index{|c, i|
		n0 = c[0].to_i	# 表の値
		n1 = c[1].to_i	# 裏の値

		# 2桁以上の数値で先頭が0はエラー
		if (ptn.size > 1) && (i == 0) && (n0 == 0) && (n1 == 0) then
			ret = []
			break
		end

		r = 10**(ptn.size - i - 1)	# 桁(上の桁から決める)

		# 値の候補を作る
		cands = []
		for j in ret
			cands << j + n0*r
			cands << j + n1*r
		end

		sm = 999999999
		mr = (m/r) * r	# mの上位(i-1)桁の値

		for cd in cands
			# 2桁以上の場合で候補値が0(=先頭が0)はエラー
			if (ptn.size > 1) && (cd == 0) then next end

			sb = cd-mr

			# cdがmrより小さい場合、最後の桁の場合を除いてrを加えて評価しなければならない
			# (例:m=200 cd=[100,200]の場合、100から199になる可能性があり、
			#  199は201と同じ近さになるので100は候補に残さなければならない)
			if (i != 0) && (sb < 0) then sb = (sb+r).abs
			else sb = sb.abs
			end

			if sb < sm then
				nxt = [cd]
				sm = sb
			elsif sb == sm then
				nxt << cd
			end
		end

		ret = nxt
	}

	return ret
end

def solve(n,m,cards)
	ret = []
	bs = 9999999999
	cards.permutation(n){|ptn|
		cands = toNum(m, ptn)
		if cands.empty? then next end

		s = (m-cands[0]).abs	# 候補値はすべて同じだけ近いので最初の値だけを比較すれば良い
		if s < bs then
			ret = cands
			bs = s
		elsif s == bs then
			ret = ret + cands
		end

		# 差が0に成ったらそれ以上の結果はないのでやめる
		if s == 0 then break end
	}

	return ret.uniq.sort
end

def printResult(ptn)
	if ptn.empty? then
		puts("-")
	else
		puts(ptn.join(","))
	end
end

while line = gets
	line.strip!
	if line.empty? then next end

	sc = line.split(",")

	n = sc[0].to_i
	m = sc[1].to_i
	cards = sc[2].split("/")

	ret = solve(n,m,cards)
	printResult(ret)
end

解説

「カードを使って数を作ろう(簡単編)」の続編です。が、こちらの問題は★★★★となっています。

計算量

簡単編は総当たりで問題なかったのですが、こちらの問題では最悪の場合、28×8!の計算量になり、総当たりでやった場合1秒では厳しくなります。ただ、私は非常にいい加減な(限定的な)条件だけでクリアしてしまいました。テストケースはすべてパスしていますがパターンによっては制限時間を超える場合があると思っています(後述します)。

solve()

引数n,m,cardsは入力値をパースして数値にしたものです。
cardsは["17","82","72","83","98","97","98"]のようなカードの値の配列です。
Rubyなのでcardsにpermutation()を使ってパターンを列挙します。
そしてtoNum()でパターンを数値に変換します。toNum()はcardsの裏表で作れる数値のうちmに最も近い値の配列を返します。エラー時は空の配列を返します。
そして帰ってきた候補値の最初の値(cands[0])とmの差の絶対値を取り、以前の差の絶対値より小さくなっていたら結果を更新します。以前の差の絶対値と同値なら結果に追加します(61〜67行目)。toNum()が返す値とmとの差は全て同じなので最初の値のみの比較でOKです。

もし、差が0に成った(mを作ることができた)らそれ以上mに近い値は作れないので処理をやめます。
これがこのプログラムのいい加減な部分で、カードが「88/88/88/88/88/88/88/79」でm=88888888、n=8のような入力値の場合、処理を止めることができず時間切れになると思うのです。

結果は同じ値が重複していたり、順番が昇順になっていないのでuniqしてsortしてから返します。

toNum()

引数ptnのカードの並びでmに最も近い値を作ります。
ptnの値を先頭から順に取り出し、裏表それぞれを数値(n0, n1)にします。
なお、仕様で先頭を0とした2桁以上の値はダメなのでチェックして弾きます(10〜13)行目。

値の候補を作ります。
まず、ptnの先頭要素が最も大きな位、最後の要素が1の位なので取り出した値の桁にします。15行目で後ろに何個0をつけるかを決定し、19〜22行目で取り出した値までの数値を作ります。
retは返却値の配列ですが、処理の途中では処理している桁までで最も近くなる可能性のある値が入っています(途中段階で最も近い値ではないことに注意してください)。
例えば、ptn=["17","82","72","83"]、m=1234で2回目のループの場合、この時点で1800と1200が作られます。

次に候補値を絞り込みます。
smはmと候補地の差です。
mrはmの現在処理している桁より後を0にしたものです(先の例で1234で上位2桁目を処理する時点ではmr=1200)。
candsに入っている候補値全てに対してmrとの差をとって最も近いものを選ぶのですが、1桁ごとに絞り込むので注意が必要です。コメントに書いてありますが、m=200で最も上の位を処理している時点の候補が[100,200]の場合、100を捨てることはできないのです。最終的に作れる数字が202と199だとすると199の方がmに近いので100を残しておかないと間違った結果になってしまいます。
そのため1の位を処理する場合以外は候補値とmrの差がマイナスの場合、rを差に加えて評価します。m=200で最上位桁処理時点の候補値が[100,200]の場合、mr=200なので候補値100との差は-100ですがr=100を加えると差は0になるので候補値200と同じ評価になります。
なお、1の位を処理している時はこのような加減をする必要はなく単に差の絶対値を評価するだけです。
全ての候補値に対して最もmに近い可能性のある値をチェックし、最上位の桁から1の桁まで繰り返して候補を絞り込みます。

なぜこのような面倒なことをしているかというと、こうすることで桁ごとに候補を絞り込めるので計算量を減らすことができるからです。ptn=["17","82","72","83"]、m=1234の場合、7878、7873、7828、7823、7278、7273、7228、7223という値は7000の時点で1000よりもmに近い値を作れる可能性はありません。同様に1800も1200よりもmに近い値を作れる可能性はないので以降の計算をする必要がありません。このように桁ごとに絞り込むことで計算量が相当減ります。

雑感

最初の方に書いた通り、テストケースにはありませんでしたが時間切れになるパターンはあるような気がします。じゃあ、どうするかというとtoNum()の先頭かtoNum()を処理する前に、その時点で最もmに近い候補値より近い値になる可能性のない値で始まるパターンは処理しない、程度の枝刈りでも計算量を27×7!くらいにできるのでこのくらいのカード枚数ならいけるんじゃないかと思っています。
ただ、カードの並び順は最上位の桁がmに近いものを含む順にソートするなどの工夫が必要でしょうが。