多段階選抜 (Ruby)(旧)


|多段階選抜|解答日|シリーズ:yieldの練習/ジェネレータを入れ子に/整数平方根・立方根の実装|
|:--|:--|:--|
|問題|　|http://nabetani.sakura.ne.jp/hena/ord24eliseq/<br>https://qiita.com/Nabetani/items/1c83005a854d2c6cbb69|
|Ruby|2014/8/2(当日)|https://qiita.com/cielavenir/items/9f15e29b73ecf98968a5|
|C#/Python|2014/8/4|https://qiita.com/cielavenir/items/a1156e6a4f71ddbe5dcb|
| |　|ここから上はdrop_prev_square/drop_prev_cubicをまとめる前の答案|
|Go/C#/Ruby/Python|2014/8/5|https://qiita.com/cielavenir/items/2a685d3080862f2c2c47|
|PHP/JavaScript|2014/9/9|https://qiita.com/cielavenir/items/28d613ac3823afbf8407|
|VB|2014/9/10|https://qiita.com/cielavenir/items/cb7266abd30eadd71c04|
|D|2015/12/21|https://qiita.com/cielavenir/items/47c9e50ee60bef2847ec|
|Perl|2017/3/10|https://qiita.com/cielavenir/items/6dfbff749d833c0fd423|
|Lua|2017/3/13|https://qiita.com/cielavenir/items/c60fe7e8da73487ba062|
|C++20(TS)|2017/3/15|https://qiita.com/cielavenir/items/e1129ca185008f49cbab (MSVC)<br>https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 (clang)|
|F#|2017/3/17|https://qiita.com/cielavenir/items/a698d6a26824ff53de81|
|Boo/Nemerle|2017/5/13|https://qiita.com/cielavenir/items/e2a783f0fe4b0fe0ed48|
|Perl6|2017/5/15|https://qiita.com/cielavenir/items/656ea17fa96c865c4498|
|Kotlin|2017/5/25|https://qiita.com/cielavenir/items/9c46ce8d9d12e51de285|
|Crystal|2018/5/8|https://qiita.com/cielavenir/items/1815bfa6a860fd1f90db|
|MoonScript|2018/6/16|https://qiita.com/cielavenir/items/8b03cce0386f4537b5ad|
|Julia/Rust|2018/12/20|https://qiita.com/cielavenir/items/3ddf72b06d625da0c4a5|
|Nim|2018/12/26|https://qiita.com/cielavenir/items/5728944867e609fd52a7|
|Tcl|2018/12/31|https://qiita.com/cielavenir/items/76cbd9c2022b48c9a2c9|
|Pascal/Cobra|2019/1/16|https://qiita.com/cielavenir/items/81b81baf8dfc1f877903|
|Icon|2019/1/17|https://qiita.com/cielavenir/items/889622dcc721f5a4da24|
|Swift|2020/5/31|https://qiita.com/cielavenir/items/3b0b84a218e35d538f7f|
|Java/Groovy/Scala|2020/5/31|https://qiita.com/cielavenir/items/7f058203a8fd03b65870|
|V|2020/10/17|https://qiita.com/cielavenir/items/df30a6c101a97a713df5|
|Zig/Zen|2020/10/17|https://qiita.com/cielavenir/items/9cced9e4a94dcd70df0f|
|Pike|2020/11/2|https://qiita.com/cielavenir/items/3a8248f41611302b34fd|
|Vala/Smalltalk|2020/11/29|https://qiita.com/cielavenir/items/085dabe593cd916af5e8|
|Objective-C|2020/11/30|https://qiita.com/cielavenir/items/a1736e38789a3dd5cc5a|
|Ruby(Ractor)|2021/1/2|https://qiita.com/cielavenir/items/f493c6d512b63cc571cc|
|Python(_xxsubinterpreters)|2021/6/29|https://qiita.com/cielavenir/items/f1f581a055db918954f1|
|Falcon/Scheme|2021/9/5|https://qiita.com/cielavenir/items/c13d12cf44f0d17f4a94|
|Clojure/Lisp|2021/9/7|https://qiita.com/cielavenir/items/7458ba076f4e5bc0f196|
|(icbrtの実装に関する)補題|2017/5/11|整数除算であってもn/(x*y)はn/x/yに等しい(ことの証明)<br>https://qiita.com/cielavenir/items/21a6711afd6be8c18c55|

最初の答案。上限固定。idxesで消す座標を得てから削除。
with_indexに引数を指定しているのでRuby 1.8.7とは互換性がありません。

