+
+

更新履歴

+
    +
  1. + : 公開 +
    2. +
+
+
+

はじめに

+

+ YAPC::Fukuoka 2025 に際してカヤックさんが開催されていたコードゴルフコンテスト、Anybatross に参加し、優勝した。この記事では自分の回答について解説する。 +

+

+ なお今回のシステムでは、現在の自分のスコア以下のコードを開催中も閲覧できる仕様だった。Hole 1 では特に使わなかったが、Hole 2 では途中他の方のコードをベースに進めた箇所がある (詳しくは後述)。 +

+

+ このコンテストは何度か開催されており、前々回 に参加したときは総合 2 位だった (前回開催は不参加)。 +

+
+
+

Hole 1

+
+

回答 (45 byte)

+
+ 
print$a+=$\=y/8B/0/+y/0469ADO-R//.$/,","for<>
+
+

+ Hole 1 については同一言語・同一スコアの回答が複数あるので詳細は省略する。 +

+
+
+
+

Hole 2

+

+ こちらは縮めていった過程も記載する。 +

+
+

回答 A (107 byte)

+

+ 最終スコアを見ると 4 位タイ (107 byte) が多く、3 位以上の回答と明確にアルゴリズムの差があるのでここから解説をスタートしようと思う。 +

+
+ 
s=gets
+?A.upto(?Z){(b,),m=s.scan(/(?=(.\B.))/).tally.max_by{_2}
+m>1&&(s.gsub!b,it;$*<<it+?:+b)}
+puts$**?,,s
+
+

+ 変数名などの細かい差異を除けば他の 107 byte 回答と同じだが、 String#scan に渡す正規表現にこれを採用していたのは私だけだったのではないだろうか。 /(?=(\S\S))/ や /(?=(\w\w))/ と比べて短くはならないので意味はない。 +

+

+ String#scan はマッチした文字列を「消費」するので、重複した範囲を切り出す必要のある bi-gram の生成には使えない。そこで、肯定先読み ((?=pattern)) を使う。これは ^ や \b などと同様に、条件を指定しているだけでゼロ幅なので、String#scan に消費されない。これを使えば bi-gram の生成ができる。ただし、s.scan(/\S\S/) などと書いた場合とは異なり、返る配列が [["la"], ["au"], ["un"], ...] のような形でネストすることに注意。 +

+

+ 出現頻度を調べるのには Enumerable#tally が使える。Perl に対する強烈な優位性はここで、これを使えばキーが各配列の要素、値が出現回数であるようなハッシュが一発で生成できる。 +

+

+ Enumerable#max_by で最頻値を取ってきた後は、多重代入を使って必要な値を取り出している。 +

+
+ 
x = [["la"], 3]
+(b,),m = x
+# => b = "la", m = 3
+
+

+ 置換テーブルのデータは $* へと追加しているが、これは Ruby の特殊変数で、本来は Object::ARGV を指す。ここでは単に最初から空配列で初期化されている便利な入れ物として用いている。 +

+

+ その他、?A や String#*、it、numbered parameters などの細かいテクニックについては、「Ruby コードゴルフ」で調べるか、最近の Ruby のリリースノートを読むと見つかるはず。 +

+
+
+

回答 B (107 byte)

+

+ 回答 A をぐっと睨むと、m>1&&(...) の括弧を削りたくなる。しかしそれには m>1&& がどうしても邪魔になる。というわけで終了条件を工夫することでなんとか m を排除できないかを考えた。それがこちら。 +

+
+ 
s=gets
+?A.upto(?Z){(b,),=(?_+s).scan(/(?=(.\B.))/).tally.max_by{_2}
+$*<<it+?:+b if s.gsub!b,it}
+puts$**?,,s
+
+

+ s の先頭に番兵 _ を置くことで、bi-gram の出現頻度がすべて 1 になったとき、b へと代入される値が「_ + (s の先頭の文字)」になる。これを String#gsub! で置き換えようとすると、そのような文字列は s 中にないので置換が発生しない。String#gsub! は置換が起きなかったとき nil を返すので、これを使って条件分岐ができる。&& だと優先度の関係から String#gsub! の括弧が省略できないが、後置 if なら省略できる。 +

+

+ しかし、これだけでは回答 A とスコアは変わらない。これを短縮したものがこちら。 +

+
+
+

回答 C (106 byte)

+

+ Kernel#gets は、入力を特殊変数 $_ へ代入する。これは Perl 由来の挙動で、Ruby にはいくつか $_ を参照するものがある。これを使って変数 s を置き換えると次のようになる。 +

+
+ 
gets
+?A.upto(?Z){(b,),="_#$_".scan(/(?=(.\B.))/).tally.max_by{_2}
+$*<<it+?:+b if$_.gsub!b,it}
+puts$**?,,$_
+
+

+ これで 1 byte 縮む。 +

+
+
+

回答 D (104 byte)

+

+ 回答 C を眺めると、b への代入に文字を費やしすぎている。これを String#gsub! の第一引数に直接書いてはどうか。更に、直前のマッチしたパターンを指す特殊変数 $& を使えば、変数 b を排除できる。それがこちら。 +

