ガジェット通信

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

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

DATE:
  • ガジェット通信を≫

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

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

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

問題のオープニング

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

「実は今おれは、世界的テロリストの 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;
}

Bash

有効回答数3。注:distancedsilhouette 様は、%20 様と同等のコードもコメントで書いていましたが、全体の文字列の長さとしては、187文字になっています。

// %20 様 (27 文字)
sed -re':;s/(.)(.)1/2/;t’

// distancedsilhouette 様 (187 文字)(sedを使った部分は33文字)
# sed
#sed -e':t;s/(.)(.)1/2/;t t’

# JavaScript(Spidermonkey)
(pg;echo)|js -e ‘
r=/(.)(.)1/
while(a=readline()){
while(a.match(r))a=a.replace(r, “$2″)
print(a)
}

// shinayoshi 様 (219 文字)
#!/bin/bash

while read LINE
do
CNT=1
while [ ${CNT} -ne 0 ]
do
LINE=`echo ${LINE} | sed ‘s/(.)(.)1/2/1’`
CNT=`echo ${LINE} | grep -E “(.)(.)1″ | wc -l`
done
echo ${LINE}
done

C

有効回答数12。

// ロータス 様 (239 文字)
char s[256];
int i,j,k;
int main(){
for(;~scanf(“%s”,s);){
for(i=0;ib)p–,l++;}else{p++,l–;}}puts(b);}return 0;}

C#

有効回答数11。

// ピロ 様 (464 文字)
using System;
using System.Text.RegularExpressions;

namespace CodeIq.RegEx {
class Program {
static void Main(string[] args) {
string line;
for (; (line = Console.ReadLine()) != null;) {
Regex r = new Regex(@”(.)(.)1″);
while (r.IsMatch(line)) {
line = r.Replace(line, @”$2″, 1);
}
Console.WriteLine(line);
}
}
}
}

// KEN0123 様 (479 文字)
using System;
using System.Text.RegularExpressions;
class Program
{
static void Main()
{
for (string line; (line = Console.ReadLine()) != null;)
{
Console.WriteLine(Decipher(line));
}
}
static string Decipher(string s)
{
Regex rgx = new Regex(@”(w)(w)1″);
for (string old_s = “”; old_s != s;)
{
old_s = s;
s = rgx.Replace(s, @”$2″, 1);
}
return s;
}
}

// Puffer 様 (498 文字)
using System;
using System.Text.RegularExpressions;

namespace Test
{
class Program
{
static void Main()
{
String line;
Regex r = new Regex(@”(?w)(?w)k”);
for (; (line = Console.ReadLine()) != null;)
{
while (r.IsMatch(line))
{
line = r.Replace(line, “${word}”);
}
Console.WriteLine(line);
}
}
}
}

C++11

有効回答数2。

// score353 様 (506 文字)
#include
#include
#include

int main()
{
char str[50][256];
int i=0, j, p;
for (p = 0;p < 50;p++)
scanf("%s", str[p]);
for (p = 0;p s){
string ans;
while(true){
bool changed=false;
int pos=0;
for(;pos System.Console.ReadLine()) |> Seq.takeWhile(() null)
|> Seq.iter (solve >> printfn “%s”)

main()

Fortran

有効回答数1。

// SOMETHING COOL 様 (1084 文字)
CHARACTER(99) R
INTEGER
E
!
標準入力
DO WHILE (.TRUE.)
READ(*, “(A)”, IOSTAT=E) R
IF (E.NE.0) THEN
EXIT
ELSE
L = LEN_TRIM(R)
IF (L.GT.0) THEN
CALL ENIGMA(R, L)
END IF
END IF
END DO
STOP
END
!
!
**********
!
* Enigma *
!
**********
SUBROUTINE ENIGMA(R, L)
CHARACTER(99) R, W
LOGICAL
F
DO WHILE (.TRUE.)
F = .FALSE.
DO I = 1, L-2
IF (R(I:I).EQ.R(I+2:I+2)) THEN
F = .TRUE.
K = 0
W = ” ”
DO J = 1, L
IF (J.EQ.I.OR.J.EQ.I+2) THEN
CYCLE
ELSE
K = K + 1
W(K:K) = R(J:J)
END IF
END DO
R = W
L = LEN_TRIM(R)
EXIT
END IF
END DO
IF (.NOT.F) EXIT
END DO
WRITE(*, “(A)”) R(1:L)
END SUBROUTINE ENIGMA

Haskell

有効回答数5。

// Bern 様 (196 文字)
f (a:[]) = a:[]
f (a:b:[]) = a:b:[]
f (a:b:c:[]) = if a==c then b:[] else a:b:c:[]
f (a:b:c:xs) = if a==c then f(b:xs) else a:f (b:c:xs)
main = getContents >>= mapM_ putStrLn . map (f . f) . lines

// erin 様 (349 文字)
— 正規表現で暗号を解こう!エニ熊の暗号文【コーディング】
import Data.List

main :: IO ()
main = do
a String
getAns = reg

reg :: String -> String
reg a = case findIndex ((x,y) -> x == y) $ zip a (drop 2 a) of
Just b -> reg $ take b a ++ (a !! (b+1)) : drop (b+3) a
Nothing -> a

// fus 様 (481 文字)
module Main where

main :: IO ()
main = do
contents String
converge [] = “”
converge [x] = x
converge (x:y:xs) | x == y = y
| otherwise = converge (y:xs)

decrypt :: String -> String
decrypt [] = []
decrypt (x:[]) = [x]
decrypt (x:y:[]) = [x,y]
decrypt (x:y:z:xs) | x == z = decrypt (y:xs)
| otherwise = x : decrypt (y:z:xs)

Java7

有効回答数11。

// まめぴ 様 (579 文字)
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Main main = new Main();
main.read();
}
public void read() {
Scanner cin = new Scanner(System.in);
for (; cin.hasNext();) {
System.out.println(decode(cin.nextLine()));
}
cin.close();
}
// 正規表現の後方参照と、記憶した文字列の利用で、短いコードでプログラムを書くことができます。
public String decode(String value) {
// 3文字で3文字目が1文字目と一致する箇所があれば解読対象
if (value.matches(“.*(.)(.)\1.*”)) {
value = value.replaceFirst(“(.)(.)\1″, “$2″);
return decode(value);
} else {
return value;
}
}
}

// まんちかん 様 (586 文字)
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class CodeIQ4 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()){
String line=cin.nextLine();
System.out.println(solve(line));
}
}
private static String solve(String text){
Pattern p= Pattern.compile(“([a-z]).\1″);
Matcher matcher=p.matcher(text);
while(matcher.find()){
String temp=matcher.group();
temp=temp.substring(1,2);
text=matcher.replaceFirst(temp);
matcher=p.matcher(text);
}
return text;
}
}

