paiza オンラインハッカソンでコードゴルフに挑戦

paiza オンラインハッカソン Vol. 6+ に挑戦しました。ウェブページはこちらです。
「え、妻が松江？」松江Ruby会議07協賛回文作成プログラミングコンテスト｜POH6+

今回は、提出したコードのバイト数が表示されていたためか、どれだけ短いコードで問題を解けるかを競うコードゴルフに挑戦する参加者が多かったようです*1。私も PHP で挑戦してみました。

最初のコードは次のようなものです*2。前半の while ループでは、読み込んだ単語を $buffer に格納して、ペアになる単語が見つかったら $pairs に移動します。すべての単語を処理して while ループを抜けた後、$pairs をソートしたものが回文の前半 ($upper)、それを反転したものが後半 ($lower) になります。また、$buffer に残っている単語から、反転しても同じになるもので辞書順の先頭になるものを探し、そのような単語があれば中央 ($center) に出力します。このコードを出発点にして、処理の内容を変えずにできるだけ短くしていきます*3。

<?php
$pairs = [];
$buffer = [];

fgets(STDIN);
while ($w = chop(fgets(STDIN))) {
    $r = strrev($w);
    if (array_key_exists($r, $buffer)) {
        if (--$buffer[$r] == 0) {
            unset($buffer[$r]);
        }
        $pairs[] = min($w, $r);
    } else {
        if (!array_key_exists($w, $buffer)) {
            $buffer[$w] = 0;
        }
        ++$buffer[$w];
    }
}

sort($pairs);
$upper = implode($pairs);
$lower = strrev($upper);

$center = '';
foreach ($buffer as $w => $c) {
    if ($w == strrev($w)) {
        $center = $center ? min($center, $w) : $w;
    }
}

echo $upper . $center . $lower . "\n";

最初のコード · y-uti/poh6-anagram-codegolf@76b3fbc · GitHub

問題の条件を満たす範囲のコード短縮

まず、変数の初期化処理を除去します。これによって実行時に Warning や Notice が発生するようになります。良い作法ではありませんし、実行速度も低下しますが、今回はコードの短縮が目的なので気にしません。

2,4d1
< $pairs = [];
< $buffer = [];
<
14,16d10
<         if (!array_key_exists($w, $buffer)) {
<             $buffer[$w] = 0;
<         }
25d18
< $center = '';

変数の初期化を省略 · y-uti/poh6-anagram-codegolf@61f7922 · GitHub

次に、ペアを見つけて --$buffer[$r] した結果が 0 になったときの unset を除去します。$buffer[$r] が 0 のまま残ることになるので、array_key_exists のチェックを変更して $buffer[$r] > 0 かどうかを調べるようにします。$buffer[$r] は整数なので、これは単に if ($buffer[$r]) { ... } と書けます。また、最後に $center を探す処理も、$c > 0 であることをチェックするように変更します。

