CodeIQ：ISBNのチェックディジットを計算して！

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ISBNのチェックディジットを計算して！」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
入力ミスなどを防ぐため、チェックディジットがよく使われます。
代表的な例として、書籍を管理するときに使われるISBN(Wikipedia)があり、チェックディジットが使われています。

ISBNには、かつて使われていた「ISBN-10」と現在主に使われている「ISBN-13」があります。
最近出版されている書籍には両方が記載されていることが一般的で、ISBN-10も使用可能です。
現在、日本国内で出版されたものについては、チェックディジットを除いた部分にISBN-10とISBN-13で同じ値が使われています。
（ISBN-10は「ISBN4-ABCD-EFGH-X」、ISBN-13は「ISBN978-4-ABCD-EFGH-Y」という形で、　ABCD-EFGHの部分は同じ、XとYがそれぞれのチェックディジット）

このABCD-EFGHがすべて異なる数字で構成され、ISBN-10とISBN-13のチェックディジットが同じ(X=Y)ものを調べることにします。
例えば、ABCD-EFGHの部分が「05192743」のものは、ISBN-10では「ISBN4-0519-2743-1」、ISBN-13では「ISBN978-4-0519-2743-1」となり、チェックディジットがともに1となります。

なお、ISBNの計算方法は以下の通りです。(Wikipediaより引用)

ISBN-10
「モジュラス11 ウェイト10-2」という計算法にて算出される。（チェックディジットを除いた左側の桁から10、9、8…2を掛けてそれらの和を取る。和を11で割って出た余りを11から引く）
ここで、例として ISBN4-10-109205-□ のチェックディジット（□部分）を求めてみる。

4×10 + 1×9 + 0×8 + 1×7 + 0×6 + 9×5 + 2×4 + 0×3 + 5×2
= 40 + 9 + 0 + 7 + 0 + 45 + 8 + 0 + 10
= 119
119 ÷ 11 = 10 あまり 9
11 - 9 = 2

よって、このISBNのチェックディジットは2である。なお、計算結果が10になった場合、10の代わりにX（アルファベットの大文字）を用いる。また、11になった場合は、0となる。

ISBN-13
「モジュラス10 ウェイト3・1（モジュラス10 ウェイト3）」という計算法にて算出される。（チェックディジットを除いた一番左側の桁から順に1、3、1、3…を掛けてそれらの和を取る。和を10で割って出た余りを10から引く。ただし、10で割って出た余りの下1桁が0の場合はチェック数字を0とする。）
ここで、例として ISBN 978-4-10-109205-□ のチェックディジット（□部分）を求めてみる。

9×1 + 7×3 + 8×1 + 4×3 + 1×1 + 0×3 + 1×1 + 0×3 + 9×1 + 2×3 + 0×1 + 5×3
= 9 + 21 + 8 + 12 + 1 + 0 + 1 + 0 + 9 + 6 + 0 + 15
= 82
82 ÷ 10 = 8 あまり 2
10 - 2 = 8

よって、このISBNのチェックディジットは8である。

標準入力からチェックディジットが与えられるとき、チェックディジットがその値に一致するISBNの個数を標準出力に出力してください。
※日本国内で出版されるもののみを考えるため、ISBN-10では先頭が「4」、ISBN-13では先頭が「978-4」を固定とします。
　また、実際に書籍が存在するかどうかは問いません。

例えば、チェックディジットが「1」のとき、上記の条件をみたすものは14751通りあります。

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

標準出力
14751

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def chk10(arr)
	isbn10 = (40+9*arr[0]+8*arr[1]+7*arr[2]+6*arr[3]+5*arr[4]+4*arr[5]+3*arr[6]+2*arr[7])%11
	return ((isbn10 == 0) ? 0 : 11-isbn10)
end

def chk13(arr)
	isbn13 = (9+21+8+12+arr[0]+3*arr[1]+arr[2]+3*arr[3]+arr[4]+3*arr[5]+arr[6]+3*arr[7])%10
	return ((isbn13 == 0) ? 0 : 10-isbn13)
end

def solve(n)
	ret = 0
	(0..9).to_a.permutation(8){|arr|
		ret += 1 if (n == chk10(arr)) && (n == chk13(arr))
	}
	return ret
end

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

	p solve(line.to_i)
end

解説

単純な総当たりで間に合ったのでそれで済ませてしまいました。

考え方

チェックディジットの数は0..9から8個を順番を考慮して選んだ場合なので順列を列挙すれば全パターンチェックできます。
あとはISBN10とISBN13で結果が同じになるものを数えます。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(n)

0..9から8個順番付きの数列を列挙します。
それをchk10()とchk13()に渡して結果を比較し、同じならretを1加算します。
全パターンをチェックした結果のretが答えになるのでそれを返却します。

chk10(arr), chk13(arr)

問題文に示されているISBN10とISBN13のチェックディジットの計算式を実装しただけです。

雑感

パターン数は10P8ですが計算が単純なのでどうかな、と思ってやって見たらローカルで1.2秒くらいでした。実行環境がローカルより少し早いから行けるのと違うか？ と思ってやって見たら間に合いました。
剰余の和は全ての数を足してから剰余を取った時と同じです。なのでその性質を使ってメモ化再帰あたりで実装するのが模範解答なんだと思います。