From 7f15e0b8277ac8b101b4f71ce57c1c5442927141 Mon Sep 17 00:00:00 2001 From: nsfisis Date: Sat, 18 Mar 2023 19:51:06 +0900 Subject: fix(nuldoc): fix whitespaces being trimmed --- .../2022-04-09/phperkaigi-2022-tokens/index.html | 258 ++++++++++----------- 1 file changed, 129 insertions(+), 129 deletions(-) (limited to 'public/posts/2022-04-09') diff --git a/public/posts/2022-04-09/phperkaigi-2022-tokens/index.html b/public/posts/2022-04-09/phperkaigi-2022-tokens/index.html index 29e5f78..86679f3 100644 --- a/public/posts/2022-04-09/phperkaigi-2022-tokens/index.html +++ b/public/posts/2022-04-09/phperkaigi-2022-tokens/index.html @@ -63,22 +63,22 @@
-

はじめに

+

はじめに

- 本日開始されたPHPerKaigi 2022の PHPer チャレンジにおいて、弊社デジタルサーカス株式会社の問題を 3問作成した。この記事では、これらの問題の解説をおこなう。 + 本日開始された PHPerKaigi 2022 の PHPer チャレンジにおいて、弊社 デジタルサーカス株式会社 の問題を 3問作成した。この記事では、これらの問題の解説をおこなう。

- +

- リポジトリはこちら:https://github.com/nsfisis/PHPerKaigi2022-tokens + リポジトリはこちら: https://github.com/nsfisis/PHPerKaigi2022-tokens

- +
-

第1問 brainf_ck.php

+

第1問 brainf_ck.php

ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。

- + 
<?php
 
   declare(strict_types=0O1);
@@ -148,34 +148,34 @@
   $👉, $👎, $📝,
   $👈, $📝,
   ]);
- +

この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。

- +
-

解説

+

解説

-

絵文字

+

絵文字

まず目につくのは大量の絵文字だろう。 PHP は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。

- +
-

プログラム全体

+

プログラム全体

Brainf*ck のインタプリタとプログラムになっている。 Brainf*ck とは、難解プログラミング言語のひとつであり、ここで説明するよりも Wikipedia の該当ページを読んだ方がよい。

- +

https://ja.wikipedia.org/wiki/Brainfuck

- +

なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。

- + 
+ + + + + + + + + +
 [
 > + + +
@@ -198,132 +198,132 @@
 > + + .
 > - .
 < .
- +

- 実行結果はこちら:https://ideone.com/22VWmb + 実行結果はこちら: https://ideone.com/22VWmb

- +

それぞれの絵文字で表された関数が、各命令に対応している。

- +
  • - $👉:> + $👉: >
    • - +
  • - $👈:< + $👈: <
    • - +
  • - $👍:+ + $👍: +
    • - +
  • - $👎:- + $👎: -
    • - +
  • - $📝:. + $📝: .
    • - +
  • - $🤡:[ + $🤡: [
    • - +
  • - $🎪:] + $🎪: ]
- +

- ,(入力) に対応する関数はない (このプログラムでは使わないので用意していない)。 + , (入力) に対応する関数はない (このプログラムでは使わないので用意していない)。

- +

- なお、$🐘はいわゆる main 関数であり、プログラムの実行部分である。 + なお、$🐘 はいわゆる main 関数であり、プログラムの実行部分である。

- +
-

絵文字の選択

+

絵文字の選択

- おおよそ意味に合致するよう選んでいるが、$🤡と$🎪は弊社デジタルサーカスにちなんでいる。 また、$🐘は PHP のマスコットの象に由来する。 + おおよそ意味に合致するよう選んでいるが、$🤡 と $🎪 は弊社デジタルサーカスにちなんでいる。 また、$🐘 は PHP のマスコットの象に由来する。

- +
-

strict_types

+

strict_types

- declare文のstrict_typesに指定できるのは、0か1の数値リテラルだが、0x0や0b1のような値も受け付ける。 今回は、PHP 8.1 から追加された、0Oまたは0oから始まる八進数リテラルを使った。 + declare 文の strict_types に指定できるのは、0 か 1 の数値リテラルだが、 0x0 や 0b1 のような値も受け付ける。 今回は、PHP 8.1 から追加された、0O または 0o から始まる八進数リテラルを使った。

- +
-

URL

+

URL

ソースコードのライセンスを示したこの部分だが、

- + 
https://creativecommons.org/publicdomain/zero/1.0/
- +

- 完全に合法な PHP のコードである。https:部分はラベル、//以降は行コメントになっている。 + 完全に合法な PHP のコードである。 https: 部分はラベル、// 以降は行コメントになっている。

- +
-

リテラルなしで数値を生成する

+

リテラルなしで数値を生成する

ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。 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 が作れる)。 + [] に ! を適用すると true が返ってくる。それに + を適用すると、bool から int ヘの型変換が走り、1 が生成される。10 はさらにトリッキーだ。まず 1 と 0 を作り、. で文字列として結合する ('10')。これに + を適用すると、string から int への型変換が走り、10 が生まれる (コード量に頓着しないなら、1 を 10 個足し合わせてももちろん 10 が作れる)。

- +

- また、error_reportingに指定しているのは-1である。 これは、!によって文字列をfalseにし、+によってfalseを0にし、さらにビット反転して-1にしている。 + また、error_reporting に指定しているのは -1 である。 これは、! によって文字列を false にし、+ によって false を 0 にし、さらにビット反転して -1 にしている。

- +
-

if文なしで条件分岐

+

if 文なしで条件分岐

