🦜

YAPC::Hakodate 2024 Perlbatross参戦記（ネタばれ含む）

に公開
Perl
codegolf
idea

注意

はじめに

最近は Perl を書くこともほとんどなくなり YAPC にも参加していなかったのですが、2024年の YAPC::Hakodate にてコードゴルフの企画 Perlbatross があるという情報が X で流れてきたので、今回はその参戦記を書いていきます。
筆者は元々10年以上前に盛り上がっていた codegolf.com で Perl で遊んでいたので、昔取った杵柄でいけるだろうと踏んでの参加です。

以下では最終的な提出コードと、そこに至るまでのステップを少し紹介することでコードゴルフのテクニックを紹介していきます。実際にはここに記載した以上に試行錯誤をしています。

Perlbatross のルールとして、自分の提出したコードと同じかより長い場合に限り他の人の提出コードを見ることが出来る、というルールがありました。そのため、解いている途中で他人のコードを参照することも出来ました。

最終結果はホール 1がスコア-36で単独首位、ホール 2がスコア-35で同率首位（提出順で負け）、総合-71で首位でした。

コードゴルフの解き方

コードゴルフでは同じ処理を短く出来るような書き方の工夫も大事ですが、そもそものアルゴリズムを変えることでより短く書けることも多いです。
そのため、それぞれの問題に対して複数のアルゴリズムを考え、それぞれを最適化していき、最終的に一番短かったコードを採用するというのが基本的な流れになります。

ホール1

問題

問題はこちら

1行の中のスペース区切りの単語リストがアナグラムの関係になっているかどうかを全行に対してチェックするという問題です。
アナグラムの関係であれば 1 そうでなければ 0 を出力するというものです。
10数年前の codegolf.com では出てこなかったような UTF-8 文字列をちゃんと扱えるかどうかの問題が出てきましたので、そのあたりの知識のアップデートが必要でした。

基本方針

こういう風に1行ごとに何かして1行出力しなさい、という問題は while(<>) { ...; print ...} という感じの処理になるわけですが、
この書き方は長くなるので、コードゴルフでの最終的な解になることはほぼないです。
基本的にこの形が出た場合は次のような形で shebang を使って perl のコマンドラインオプションを活用します。
（記事では表現出来ていないですが、最終行の改行コードは除去してから提出するのを忘れずに）

#!perl -p
$_=...

改行コードを良い感じ（詳しくは perldoc perlrun 参照）に処理する -l など、短く書くのに有用なオプションがいくつかあります。
この問題のように空白区切りの単語列が与えられる場合は -a を付けておくと @F に分割された単語が入るので、それを使って処理を進めていきます。
ついでに -l も付けておくと print で出力するときに自動で改行が付くので便利です。

アルゴリズム

アナグラムのチェックは、単語をソートして全部が一致しているか確認する方法が最も単純です。
全部が一致していることの確認方法は3種類考えてみました。

  1. 配列に入れて全部の要素が先頭と一致してるか確認する
  2. 全部連結した文字列にして最初から最後まで繰り返しになっているか正規表現で確認する
  3. ハッシュに入れてキーの数が1つか確認する

それぞれ大まかな実装を説明すると以下のような感じになります。

  1. @a==grep$_ eq$a[0],@a
  2. join''=~/^(.+)\1+$/
  3. %h=...;0+%h==1

実際にはしっかり実装して詰めていかないといけないのですが、3.の書き方が最も短いようです。

解答

素直に書いていくとこんな感じです

#!perl -lap
%m=map{utf8::decode$_;join("",sort/./g)=>1}@F;$_=%m>1^1

utf8::decode しておくことで正規表現の . が日本語文字などの1文字にマッチするようになります。
期待される出力は 1 と 0 ですが、perl の真偽値は文字列化すると 1 と空文字列なのでビット演算を使って良い感じに変換します。
変換方法はいくつかあって、同じ長さのものもあるのですが、今回は ^1 を使ってみました。

ここからもうちょっと縮めていくと、joinの第一引数の空文字列作っているところと utf8::decode の戻り値を捨ててるところが気になります。
utf8::decode は成功したときに真を返すので、文字列化すると 1 になります。これをjoinの第一引数に与えると、1文字ずつ 1 が挟まれることになりますが、全部に同じように入るので問題ありません。せっかくなのでこれを使います。

#!perl -lap
%m=map{join(utf8::decode($_),sort/./g)=>1}@F;$_=%m>1^1

こういう風に普段は使わないような戻り値を使ったりして短くすることも良くあるテクニックです。昔の記憶では、print の戻り値を 1 として使ったこともあります。

utf8::decode は昔の書き方で utf8'decode とも書けますし、%m に代入してるのも無駄な感じがします。これを使ってもう少し短くした以下が提出コードです。

