Puzzles for Hackers

副題：スクリプトキディから大人のハッカーへ
イワン・スクリャロフ(著)
鷹跣 搗汯(翻訳)
翔泳社 (2006/8/29)

裏表紙には「下記の問題をいとも簡単に解ける人は本書は必要ありません」とあって、問題が一つ紹介されている。「HACKER + HACKER + HACKER + ENERGY」という覆面算なんだけど、これが簡単に解けるぐらいの人には、この本はちょっと難しいかもしれない。もっとレベルの高い問題もたくさんある。

問題が全体の1/3で残りが解答編だということからもわかるように、各問題にはけっこう丁寧な解答がついている。このこと自体はとてもいいことなのだけれど、ちょっとひどい解答もあるねえ。さっきの覆面算なんて、C言語の単純な入れ子のループで解いてるよ（C言語を選んだ時点でちょっと減点したい）。

もう少し汎用的な形を提供した方が教育的なんじゃないかな。単純探索のためのテンプレートを使うのが簡単。再帰的に解を作って、割り当てが全部決まったらチェックする。（遅いから、解が一つ見つかったら終了）

search[x_] := Or[ goal@x, deepen@x]

goal[x_] := And[
  Length@x == 9,
  Module[{h, a, c, k, e, r, n, g, y},
   {h, a, c, k, e, r, n, g, y} = x;
   And[h != 0, e != 0,
    3 FromDigits@{h, a, c, k, e, r} == FromDigits@{e, n, e, r, g, y},
    Print@{{h, a, c, k, e, r}, {e, n, e, r, g, y}}; True]]]

deepen[x_] := scanOr[search, Append[x, #] & /@ Complement[Range[0, 9], x]]

scanOr[f_, x_] := Catch[Scan[If[f@#, Throw@True] &, x]; False]

search@{}

{{1,2,4,5,3,6},{3,7,3,6,0,8}}

これじゃさすがに遅いから、バックグラウンドで実行させながら、割り当てる順番を桁にあわせて、桁毎のテストをするようにする。（速いから、解をすべて見つけられる。）

goal[x_] := And[
  Length@x == 9,
  Module[{h, a, c, k, e, r, n, g, y},
   {r, y, g, e, k, c, a, n, h} = x;
   And[h != 0, e != 0,
    3 FromDigits@{h, a, c, k, e, r} == FromDigits@{e, n, e, r, g, y},
    Print@{{h, a, c, k, e, r}, {e, n, e, r, g, y}}; True]]]

test[x_] := Module[{h, a, c, k, e, r, n, g, y, len = Length@x},
  Or[
   len == 0,
   len == 1,
   len == 3,
   len == 7,
   len == 9,
   And[len == 2, {r, y} = x; myMod@{r} == y],
   And[len == 4, {r, y, g, e} = x; myMod@{e, r} == FromDigits@{g, y}],
   And[len == 5, {r, y, g, e, k} = x; 
    myMod@{k, e, r} == FromDigits@{r, g, y}],
   And[len == 6, {r, y, g, e, k, c} = x; 
    myMod@{c, k, e, r} == FromDigits@{e, r, g, y}],
   And[len == 8, {r, y, g, e, k, c, a, n} = x; 
    myMod@{a, c, k, e, r} == FromDigits@{n, e, r, g, y}]]]

myMod[x_] := Mod[3 FromDigits@x, 10^Length@x]

deepen[x_] := mapOr[search, Select[Append[x, #] & /@ Complement[Range[0, 9], x], test]]

mapOr[f_, x_] := Or @@ Map[f, x]

search@{}

{{2,0,5,4,6,3},{6,1,6,3,8,9}}
{{1,2,4,5,3,6},{3,7,3,6,0,8}}

True

16進数なら、26d071 + 26d071 + 26d071 = 747153とかたくさんあるよ。基数が大きくなると、解の数もだいたい多くなる。

という感じで、この本はちょっとゆっくり読みたい。

帯にはこうある。

本物のプログラマになるための定本「ハッカーのたのしみ」の入門書としてこの問題集は欠かせない。

たしかにそうかもしれない。学部ではこPuzzles for Hackersで遊んで、大学院で『ハッカーのたのしみ』で遊ぶ感じかな。教養では『ミンスクのにわとり』や『ビル・ゲイツの面接試験』がおすすめ。