Multi-stage selection (Go / C # / Ruby / Python)

Multi-stage selection Answer date series:Yield practice/Nesting generators/Implementation of integer square root and cube root
problem http://nabetani.sakura.ne.jp/hena/ord24eliseq/
https://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
Ruby 2014/8/2(On the day) https://qiita.com/cielavenir/items/9f15e29b73ecf98968a5
C#/Python 2014/8/4 https://qiita.com/cielavenir/items/a1156e6a4f71ddbe5dcb
Drop from here_prev_square/drop_prev_Answer before putting together 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)
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
(Regarding the implementation of icbrt)Lemma 2017/5/11 N even for integer division/(x*y)Is n/x/Equal to y(Proof of that)
https://qiita.com/cielavenir/items/21a6711afd6be8c18c55

[140805] fixed cbrt. Also fixed a bug in Py3.

All are infinite lists. I was pointed out by Mr. Nabeya that it wasn't DRY, so I refactored it.

Github commit log. https://github.com/cielavenir/procon/commit/752122c53288d8428dc4aadfbdfae7eac151eea2 We succeeded in reducing an average of 25 lines.

By the way, aren't there any methods in Go and C # that partially apply functions?

Go It would be so much easier without using Generics.

hena24_enum.go


//usr/bin/env go run $0 $@;exit

// http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
// http://nabetani.sakura.ne.jp/hena/ord24eliseq/

package main
import (
	"fmt"
	//"math"
	"bufio"
	"os"
)

func isqrt(n int) int{
	if n<=0 {return 0}
	if n<4 {return 1}
	x:=0
	y:=n
	for x!=y&&x+1!=y {x=y;y=(n/y+y)/2}
	return x
}
func icbrt(n int) int{
	if n<0 {return icbrt(-n)}
	if n==0 {return 0}
	if n<8 {return 1}
	x:=0
	y:=n
	for x!=y&&x+1!=y {x=y;y=(n/y/y+y*2)/3}
	return x
}

func is_sq(n int) bool{
	//x:=int(math.Sqrt(float64(n)))
	x:=isqrt(n)
	return x*x==n
}
func is_cb(n int) bool{
	//x:=int(math.Cbrt(float64(n)))
	x:=icbrt(n)
	return x*x*x==n
}
func is_multiple(i int,n int) bool{ return i%n==0 }
func is_le(i int,n int) bool{ return i<=n }

func generate() <-chan int{
	ch := make(chan int)
	go func(){
		i:=1
		for {
			ch <- i
			i++
		}
	}()
	return ch
}

func drop_prev(check func(int)bool,prev <-chan int) <-chan int{
	ch := make(chan int)
	go func(){
		a:=<-prev
		b:=<-prev
		for {
			if !check(b) { ch<-a }
			a=b
			b=<-prev
		}
	}()
	return ch
}

func drop_next(check func(int)bool,prev <-chan int) <-chan int{
	ch := make(chan int)
	go func(){
		a:=<-prev
		b:=<-prev
		ch<-a
		for {
			if !check(a) { ch<-b }
			a=b
			b=<-prev
		}
	}()
	return ch
}

func drop_n(check func(int,int)bool,n int,prev <-chan int) <-chan int{
	ch := make(chan int)
	go func(){
		i:=0
		for {
			i++
			a:=<-prev
			if !check(i,n) { ch<-a }
		}
	}()
	return ch
}

func main(){
	f:=map[int]func(<-chan int)<-chan int{
		'S': func(prev <-chan int)<-chan int{return drop_next(is_sq,prev)},
		's': func(prev <-chan int)<-chan int{return drop_prev(is_sq,prev)},
		'C': func(prev <-chan int)<-chan int{return drop_next(is_cb,prev)},
		'c': func(prev <-chan int)<-chan int{return drop_prev(is_cb,prev)},
		'h': func(prev <-chan int)<-chan int{return drop_n(is_le,100,prev)},
	}
	for i:=2;i<10;i++ {
		j:=i //Create a short-lived scope to avoid bugs in lambda-style captures.
		f[j+'0']=func(prev <-chan int)<-chan int{return drop_n(is_multiple,j,prev)}
	}

	sin:=bufio.NewReader(os.Stdin)
	_line,_,_:=sin.ReadLine()
	line:=string(_line)
	for line!="" {
		//cS => f['S'](f['c'](generate()))
		ch := generate()
		for _,c:=range(line) {
			ch=f[int(c)](ch)
		}
		for i:=0;i<10;i++ {
			if i>0 { fmt.Print(",") }
			a:=<-ch
			fmt.Printf("%d",a)
		}
		fmt.Println()
		os.Stdout.Sync()
		_line,_,_=sin.ReadLine()
		line=string(_line)
	}
}