+
+ 
gets
+?A.upto(?Z){$*<<it+?:+$&if$_.gsub!"_#$_".scan(/(?=(.\B.))/).tally.max_by{_2}[0][0],it}
+puts$**?,,$_
+
+

+ コードゴルフとして [0][0] は気になるところだが、それでも 2 byte 一気に縮まった。 +

+
+
+

回答 E (103 byte)

+

+ 回答 D を提出したことで tompng 氏のスコアを越え、氏のコードを閲覧できるようになった。そこから少し変更したものが、mame 氏と (変数名などの些事を除いて) 同じ以下のコードである。 +

+
+ 
s=gets
+?A.upto(?Z){s.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],1or($*<<it+?:+b;s.gsub!b,it)}
+puts$**?,,s
+
+

+ ここまでとは大きく異なる戦略で終了条件を判定している。使われているのはパターンマッチで、in がマッチの有無を true / false で返すことを利用している。or を用いて、最頻値の出現回数が 1 でないなら置換処理を継続する。 +

+

+ パターンマッチの利用については途中何度か検討したが、1 でないときに処理を実行するという方針で実装しようとしてしまい、上手く短縮できなかった。 +

+
+ 
# これは 106 byte
+s=gets
+?A.upto(?Z){s.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],2..and($*<<it+?:+b;s.gsub!b,it)}
+puts$**?,,s
+
+
+
+

回答 F (103 byte)

+

+ さて、ヒントを求めて 前回開催の公式解説ブログ を読んでいたところ、次のような興味深い記述を発見した。 +

+
+

+ 参加者のみなさんの最短解はshebangを書いてPerlのオプションを設定していい感じにやるものでしたが、(中略) 今回はチート抑止みたいなところの意図でperlコマンドを実行する方式になったので、ちゃんとshebangを書けば効くようになっていたのでした。 +

+
+

+ Shebang が使えるのなら、Ruby にも Perl に由来するオプションがいくつかあるので、似たような手段で短縮できるのではないか？ +

+

+ ruby で -p を付けると、以下のようなコードを書いたかのように動作する。 +

+
+ 
while gets
+  ... # 記載したコードの処理
+  puts $_
+end
+
+

+ また、Kernel#gsub という $_ = $_.gsub(...) と同様の処理をおこなうメソッドが生えてくる。今回は String#gsub! も使うので、shebang の分を回収できれば短縮になりそうだ。 +

+

+ というわけで、実はこれまでも shebang での短縮は何度か試していた。しかし、いずれも 1 byte 増えたり変化しなかったりで成果を上げられずにいた。回答 E についても同様に、以下のようなコードを作っていた。 +

+
+ 
#!ruby -p
+?A.upto(?Z){$_.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],1or($*<<it+?:+b;gsub b,it)}
+puts$**?,
+
+

+ しかしこれは 103 byte で縮められない。にっくきは gsub と b の間のスペースである。せっかく s.gsub! を gsub にしたのに、後ろが記号でなくなったことでスペースが生じている。といって、括弧を付けるのも上手くはいかない。 +

+
+ 
# これも同じく 103 byte
+#!ruby -p
+?A.upto(?Z){$_.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],1or$*<<it+?:+b&&gsub(b,it)}
+puts$**?,
+
+

+ 外側の括弧を移動させてくれば gsub と b の間のスペースを消せるが、; を && にせねばならず失敗する。この問題を解決したのが最終回答の 102 byte コードである。 +

+
+
+

最終回答 (102 byte)

+
+ 
#!ruby -p
+?A.upto(?Z){$_.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],1or$*<<it+?:+b%gsub(b,it)}
+puts$**?,
+
+

+ String#% は文字列のフォーマット処理をおこなう演算子だが、ここでは特にフォーマット目的で呼んでいるわけではない。ここで重要なのは、この演算子が特に副作用を持たず、どんな型でも右辺に取れることである。b の中身にフォーマット指定子はない (% などの記号が入力されないことが問題文から分かる) ので、誤って動作を壊してしまうおそれもない。 +

+

+ これによって Hole 2 の単独 1 位スコアとなった。 +

+
+
+
+

LLM のコードゴルフ性能

+

+ ところで、今回スコア短縮に行き詰まったあたりから LLM を使ってみた (コンテストのレギュレーションとして明示的に利用が許可されている)。 +

+

+ 結論から言うと役には立たなかった。サンプルコードを縮めるくらいの用途には使えるかもしれないが (未検証)、すでに人間がある程度のところまで縮めたコードを更に短縮するのはまだ荷が重いようだ。そもそもそれで縮まって楽しいのかという別の問題もある。 +

+

+ なお、LLM は文字数カウントを大の苦手としているので、縮めた (と言い張っている) コードを wc コマンドに渡し、その結果を LLM に見てもらった方がよい。 +

+
+
+

おわりに

+

+ 楽しかったです。運営のみなさま、ありがとうございました！ +

+
+