コンピューターの「探索アルゴリズム」を知るパズルゲームです。フクロウの司書の書庫では、本は番号順にならんでいますが、背はカバーでかくれていて、1 冊めくって番号を見るごとに 1 手かかります。はしから 1 冊ずつ見るのが線形探索で、31 冊なら最悪 31 回。まん中をめくって、さがす番号より大きければ前半、小さければ後半。1 回ごとに半分を消せるので、31 冊でも最大 5 回ですみます。これが二分探索です。
この書庫は「いたずら好き」。かくれた答えはめくったときに決まり、いつも大きいほうの半分にかくれるので、手数はほんとうの最悪の場合になります。毎回のこりを同じ大きさの 2 つに分けたときだけ星 3 つ。消えた本は自動で灰色になり、上の欄にはめくるたびにのこった可能性の数(31、15、7、3、1)が記録されます。結果カードでは、半分ずつへっていくようすを棒グラフで表し、1 冊ずつ見た場合の最悪の回数とくらべます。
全 5 章 30 ステージで、章ごとに代表的な探索を 1 つずつ:ならんだ本だな(二分探索)、新しい本はどこ?(入れる場所)、どこから印刷ミス?(プログラマーが使う git bisect と同じ考え方)、いちばん高い本(山の形の列で頂上さがし。となりの本と高さをくらべます)、カード目録の引き出し(横にもたてにも順にならんだ表を、右上から階段のようにさがす)。さらに無限のランダム問題があります。問題は毎回プログラムで作られ、星 3 つの基準はアルゴリズムの最悪の手数です。
あそびかた
- 「さがしはじめる」でまだクリアしていないステージから、または「ステージ」から章を選びます。新しい章にはじめて入ると「司書のメモ」が小さな図でその章のさがし方を説明します。タイトル画面の「司書のメモ」でいつでも読み返せます。
- 上の欄には、さがすもの(たとえば「653 番の本をさがそう」)とそのステージのルールが書いてあります。本をタップしてめくると、フクロウがその本からわかったことと、のこりの可能性の数を教えてくれます。答えになりえない本は灰色のしまもようになり、タップしても手数はふえません。本の下の小さい数字は位置(何冊目か)、めくったあとのまん中の大きい数字が番号です。
- 章ごとの目標:第 1 章はさがす本をめくる。第 2 章は左が小さく右が大きいすき間を見つける(同じ本は見つけなくてよい)。第 3 章は最初の印刷ミスの本(その前の本はだいじょうぶ)を見つける。第 4 章は両どなりより高い本を、となり合う 2 冊をめくってくらべながら見つける。第 5 章は横にもたてにも小さい順にならんだ目録から、その数を見つける。
- めくった回数が星 3 の基準以内なら星 3 つ、1~2 回多いと 2 つ、それより多いと 1 つ。電球を押すといちばんよい本が光りますが、そのステージは最大で星 2 つです。失敗はなく、制限時間もありません。左下のボタンで新しい問題にやり直せます。1 つの章で 3 ステージクリアすると次の章が開きます。
そうさ方法
- スマホ・タブレット:本(またはカード目録の引き出し)をタップしてめくります。1 回めくるごとに 1 手です。もう消えた本は灰色になり、タップしても手数はふえず、なぜ消えたかを教えてくれます。右上の電球でヒント、左下のボタンで新しい問題にやり直せます。
- マウス:タッチと同じく、本をクリックしてめくります。
- キーボード:矢印でカーソル移動(↑ ↓ で上下の段へ)、Enter かスペースでめくる。H ヒント、R やり直し、M 消音、Esc もどる。
保護者の方へ
- 主に 13 歳以上向け、9~12 歳も前半の 2 章から楽しめます。情報の授業の「探索とアルゴリズムの効率」(線形探索と二分探索、データを先にならべる理由、log₂ の感覚=データが 2 倍でも 1 手ふえるだけ、最悪の場合の分析、入れる場所さがし、二分法でのバグさがし=git bisect、頂上さがし、たてにも横にもならんだ表の階段探索)をあつかいます。「いたずら書庫」が答えをいつも大きいほうの半分にかくすので、なぜ「半分に分ける」がいちばん確実かを自分で発見できます。
- 辞書を引くとき、電話帳で名前をさがすとき、データベースがデータを見つけるとき、数当てゲームでも、知らないうちに二分探索を使っています。プログラマーがどの版からプログラムがこわれたかをさがすのも、半分ずつしぼりこむ方法です、という話をしてみてください。失敗や制限時間はなく、手数が多いと星が少しへって「次はまん中を」とすすめるだけ。消えた本をタップしても理由を説明するだけで、手数はふえません。情報はすべて数字で表示し、だいじょうぶ/印刷ミスはチェックの丸とぎざぎざのインクのしみという別の形でも表すので、色にたよりません。本の背の色はかざりです。
- チャット・課金・広告・外部リンク・オンラインランキングはなく、個人情報の入力も一切ありません。星の数・読んだメモ・ランダム問題のクリア数・消音の設定はこの端末のブラウザにだけ保存され、オフラインでも遊べます。