C# ##

hena24_enum.cs


// http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
// http://nabetani.sakura.ne.jp/hena/ord24eliseq/

using System;
using System.Linq;
using System.Collections.Generic;
//using System.Runtime.InteropServices;

class Hena24{
	//[DllImport("c")]
	//private extern static double cbrt(double d);

	static private int isqrt(int n){
		if(n<=0)return 0;
		if(n<4)return 1;
		int x=0,y=n;
		for(;x!=y&&x+1!=y;){x=y;y=(n/y+y)/2;}
		return x;
	}
	static private int icbrt(int n){
		if(n<0)return icbrt(-n);
		if(n==0)return 0;
		if(n<8)return 1;
		int x=0,y=n;
		for(;x!=y&&x+1!=y;){x=y;y=(n/y/y+y*2)/3;}
		return x;
	}

	static private bool is_sq(int n){
		//int x=(int)Math.Sqrt(n);
		int x=isqrt(n);
		return x*x==n;
	}
	static private bool is_cb(int n){
		//int x=(int)cbrt(n);
		int x=icbrt(n);
		return x*x*x==n;
	}
	static private bool is_multiple(int i,int n){return i%n==0;}
	static private bool is_le(int i,int n){return i<=n;}

	static private IEnumerable<int> generate(){
		int i=1;
		for(;;){
			yield return i;
			i+=1;
		}
	}
	static private IEnumerable<int> drop_prev(
		Func<int,bool> check,IEnumerable<int> _prev
	){
		IEnumerator<int> prev=_prev.GetEnumerator();
		prev.MoveNext();
		int a=prev.Current;
		prev.MoveNext();
		int b=prev.Current;
		for(;;){
			if(!check(b))yield return a;
			a=b;
			prev.MoveNext();
			b=prev.Current;
		}
	}
	static private IEnumerable<int> drop_next(
		Func<int,bool> check,IEnumerable<int> _prev
	){
		IEnumerator<int> prev=_prev.GetEnumerator();
		prev.MoveNext();
		int a=prev.Current;
		prev.MoveNext();
		int b=prev.Current;
		yield return a;
		for(;;){
			if(!check(a))yield return b;
			a=b;
			prev.MoveNext();
			b=prev.Current;
		}
	}
	static private IEnumerable<int> drop_n(
		Func<int,int,bool> check,int n,IEnumerable<int> _prev
	){
		IEnumerator<int> prev=_prev.GetEnumerator();
		int i=0;
		for(;;){
			i++;
			prev.MoveNext();
			int a=prev.Current;
			if(!check(i,n))yield return a;
		}
	}
	static public void Main(){
		var f=new Dictionary<char,Func<IEnumerable<int>,IEnumerable<int>>>(){
			{'S',e => drop_next(is_sq,e)},
			{'s',e => drop_prev(is_sq,e)},
			{'C',e => drop_next(is_cb,e)},
			{'c',e => drop_prev(is_cb,e)},
			{'h',e => drop_n(is_le,100,e)},
		};
		for(int i=2;i<10;i++){
			int j=i; //Create a short-lived scope to avoid bugs in lambda-style captures.
			f[(char)('0'+j)] = e=>drop_n(is_multiple,j,e);
		}
		string line;
		for(;(line=Console.ReadLine())!=null;){
			bool first=true;
			//cS => f['S'](f['c'](generate()))
			foreach(int n in line.Aggregate(generate(),(s,e)=>f[e](s)).Take(10)){
				if(!first)Console.Write(',');
				first=false;
				Console.Write(n);
			}
			Console.WriteLine();
			Console.Out.Flush();
		}
	}
}

Feasible

If you prepare such csx, it seems that you can execute it directly.

tyama_hena24_enum.csx


//usr/bin/env csi $0 $@;exit

#load "tyama_hena24_enum.cs"
Hena24.Main()

Ruby

hena24_enum.rb


#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
#http://nabetani.sakura.ne.jp/hena/ord24eliseq/

=begin
if RUBY_VERSION<'1.9'
	module Math
		def self.cbrt(n)
			n**(1-2.0/3)
		end
	end
end
=end

