diff options
| author | nsfisis <nsfisis@gmail.com> | 2023-09-20 19:56:52 +0900 |
|---|---|---|
| committer | nsfisis <nsfisis@gmail.com> | 2023-09-20 19:56:57 +0900 |
| commit | a84908b7e8a0e2423afd6b836eccf27a420270b4 (patch) | |
| tree | 00204b62358f8c57fcb36f601db360626484cc1a /vhosts/blog/content/posts/2022-04-09 | |
| parent | 0b488f85380f964c40b0b9aae69c6611bc7978bc (diff) | |
| download | nsfisis.dev-a84908b7e8a0e2423afd6b836eccf27a420270b4.tar.gz nsfisis.dev-a84908b7e8a0e2423afd6b836eccf27a420270b4.tar.zst nsfisis.dev-a84908b7e8a0e2423afd6b836eccf27a420270b4.zip | |
feat(blog/nuldoc): change content format from DocBook to NulDoc
Diffstat (limited to 'vhosts/blog/content/posts/2022-04-09')
| -rw-r--r-- | vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc (renamed from vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.xml) | 500 |
1 files changed, 248 insertions, 252 deletions
diff --git a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.xml b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc index 898d7ea9..c13b0c55 100644 --- a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.xml +++ b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc @@ -1,44 +1,40 @@ -<?xml version="1.0" encoding="UTF-8"?> -<article xmlns="http://docbook.org/ns/docbook" xmlns:xl="http://www.w3.org/1999/xlink" version="5.0"> - <info> - <title>PHPerKaigi 2022 トークン問題の解説</title> - <abstract> - PHPerKaigi 2022 で私が作成した PHPer チャレンジ問題を解説する。 - </abstract> - <keywordset> - <keyword>conference</keyword> - <keyword>php</keyword> - <keyword>phperkaigi</keyword> - </keywordset> - <revhistory> - <revision> - <date>2022-04-09</date> - <revremark>公開</revremark> - </revision> - <revision> - <date>2022-04-16</date> - <revremark>2問目、3問目の解説を追加、1問目に加筆</revremark> - </revision> - </revhistory> - </info> - <section xml:id="intro"> - <title>はじめに</title> - <para> - 本日開始された <link xl:href="https://phperkaigi.jp/2022/">PHPerKaigi 2022</link> の PHPer +--- +[article] +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 チャレンジにおいて、弊社 - <link xl:href="https://www.dgcircus.com/">デジタルサーカス株式会社</link> の問題を + <a href="https://www.dgcircus.com/">デジタルサーカス株式会社</a> の問題を 3問作成した。この記事では、これらの問題の解説をおこなう。 - </para> - <para> - リポジトリはこちら: <link xl:href="https://github.com/nsfisis/PHPerKaigi2022-tokens">https://github.com/nsfisis/PHPerKaigi2022-tokens</link> - </para> + </p> + <p> + リポジトリはこちら: <a href="https://github.com/nsfisis/PHPerKaigi2022-tokens">https://github.com/nsfisis/PHPerKaigi2022-tokens</a> + </p> </section> - <section xml:id="q1-brainfuck"> - <title>第1問 brainf_ck.php</title> - <para> + <section id="q1-brainfuck"> + <h>第1問 brainf_ck.php</h> + <p> ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ <?php @@ -110,33 +106,33 @@ $👈, $📝, ]); ]]> - </programlisting> - <para> + </codeblock> + <p> この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。 - </para> - <section xml:id="q1-brainfuck--commentary"> - <title>解説</title> - <section xml:id="q1-brainfuck--commentary--emoji"> - <title>絵文字</title> - <para> + </p> + <section id="q1-brainfuck--commentary"> + <h>解説</h> + <section id="q1-brainfuck--commentary--emoji"> + <h>絵文字</h> + <p> まず目につくのは大量の絵文字だろう。 PHP は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。 - </para> + </p> </section> - <section xml:id="q1-brainfuck--commentary--brainfuck"> - <title>プログラム全体</title> - <para> + <section id="q1-brainfuck--commentary--brainfuck"> + <h>プログラム全体</h> + <p> Brainf*ck のインタプリタとプログラムになっている。 Brainf*ck とは、難解プログラミング言語のひとつであり、ここで説明するよりも Wikipedia の該当ページを読んだ方がよい。 - </para> - <para> - <link xl:href="https://ja.wikipedia.org/wiki/Brainfuck">https://ja.wikipedia.org/wiki/Brainfuck</link> - </para> - <para> + </p> + <p> + <a href="https://ja.wikipedia.org/wiki/Brainfuck">https://ja.wikipedia.org/wiki/Brainfuck</a> + </p> + <p> なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。 - </para> - <literallayout class="monospaced"> + </p> + <codeblock> <![CDATA[ + + + + + + + + + + [ @@ -161,68 +157,68 @@ > - . < . ]]> - </literallayout> - <para> - 実行結果はこちら: <link xl:href="https://ideone.com/22VWmb">https://ideone.com/22VWmb</link> - </para> - <para> + </codeblock> + <p> + 実行結果はこちら: <a href="https://ideone.com/22VWmb">https://ideone.com/22VWmb</a> + </p> + <p> それぞれの絵文字で表された関数が、各命令に対応している。 - </para> - <itemizedlist> - <listitem><literal>$👉</literal>: <literal>></literal></listitem> - <listitem><literal>$👈</literal>: <literal><</literal></listitem> - <listitem><literal>$👍</literal>: <literal>+</literal></listitem> - <listitem><literal>$👎</literal>: <literal>-</literal></listitem> - <listitem><literal>$📝</literal>: <literal>.</literal></listitem> - <listitem><literal>$🤡</literal>: <literal>[</literal></listitem> - <listitem><literal>$🎪</literal>: <literal>]</literal></listitem> - </itemizedlist> - <para> - <literal>,</literal> (入力) に対応する関数はない + </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> (入力) に対応する関数はない (このプログラムでは使わないので用意していない)。 - </para> - <para> - なお、<literal>$🐘</literal> はいわゆる main 関数であり、プログラムの実行部分である。 - </para> + </p> + <p> + なお、<code>$🐘</code> はいわゆる main 関数であり、プログラムの実行部分である。 + </p> </section> - <section xml:id="q1-brainfuck--commentary--emoji-selection"> - <title>絵文字の選択</title> - <para> - おおよそ意味に合致するよう選んでいるが、<literal>$🤡</literal> と <literal>$🎪</literal> - は弊社デジタルサーカスにちなんでいる。 また、<literal>$🐘</literal> は PHP + <section id="q1-brainfuck--commentary--emoji-selection"> + <h>絵文字の選択</h> + <p> + おおよそ意味に合致するよう選んでいるが、<code>$🤡</code> と <code>$🎪</code> + は弊社デジタルサーカスにちなんでいる。 また、<code>$🐘</code> は PHP のマスコットの象に由来する。 - </para> + </p> </section> - <section xml:id="q1-brainfuck--commentary--strict-types"> - <title>strict_types</title> - <para> - <literal>declare</literal> 文の <literal>strict_types</literal> に指定できるのは、<literal>0</literal> か <literal>1</literal> - の数値リテラルだが、 <literal>0x0</literal> や <literal>0b1</literal> のような値も受け付ける。 今回は、PHP - 8.1 から追加された、<literal>0O</literal> または <literal>0o</literal> から始まる八進数リテラルを使った。 - </para> + <section id="q1-brainfuck--commentary--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 xml:id="q1-brainfuck--commentary--url"> - <title>URL</title> - <para> + <section id="q1-brainfuck--commentary--url"> + <h>URL</h> + <p> ソースコードのライセンスを示したこの部分だが、 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ https://creativecommons.org/publicdomain/zero/1.0/ ]]> - </programlisting> - <para> - 完全に合法な PHP のコードである。 <literal>https:</literal> 部分はラベル、<literal>//</literal> + </codeblock> + <p> + 完全に合法な PHP のコードである。 <code>https:</code> 部分はラベル、<code>//</code> 以降は行コメントになっている。 - </para> + </p> </section> - <section xml:id="q1-brainfuck--commentary--numbers"> - <title>リテラルなしで数値を生成する</title> - <para> + <section id="q1-brainfuck--commentary--numbers"> + <h>リテラルなしで数値を生成する</h> + <p> ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。 PHP では、型変換を利用することで任意の整数を作り出すことができる。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ assert(0 === +!![]); assert(1 === +![]); @@ -230,55 +226,55 @@ assert(3 === ![]+![]+![]); assert(10 === +(![].+!![])); ]]> - </programlisting> - <para> - <literal>[]</literal> に <literal>!</literal> を適用すると <literal>true</literal> が返ってくる。それに <literal>+</literal> - を適用すると、<literal>bool</literal> から <literal>int</literal> ヘの型変換が走り、<literal>1</literal> が生成される。<literal>10</literal> - はさらにトリッキーだ。まず <literal>1</literal> と <literal>0</literal> を作り、<literal>.</literal> で文字列として結合する - (<literal>'10'</literal>)。これに <literal>+</literal> を適用すると、<literal>string</literal> から <literal>int</literal> - への型変換が走り、<literal>10</literal> が生まれる (コード量に頓着しないなら、<literal>1</literal> を 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 が作れる)。 - </para> - <para> - また、<literal>error_reporting</literal> に指定しているのは <literal>-1</literal> である。 これは、<literal>!</literal> - によって文字列を <literal>false</literal> にし、<literal>+</literal> によって <literal>false</literal> を <literal>0</literal> - にし、さらにビット反転して <literal>-1</literal> にしている。 - </para> + </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 xml:id="q1-brainfuck--commentary--conditionals"> - <title><literal>if</literal> 文なしで条件分岐</title> - <para> - 三項演算子ないし <literal>match</literal> 式を使うことで、<literal>if</literal> - を一切書かずに条件分岐ができる。 また、<literal>&&</literal> / <literal>||</literal> も使えることがある。 - 遅延評価が不要なケースでは、<literal>[$t, $f][$cond]</literal> + <section id="q1-brainfuck--commentary--conditionals"> + <h><code>if</code> 文なしで条件分岐</h> + <p> + 三項演算子ないし <code>match</code> 式を使うことで、<code>if</code> + を一切書かずに条件分岐ができる。 また、<code>&&</code> / <code>||</code> も使えることがある。 + 遅延評価が不要なケースでは、<code>[$t, $f][$cond]</code> のような形で分岐することもできる。 - </para> + </p> </section> - <section xml:id="q1-brainfuck--commentary--loops"> - <title><literal>while</literal>、<literal>for</literal> 文なしでループ</title> - <para> + <section id="q1-brainfuck--commentary--loops"> + <h><code>while</code>、<code>for</code> 文なしでループ</h> + <p> 不動点コンビネータを使って無名再帰する (詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に - Z コンビネータとして知られるものを使った (<literal>$z</literal>)。 - </para> - <para> - 実際のところ、<literal>$🤡</literal> や <literal>$🎪</literal>、<literal>$🐘</literal> は、一度 Scheme (Lisp の一種) + Z コンビネータとして知られるものを使った (<code>$z</code>)。 + </p> + <p> + 実際のところ、<code>$🤡</code> や <code>$🎪</code>、<code>$🐘</code> は、一度 Scheme (Lisp の一種) で書いてから PHP に翻訳する形で記述した。 - </para> - <para> + </p> + <p> なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは) ので、 あまりに長い brainf*ck プログラムを書くとスタックオーバーフローする。 - </para> + </p> </section> </section> </section> - <section xml:id="q2-riddle"> - <title>第2問 riddle.php</title> - <para> + <section id="q2-riddle"> + <h>第2問 riddle.php</h> + <p> ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ <?php @@ -315,99 +311,99 @@ echo "{$x}\n\n"; } ]]> - </programlisting> - <para> + </codeblock> + <p> さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。 - トークンを得るためには、ソースコードを読み、定数 <literal>N</literal> + トークンを得るためには、ソースコードを読み、定数 <code>N</code> を特定する必要がある。 - </para> - <para> + </p> + <p> ここでは、私の想定解を解説する。 - </para> - <section xml:id="q2-riddle--code-reading"> - <title>読解</title> - <para> + </p> + <section id="q2-riddle--code-reading"> + <h>読解</h> + <p> まずはソースコードを読んでいく。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ $token = [ // 略 ]; ]]> - </programlisting> - <para> - 数値からなる <literal>$token</literal> があり、各要素をループしている。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </codeblock> + <p> + 数値からなる <code>$token</code> があり、各要素をループしている。 + </p> + <codeblock language="php"> <![CDATA[ $x = $x ^ N; ]]> - </programlisting> - <para> + </codeblock> + <p> まずは排他的論理和 (xor) を取り、 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ $x = sprintf('%025b', $x); ]]> - </programlisting> - <para> + </codeblock> + <p> 二進数に変換して、 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x); ]]> - </programlisting> - <para> - 0 を空白に、1 を <literal>#</literal> にし、 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </codeblock> + <p> + 0 を空白に、1 を <code>#</code> にし、 + </p> + <codeblock language="php"> <![CDATA[ $x = implode("\n", str_split($x, length: 5)); ]]> - </programlisting> - <para> + </codeblock> + <p> 5文字ごとに区切ったあと、改行で結合している。 - </para> + </p> </section> - <section xml:id="q2-riddle--hint"> - <title>ヒント</title> - <para> + <section id="q2-riddle--hint"> + <h>ヒント</h> + <p> 次に、ソースコードに書いてあるヒントを読んでいく。 - </para> - <itemizedlist> - <listitem><literal>N</literal> それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている</listitem> - <listitem><literal>$token</literal> の各要素は、1文字を表す</listitem> - <listitem>1文字は 5x5 のセルからなる</listitem> - <listitem>出力されるのは、完全な PHPer トークンである</listitem> - </itemizedlist> - <para> - ここで、PHPer トークンは必ず <literal>#</literal> 記号から始まることを思いだすと、 - <literal>$token</literal> の最初の数字 <literal>0x14B499C</literal> は、変換の結果 <literal>#</literal> + </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 ファイルに追加ヒントとして書かれている)。 - </para> + </p> </section> - <section xml:id="q2-riddle--solve"> - <title>解く</title> - <para> - ここまでわかれば、あと一歩で解ける。すなわち、<literal>0x14B499C</literal> が <literal>#</literal> - に変換されるような <literal>N</literal> を見つければよい。 - </para> - <para> - <literal>N</literal> は高々 - </para> - <programlisting language="php" linenumbering="unnumbered"> + <section id="q2-riddle--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); ]]> - </programlisting> - <para> + </codeblock> + <p> なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ <?php @@ -426,11 +422,11 @@ "#####\n" . " # # "); ]]> - </programlisting> - <para> + </codeblock> + <p> この一連の変換に対する逆変換を考えると、次のようになる。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ <?php @@ -449,18 +445,18 @@ echo "N = $n\n"; ]]> - </programlisting> - <para> - これを実行すると、<literal>N</literal> が得られる。 - </para> + </codeblock> + <p> + これを実行すると、<code>N</code> が得られる。 + </p> </section> </section> - <section xml:id="q3-toquine"> - <title>第3問 toquine.php</title> - <para> + <section id="q3-toquine"> + <h>第3問 toquine.php</h> + <p> ソースコードはこちら。 - </para> - <programlisting language="php" linenumbering="unnumbered"> + </p> + <codeblock language="php"> <![CDATA[ <?php @@ -492,72 +488,72 @@ $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)); ]]> - </programlisting> - <para> + </codeblock> + <p> コメントにもあるとおり、次のようにして実行すれば答えがでてくる。 - </para> - <programlisting language="shell-session" linenumbering="unnumbered"> + </p> + <codeblock language="shell-session"> <![CDATA[ $ php toquine.php | php | php | php | ... ]]> - </programlisting> - <para> + </codeblock> + <p> 実際にはもう少しパイプで繋げなければならない。 - </para> - <section xml:id="q3-toquine--commentary"> - <title>解説</title> - <section xml:id="q3-toquine--commentary--quine"> - <title>プログラム全体</title> - <para> + </p> + <section id="q3-toquine--commentary"> + <h>解説</h> + <section id="q3-toquine--commentary--quine"> + <h>プログラム全体</h> + <p> コメントにもあるとおり、これは quine (風) のプログラムになっている。 Quine とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。 - </para> - <para> + </p> + <p> このプログラムは、実行すると自身とほとんど同じプログラムを出力する。 異なるのはトークンになっている部分のみである。 - </para> + </p> </section> - <section xml:id="q3-toquine--commentary--tokens"> - <title>トークン</title> - <para> - <literal>$xs</literal> がトークンに対応している。変換のロジックは <literal>riddle.php</literal> + <section id="q3-toquine--commentary--tokens"> + <h>トークン</h> + <p> + <code>$xs</code> がトークンに対応している。変換のロジックは <code>riddle.php</code> とほぼ同じなので省略する。 - </para> + </p> </section> - <section xml:id="q3-toquine--commentary--states"> - <title>状態保持</title> - <para> + <section id="q3-toquine--commentary--states"> + <h>状態保持</h> + <p> トークンの何文字目まで出力したかを、ソースコードを変えずに (quine なので) 覚えておく必要がある。 - このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、<literal><emphasis>LINE</emphasis></literal> + このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、<code>__LINE__</code> から情報を取得している。 - </para> + </p> </section> - <section xml:id="q3-toquine--commentary--rot-13"> - <title>ROT 13</title> - <para> + <section id="q3-toquine--commentary--rot-13"> + <h>ROT 13</h> + <p> Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。 - これがあまり美しくないので、<literal>toquine.php</literal> では、ROT 13 + これがあまり美しくないので、<code>toquine.php</code> では、ROT 13 変換を使って難読化した。 - </para> - <para> + </p> + <p> それにしてもなぜこんなものが標準ライブラリに……。 - </para> + </p> </section> </section> </section> - <section xml:id="outro"> - <title>おわりに</title> - <para> + <section id="outro"> + <h>おわりに</h> + <p> 解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。 - </para> - <para> + </p> + <p> 今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、 来年は 5問、より面白い問題を持っていきます。 - </para> - <para> + </p> + <p> 実はもう作りはじめているので、どうか来年もありますように……。 - </para> + </p> </section> </article> |
