JavaScriptでtr

コメントする

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' );

リリースノート

  • v1.1.1.zip [2015-11-09] – コードを整理
  • v1.1.0.zip [2015-11-08] – バックスラッシュの扱いを整備
  • v1.0.0.zip [2015-11-06] – 公開

JavaScriptでstrtr

コメントする

PHP の strtr を JavaScript で使えるようにしました。ここで出てる例と同じ結果を返すので多分問題ないと思います。

// 'hello all, I said hi'を返す
php_strtr( 'hi all, I said hello', {
    'h'     : '-',
    'hello' : 'hi',
    'hi'    : 'hello'
});

リリースノート

  • v1.0.1 [2015.11.10] – コードを整理
  • v1.0.0 [2015.11.05] – 公開

JavaScriptでガンマ関数

コメントする

ここの下の方にあるランチョス近似のコード（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;
})();

JavaScriptでparse_str（クエリ文字列のパース）

1件のコメント

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

　

リリースノート

  • v1.0.3 [2015.10.31] – URLエンコードを修正
  • v1.0.2 [2015.09.28] – 第四引数に対応
  • v1.0.1 [2015.09.28] – 処理を改善
  • v1.0.0 [2015.09.27] – 公開

シェルトの棋譜の圧縮

コメントする

シェルトの指し手は、動かす駒（29 通り）とその動き（盤上＋方向転換＋張り戻しの計 52 通り）と随伴情報（随伴なし＋上下左右随伴の計 5 通り）の三つで表すことができるので、単純に指し手を符号化する場合 $5+6+3=14$ ビットで表せることになります。

局面の最大分岐数（合法手数）は、将棋は 593 手1、チェスは今まで見つかっている中では 218 手2のようなので、だいたいシェルトの最大分岐数も 200 以下に収まる気がします（予想）。その場合、局面のすべての合法手を列挙＆ソートしたときのインデックスで手を表すという方法をとると、一手あたり 8 ビット程度で表せることになります。『シェルト-Vas e Lantis-』の棋譜URLでは一手あたり 7 ビットで表している（違法手は別の手段で表す）ので、$n$ 手の棋譜は $\frac{7}{6} n$ 文字で表されることになります。

  1. 将棋における最大分岐数 – 奈良女子大学 ↩
  2. max amount of moves from a position? ↩

シェルトの局面ハッシュ

コメントする

サイトに局面図を表示したい都合で局面図スクリプトを作っていたら、局面ハッシュ（圧縮）を再考してみたくなったので再考してみました。そのうち何らかの形でサイトの方にまとめると思います。

このハッシュは可逆ハッシュで、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, …）にしたほうが分かりやすそうです。

移転

コメントする

サイトのサーバーを変えたのでブログも変えてみた。
借り物のブログをやめてサイトと同じサーバーに纏めたのですっきり感ある。