class Integer
	def isqrt
		return 0 if self<=0
		return 1 if self<4 # 1
		x,y=0,self
		while x!=y&&x+1!=y
			x,y=y,(self/y+y)/2
		end
		x
	end
	def icbrt
		return -self.icbrt if self<0
		return 0 if self==0
		return 1 if self<8 # 1,7
		x,y=0,self
		while x!=y&&x+1!=y
			x,y=y,(self/y/y+y*2)/3
		end
		x
	end
end

=begin
def generate
	return to_enum(:generate) if !block_given?
	i=1
	loop{
		yield i
		i+=1
	}
end
=end

def drop_prev(check,prev)
	return to_enum(:drop_prev,check,prev) if !block_given?
	a=prev.next
	b=prev.next
	loop{
		yield a if !check[b]
		a,b=b,prev.next
	}
end
def drop_next(check,prev)
	return to_enum(:drop_next,check,prev) if !block_given?
	a=prev.next
	b=prev.next
	yield a
	loop{
		yield b if !check[a]
		a,b=b,prev.next
	}
end
def drop_n(check,n,prev)
	return to_enum(:drop_n,check,n,prev) if !block_given?
	i=0
	loop{
		i+=1
		a=prev.next
		yield a if !check[i,n]
	}
end

is_sq=lambda{|n|n.isqrt**2==n}
is_cb=lambda{|n|n.icbrt**3==n}
is_multiple=lambda{|i,n|i%n==0}
is_le=lambda{|i,n|i<=n}

if RUBY_VERSION<'1.9'
	f={
		'S'=>lambda{|enum|drop_next(is_sq,enum)},
		's'=>lambda{|enum|drop_prev(is_sq,enum)},
		'C'=>lambda{|enum|drop_next(is_cb,enum)},
		'c'=>lambda{|enum|drop_prev(is_cb,enum)},
		'h'=>lambda{|enum|drop_n(is_le,100,enum)},
	}
	(2..9).each{|e|f[e.to_s]=lambda{|enum|drop_n(is_multiple,e,enum)}}
else
	f={
		'S'=>Kernel.method(:drop_next).to_proc.curry[is_sq],
		's'=>Kernel.method(:drop_prev).to_proc.curry[is_sq],
		'C'=>Kernel.method(:drop_next).to_proc.curry[is_cb],
		'c'=>Kernel.method(:drop_prev).to_proc.curry[is_cb],
		'h'=>Kernel.method(:drop_n).to_proc.curry[is_le,100],
	}
	(2..9).each{|e|f[e.to_s]=Kernel.method(:drop_n).to_proc.curry[is_multiple,e]}
end

if $0==__FILE__
	STDOUT.sync=true
	while gets
		#cS => f['S'].call(f['c'].call(1.upto(1/0.0)))
		puts $_.chomp.chars.reduce(1.upto(1/0.0)){|s,e|f[e][s]}.take(10)*','

		#enum=generate
		#$_.chomp.chars.each{|e|enum=f[e][enum]}
		#puts enum.take(10)*','
	end
end

Python

hena24_enum.py


#!/usr/bin/env python
#http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
#http://nabetani.sakura.ne.jp/hena/ord24eliseq/
import sys
import itertools
from functools import partial,reduce

'''
from math import sqrt
try:
	#from scipy.special import cbrt # thx @ryosy383
    from numpy import cbrt
except ImportError:
	try:
		import ctypes
		if sys.platform.startswith('linux'):
			libm=ctypes.cdll.LoadLibrary('libm.so.6')
		elif sys.platform=='darwin':
			libm=ctypes.cdll.LoadLibrary('libSystem.dylib')
		elif sys.platform=='win32':
			libm=ctypes.cdll.LoadLibrary('msvcr120.dll')
		else:
			raise ImportError
		cbrt=lambda n:libm.cbrt(ctypes.c_double(n))
		libm.cbrt.restype=ctypes.c_double
	except ImportError:
		cbrt=lambda n: n**(1-2.0/3)
'''

