前書き
最近、「STYLYからの挑戦状」という採用試験を作りました。
この採用試験は11月末をもって、回答を締め切ったのですが、今回、STYLYのアドベントカレンダーをする。ということで解説記事を書くことにしました。
この記事では私が担当した3問について解説します。
ゲーデル数暗号
問1
以下の暗号を解け。理由と解読に利用したプログラムを併せて答えよ。
A = 2
B = 4
C = 8
G = 128
O = 32768
GO = 1836660096
BAG = 937500
??? = 107986511563267291742738627625390973109310421142578125000
これは、ゲーデル数というものを知っているか、思いつけるか。という問題です。
ゲーデル数とは簡単に言うと、素因数分解の一意性を利用して、符号化する方式です。
ここではアルファベットが何番目の文字であるか？に注目します。
例えば、Aという文字はアルファベットの1番目、Bは2番目、Cは3番目という順番です。
そうしたとき、この問題では、
A=2=2^1
としています。1番目の素数(2)のA番目(1)乗としています。同様にBについて考えると、
B=4=2^2
で、1番目の素数のB番目(2)乗としています。ここで、GOを見ると、
GO = 1836660096 = 2^7 * 3^15
となっています。ここから、1番目の素数(2)のG番目(7)乗、2番目の素数(3)のO(15)番目乗となっています。
このように、
1番目の素数^(1文字目のアルファベットの番目)*2番目の素数^(2文字目のアルファベットの番目)...
と符号化する方式となっています。
そのため、???となっている値を素因数分解すると、
107986511563267291742738627625390973109310421142578125000 = 2^3 * 3^25 * 5^16 * 7^8 * 11^5 * 13^18
となり、3,25,16,8,5,18番目のアルファベットを考えると、「CYPHER」という答えになります。
この問題のポイントは2点あって、ゲーデル数のロジックを見抜けること。というのが1点。もう1つは巨大な数字を素因数分解できるのか。というのがもう1つのポイントです。
例えば、C#であれば、ulong型でも2^64-1以下の値しか扱うことが出来ません。そのため、巨大な数字をどのように素因数分解するかがカギになってきます。もしくは、Pythonであれば、int型の精度は基本的に無限です。そのため、用途に合った言語にスイッチして解答を構築できるか？がカギになります。
作問に使ったプログラムはこんな感じ。
作問時は、NEWVIEWとかを値として出力する候補があったんですが、あまりにも数値が凶悪だな。というので小さめの数字にするためにCYPHERになりました。
def prime():
data = [2,3]
yield 2
yield 3
i=4
while True:
if all(i%j != 0 for j in data):
data.append(i)
yield i
i += 1
table = {
chr(ord('A')+i):i+1
for i in range(26)
}
primes = [p for i,p in zip(range(10),prime())]
def encode(text,table,primes):
result = 1
for t,p in zip(text,primes):
result *= (p**table[t])
return result
def decode(value,table,primes):
data = []
i = 0
while value != 1:
count = 0
while value % primes[i] == 0:
value //= primes[i]
count += 1
if count > 0:
data.append((primes[i],count))
i += 1
if i == len(primes):
raise
return data
def puts(text):
print(text,encode(text,table,primes))
print(table)
puts('A')
puts('B')
puts('C')
puts('G')
puts('O')
puts('GO')
puts('BAG')
puts('NEWVIEW')
puts('CYPHER')
factor = (decode(107986511563267291742738627625390973109310421142578125000,table,primes))
print(factor)
print("".join(chr(ord('A')-1+b) for a,b in factor))
Brainf*ck問題
以下は自作プログラミング言語、virtual 言語のプログラムとその出力結果である。
プログラム
aaaaaiaaaaavraaaaaaaaraaaaaiaaaaaaaraaarattttilruraauaaaaiaaaauuaaauraaaaauttaaaaaaaaiiaaaaaaaaauruaaauiiiiiiuiiiiaiiiiiurau
出力
Hello World!
プログラミング言語 virtual は、Brainfck 言語を元にした言語である。
Brainfck 言語上の記号 +-><.[] を virtual の文字に割り当てた言語である。(,は不使用)
記号の割り当てルールを導出過程と合わせて答えよ。
これは、ある意味で解くだけの問題。という想定でした。
この問題はほとんど答えが書いてあって、Brainfckのインタープリターを実装して、Brainfckの記号である+-><.[]がvirtualのどの文字にあたるかを総当たりで調べて、HelloWorld!が出力できる記号の組み合わせを計算する問題でした。
作問に使ったプログラムはこんな感じ
def exec_source(source):
output = ""
ptr_index = 0
data = [0] * 300000
index = 0
count = 0
while index < len(source):
if 0 > index:
return None
if (ptr_index < 0 or ptr_index >= len(data)):
return None
if count > 100000:
return None
c = source[index]
if c == '>':
ptr_index += 1
elif c == '<':
ptr_index -= 1
elif c == '+':
data[ptr_index] += 1
elif c == '-':
data[ptr_index] -= 1
elif c == '.':
try:
output += chr(data[ptr_index])
except:
return None
elif c == '[':
if data[ptr_index] == 0:
nest = 0
while True:
index += 1
if index == len(source):
return None
elif source[index] == '[':
nest += 1
elif source[index] == ']':
if nest == 0:
break
else:
nest -= 1
elif c == ']':
if data[ptr_index] != 0:
nest = 0
while True:
index -= 1
if index < 0:
return None
elif source[index] == ']':
nest += 1
elif source[index] == '[':
if nest == 0:
break
else:
nest -= 1
index += 1
count += 1
return output
ABC = "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++."
hello_world = "+++++-+++++[>++++++++>+++++-+++++++>+++>+<<<<-]>.>++.++++-++++..+++.>+++++.<<++++++++--+++++++++.>.+++.------.----+-----.>+."
hoge = "++++++++++[>++++++++++<-]>++++.+++++++.--------.--."
fizzbuzz = """++++++[->++++>>+>+>-<<<<<]>[<++++>>+++>++++>>+++>+
++++>+++++>>>>>>++> >++<<<<<<<<<<<<<<-]<++++>+++
>-->+++>->>--->++>>>+++++[->++>++<<]<<<<<<<<<<[->-
[>>>>>>>]>[<+++>.>.>>>>..>>>+<]<<<<<-[>>>>]>[<+
++++>.>.>..>>>+<]>>>>+<-[<<<]<[[-<<+>>]>>>+>+<<<<<
<[->>+>+>-<<<<]<]>>[[-]<]>[>>>[>.<<.<<<]<[.<<<<]>]>.<<<<
<<<<<<<]"""
def replace(s):
return s.replace("[","v").replace("-","i").replace(">","r").replace("<","t").replace(".","u").replace("+","a").replace("]","l")
a = "virtual"
b = "+-><.[]"
print(exec_source(hello_world))
replaced_hello_world = replace(hello_world)
print(replaced_hello_world)
import tqdm
import itertools
for p in tqdm.tqdm(list(itertools.permutations(b))):
s = replaced_hello_world
for s1,s2 in zip(a,p):
s = s.replace(s1,s2)
r = exec_source(s)
if r is None:
continue
if r == "Hello World!":
print(r)
print(s)
for s1,s2 in zip(a,p):
print(f"{s1} => {s2}")
この問題の難しいポイントは、インタープリターの実装とプログラムの停止問題でした。Brainf*ckのインタープリターを作る必要があるので、それを「インタープリターを実装できるぐらい言語仕様に詳しい必要があること」そして、もう1つは置換した文字の組み合わせにおいては、「プログラムが停止しないこと」でした。"["や"]"の文字は、ポインタが指している値が0かそうでないかによって、ジャンプの可否が決まる仕様となっています。そのため、置換を試行している過程において、無限ループに陥り、プログラムが終了しないことがあります。そういったことが分かっており、インタープリターの実装に細工を入れ、命令の実行で途中で止められる改造を施す工夫が必要でした。
が、この問題は回答者の方は想定を超えてました。というのは文字の頻度解析で大体解ける。という感じでした。
問題文の文字列の頻度解析をすると、
- v => 1回
- i => 21回
- r => 9回
- t => 6回
- u => 12回
- a => 74回
- l => 1回
と分かります。
今回、Hello World!という文字列を出力しているため、出力の記号"."にあたる記号は、12回出現する。ということが分かります。そこで、virtual言語で12回出ている文字は何か。というと、"u"となり、"."の文字が確定します。
また、"["と"]"の文字は、対応関係になると考えられます。そうすると、"[","]"にあたる文字は同数になると考えられます。ここから、"[","]"にあたる文字は、"v"と"l"であろう。ということは分かります。ここで、問題文を見返すと、先に出てくる文字が"v"なので、"v"が"[","l"が"]"ということで、確定します。
また、"uuaaau"という文字列があります。これは、Hello World!の文字列で言えば、"llo"を出力する部分にあたります。uuで、"ll"と出力しているのでポインタの指している値は、108(lのASCIIコード)です。それに"aaa"を行うことで、"o"を出力しています。"o"はACIIコードで111なので、"a"はポインタの値のインクリメントを表す記号。"+"にあたることが分かります。
同様に、"u"が出力を表すことから、"uiiiiiiu"という部分が、"Hello World!"の"rl"に当てはまることが分かります。そこで、"r"はASCIIコードで114、"l"は108で表されます。ここで、間に"i"が6つあることから、"i"がポイントの値のデクリメントを表す記号、"-"であることが分かります。
残りの記号を見ると、"r"と"t"が">"と"<"のどちらかに割当たるかが分かります。ここで、問題文の最初である"aaaaaiaaaaavr"を見たとき、ポインタの指す番地がマイナスになることは無いだろう。と考えると、"r"は自然と">"に割当たります。そして、残った値として、"t"が"<"にあたることが分かります。
社内で問題を見せたときに、@segurさんがこんな感じの回答をしていたので、そんなやつ他におれへんやろ。と思ったんですが、社外の人の回答は頻度解析(とそれに類する合わせ技)の方が多く、むしろ私の方がマイナーな解き方でビビった感じでした。
Zip問題
問4
以下のzipファイルに含まれる暗号文をすべて解析せよ。https://drive.google.com/file/d/1rUdQvoMUKfRTqB2ZqFHWGutOT2fNSfy0/view?usp=sharing
（※ 複雑なzipファイルのため、既存の解凍ソフトを使った場合、コンピューターが応答不能になる場合があります。注意してください。）
この問題は回答者がいたものの正答した人が居なかった問題です
この問題は、回答が2つあります。この問題は実はいやらしくて、この問題だけ"すべて解析せよ"という文言になっています。
1つの問題は何か。というと、ファイルがzip圧縮されているので、それを解凍します。
解凍すると、"comp10000.zip"というファイルが出力されます。そして、このファイルをもう一度解凍すると、"comp9999.zip"というファイルが出力されます。もう一度、解凍すると、"comp9998.zip"というファイルが出力されます。・・・という感じで1万回解凍が必要なデータになっています。
というので、1万回解凍できるか否かが問題になります。これは、私の視点で言えばシェル力です。一番、簡単に組めるのはbashなどのシェルが簡単かな。と思ったので、そういう風にシェルが組めるかどうかを見たかった問題になっています。そうやって解凍していくと、sample.txtというファイルが手に入り、
他人が見えない世界を見ること
Never be perfect.
というテキストが手に入ります。これが第一問の答えです。
というわけで、他人が見えない世界を見る必要があるのが第2問目です。
そこで、result.zipの内容をバイナリで見ると、以下の様になっています。
最後の方に、"SGFjayB0aGUgcHJvY2Vzcwo="という文字列があります。この文字列をbase64でデコードすると、
$ echo "SGFjayB0aGUgcHJvY2Vzcwo=" | base64 -d
Hack the process
となります。というわけで、もう1つの答えは"Hack the process"でした。
流石に、ここまでたどり着く人はいないかな。いたら嬉しいな。という感じの作問でした。
採用問題を作るにあたって考えたこと
- 答えが1つに決まること
- トリッキーな問題であること
1.に関して言えば、採点効率の問題です。例えば、「STYLYのサーバーサイドAPIを作るにあたって、どのような技術選定をしますか？その理由も合わせて答えなさい。」という問題は興味深い内容ではあります。しかし、技術にも好き嫌いがあり、それが合理的であるかは、議論の分かれるところではあります。そのため、一概に、正解・不正解。と言いにくい問題は避け、必ず答えが1つに定まるような作問を心掛けました。
2.は、どういうことかというとシニアエンジニア向けな内容を目指していました。したがって、競技プログラミングのような「問題をいかに効率的に解くか？」という視点ではなく、「必ずプログラムを書かざるを得ない謎解き」であったり、「技術的にエッジの尖った知識を要する」という視点を盛り込みながら作問をしていました。
例えば、問1であれば、「107986511563267291742738627625390973109310421142578125000を素因数分解する必要がある」という技術課題があります。話が繰り返しになりますが、この値は、組み込みのint型などで扱えないサイズの値になっています。そのため、整数で任意精度の数字を扱う必要があります。そういった視点で問題を見ることが出来て、任意の精度をライブラリを知っている。使いこなせる実力があるか。というのがキーになります。
問3であれば、もともとBrainfckを言語として扱っています。Brainfck自体は、ネタなプログラミング言語として有名な部類であると認識しています。そのため、見たら何言語かは分かる人は多いですが、それでまともにプログラムを組んだり、ちゃんと読めたり書けたりする人は珍しい人(技術的に尖った人)だと認識しています。そのため、Brainf*ckを用いた作問をしました。
問4は、完全にトリッキーな問題を解けるか。というところを狙っています。おそらく、人生の中で1万回zip圧縮されたファイルを解凍することは無いと思います。しかし、そういうトリッキーなことを要求されることは現実世界ではたまにあります。そのようなトリッキーな案件をこなせるか？というところが1点。もう1つはCTF的な視点。さすがに1万回だと、面白みが少なかったので、バイナリに値を隠す。ということをして、そういう視点まで見抜ける人が居たら嬉しいな。という問題でした。
STYLYからの挑戦状 第2弾開催
というわけで、また、私が「STYLYからの挑戦状 第2弾」を作成しました。
XRに興味のある方。実力試しをしてみたい方、年末年始の休みを利用して解いてみてはいかがでしょうか？
Psychic VR Labでは、Webエンジニア・XRエンジニアを募集中です！！