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

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

締め切りが 2017/10/03 10:00 AM なので，その 1 分後に投稿されるように予約

設問

入力ミスなどを防ぐため、チェックディジットがよく使われます。
代表的な例として、書籍を管理するときに使われる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

======================================================================

1. ABCD-EFGHがすべて異なる数字
2. ISBN-10では先頭が「4」、ISBN-13では先頭が「978-4」を固定

という条件つきなので，数え上げが可能。

R だと，順列生成とベクトル演算で短く書くことができる。
permutations はライブラリにあるので，隠蔽することができ，実質の関数 f はわずか 2 行ということになる。
が，しかし。これでは 0.8 秒ほど掛かる。

permutations = function(n) {
    z = matrix(1)
    for (i in 2:n) {
        x = cbind(z, i)
        a = c(1:i, 1:(i - 1))
        z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
        z[1:nrow(x), ] = x
        for (j in 2:i - 1) {
            z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
        }
    }
    z[, 1:(n-2)]-1
}

f = function(cd) {
    a = permutations(10) # 0 ~ 9 のうちの 8 個を使った順列を生成（同じものが 2 つずつある）
    cat(sum(11-(40+a %*% 9:2) %% 11 == cd & 10-(50+a %*% c(1,3,1,3,1,3,1,3)) %% 10 == cd)/2) # ISBN10 と ISBN13
}

permutations を java に移植してもよいのだが，単純に 8 重の for ループのプログラムを書く。
以下の R プログラムだと 3 秒ほどかかるので，Java に書き直して O.K.

R プログラム

f = function(cd) {
    count = 0
    for (i5 in 0:9) {
        x5 = 50 + i5
        y5 = 40 + 9 * i5
        for (i6 in 0:9) {
            if (i6 == i5) next
            x6 = x5 + 3 * i6
            y6 = y5 + 8 * i6
            for (i7 in 0:9) {
                if (i7 == i5 || i7 == i6) next
                x7 = x6 + i7
                y7 = y6 + 7 * i7
                for (i8 in 0:9) {
                    if (i8 == i5 || i8 == i6 || i8 == i7) next
                    x8 = x7 + 3 * i8
                    y8 = y7 + 6 * i8
                    for (i9 in 0:9) {
                        if (i9 == i5 || i9 == i6 || i9 == i7 || i9 == i8) next
                        x9 = x8 + i9
                        y9 = y8 + 5 * i9
                        for (i10 in 0:9) {
                            if (i10 == i5 || i10 == i6 || i10 == i7 || i10 == i8 || i10 == i9) next
                            x10 = x9 + 3 * i10
                            y10 = y9 + 4 * i10
                            for (i11 in 0:9) {
                                if (i11 == i5 || i11 == i6 || i11 == i7 || i11 == i8 || i11 == i9 || i11 == i10) next
                                x11 = x10 + i11
                                y11 = y10 + 3 * i11
                                for (i12 in 0:9) {
                                    if (i12 == i5 || i12 == i6 || i12 == i7 || i12 == i8 || i12 == i9 || i12 == i10 || i12 == i11) next
                                    isbn13 = 10 - (x11 + 3 * i12)%%10
                                    isbn10 = 11 - (y11 + 2 * i12)%%11
                                    if (isbn13 == cd && isbn10 == cd) {
                                        count = count + 1
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cat(count)
}

system.time(f(1)) # 14751, 3.7sec.
system.time(f(2)) # 18271, 3.7sec.
system.time(f(5)) # 14549, 3.7sec.
system.time(f(7)) # 14578, 3.7sec.
system.time(f(8)) # 18358, 3.7sec.

Java プログラム

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        if (true) {
            System.out.println(f(1)); // 14751
            System.out.println(f(2)); // 18271
            System.out.println(f(5)); // 14549
            System.out.println(f(7)); // 14578
            System.out.println(f(8)); // 18358
        } else {
            Scanner cin = new Scanner(System.in);
            String line;
            line = cin.nextLine();
            int cd = Integer.parseInt(line);
            System.out.println(f(cd));
        }
    }

    static int f(int cd) {
        int i5, i6, i7, i8, i9, i10, i11, i12;
        int x5, x6, x7, x8, x9, x10, x11;
        int y5, y6, y7, y8, y9, y10, y11;
        int isbn10, isbn13;
        int count = 0;
        for (i5 = 0; i5 < 10; i5++) {
            x5 = 50 + i5;
            y5 = 40 + 9 * i5;
            for (i6 = 0; i6 < 10; i6++) {
                if (i6 == i5) continue;
                x6 = x5 + 3 * i6;
                y6 = y5 + 8 * i6;
                for (i7 = 0; i7 < 10; i7++) {
                    if (i7 == i5 || i7 == i6) continue;
                    x7 = x6 + i7;
                    y7 = y6 + 7 * i7;
                    for (i8 = 0; i8 < 10; i8++) {
                        if (i8 == i5 || i8 == i6 || i8 == i7) continue;
                        x8 = x7 + 3 * i8;
                        y8 = y7 + 6 * i8;
                        for (i9 = 0; i9 < 10; i9++) {
                            if (i9 == i5 || i9 == i6 || i9 == i7 || i9 == i8) continue;
                            x9 = x8 + i9;
                            y9 = y8 + 5 * i9;
                            for (i10 = 0; i10 < 10; i10++) {
                                if (i10 == i5 || i10 == i6 || i10 == i7 || i10 == i8 || i10 == i9) continue;
                                x10 = x9 + 3 * i10;
                                y10 = y9 + 4 * i10;
                                for (i11 = 0; i11 < 10; i11++) {
                                    if (i11 == i5 || i11 == i6 || i11 == i7 || i11 == i8 || i11 == i9 || i11 == i10) continue;
                                    x11 = x10 + i11;
                                    y11 = y10 + 3 * i11;
                                    for (i12 = 0; i12 < 10; i12++) {
                                        if (i12 == i5 || i12 == i6 || i12 == i7 || i12 == i8 || i12 == i9 || i12 == i10 || i12 == i11) continue;
                                        isbn13 = 10 - (x11 + 3 * i12) % 10;
                                        isbn10 = 11 - (y11 + 2 * i12) % 11;
                                        if (isbn13 == cd && isbn10 == cd) {
                                            count++;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return count;
    }

}