第24回オフラインリアルタイムどう書く「多段階選抜」の rubyによる実装

問題 http://nabetani.sakura.ne.jp/hena/ord24eliseq/
解答リンク集 http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
イベント http://yhpg.doorkeeper.jp/events/13159

当日お見せした実装。

def is_sq(b)
  (b**0.5).round**2==b
end

def is_cu(b)
  (b**(1r/3)).round**3==b
end

module Enumerable
  def prepend( a )
    if block_given?
      a.each{ |e| yield e }
      self.each{ |e| yield e }
    else
      to_enum( :prepend, a )
    end
  end
end

def remove_before( seq )
  seq.each_cons(2).select{ |i| ! yield i[1] }.map{ |i| i[0] }
end

def remove_after( seq )
  seq.each_cons(2).select{ |i| ! yield i[0] }.map{ |i| i[1] }.prepend( seq.first(1) )
end

def solve_core( s )
  seq=loop.lazy.with_index(1).map{ |*i| i.last }
  s.chars.each do |cmd|
    seq=case cmd
    when "s"; remove_before( seq ){ |n| is_sq(n) }
    when "S"; remove_after( seq ){ |n| is_sq(n) }
    when "c"; remove_before( seq ){ |n| is_cu(n) }
    when "C"; remove_after( seq ){ |n| is_cu(n) }
    when "h"; seq.drop(100)
    when /[2-9]/
      seq.each_slice(cmd.to_i).flat_map{ |i| i[0..-2] }
    else
      raise "unexpected cmd : #{cmd} in #{s}"
    end
  end
  seq
end

def solve( s, len=10 )
  solve_core( s ).first(len).to_a.join(",")
end

DATA.map{ |line|
  id, src, expected = line.split(/\s+/ )
  actual = solve( src )
  ok = actual == expected
  puts "***NG*** : %s %s->%s ( %s )" % [ id, src, actual, expected ] unless ok
  ok
}.all?.tap{ |r| puts ( r ? "ok" : "NG" ) }

__END__
0 ss6cc24S  1,9,21,30,33,37,42,44,49,56
1 h 101,102,103,104,105,106,107,108,109,110
2 hh  201,202,203,204,205,206,207,208,209,210
3 hhh 301,302,303,304,305,306,307,308,309,310
50  23h465Ssc9CchC  1027,1033,1045,1047,1057,1069,1071,1075,1081,1093

いつも通り、テストデータの大半は省略。

たぶん、遅延評価を前提に無限リストを作って、それをこねると出来上がる、というのが順当な実装だと思う。

遅延評価がない処理系だと固定長で用意していくんだと思うけど、ruby には lazy があるので大丈夫。

実装で手間取ったのは
　「無限リストの前に要素を１つ追加する」
という処理を書く部分。
当初はどうせあるだろうと思って調べたんだけど実は存在せず、実装するはめになった。
普通に [1]+lazy_enum という感じで加算できていいと思うんだけど。

当日罠として機能した三乗根の計算は

(b**(1r/3)).round**3==b

という風にして浮動小数点の計算誤差を回避したんだけど、ruby には Math.cbrt があることを教えていただいた。

Math.cbrt(100**3) #=> 100.0
(100**3)**(1r/3) #=> 99.99999999999997

Math.cbrt(100.00000000000001**3) #=> 100.00000000000001
 (100.00000000000001**3)**(1r/3) #=> 99.99999999999999

という感じ。素晴らしい。