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();
}
}
}
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