キャパカリオンでもわかるプログラミング講座（ヨ）
キャパカリオン講座もいよいよ（ヨ）まで来てしまいました。
となると残すところは（心）しかありませんので、そろそろ締めにかからないとですね。
没案として(心)をさらに(必), (-), (ノ)に分解することも考えましたが流石にくどいのでやめました（笑）
それではさっそく、キャパカリオン講座の本題に着手していきましょう。
本題ってなんだっけ？
と思っている方が多いと思います。そもそもこのキャパカリオンシリーズ（旧シンカリオンシリーズ）は、パスワードの総当たりをどうやって実装するかを解説するために始めたものでした。
問題を再掲しますね。
さて、上記のコード内の「みせられないぜ」と「みせられないよ」にはそれぞれ小文字・大文字・数字がランダムに並んだ30桁の文字列を入れてあります。
(中略)
試しに[a-z][A-Z][0-9]の全62種類のなかから4個選んで(重複可)並べることを考えましょう。
(中略)
プログラマーを自称している男性諸君，こういう総当たりの処理はforループで実装しますよね？
3桁ぐらいであればforループを3重にネストして書けばいいですが， これが今回みたいに大きな桁数になる場合，または桁数を容易に変更できるよう汎用性をもたせたい場合， あなたならどうやってかきますか？（知っていれば簡単ですが。解答をコメントにどうぞ！）
さてこの問題、驚いたことに２月１０日の記事でした。
そして翌週１７日にはこんな記事が。
じゃあ今日はなに書くねんということですが、前回出したプログラミングの問題をinovativeさんが解答してくれましたので、その答え合わせをしようと思います。
答え合わせをするといってから実に1ヵ月半。ラブコメにおける難聴男子ばりの引き延ばしですね。
とはいえ、ここまでのシリーズを読んできたあなたなら、以前よりも問題のイメージが湧くのではないでしょうか？
問題を整理
ここまでの知識を使って、今回の問題を整理してみましょう。
ただ、いきなり[a-z][A-Z][0-9]の62種を対象とするのは大変（というより時間の無駄）ですので、まずはabcの３種類だけを考えましょう。
まずは文字列とfor文の復習
復習大事。
文字列は、＋で連結したり、実際は１文字ずつのリストとして作用するんでしたね。
一方for文はリストから１要素ずつ取り出して繰り返し処理をするのでした。
一桁パスワード
まずは簡単に一文字パスワードを考えてみましょう。これでパスワードがaかbかcのどれかというざるセキュリティならクラックできます（もはや手入力しろレベル）
文字列のリストとしての性質とfor文を組み合わせれば簡単ですね。
二桁パスワード
では、これが二桁になったらどうでしょうか。1桁目にa~cの候補があり、そしてそのそれぞれに2桁目のa~cの候補があります。
ということはfor文の中でfor文を呼び出せばいけそうですね。
三桁、四桁、、、あれ？
さてこの調子で考えていけばよさそうですね。簡単簡単。
三桁なら
for c1 in characters: for c2 in characters: for c3 in characters: print(c1+c2+c3)
四桁なら
for c1 in characters: for c2 in characters: for c3 in characters: for c4 in characters: print(c1+c2+c3+c4)
ん。まだいける、、、けど、あれ？雲行きが怪しいぞ？
十桁なら
for c1 in characters: for c2 in characters: for c3 in characters: for c4 in characters: for c5 in characters: for c6 in characters: for c7 in characters: for c8 in characters: for c9 in characters: for c10 in characters: print(c1+c2+c3+c4+c5+c6+c7+c8+c9+c10)
３０桁なら・・・ってもう書く気がしませんね。
やってることはすごく簡単なんですが、この書き方だと桁数を変えるたびにプログラム自体を書き換えなければなりません。
今回の問題は、コードの中身を書き換えることなく桁数を変えるにはどうしたらいいかという話です。
つまり、桁数を変数Nとして
N = 30 #桁数の指定 (なんかの処理)
みたいに書きたいということです。
inovativeくんのこたえ
この難問（？）に果敢に挑戦したのが優良な読者の一人であるinovativeくんです。
彼のアイディアはずばり全通りに対するループにしてしまおうというものです。
例えば、桁数が2桁で、文字の種類がa,b,cのとき、パスワードの全通りの数は3*3 = 9通りですね。
今までは、
abc = 'abc'
for i in 0,1,2
for j in 0,1,2
abc[i] + abc[j]
と１桁目と2桁目のそれぞれについて考えていましたが、
for k in 0,1,2,3,4,5,6,7,8
i, j = (kを1桁目と2桁目の数字に分ける処理)
abc[i] + abc[j]
と考えるわけです。
そしてこの1桁目と2桁目に分ける処理は、実は割り算の商と余りで実装できます。
試しに0~8までの数字を候補の種類の数(3)で割ってみましょう。
- 0 ÷ 3 = 0 .. 0
- 1 ÷ 3 = 0 .. 1
- 2 ÷ 3 = 0 .. 2
- 3 ÷ 3 = 1 .. 0
- 4 ÷ 3 = 1 .. 1
- 5 ÷ 3 = 1 .. 2
- 6 ÷ 3 = 2 .. 0
- 7 ÷ 3 = 2 .. 1
- 8 ÷ 3 = 2 .. 2
ね、まんべんなく組み合わせができてるでしょ？
今は2桁×3種類ですが、これをN桁×62種類に拡張してあげればいいわけです。
ここの説明についてはinovativeくんのブログをそのまま引用しましょう。
N桁のパスワードの場合、62N個のパターンが存在します。
そこで、0～(62N-1)までの数字を62進数で表して、それぞれの桁数に文字列を当てはめるようなプログラムを作成しました。
数字と文字列の対応は、
0～9 → 0～9
10～35 → a～z
36～61 → A～Z
としました。例
10 → 10×620 → 10 → a
385 → 6×621 + 13×620 → 6 - 13 → 6d
123456789
→ 8×624 + 22×623 + 0×622 + 46×621 + 33×620
→ 8 - 22 - 0 - 46 - 33
→ 8m0Kx
では早速提供していただいたコードを見てきましょう。
彼がfortranという言語で書いたコード（原文ママ）はこちらです。
program cracking !-------------------------------------------------- implicit none integer n,i,imax,j integer it integer,allocatable,dimension(:) :: a character,allocatable,dimension(:) :: c character cc*10 integer t1, t2, t_rate, t_max, diff, tm, ts, tt !-------------------------------------------------- open(1,file='output.dat') print *, "何桁?" read *, n allocate( a(n) ) allocate( c(n) ) imax=62**n call system_clock(t1) do i = 0, imax-1 it = i do j = n, 1, -1 a(j) = it / (62**(j-1)) it = it - a(j) * 62**(j-1) end do !----- number to character ------------------------ do j = 1, n if(a(j)==0) c(j)='0' if(a(j)==1) c(j)='1' if(a(j)==2) c(j)='2' if(a(j)==3) c(j)='3' if(a(j)==4) c(j)='4' if(a(j)==5) c(j)='5' if(a(j)==6) c(j)='6' if(a(j)==7) c(j)='7' if(a(j)==8) c(j)='8' if(a(j)==9) c(j)='9' if(a(j)==10) c(j)='a' if(a(j)==11) c(j)='b' if(a(j)==12) c(j)='c' if(a(j)==13) c(j)='d' if(a(j)==14) c(j)='e' if(a(j)==15) c(j)='f' if(a(j)==16) c(j)='g' if(a(j)==17) c(j)='h' if(a(j)==18) c(j)='i' if(a(j)==19) c(j)='j' if(a(j)==20) c(j)='k' if(a(j)==21) c(j)='l' if(a(j)==22) c(j)='m' if(a(j)==23) c(j)='n' if(a(j)==24) c(j)='o' if(a(j)==25) c(j)='p' if(a(j)==26) c(j)='q' if(a(j)==27) c(j)='r' if(a(j)==28) c(j)='s' if(a(j)==29) c(j)='t' if(a(j)==30) c(j)='u' if(a(j)==31) c(j)='v' if(a(j)==32) c(j)='w' if(a(j)==33) c(j)='x' if(a(j)==34) c(j)='y' if(a(j)==35) c(j)='z' if(a(j)==36) c(j)='A' if(a(j)==37) c(j)='B' if(a(j)==38) c(j)='C' if(a(j)==39) c(j)='D' if(a(j)==40) c(j)='E' if(a(j)==41) c(j)='F' if(a(j)==42) c(j)='G' if(a(j)==43) c(j)='H' if(a(j)==44) c(j)='I' if(a(j)==45) c(j)='J' if(a(j)==46) c(j)='K' if(a(j)==47) c(j)='L' if(a(j)==48) c(j)='M' if(a(j)==49) c(j)='N' if(a(j)==50) c(j)='O' if(a(j)==51) c(j)='P' if(a(j)==52) c(j)='Q' if(a(j)==53) c(j)='R' if(a(j)==54) c(j)='S' if(a(j)==55) c(j)='T' if(a(j)==56) c(j)='U' if(a(j)==57) c(j)='V' if(a(j)==58) c(j)='W' if(a(j)==59) c(j)='X' if(a(j)==60) c(j)='Y' if(a(j)==61) c(j)='Z' end do !-------------------------------------------------- cc=c(1) do j = 2, n cc=c(j)//cc end do print *, cc write(1,*) cc end do call system_clock(t2, t_rate, t_max) if ( t2 < t1 ) then diff = (t_max - t1) + t2 + 1 else diff = t2 - t1 endif tt = diff/t_rate tm = tt/60 ts = tt - tm*60 print * if(tm > 0) then print *, 'Time ', tm, 'm', ts, 's' else print "(A,f5.1,A)", 'Time ', diff/dble(t_rate), 's' end if close(1) deallocate(a) deallocate(c) end program cracking
fortranなんてちんぷんかんぷんだという方、pythonでエッセンスを再現するとこうなります。
（文字の種類はわかりやすいようにabcの３つにしてます）
いや～素晴らしい！
何も頼んでいないのに完璧なクオリティです！
もちろん教材としてね！
・
・
・
・
・
さあ、ダメ出しと総復習の時間です！
パラメータ名は適切に
まあ元はinovative本人しか目を通す予定がないのものだったので強くは言いませんが、変数名がわかりにくいですね。
これだとあまりに解説しにくいので、意味がわかりやすい変数名に書き換えましょう。
ついでに、唐突に出てくる3（原文だと62）という数字は文字の種類で変更されるかもしれないわけですから、直打ちせず変数にすべきですね。
これは以前、消費税も1.08と直打ちせずにTAX=1.08のように変数にしましょうとお伝えしたのと同じです。
#桁数 digit_count = 4 #文字の種類 a,b,c candidate_count = 3 #パスワードの組み合わせの総数 total_count = candidate_count ** digit_count # **は階乗 #各桁での対応する数字 numbers = [0] * digit_count #各桁での対応する文字 characters = ['a'] * digit_count for i in range(total_count): #各桁に分割する処理 mod = i for j in range(digit_count)[::-1]: #カウントダウンするときの書き方 numbers[j] = mod // (candidate_count ** j) #//は整数の割り算でしたね mod = mod - numbers[j] * candidate_count ** j #各桁で数字と文字の対応付け for j in range(digit_count): if numbers[j] == 0: characters[j] = 'a' if numbers[j] == 1: characters[j] = 'b' if numbers[j] == 2: characters[j] = 'c' #文字を連結してパスワードに password = characters[0] for j in range(1,digit_count): password = characters[j] + password print(password)
発見！古風なOL
変数の見通しが良くなったところで、次に目につくのはここの部分でしょう。
for j in range(digit_count): if numbers[j] == 0: characters[j] = 'a' if numbers[j] == 1: characters[j] = 'b' if numbers[j] == 2: characters[j] = 'c'
これ、どこかでみましたよね。そうです。「いくつだと思いますか～」と聞いてくるじゃかしいOLです。
原文は62個もif文があるのですごい労力です。
前回は日付を整数化するために整形が必要でしたが、今回numbersの中は整数そのものですので、簡単ですね。
#桁数 digit_count = 4 #文字の候補 candidates = 'abc' #候補の数 candidate_count = 3 #パスワードの組み合わせの総数 total_count = candidate_count ** digit_count #各桁での対応する数字 numbers = [0] * digit_count #各桁での対応する文字 characters = ['a'] * digit_count for i in range(total_count): #各桁に分割する処理 mod = i for j in range(digit_count)[::-1]: numbers[j] = mod // (candidate_count ** j) mod = mod - numbers[j] * candidate_count ** j #各桁で数字と文字の対応付け for j in range(digit_count): characters[j] = candidates[numbers[j]] #文字を連結してパスワードに password = characters[0] for j in range(1,digit_count): password = characters[j] + password print(password)
大分すっきりしてきました。
あれ、こんなにfor文いらないんじゃ？
今for文の中に、3つfor文が入っていますね。
でもよくよく見ると。。。こんなにfor文いらなさそうですね。
それに伴ってリストも減らせそうです。
#桁数 digit_count = 4 #文字の候補と数 candidates = 'abc' candidate_count = len(candidates) #パスワードの組み合わせの総数 total_count = candidate_count ** digit_count for i in range(total_count): mod = i password = '' for j in range(digit_count)[::-1]: #各桁に分割する処理 number = mod // (candidate_count ** j) mod = mod - number * candidate_count ** j #各桁で数字と文字の対応付け character = candidates[number] #文字を連結してパスワードに password += character print(password)
更なる高みを目指して
もうほとんどいいですが、さらに改善できるところが2点あります。
一つ目は、余りの計算です。
inovativeくんはご丁寧に
mod = mod - number * candidate_count ** j
こう計算していますが、
mod = mod % candidate_count ** j
こう書けるんでしたね。
今回のように、商と余りを両方使う場合は、divmod関数をつかうと一発で計算できて効率的です。
number, mod = divmod(mod,candidate_count**j)
もう一つはcandidate_count**jの部分です。
階乗の計算はとても負荷が大きので、毎回計算するのは得策ではありません。
少なくとも
base = total_count # = candidate_count ** digit_count for j in range(digit_count)[::-1]: base = base // candidate_count #ループが回るごとにcandidate_countで割っていく number, mod = divmod(mod, base)
のようにするか、次のように先に計算しておいてリストに格納しておくのが良いでしょう。
さて、paiza.ioでも8桁までは計算できる（表示できる）ようなので、修正前後で8桁の計算にかかる時間を比較してみてください。
2倍以上速くなっていますね。
こっからが本当のだめだし
さんざん修正してきましたがこっからが本当のだめだしです（笑）
実は、inovativeくんのコードだと5桁までしか対応できないのです。
第一回目の時に変数には型というものがあるとお話しました。
なぜ型を気にしなくていいpythonで、わざわざ型の説明をしたかというと、inovativeくんのこの問題を説明するためだったのです。
さて、昨今では携帯会社が通信量についてギガギガ言ってますが、ギガは接頭語で単位として意味があるのはバイトのほうだということは皆さんクラスであればご存知でしょう。
そしてバイトは情報量の単位です。
コンピュータの情報はすべて0か1でできているっていうのはなんとなく聞いたことがあると思います。
この0か1の情報を1ビットと呼びます。1ビットで0か1の2通りの状態を区別できるわけですね。
では、バイトはどういうものかというと、8ビットを1バイトと呼んでいるだけです。
２通りの情報を区別できるビットが8個あるわけですから1バイトで区別できる状態は28 = 256通りです。
話をもどしますが、当然変数の値もこのビットを使って記憶しています。
そしてint型の変数には多くの場合4バイトの記憶領域が割りてられます。
では、4バイトで区別できる状態は何通りあるでしょうか。
1バイトが256通りなわけですから4バイトは2564 = 4,294,967,296通りですね。
・・・さあ、お気づきになりましたか。
どうあがいても4バイトでは4,294,967,296通りしか区別できないのですから、int型が記憶できる数字の範囲にも当然限界があります。
int型で表現できるのは、マイナス側を含めた -2,147,483,648 ～ 2,147,483,647の範囲です。
一方でlog62(2,147,483,647) = 5.2ですから、inovativeくんのプログラムは計算時間がどうこう以前に6桁以上になるとimax（もしくはtotal_count）が計算できず、エラーで止まります。
多くのプログラムでは8バイト整数型も存在しますが、それを使っても10桁が限度です。
これ以上の数を取り扱うためには多倍長整数とその演算を自分で定義する必要があります。
もしかしたらここまでフォローしているかも・・・と思ってコードを提供してもらいましたが、ま、案の定でしたね。（せめてunsignedな8バイト整数にしていてほしかったな～）
python半端ないって
ちなみにpythonの整数型は驚くことにデフォルトで多倍長整数です。メモリが許す限り何桁でも取り扱えます。
もしinovativeくんがpythonで実装していた場合、（無駄なところは多いものの）合格でした。
惜しかったですね。
おわりに
inovativeくんのおかげでいい復習ができましたね。
次回はシリーズ最終回で、『もっとエレガントな解法』をご紹介したいと思います。
余談
inovativeくんから頂いたコードをこちらで実行してみると、2桁で0.4秒、3桁で24秒、4桁で1548秒（25分48秒）かかりました。
次回紹介する書き方では4桁112秒で計算できますので、無茶苦茶遅いですが、１桁増えるごとにちゃんと計算時間がおおよそ62倍になっていますね。
一方でinovativeくんがブログに載せている情報によると2桁で1秒、3桁で7.8秒、4桁で6分40秒だったとのこと。
あれれ～おかしいぞ～。
実行結果をよーく目を凝らしてみると順列ではなく組み合わせになっているような・・・？
ともあれ、私に提出するタイミングで修正したみたいですね（笑）
余談２
ハッピーバースデー、キャパカリオン！
