多段階選抜 (F#)

多段階選抜
解答日
シリーズ:yieldの練習/ジェネレータを入れ子に/整数平方根・立方根の実装

問題
 

http://nabetani.sakura.ne.jp/hena/ord24eliseq/
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)
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

(icbrtの実装に関する)補題
2017/5/11
整数除算であってもn/(x*y)はn/x/yに等しい(ことの証明)
https://qiita.com/cielavenir/items/21a6711afd6be8c18c55

いつのまにか12言語になってしまいました。


  • F#ですが、実際はこってりとしたC#。そしてsolve関数だけすごく関数型っぽい、このギャップ。

  • cbrtはlibcを使用。

  • 拡張子はfsxにしているのでfsharpiから実行できるのかと思いきや、libcを呼び出しているためエラーになります。つまりせっかくのShebangが無意味です。


tyama_hena24_enum.fsx

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

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

open System
//open System.Runtime.InteropServices

//[<Literal>]
//let libc_="c"
//module libc=
// [<DllImport(libc_,CallingConvention=CallingConvention.Cdecl,EntryPoint="cbrt")>]
// extern double cbrt(double n)

let rec isqrt2 (n:int) (x:int) (y:int) =
if x=y || x+1=y then
x
else
isqrt2 n y ((n/y+y)/2)
let isqrt (n:int) =
if n=0 then
0
elif n<4 then
1
else
isqrt2 n 0 n
let rec icbrt2 (n:int) (x:int) (y:int) =
if x=y || x+1=y then
x
else
icbrt2 n y ((n/y/y+y*2)/3)
let icbrt (n:int) =
if n=0 then
0
elif n<8 then
1
else
icbrt2 n 0 n

let is_sq (n:int) =
//let x=int(Math.Sqrt(double(n)))
let x=isqrt n
x*x=n
let is_cb (n:int) =
//let x=int(libc.cbrt(double(n)))
let x=icbrt n
x*x*x=n
let is_multiple (i:int) (n:int) = i%n=0
let is_le (i:int) (n:int) = i<=n

let generate =
seq{
let mutable i=1
while true do
yield i
i<-i+1
}
let drop_prev check (_prev:int seq) =
seq{
let prev=_prev.GetEnumerator()
prev.MoveNext() |> ignore
let mutable a=prev.Current
prev.MoveNext() |> ignore
let mutable b=prev.Current
while true do
if not (check b) then
yield a
a<-b
prev.MoveNext() |> ignore
b<-prev.Current
}
let drop_next check (_prev:int seq) =
seq{
let prev=_prev.GetEnumerator()
prev.MoveNext() |> ignore
let mutable a=prev.Current
prev.MoveNext() |> ignore
let mutable b=prev.Current
yield a
while true do
if not (check a) then
yield b
a<-b
prev.MoveNext() |> ignore
b<-prev.Current
}
let drop_n check (n:int) (_prev:int seq) =
seq{
let prev=_prev.GetEnumerator()
let mutable i=0
while true do
i<-i+1
prev.MoveNext() |> ignore
let a=prev.Current
if not (check i n) then
yield a
}

let f0=[
('S',fun e->drop_next is_sq e);
('s',fun e->drop_prev is_sq e);
('C',fun e->drop_next is_cb e);
('c',fun e->drop_prev is_cb e);
('h',fun e->drop_n is_le 100 e);
]
let f=Seq.append f0 (List.map (fun i->(char(int('0')+i),fun e->drop_n is_multiple i e)) [2..9]) |> dict

let solve line=List.ofSeq line |> Seq.fold (fun s e->f.[e] s) generate |> Seq.take 10 |> Seq.map string |> String.concat "," |> Console.WriteLine

let mutable line=Console.ReadLine() in
while line<>null do
solve line
Console.Out.Flush()
line<-Console.ReadLine()