```rb:hena24.rb
#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
#http://nabetani.sakura.ne.jp/hena/ord24eliseq/
MAX=10000
sq=Hash[[*1..100].map{|e|[e**2,1]}]
cb=Hash[[*1..100].map{|e|[e**3,1]}]
if $0==__FILE__
	STDOUT.sync=true
	while gets
		input=$_.chomp.split('')
		a=[*1..MAX]
		input.each{|e|
			if e=='S'
				idxes=a.each.with_index.select{|f,i|sq.include?(f)}.map{|e|e.last+1}
				a=a.each.with_index.reject{|f,i|idxes.include?(i)}.map(&:first)
			elsif e=='s'
				idxes=a.each.with_index.select{|f,i|sq.include?(f)}.map{|e|e.last-1}
				a=a.each.with_index.reject{|f,i|idxes.include?(i)}.map(&:first)
			elsif e=='C'
				idxes=a.each.with_index.select{|f,i|cb.include?(f)}.map{|e|e.last+1}
				a=a.each.with_index.reject{|f,i|idxes.include?(i)}.map(&:first)
			elsif e=='c'
				idxes=a.each.with_index.select{|f,i|cb.include?(f)}.map{|e|e.last-1}
				a=a.each.with_index.reject{|f,i|idxes.include?(i)}.map(&:first)
			elsif e=='h'
				a=a.drop(100)
			else
				a=a.each.with_index(1).select{|f,i|i%e.to_i!=0}.map(&:first)
			end
		}
		puts a[0,10]*','
	end
end
```

解き直したもの。Enumeratorを使う。main中はreduce一個のみ。XY-sort( http://qiita.com/cielavenir/items/84e5cb1e5081bccdbbcd )と同じぐらいきれいに書けた。

Ruby 1.8.7: 70s
Ruby 2.0.0: 0.3s

```rb:hena24_enum.rb
#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
#http://nabetani.sakura.ne.jp/hena/ord24eliseq/
if RUBY_VERSION<'1.9'
	module Math
		def self.cbrt(n)
			n**(1.0/3)+1e-9
		end
	end
end
def generate
	return to_enum(:generate) if !block_given?
	i=1
	loop{
		yield i
		i+=1
	}
end
def drop_prev_square(prev)
	return to_enum(:drop_prev_square,prev) if !block_given?
	a=prev.next
	b=prev.next
	loop{
		yield a if Math.sqrt(b).to_i**2!=b
		a,b=b,prev.next
	}
end
def drop_next_square(prev)
	return to_enum(:drop_next_square,prev) if !block_given?
	a=prev.next
	b=prev.next
	yield a
	loop{
		yield b if Math.sqrt(a).to_i**2!=a
		a,b=b,prev.next
	}
end
def drop_prev_cubic(prev)
	return to_enum(:drop_prev_cubic,prev) if !block_given?
	a=prev.next
	b=prev.next
	loop{
		yield a if Math.cbrt(b).to_i**3!=b
		a,b=b,prev.next
	}
end
def drop_next_cubic(prev)
	return to_enum(:drop_next_cubic,prev) if !block_given?
	a=prev.next
	b=prev.next
	yield a
	loop{
		yield b if Math.cbrt(a).to_i**3!=a
		a,b=b,prev.next
	}
end
def drop_num(n,prev)
	return to_enum(:drop_num,n,prev) if !block_given?
	i=0
	loop{
		i+=1
		a=prev.next
		yield a if i%n!=0
	}
end
def drop_cnt(n,prev)
	return to_enum(:drop_cnt,n,prev) if !block_given?
	i=0
	loop{
		i+=1
		a=prev.next
		yield a if i>n
	}
end
f={
	'S'=>Kernel.method(:drop_next_square),
	's'=>Kernel.method(:drop_prev_square),
	'C'=>Kernel.method(:drop_next_cubic),
	'c'=>Kernel.method(:drop_prev_cubic),
	'h'=>RUBY_VERSION<'1.9' ?
		lambda{|enum|drop_cnt(100,enum)} :
		Kernel.method(:drop_cnt).to_proc.curry[100],
}
('2'..'9').each{|e|f[e]=RUBY_VERSION<'1.9' ?
	lambda{|enum|drop_num(e.to_i,enum)} :
	Kernel.method(:drop_num).to_proc.curry[e.to_i]
}

if $0==__FILE__
	STDOUT.sync=true
	while gets
		puts $_.chomp.chars.reduce(generate){|s,e|f[e][s]}.take(10)*','
=begin
		enum=generate
		$_.chomp.chars.each{|e|
			if e=='S'
				enum=drop_next_square(enum)
			elsif e=='s'
				enum=drop_prev_square(enum)
			elsif e=='C'
				enum=drop_next_cubic(enum)
			elsif e=='c'
				enum=drop_prev_cubic(enum)
			elsif e=='h'
				enum=drop_cnt(100,enum)
			else
				enum=drop_num(e.to_i,enum)
			end
		}
		puts enum.take(10)*','
=end
	end
end
```