こもろぐ @tenkoma

What We Find Changes Who We Become -- Peter Morville著『アンビエント・ファインダビリティ 』

⛳ PHPer Code Golf by pixiv(PHPerKaigi 2020) 上級編の回答について解説

PHPerKaigi 2020 、お疲れ様でした!! PHPer Code Golf by pixiv で賞を頂いたtenkomaです。

イベントについてのエントリーは別途書くとして、Code Golf上級編で書いたコードの解説をします。 1問目はHello, World, 2問目はFizzBuzzなので詳しい解説はしません。

個人的にはCode Golfガチ勢では全く無いのですが、賞をもらってしまったので、コードを晒す義務が発生した気がします。 ちなみに会場のネットワークの混雑等のトラブルもあり、第3ホールの開催時間は1時間20分ほどだったようです。

出題概要

PHPerKaigi 2020参加者向けに用意されたこのサイトで、問題を解く形式です。サイトは停止するかもしれないので出題文を転載します。

配列を展開せよ

あるサイトにのAPIにリクエストを送ると、結果がとても変な形式のJSONで帰ってきてしまいます。

{"foo": "1", "bar[0]": "A", "bar[1]": "B", "buz[0][0]": "00", "buz[0][1]": "01"}

あなたの仕事はこの独特なフォーマットのレスポンスを常識的に綺麗な形状の配列に直すことです。

{"foo": "1", "bar": ["A", "B"], "buz": [["00", "01"]]}

結果の配列は json_encode() で変換して出力してください。

コード入力

<?php

declare(strict_types=1);

$input = json_decode(stream_get_contents(STDIN), true);

$converter = function (array $in) {
    // ...
};

// 最終的にこの変換結果が出力されるようにしてください。
// コード内の好きな位置に関数やクラスを定義しても構いません。
echo json_encode($converter($input));

問題文は以上です。

問題についての注意点

出力後のjson は所々スペースが入ってますが、json_encode()の出力ではスペースを入れることができなかったので、レギュレーションについてゴルフ場デベロッパーさん (@tadsan) / Twitterに問い合わせして、スペースを含まないjsonで正解することができるようになりました。

とりあえず正解にたどり着く

最初に正解にたどり着いたときのコードは以下のような感じでした。

<?php

foreach (json_decode(stream_get_contents(STDIN), true) as $k => $v) {
    $a[] = "{$k}={$v}";
}
parse_str(implode('&', $a), $a);
echo json_encode($a);

この答えにたどり着くまでに可変変数や eval() などを試していたのですが、うまくパスできませんでした。 そのころから、JSONハッシュのキーがURLのクエリのキー形式として使えそうだったので、URLクエリ形式に変換して parse_url() で配列化する方法をためして、正解することができました。 $a 配列をimplode() でまとめた文字列が

foo=1&bar[0]=A&bar[1]=B&buz[0][0]=00&buz[0][1]=01

になるので、それを parse_url() で求める連想配列にできる、という感じです。

最適化1 標準入力の受け取りが長い

stream_get_contents(STDIN)

ここですね。いかにも冗長な感じがします。検索したところ、

fgets(STDIN)

で受け取れることが分かったので、短くなりました。 なお、今回のレギュレーションだと、単に文字数が短いというのが高得点のコツではないそうですが、スコアは良くなりました。

最適化2 ループをなくす

次に見たのがここです。

foreach (json_decode(fgets(STDIN), true) as $k => $v) {
    $a[] = "{$k}={$v}";
}

json_decode して foreach するとか、コード書きすぎですね。。。 ループをなくして、文字列変換ですませることができれば、かなりコードをシンプルにできそうです。

{"foo": "1", "bar[0]": "A", "bar[1]": "B", "buz[0][0]": "00", "buz[0][1]": "01"}

この入力を見ると、jsonのキーと値は ":", 各要素は "," で区切られていることが分かるので、それぞれを =,&に変換してから、周りの{}" を除去できれば、期待するURLクエリに変換できそうです。 そこで最適化したコードが以下です。

<?php
parse_str(strtr(trim(fgets(STDIN), '{}"'), ['":"' => '=', '","' => '&']), $a);
echo json_encode($a);

標準入力を trim(fgets(STDIN), '{}"') で、余計な文字列を削除して以下にします。

foo": "1", "bar[0]": "A", "bar[1]": "B", "buz[0][0]": "00", "buz[0][1]": "01

あとは strtr(..., ['":"' => '=', '","' => '&'])でURLクエリになるように変換します。 (入力のjsonにもスペースがなかったようです) 時間制限最後の回答は以下だったかと思います。

<?php
parse_str(strtr(trim(fgets(STDIN), '{}"'), ['":"' => '=', '","' => '&']), $a);
echo json_encode($a);

今思えば、値に :, が入ってると変換できないですね。

最適化3 (時間切れですが、少し最適化)

LTの時間にやっていたのですが、 preg_replace() を使って {}" をすべて削除してから、 strtr() で1文字毎に変換(:=, ,&)するコードだと抽象構文木としてはシンプルになるので試したところ、スコアが良くなりました。

<?php
parse_str(strtr(preg_replace('/[{}"]/','',fgets(STDIN)),':,', '=&'), $a);
echo json_encode($a);

そのときのスコアは以下の通り。

  • 項目A(低いほど高評価) 105 (最適化2では107)
  • 項目B(低いほど高評価) 4 (最適化2では4)
  • 項目C(低いほど高評価) 39 (最適化2では46)
  • 項目D(低いほど高評価) 105 (最適化2では107)
  • 項目E(高いほど高評価) 8 (最適化2では10)

いまのところ、僕の最高スコアはこちらになります。

おまけ: FizzBuzz について

FizzBuzz については昔作ったプログラムを少し最適化して

<?for(;$i++<100;)echo(($i%3?'':Fizz).($i%5?'':Buzz)?:$i).'
';

として解いてました。しかし、このゴルフ場はPHP7.4、7.4の最新の文法を使ったら、もしかしたらPHPerチャレンジのボーナストークン的なものがもらえるかも!?とおもい、アロー関数を使って

<?for(;$i++<100;)echo(($f=fn($d,$w)=>$i%$d?'':$w)(3,Fizz).$f(5,Buzz)?:$i)."
";

と書いて正解になりましたが、別のトークンはもらえませんでした!

終わり。