HSPでコムソート
HSPで一次元配列をコムソートでソートするための命令を作りました。
サンプルファイルのようにして比較関数(のようなもの)を作って使用します。
- combsort.hsp-v1.0.0.zip
- combsort.hsp
- combsort-sample.hsp
リリースノート:
- v1.0.0 [2015.12.20]:公開
HSPで一次元配列をコムソートでソートするための命令を作りました。
サンプルファイルのようにして比較関数(のようなもの)を作って使用します。
リリースノート:
JavaScriptでPerlのtrを使えるようにしました。
文字リスト(第二,第三引数)中でバックスラッシュ(円記号)を使う場合、各バックスラッシュについてエスケープ(\→\)する必要があるので、Perlに対して倍の量が必要になります。
// Perl
$str =~ tr/A\\Z/a\-z/;
// JavaScript
perl_tr( str, 'A\\\\Z', 'a\\-z' );
以下動作例です。
// 'AAABBBefg' を返す
perl_tr( 'AAabcdefg', 'abcd', 'AB' );
// 'BBabcdBBB' を返す
perl_tr( 'AAabcdefg', 'abcd', 'AB', 'c' );
// 'AAABefg' を返す
perl_tr( 'AAabcdefg', 'abcd', 'AB', 'd' );
// 'AAABefg' を返す
perl_tr( 'AAabcdefg', 'abcd', 'AB', 's' );
// 'J S ' を返す
perl_tr( 'JavaScript', 'A-Z', ' ', 'cs' );
PHP の strtr を JavaScript で使えるようにしました。ここで出てる例と同じ結果を返すので多分問題ないと思います。
// 'hello all, I said hi'を返す
php_strtr( 'hi all, I said hello', {
'h' : '-',
'hello' : 'hi',
'hi' : 'hello'
});
ここの下の方にあるランチョス近似のコード(Python)を JavaScript にしてみた。
/*
* Γ(x) = (x - 1)! = Gamma(x)
*/
var Gamma = (function()
{
var p = [
676.5203681218851,
-1259.1392167224028,
771.32342877765313,
-176.61502916214059,
12.507343278686905,
-0.13857109526572012,
9.9843695780195716e-6,
1.5056327351493116e-7
];
var g = 7;
function Gamma( z )
{
if( z < 0.5 ){
return Math.PI/( Math.sin(Math.PI*z)*Gamma(1-z) );
}
z --;
var x = 0.99999999999980993;
for( var i=p.length; i--; ){
x += p[i] / (z + i + 1);
}
var t = z + g + 0.5;
var G = Math.sqrt(Math.PI*2) *Math.exp( (z+0.5)*Math.log(t)-t ) *x;
if( Math.floor(z) === z ){
return Math.round( G );
} else {
return G;
}
}
return Gamma;
})();
少し書き換えて対数ガンマ関数を計算できるようにしたものも置いておきます。
/*
* ln Γ(x) = GammaLN(x)
*/
var GammaLN = (function()
{
var p = [
676.5203681218851,
-1259.1392167224028,
771.32342877765313,
-176.61502916214059,
12.507343278686905,
-0.13857109526572012,
9.9843695780195716e-6,
1.5056327351493116e-7
];
var g = 7;
var LN_PI = Math.log( Math.PI );
function GammaLN( z )
{
if( z < 0.5 ){
return LN_PI -Math.log(Math.sin( Math.PI*z )) -GammaLN(1-z);
}
z --;
var x = 0.99999999999980993;
for( var i=p.length; i--; ){
x += p[i] / (z + i + 1);
}
var t = z + g + 0.5;
return ( LN_PI+Math.LN2 )/2 +Math.log(x) +(z+0.5)*Math.log(t) -t;
}
return GammaLN;
})();
ついでに逆数を計算できるようにしたものも。
/*
* 1/Γ(x) = GammaInv(x)
*/
var GammaInv = (function()
{
var p = [
676.5203681218851,
-1259.1392167224028,
771.32342877765313,
-176.61502916214059,
12.507343278686905,
-0.13857109526572012,
9.9843695780195716e-6,
1.5056327351493116e-7
];
var g = 7;
function GammaInv( z )
{
if( z < 0.5 ){
return Math.sin(Math.PI*z) /( Math.PI*GammaInv(1-z) );
}
z --;
var x = 0.99999999999980993;
for( var i=p.length; i--; ){
x += p[i] / (z + i + 1);
}
var t = z + g + 0.5;
return Math.exp( t-(z+0.5)*Math.log(t) ) /Math.sqrt(Math.PI*2) /x;
}
return GammaInv;
})();
PHPのparse_strをJavaScriptで使うためのコードをつくりました。入れ子の配列にも対応してたら長く(100行程度)なったのでzipにしたものを置いておきます。
http_parse_query.js-v1.0.3.zip
これを script
タグで読み込むと関数 http_parse_query
が定義されます。parse_str
とはやや使い方が異なるので違う名前にしました。
var query_str = 'a=0&b%5B%5D=1&b%5B%5D=2&b%5B%5D=3&c%5Bk%5D%5B%5D%5Br%5D=4';
var output = http_parse_query( query_str );
// 結果
output = {
"a" : "0",
"b" : ["1","2","3"],
"c" : { "k":[ {"r":"4"} ] }
}
配列は、すべての要素が0番からの連番になっている場合のみ添字配列として扱い、連番になっていない要素を含む場合は連想配列扱いになります。
第二・第三・第四引数に文字列を渡すと、PHP の http_build_query()
のそれと同じように解釈します。またクエリ文字列のURLエスケープは UTF-8 でしてある必要があります。
var query_str = 'var_0=%E3%81%82;var_1=%E3%81%84;var_2=%E3%81%86+%E3%81%88';
var output = http_parse_query( query_str, 'var_', ';', 'PHP_QUERY_RFC3986' );
// 結果
output = ["あ","い","う+え"];
URLのクエリ文字列をパースするコードは次のようになります。
// JavaScript
var output = http_parse_query( location.search.substr(1) );
// PHP(参考)
parse_str( $_SERVER['QUERY_STRING'], $output );
シェルトの指し手は、動かす駒(29 通り)とその動き(盤上+方向転換+張り戻しの計 52 通り)と随伴情報(随伴なし+上下左右随伴の計 5 通り)の三つで表すことができるので、単純に指し手を符号化する場合 $5+6+3=14$ ビットで表せることになります。
局面の最大分岐数(合法手数)は、将棋は 593 手1、チェスは今まで見つかっている中では 218 手2のようなので、だいたいシェルトの最大分岐数も 200 以下に収まる気がします(予想)。その場合、局面のすべての合法手を列挙&ソートしたときのインデックスで手を表すという方法をとると、一手あたり 8 ビット程度で表せることになります。『シェルト-Vas e Lantis-』の棋譜URLでは一手あたり 7 ビットで表している(違法手は別の手段で表す)ので、$n$ 手の棋譜は $\frac{7}{6} n$ 文字で表されることになります。
サイトに局面図を表示したい都合で局面図スクリプトを作っていたら、局面ハッシュ(圧縮)を再考してみたくなったので再考してみました。そのうち何らかの形でサイトの方にまとめると思います。
このハッシュは可逆ハッシュで、34 文字(204 ビット)で 1 つの局面を表すことができます。1 文字あたり 6 ビットを割り当てて、文字は Base64url と同じものを使います。この場合表現できる状態の数は $2\times 10^{61}$ ということになりますが、以前シェルトの合法局面数を計算(ページ作成中)したところ $8\times 10^{49}$ という値になったので、やろうと思えばもっと縮められるはずということになります。ただ、ここから縮めようとするとちょっと面倒なことにならざるを得ない感じだったので、やめることにしました。
このハッシュは、手番情報と方向転換情報からなる先頭 5 文字($1+29$ ビット)と、1 文字あたり 1 つの駒の状態を表した 29 文字を合わせた計 34 文字からなります。手番情報は、次の手番が先手か後手かを表すもので、方向転換情報は、29 の駒が方向転換しているかどうかを(方向転換不能な駒も含めて)表すものです。この場合、1つの駒がとりうる状態は盤上のマス(49 通り)と持ち駒台と張り駒台と駒箱の計 52 通りなので、ちょうど 1 文字で表せることになります。
この仕様だと 1 文字に 1 つの駒の情報が(方向転換を除いて)対応するうえビットが余りなく(6 ビットで区切る場合)使い切られるので、個人的に扱いやすそう&まとまってる感があります。駒の情報の並びについては使徒の順(dia, vio, lis, …)にすることを考えました。なお後衛の方向転換情報を取り除くと 2 文字削れて 32 文字(2 ビット余り)になります。この場合は駒の情報の並びは開始局面に倣ったもの(pal, ful, mik, …)にしたほうが分かりやすそうです。
サイトのドメイン名がmatrix exponential(行列指数関数)なのでそれに因んだものを作りたい。 [Read more…]
サイトのサーバーを変えたのでブログも変えてみた。
借り物のブログをやめてサイトと同じサーバーに纏めたのですっきり感ある。