infix to postfix again

はまじしん一ろう

Reject kaigi

自己紹介: インフラにしか興味がありません

! Agenda

ゴルフ

! hoge

プログラミングシンポジウムでも紹介した
とある興味深い問題について、既に紹介したこと以外に
面白い発見があったので話します。

http://shinh.skr.jp/dat_dir/golf_prosym.pdf

! これまでのあらすじ

infix to postfix という問題
中置記法の式を後置記法に変換する

 a*b*(c+d)+e

を

 ab*cd+*e+

に変換する問題。

! 普通に解くと

 #!ruby -p
 $\="(
 "
 z=/([^(]*)/
 gsub(/\W/){|c|
   $\["+-"[c]?z:"("[c]?//:c>")"?/([*\/]*)/:
     /#{c="";z}\(/]=c;$1
 }

104B

kinaba (2007)

http://www.kmonos.net/wlog/71.html#_2014070301

! 全然普通じゃない

読めません

! 賢い解き方

 undef:p
 def method_missing s,*
   $><<s
 end
 loop{eval(gets)<<$/}

61B

flagitious, kinaba (2007)

http://www.kmonos.net/wlog/71.html#_2014070301

! どう賢いの

 '''undef''':p
 def '''method_missing''' s,*
   $><<s
 end
 loop{'''eval'''(gets)<<$/}

eval で Ruby に中置記法をパースさせて、
method_missing で出力しちゃう

Kernel#p は邪魔なので undef

! ここまでが

これまでのあらすじ

目標1分

! 改善

 undef:p
 def method_missing s,*
   $><<s
 end
 '''loop'''{eval(gets)<<$/}

実はこのプログラムは無限ループしてる
終了は TypeError で。

 in `eval': can't convert nil into String (TypeError)

だから無限ループならなんでもいい

! loop{} => until def

 undef:p
 eval(gets)<<$/'''until def''' method_missing s,*
   $><<s
 end

def は実は nil を返してる

60B

shinh (2008)

! loop => Array#*

 undef:p
 def method_missing s,*
   $><<s
 end
 eval [*$<]*'puts;'

入力の入った Array を 'puts;' で join して eval

59B

flagitious, kinaba, shinh (2008)

! loop => Array#*

 undef:p
 def method_missing s,*
   $><<s
 end
 eval [*$<]*'puts;'

以下ような文字列を eval することになる

 a+b
 puts;a*b*(c+d)+e
 puts; ...

! goruby

Ruby 1.9 で入ってるゴルフ用の Ruby

メソッドの省略呼び出しが可能

each_with_index => ew とか

! 今回の問題への適用

Kernel#p だけでなく Kernel#h も邪魔
Kernel#h - Hello, world! と出力する関数

method_missing を上書きするので
goruby の短縮記法のメリット少ない。

=> 縮む要素がない。

! 40B

 O.u:p,:h
 O.a_ _,:print
 eval [*$<]*'say;'

shinh (2008)

http://d.hatena.ne.jp/shinichiro_h/20080408#1207654730

! undef

 '''O.u:p,:h'''
 O.a_ _,:print
 eval [*$<]*'say;'

undef より O.u

O.u == Object.undef_method

! O.a_

method_missing を print に alias

 O.u:p,:h
 '''O.a_''' _,:print
 eval [*$<]*'say;'

O.a_ == Object.alias_method

! alias は 1.8 では使えなかった

理由: 2006年の nil.to_s => 'nil' 論争

print nil では 'nil' が出力されていたのだが (1.8)
この論争のどさくさに紛れてなんも出なくなった (1.9)

 > ruby -e 'puts nil'
 nil
 > ruby1.9 -e 'puts nil'
 
 >

http://osdir.com/ml/lang.ruby.devel/2006-09/threads.html#00011

! _

 O.u:p,:h
 O.a_ '''_''',:print
 eval [*$<]*'say;'

このアンダースコアは実は ''':method_missing'''

 > goruby1.9 -e 'p _'
 ''':method_missing'''

! _ == __callee__

1. _ なんてメソッドは存在しない
2. goruby の method_missing が呼ばれる
3. method_missing は _ を __callee__ と解決する
4. __callee__ が呼ばれる
5. この時呼び出し元は method_missing
6. よって :method_missing が返る

! おわり

というわけでまだ縮んだのでした。

Ruby: 61B => 59B

goruby: 40B

めでたしめでたし

! おわり

ところで一昨日のコンペの複利計算は
一昨日の時点では 49B がトップだったのですが
今はプロの手によって 45B が…

 gets;eval"p a=!a ?!0?#{chop}*a/?d+a;"*$_.to_i

以下のようなコードを eval している...

 p a = !a ? false ? 20 : 100 : 5*a/100+a

kurimura et al. (2008)

http://golf.shinh.org/reveal.rb?Compound+interest/kurimura/1214038550&rb