どうも谷脇です。お待たせいたしましたが、Anybatrossの講評です。
開催記事
Anybatrossの仕組みに関する解説記事
Anybatrossはいわゆるコードゴルフのコンテストです。与えられたお題を解くようなプログラムを書くのですが、このプログラムが短ければ短いほど良いです。この記事では上位回答者のコードについて解説しますが、Hole 1はコードゴルフの解き方について学ぶちょうどよい問題なので、入門という形でも解説していきます。
Hole 1. Counter Counter
問題文
アルファベットのAやBにあるような、文字の中にある閉じた空間のことをカウンターといいます。
0〜9までの10種と、アルファベット大文字のA〜Zの26種、合計36種の文字やその他の記号を利用した文字列が渡されるので、カウンターの数を数えてください。アルファベット小文字は来ません。その他の記号のカウンターは数えなくてよいです。
1行ずつ数えて、その行までの累積個数と、その行での出現個数を出力してください。
例
KAYAC
YAPC FUKUOKA
WHITE
POWAWA
*STRONG*: ZERO
↓
2,2
6,4
6,0
10,4
14,4
複数行の例
SNAKE CASE
WHITE SPACE
ITERATOR
TOKEN GENERATION
COMPILE ERROR
HASH MAP
2025 NOVEMBER
↓
2,2
4,2
8,4
12,4
18,6
21,3
26,5
参考: 文字ごとのカウンターの数
| 文字 | 個数 | 文字 | 個数 | 文字 | 個数 | 文字 | 個数 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | A | 1 | K | 0 | U | 0 |
| 1 | 0 | B | 2 | L | 0 | V | 0 |
| 2 | 0 | C | 0 | M | 0 | W | 0 |
| 3 | 0 | D | 1 | N | 0 | X | 0 |
| 4 | 1 | E | 0 | O | 1 | Y | 0 |
| 5 | 0 | F | 0 | P | 1 | Z | 0 |
| 6 | 1 | G | 0 | Q | 1 | ||
| 7 | 0 | H | 0 | R | 1 | ||
| 8 | 2 | I | 0 | S | 0 | ||
| 9 | 1 | J | 0 | T | 0 |
与えられた36種の文字から構成される文字列のうち、文字の形の中で囲まれている部分(カウンター)の合計を数えるというものです。なんじゃそりゃと思うかもしれませんが、各言語の初期コードに各文字のカウンター個数を示した表があるので、それを見ると何が言いたいかわかるかもしれません。
参考: Perlの対応表
our $COUNTER_MAP = { '0' => 1, '1' => 0, '2' => 0, '3' => 0, '4' => 1, '5' => 0, '6' => 1, '7' => 0, '8' => 2, '9' => 1, 'A' => 1, 'B' => 2, 'C' => 0, 'D' => 1, 'E' => 0, 'F' => 0, 'G' => 0, 'H' => 0, 'I' => 0, 'J' => 0, 'K' => 0, 'L' => 0, 'M' => 0, 'N' => 0, 'O' => 1, 'P' => 1, 'Q' => 1, 'R' => 1, 'S' => 0, 'T' => 0, 'U' => 0, 'V' => 0, 'W' => 0, 'X' => 0, 'Y' => 0, 'Z' => 0, };
初期コードを見てみると、バイト数の多くをこの対応表が占めています。なので、この対応表を圧縮したり、別の表現方法にしていくのが最初のステップです。例えば以下のようにしてみましょう。
our $COUNTER_MAP = { '0' => 1, '4' => 1, '6' => 1, '8' => 2, '9' => 1, 'A' => 1, 'B' => 2, 'D' => 1, 'O' => 1, 'P' => 1, 'Q' => 1, 'R' => 1, };
こうするとだいぶ圧縮できますよね。しかし、文字と数字のmapだと数字の部分が冗長に感じます。ハッシュではなく配列にしてしまうのはどうでしょうか。2個カウンターがある文字をどうするかという問題があります。具体的には8とBです。
配列中に2つ登場させるというアイデアはどうでしょうか。
@M = qw/0 4 6 8 8 9 A B B D O P Q R/;
これを使って、置き換えるコードを書いてみます。
for (<>) { $l=0; @s = split//; for $S (@s) { for (@M) { ++$t && ++$l if $S eq $_; } } print "$t,$l\n"; }
これで+54(154bytes)まできました。 さらに文法上問題がない程度に改行や空白を省くと+15(115bytes)です。
@M=qw/0 4 6 8 8 9 A B B D O P Q R/;for(<>){$l=0;@s=split//;for$S(@s){for(@M){++$t&&++$l if$S eq$_;}}print"$t,$l ";}
このように、データに依存するプログラムであれば、それを圧縮して表現します。また言語機能を用いて圧縮して書くというのもあります。また、高度なコードゴルフのプログラムでは、プログラムの中で2つの箇所に分かれている処理を一気に行うのもコード圧縮のために必須の考え方です。
では、各言語の一位の回答を見ていきましょう。
PHP
PHPでの1位はtakaramさんの回答でした。
+8(108bytes) でした。おめでとうございます。
<?for(;$l=fgets(STDIN);){for($i=$s=0;$i<14;)$s+=substr_count($l,'046889ABBDOPQR'[$i++]);echo@$t+=$s,",$s ";}
最初のfor(;$l=fgets(STDIN);)で1行ずつ標準入力から読んでいます。
その後のさらに内側のforループで$iと$sを初期化し、$i<14という終了条件があります。14というマジックナンバーはこのコードにおけるカウンターの対応表046889ABBDOPQRの文字数です。
substr_count関数で入力行の$lにあるカウンター文字の数を調べています。$iはここで文字列スライスのインデックスの形で登場しています。
$sに行ごとのカウンター数が加算されていき、最後にechoで出力しています。@$t+=$sと@がついているのは、最初のループの時点では$tが初期化前の変数のため、Warningが出てしまいます。その抑制のために@がついています。Warningが出るだけなら無視できるのでは？と思うかもしれませんが、今回の環境ではWarningが標準出力に出てしまうため、回答に混ざってしまいます。なので抑制する必要がありました。
なお、社内の事前回答ではもっと短いものもあったので紹介します。どこが違うか調べてみてくださいね。
<?for(;$l=fgets(STDIN);)echo@$t+=$c=($f='preg_match_all')('/[04689ABDO-R]/',$l)+$f('/[B8]/',$l),",$c ";
JavaScript
JavaScriptでの1位はdo7beさんの回答でした。
-10(90bytes) でした。おめでとうございます。
for(s=0;h=0,l=std.in.getline();print([s+=h,h]))for(k of l)for(c of'046889ABBDOPQR')h+=k==c
JavaScriptはQuickJS(厳密にはNG版)で動作しています。なので、標準入力はstd.in.getline()という形で使うようになっています。
最も外側のループでは、s, h を0に初期化し、lを標準入力から得られた1行、そして行ごとに実行される式としてprintがあります。ここで累積と各行のカウンター数を出しているんですね。
JavaScriptは文字列(ここではl)をofでループさせると、一文字ずつに分解してループできます。1
私が最初に書いたPerl版のように二重ループで文字の一致を行なっていき、hに行ごとのカウンター個数を加算しています。
Python
Pythonでの1位はalceaさんの回答でした。
-23(77bytes) でした。おめでとうございます。
c=0 while 1:s=sum(map('046889ABBDOPQR'.count,input()));c+=s;print(f'{c},{s}')
いきなり無限ループwhile 1:があるのですが、終了条件はどうなっているかというと、実行ログを見るとなるほどとなります。
Traceback (most recent call last):
File "//code.py", line 2, in <module>
while 1:s=sum(map('046889ABBDOPQR'.count,input()));c+=s;print(f'{c},{s}')
~~~~~^^
EOFError: EOF when reading a line
/var/task/script/../judge_local/test.t ..
EOFになった時にエラーになるのでそれで強制終了するようになっていました。今回のjudgeサーバーではexit statusを見ていなかったので、これが通ってしまっていたようです。
さて、カウント方法等は今まで紹介した言語と同様です。'046889ABBDOPQR'.count で関数オブジェクトが返ってきます。input()で得た標準入力の文字列がイテレータブルオブジェクトと解釈され、一文字ずつ'046889ABBDOPQR'に何回登場するかという処理がされています。その合計をsumでまとめて変数sに入れています。
Ruby
Rubyでの1位はmameさんの回答でした。
-36(64bytes) でした。おめでとうございます。
puts$<.map{|s|[$.+=~-n=%w(04689ABDO-R 8B).sum{s.count it},n]*?,}
一気にやってることがわからなくなってきましたね！ コードゴルフは極めていくとこのようにどこまでが何の処理だかぱっと見でわからなくなるのが醍醐味です。
いきなり標準出力への出力putsをしていますが、これは読み飛ばして、まずは$<ですね。これは標準入力を表す仮想ファイルです。2 なのでこのあとのmapは、標準入力に対してのメソッドです。mapのブロック内に渡される要素sは1行を表します。
$.は読んだファイルの行番号3なのですが、行番号としては使わず、0に初期化されている変数として用いています。つまりこの右辺はカウンターを数える計算をしているはず。
~-は最後にかかっているのでこれは一旦飛ばします。nは行ごとのカウンター数ですね。問題の%w(046789ABDO-R 8B)ですが、%w(...)は空白区切りの文字列の配列を作る記法です。つまりこの場合は、["04689ABDO-R", "8B"]と等価です。その配列のsumメソッドでs.count itとしています。sは標準入力の行です。itは配列の要素が入ります。ちなみにこのitは2024年12月にリリースされたRuby 3.4で実装されたものです4。最新機能ですね！ さて、s.countですが、countの引数には面白い機能があります。O-R のように-で繋げられた文字列が入力された場合、辞書順で文字を並べた際の間の文字を補完するように働きます。O-RはOPQRと同じ意味です。一文字削減になりますね。2つ目の8Bはカウンターが2つあるので、二重にカウントするためにこうなっています。
さてこれで1行のカウンター数が導けたので、nに代入します。Rubyは代入の結果が返ってくるので、それも$.に入れたいというか、実際そうなっているのですが、ここで注意点です。$.は初期状態では1が入っています。これに+=してしまうと、累計文字数が1多くなってしまいます。次の行にいく時にもインクリメントされてしまうので、各行でデクリメントが必要です。そこで~-の効果があります。~はビット反転です。整数をビット反転させた場合、-(<元々の整数>) - 1という整数となります。ここではさらに-で符号反転させてますから、~-がかかった整数は実質的には<元々の整数> - と等価です。デクリメントをすると1つの式で表現できず文字数が嵩むので、文字数を少なくするためにこのようなテクニックが使われているんですね。
そして、配列に累計カウンター数と1行のカウンター数を収めて、*?,しています。?,は,一文字を表します。クオートで囲むのに比べて一文字削減です。Rubyは便利だなあ。配列に*演算子で文字列をかけるとjoinと同じ効果です。Rubyは便利だなあ。というわけで、これがちゃんと通る回答になります。素晴らしいですね。
Perl
Perlでの1位はmoznionさんの回答でした。
-55(45bytes)でした。おめでとうございます。その他-55の方は多数いますが、最初に-55に到達したのはmoznionさんでした。
print$t+=$d=y/B8/A/+y/ADO-R0469//,",$d "for<>
Rubyの技巧的なコードゴルフに比べるとPerlは「それでいけるの？」という感じですね。解説しましょう。
$tを累計カウンター数とし、$dを1行のカウンター数にするのはRubyと同様。Rubyと違いPerlは未定義の変数に加算代入が使えてしまうというのは有利な点だと言えます。
飛んで末尾のfor<>ですが、後置forで、標準入力を1行ずつ読んでいます。<>で標準入力を読む時の省略記法です。読まれた行は変数$_に暗黙的に入ります。あと後置forの文は最初のprintまでかかっているので、1行ごとにこの式全体が実行されることになっています。
問題のカウント部分です。y/B8/A/+y/ADO-R0469//ですが、2回にわたって文字列置換をしています。y/B8/A/ の部分と y/ADO-R0469// の部分です。y/../../はtr/../../と等価です。yでやる方が一文字少なくてお得ですね。y/../../は基本的には$str =~ y/../../という形で置換対象文字列を=~で指定して使うのですが、省略することができます。省略した場合の置換対象文字列は$_が暗黙的に使われます。Perlって便利だなあ。y/../../を実行した際に返り値は置換が行われた文字数が返されます。最初のy/B8/A/で2つカウンターがある文字列をカウントした上で、もう一度カウントしたいのでAに変換します。そして2度目の文字列置換でカウントのみを行います。y/...//の場合は置換を行わず文字数カウントだけ行うような挙動を示します。Rubyのcountと同様、範囲演算子が使用できるのでO-RがOPQRになります。
また、改行を伴うprint関数sayはuse feature qw/say/;だとかuse v5.42;だとかをしないといけないので、文字数が嵩みます。そこで、print "$t,$d\n";のような形にするのが普通なのですが、この回答のように改行自体をダブルクオートに含めてしまうこともできます。これで一文字削減です。
こんな短いコードでもテクニックは潜んでいます。コードゴルフはいろんなことを教えてくれますね。
というわけで、Hole 1はPerlで解いたmoznionさんが最短でした。おめでとうございます。
Perl 1位タイの別解
もう一つ1位タイの別解のコードも共有します。
print$a+=$\=y/8B/0/+y/0469ADO-R//.$/,","for<>
nsfisisさんや、sugyanさんがこの回答をしています。
他の方の回答との違いは$\を使っている点です。特殊変数$\は「print 演算子のための出力レコードセパレータ」で、printを行う際の末尾にこの変数に入っている中身が一緒に出力されます。つまり、カウンター個数に関しては$\に入れて末尾に出力しています。また紛らわしいですが、$/という特殊変数も入れてます。これは入力レコードセパレータと呼ばれるもので、本来は入力に対して行の末尾の文字が何かを定義している変数ですが、ここでは改行文字をくっつけるために使用しています。
$\にはカウンター個数と改行文字が入るわけですが、じゃあ$aに対して+=しているのはどうなるのかというと、Perlは文字列を数値として解釈するとき、数値っぽい文字までを使用し、あとは捨てるという挙動を利用しています。$\に"1\n"が入っていたとしても、$aに加算されるのは1です。この式は$aの値が返ってくるため、累計文字数がちゃんとプリントされます。printは","で終わっていますが、$\に行ごとのカウンター個数+改行が含まれているためそれも一緒に末尾に出力されます。これもまた味わいがありますね。
Hole 2. BPEagle
問題文
アルファベット小文字と半角スペースを用いて分かち書きされたテキストが標準入力で与えられます。このテキストを以下のルールに従って圧縮してください。
1. テキストを半角スペースで分割し、単語にわけます
入力例: launchpad launchsite launchcrew
処理例: ["launchpad", "launchsite", "launchcrew"]
2. それぞれの単語の中で、隣り合う文字についてペアを作ります
処理例: ["la", "au", "un", "nc", "ch", "hp", "pa", "ad", "la", "au", "un", "nc", "ch", "hs", "si", "it", "te", "la", "au", "un", "nc", "ch", "hc", "cr", "re", "ew"]
3. それぞれのペアの出現頻度を調べます
処理例: { "la": 3, "au": 3, "un": 3, "nc": 3, "ch": 3, "hp": 1, "pa": 1, "ad": 1, "hs": 1, "si": 1, "it": 1, "te": 1, "hc": 1, "cr": 1, "re": 1, "ew": 1 }
4. 最も多いペアを1つ見つけてそれをAに置き換えて元の文に戻します。また置き換えたペアを記録します
最も出現頻度が多いペアが複数ある場合は、文章中で最初に出現したものを選びます。
また、置き換えたペアは辞書の形で記録します。辞書のキーはA, B, C...の順に割り当てます。
処理例: ["Aunchpad", "Aunchsite", "Aunchcrew"], { "A": "la" }
5. 2〜4を繰り返します。全ての頻度が1になるまで繰り返します
["Aunchpad", "Aunchsite", "Aunchcrew"],{ "A": "la" }["Bnchpad", "Bnchsite", "Bnchcrew"],{ "A": "la", "B": "Au" }["Cchpad", "Cchsite", "Cchcrew"],{ "A": "la", "B": "Au", "C": "Bn" }["Dhpad", "Dhsite", "Dhcrew"],{ "A": "la", "B": "Au", "C": "Bn", "D": "Cc" }["Epad", "Esite", "Ecrew"],{ "A": "la", "B": "Au", "C": "Bn", "D": "Cc", "E": "Dh" }
6. 最終的に圧縮されたテキストと置き換えたペアを以下の形で出力します
1行目が置き換えたペア(辞書)をカンマ区切りで表したもの、2行目が圧縮されたテキストになります。
出力例:
A:la,B:Au,C:Bn,D:Cc,E:Dh
Epad Esite Ecrew
これもややこいなあと思うかもしれませんが、実際ややこしいです。やりたいことは文字列の圧縮です。登場頻度が高い2つの文字からなるペアの部分文字列を見つけて、それを一文字に置き換えていくというものです。
題名からわかるかもしれませんが、生成AIに使われるByte Pair Encodingという手法のアルゴリズムです。
このコードはナイーブに書くと問題文の通り5つのフェーズに分けれます。コードゴルフとしてはそれぞれのフェーズをコンパクトに書き、2つ以上のフェーズを1回の処理でまとめられるかどうかというのがポイントになっていきます。
Ruby
Hole 2は全体の最短から解説します。
Rubyおよび全体での1位はnsfisisさんの回答でした。
-148(102 bytes)です。おめでとうございます。驚異的ですね。
#!ruby -p ?A.upto(?Z){$_.scan(/(?=(.\B.))/).tally.max_by{_2}in[b],1or$*<<it+?:+b%gsub(b,it)} puts$**?,
まずshebangを使ったコマンドラインスイッチを使用しています。
#!ruby -p
Perlでも利用できるテクニックなんですが、Rubyの-pは変数$_を最後にprintする挙動になります。今回はWebAssemblyで動かしていたので厳密にはシェルのようなものはないはずですが、動くんですね。ちなみにPerlでも動作します。
まず一番外側のループです。
?A.upto(?Z){...}
与えられる入力はアルファベットの範囲を超えないようになっているため、理にかなった指定と言えます。また、終了条件の判定をしなくて良いのもメリットですね。
$_.scan(/(?=(.\B.))/)
次に正規表現で単語を跨がずに隣り合うアルファベットのペアを抜き出しています。lorem ipsumという入力がある場合は、["lo", "or", "re", "em", "ip", "ps", "su", "um"] という配列を返しています。
.tally
このメソッドは配列内で同じ要素が出現した回数を数えてHashを返します。["ab", "bc", "ca", "ab"]という配列にtallyをすれば{:ab => 2, :bc => 1, :ca => 1}となります。便利だなあRuby。
.max_by{_2}
これはハッシュの値を使ってソートを行うことを示しています。これで、{:ab => 2, :bc => 1, :ca => 1}というハッシュに関しては[:ab, 2]という2つの要素が入った配列が返ります。
ちなみに今回の問題では同じ回数だけ出たアルファベットのペアは先に登場したものを優先するというルールがあります。これで満たせるのかな？と思ったのですが、Rubyのハッシュは入れた順番が保持され、ループ時も入れた順番で回ります。この効果で.tally.max_by{_2}でも問題がなくなっていると思われれます。
in[b],1or
さてここからが問題です。いきなりinが出てきます。分かりにくいですがパターンマッチです。直前のmax_by{_2}の結果、最大となるキー[[b], 1] に当てはまらない場合はfalseを返す式となります。そして当てはまらないケースでは、後続のor以降が走るという挙動です。ちなみに当てはまるケース、つまり[[b], 1]がマッチするケースというのは、単語中に登場するアルファベットのペアの頻度が最大でも1回、つまり重複するものがなく圧縮する必要がないケースです。過剰に圧縮するのを防いでいる部分と言えます。
しかし、後続の[[b], 1]にマッチしないケースではあたかもbにハッシュのキーが代入されている前提で書かれているように見えますし、実際これで動いています。これってRubyの仕様なの？と調べたところ、「付記B: 未定義の振る舞いの例」5 に書かれていました。「マッチしなかったパターンに指定した変数を使う」の部分ですね。パターンマッチの変数バインディングがローカルマッチにしか適用できない点を議論する際にも、このような副作用が現状あるためサポートしていない旨が話されていました。6 コードゴルフにこういうの持ち込んでくるのだいぶテクいですね！
$*<<it+?:+b%gsub(b,it)
あとは仕上げの部分ですね。$*は本来はRubyスクリプトを起動する際に与えられた引数を表す配列ですが、コードゴルフではしばしば初期化済みの配列として扱われます。この部分はアルファベットのペアを大文字のアルファベットに置換した際の辞書を作る部分です。<<はRubyではpush/appendで、itには?A.upto(?Z)でループ回している部分のアルファベットが入ってきます。?:は:一文字を表す文字列です。b % gsub(b, it)の%はsprintfのような挙動をする文字列に使える演算子です。しかしbには%sなどのフォーマットに使われるような構文が入ってこないのが問題文から保証されているので、実際には何も起きません。gsub(b, it)という部分を$*に追加したい文字列に影響を与えずに実行したい、bが使えるスコープで実行するために式としてまとめる必要があるために使われています。ゴルフですね〜〜。
Rubyなのにgsubがレシーバなしで(s.gsubのような形式ではなく)呼び出されているのはなぜ？ と思った方、鋭いですね。これはKernelモジュールで定義されているgsubモジュール関数です。7 コマンドラインオプションで-pもしくは-nを指定した時のみ定義されます。最初のshebangでの指定がここで効いてきます。$_.gsubと挙動は同様ですが、$_の内容を置き換えます。これで、次のループでは圧縮済みの文字列を対象にまた同じ処理が走ります。
puts$**?,
最後に辞書をカンマ区切りで出力し、そしてruby -pの効果で大文字アルファベットに置換された圧縮済み文字列も次の行に出力されます。これで特定の条件のみですがBPEが動きました。
と、ここまで書いて、そういえば回答していただいたnsfisisさんがWrite Up記事を書いていだたいてました。こちらにもっと詳しい途中の回答などの解説も載っているのでぜひご覧ください。
Perl
Perlでの一位はmasiuchiさんの回答でした。
-126(124bytes)です。おめでとうございます。
$_=<>;for$c(A..Z){$f=$i=$_;(@b=$i=~/$_/g)>$f&&($f=@b,$b=$_)for/(?=(\S\S))/g;s/$b/$c/g,$d.="$c:$b,"if$f>1}chop$d;print"$d $_"
ぎゅっと圧縮されてどこが切れ目かわからないと思うので整理するとこう。
$_ = <>; for $c (A..Z) { $i = $_; $f = $i; for (/(?=(\S\S))/) { if ((@b = $i =~ /$_/g) > $f) { $f = @b; $b = $_; } } if ($f > 1) { $_ =~ s/$b/$c/g; $d .= "$c:$b,"; } } chop$d; print"$d $_"
スペースや改行入れる他には、後置forや後置ifを普通のfor, ifに置き換えたりしました。式にするために&&などを使っている箇所も、文に分けて置き換えています。
$_ = <>; for $c (A..Z) {
標準入力から取り込んで、A..Zまでループする部分です。Rubyと同じ戦略ですね。PerlもRubyと同様shebangを使って$_ = <>;と同様のことができるんですが、<>が短すぎてshebangを書いた方がむしろ文字数が嵩んでしまいます。
$i = $_; $f = $i; for (/(?=(\S\S))/) {
後のforループで$_に/(?=(\S\S))/の結果が入ってきてしまうので、$iに入力を待避させています。この/(?=(\S\S))/はRubyで使われているのと同様、隣接する空白文字ではない文字のペアをとる正規表現です。
if ((@b = $i =~ /$_/g) > $f) { $f = @b; $b = $_; }
このif文の中がテクいです。$fは$f = $iの通り、ループの最初では文字列が入っています。一方左辺値は@b = $i =~ /$_/gなので、入力文字列中に含まれているアルファベットのペアが個数分@bに入ってきます。そして>なので@bはスカラコンテキストで評価され、配列のスカラコンテキストは要素の個数が返ります。
つまり、このif文は数値と文字列を数値比較演算子(Perlは文字列用の比較演算子が別であります)で比較しているわけですが、これは一体どうなってしまうのか？
結論を言うと、このケースと入力文字列では文字列が入っている場合は右辺は0と解釈されます。Perlは数字っぽい文字は数字として解釈しようとします。なので、"1"という文字列が変数に入っていたとしても、数値比較演算子で正しく扱えます。この問題の場合、入力はアルファベットに限られているため、数字が入ってくることはありません。そのケースでは0と等価です。なので、初期状態では、
if (<アルファベットのペアがマッチした個数> > 0) {
となり、この個数は必ず1以上のため、ifの中に入ります。そして次の行の$f = @bはスカラコンテキストで配列を評価しているので$fには個数が入ります。そして$bにはアルファベットのペアが入ります。このif文全体で「アルファベットのペアのうち最も登場するものを$bに入れる。というコードです。また、比較演算子が >=ではなく > なので、最も頻度が多いペアのうち最初に登場したペアを置き換えるルールも実現できています。
if ($f > 1) { $_ =~ s/$b/$c/g; $d .= "$c:$b,"; }
$fつまり頻度が1以上、圧縮する必要がある場合は、置換を行います。ちなみに提出しているコードは $_ =~が省略されています。単にs/.../.../g と書くと $_に置換を行うコードになります。
そして$dに辞書となる文字列を連結していきます。
chop$d; print"$d $_"
$dには必ず末尾に , をつけながら連結していくため余計な , が末尾に含まれているはずです。これをchopで切り飛ばします。
そして、結果を出力するという形です。
以上です。整理するとちゃんと読めるのではないのでしょうか？
Python
Pythonでの1位はalceaさんの回答でした。
-96(154bytes)です。おめでとうございます。
s=input() d=e='@' while(f:=(g:=s.replace)(*' $').count)(c:=max(map(str.__add__,e+s,s),key=f))>1:s=g(c,e:=chr(ord(e)+1));d+=','+e+':'+c print(d[2:]+'\n'+s)
これもギュッとなってますね。Pythonでもこんなに切れ目がわからないコードが書けるんですね。バラしていきましょう。
s = input() e = '@' d = e while ( (f := (g := s.replace)(*' $').count)( c := max( map(str.__add__, e + s, s), key=f, ) ) ) > 1: s = g(c, e := chr(ord(e) + 1)) d += ',' + e + ':' + c print(d[2:] + '\n' + s)
気になる点を見ていきましょう。:=はウォルラス演算子というやつで、Pythonの普通の代入と違い、式として解釈されます。なのでwhile (f := ...) > 1 は ... の部分で返した数値を1を比較して...の部分が1より大きい間はループを続けます。今まで見た通り、fはアルファベットのペアのうち最も多く登場するペアの登場頻度ですね。
(g := s.replace)(*' $')
(g := s.replace) は一旦 g に s.replace というメソッド自体を入れてます。よく見るとwhileの中でgを使っていますね。replaceを2回書くより短くなるためこうなっていますね。
またここでウォルラス演算子を使って代入したばかりのs.replaceを呼び出しています。(*' $')もなかなかテクいのですが、これは(' ', '$')と等価です。つまり文字列を2つに分解して引数にわたすことをしています。これは何をやっているかというと、空白、つまり単語の区切りを$に変換しています。lorem ipsumという文字列が入力されたら、lorem$ipsumという文字列が返ってきます。
(f := (g := s.replace)(*' $').count)( c := max( map(str.__add__, e + s, s), key=f, ) )
さらにこの文字列のcountをfに代入しつつ呼び出しています。countは引数に渡された文字列が自身に何回登場するかを調べるメソッドです。この中でもウォルラス演算子を使用していますね。maxはここでは2つの引数を受け取っています。一つ目はこちら
map(str.__add__, e + s, s),
mapは2つ目の引数に指定されたイテレータに対して1つ目の引数に指定された関数を適用します。しかし3つ目にイテレータを入れると2つ目と3つ目のイテレータから1つずつ要素を取り出して、1つ目の関数の引数に適用します。入力がlorem isumであれば、
map(str.__add__, '@lorem ipsum', 'lorem ipsum') # => ['@l', 'lo', 'or', ...]
というイテレータを返すことになります。つまりRubyやPerlが正規表現でやったようなことをPythonはこのようにやっています。
maxのキーワード引数keyは比較用の関数を渡しています。この場合、比較用の関数は、
g := s.replace)(*' $').count
の部分で、つまり出現回数を数えています。そしてcには最も多く出現したペアが入ります。つまり、再掲しますが、
(f := (g := s.replace)(*' $').count)( c := max( map(str.__add__, e + s, s), key=f, ) )
この部分全体では、「アルファベットのペアのうち最も多く出現するペアの頻度を返す」式となっています。ちなみにRubyとPerlでは正規表現で除外されていた単語の区切りを跨いだり、空白を含んだペアですが、それは空白を$で置換することで実現しています。出現回数を調べるときには、$で置換された文字列を対象に、$で置換していない文字列から作ったイテレータを使って検査しています。よって、aのようなペアがあっても、対象の文字列にはa$で置換されているため、マッチしません。巧妙ですね〜〜！
あと言うべき点としては、
e = '@' ... s = g(c, e := chr(ord(e) + 1))
ここですね。Aの前の文字列はascii順で言うと@なので、常に加算した値を使うために@を入れています。
以上です。Pythonでもこんなに技巧的なコードが書けるんだと感動してしまいました。
PHP
PHPでの1位はtakaramさんの回答です。
-25(225bytes)でした。おめでとうございます。
<?$s=fgets(STDIN);for($n=64,$d='';;$s=strtr($s,[$k=>$c=chr(++$n)]),$d.="$c:$k,",$p=[]){for($i=0;$i<999;)strstr($t=substr($s,$i++,2),' ')||!$t||@$p[$t]++;if(arsort($p)&$p[$k=array_keys($p)[0]]<2)break;}echo trim($d,',')," $s";
整理するとこうです。
<?php $s = fgets(STDIN); for ( $n = 64, $d = ''; ; $s = strtr($s, [ $k => $c = chr(++$n) ]), $d .= "$c:$k,", $p = [] ) { for ($i = 0; $i < 999; ) { $t = substr($s, $i++, 2); strstr($t, ' ') || !$t || @$p[$t]++; } arsort($p); $k = array_keys($p)[0]; if ($p[$k] < 2) { break; } } echo trim($d, ','), "\n", $s;
要点を見ていきましょう。
$n = 64, $d = '';
64というマジックナンバーはasciiコードでいう@を表します。Pythonの際の@と同じ効果です。
for ($i = 0; $i < 999; ) { $t = substr($s, $i++, 2); strstr($t, ' ') || !$t || @$p[$t]++; }
substrは文字列から位置を指定して文字列を抜き出します。1文字ずつスライドしながら2文字取り出しているのでアルファベットのペアを作っている部分ですね。strstr($t, ' ')は空白を置換していますが、置換ができなかった場合はfalseを返します。つまり、空白が含まれてない場合は!$t || @$p[$t]++;の部分が実行されるということですね。!$tですが、substr($s, $i++, 2)で$iが$sの文字列長を超えた場合は、substrは空白が返ってくるため、そのガードのためにあります。これらのガードを乗り越えると連想配列$pのアルファベットのペアのキーに対してインクリメントされます。@は未初期化変数に対してインクリメントする際のWarningを出さないためですね。
arsort($p);
$k = array_keys($p)[0];
if ($p[$k] < 2) {
break;
}
arsortは連想配列用のソート関数です。これで最も多く登場するアルファベットのペア順に並びます。array_keysで連想配列のキーのみの配列を作り、その先頭を取ることで、最も多く登場するアルファベットのペアを$kに入れます。PHPもまた連想配列を入れた順序で保持するので、最も頻度が高く最初に登場したキーを取り出すルールを満たせています。
以上です。ちなみに、社内の予備回答ではもっと短い回答があったので参考までに載せておきます。どこか違うか検討してみてください。
-51(199bytes)です。
<?for($s=fgets(STDIN),$b='A';;$b++){preg_match_all('/(?=(\w\w))/',$s,$m);$c=array_count_values($m[1]);arsort($c);if($c[$k=key($c)]<2)die(@substr($e,1)."\n$s");$s=str_replace($k,$b,$s);@$e.=",$b:$k";}
JavaScript
JavaScriptでの1位はdo7beさんの回答でした。
-27(223bytes)です。おめでとうございます。
l=std.in.getline() for(w=[],j=65;m={},l.split` `.map(s=>{for(i=h=0;s[i+1];)m[v=s[i]+s[++i]]=-~m[v]}),eval("for(e in m)m[e]>h&&(h=m[e],b=e)"),h>1;)w.push((k=String.fromCharCode(j++))+':'+b),l=l.replaceAll(b,k) print(w+` `+l)
こちらも整理します。
l = std.in.getline() for ( w = [], j = 65; m = {}, l.split` `.map(s => { for (i = h = 0; s[i + 1]; ) { m[v = s[i] + s[++i]] = -~m[v] } }), eval("for(e in m)m[e]>h&&(h=m[e],b=e)"), h > 1; ) { w.push((k = String.fromCharCode(j++)) + ':' + b) l = l.replaceAll(b, k) } print(w + `\n` + l)
まずここを解説しましょう。
l.split` `.map(s => { for (i = h = 0; s[i + 1]; ) { m[v = s[i] + s[++i]] = -~m[v] } }),
lは入力文字列ですが、これをまずsplitで空白区切りにします。ちなみにsplitの引数に括弧がないですが、タグ付きテンプレートリテラルとして呼んでいるのでl.split([" "])と等価です。
そのあとmapで単語ごとに処理をしているわけですが、forループを使用しています。s[i + 1]なので、末尾に到達してundefinedを返すまでループを繰り返します。m[v = s[i] + s[++i]]は技巧的です。隣接するアルファベットのペアを作っていますが、2つ目は++iを使うことで、forループのiのインクリメントとインデックスアクセスを同時にしています。
-~m[v]はm[v] + 1と等価です。しかし + 1ではなくあえてこうしているのには理由があります。最初はm[v]は未定義です。未定義に+ 1をしてもうまくいきません。一方で-~は未定義であっても1を返します。
というわけで、mにアルファベットのペアの登場頻度を表すobjectが作られました。
eval("for(e in m)m[e]>h&&(h=m[e],b=e)"), h > 1;
そして突然のevalですが、これは式じゃないと置けない部分にループを入れるために使われています。このeval部分で最も登場するアルファベットのペアがbに入り、その頻度がhに入ります。そのhを使って、ループの終了条件を決めています。
以上です。evalやタグ付きテンプレートリテラルを使うのは面白いアイデアですね。
まとめ
全体の優勝はnsfisisさんでした。おめでとうございます。
またご参加していただいた皆様もありがとうございます。今回は前回に比べて多くの方に参加していただきました。盛り上がりも観測できたかと思います。
参加していただいた方にアンケートもさせていただきました。一部ピックアップして紹介させていただきます。紹介させていただく設問は「生成AIは使用しましたか？」と「問題を解く際に生成AIを使い始めたのはいつぐらいからですか？」です。
今回のコンテストではLLMの使用は明示的に許可していました。というのも、急速に発展したLLMによるコーディングですが、コードゴルフにも適用できるかどうかに興味があったからです。事前に社内では単純なプロンプトでは人間で書くより長くなってしまうので、まだ人間は負けてないぞと思いましたが、プロンプトがうまければ短くできるのではないか？とも思っていました。
アンケート結果がこちら。
また、「もし生成AIを使用した場合にコードゴルフを行う上で困難だったことを教えてください」という自由回答の設問も用意しましたが、「最初に参考回答を短くする程度には役立つものの、トップ5を狙うぐらいになってくると使えない」という回答でした。また、LLMは文字数ではなくトークン単位で文章を認識しているため、文字数を短くするというタスクは苦手ではないかという考察もWrite Up記事で見かけしました。
これ以外にも改善点などももらっております。次回以降の開催でもっと面白く、もっと多くの方にコードゴルフに興味を持っていただけたらなと思います。
レッツコードゴルフライフ！ 皆様お疲れ様でした〜。良いお年を！
- https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String/Symbol.iterator↩
- https://docs.ruby-lang.org/ja/latest/method/Kernel/v/=3c.html↩
- https://docs.ruby-lang.org/ja/latest/method/Kernel/v/=2e.html↩
- https://www.ruby-lang.org/ja/news/2024/12/25/ruby-3-4-0-released/#it-%E3%81%AE%E8%BF%BD%E5%8A%A0↩
- https://docs.ruby-lang.org/ja/3.4/doc/spec=2fpattern_matching.html#some_undefined_behavior_examples↩
- https://bugs.ruby-lang.org/issues/18408#note-19↩
- https://docs.ruby-lang.org/ja/3.4/method/Kernel/m/gsub.html↩
