パズル

H.Mの出したパズルが解けない。

昨日から暇を見つけては考えているが、どうしても不可能のように思える。

周りの人たちは答えがわかったようだから、正解はあるようだ。しかし、それが自分も納得のいくものかはわからない。

もしかしたら、ちょっとずるいことをするのではないかなどと考えてしまう。答えを聞いてがっかり、ということは何としても避けたい。

一番手っ取り早いのは実際にやってみることである。

ずるいことはできないよう、プログラムを組んだ。

この設定された状況下でも問題にあるようなことが可能なら僕もあきらめよう。

実演で示されたなら示したほうも示されたほうもすがすがしい気分になるだろう。

もちろんプログラムは公開するし、不正はない。

（以下ネタばれの可能性あり。問題に心当たりがあり知りたくない人は読まないでください。もちろん正解は書いてありません。）

プログラムを説明する。本当にその通りかは、添付してあるコードを読んで判断してほしい。

まず、このプログラムはc言語で書かれている。

箱にデータを入れる、錠をかける、錠をはずす、箱からデータを取り出す、かかっている錠の数を調べる、などといった動作を実装してある。

箱と南京錠の機能は、リスト構造のNankinjo構造体で実現している。

リスト構造の先頭のNankinjo構造体（topとしよう）は箱を表わしていて、topのメンバー変数のlock（つまりtop.lock）が箱の中に入れられるデータを表わす。

topのメンバー変数nextがさすポインタがNULLならばその箱に錠がかかっていないことを表わす。

NULLでないならば、その箱には錠がかかっている。

top.nextのさす構造体をjoとしよう。jo.lockにはその錠の名前が、jo.keyにはその錠を開けるための鍵（つまりパスワード）が格納されている。Nankinjo構造体を連結させることでいくつも錠がかかった箱を実現する。

archという配列の要素は一つの箱に対応する。箱を複数つくっておくのは、途中で箱が盗まれた場合のことを再現するためである。

AからBに秘密文書を送るのだが、その経路の安全性は保証されていない。

そのことは仮想的な人物Xを考えると簡単である。途中で盗まれた箱はすべてXが持っている。これが配列archである。

だから、はじめにAが秘密文書を箱に入れ錠をしてBに送り、その後で鍵を送るという方法は成立しない。

秘密文書が入った箱はXの手に渡る可能性があり、鍵もXの手に渡れば文書は見られてしまう。

A、B、Xができる動作はコマンドの形で実装している。

・データの入力

これはコマンドではないが、A、Bに許されている。

プロンプトに続いて文字列を入力すると、その文字列が当該箱のデータになる。

以後データは変更することができない。

データを入力できるのは、プログラムを実行した直後またはnew（後述）した直後のみである。

データを所得できるのは錠がかかっていないときにgetdataコマンドを実行した場合のみである。

・lock

lockと入力した後に、locknameを入力し、次いでkeynameを入力すれば、

現在着目している箱にlocknameという名前で、keynameを入力すれば開く錠をかけたことになる。

データをみると、新しいNankinjo構造体(newjoとする)がつくられ、

newjo.lockにlocknameが、newjo.keyにkeynameが格納され、Nankinjo構造体のリストに連なる。

insertは連なる時の関数である。

またlockが同じなのにkeyが異なるような構造体がないように、存在する構造体すべてを調べるfindという関数が実装されている。

・unlock

unlockと入力した後に、keynameを入力すると、かかっている錠のうち、keynameで開くものが一つ開く。

つまりメンバー変数keyがkeynameと等しいようなNankinjo構造体がリストから外れる。

プログラムではunlock関数内で実装されている。

・getdata

getdataと入力すると、錠が一つもかかっていない場合は当該箱に入っているデータを表示する。錠が一つでもかかっている場合は表示されない。

プログラムでは、先頭のNankinjo構造体のnextがNULLかどうかで判断する。

・new

newと入力すると、現在の当該箱は盗まれたことになり、新しい箱(arch配列の次の要素)が当該箱になる。

A、Bは当該箱に対する操作しか許されていない。これは当該箱以外は、Xの手元にあるということをプログラムで再現したものである。

Xは当該箱以外の箱の操作も許される。

プログラムでは当該箱をkという整数であらわす。これはarch[k]が当該箱であるという意味である。

今までにいくつ箱をつくったかをarchcという整数で保持する。newするとarchcが1増える。

・locknum

locknumと入力すると、当該箱にかかっている鍵の数を表示する。

次の二つは、Xにのみ許されるコマンドである。

・arch

archと入力したあとに、整数dを入力すると、当該箱がarch[d]に変わる。

何度も書くが、当該箱以外の箱はXの手元にあり、下手に鍵を送ったりすると開けられる。

・exit

これはプログラムを終了することを意味する。

Xの手元にある箱がすべて失われるので、Xにしか許されていない。

Xにしか許されていないものは、パスワードが要求される。プログラムではパスワードはコマンドライン引数により指定する。

それから一応デバッグ用にprintなる関数をつくってあるが、

もちろん実演に使う実行ファイルはこの部分をコメントアウトしたコードをコンパイルする。

以上で必要な動作は実装されていることがわかっただろうか。詳細は自分で読んでほしい。

南京錠および箱そのものを箱に入れたいときはどうするんだといわれるかもしれない。

これらは入れる必要のないと思われる。

南京錠は単独では送れないことになっているし、これらのことをしてもほとんどメリットはない。

しかし、こういうところにこそ落とし穴があるものだ。

本当はきちんと証明しなければならないが省かせてもらう。今井先生ごめんなさい。

もし、正解の手順にこれらの操作が入っていれば、来年も離散数学を受ける。

キーボードで打ち込んだ文字列が表示されてはまずいから、%stty –echoコマンドで表示されないようにしてから実行する。

動作に対しても必要最低限のコメントしか返さない。

さて、実演の方法である。4人必要だ。A、B、X、経路担当である。

A、B、経路担当は正解を知っている人がすればいい。僕はそんな方法はないという立場でXをやらせてもらう。