採用試験「STYLYからの挑戦状 Vol.3 サーバーサイド長からの奇問」の解説

前書き

先日、「STYLYからの挑戦状 Vol.3 サーバーサイド長からの奇問」という企画を公開させていただきました。

これは2問正解するとPsychic VR Labの採用試験の書類選考をスキップできる。というものでした。

過去の記事はこちら

• 採用試験「STYLYからの挑戦状　Vol.2」の解説
• 採用試験「STYLYからの挑戦状」の解説

前回の解説記事で「過去最高難易度」という文言をつけたため、今回は応募が少ないだろうと予測をしていましたが、多くの方にご応募いただきました。ありがとうございます。
このVol.3は、先月4月10日をもって募集を締め切ったので、前回同様、問題の解説をしたいと思います。

問１　ケンタウロスよ星降らせ

以下の3つの暗号を解いてください。
3つの暗号は全て同じ置換ルールです。
大文字のアルファベットと、小文字のアルファベットは同じ置換のルールに基づいて置換されており、空白や記号については、暗号化されていません。
また、考え方についても記述してください。

暗号文：
Nji rlwxk tdufh buy slzcq umid nji ageo vup.
Xueo alzzuy pwmiq qzgdn qrlwv fju gqkq bud sut cih.
Cgxk zo tuy fwnj bwmi vueih awrlud slpq.

答えは、

The quick brown fox jumps over the lazy dog.
Cozy lummox gives smart squid who asks for job pen.
Pack my box with five dozen liquor jugs.

答えから言うとプログラミングで解くような問題ではない。

というヒドイ問題です。
置換ルールがランダムであり、文章が短いです。そのため、ナイーブに試すと26!パターンを試す必要があり、あまり現実的ではありません。
このような換字式暗号を解読する際には頻度解析がよく用いられます。一般的な英文であれば、EやTの頻度が高いことで知られています。しかし、この文章では、そのような傾向にない。むしろ、一様分布に近い分布になっています。
答えから言うと、この文章は全てパングラムになっています。パングラムとは全てのアルファベットを使った文章のことで、その有名なパングラムをWikipediaから拝借したものになっています。
したがって、文字の出現頻度から一様分布に近い。ということから、パングラムを類推し、既存のパングラムに当てはめる。という解法になります。
また、題名の「ケンタウロスよ星降らせ」というところに意味があります。竹本健治作のミステリである「涙香迷宮」の一節に

ケンタウロスよ　星降らせ
琴座のベガも　笑み送れ
天ぞ指にて　螺子廻る
夜話を紡ぎぬ　營爲なり

というパングラムがあるそうです。この題名はその最初の文を取ってきたもので、暗にパングラムであることを示す題名となっています。参考

この問題はほぼすべての応募者は途中でパングラムだと気付いて解答を送ってきました。しかし、1人だけ例外が居ました。社長です。
Substitution Breakerという換字式暗号を解くためだけのライブラリが存在するらしく、こいつを使ってプログラムでパワープレイで解いてきました。なんでやねん。

!pip3 install subbreaker
import subbreaker
ciphertext = """Nji rlwxk tdufh buy slzcq umid nji ageo vup.
Xueo alzzuy pwmiq qzgdn qrlwv fju gqkq bud sut cih.
Cgxk zo tuy fwnj bwmi vueih awrlud slpq."""

!wget "https://gitlab.com/guballa/SubstitutionBreaker/-/raw/master/subbreaker/quadgram/EN.json" -O "EN.json"
with open("EN.json") as fh:
  breaker = subbreaker.Breaker(fh)
result = breaker.break_cipher(ciphertext)
print("復号化した文字列は")
print(result.plaintext)

問２　覆面算

覆面算（ふくめんざん）は、0から9の数字がそれぞれに対応する別の記号に置き換えられた計算式を与えられ、どの記号が何の数字に対応しているかを推理し、完全な計算式を導き出すパズルである。

引用：https://ja.wikipedia.org/wiki/%E8%A6%86%E9%9D%A2%E7%AE%97

仮に、覆面算を

AB*CDE=FGHIJ

としたとき、

54*297=16038

は覆面算を満たす解の1つです。ここで、以下の条件の覆面算の内、計算結果が最大となる解を求めて下さい。また、導出に使ったプログラムを提出してください。

覆面算は2項の掛け算(x * y = z)である。
0～9の全ての数字を1度だけ利用する。
54*297=16038は、条件を満たす例の1つです。

これはもう本当に解くだけの問題です。
問題のために作ったプログラムはこちら。

import itertools
from tqdm import tqdm

numbers = [0,1,2,3,4,5,6,7,8,9]

