こんにちは、技術部の谷脇です。
去る2月10日に行われたYAPC::Hiroshima2024ですが、みなさまはいかがだったでしょうか。私は参加して大満足であり、運営の方々に大感謝させていただきます。
さて、カヤックではゴールドスポンサーと椅子スポンサーをしていたというのは開催直前に出した記事で述べさせていただきました。
この記事では伏せられていた、椅子スポンサーのPerlbatrossですが、この記事ではPerlbatrossの内容紹介と問題解説をしようと思います。
Perlbatrossとは
YAPC::Hiroshima2024の開催期間中にコードゴルフの問題を出していました。以下は椅子スポンサーで貼らせていただいた問題です。
さて、これだけではなく、QRコードにアクセスすると実際に問題を解けるサイトがあります。こちらがPerlbatrossです。問題は4つありました。またランキング形式になっており、各4問を最もコードを短くできた方が上の方に乗っています。また開催中は見れませんでしたが、他の方のコードも今は見れるようにしていますので、ぜひアクセスしてみてください。
⛳ Perlbatross閉幕〜! 参加ありがとうございました。
— カヤック技術部ブログ (@tech_kayac_com) 2024年2月13日
最終順位は以下です。「なるほどそうきたか〜」と唸るコードが沢山投稿されて感激です。
他の方のコードも見れますので、ご興味のある方は御覧ください。https://t.co/Ll25U6s6fP
またカヤック技術部ブログで後日解説をアップします。 #yapcjapan pic.twitter.com/2SBgmXZ75z
それぞれの問題は標準入力で与えたデータを処理し、規定されている出力に加工する形式になっています。検証を行うための仕組みもサイトに組み込まれていました。
問題の解説と講評
ここではPerlbatrossで出題した問題を解説していきます。
Hole1: Split of Grapheme
問題
https://perlbatross.kayac.com/challenge/1
標準入力に文字列が与えられます。
1行ごとに奇数文字目を結合したものと、同じ行数に偶数文字目を結合したものを半角スペース区切りで分けて出力してください。入力は1行当たり偶数文字数のものしかないとします。
入力例: パタトクカシーー
出力例: パトカー タクシー
元ネタは言語処理100本ノックの第1章1問目です。ですが、タイトルにあるGraphemeの通り、ひねりを加えています。以下はテストケース2の入力例と出力例です。
入力例
ABCD 😊🐱🐶🐭 あAいBうC 🌟星🌙月 🍎🚗🍌📚 #️⃣1️⃣2️⃣3️⃣ 🧑🤝🧑👫 👨👩👦👦👨👩👧 👨🏻👩🏼👦🏽👧🏾 ★☆♡♢
出力例
AC BD 😊🐶 🐱🐭 あいう ABC 🌟🌙 星月 🍎🍌 🚗📚 #️⃣2️⃣ 1️⃣3️⃣ 🧑🤝🧑 👫 👨👩👦👦 👨👩👧 👨🏻👦🏽 👩🏼👧🏾 ★♡ ☆♢
途中までは良いのですが、「1️⃣」あたりから怪しくなります。以下のワンライナーでこの文字のUnicodeでの名前を見てみましょう。
$ perl -Mcharnames\ qw/:full/ -E 'use utf8; say charnames::viacode(ord($_)) for split //, "1️⃣"'; DIGIT ONE VARIATION SELECTOR-16 COMBINING ENCLOSING KEYCAP
このように、この記号は複数の文字で構成されています。でも人の目で見ると1文字ですよね。この人の目から見た文字の単位をUnicodeでは書記素(Grapheme)クラスターと呼びます。
もう一つ、「🧑🤝🧑」を見てみましょう。
$ perl -Mcharnames\ qw/:full/ -E 'use utf8; say charnames::viacode(ord($_)) for split //, "🧑<200d>🤝<200d>🧑"'; ADULT ZERO WIDTH JOINER HANDSHAKE ZERO WIDTH JOINER ADULT
文字単位でも仲良く手を繋いでいますね。このように、絵文字がたくさん使われる現代では、人の感覚と合致する文字数のカウントであったり、分割というのは難しいよという問題なのでした。
ちなみに初期実装のコードでは正規表現の\Xを使って書記素クラスター単位の抜き出しをしています。
ベスト回答
1位だったKarakasaDcFdさんの回答を見てみましょう。
(utf8'decode$_)^print/(\X)\X/g,$",/\X(\X)/g,$/for<>
これで51バイトという記録でした。おめでとうございます。
まず、問題にある「1行ごとにsplitしていく」という部分ですが、それは末尾のfor<>で示されています。これはfor my $_ (<STDIN>) { ... }の略です。Perlは普通のループの場合と違って後置ループはカッコが省略できます。また、foreachやwhileも同様の目的に使えますが、この場合はforが最も文字数が少なくなります。また、このコード全体は1つのstatementですが、Perlはブロックやコード全体の末尾のセミコロンを省略できます。
さらに初期実装コードにあった入力値のUnicode decodeですが、Encodeモジュールから最初から使えるutf8プラグマに切り替わっています。utf8プラグマでもdecodeできるというのは普段ではあまり使わないですが、これで3文字の省略です。そして、'がパッケージの区切り文字に使われています。Perl5(現行バージョン)のパッケージの区切り文字は::ですが、Perl4の時代では'でした。後方互換性の観点から今でも'を使えます。しかし、非推奨かつ5.42で廃止予定です。実際にテスト出力で以下の警告が出ています。YAPC::Hiroshimaでも「2024年冬のPerl」というトークでもこの話が出ましたね。
Old package separator "'" deprecated at /tmp/tdKmQucCMy/YAZ0lfwj line 1.
また、EncodeモジュールのEncode::decode_utf8と違いutf8::decodeは結果を返すのではなく、与えた変数の中身を書き換えるので、その点でもコードゴルフ向きと言えます。また、Perlは関数呼び出し時のカッコを省略できるため、utf8'decode$_でutf8::decode($_)と同じ意味になるのでした。
さて次ですが、このdecodeのあとに^演算子で接続されています。これは排他的論理和です。全体を一つのstatementにし、forループの中にいれるために^を使っていると思われます。utf8::decodeは1を返すので、他にも&&や||も使えると思いきや、演算子の結合の強度として、これらは$_にくっついてしまいます。他にも+なども使えるようでした。
そして/(\X)\X/のように正規表現マッチで奇数個目と偶数個目を取り出していきます。ここで面白いのは、$"と$/です。これらは、Perlの特殊変数ですが、それぞれリスト区切り文字と入力レコードセパレーターです。前者はprint "@array"のように配列を文字列内で展開する際に使われる区切り文字でデフォルトではスペースが入っています。後者はfor <STDIN>のように入力値を区切るときに使うもので、デフォルトでは改行が入っています。ここでは" "と"\n"を省略して書くために特殊変数が使われています。
Hole2: The bombe
問題
標準入力に暗号文が入力されます。暗号は換字式暗号であり、アルファベット順で以下の例のようにシフトされています。
例1: シフト量1の場合
a->bb->cz->a例2: シフト量-1の場合
b->aa->zz->y平文は小文字のアルファベットのみ使用されています。
シフト数は不明です。またシフト数は行ごとに変わります。
入力された暗号文の先頭には必ず平文で
yapcという単語が入っています。一行ごとに解読した平文を出してください。
よくあるシーザー暗号ですが、ひねりとしてはシフト量が事前にわからないという問題になっています。「The bombe」というタイトルですが、チューリングマシンやチューリング完全などに名を残す計算機科学者のアラン・チューリングが第二次大戦中に開発した暗号解読機「Bombe」に由来しています。この暗号解読機はドイツ軍のエニグマ暗号を解くために開発されたものです。Bombe、暗号文でよく使われていたフレーズを手がかりにエニグマ暗号機の設定を推測するというものでした。エニグマ暗号はシーザー暗号よりかなり複雑ですが、今回の問題はBombeと同様にyapcを手がかりにシフト量を推測するというものでした。
ベスト回答
こちらもKarakusaDcFdさんの回答が1位でした。おめでとうございます。
eval'y/a-z/za-y/;'x(9+ord),print for<>
記録は38バイトでした。パーが105だったので、スコアは-67でした。驚異的ですね。
では解説をしていきましょう。for<>で1行毎に処理を回しているのはHole1と同様です。そして文字列evalをしていますね。ここでy/a-z/za-y/はtr/a-z/za-y/と同じ意味です。yを使うことで1文字節約になっています。さてこれで、aがzに、bがaにと-1ずつシフトしていきます。これだけだとすべての行がシフト量-1のシーザー暗号として処理されます。
そこで出てくるのがx(9+ord)です。ここでのxは左辺値の文字列を右辺値分繰り返す演算子です。
ordを見てきましょう。こちらは与えられた文字をascii上のコードポイントに変換する組み込み関数です。省略された場合は$_になり、また複数の文字からなる文字列が与えられた場合は、最初の文字を評価するとされています。最初の文字はyがn個分シフトされた文字ですね。yはコードポイントでいうと121です。121+9は130ですね。
もし1文字目がyだった場合、y/a-z/za-y/を130回分繰り返すコードが生成されます。130回ローテートするとどうなるでしょうか？ アルファベット26文字で一周するので26の剰余分が実際のシフト量(マイナス)であると言えます。130mod26は0になるので、yに戻ってきます。
同様に、一文字目がzの場合は131になるので-1文字分シフトします。というように、力技でどんどんシフトするコードをこの短い文字数で生成しているのでした。最後に引数無しでprintしていますが、y/.../.../は$_に作用し、printは引数がない場合は$_を出力します。またy/a-z/za-y/は入力の末尾にある改行コードには反応しないため、改行も一緒に出力されるのでOK、というものでした。
Hole3: Apache's Call
問題
標準入力にApache combined logにリクエスト処理時間(マイクロ秒)を付与した形式のログが与えられます。
参考としてLogFormatの書式を示します。
LogFormat "%h %l %u %t \"%r\" %>s %b \"%{Referer}i\" \"%{User-agent}i\" %D"
また、入力例は以下です。
127.0.0.1 - - [10/Feb/2024:15:16:17 +0900] "GET /challenge/9 HTTP/1.1" 200 2326 "https://perlbatross.kayac.com/" "Mozilla/4.08 [en] (Win98; I ;Nav)" 123456
ログを1分ごとのウィンドウに区切って処理した上で、1行あたり1ウィンドウの出力として、以下の指標を順番にスペース区切りで標準出力に出してください。
2xxリクエストの数 3xxリクエストの数 4xxリクエストの数 5xxリクエストの数 また、5xxリクエストの数が10を超えるウィンドウが現れた場合は、そのウィンドウの結果を出力後に処理を打ち切り即座にプログラムを終了してください。
なお、ログは時系列で並んでいるとします。
これまでとは異なり実用的なネタです。私はこのようなアクセスログをなどをワンライナーで解析することがあります。ただ、ApacheのCombined Logはパースが難しく、実務的にはltsvやJSONで吐いていることが多いですね。
ベスト回答
Hole3のベストはsugyanさんの回答でした。おめでとうございます。
for(<>){/(\d+).{3} .*?" (.)/;($h[$1]||=[(0)x4])->[$2-2]++}for(@h){print"@$_$/"if$_;last if$_->[3]>10}
長さは101バイトで、このHoleはパーが190だったので、スコアは-89でした。素晴らしいですね。では解説をしていきましょう。
B::Deparseを使って、省略されている部分も表示してみます。
$ perl -MO=Deparse -e 'for(<>){/(\d+).{3} .*?" (.)/;($h[$1]||=[(0)x4])->[$2-2]++}for(@h){print"@$_$/"if$_;last if$_->[3]>10}' foreach $_ (readline ARGV) { /(\d+).{3} .*?" (.)/; ++($h[$1] ||= [(0) x 4])->[$2 - 2]; } foreach $_ (@h) { print "@$_$/" if $_; last if $_->[3] > 10; }
実は<>は@ARGVに書かれたファイル名から読むという演算子であり、@ARGVが空であれば標準入力から読みます。
さて最初の/(\d+).{3} .*?" (.)/;ですが、(\d+).{3}は数字が1文字以上あり、その後何らかの文字が3つ続いたあとに空白がある箇所にマッチします。例をもとに先頭から読んでいった場合、それに初めて合致するのは 16:17の部分になります。もしIPアドレスが127.0.0.1以外ではなく4オクテット目に2桁の数字が入っていた場合はそちらにマッチしていたでしょう。しかし、テストケースがすべて127.0.0.1であったため、こちらで分をキャプチャすることができていました。
そのあとの.*?"でダブルクオートとスペースが連続する最初の箇所まで読み飛ばしています。*?は非貪欲マッチであり、もしこれが*だけであった場合は一番最後のUser-Agentの部分まで読み飛ばしてしまいます。そして、その後に出てきた1文字、つまりステータスコードの先頭の1文字をキャプチャしています。キャプチャした結果はそれぞれ順番に$1と$2に入ります。
$h[$1] ||= [(0) x 4]を見ていきます。$h[$1]は配列アクセスです。つまり、$1が16であれば、@hの16個目の要素にアクセスします。ところでこの場合、@hに何も入っていない状態でいきなり添字16の要素にアクセスした場合、0から16までの要素がすべてundefに初期化されます。そこで ||=が効いてくるわけですが、これは左辺値がfalsyである場合に右辺値を代入します。右辺値は[(0) x 4]ですね。先ほども出たx演算子ですが、先ほどとと違い左辺値がリストなので、この場合は(0, 0, 0, 0)というリストを生成します。そして、[...]は配列リファレンスなので、[0, 0, 0, 0]という配列リファレンスがめでたく右辺に代入されるわけです。
さて、次は++($h[$1] ||= [(0) x 4])->[$2 - 2];ですね。@hの各要素には配列リファレンスが入っているので、2次元配列の状態になっています。そこで->[$2-2]で分ごと要素のさらに現れたステータスコードの数を表す要素にアクセスしています。$2 - 2なので2xxの場合は0番目、5xxの場合は3番目ですね。そして最後に++でインクリメントします。というわけですね。
そして、後半のforですが、このプログラムは実は1行毎に逐次回していくのではなく、入力をすべて読みこんで集計したうえで表示を最後に行っています。つまり集計部のループと表示部のループが分かれています。
print "@$_$/" if $_; の解説をします。if $_で@hの各要素がfalsyであれば表示はしません。先程0から15番目まではundefが入ってしまっているという話がありましたが、それはここで省かれています。そして@$_ですが、各要素には配列リファレンスが入っているのでこれをデリファレンスしてあげます。文字列内で配列を展開するとデフォルトではスペース区切りで表示されますから、問題で求められている形式に合います。そして先程もでた$/ですね。改行コードが入っているので、1つのループごとに改行されていきます。
そして問題にある「5xxリクエストの数が10を超えるウィンドウが現れた場合は、そのウィンドウの結果を出力後に処理を打ち切り即座にプログラムを終了してください。」ですが、こちらはシンプルにlast if $_->[3] > 10;で実現していました。
ぎゅっと短く書かれているとドキッとしますが、B::Deparseを使うとシンプルなアルゴリズムを工夫して短く書いていることがよくわかりますね。
Hole4: Pytecode
問題
独自のプログラミング言語の命令と値が改行区切りで渡されます。
このプログラミング言語には変数はなく、ただ1つのスタックが存在します。以下の文章ではスタックの一番上の値をスタックトップと言います。
命令表
- 二項演算子
+-*/%: スタックトップとスタックの次の値を取り出して演算子を適用してスタックトップに積みます- 比較演算子
=!=<><=>=: スタックトップとスタックの次の値を取り出して比較し、条件に一致すれば1をスタックトップに積み、そうでなければ0を積みますdup: スタックトップの値を複製してスタックの上に更に積みますdrop: スタックトップの値を取り出して破棄しますswap: スタックトップとスタックの次の値を入れ替えます.: スタックトップを取り出して標準出力へ出力しますcr: 改行を標準出力へ出力しますif〜else〜then: スタックトップの値が1である場合はifとelseの間の命令を実行します。スタックトップの値が0である場合はelseとthenの間の命令を実行します。elseは省略できませんbegin〜until: まず、beginからuntilの間の命令を実行し、untilに到達したらスタックトップから値を取り出し、この値が0であれば、beginの次の命令まで戻ります。1以外であれば、untilの次の命令に移りますこれ以外の値が入力された場合はスタックトップに積みます
元ネタはForthというプログラミング言語です。本物は命令の区切り文字が改行ではなくスペースですが、それ以外はほぼ同じ仕様です。ただ、命令が足りなくこれだけでは普通にプログラミングを行うはかなり困難です。私もテスト用の入力コードを書く際は大変苦労しました。
ベスト回答
1位はKarakasaDcFdさんのスコア-194です。おめでとうございます。こちらの解説は後日出す予定の「チート・グリッチ編」で解説するとして、2位のnsfisisさんの回答を見ていきます。こちらはスコア-107でした。
$_='@q=<>;while($_=$q[$c++]){if(/^i/){$n=!#;($_=$q[$c++])=~/^i`$n++"^e/&&$n--while$n;}elsif(/^e/){$n=1;($_=$q[$c++])=~/^e`$n++"th/&&$n--while$n;}else{/^=`%,#==#"\.`print #"du`%,$s[-1]"dr`#"^s`%,#,#"c`print$/"th`0"b`push@u,$c-1"^u`(#?$c:$d)=pop@u"[^!-\/<>\n]+`%,$&:($i=#,$j=#,%,eval$j.$_.$i);}}';s'%'push@s'g;s'#'pop@s'g;s'`'/?'g;s'"':/'g;eval;
スタック指向のインタプリタを実装する場合の戦略が初期実装と比べてもそこまでは変わっていません。初期実装は命令列を配列で持ち、プログラムカウンタも変数で持ちます。全体のスタックは配列で持っていましたが、ifやループはPerl自身の関数のコールスタックを利用していました。本当はこれもプログラムカウンタの戻り位置を覚えることで素朴に実装しようとしたのですが、バグが取り切れず間に合わなかったというのがあります。
さてこのコードはどうでしょうか。まず、全体のコードを圧縮するために定型的に出てくるようなpush @sのようなものを%や#に置き換えて定義しておき、正規表現で置き換えてから実行しているというのがあります。s'%'push@s'g; s'#'pop@s'g;s''/?'g;` の部分がそうですね。他の方の回答でも、push/popのような頻出コードは関数にまとめたりなどの工夫が見られます。
コードの全体を把握するには、一旦置換を行ったあとのコード文字列をB::Deparseして見るのが良さそうです。そうしてみたのが以下です。
@q = readline ARGV; while ($_ = $q[$c++]) { if (/^i/) { $n = !pop(@s); ($_ = $q[$c++]) =~ /^i/ ? ++$n : /^e/ && --$n while $n; } elsif (/^e/) { $n = 1; ($_ = $q[$c++]) =~ /^e/ ? ++$n : /th/ && --$n while $n; } else { /^=/ ? push(@s, pop @s == pop @s) : (/\./ ? print(pop @s) : (/du/ ? push(@s, $s[-1]) : (/dr/ ? pop @s : (/^s/ ? push(@s, pop @s, pop @s) : (/c/ ? print($/) : (/th/ ? '???' : (/b/ ? push(@u, $c - 1) : (/^u/ ? pop @s ? $c : $d = pop @u : (m[[^!-/<>\n]+] ? push(@s, $&) : ($i = pop @s, $j = pop @s, push(@s, eval $j . $_ . $i))))))))))); } }
では見ていきましょう。@qに命令全体を読み込み、$cをプログラムカウンタとするのは初期実装と代わりありません。一方で違うのは命令列の解析方法です。初期実装では文字列の完全一致で行っていたのを、この回答では正規表現で短く書いています。例えばifであれば/^i/で済ましています。もしスタックに積む文字列としてiから始まるものがテストケースに含まれていたらこの回答は通りませんでしたが、テストコードにはそういった意地悪なものが含まれていなかったので、こちらで問題ありませんでした。またelseが現れた場合も/^e/で判定していますね。ifのスタックの深さに関しては$nで判定しています。そして$nが0になるまでスキップしています。これでifがtrueの場合にelseの中をスキップするコードが実現されています。
その他の部分は巨大な三項演算子で実現されていますが、一旦見やすくするとこんな感じです。
if (/^=/) { # = push(@s, pop @s == pop @s); } elsif (/\./) { # . print(pop @s); } elsif (/du/) { # dup push(@s, $s[-1]); } elsif (/dr/) { # drop pop @s; } elsif (/^s/) { # swap push(@s, pop @s, pop @s); } elsif (/c/) { # cr print($/); } elsif (/th/) { # then '???'; } elsif (/b/) { # begin push(@u, $c - 1); } elsif (/^u/) { # until if (pop @s) { $c; } else { $d = pop @u; } } elsif (m[[^!-/<>\n]+]) { # 命令以外 push(@s, $&); } else { # 演算子 $i = pop @s; $j = pop @s; push(@s, eval $j . $_ . $i); }
今回のテストケースが通るような最小限の正規表現で実現しているのがよくわかります。ちなみに$&は最後に正規表現でマッチした文字列が入る特殊変数です。
他の方の回答では三項演算子の他にも廃止予定のgiven/whenを使っている方もいました。ちなみに上位の回答にはありませんでしたが、私が自ら解いたときには、命令全体をPerlのコードにコンパイルするアプローチを取りました。
@t=<>;$p="(pop\@s)";sub o{push@s,@_};for$i(0..$#t){$_=$t[$i];chomp;if(s/^if$/if($p==1){/) {}elsif(s/^else$/}else{/) {}elsif(s/^then$/}/){}elsif(s/^begin$/do{/){}elsif(s/^until$/}while($p!=0);/){}elsif(s!^([+\-*/%])!(\$c,\$d)=($p,$p);o(\$d$1\$c);!){}elsif(s/^cr/print"\n";/g){}elsif(s!^\.!print$p;!g){}elsif(s/^dup/o(\$s[$#s]);/){}elsif(s/^drop/$p;/){}elsif(s/^swap/(\$c,\$d)=($p,$p);o(\$c,\$d);/){}elsif(s/^(!=|<|>|<=|>=)/if($p$1$p){o(1);}else{o(0);}/){}elsif(s/^=$/if($p==$p){o(1);}else{o(0);}/){}else{s/^(.*)$/o(\'$1\');/g;}$t[$i]=$_;}eval"@t";
まだまだ削れる気はしますが、スコアは+96です。
まとめ
というわけで総合1位はKarakasaDcFdさんのスコア-401です。おめでとうございます。
私自身も今回のコードゴルフの作問で大変勉強させていただきました。またまだまだPerlの知らない機能がたくさんあることを知れました。短く書くというのは、現代のプログラミング環境においてはあまり歓迎されませんが、こういったホビーとしてのプログラミングでは大変おもしろいものだと感じます。また、テキスト処理を行うためのPerlの価値というのもまだまだ捨てたもんじゃないと私は思います。
私は今でも仕事でアドホックに使うPerlのワンライナーを書く機会がありますが、皆様はいかがでしょうか。たまにはPerlのことも思い出してくださいね。
また、このコードゴルフの企画が面白かったなと思う方はぜひXのカヤック技術部アカウントをフォローしてください。反響が多ければまた次も同じようなことをやるかもしれません。
では次はチート・グリッチ編の解説でお会いしましょう。他にも今回のジャッジサーバーの仕組みなども解説してコードを公開して締める、といったことを予定しています。上記Xアカウントをフォローしておけばすぐに見れますので是非フォローしてください。