#!perl -lap
$_=%{{map{join(utf8'decode($_),sort/./g),1}@F}}>1^1

ホール2

問題

問題はこちら

` か # の2つのどちらかの文字で構成されたアスキーアートを1/4にリサイズするという問題です。つまり、2行に対して1行を出力するということになります。

基本方針

2行に対して1行を出力するということは、言い換えると1行ごとに処理するコードに追加でもう1行先読みする処理を追加するということです。
これは以下のような感じで書けます。

#!perl -p
$n=<>;$_=...

あとはそれぞれの行を2文字ずつ取り出して2x2のブロックを作ってブロックごとにどちらの文字を出力すれば良いか判定すれば良いです。

アルゴリズム

単純なアルゴリズムとしては 4文字をひとまとめにした文字列が作れれば、y/#//で # の数を数えることが出来ます。

最初はこのアルゴリズムで進めていたのですが、ある程度短くしてすぎゃーんさんのコードが読めるようになったとき、以下のアルゴリズムを見つけました。

そのアルゴリズムはちょっとややこしいのですが

  1. 上の段が同じ文字ならその文字
  2. 下の段が同じ文字ならその文字
  3. そうでなければ左上の文字

という判定をします。1. の場合は上の段に2文字あるので、全体として2文字・3文字・4文字の場合があり、いずれの場合もその文字で良いです。
この判定が偽の場合は上の段は `# か #` のどちらかになります。 このとき、下の段が同じ文字ならその文字が3個になるのでその文字、
そうでなければ2個ずつということになるので左上の文字ということになります。

解答

'#' の数をカウントする方針をざっと書いてみると以下のようになりました。

#!perl -lp
$n=<>;$_=join"",map{/./;@a="##$&``"=~/./g;$n=~/../g;$_.=$&;$a[y/`//]}/../g

上の段は /../g をリストコンテキストで評価して map にかけています。下の段は /../g をスカラーコンテキストで評価して呼び出しごとに2文字ずつ読み進めていきます。
join map が無駄っぽいとか色々あるのですが、一旦この方針のことは置いておいて、別の方針を考えてみます。

2つ目のアルゴリズムで検討していきます。

#!perl -p
$n=<>;s!..!$_=$&;$n=~/../g;/(.)\1/||$&=~/(.)\1/||/(.)/;$1!ge

上の段はループの代わりに正規表現置換の s!!!ge を使って置き換えることにしました。この場合行末の改行文字が残るのでコマンドラインオプションの -l が不要になりました。
|| で連結しているので、最終的にマッチした正規表現の中のキャプチャグループが $1 に入るので、それを出力に使っています。
この辺りで期限の日の午前2時頃だったでしょうか。ひと眠りして11:40頃に起きたらすぎゃーんさんに抜かれていたのでちょっと考えて以下のコードで提出してスコア-35でフィニッシュでした。

#!perl -p
$n=<>;s!..!$_=$&;$n=~/(.)(.)/g;/(.)\1/||$1eq$2||/(.)/;$1!ge

あとのまつり

2024/10/7の12:00が締め切りだったのですが、その後の15時頃に考え直して、ホール2のアルゴリズムがもっと整理出来ました。
出力する文字は基本的には2x2ブロックの左上の文字を出力すれば良くて、唯一の例外は

`#
##

#`
``

のように、連結したときに ABBB の形になるときだけしかありません。

これを反映させると以下のようになり、スコア-37でした。

#!perl -p
$n=<>;s!..!$_=$&;$n=~/../g;$_.=$&;/.(.)\1\1/||/(.)/;$1!ge

経験からするとコマンドラインオプションが -p しかないときは shebang を外して print で書いた方が短くなることもあるので考慮しないとならないのですが、
今回は2行ずつ読み込むので、後置の for<> が使えなくて多分短くならない・・・かな？

今回全然検討出来ていなかったのですが、` と # の文字コードを利用して数値・ビット演算で謎の計算をするというアルゴリズムも考えられるかもしれません。
上手く出来るとめちゃくちゃ縮むことがあるので検討するべきなのですが、私はこのタイプのアルゴリズムが苦手なのであまり考えませんでした。

狂喜乱舞（追記: 2024/10/08 05:00頃）

更に考えたらスコア-44にまでなりました。

#!perl -p
@b=<>=~/../g;s!(.).!($&.shift@b)=~/.(.)\1\1/;$1!ge

もうちょっとだけ考えたら-45でした。詰めが甘いですね。

#!perl -p
@b=<>=~/../g;s!(.).!($&.shift@b)=~/(.)\1\1/;$1!ge

resultを読んで（追記: 2024/10/09/20:20頃）

やっぱり utf8::decode 消せるのかー。UTF-8と真面目に向きあうべきだった。

以下で スコア-42

#!perl -lap
$_=%{{map{join('',sort/\w|\W{3}/g),1}@F}}>1^1

join('',LIST) は長いので短縮してスコア-43

#!perl -lap
$_=%{{map{+"@{[sort/\w|\W{3}/g]}",1}@F}}>1^1

上にも書いたけどハッシュを使わない方針としてはもう一つ「文字列化して正規表現」があるけど、スコア-39止まり。

#!perl -lap
$_="@{[map{sort/\w|\W{3}/g}@F]} "=~/^(.+)\1+$/+0

おわりに

どちらの問題も割と正統派のゴルフ問題という感じで、程よく縮んでとても楽しかったです。運営の方々に感謝します。

Discussion