なでしこさんで数当て (嘘対応)
有名な、リストの中に思い浮かべた数があるかの質問を繰り返すことで思い浮かべた数を当てるやつをなでしこで実装してみた。
数を当てる方法
基本
0~15の整数を2進数で表し、それぞれの位ごとに「1」になっている数をリストにする。
1の位が「1」:1、3、5、7、9、11、13、15
2の位が「1」:2、3、6、7、10、11、14、15
4の位が「1」:4、5、6、7、12、13、14、15
8の位が「1」:8、9、10、11、12、13、14、15
思い浮かべた数がこのそれぞれのリストにあるかを聞くことで、思い浮かべた数の各ビットの情報を得ることができる。
とはいえ、このリストをそのまま用いると露骨すぎる。
そのため、1~16の整数を格納した配列をシャッフルし、上のリストの数をこの配列の添字として用いることで、ユーザーに提示する整数を決定する。
1回の嘘を見抜く
4ビットの情報があれば、1~16の整数の中からユーザーが思い浮かべた1個を特定できる。
しかし、これだけでは、ユーザーが質問に1個でも嘘を答えてしまうと、ユーザーが思い浮かべた数の判断を誤ってしまう。
そこで、誤り訂正技術の一つであるハミング符号を応用し、冗長な情報を追加しておくことで、1回なら嘘をつかれても (すなわち、1ビットだけ反転していても) ユーザーが思い浮かべた数を正しく判断できるようにする。
もとの情報が4ビットの場合、3ビットの情報を追加することで、これを実現できる。
まず、円3個からなるベン図を用意する。
そして、その中の円が重なっている部分に、もとの情報の4ビット (0~3) を割り当てる。
さらに、円が1個だけの部分に、追加する情報の3ビット (4~6) を割り当てる。
追加する情報は、それぞれの円の中に割り当てられたビットの中で 「1」であるビットの数が偶数になるように決める。
ユーザーから質問の答えとして7ビットの情報を受け取ったら、それぞれの円の中に割り当てられたビットの中で「1」であるビットの数が偶数かどうかを確認する。
全ての円でこれが偶数であれば、ユーザーは嘘をついていないと判断できる。
偶数になっていない円がある場合、それらの円が、かつそれらの円のみが重なっている場所に割り当てられたビットを反転させることで偶数にできる。
このようなビットは必ず1個だけ存在するので、ユーザーはそのビット (質問) について嘘をついたと判断できる。
ただし、ユーザーが2回以上嘘をついたり答えを間違えたりしてしまった場合は、それを検出できず、ユーザーが思い浮かべた整数や嘘をついたビットの位置について間違った判断をしてしまうことになる。
実装
数当て (嘘対応) (なでしこ3貯蔵庫)
実装のポイント
ロジック
●(AでBの)ビット立とは
OR(A,SHIFT_L(1,B))を戻す。
ここまで。
●(AでBの)ビット折とは
AND(A,NOT(SHIFT_L(1,B)))を戻す。
ここまで。
●(AでBの)ビット反転とは
XOR(A,SHIFT_L(1,B))を戻す。
ここまで。
●(AでBの)ビット確認とは
AND(SHIFT_R(A,B),1)が1と等しいかを戻す。
ここまで。ビットの操作を行う関数を用意する。
定数の確認位置リストは[[0,1,2],[0,2,3],[0,1,3]]。
定数の嘘位置リストは[4,5,2,6,1,3,0]。
定数のエンコードリストは空配列。
数を0から15まで繰り返す
エンコードは数。
確認位置を0から2まで繰り返す
確認位置リスト@確認位置を反復
もし、エンコードで対象のビット確認ならば
エンコードで(確認位置+4)のビット反転して、エンコードに代入。
ここまで。
ここまで。
ここまで。
エンコードリストにエンコードを配列追加。
ここまで。冗長な情報を追加する際にどのビットを参照するかの表「確認位置リスト」と、「1」であるビットの数が偶数でなかった円の情報からにどのビットが反転しているらしいかを求める表「嘘位置リスト」を用意する。
そして、「確認位置リスト」を用いて実際に冗長な情報を追加し、「エンコードリスト」に格納する。
候補リストとは変数。
現在質問とは変数。
回答とは変数。
●状態初期化とは
候補リストは1から16までの配列連番作成。
それを配列シャッフル。
現在質問は0。
回答は0。
ここまで。ユーザーに提示する整数のリスト「候補リスト」と、今どのビットについて質問をしているかを表す「現在質問」、ユーザーから得られた情報を保存する「回答」を用意する。
●(POSの)質問配列取得とは
定数の質問配列は空配列。
位置を0から15まで繰り返す
もし、エンコードリスト@位置でPOSのビット確認ならば
質問配列に候補リスト@位置を配列追加。
ここまで
ここまで。
質問配列を配列数値ソート。
それを戻す。
ここまで。ユーザーに提示する用に、指定された位置のビットが「1」である情報に対応する整数のリストを作成する。
●(POSにANSを)回答記録とは
もし、ANSならば
回答でPOSのビット立て、回答に代入。
違えば
回答でPOSのビット折り、回答に代入。
ここまで。
ここまで。ユーザーからの情報を「回答」に記録する。
●嘘位置取得とは
変数の確認結果は回答。
確認位置を0から2まで繰り返す
確認位置リスト@確認位置を反復
もし、確認結果で対象のビット確認ならば
確認結果で(確認位置+4)のビット反転して、確認結果に代入。
ここまで。
ここまで。
ここまで。
確認結果はSHIFT_R(確認結果,4)。
もし、確認結果が0と等しいならば
NULLを戻す。
違えば
嘘位置リスト@(確認結果-1)を戻す。
ここまで。
ここまで。
●選択候補取得とは
変数の選択結果は回答。
定数の嘘位置は嘘位置取得。
もし、それがNULLと等しく無いならば
選択結果で嘘位置のビット反転して、選択結果に代入。
ここまで。
候補リスト@AND(選択結果,15)を戻す。
ここまで。「嘘位置取得」では、それぞれの円について「1」になっているビットの数が偶数かを調べ、それに基づいて反転しているビットを求める。
さらに、「選択候補取得」では、それを用いて実際にユーザーが思い浮かべた整数を求める。
UI
●(DOMにVALUEを)DOM表示設定とは
もし、VALUEならば
DOMの「ボックス表示」に「ブロック」をDOMスタイル設定。
違えば
DOMの「ボックス表示」に「なし」をDOMスタイル設定。
ここまで。
ここまで。標準で用意されている「DOM可視設定」風のインターフェースで、display スタイルを切り替えて画面を表示したり隠したりする関数を用意する。
「DOM可視設定」では visibility を用いるので、隠してもそれがあるはずの空間が空いてしまい、ページの切り替えには適さない。
display を用いれば、非表示にしたときに空間を詰めることができる。
タイトル画面は「DIV」のDOM部品作成。
それの「行揃え」に「中央」をDOMスタイル設定。
選択画面は「DIV」のDOM部品作成。
それの「行揃え」に「中央」をDOMスタイル設定。
それにオフをDOM表示設定。
結果画面は「DIV」のDOM部品作成。
それの「行揃え」に「中央」をDOMスタイル設定。
それにオフをDOM表示設定。
タイトル画面にDOM親要素設定。
「数当て」のラベル作成。
それの「文字サイズ」に「300%」をDOMスタイル設定。
2回、改行作成。
「1~16の整数の中から1個だけ思い浮かべてください。」のラベル作成。
改行作成。
「これから、提示する整数の中にそれがあるかの質問を7回します。」のラベル作成。
改行作成。
「7回のうち、1回だけ嘘をついてもかまいません。」のラベル作成。
改行作成。
「もちろん、嘘をつかなくてもかまいません。」のラベル作成。
2回、改行作成。
スタートボタンは「思い浮かべた!」のボタン作成。
選択画面にDOM親要素設定。
「質問 」のラベル作成。
質問回数ラベルは「-」のラベル作成。
「 / 7」のラベル作成。
改行作成。
DOM部品オプション["テーブルヘッダ"]はオフ。
質問テーブルは空配列のテーブル作成。
それの「ボックス表示」に「inline-table」をDOMスタイル設定。
改行作成。
「この中に思い浮かべた整数はありますか?」のラベル作成。
2回、改行作成。
肯定ボタンは「はい」のボタン作成。
否定ボタンは「いいえ」のボタン作成。
結果画面にDOM親要素設定。
「あなたが思い浮かべた整数は」のラベル作成。
2回、改行作成。
結果整数ラベルは「-」のラベル作成。
それの「文字サイズ」に「300%」をDOMスタイル設定。
2回、改行作成。
嘘位置ラベルは「-」のラベル作成。
2回、改行作成。
タイトルボタンは「最初に戻る」のボタン作成。DOM部品を操作する命令を並べ、それぞれの画面を作成する。
「ヘッダ無テーブル作成」でヘッダ無しのテーブルを作成しても、それに対して「テーブル更新」を行うとヘッダができてしまったので、かわりに「DOM部品オプション」でヘッダを作らない設定にした。
●質問表示とは
質問回数ラベルに(現在質問+1)をDOMテキスト設定。
定数の質問配列は現在質問の質問配列取得。
もし、質問配列の要素数が8と等しく無いならば
「質問配列の要素数が異常です!」のエラー発生。
ここまで。
定数の表用配列は空配列。
質問配列の0…3を参照して表用配列に配列追加。
質問配列の4…7を参照して表用配列に配列追加。
質問テーブルを表用配列にテーブル更新。
ここまで。
●質問進とは
現在質問を1増やす。
選択画面にオフをDOM表示設定。
もし、現在質問が7未満ならば
質問表示。
0.2秒待つ。
選択画面にオンをDOM表示設定。
違えば
選択候補取得して結果整数ラベルにDOMテキスト設定。
定数の嘘位置は嘘位置取得。
もし、それがNULLと等しいならば
嘘位置ラベルに「あなたは正直でしたね!」をDOMテキスト設定。
違えば
嘘位置ラベルに「あなたは{嘘位置+1}番目の質問に嘘をつきましたね!」をDOMテキスト設定。
ここまで。
1秒待つ。
結果画面にオンをDOM表示設定。
ここまで。
ここまで。
スタートボタンをクリックした時には
タイトル画面にオフをDOM表示設定。
状態初期化。
質問表示。
0.2秒待つ。
選択画面にオンをDOM表示設定。
ここまで。
肯定ボタンをクリックした時には
現在質問に真を回答記録。
質問進める。
ここまで。
否定ボタンをクリックした時には
現在質問に偽を回答記録。
質問進める。
ここまで。
タイトルボタンをクリックした時には
結果画面にオフをDOM表示設定。
0.2秒待つ。
タイトル画面にオンをDOM表示設定。
ここまで。それぞれのボタンを押したときの動作を定義した。
まとめ
4ビットの情報に3ビットの冗長な情報を加えて7ビットにすることで、1ビットだけ反転してももとの情報がわかるようにする有名なアルゴリズムをなでしこで実装し、これを用いて「ユーザーが思い浮かべた1~16の整数を質問の答えから当てる」アプリケーションを作成した。


コメント