// kid_shelted 様 (649 文字)
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Main{
public static void main(String[]args){
Scanner cin=new Scanner(System.in);
for(;cin.hasNext();){
System.out.println(bear(cin.nextLine()));
}
}
private static final Pattern key = Pattern.compile(“([a-z])([a-z])\1″);
private static String bear(String _line)
{
String line = _line;
Matcher match = key.matcher(_line);
while (match.find())
{
line = match.replaceFirst(“$2″);
match = key.matcher(line);
}
return line;
}
}

Java8

有効回答数12。

// Mattsun 様 (374 文字)
import java.util.Scanner;

class AnyBear {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
while (sc.hasNextLine()) {
String pre = “”;
String str = “”;
str = sc.nextLine();
while (!str.equals(pre)) {
pre = str;
str = str.replaceFirst(“(.)(.)\1″, “$2″);
}
System.out.println(str);
}
}
}

}

// 退会済ユーザー 様 (490 文字)
import java.util.Scanner;

class Enigma
{
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
while(stdIn.hasNext())
{
StringBuilder codeStr = new StringBuilder(stdIn.nextLine());
for(int i = 0; i < codeStr.length() – 2; i++)
{
if(codeStr.charAt(i) == codeStr.charAt(i + 2))
{
codeStr.deleteCharAt(i);
codeStr.deleteCharAt(i + 1);
i = -1;
}
}
System.out.println(codeStr);
}
stdIn.close();
}
}

// SUZAKU 様 (542 文字)
import java.util.regex.*;
import java.util.*;
class RegularExpression {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String target = "";
while(scan.hasNext()) {
target += scan.next() + "n";
}
String regex = "(\w)(\w)\1";
Pattern pattern = Pattern.compile(regex);
Matcher match = pattern.matcher(target);
while(match.find()) {
target = match.replaceAll("$2");
match.reset(target);
}
System.out.println(target);
}
}

JavaScript (rhino)

有効回答数5。

// lightpurplewisteria 様 (227 文字)
d=new java.util.Scanner(java.lang.System.in);
s=u=”
while(d.hasNext())s+=d.nextLine()+’rn';
function c(t){for(i=0;i

Prolog (swi)

有効回答数1。

// pelicanlord 様 (407 文字)
trans([X,A,X|Rest] , [A|Rest]):-!.
trans([X|Rest],[X|Rest1]):-
trans(Rest,Rest1).

decode(X,Code):-
trans(X,Y),!,
decode(Y,Code).
decode(X,X).
writelist([]):-nl.
writelist([X|Rest]):-
format(“~c”,X),
writelist(Rest).

solve:-
at_end_of_stream(user_input).
solve:-
readln([Str]),
string_to_list(Str,List),
decode(List,Code),
writelist(Code),
solve.

:-prompt(_,”),
solve.

Python

有効回答数14。

// だいじゅ 様 (163 文字)
import re

try:
while True:
s = raw_input()
while True:
s, n = re.subn(“(w)(w)\1″, “\2″, s)
if n == 0:
break
print s
except EOFError:
pass

// Kezy 様 (166 文字)
import re
try:
while True:
s=raw_input()
while s!=re.sub(r”(w)(w)1″,r”2″,s):
s=re.sub(r”(w)(w)1″,r”2″,s)
print s
except EOFError:
pass

// mmiehana 様 (189 文字)
import re
import copy

try:
while True:
l = raw_input()
while True:
c = copy.copy(l)
l = re.sub(r'(w)(w)1′, r’2′, l)
if c == l:
break
print l
except EOFError:
pass

Python 3

有効回答数18。

// ほげはげ 様 (168 文字)
import re
import sys

for s in sys.stdin.read().split():
while re.match(r’.*(w)(w)(1).*’, s):
s = re.sub(r'(w)(w)(1)’, r’2′, s, count=1)
print(s)

// soliton_at_evolve 様 (196 文字)
import fileinput, re

for line in fileinput.input():
s = str(line.strip())
while s :
t = re.compile(r”(.)(.)1″).sub(r”2″, s)
if t == s : break
s = t
print (s)

// ボヤッキー 様 (200 文字)
import re
import sys

for line in sys.stdin.readlines():
x = line.strip()
while True:
y = re.sub(r'(.)(.)1′, r’2′, x)
if x == y:
break
x = y
print(x)

Ruby

有効回答数58。

// rotary-o 様 (39 文字)
#!ruby -p
0while$_.sub! /(.)(.)1/,’2′

// y azshe 様 (50 文字)
puts $

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP