Puzzles for Hackers


Puzzles for Hackers:スクリプトキディから大人のハッカーへ (IT Architects' Archive 知の連環) (単行本(ソフトカバー))副題:スクリプトキディから大人のハッカーへ
イワン・スクリャロフ(著)
鷹跣 搗汯(翻訳)
翔泳社 (2006/8/29)

裏表紙には「下記の問題をいとも簡単に解ける人は本書は必要ありません」とあって、問題が一つ紹介されている。「HACKER + HACKER + HACKER = ENERGY」という覆面算。でも、もっとレベルの高い問題もたくさん載っているから、この問題が簡単に解ける人でも楽しめる可能性大。

問題が全体の1/3で残りが解答編だということからもわかるように、各問題にはけっこう丁寧な解答がついている。このこと自体はとてもいいことなのだけれど、ちょっと変な解答もある。

上記の覆面算は、単純な多重ループで解くよりも、もう少し汎用的な形にしておいた方が他の問題に応用しやすいはず。たとえば、再帰的に解を作って、割り当てが全部決まったらチェックすればいい。(遅いから、解が一つ見つかったら終了することにする。UMMでも動く。)

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},
    Sow@{{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]

Reap@search@{}

{True, {{{{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},
    Sow@{{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]

Reap@search@{}

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

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

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

帯にはこうある。

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

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です