ガジェット通信 GetNews

見たことのないものを見に行こう

体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

【言語不問】正規表現で暗号を解こう!エニ熊の暗号文【コーディング】解答と解説

正規表現で暗号を解こう!エニ熊の暗号文

本問題は、正規表現を利用したコードで簡単に解ける問題を、言語不問でコーディングして解くというものでした。

それでは以下、問題とその解答を見ていきましょう。

問題のオープニング

 あなたは、インターポールに協力しているホワイトハッカーだ。そんなあなたの元に、インターポールの友人、鉄形がやって来た。

「実は今おれは、世界的テロリストの Any Bear を追っている。そいつが、仲間たちとやり取りしている暗号文を入手した。

 どうやら奴らは”正規表現”を使い、”短いプログラム”でその暗号文を解読しているらしい。

 この暗号文には、Any Bear 一味が、次に爆破する予定の都市名が記されているらしい。頼む○○よ。この暗号文を、何とかして解読してくれないか」

 Any Bear は、日本では”エニ熊”と呼ばれているテロリストだ。よく考えれば解ける暗号文を使い、犯行声明を出すことで有名だ。

「わかった。”正規表現”で、”短いプログラム”で解読できるのだな」

 鉄形は、暗号文の一部をあなたに手渡した。それは、以下のようなものだった。

dtdvovuaueazebzjbnjxgnglklqxqfifswscicrmrymhphwpo

vdvybyeborolrtzthzxuxkuqfqwkwapagfgjnjincscmspm

emeuauyknkfyfzdzwdbwxixjbjtstrhrchqcvsvologqgpap

ntnbtmbcmscrervovwhkhawafgfpgypjyujdxdqxkqizilz

 解析の結果、あなたは1つの単純な法則で、暗号文を解読できることに気が付いた。

「なるほど。文字列を先頭から見ていき、文字の並びが『ABA』のようになっている3文字を、1回だけ『B』に置換する。この処理を置換不可能になるまで繰り返すのか」

 あなたは、簡単な解読サンプルを作り、鉄形にメモを手渡した。

wbwvcvhczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr

bvcvhczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr

bvcvhczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr

bchczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr

「鉄形。こんな感じで置換していくんだ。置換できなくなるまで、続けてみるぞ」

wbwvcvhczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bvcvhczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bchczhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bhzhdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bzdzmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bdmdpmyjnjpnsesiyiulugxgflftotaokqkxqr
bmpmyjnjpnsesiyiulugxgflftotaokqkxqr
bpyjnjpnsesiyiulugxgflftotaokqkxqr
bpynpnsesiyiulugxgflftotaokqkxqr
bpypsesiyiulugxgflftotaokqkxqr
bysesiyiulugxgflftotaokqkxqr
byeiyiulugxgflftotaokqkxqr
byeyulugxgflftotaokqkxqr
beulugxgflftotaokqkxqr
belgxgflftotaokqkxqr
belxflftotaokqkxqr
belxltotaokqkxqr
bextotaokqkxqr
bexoaokqkxqr
bexakqkxqr
bexaqxqr
bexaxr
bear

 ”bear”という文字列が現れたことに鉄形は驚いた。”bear”は、憎きテロリスト”エニ熊”の名前の一部である。

 鉄形は興奮して、あなたに体を寄せてきた。

「○○よ。すぐに、暗号解読のプログラムを作ってくれ。超特急だ!」

 ……やれやれ、相変わらずだなあ。まあ、人の命を救うためだ。協力しよう。

 あなたは鉄形に、プログラム作成の料金を告げ、さっそくコーディングに取りかかった。

解答例

作成するプログラム自体は、かなり簡単なものです。全ての行に対して、以下の処理を行えばよいです。

・文字列を先頭から見ていき、文字の並びが『ABA』のようになっている3文字を1つ探す。

・この3文字を『B』に置換する。

・この処理を置換不可能になるまで繰り返す。

この処理を、シンプルなJavaScriptで書いてみます。

// JavaScript (spidermonkey)
while(t = readline()) {
do {
c = t;
t = t.replace(/(.)(.)1/, “$2”);
} while(c != t)
print(t);
}

「(.)(.)1」の部分が『ABA』の部分です。最初の「(.)」と最後の「1」の部分が同じ文字を指します。そして、2番目の「(.)」と置換文字列の「$2」が同じ文字で対応しています。

そして、「while(c != t)」で、置換結果が一致しなくなるまで、置換処理を繰り返しています。

この問題はシンプルなので、どのプログラミング言語でも、同じアルゴリズムで解くことができます。それでは、解答者のコードの中から、そうしたコードを見ていきましょう。各言語で、簡潔なコードを3つずつ掲載していきます。

AWK (gawk)

有効回答数1。

// deni_T 様 (331 文字)
{
code=$0;
while(1){
i++;
if(i>(length(code)-2)){break;}
code=sprintf(“%s”,code);
if(substr(code,i,1)==substr(code,(i+2),1)){
code=subS(code,i);
i=0;
}
}print code;
}

function subS(str,n){
char1=substr(str,n,3);
char2=substr(str,n+1,1);
sub(char1,char2,str);
return str;
}

1 2 3 4次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

山寺宏一&高木渉で『ポプテピピック』

GetNews girl / GetNews boy