多段階選抜 (PHP/JavaScript)

多段階選抜
解答日
シリーズ: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


PHP (5.5以降専用)

ラムダ式への正しい変数束縛の方法を知った。useを使うんですね。


hena24_enum.php

#!/usr/bin/env php

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

//function cbrt($n){
// return pow($n,1-2.0/3);
//}

function isqrt($n){
if($n<=0)return 0;
if($n<4)return 1;
$x=0;$y=$n;
for(;$x!=$y&&$x+1!=$y;){$x=$y;$y=intval((intval($n/$y)+$y)/2);}
return $x;
}
function icbrt($n){
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=intval( (intval(intval($n/$y)/$y)+$y*2)/3 );}
return $x;
}

function generate(){
$i=1;
for(;;){
yield $i;
$i++;
}
}

function drop_prev($check,$prev){
$prev->rewind();
$a=$prev->current();
$prev->next();
$b=$prev->current();
for(;;){
if(!$check($b))yield $a;
$a=$b;
$prev->next();
$b=$prev->current();
}
}
function drop_next($check,$prev){
$prev->rewind();
$a=$prev->current();
$prev->next();
$b=$prev->current();
yield $a;
for(;;){
if(!$check($a))yield $b;
$a=$b;
$prev->next();
$b=$prev->current();
}
}
function drop_n($check,$n,$prev){
$prev->rewind();
$i=0;
for(;;){
$i+=1;
$a=$prev->current();
$prev->next();
if(!$check($i,$n))yield $a;
}
}
function is_sq($n){
//$x=intval(sqrt($n));
$x=isqrt($n);
return $x*$x==$n;
}
function is_cb($n){
//$x=intval(cbrt($n));
$x=icbrt($n);
return $x*$x*$x==$n;
}
function is_multiple($i,$n){
return $i%$n==0;
}
function is_le($i,$n){
return $i<=$n;
}

$f=[
'S'=>function($enum){return drop_next('is_sq',$enum);},
's'=>function($enum){return drop_prev('is_sq',$enum);},
'C'=>function($enum){return drop_next('is_cb',$enum);},
'c'=>function($enum){return drop_prev('is_cb',$enum);},
'h'=>function($enum){return drop_n('is_le',100,$enum);},
];
for($i=2;$i<=9;$i++){$f[(string)$i]=function($enum)use($i){return drop_n('is_multiple',$i,$enum);};}

for(;$line=fgets(STDIN);){
//cS => $f['S']($f['c'](generate()))
$z=array_reduce(str_split(rtrim($line)),function($s,$e)use($f){return $f[$e]($s);},generate());
$z->rewind();
$cnt=10;
$a=[];
for($i=0;$i<$cnt;$i++){
$a[]=$z->current();
if($i<$cnt-1)$z->next();
}
echo implode(',',$a).PHP_EOL;
flush(); //STDOUT);
}



JavaScript (node.js 0.11以降専用。Ubuntu node.js-devel PPAで確認)

v8でも動くようになった。

Node.jsのIOの仕様により、採点プログラムv1では採点できません。


hena24_enum.js

//usr/bin/env node --harmony $0 $@;exit

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

var isqrt=function(n){
if(n<=0)return 0;
if(n<4)return 1;
var x=0,y=n;
for(;x!=y&&x+1!=y;){x=y;y=Math.floor((Math.floor(n/y)+y)/2);}
return x;
}
var icbrt=function(n){
if(n<0)return icbrt(-n);
if(n==0)return 0;
if(n<8)return 1;
var x=0,y=n;
for(;x!=y&&x+1!=y;){x=y;y=Math.floor( (Math.floor(Math.floor(n/y)/y)+y*2)/3 );}
return x;
}

var generate=function*(){
var i=1;
for(;;){
yield i;
i++;
}
};

var drop_prev=function*(check,prev){
//var {value: a}=prev.next(); //not working yet
var a=prev.next().value;
var b=prev.next().value;
for(;;){
if(!check(b))yield a;
a=b;
b=prev.next().value;
}
};
var drop_next=function*(check,prev){
var a=prev.next().value;
var b=prev.next().value;
yield a;
for(;;){
if(!check(a))yield b;
a=b;
b=prev.next().value;
}
};
var drop_n=function*(check,n,prev){
var i=0;
for(;;){
i+=1
a=prev.next().value;
if(!check(i,n))yield a;
}
};

var is_sq=function(n){
//var x=Math.sqrt(n)^0;
var x=isqrt(n);
return x*x==n;
};
var is_cb=function(n){
//var x=cbrt(n)^0;
var x=icbrt(n);
return x*x*x==n;
};
var is_multiple=function(i,n){return i%n==0;};
var is_le=function(i,n){return i<=n;};

var f={
S:function(_enum){return drop_next(is_sq,_enum);},
s:function(_enum){return drop_prev(is_sq,_enum);},
C:function(_enum){return drop_next(is_cb,_enum);},
c:function(_enum){return drop_prev(is_cb,_enum);},
h:function(_enum){return drop_n(is_le,100,_enum);},
};
for(var i=2;i<=9;i++){
(function(){
var j=i;
f[String(j)]=function(_enum){return drop_n(is_multiple,j,_enum);};
})()
}

var solve=function(s){
//cS => f['S'](f['c'](generate()))
var z=s.split('').reduce(function(s,e){return f[e](s);},generate());
var a=[];
for(var j=0;j<10;j++)a[j]=z.next().value;
return a.join(',');
}

//var cbrt=(typeof Math.cbrt==='function') ? Math.cbrt : function(n){return Math.pow(n,1-2/3);};

var main=function(){
for(var line;line=readline();)print(solve(line));
}

/// IO ///
if(typeof process!=='undefined'){
//node.js
var print=function(x){
console.log(x);
}
var readline=(function(){
var T=[],cnt=0;
var stdin = process.openStdin();
stdin.setEncoding('utf8');

var input_fragment="";
stdin.on('data', function(input) {
var ref=(input_fragment+input).split("\n");
input_fragment=ref.pop();
for(var i=0;i<ref.length;i++){
if(ref[i]=='')continue;
T.push(ref[i]);
}
});
stdin.on('end', function(z) {
if(input_fragment){
var ref=(input_fragment+"\n").split("\n");
input_fragment=ref.pop();
for(var i=0;i<ref.length;i++){
if(ref[i]=='')continue;
T.push(ref[i]);
}
}
main();
});

return function(){
if(T.length<=cnt)return null;
return T[cnt++];
};
})();
}else{
//v8
main();
}