前書き
昨年末、「STYLYからの挑戦状 Vol.2」という企画を公開させていただきました。
これは2問正解するとPsychic VR Labの採用試験の書類選考をスキップできる。というものでした。
このVol.2は、先月2月末をもって募集を締め切ったので、前回同様、問題の解説をしたいと思います。
シーザー暗号
以下のn文字シフトにより暗号化された暗号文を解いて下さい。
また、利用したプログラムや考え方を記述してください。Rewzdi Newzdi ckd yx k gkvv,
Rewzdi Newzdi rkn k qbokd pkvv.
Kvv dro usxq'c rybcoc kxn kvv dro usxq'c wox
Myevnx'd zed Rewzdi dyqodrob kqksx.
シーザー暗号は暗号としてはかなり簡単な部類です。
シーザー暗号では最初に何文字ずらすか。ということを決めます。例えば、これを3文字とします。
そうすると、AはDにマッピングされ、BはEへマッピングされる。という風にアルファベット同士の対応関係が生まれます。この対応関係を用いて、文章の暗号化・復号化を行います。
この問題の難しいポイントは「何文字ずらすか」というところが不明であることです。この辺りの解析もやり方は複数あります。例えば、"This is a pen."といった例文を考えたとき、冠詞のaは小文字1文字で存在します。そうすると、暗号化された文章でも、冠詞のaは小文字1文字で表されるだろう。ということが予想がつきます。
そうした場合、今回の暗号文には"k"という1字が見つかります。そこから、"k"は"a"にあたるのではないか。という推論が成り立ちます。シーザー暗号の場合、「何文字ずらすか」が分かればなんとかなるので、"k"と"a"の差分を求めることで暗号の解読が可能です。
答えは、
Humpty Dumpty sat on a wall,
Humpty Dumpty had a great fall.
All the king's horses and all the king's men
Couldn't put Humpty together again.
問題作成に使用したコード
s = """Humpty Dumpty sat on a wall,
Humpty Dumpty had a great fall.
All the king's horses and all the king's men
Couldn't put Humpty together again."""
def encoder_seaser(text,n):
def _():
for a in text:
if not a.isalpha():
yield a
continue
base = "A" if a.isupper() else "a"
yield chr((ord(a)-ord(base)+n)%26+ord(base))
return "".join(_())
p = encoder_seaser(s,10)
print("encoded")
print(p)
print("-"*10)
for i in range(26):
s = encoder_seaser(p,i)
if any("the" in a for a in s.split(" ")):
print(i)
print(s)
print("="*26)
私の書いたプログラムでは、「まぁ大体の英文にtheって単語は入っているだろう」という推論から、とりあえず総当たりでアルファベットをシフトした後、"the"という単語が復号した文章に含まれていれば出力する。というプログラムになっています。
パンダ問題
以下のプログラムの実行結果がなぜ以下の様な出力になるか説明して下さい。
プログラム：
from itertools import combinations data = ['パンダ','パンダ','パンダ','パンダ','パンダ','パンダ','パンダ','パンダ'] for a,b in combinations(data,2): print(f"{a} === {b} is {a==b}")実行結果：
パンダ === パンダ is False
パンダ === パンダ is True
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is True
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is True
パンダ === パンダ is False
パンダ === パンダ is False
パンダ === パンダ is True
パンダ === パンダ is False
これは作ったはいいのですが、若干の悪問だったので反省している問題です。
端的には、
Unicodeの正規化の問題です。
「パ」などの文字は「ハ」＋「゜」の2つのパーツに分けられます。この時、「パ」を1文字として扱う正規化と「ハ」+「゜」の2つに分ける正規化の２つがあります。前者をNFC、NFDといいます(本当はもう少し分類がありますが、簡単のためにこう表現しています)。WindowsはNFCという形で日本語を正規化していましたが、古いMacはNFDの形式で正規化をしていたそうです。
問題では、「パ」と「ダ」の文字にNFCとNFDの2つの表記があります。これらの文字は見た目では分かりませんが、バイナリレベルでは値が異なります。
パ
NFC e38391
NFD e3838fe3829a
ン
NFC e383b3
NFD e383b3
ダ
NFC e38380
NFD e382bfe38299
一方で、「ン」の文字は、NFC,NFDどちらでも値は変わりません。
問題のパンダはそれぞれの文字をNFCかNFDかのどちらかで正規化したあと、合体させた文字になっています。
それぞれの"パンダ"のエンコードは以下の様になっています。
('NFC', 'NFC', 'NFC')
('NFC', 'NFC', 'NFD')
('NFC', 'NFD', 'NFC')
('NFC', 'NFD', 'NFD')
('NFD', 'NFC', 'NFC')
('NFD', 'NFC', 'NFD')
('NFD', 'NFD', 'NFC')
('NFD', 'NFD', 'NFD')
ここで、パンダ==パンダとなりうるのは、左辺と右辺の"パ"の正規化形式が一致しており、かつ、左辺と右辺の"ダ"の正規化形式が一致しているパターンとなります。
それらは以下の4パターンとなり、4つだけTrueになる。という仕組みになっています。
NFC NFC NFC
NFC NFD NFC
NFC NFD NFD
NFC NFC NFD
NFD NFC NFC
NFD NFD NFC
NFD NFD NFD
NFD NFC NFD
多くの解答が「"パ"と見える文字だが、"パ"と表現する方式と、"パ"を"ハ"+"゜"で表現する方式に分かれているから」。もしくは、「"パンダ"という文字が4種類の表現で表されている」というものでした。これらの解答は答えに近いのですが、作者としては少しずれている。という気持ちでした。仮に、「4種類で表現されている」というところを正解だとすると、問題のソースコードで、['パンダ','パンダ','パンダ','パンダ','パンダ','パンダ','パンダ','パンダ']と8つパンダを書く必然性がありません。4つの表記で十分なはずです。
問題の想定としては、"NFCとNFDの2つのエンコード方式を用いている"。パンダは3文字である。それぞれの文字をエンコードして結合すると、2^3=8パターン存在する。その中で、"ン"はNFC,NFDのどちらも変わらないため、パとダのエンコードが一致した4パターンのみがTrueとなる。という解答を予想していました。
これは作問の難しさもあり、「Unicodeという言葉を用いて説明しなさい」といった細かい誘導を書きすぎるとタネがバレやすく、しかし、そこを適切に誘導できていないため、解答者側もうまく解答してもらえなかった。というなかなか作問者にとっても痛しかゆしな問題でした。
問題作成に使用したコード
from itertools import product
import unicodedata
panda = "パンダ"
p = ['NFC','NFD']
for s in panda:
print(s)
for pt in p:
c = unicodedata.normalize(pt, s)
t = c.encode('utf-8').hex()
print(f"{pt} {t}")
data = []
for pp in product(p,repeat=3):
print(pp)
target = "".join(unicodedata.normalize(pt,s) for s,pt in zip(panda,pp))
#print(target)
#print(target.encode('utf-8').hex())
data.append(target)
print("""
from itertools import combinations
data = [%s]
for a,b in combinations(data,2):
print(f"{a} === {b} is {a==b}")
"""%(",".join("'%s'"%d for d in data)))
これは完全に余談なんですが、大学時代、プログラミング演習の授業があり、当時は課題のソースコードをUSBメモリに入れ、教授にもっていっていました。ある日の放課後、私は課題の提出に研究室に行きました。その時、たまたま同級生の女の子がいて、先に提出をしていました。教授は女子から受け取ったUSBメモリを、FedoraのPCに刺し、課題のデータを取り込んでいました。その様子を、女の子と私は見ていたのですが、そこで私はあることに気づき、
「うん？君の家のPCってMac？」
と聞いてしまい、
「え、なんで分かるの。気持ち悪い・・・」
と女の子から言われた記憶があります。答えは簡単で、このNFCとNFDの話で、当時のMacで作った"プログラミング演習"というファイル名が、教授のパソコンでは"フ゜ログラミンク゛演習"のような表記になっていたからです。当時はそんな知識は無かったので、Windowsだとそういうこと起きない(当時もWindowsとLinuxを併用していた)から、たぶんMacじゃね？ぐらいの勘です。でも、授業の演習などでたまに少し話す程度の人と、偶然に提出で鉢合わせて、提出の風景を見ているだけなのに、ぴたりと「君の家のPCってMacだよね？」と言われて、当てられてたら年頃の女性からすると相当気持ち悪いですよね。ハイ。思ってても言わない方がいいことがあるってのをUnicodeの正規化から学びました。
広大で深淵なjson
以下のようなjsonを考えます。
{ "a1": { "b1" : { "c1" : "v1" } }, "a2": { "b2" : { "c2" : { "d2" : "v2" } } }, "a3": { "b3" : "c3" } }このデータでは、Objectの要素が階層構造になっている(a1の中にb1,b1の中にc1)ことが分かります。このようなjsonのObjectの中の階層構造が一番深い部分に入っているデータ。サンプルの”v2”に当たるデータのことを、ここでは「一番深いデータ」と呼ぶこととします。
この時、以下のjsonファイルの「一番深いデータ」を答えて下さい。
また、利用したプログラムや考え方を記述してください。
https://drive.google.com/file/d/1NNys5AQ6m2NWNeX0rT_nrWIbvsdFCfHD/view?usp=sharing
この問題は、かなり凝った問題になっています。
多分普通の方であれば、まぁjsonをパースして値を深さ優先探索なりをするのがベターな方針だと思います。しかし、それほど簡単には作っていません。作問の時点で、 python,php,rubyの標準のjsonパーサーだとエラーで処理できない規模のjsonにしてあります。 したがって、そういった問題を"どういった工夫で乗り切るか"を見る問題です。
解答例はこちら。
const fs = require('fs');
const jsonObject = JSON.parse(fs.readFileSync('./sample_dl.json', 'utf8'));
let max_depth = 0;
let max_value = "";
let queue = [[0,jsonObject]];
while (queue.length > 0) {
let obj = queue.shift();
let depth = obj[0];
let value = obj[1];
for (let key in value) {
if (typeof(value[key]) === 'object') {
queue.push([depth + 1, value[key]]);
} else {
if (depth > max_depth) {
max_depth = depth;
max_value = value[key];
}
}
}
}
console.log(max_depth);
console.log(max_value);
python,php,rubyは巨大なjsonを処理することが出来ませんでしたが、node.jsはパースすることが可能でした。したがって、問題によって言語を変える柔軟さがあるか？というところもポイントでした。しかし、node.jsはパースは可能ですが、普通に再帰の深さ優先探索で組むと再帰の上限に引っかかり、動かなくなりました。したがって、キューを用いて、再帰の上限に引っかからないようにプログラムを変形し、探索する。というのが模範解答です。
私が採点をしていると、"jsonのパーサーを簡易的に自作する"というものが多かったです。"{"が見つかる度にdepth++,"}"が見つかる度にdepth--。文字列が見つかったら切り出して、一番depthが深いものを出力する。というものです。
この辺ぐらいまでは、想定の範囲内でしたが、社長が社員の発想を飛び越えた解き方を出してきたので紹介します。
import urllib.request, urllib.error,json,sys
sys.setrecursionlimit(100000)
url = 'https://drive.google.com/uc?id=1NNys5AQ6m2NWNeX0rT_nrWIbvsdFCfHD'
response = urllib.request.urlopen(url=url)
output_json = json.loads(response.read())
#再帰的にJSONのvalueを掘っていき、valueが文字列のときにその深さと値を表示
def getValueAndDepthIfValueIsString(json_data, depth):
for (k, v) in json_data.items():
if(type(v) != str):
getValueAndDepthIfValueIsString(v,depth+1)
else:
print(depth, v)
getValueAndDepthIfValueIsString(output_json, 0)
どういうことか。というと、sys.setrecursionlimit(100000)を用いる。というのがミソです。pythonではデフォルトでは再帰の上限が1,000回になっているようです。今回のjsonをパース出来ない原因は、標準ライブラリのjsonのパース処理では、この再帰の1,000回の上限に引っかかる。ということでした。では、その再帰の上限を限界を変更すればよいというアプローチです。sys.setrecrusionlimitはシステムレベルの再帰条件を変更することが出来るので、ここで再帰の上限を変更し、標準のパーサーで乗り切る。というアプローチです。しかも、再起の上限を変更しているので、再帰での深さ優先も簡単に実装できているので、かなりシンプルな答えになっています。完全に想定を超えてきました。社長しかこの解法をしていませんでした。
この問題の答えは、
What is real? How do you define 'real'? If you're talking about what you can feel, what you can smell, what you can taste and see, then 'real' is simply electrical signals interpreted by your brain.
これは映画マトリックス(初代)の一節です。
リアルとは何か？「現実」をどう定義するのでしょうか？もし、あなたが感じるもの、嗅ぐもの、味わうもの、見るものについて話しているなら、「リアル」は単にあなたの脳によって解釈される電気信号です。
たまたまこの問題を公開したあたりにマトリックスの映画が公開されたりしてビックリしました。(公開を知らずに問題を作っていた)
STYLYからの挑戦状 第3弾
前回の記事はアドベントカレンダーということもあって目に留まり、「おもしろい」と思って、Vol 2.に応募していただいた方もいらっしゃいました。非常にうれしかったです。
今回、問題を振り返ってみると、少し難易度が低めだったかな？と思いました。それも一因かもしれませんが、前より応募も多かったです。
しかし！サーバーサイドエンジニアの応募が少ない！
という問題があります。私は、サーバーサイドエンジニアだし、応募に来て欲しいのに！！
というわけで、第3弾を公開しました。
STYLYからの挑戦状 Vol.3 サーバーサイド長からの奇問
前回の難易度が低かったのもあり、今回は高難易度の問題にしています。
あまりにも高難易度だと思うので、この難易度設定は後にも先にもこれっきりかもしれないです。
是非、腕に自信のある方は解いてご応募していただければ嬉しいです。
サーバサイド！！とは言っていますが、Unityエンジニアもフロントエンドエンジニアも募集しているので、ぜひご応募ください。
ご応募お待ちしております！！