GOTO M.

趣味のコーディングとか、勉強とか、読書とか

Code golf 反省メモ(Advent of Code Not Quite Lisp)(Ruby)

挑戦した問題

Advent of Code Not Quite Lisp (anarchy golf)

http://golf.shinh.org/p.rb?Advent+of+Code+Not+Quite+Lispgolf.shinh.org

要約

開き括弧"("と閉じ括弧")"が並んだ文字列が与えられます。"("を+1、")"を-1として左から順に加算していき、合計値が-1となるまでに読込んだ文字数を出力します。

言い換えると、開き括弧と対応付かない閉じ括弧のうち最左のもののindexを1-originで求める問題です。

(()()))()(()

例えば↑のような入力の場合、(()())までは括弧の対応が取れていますが次の)には対応する開き括弧が無いため、7を出力することとなります。

Ruby1.8.7とRuby2.2.3でチャレンジし、いずれも2位でした。進歩してはいるものの、1位が段違いだなぁと感じた挑戦でした。

ソースコード(Ruby 1.8.7)

自分のコード(44)
#!ruby -n
c=1;$_["()"]=""*c+=2while/^\(/;p c
  • 「対応付く括弧の対"()"」を順に取り除いていくことを、先頭が)になるまで繰返すという方針です。
  • 変数cの宣言などが重たい感じがします。
1位の方(mitchs様)のコード(39)の吟味
def f
getc>40?1:f-~f
end
loop{p f
gets}
  • loopで回しているうちにgetcがエラーとなるので停止する?(anarchy golfのエラー出力の扱いがよく分からないので、次の挑戦時に色々試してみます)
  • golf的にはよく使う書き方ですが、f-~ff+f+1と同値です。
  • 関数fについては色々な解釈が考えられますが、開き括弧"("※を読んだ直後に使用することで、※より後ろで、※に対応する閉じ括弧までの文字数を返すという関数だと解釈しました。
  • f:id:g_m_k:20160104220302p:plain

ソースコード(Ruby 2.2.3)

自分のコード(35)
#!ruby -n
p$_[/(\(\g<0>.)*/].size+1
  • Ruby2は正規表現エンジンとして「鬼車」を搭載しているので、部分式呼出し\g<n>が使用できます。特に\g<0>でその正規表現全体と再帰的にマッチさせることができます。
  • つまり/(\(\g<0>.)*/は、ちゃんと対応する開き括弧"("と閉じ括弧")"の連続(ディック言語)にマッチします。欲しいのはその後の閉じ括弧")"なので+1をしています。
  • +1をなんとか削りたかったけれど、うまい案が浮かびませんでした。
1位の方(mitchs様)のコード(32)の吟味
loop{p gets[/(\(\g<0>)*./].size}
  • /(\(\g<0>)*./は、そのものずばり、対応する開き括弧"("と閉じ括弧")"の連続(ディック言語)とその直後の閉じ括弧")"にマッチします。(本問の場合.\)と読み替えて差し支えありません)

今後の Code golf に向けた反省

  • まとめると「うまい言い換え」と「単純なパターンからの成長」が大切だと感じました。
  • 「うまい言い換え」について。問題を以下のように読み替えることで、最短コードに一歩近付けたと思います。
    • 入力の先頭に仮想の開き括弧"("を想定することで「対応する閉じ括弧")"までの文字数を計算する」という問題に帰着する。(Ruby 1.8.7の解答)
    • 「開き括弧"("と対応付かない最初の閉じ括弧")"の位置を特定する」という問題に帰着する。(Ruby 2.2.3の解答)
  • 「単純なパターンからの成長」について。上の「うまい言い換え」が出来たとしても、自分のレベルではまだ一発で解答コードには至れません。最初の一歩として一番シンプルなパターンを、次の一歩として次にシンプルなパターンを……と少しずつ考えて行くことが大切そうです。
    • Ruby1.8.7/2.2.3のいずれの場合も、まず)という最もシンプルなパターンを考え、次に())というパターンを考えることで一歩一歩進める…のかなぁ。
  • 上記とは別に、個々の語彙レベルでも力不足を感じました。
    • loop{ ~ }という書き方
    • 再帰のためにdef ~ endを用いるという選択肢。(Ruby1.8.7ではアロー演算子も使えないこともあり、ついつい脳内で枝切りしてしまう)