- 三項演算子ないしmatch式を使うことで、ifを一切書かずに条件分岐ができる。 また、&&/||も使えることがある。 遅延評価が不要なケースでは、[$t, $f][$cond]のような形で分岐することもできる。 + 三項演算子ないし match 式を使うことで、if を一切書かずに条件分岐ができる。 また、&& / || も使えることがある。 遅延評価が不要なケースでは、[$t, $f][$cond] のような形で分岐することもできる。

- +
-

while、for文なしでループ

+

while、for 文なしでループ

不動点コンビネータを使って無名再帰する (詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に Z コンビネータとして知られるものを使った ($z)。

- +

- 実際のところ、$🤡や$🎪、$🐘は、一度 Scheme (Lisp の一種) で書いてから PHP に翻訳する形で記述した。 + 実際のところ、$🤡 や $🎪、$🐘 は、一度 Scheme (Lisp の一種) で書いてから PHP に翻訳する形で記述した。

- +

なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは) ので、 あまりに長い brainf*ck プログラムを書くとスタックオーバーフローする。

- +
-

第2問 riddle.php

+

第2問 riddle.php

ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。

- + 
<?php
 
   /*********************************************************
@@ -358,99 +358,99 @@
   $x = implode("\n", str_split($x, length: 5));
   echo "{$x}\n\n";
   }
- +

- さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。 トークンを得るためには、ソースコードを読み、定数Nを特定する必要がある。 + さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。 トークンを得るためには、ソースコードを読み、定数 N を特定する必要がある。

- +

ここでは、私の想定解を解説する。

- +
-

読解

+

読解

まずはソースコードを読んでいく。

- + 
$token = [
   // 略
   ];
- +

- 数値からなる$tokenがあり、各要素をループしている。 + 数値からなる $token があり、各要素をループしている。

- + 
  $x = $x ^ N;
- +

まずは排他的論理和 (xor) を取り、

- + 
  $x = sprintf('%025b', $x);
- +

二進数に変換して、

- + 
  $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
- +

- 0 を空白に、1 を#にし、 + 0 を空白に、1 を # にし、

- + 
  $x = implode("\n", str_split($x, length: 5));
- +

5文字ごとに区切ったあと、改行で結合している。

- +
-

ヒント

+

ヒント

次に、ソースコードに書いてあるヒントを読んでいく。

- +
  • - Nそれ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている + N それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている
    • - +
  • - $tokenの各要素は、1文字を表す + $token の各要素は、1文字を表す
    • - +
  • 1文字は 5x5 のセルからなる
    • - +
  • 出力されるのは、完全な PHPer トークンである
- +

- ここで、PHPer トークンは必ず#記号から始まることを思いだすと、$tokenの最初の数字0x14B499Cは、変換の結果#になるのではないかと予想される (なお、このことは、リポジトリの README ファイルに追加ヒントとして書かれている)。 + ここで、PHPer トークンは必ず # 記号から始まることを思いだすと、 $token の最初の数字 0x14B499C は、変換の結果 # になるのではないかと予想される (なお、このことは、リポジトリの README ファイルに追加ヒントとして書かれている)。

- +
-

解く

+

解く

- ここまでわかれば、あと一歩で解ける。すなわち、0x14B499Cが#に変換されるようなNを見つければよい。 + ここまでわかれば、あと一歩で解ける。すなわち、0x14B499C が # に変換されるような N を見つければよい。

- +

- Nは高々 + N は高々

- + 
assert(0 <= N && N <= 0b11111_11111_11111_11111_11111);
- +

なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。

- + 
<?php
 
   $x = 0x14B499C;
@@ -467,11 +467,11 @@
   " # # \n" .
   "#####\n" .
   " # # ");
- +

この一連の変換に対する逆変換を考えると、次のようになる。

- + 
<?php
 
 $x =
@@ -488,19 +488,19 @@
 $n = $x ^ 0x14B499C;
 
 echo "N = $n\n";
- +

- これを実行すると、Nが得られる。 + これを実行すると、N が得られる。

- +
-

第3問 toquine.php

+

第3問 toquine.php

ソースコードはこちら。

- + 
<?php
 
   // License: https://creativecommons.org/publicdomain/zero/1.0/
@@ -530,67 +530,67 @@
   $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));
- +

コメントにもあるとおり、次のようにして実行すれば答えがでてくる。

- + 
$ php toquine.php | php | php | php | ...
- +

実際にはもう少しパイプで繋げなければならない。

- +
-

解説

+

解説

-

プログラム全体

+

プログラム全体

コメントにもあるとおり、これは quine (風) のプログラムになっている。 Quine とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。

- +

このプログラムは、実行すると自身とほとんど同じプログラムを出力する。 異なるのはトークンになっている部分のみである。

- +
-

トークン

+

トークン

- $xsがトークンに対応している。変換のロジックはriddle.phpとほぼ同じなので省略する。 + $xs がトークンに対応している。変換のロジックは riddle.php とほぼ同じなので省略する。

- +
-

状態保持

+

状態保持

- トークンの何文字目まで出力したかを、ソースコードを変えずに (quine なので) 覚えておく必要がある。 このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、LINEから情報を取得している。 + トークンの何文字目まで出力したかを、ソースコードを変えずに (quine なので) 覚えておく必要がある。 このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、LINE から情報を取得している。

- +
-

ROT 13

+

ROT 13

- Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。 これがあまり美しくないので、toquine.phpでは、ROT 13 変換を使って難読化した。 + Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。 これがあまり美しくないので、toquine.php では、ROT 13 変換を使って難読化した。

- +

それにしてもなぜこんなものが標準ライブラリに……。

- +
-

おわりに

+

おわりに

解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。

- +

今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、 来年は 5問、より面白い問題を持っていきます。

- +

実はもう作りはじめているので、どうか来年もありますように……。

-- cgit v1.2.3-70-g09d2