def isqrt(n):
	if n<=0: return 0
	if n<4: return 1
	x,y=0,n
	while x!=y and x+1!=y:
		x,y=y,(n//y+y)//2
	return x
def icbrt(n):
	if n<0: return icbrt(-n)
	if n==0: return 0
	if n<8: return 1
	x,y=0,n
	while x!=y and x+1!=y:
		x,y=y,(n//y//y+y*2)//3
	return x

if sys.version_info[0]>=3: raw_input=input

'''
def generate():
	i=1
	while True:
		yield i
		i+=1
'''

def drop_prev(check,prev):
	a=next(prev)
	b=next(prev)
	while True:
		if not check(b): yield a
		a,b=b,next(prev)

def drop_next(check,prev):
	a=next(prev)
	b=next(prev)
	yield a
	while True:
		if not check(a): yield b
		a,b=b,next(prev)

def drop_n(check,n,prev):
	i=0
	while True:
		i+=1
		a=next(prev)
		if not check(i,n): yield a

is_sq=lambda n: isqrt(n)**2==n
is_cb=lambda n: icbrt(n)**3==n
is_multiple=lambda i,n: i%n==0
is_le=lambda i,n: i<=n

f={
	'S': partial(drop_next,is_sq),
	's': partial(drop_prev,is_sq),
	'C': partial(drop_next,is_cb),
	'c': partial(drop_prev,is_cb),
	'h': partial(drop_n,is_le,100),
}

#cf: https://twitter.com/closureobject/status/678619154346151941
for e in range(2,10): f[str(e)]=partial(drop_n,is_multiple,e) # OK
#for e in range(2,10): f[str(e)]=lambda n:drop_n(is_multiple,e,n) #NG
#for e in range(2,10): f[str(e)]=(lambda x:lambda n:drop_n(is_multiple,x,n))(e) # OK

if __name__=='__main__':
	try:
		while True:
			#cS => f['S'](f['c'](itertools.count(1)))
			'''
			print(','.join(
				map(str,itertools.islice(
					reduce(lambda s,e:f[e](s),raw_input().rstrip(),itertools.count(1)),
				10))
			))
			'''
			g=reduce(lambda s,e:f[e](s),raw_input().rstrip(),itertools.count(1))
			print(','.join(str(next(g)) for i in range(10)))
			sys.stdout.flush()
	except EOFError:
		pass

Recommended Posts

Multi-stage selection (Go / C # / Ruby / Python)
Multi-stage selection (C # / Python) (old)
Multi-stage selection
Call popcount from Ruby / Python / C #
msgpack deserialization performance comparison (C ++ / Python / Ruby)
Python with Go
python C ++ notes
python, openFrameworks (c ++)
GNU GLOBAL (gtags) + α in Go, Ruby, Python
paiza POH ec-campaign (C # / Java / Python / Ruby) # paizahack_01
Grouping combination in Python / Ruby / PHP / Golang (Go)
Python C / C ++ Extension Pattern-Pointer
Ruby, Python and map
Ruby, Python code fragment execution of selection in Emacs
Next Python in C
Python and Ruby split
This Week's Algorithm: Shortest Path Calculation! (Permutation iterator in Ruby / Python / C # / VB / Go)
Handle prime numbers in Python / Ruby / PHP / Golang (Go)
C API in Python 3
ABC147 C --HonestOrUnkind2 [Python]
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Mandelbrot Benchmark (C, PHP, HHVM, Ruby, Python, PyPy, and Kinx)
Five languages basic grammar comparison (C #, Java, Python, Ruby, Kotlin)
Overlapping combinations with limits in Python / Ruby / PHP / Golang (Go)
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Newton's method in C ++, Python, Go (for understanding function objects)
Factorial, permutations, (duplicate) combinations in Python / Ruby / PHP / Golang (Go)
Extend python in C ++ (Boost.NumPy)
Python on Ruby and angry Ruby on Python
ABC163 C problem with python3
PyTorch C ++ VS Python (2019 Edition)
Java VS PHP VS Python VS Ruby
C / C ++ programmer challenges Python (class)
ABC memorandum [ABC163 C --managementr] (Python)
Python and ruby slice memo
Standard input / summary / python, ruby
Behavior of division operators between integers (C, C ++, Scala, Java, Rust, Go, PHP, JavaScript, Perl, Python, Ruby)
Binary search in Python / C ++
Zundokokiyoshi with python / ruby / Lua
About Perl, Python, PHP, Ruby
Ruby and Python syntax ~ branch ~
Ruby, Python Module Installation Guide
I tried Python C extension
Python started by C programmers
ABC188 C problem with python3
ABC187 C problem with python
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Summary of how to write if statements (Scala, Java, Rust, C language, C ++, Go language, PHP, Perl, Python, Ruby)
Summary of how to write increment / decrement (Scala, Java, Rust, C, C ++, Go, PHP, Perl, Python, Ruby, JavaScript)