diff options
Diffstat (limited to 'vhosts/blog/content/posts/2022-04-09')
| -rw-r--r-- | vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.dj | 489 | ||||
| -rw-r--r-- | vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc | 560 |
2 files changed, 489 insertions, 560 deletions
diff --git a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.dj b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.dj new file mode 100644 index 00000000..e0fe0279 --- /dev/null +++ b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.dj @@ -0,0 +1,489 @@ +--- +[article] +uuid = "f4985d54-0907-4449-8101-0fcd382f9e02" +title = "PHPerKaigi 2022 トークン問題の解説" +description = "PHPerKaigi 2022 で私が作成した PHPer チャレンジ問題を解説する。" +tags = [ + "conference", + "php", + "phperkaigi", +] + +[[article.revisions]] +date = "2022-04-09" +remark = "公開" + +[[article.revisions]] +date = "2022-04-16" +remark = "2問目、3問目の解説を追加、1問目に加筆" +--- +{#intro} +# はじめに + +本日開始された [PHPerKaigi 2022](https://phperkaigi.jp/2022/) の PHPer +チャレンジにおいて、弊社 +[デジタルサーカス株式会社](https://www.dgcircus.com/) の問題を +3問作成した。この記事では、これらの問題の解説をおこなう。 + +リポジトリはこちら: https://github.com/nsfisis/PHPerKaigi2022-tokens + +{#q1-brainfuck} +# 第1問 brainf_ck.php + +ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。 + +```php +<?php + +declare(strict_types=0O1); + +namespace Dgcircus\PHPerKaigi\Y2022; + +/** + * @todo + * Run this program to acquire a PHPer token. + */ + +https://creativecommons.org/publicdomain/zero/1.0/ + +\error_reporting(~+!'We are hiring!'); + +$z = fn($f) => (fn($x) => $f(fn(...$xs) => $x($x)(...$xs)))(fn($x) => $f(fn(...$xs) => $x($x)(...$xs))); +$id = \spl_object_id(...); +$put = fn($c) => \printf('%c', $c); +$mm = fn($p, $n) => new \ArrayObject(\array_fill(+!![], $n, $p)); + +$👉 = fn($m, $p, $b, $e, $mp, $pc) => [++$mp, ++$pc]; +$👈 = fn($m, $p, $b, $e, $mp, $pc) => [--$mp, ++$pc]; +$👍 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, ++$m[$mp]]; +$👎 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, --$m[$mp]]; +$📝 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, $put($m[$mp])]; +$🤡 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) { + +!![] => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) { + $b => $loop(++$pc, ++$n), + $e => $n === +!![] ? ++$pc : $loop(++$pc, --$n), + default => $loop(++$pc, $n), + })($pc, -![])], + default => [$mp, ++$pc], +}; +$🎪 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) { + +!![] => [$mp, ++$pc], + default => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) { + $e => $loop(--$pc, ++$n), + $b => $n === +!![] ? $pc+![] : $loop(--$pc, --$n), + default => $loop(--$pc, $n), + })($pc, -![])], +}; +$🐘 = fn($p) => $z(fn($loop) => fn($m, $p, $b, $e, $mp, $pc) => + isset($p[$pc]) && $loop($m, $p, $b, $e, ...($p[$pc]($m, $p, $b, $e, $mp, $pc))) +)($mm(+!![], +(![].![])), $p, $id($🤡), $id($🎪), +!![], +!![]); + +$🐘([ + $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, + $🤡, + $👉, $👍, $👍, $👍, + $👉, $👍, $👍, $👍, $👍, $👍, + $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, + $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, + $👈, $👈, $👈, $👈, $👎, + $🎪, + $👉, $👍, $👍, $👍, $👍, $👍, $📝, + $👎, $👎, $📝, + $👉, $👎, $👎, $👎, $📝, + $👉, $👎, $👎, $👎, $📝, + $👎, $👎, $📝, + $👎, $📝, + $👈, $📝, + $👉, $👉, $👎, $👎, $📝, + $👍, $👍, $👍, $👍, $👍, $👍, $👍, $📝, + $👈, $👎, $👎, $👎, $👎, $📝, + $👈, $📝, + $👉, $👍, $👍, $📝, + $👉, $👎, $📝, + $👈, $📝, +]); +``` + +この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。 + +{#commentary} +## 解説 + +{#emoji} +### 絵文字 + +まず目につくのは大量の絵文字だろう。 PHP +は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。 + +{#brainfuck} +### プログラム全体 + +Brainf\*ck のインタプリタとプログラムになっている。 Brainf\*ck +とは、難解プログラミング言語のひとつであり、ここで説明するよりも +Wikipedia の該当ページを読んだ方がよい。 + +https://ja.wikipedia.org/wiki/Brainfuck + +なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。 + +``` ++ + + + + + + + + + +[ + > + + + + > + + + + + + > + + + + + + + + + + + + + > + + + + + + + + + + + < < < < - +] +> + + + + + . +- - . +> - - - . +> - - - . +- - . +- . +< . +> > - - . ++ + + + + + + . +< - - - - . +< . +> + + . +> - . +< . +``` + +実行結果はこちら: https://ideone.com/22VWmb + +それぞれの絵文字で表された関数が、各命令に対応している。 + +* `$👉`: `>` +* `$👈`: `<` +* `$👍`: `+` +* `$👎`: `-` +* `$📝`: `.` +* `$🤡`: `[` +* `$🎪`: `]` + +`,` (入力) に対応する関数はない +(このプログラムでは使わないので用意していない)。 + +なお、`$🐘` はいわゆる main 関数であり、プログラムの実行部分である。 + +{#emoji-selection} +### 絵文字の選択 + +おおよそ意味に合致するよう選んでいるが、`$🤡` と `$🎪` +は弊社デジタルサーカスにちなんでいる。 また、`$🐘` は PHP +のマスコットの象に由来する。 + +{#strict-types} +### strict_types + +`declare` 文の `strict_types` に指定できるのは、`0` か `1` +の数値リテラルだが、 `0x0` や `0b1` のような値も受け付ける。 今回は、PHP +8.1 から追加された、`0O` または `0o` から始まる八進数リテラルを使った。 + +{#url} +### URL + +ソースコードのライセンスを示したこの部分だが、 + +```php +https://creativecommons.org/publicdomain/zero/1.0/ +``` + +完全に合法な PHP のコードである。 `https:` 部分はラベル、`//` +以降は行コメントになっている。 + +{#numbers} +### リテラルなしで数値を生成する + +ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。 +PHP では、型変換を利用することで任意の整数を作り出すことができる。 + +```php +assert(0 === +!![]); +assert(1 === +![]); +assert(2 === ![]+![]); +assert(3 === ![]+![]+![]); +assert(10 === +(![].+!![])); +``` + +`[]` に `!` を適用すると `true` が返ってくる。それに `+` +を適用すると、`bool` から `int` ヘの型変換が走り、`1` が生成される。`10` +はさらにトリッキーだ。まず `1` と `0` を作り、`.` で文字列として結合する +(`'10'`)。これに `+` を適用すると、`string` から `int` +への型変換が走り、`10` が生まれる (コード量に頓着しないなら、`1` を 10 +個足し合わせてももちろん 10 が作れる)。 + +また、`error_reporting` に指定しているのは `-1` である。 これは、`!` +によって文字列を `false` にし、`+` によって `false` を `0` +にし、さらにビット反転して `-1` にしている。 + +{#conditionals} +### `if` 文なしで条件分岐 + +三項演算子ないし `match` 式を使うことで、`if` +を一切書かずに条件分岐ができる。 また、`&&` / `||` も使えることがある。 +遅延評価が不要なケースでは、`[$t, $f][$cond]` +のような形で分岐することもできる。 + +{#loops} +### `while`、`for` 文なしでループ + +不動点コンビネータを使って無名再帰する +(詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に +Z コンビネータとして知られるものを使った (`$z`)。 + +実際のところ、`$🤡` や `$🎪`、`$🐘` は、一度 Scheme (Lisp の一種) +で書いてから PHP に翻訳する形で記述した。 + +なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは) +ので、 あまりに長い brainf*ck +プログラムを書くとスタックオーバーフローする。 + +{#q2-riddle} +# 第2問 riddle.php + +ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。 + +```php +<?php + +/********************************************************* + * This program displays a PHPer token. * + * Guess 'N'. * + * * + * Hints: * + * - N itself has no special meaning, e.g., 42, 8128, * + * it is selected at random. * + * - Each element of $token represents a single letter. * + * - One letter consists of 5x5 cells. * + * - Remember, the output is a complete PHPer token. * + * * + * License: * + * https://creativecommons.org/publicdomain/zero/1.0/ * + *********************************************************/ +const N = 0 /* Change it to your answer. */; +assert(0 <= N && N <= 0b11111_11111_11111_11111_11111); + +$token = [ + 0x14B499C, + 0x0BE34CC, 0x01C9C69, + 0x0ECA069, 0x01C2449, 0x0FDB166, 0x01C9C69, + 0x01C1C66, 0x0FC1C47, 0x01C1C66, + 0x10C5858, 0x1E4E3B8, 0x1A2F2F8, +]; +foreach ($token as $x) { + $x = $x ^ N; + + $x = sprintf('%025b', $x); + $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); + $x = implode("\n", str_split($x, length: 5)); + echo "{$x}\n\n"; +} +``` + +さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。 +トークンを得るためには、ソースコードを読み、定数 `N` +を特定する必要がある。 + +ここでは、私の想定解を解説する。 + +{#code-reading} +## 読解 + +まずはソースコードを読んでいく。 + +```php +$token = [ + // 略 +]; +``` + +数値からなる `$token` があり、各要素をループしている。 + +```php +$x = $x ^ N; +``` + +まずは排他的論理和 (xor) を取り、 + +```php +$x = sprintf('%025b', $x); +``` + +二進数に変換して、 + +```php +$x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); +``` + +0 を空白に、1 を `#` にし、 + +```php +$x = implode("\n", str_split($x, length: 5)); +``` + +5文字ごとに区切ったあと、改行で結合している。 + +{#hint} +## ヒント + +次に、ソースコードに書いてあるヒントを読んでいく。 + +* `N` それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている +* `$token` の各要素は、1文字を表す +* 1文字は 5x5 のセルからなる +* 出力されるのは、完全な PHPer トークンである + +ここで、PHPer トークンは必ず `#` 記号から始まることを思いだすと、 +`$token` の最初の数字 `0x14B499C` は、変換の結果 `#` +になるのではないかと予想される (なお、このことは、リポジトリの README +ファイルに追加ヒントとして書かれている)。 + +{#solve} +## 解く + +ここまでわかれば、あと一歩で解ける。すなわち、`0x14B499C` が `#` +に変換されるような `N` を見つければよい。 + +`N` は高々 + +```php +assert(0 <= N && N <= 0b11111_11111_11111_11111_11111); +``` + +なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。 + +```php +<?php + +$x = 0x14B499C; + +$x = $x ^ N; + +$x = sprintf('%025b', $x); +$x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); +$x = implode("\n", str_split($x, length: 5)); + +assert($x === +" # # \n" . +"#####\n" . +" # # \n" . +"#####\n" . +" # # "); +``` + +この一連の変換に対する逆変換を考えると、次のようになる。 + +```php +<?php + +$x = +" # # \n" . +"#####\n" . +" # # \n" . +"#####\n" . +" # # "; + +$x = implode('', explode("\n", $x)); +$x = str_replace(search: [' ', '#'], replace: ['0', '1'], subject: $x); +$x = bindec($x); + +$n = $x ^ 0x14B499C; + +echo "N = $n\n"; +``` + +これを実行すると、`N` が得られる。 + +{#q3-toquine} +# 第3問 toquine.php + +ソースコードはこちら。 + +```php +<?php + +// License: https://creativecommons.org/publicdomain/zero/1.0/ +// This is a quine-like program to generate a PHPer token. +// Execute it like this: php toquine.php | php | php | php | ... + +$s = <<<'Q' +<?cuc +// Yvprafr: uggcf://perngvirpbzzbaf.bet/choyvpqbznva/mreb/1.0/ +// Guvf vf n dhvar-yvxr cebtenz gb trarengr n CUCre gbxra. +// Rkrphgr vg yvxr guvf: cuc gbdhvar.cuc | cuc | cuc | cuc | ... +%f$f = %f; +$f = fge_ebg13($f); $kf = [ +%f, +]; +$g = ahyy.snyfr; sbe ($v = 0; $v <= vagqvi(__YVAR__-035,6); ++$v) vs (!vffrg($kf[$v])) oernx; ryfr +$g .= vzcybqr("\a", fge_fcyvg(fge_ercynpr(['0','1'], [' ','##'], fcevags(pue(37) . '025o', $kf[$v])), 012)) . "\a\a"; +$jf = neenl_znc(sa($j) => vzcybqr(', ', $j), neenl_puhax(neenl_znc(sa($k) => fcevags('0k' . pue(37) . '07K', $k), $kf), 10)); +cevags($f, $g, fge_ebg13("<<<'Q'\a{$f}\aQ"), vzcybqr(",\a", $jf)); +Q; +$s = str_rot13($s); $xs = [ +0x0AFABEA, 0x1F294A7, 0x1F2109F, 0x1F294A7, 0x0002800, 0x1F2109F, 0x0117041, 0x1F294A7, 0x1FAD6B5, 0x1F295B7, +0x010FC21, 0x1FAD6B5, 0x1151151, 0x010FC21, 0x1F294A7, 0x1F295B7, 0x1FAD6B5, 0x1F294A7, 0x1F295B7, 0x1F8C63F, +0x1F8C631, 0x1FAD6B5, 0x17AD6BD, 0x17AD6BD, 0x1F8C63F, 0x1F295B7, +]; +$t = null.false; for ($i = 0; $i <= intdiv(__LINE__-035,6); ++$i) if (!isset($xs[$i])) break; else +$t .= implode("\n", str_split(str_replace(['0','1'], [' ','##'], sprintf(chr(37) . '025b', $xs[$i])), 012)) . "\n\n"; +$ws = array_map(fn($w) => implode(', ', $w), array_chunk(array_map(fn($x) => sprintf('0x' . chr(37) . '07X', $x), $xs), 10)); +printf($s, $t, str_rot13("<<<'D'\n{$s}\nD"), implode(",\n", $ws)); +``` + +コメントにもあるとおり、次のようにして実行すれば答えがでてくる。 + +```shell-session +$ php toquine.php | php | php | php | ... +``` + +実際にはもう少しパイプで繋げなければならない。 + +{#commentary} +## 解説 + +{#quine} +### プログラム全体 + +コメントにもあるとおり、これは quine (風) のプログラムになっている。 +Quine +とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。 + +このプログラムは、実行すると自身とほとんど同じプログラムを出力する。 +異なるのはトークンになっている部分のみである。 + +{#tokens} +### トークン + +`$xs` がトークンに対応している。変換のロジックは `riddle.php` +とほぼ同じなので省略する。 + +{#states} +### 状態保持 + +トークンの何文字目まで出力したかを、ソースコードを変えずに (quine +なので) 覚えておく必要がある。 +このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、`__LINE__` +から情報を取得している。 + +{#rot-13} +### ROT 13 + +Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。 +これがあまり美しくないので、`toquine.php` では、ROT 13 +変換を使って難読化した。 + +それにしてもなぜこんなものが標準ライブラリに……。 + +{#outro} +# おわりに + +解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。 + +今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、 +来年は 5問、より面白い問題を持っていきます。 + +実はもう作りはじめているので、どうか来年もありますように……。 diff --git a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc deleted file mode 100644 index c0540482..00000000 --- a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc +++ /dev/null @@ -1,560 +0,0 @@ ---- -[article] -uuid = "f4985d54-0907-4449-8101-0fcd382f9e02" -title = "PHPerKaigi 2022 トークン問題の解説" -description = "PHPerKaigi 2022 で私が作成した PHPer チャレンジ問題を解説する。" -tags = [ - "conference", - "php", - "phperkaigi", -] - -[[article.revisions]] -date = "2022-04-09" -remark = "公開" - -[[article.revisions]] -date = "2022-04-16" -remark = "2問目、3問目の解説を追加、1問目に加筆" ---- -<article> - <section id="intro"> - <h>はじめに</h> - <p> - 本日開始された <a href="https://phperkaigi.jp/2022/">PHPerKaigi 2022</a> の PHPer - チャレンジにおいて、弊社 - <a href="https://www.dgcircus.com/">デジタルサーカス株式会社</a> の問題を - 3問作成した。この記事では、これらの問題の解説をおこなう。 - </p> - <p> - リポジトリはこちら: https://github.com/nsfisis/PHPerKaigi2022-tokens - </p> - </section> - <section id="q1-brainfuck"> - <h>第1問 brainf_ck.php</h> - <p> - ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。 - </p> - <codeblock language="php"> - <![CDATA[ - <?php - - declare(strict_types=0O1); - - namespace Dgcircus\PHPerKaigi\Y2022; - - /** - * @todo - * Run this program to acquire a PHPer token. - */ - - https://creativecommons.org/publicdomain/zero/1.0/ - - \error_reporting(~+!'We are hiring!'); - - $z = fn($f) => (fn($x) => $f(fn(...$xs) => $x($x)(...$xs)))(fn($x) => $f(fn(...$xs) => $x($x)(...$xs))); - $id = \spl_object_id(...); - $put = fn($c) => \printf('%c', $c); - $mm = fn($p, $n) => new \ArrayObject(\array_fill(+!![], $n, $p)); - - $👉 = fn($m, $p, $b, $e, $mp, $pc) => [++$mp, ++$pc]; - $👈 = fn($m, $p, $b, $e, $mp, $pc) => [--$mp, ++$pc]; - $👍 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, ++$m[$mp]]; - $👎 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, --$m[$mp]]; - $📝 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, $put($m[$mp])]; - $🤡 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) { - +!![] => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) { - $b => $loop(++$pc, ++$n), - $e => $n === +!![] ? ++$pc : $loop(++$pc, --$n), - default => $loop(++$pc, $n), - })($pc, -![])], - default => [$mp, ++$pc], - }; - $🎪 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) { - +!![] => [$mp, ++$pc], - default => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) { - $e => $loop(--$pc, ++$n), - $b => $n === +!![] ? $pc+![] : $loop(--$pc, --$n), - default => $loop(--$pc, $n), - })($pc, -![])], - }; - $🐘 = fn($p) => $z(fn($loop) => fn($m, $p, $b, $e, $mp, $pc) => - isset($p[$pc]) && $loop($m, $p, $b, $e, ...($p[$pc]($m, $p, $b, $e, $mp, $pc))) - )($mm(+!![], +(![].![])), $p, $id($🤡), $id($🎪), +!![], +!![]); - - $🐘([ - $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, - $🤡, - $👉, $👍, $👍, $👍, - $👉, $👍, $👍, $👍, $👍, $👍, - $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, - $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, - $👈, $👈, $👈, $👈, $👎, - $🎪, - $👉, $👍, $👍, $👍, $👍, $👍, $📝, - $👎, $👎, $📝, - $👉, $👎, $👎, $👎, $📝, - $👉, $👎, $👎, $👎, $📝, - $👎, $👎, $📝, - $👎, $📝, - $👈, $📝, - $👉, $👉, $👎, $👎, $📝, - $👍, $👍, $👍, $👍, $👍, $👍, $👍, $📝, - $👈, $👎, $👎, $👎, $👎, $📝, - $👈, $📝, - $👉, $👍, $👍, $📝, - $👉, $👎, $📝, - $👈, $📝, - ]); - ]]> - </codeblock> - <p> - この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。 - </p> - <section id="commentary"> - <h>解説</h> - <section id="emoji"> - <h>絵文字</h> - <p> - まず目につくのは大量の絵文字だろう。 PHP - は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。 - </p> - </section> - <section id="brainfuck"> - <h>プログラム全体</h> - <p> - Brainf*ck のインタプリタとプログラムになっている。 Brainf*ck - とは、難解プログラミング言語のひとつであり、ここで説明するよりも - Wikipedia の該当ページを読んだ方がよい。 - </p> - <p> - https://ja.wikipedia.org/wiki/Brainfuck - </p> - <p> - なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。 - </p> - <codeblock> - <![CDATA[ - + + + + + + + + + + - [ - > + + + - > + + + + + - > + + + + + + + + + + + + - > + + + + + + + + + + - < < < < - - ] - > + + + + + . - - - . - > - - - . - > - - - . - - - . - - . - < . - > > - - . - + + + + + + + . - < - - - - . - < . - > + + . - > - . - < . - ]]> - </codeblock> - <p> - 実行結果はこちら: https://ideone.com/22VWmb - </p> - <p> - それぞれの絵文字で表された関数が、各命令に対応している。 - </p> - <ul> - <li><code>$👉</code>: <code>></code></li> - <li><code>$👈</code>: <code><</code></li> - <li><code>$👍</code>: <code>+</code></li> - <li><code>$👎</code>: <code>-</code></li> - <li><code>$📝</code>: <code>.</code></li> - <li><code>$🤡</code>: <code>[</code></li> - <li><code>$🎪</code>: <code>]</code></li> - </ul> - <p> - <code>,</code> (入力) に対応する関数はない - (このプログラムでは使わないので用意していない)。 - </p> - <p> - なお、<code>$🐘</code> はいわゆる main 関数であり、プログラムの実行部分である。 - </p> - </section> - <section id="emoji-selection"> - <h>絵文字の選択</h> - <p> - おおよそ意味に合致するよう選んでいるが、<code>$🤡</code> と <code>$🎪</code> - は弊社デジタルサーカスにちなんでいる。 また、<code>$🐘</code> は PHP - のマスコットの象に由来する。 - </p> - </section> - <section id="strict-types"> - <h>strict_types</h> - <p> - <code>declare</code> 文の <code>strict_types</code> に指定できるのは、<code>0</code> か <code>1</code> - の数値リテラルだが、 <code>0x0</code> や <code>0b1</code> のような値も受け付ける。 今回は、PHP - 8.1 から追加された、<code>0O</code> または <code>0o</code> から始まる八進数リテラルを使った。 - </p> - </section> - <section id="url"> - <h>URL</h> - <p> - ソースコードのライセンスを示したこの部分だが、 - </p> - <codeblock language="php"> - <![CDATA[ - https://creativecommons.org/publicdomain/zero/1.0/ - ]]> - </codeblock> - <p> - 完全に合法な PHP のコードである。 <code>https:</code> 部分はラベル、<code>//</code> - 以降は行コメントになっている。 - </p> - </section> - <section id="numbers"> - <h>リテラルなしで数値を生成する</h> - <p> - ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。 - PHP では、型変換を利用することで任意の整数を作り出すことができる。 - </p> - <codeblock language="php"> - <![CDATA[ - assert(0 === +!![]); - assert(1 === +![]); - assert(2 === ![]+![]); - assert(3 === ![]+![]+![]); - assert(10 === +(![].+!![])); - ]]> - </codeblock> - <p> - <code>[]</code> に <code>!</code> を適用すると <code>true</code> が返ってくる。それに <code>+</code> - を適用すると、<code>bool</code> から <code>int</code> ヘの型変換が走り、<code>1</code> が生成される。<code>10</code> - はさらにトリッキーだ。まず <code>1</code> と <code>0</code> を作り、<code>.</code> で文字列として結合する - (<code>'10'</code>)。これに <code>+</code> を適用すると、<code>string</code> から <code>int</code> - への型変換が走り、<code>10</code> が生まれる (コード量に頓着しないなら、<code>1</code> を 10 - 個足し合わせてももちろん 10 が作れる)。 - </p> - <p> - また、<code>error_reporting</code> に指定しているのは <code>-1</code> である。 これは、<code>!</code> - によって文字列を <code>false</code> にし、<code>+</code> によって <code>false</code> を <code>0</code> - にし、さらにビット反転して <code>-1</code> にしている。 - </p> - </section> - <section id="conditionals"> - <h><code>if</code> 文なしで条件分岐</h> - <p> - 三項演算子ないし <code>match</code> 式を使うことで、<code>if</code> - を一切書かずに条件分岐ができる。 また、<code>&&</code> / <code>||</code> も使えることがある。 - 遅延評価が不要なケースでは、<code>[$t, $f][$cond]</code> - のような形で分岐することもできる。 - </p> - </section> - <section id="loops"> - <h><code>while</code>、<code>for</code> 文なしでループ</h> - <p> - 不動点コンビネータを使って無名再帰する - (詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に - Z コンビネータとして知られるものを使った (<code>$z</code>)。 - </p> - <p> - 実際のところ、<code>$🤡</code> や <code>$🎪</code>、<code>$🐘</code> は、一度 Scheme (Lisp の一種) - で書いてから PHP に翻訳する形で記述した。 - </p> - <p> - なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは) - ので、 あまりに長い brainf*ck - プログラムを書くとスタックオーバーフローする。 - </p> - </section> - </section> - </section> - <section id="q2-riddle"> - <h>第2問 riddle.php</h> - <p> - ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。 - </p> - <codeblock language="php"> - <![CDATA[ - <?php - - /********************************************************* - * This program displays a PHPer token. * - * Guess 'N'. * - * * - * Hints: * - * - N itself has no special meaning, e.g., 42, 8128, * - * it is selected at random. * - * - Each element of $token represents a single letter. * - * - One letter consists of 5x5 cells. * - * - Remember, the output is a complete PHPer token. * - * * - * License: * - * https://creativecommons.org/publicdomain/zero/1.0/ * - *********************************************************/ - const N = 0 /* Change it to your answer. */; - assert(0 <= N && N <= 0b11111_11111_11111_11111_11111); - - $token = [ - 0x14B499C, - 0x0BE34CC, 0x01C9C69, - 0x0ECA069, 0x01C2449, 0x0FDB166, 0x01C9C69, - 0x01C1C66, 0x0FC1C47, 0x01C1C66, - 0x10C5858, 0x1E4E3B8, 0x1A2F2F8, - ]; - foreach ($token as $x) { - $x = $x ^ N; - - $x = sprintf('%025b', $x); - $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); - $x = implode("\n", str_split($x, length: 5)); - echo "{$x}\n\n"; - } - ]]> - </codeblock> - <p> - さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。 - トークンを得るためには、ソースコードを読み、定数 <code>N</code> - を特定する必要がある。 - </p> - <p> - ここでは、私の想定解を解説する。 - </p> - <section id="code-reading"> - <h>読解</h> - <p> - まずはソースコードを読んでいく。 - </p> - <codeblock language="php"> - <![CDATA[ - $token = [ - // 略 - ]; - ]]> - </codeblock> - <p> - 数値からなる <code>$token</code> があり、各要素をループしている。 - </p> - <codeblock language="php"> - <![CDATA[ - $x = $x ^ N; - ]]> - </codeblock> - <p> - まずは排他的論理和 (xor) を取り、 - </p> - <codeblock language="php"> - <![CDATA[ - $x = sprintf('%025b', $x); - ]]> - </codeblock> - <p> - 二進数に変換して、 - </p> - <codeblock language="php"> - <![CDATA[ - $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); - ]]> - </codeblock> - <p> - 0 を空白に、1 を <code>#</code> にし、 - </p> - <codeblock language="php"> - <![CDATA[ - $x = implode("\n", str_split($x, length: 5)); - ]]> - </codeblock> - <p> - 5文字ごとに区切ったあと、改行で結合している。 - </p> - </section> - <section id="hint"> - <h>ヒント</h> - <p> - 次に、ソースコードに書いてあるヒントを読んでいく。 - </p> - <ul> - <li><code>N</code> それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている</li> - <li><code>$token</code> の各要素は、1文字を表す</li> - <li>1文字は 5x5 のセルからなる</li> - <li>出力されるのは、完全な PHPer トークンである</li> - </ul> - <p> - ここで、PHPer トークンは必ず <code>#</code> 記号から始まることを思いだすと、 - <code>$token</code> の最初の数字 <code>0x14B499C</code> は、変換の結果 <code>#</code> - になるのではないかと予想される (なお、このことは、リポジトリの README - ファイルに追加ヒントとして書かれている)。 - </p> - </section> - <section id="solve"> - <h>解く</h> - <p> - ここまでわかれば、あと一歩で解ける。すなわち、<code>0x14B499C</code> が <code>#</code> - に変換されるような <code>N</code> を見つければよい。 - </p> - <p> - <code>N</code> は高々 - </p> - <codeblock language="php"> - <![CDATA[ - assert(0 <= N && N <= 0b11111_11111_11111_11111_11111); - ]]> - </codeblock> - <p> - なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。 - </p> - <codeblock language="php"> - <![CDATA[ - <?php - - $x = 0x14B499C; - - $x = $x ^ N; - - $x = sprintf('%025b', $x); - $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); - $x = implode("\n", str_split($x, length: 5)); - - assert($x === - " # # \n" . - "#####\n" . - " # # \n" . - "#####\n" . - " # # "); - ]]> - </codeblock> - <p> - この一連の変換に対する逆変換を考えると、次のようになる。 - </p> - <codeblock language="php"> - <![CDATA[ - <?php - - $x = - " # # \n" . - "#####\n" . - " # # \n" . - "#####\n" . - " # # "; - - $x = implode('', explode("\n", $x)); - $x = str_replace(search: [' ', '#'], replace: ['0', '1'], subject: $x); - $x = bindec($x); - - $n = $x ^ 0x14B499C; - - echo "N = $n\n"; - ]]> - </codeblock> - <p> - これを実行すると、<code>N</code> が得られる。 - </p> - </section> - </section> - <section id="q3-toquine"> - <h>第3問 toquine.php</h> - <p> - ソースコードはこちら。 - </p> - <codeblock language="php"> - <![CDATA[ - <?php - - // License: https://creativecommons.org/publicdomain/zero/1.0/ - // This is a quine-like program to generate a PHPer token. - // Execute it like this: php toquine.php | php | php | php | ... - - $s = <<<'Q' - <?cuc - // Yvprafr: uggcf://perngvirpbzzbaf.bet/choyvpqbznva/mreb/1.0/ - // Guvf vf n dhvar-yvxr cebtenz gb trarengr n CUCre gbxra. - // Rkrphgr vg yvxr guvf: cuc gbdhvar.cuc | cuc | cuc | cuc | ... - %f$f = %f; - $f = fge_ebg13($f); $kf = [ - %f, - ]; - $g = ahyy.snyfr; sbe ($v = 0; $v <= vagqvi(__YVAR__-035,6); ++$v) vs (!vffrg($kf[$v])) oernx; ryfr - $g .= vzcybqr("\a", fge_fcyvg(fge_ercynpr(['0','1'], [' ','##'], fcevags(pue(37) . '025o', $kf[$v])), 012)) . "\a\a"; - $jf = neenl_znc(sa($j) => vzcybqr(', ', $j), neenl_puhax(neenl_znc(sa($k) => fcevags('0k' . pue(37) . '07K', $k), $kf), 10)); - cevags($f, $g, fge_ebg13("<<<'Q'\a{$f}\aQ"), vzcybqr(",\a", $jf)); - Q; - $s = str_rot13($s); $xs = [ - 0x0AFABEA, 0x1F294A7, 0x1F2109F, 0x1F294A7, 0x0002800, 0x1F2109F, 0x0117041, 0x1F294A7, 0x1FAD6B5, 0x1F295B7, - 0x010FC21, 0x1FAD6B5, 0x1151151, 0x010FC21, 0x1F294A7, 0x1F295B7, 0x1FAD6B5, 0x1F294A7, 0x1F295B7, 0x1F8C63F, - 0x1F8C631, 0x1FAD6B5, 0x17AD6BD, 0x17AD6BD, 0x1F8C63F, 0x1F295B7, - ]; - $t = null.false; for ($i = 0; $i <= intdiv(__LINE__-035,6); ++$i) if (!isset($xs[$i])) break; else - $t .= implode("\n", str_split(str_replace(['0','1'], [' ','##'], sprintf(chr(37) . '025b', $xs[$i])), 012)) . "\n\n"; - $ws = array_map(fn($w) => implode(', ', $w), array_chunk(array_map(fn($x) => sprintf('0x' . chr(37) . '07X', $x), $xs), 10)); - printf($s, $t, str_rot13("<<<'D'\n{$s}\nD"), implode(",\n", $ws)); - ]]> - </codeblock> - <p> - コメントにもあるとおり、次のようにして実行すれば答えがでてくる。 - </p> - <codeblock language="shell-session"> - <![CDATA[ - $ php toquine.php | php | php | php | ... - ]]> - </codeblock> - <p> - 実際にはもう少しパイプで繋げなければならない。 - </p> - <section id="commentary"> - <h>解説</h> - <section id="quine"> - <h>プログラム全体</h> - <p> - コメントにもあるとおり、これは quine (風) のプログラムになっている。 - Quine - とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。 - </p> - <p> - このプログラムは、実行すると自身とほとんど同じプログラムを出力する。 - 異なるのはトークンになっている部分のみである。 - </p> - </section> - <section id="tokens"> - <h>トークン</h> - <p> - <code>$xs</code> がトークンに対応している。変換のロジックは <code>riddle.php</code> - とほぼ同じなので省略する。 - </p> - </section> - <section id="states"> - <h>状態保持</h> - <p> - トークンの何文字目まで出力したかを、ソースコードを変えずに (quine - なので) 覚えておく必要がある。 - このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、<code>__LINE__</code> - から情報を取得している。 - </p> - </section> - <section id="rot-13"> - <h>ROT 13</h> - <p> - Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。 - これがあまり美しくないので、<code>toquine.php</code> では、ROT 13 - 変換を使って難読化した。 - </p> - <p> - それにしてもなぜこんなものが標準ライブラリに……。 - </p> - </section> - </section> - </section> - <section id="outro"> - <h>おわりに</h> - <p> - 解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。 - </p> - <p> - 今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、 - 来年は 5問、より面白い問題を持っていきます。 - </p> - <p> - 実はもう作りはじめているので、どうか来年もありますように……。 - </p> - </section> -</article> |