http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0506

久しぶりにゴルフをやりたくなったのでやった。AOJの仕様上、コードを短くしても自分の他の解答より実行時間が速くなければランキングにのらない様で、悲しかったのでブログ記事にした。なお、言語はRubyである。

問題

問題文を引用する。

0 から 9 までの数字だけで構成された文字列が与えられたとき,その文字列から次の規則に従って新しい文字列を作る操作を考える.与えられた文字列を左端から1文字ずつ順に読んで行き,同じ数字 a が r 個続いていた場合,個数 r と数字a を空白で区切らずにこの順で書き出す.与えられた文字列の右端まで読み,最後の書き出しが終わったところまでを途中何回書き出しがあったとしても全部まとめて操作1回とカウントする.2回目以降の操作は前回の操作により書き出された文字列を与えられた文字列として同様の操作を実施する.例えば “122244” という文字列が与えられた場合には左端から順に1個の1, 3個の2,2個の4なのでこの操作1回で得られる文字列は “113224” であり,“44444444444” (11 個の4)の場合には得られる文字列は “114” となる.

例を見ると言いたいことがわかると思う。

入力は以下のようになる。

入力データは 2 行からなり,1 行目に操作回数 n, 2 行目に最初の文字列が書かれている. 入力は複数のデータセットからなる．n が 0 のとき入力が終了する．データセットの数は 5 を超えない．

この例だと、「5 11」が一つのデータセットで、「0」がデータの終端である。

Step 1 (83 bytes)

4年近く前に自分が解答していたものがあったので、これをスタート地点にする。

while(n=gets.to_i)!=0
s=gets
n.times{s.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts s
end

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=776931#1

素朴な実装である。メインとなるs.gsub!(/(.)\1*/){"#{$&.size}#$1"}以外は至って普通でわかりやすい。

Step 2 (82 bytes)

なんと、ランキングページを見たところ、この解答が抜かされていた。以下にそのコードを引用する。

while(n=gets.to_i)>0
s=gets
n.times{s.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts s
end

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1047873#1

何が異なるかと言うと、!=0が>0になったのみである。これで1bytes減った。

抜かされていたのが悔しかったので、これよりも短くすることを目標とした。

Step 3 (81 bytes)

while 0<n=gets.to_i
s=gets
n.times{s.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts s
end

0<を代入の前に移動した。これにより括弧を削ることが出来る。

Step 4 (80 bytes)

while 0<n=gets.to_i
gets
n.times{$_.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts$_
end

s=getsの代入をなくした。Rubyでは、getsした文字列は自動的に$_という特別なグローバル変数変数に格納される。 module Kernel (Ruby 2.4.0)
これはコードを短くする上での常套手段なので覚えておきたい。

また、putsと$_の間には空白を開けなくてもきちんとパースできるため、ここでも文字数の節約をする必要がある。

Step 5 (79 bytes)

while(n=gets.to_i;gets)
n.times{$_.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts$_
end

0<のチェックをなくした。代わりに、getsの戻り値をループの条件とした。getsはEOFに達したらnilを返すので、whileの条件として使うことが出来る。

Step 6 (78 bytes)

n=(n.to_i.times{$_.gsub!(/(.)\1*/){"#{$&.size}#$1"}}
puts$_)while(n=gets;gets)

後置whileを使用するようにした。後置whileはendが必要ないので、短くしやすい。

なお、後置whileの条件内で代入を行っても後置whileの本文ではその変数を参照できない(はじめて知った)。そのため、n=でwhileの外に先に変数を宣言している。これは、ローカル変数をグローバル変数にしたり(文字数は同じ)、定数を使用したりすることでも解決することが出来る。定数を使用するとより短くすることが出来るが、AOJでは標準エラー出力に出力があるとエラーとなってしまうため採用できなかった。

Step 7 (78 bytes)

n=(eval'$_.gsub!(/(.)\1*/){"#{$&.size}#$1"};'*n.to_i
puts$_)while(n=gets;gets)

バイト数は変わっていないが、説明の為にこのステップも記述する。今までInteger#timesを使用してgsub!を繰り返していたのを、回数分のgsub!を文字列として生成しevalすることによって繰り返しを実装する。

Step 8 (77 bytes)

n=(puts eval'$_'+'.gsub(/(.)\1*/){"#{$&.size}#$1"}'*n.to_i)while(n=gets;gets)

.gsubの戻り値を使用できるように書き換えた。これにより不要な改行を減らしたり、.gsubのbangを取ることが出来て、より短くなる。

Step 9 (76 bytes)

puts eval'$_'+'.gsub(/(.)\1*/){"#{$&.size}#$1"}'*$n.to_i while($n=gets;gets)

whileの中が1文になったので、括弧を取り払った。また、括弧を取り払うために、ローカル変数ではなくグローバル変数を使用するように変更した。

Step 10 (74 bytes)

puts eval'gets'+'.gsub(/(.)\1*/){"#{$&.size}#$1"}'*$n while 0<$n=gets.to_i

$_を削るために、getsを直接書くようにした。

Step 11 (66 bytes)

#!ruby -p
$_=eval'gets'+'.gsub(/(.)\1*/){"#{$&.size}#$1"}'*$_.to_i

-pというRubyの起動オプションを使うことにした。 Rubyの起動 (Ruby 2.4.0)

これは、Rubyプログラムが

while gets
  ...
  print $_
end

のようなループで囲まれているように動くようになる。

今回の処理は行単位ではないのでうまく使えないのではと思いこれまで使ってこなかったが、意外とうまくいった。なお、ループの最後の回(入力が0の回)の処理は、$_がnilになるためうまくいっている。

Step 12 (64 bytes)

#!ruby -p
eval'gets'+'.gsub!(/(.)\1*/){"#{$&.size}#$1"}'*$_.to_i

$_への明示的な代入は、$_を破壊的に変更することで必要がなくなる。

まとめ

まだコードを短く出来る余地は残っているかも知れないが、これ以上はなにも思いつかなかったのでここで終了とする。

コードゴルフは中毒性が高く非常に楽しいので、是非チャレンジしてみて欲しい。

pockestrap

Programmer's memo

AOJ 0506 をゴルフした

問題