for f in tqdm(list(itertools.product([0,1,2], repeat=10))):
    p1 = list(a for a,b in zip(numbers,f) if b==0)
    p2 = list(a for a,b in zip(numbers,f) if b==1)
    p3 = list(a for a,b in zip(numbers,f) if b==2)

    if len(p1)==0 or len(p2)==0 or len(p3)==0:
        continue

    if len(p1) > len(p2):
        continue

    if len(p2) > len(p3):
        continue

    for c1 in itertools.permutations(p1):
        for c2 in itertools.permutations(p2):
            for c3 in itertools.permutations(p3):
                if c1[-1]==0 or c2[-1]==0 or c3[-1]==0:
                    continue
                v1 = sum(a*(10**i) for i,a in enumerate(c1))
                v2 = sum(a*(10**i) for i,a in enumerate(c2))
                v3 = sum(a*(10**i) for i,a in enumerate(c3))
                
                #if(v1+v2==v3 and v1 < v2):
                    #print(f"{v1}+{v2}={v3}")
                    #exit(1)
                if(v1*v2==v3 and v1 < v2):
                    print(f"{v1}*{v2}={v3}")
                    #exit(1)

プログラムとしては、それほど難しくなく、0～9の数字に0,1,2の数字を割り振ります。

• 0に割り振られた数字を左辺第1項を構成する数字
• 1に割り振られた数字を左辺第2項を構成する数字
• 2に割り振られた数字を右辺を構成する数字

として分割します。その後、それぞれの項を構成する数字で順列を作り、全ての組み合わせを試し、a*b=cを満たす数式を全探索する。というとても素直な実装になっています。
数字の並びのみを考えると、10!(=3,628,800)通りなので、探索の数としては大きいですが、実際に組んでみると割と全探索っぽいコードでも計算時間的に何とかなったので出題しました。
この問題はpermutationsなどの順列を作る機能が弱い言語であると、解きにくい問題ではあります。誰か再帰で解いてくるかな？と期待したんですが、誰もいませんでした。

実は、この問題はミスリードを誘っており、

仮に、覆面算を

AB*CDE=FGHIJ

という表記をすることで、答えが左辺第1項が2桁、左辺第2項が3桁である。ように見せかけています。したがって、ここに引っかかって、2桁*3桁=5桁で解を求める人が多数いました。問題では、

覆面算は2項の掛け算(x * y = z)である。
0～9の全ての数字を1度だけ利用する。

としか書いていないので、1桁*4桁=5桁でも構わないです。したがって、実際の答えは、

7*9403=65821

となっています。

問３　バイナリが本体

答えは、

1. A
2. D
3. B
4. C

です。どのように解くか。というと、javascriptのコードなので、大体ASCIIコードで書かれています。ASCIIコードは7bitで表現されます。そのため、必ず最上位bitが必ず0になるため、最大で127の輝度しかありません。そのため、全体が暗くなります。したがって、Aだと分かります。
bmpはファイルのフォーマット上、無圧縮です。そのため、ほぼRGBのデータが並び、元の画像に含まれる模様が一画像に現れます。そのため、Dがbmpであることが分かります。
pngはファイルはバイナリのフォーマットとして圧縮されているため、全体のランダム性が高い状態になります。そのため、全体が一定のノイズのような画像になるため、Bがpngであることが分かります。
VRMのアバターデータはメタデータとして最初の方はjsonが含まれているため、Aのように暗くなります。また、バイナリのフォーマットとしてテクスチャ―などpngのデータを含むため、途中からpngのような見た目になります。したがって、このように複数の種類が複合したデータということからCがVRMデータだと分かります。

これは1.のjavascriptがASCIIだから全体が暗くなりそう。3.のpngは圧縮されているから全体が(相対的に)明るくランダムになっていそう。4.のVRMアバターはjsonとの複合データになりそう。という3つの推論を合わせて、1がA,3がB,4がCが決まって、残りはDは2かな。というのが模範解答でした。

この問題は「とっかかりが無く難しいかな？」と思ってはいたのですが、逆に「バイナリデータから画像化するプログラムを書けばなんとなくわかる」という意味では、実は2番より難易度は低い問題だったんじゃないか。と公開した後に思いました。実際に画像化するプログラムを作った方も2,3名いました。

元ネタは目grep入門というスライドがあり、色々なバイナリデータを画像化し、そこからどのようなデータかを類推できる人が居るらしい。というところから着想しました。

こういう「STYLYからの挑戦状」は私が業務時間中にふらっと思いついて、社内のslackに書き込むんですが、CTOの@afjkさんが5分で回答をしてきて超絶ビックリしました。

問４　なぞのプログラム

以下のプログラムをビルドし、実行してください。
このプログラムが何のハードウェアで動くプログラムで、どのように動かしたのかを記述してください。また、スクリーンショットを添付して下さい。

https://drive.google.com/file/d/1XkvxnqVJhlOFhi3qk4--QPlhdvoWZgg5/view?usp=sharing

割と問題作です。答えはこんな感じです。

動作するハードウェアはファミコンです。VirtualNESで動作確認できます。
やろうとするとめっちゃ簡単なんですが、資料が少ないです。

$ docker run --rm -it -v `pwd`:`pwd` bensuperpc/cc65 bash
# cl65 -t nes styly.s