5,8c5,6
<     if (array_key_exists($r, $buffer)) {
<         if (--$buffer[$r] == 0) {
<             unset($buffer[$r]);
<         }
---
>     if ($buffer[$r]) {
>         --$buffer[$r];
20c18
<     if ($w == strrev($w)) {
---
>     if ($w == strrev($w) && $c) {

ペアを見つけて $buffer[$r] が 0 になっても unset しない · y-uti/poh6-anagram-codegolf@675b4ea · GitHub

$center を探す処理を while ループに統合します。ペアが見つからなかったときの処理として、反転しても同じ文字列なら $centers[$w] = 1 にします。右辺の 1 には特に意味はなく、どんな値でもかまいません。ペアが見つかったときには unset($centers[$w]) します。$centers のキーに $w があれば、$w は中央の単語の候補になります。これまで $buffer から探していた処理は、$centers を ksort で整列した後に先頭のキーを取れば済みます。

7a8
>         unset($centers[$w]);
9a11,13
>         if ($r == $w) {
>             $centers[$w] = 1;
>         }
17,21c21,22
< foreach ($buffer as $w => $c) {
<     if ($w == strrev($w) && $c) {
<         $center = $center ? min($center, $w) : $w;
<     }
< }
---
> ksort($centers);
> $center = key($centers);

$center の管理を while ループに統合 · y-uti/poh6-anagram-codegolf@a6213cc · GitHub

文字列の出力部分を短くします。implode を join に変更します。また、一つずつ変数に代入していた処理を echo にまとめます。echo はカンマ区切りで複数の文字列を受け取れます。カンマ演算子は代入演算子よりも優先順位が低いので、ピリオドで文字列を連結せずにカンマ区切りで渡すことで、$upper = join($pairs) を括弧で囲まなくてもよくなります。

18,20d17
< $upper = implode($pairs);
< $lower = strrev($upper);
<
22d18
< $center = key($centers);
24c20
< echo $upper . $center . $lower . "\n";
---
> echo $upper = join($pairs), key($centers), strrev($upper), "\n";

echo 部分の処理のコード短縮 · y-uti/poh6-anagram-codegolf@cc9e7a3 · GitHub

ここから、論理演算子を使って処理をまとめていきます。まず then 節のステートメントを条件節にまとめます。--$buffer[$r] を $buffer[$r]-- に変えれば、評価結果は必ず 1 以上になるので、&& で繋がれた $pairs[] = min($w, $r) が実行されます。$w, $r はいずれも true に評価される文字列なので、全体も true になって then 節の unset($centers[$w]) も実行されます。なお、unset は値を戻さないステートメントなので条件節にまとめることができません。then 節にそのまま残すことになります。

5,7c5
<     if ($buffer[$r]) {
<         --$buffer[$r];
<         $pairs[] = min($w, $r);
---
>     if ($buffer[$r] && $buffer[$r]-- && $pairs[] = min($w, $r)) {

論理演算子を用いて処理をまとめる: then 節 · y-uti/poh6-anagram-codegolf@92c5906 · GitHub

同様に else 節のステートメントも条件節にまとめます。|| 演算子の後ろに処理をまとめていきます。代入演算子は || 演算子よりも優先順位が低いので、$pairs[] への代入は括弧で囲まなければいけません。また、|| の後ろは全体として false にならなければいけません。今回のケースでは、$centers[$w] の右辺は何でもよかったので、これを 0 に変えて false になるようにしました。

5c5,6
<     if ($buffer[$r] && $buffer[$r]-- && $pairs[] = min($w, $r)) {
---
>     if ($buffer[$r] && $buffer[$r]-- && ($pairs[] = min($w, $r))
>         || ++$buffer[$w] && $r == $w && $centers[$w] = 0) {
7,11d7
<     } else {
<         ++$buffer[$w];
<         if ($r == $w) {
<             $centers[$w] = 1;
<         }

論理演算子を用いて処理をまとめる: else 節 · y-uti/poh6-anagram-codegolf@310aaac · GitHub

先頭行を読み飛ばしていた処理を while ループにまとめます。先頭行は数字なので、読み飛ばさずに処理しても他の行とペアになることはありません。一方、先頭行の数字が回文 (121 など) になっていると、$centers に含まれることになり、誤った結果を出力してしまいます。$w < 1 という条件を追加することで、$w が数字なら $centers に追加されないようにしています。$w が 0 の場合は最初の while の条件判断で false になるので、何も出力せずにプログラムは終了します*4。

2d1
< fgets(STDIN);
6c5
<         || ++$buffer[$w] && $r == $w && $centers[$w] = 0) {
---
>         || ++$buffer[$w] && $r == $w && $w < 1 && $centers[$w] = 0) {

先頭行の読み飛ばし処理を while ループに統合 · y-uti/poh6-anagram-codegolf@856d6c4 · GitHub

最後に細かな改良を加えます。$r = strrev($w) の代入を if 文での配列アクセスにまとめます。これで while 文の中が 1 ステートメントになり括弧を省略できます。また、&& 演算子の中で短絡評価しなくてもよいものを & 演算子に置き換えます。ただし $buffer[$r]-- && ($pairs[] = min($w, $r)) の && は、ビット演算の & にすると数値同士のビット演算と解釈されて結果が 0 になってしまいます。そこで、文字列の連結にして結果が true になるようにしています。

3,5c3,4
<     $r = strrev($w);
<     if ($buffer[$r] && $buffer[$r]-- && ($pairs[] = min($w, $r))
<         || ++$buffer[$w] && $r == $w && $w < 1 && $centers[$w] = 0) {
---
>     if ($buffer[$r = strrev($w)] && $buffer[$r]-- . ($pairs[] = min($w, $r))
>         || ++$buffer[$w] & $r == $w & $w < 1 && $centers[$w] = 0) {

$r への代入を配列アクセスに統合。論理演算子を 1 文字の演算子に置き換え · y-uti/poh6-anagram-codegolf@45beb8a · GitHub

あとは、このコードから余分な括弧、空白、改行をすべて除去して、各変数を一文字に変更すれば、188 バイトになります。
188 バイトのコード · y-uti/poh6-anagram-codegolf@4c5febc · GitHub

オンラインハッカソンのテストケースに特化したコード短縮

ここまでは、オンラインハッカソンの問題の条件を満たす範囲でコードを短くしてきました。ところが下記のページによれば、テストケースが問題の条件を十分に網羅していないため、より簡単な (本来ならバグのある) コードでも、用意されたすべてのテストケースを通過してしまうようです。ここから先では、このことを利用してさらにコードを短くしていきます。
POH6+『「え、妻が松江？」松江Ruby会議07協賛回文作成プログラミングコンテスト』ゴルフ編 - Qiita

オンラインハッカソンのテストケースでは、反転しても同じ文字列になる単語は 1 種類しか出現しません。したがって $centers の配列は不要で、次のように書けます。外側の if 文では、$w と strrev($w) が異なっているかどうかを判断します。異なっていれば then 節が実行されます。then 節はここまでのコードの処理と同様ですが、$centers[$w] = 0 に関する処理は削除しています。一方、$w と strrev($w) が等しいときは else 節が実行されます。else 節では単純に $w を $center に付け足していきます。こうして作られた $center が回文の中央部分に出力されます。

<?php
while ($w = chop(fgets(STDIN))) {
    if ($w != ($r = strrev($w)) | $w > 0) {
        if ($buffer[$r] && $buffer[$r]-- . ($pairs[] = min($w, $r)) || ++$buffer[$w]);
    } else {
        $center .= $w;
    }
}

sort($pairs);

echo $upper = join($pairs), $center, strrev($upper), "\n";

逆から読んでも同じ単語は一種類しか存在しない · y-uti/poh6-anagram-codegolf@552b05a · GitHub

また、オンラインハッカソンのテストケースでは、反転して同じ文字列になる単語以外は、重複して何度も出現することはありません。したがって $buffer はキーが存在しているかどうかだけを管理すればよく、個数を管理する必要はありません。したがって次のようにコードを短くできます。

4c4
<         if ($buffer[$r] && $buffer[$r]-- . ($pairs[] = min($w, $r)) || ++$buffer[$w]);
---
>         if ($buffer[$r] && ($pairs[] = min($w, $r)) || ++$buffer[$w]);

逆から読んで同じになる単語以外は各々一回しか出現しない · y-uti/poh6-anagram-codegolf@5d4439b · GitHub

また、出力の最後に改行がなくてもテストケースをパスします。

12c12
< echo $upper = join($pairs), $center, strrev($upper), "\n";
---
> echo $upper = join($pairs), $center, strrev($upper);

最後の改行の出力は不要 · y-uti/poh6-anagram-codegolf@4c4566b · GitHub

$centers の管理をやめたことによって unset 文が無くなったので、三項演算子を用いて if 文を置き換えます。

3,7c3
<     if ($w != ($r = strrev($w)) | $w > 0) {
<         if ($buffer[$r] && ($pairs[] = min($w, $r)) || ++$buffer[$w]);
<     } else {
<         $center .= $w;
<     }
---
>     $w != ($r = strrev($w)) | $w > 0 ? $buffer[$r] ? $pairs[] = min($w, $r) : ++$buffer[$w] : $center .= $w;

if 文を三項演算子に置き換え · y-uti/poh6-anagram-codegolf@3e91e20 · GitHub

あとは先ほどと同様に、余分な括弧、空白、改行をすべて除去して、各変数を一文字に変更します。最終的に 137 バイトになります。
137 バイトのコード · y-uti/poh6-anagram-codegolf@c3991b4 · GitHub

*1:公式には、あくまでも処理速度を競う形式で、コードの短さを競うというアナウンスがされていたわけではありません。

*2:今回の記事のために清書しているので、実際に提出したコードと完全には一致していません。

*3:$pairs を key-value ペアにしたり、最初に全単語を読み込んで array_count_values で変換したりして、同一単語をまとめてから処理する方法も考えられます。それぞれ、テストデータにおける単語の出現頻度によって得失があります。今回のオンラインハッカソンのテストケースでは処理速度上のメリットがなさそうだったので、採用しませんでした。

*4:オンラインハッカソンの問題の条件では単語数は 1 以上 1,000 以下なので、$w が 0 の場合を気にする必要はありません。

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

paiza オンラインハッカソンでコードゴルフに挑戦

問題の条件を満たす範囲のコード短縮

オンラインハッカソンのテストケースに特化したコード短縮