cc65というモトローラ社の6502のCPU用のクロスコンパイラが存在しており、それのDockerImageが公開しているので、ここにたどり着けるとそこまで難しくはないです。
アセンブリのコードに

	.fopt		compiler,"cc65 v 2.19 - Git 1d36f255e"
	.setcpu		"6502"

とあるので、これで大体分かるようになっています。あとは気合で英語の文章などからあたりをつけて見つけることが出来るか。という感じの問題です。
この採用試験を作っているときに、「ファミコン用のプログラム作って出してぇなぁ・・・」という野望があったので、割と満足です。ただやってみた結果、それほど情報が整っているわけではなく、門外漢がサクッと出来る。って程ではなかったです。やはり古いCPUなのでアセンブラが前提で、C言語で書いてもやれる範囲が狭く、速度も全然でませんでした。

ゲームのプログラムはこちら

#include <stdlib.h>
#include <conio.h>
#include <tgi.h>
#include <nes.h>
#include <joystick.h>
 
/*
width 63
height 55
*/
 
static const unsigned char Palette[8] = { COLOR_BLACK, COLOR_BLACK };
 
int main (void)
{
    int x=0;
    int y=0;
    int w=30;
    int h=26;
    int i=0;
    int j=0;
    int offsetX = 4;
    int offsetY = 10;
 
    int MaxX;
    int MaxY;
 
 
    int width=3;
    int left=2;
    int right=61;
    int head=11;
    int tail=40;
 
    tgi_install (tgi_static_stddrv);
 
    tgi_init();
    tgi_clear();
 
    tgi_setpalette (Palette);
   
    MaxX = tgi_getmaxx();
    MaxY = tgi_getmaxy();
 
    left = width;
    right = MaxX - width;
    tail = MaxY - head;
 
    tgi_setcolor(COLOR_WHITE);
 
    for(i=0;i<=MaxY;i++){
        for(j=0;j<=MaxX;j++){
            if((j+i%2)%2!=0){
                if(j<left || j >right){
                    tgi_setcolor (1);
                } else if(i < head || i > tail) {
                    tgi_setcolor (1);
                }
            } else{
                tgi_setcolor (0);
            }
            tgi_setpixel (j,i);
        }
        waitvsync();
    }
   
    tgi_done();
    //tgi_unload();
 
    waitvsync();
   
    //bgcolor(1);
    textcolor(2);
    //clrscr();
 
    gotoxy(7,      offsetY+1);       cprintf("STYLY CI COMPASS");
    gotoxy(offsetX,offsetY+3); cprintf("* Hack The Process.");
    gotoxy(offsetX,offsetY+4); cprintf("* Never Be Perfect.");
    gotoxy(offsetX,offsetY+5); cprintf("* Expand Your World.");
    gotoxy(offsetX,offsetY+6); cprintf("* Take Every Chance.");
    gotoxy(offsetX,offsetY+7); cprintf("* Respect and Commitment.");
    //gotoxy(offsetX,8); cprintf("%d",MaxX);
    //gotoxy(offsetX,9); cprintf("%d",MaxY);
 
    while(1)
    {
    }
    return 0;
}

画像を見てもらえば分かりますが、市松模様の右下が欠けています。どうも私には直せなかったので、まぁいっか。サンプルだし。と思ってそのままで出しました。
　なんでファミコンのゲームを題材に？と思われるかもしれませんが、多くは私の趣味ですあえて理由付けをすると、XRの業界というのは日本語化される情報が圧倒的に少なく、環境構築が一番ハードルであることもあります。そのため、英語の情報しかない。もしくは、丁寧に整備されているわけではない情報から、環境を構築するような、問題解決の突破力があるか。を問う問題でした。

STYLYからの挑戦状　第4弾 & Psychic VR Lab 新卒採用

というわけで、

STYLYからの挑戦状　第4弾 なぜ採用問題に奇問を入れるのか

を公開しました。前回、あれほど難しい。と書いたのに、来年から大学生というぐらいの若い人が解答して合格をしていたので、私はビビり散らしていました。私が学生だった頃は絶対解けなかった。したがって、問題が難しいか。簡単か。は正直わからなくなってしまいました。
STYLYからの挑戦状はコンセプトとして「検索しても直接的な解法が分からない」内容を目指しています。例えば、FizzBuzzは割と使い古された問題だと思います。そうではなく、教科書の隅にある割とコアでニッチなコンピュータの知識で解ける感じにしています。今回も、そんな感じのニッチな奇問を用意しました(たぶん)
今回は、Vol.4だけでなく

Psychic VR Lab 2023年新卒採用問題 Tell Your Metaverse ～あなたの想像するメタバースのミライ～

という新卒採用問題も公開しております。新卒採用問題はSTYLYからの挑戦状のような問題解決能力を問うというよりかは、実際に業務に必要なUnityの開発能力を計る問題になっております。こちらもコンセプト設計をお手伝いしています。新卒採用の応募は5/8までになっているので、2023新卒の興味のある方はぜひご応募よろしくお願いします。