プログラミングの最近のブログ記事

　普段訪れる事のないハードディスクの深い階層に、過去に書いたあるシステムのPHPのソース群が格納されていた。
　拡張子は.php3、ファイルの日付は2001年。7年前のPHP3ファイルだった。

　初めてデータベース連携に挑戦したシステムだったはずで、このシステムは結局日の目を見ることはなかったのだけど、試しにファイルを開いてみたところ絶望的なありさま。

　薄ら寒くなった。


　でも大切に取っておきます。

　どう書く？orgに投稿。

　今回のお題は必ず解ける迷路です。

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。ループも認めません。
4. 出力の度にランダムな迷路であること。ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

　迷路生成のアルゴリズムはここを参考にさせて頂きました。
　迷路のアルゴリズムなんてこんな機会が無ければ調べたり考えたりする事ないので楽しかったです。

　以下投稿したコード。選択した言語はPHP。「棒倒し法」と呼ばれるアルゴリズムを採用しています。暇を見つけて「穴掘り法」や「壁延ばし法」などでも組んで見たいと思っています。

<?php
function Maze($x, $y)
{
    /* init     */
    $l_array = str_repeat('1', $x*2-1+2);
    $s_array = array_fill(0, $x*2-1, '0');
    $p_array = str_split(str_repeat('01', $x-1).'0');
    $work = array();
    $work[] = $s_array;
    $work[] = $p_array;
    $work[] = $s_array;

    /* build    */
    $maze = $l_array."\n";
    for ($row = 0; $row < $y-1; $row++) {
        for ($col = 0; $col < $x-1; $col++) {
            wall($work, $row, $col);
        }
        $maze .= '1'.implode('', array_shift($work))."1\n";
        $maze .= '1'.implode('', array_shift($work))."1\n";
        $work[] = $p_array;
        $work[] = $s_array;
    }
    $maze .= '1'.implode('', array_shift($work))."1\n";
    $maze .= $l_array."\n";
    $maze = strtr($maze, array('1'=>'■', '0'=>'　'));

    return $maze;
}

function wall(&$work, $row, $col)
{
    $w = array();
    if ($row == 0 && $work[0][$col*2+1] == '0') {
        $w[] = array(0, $col*2+1);
    }
    if ($work[1][$col*2+2] == '0') {
        $w[] = array(1, $col*2+2);
    }
    if ($work[2][$col*2+1] == '0') {
        $w[] = array(2, $col*2+1);
    }
    if ($work[1][$col*2] == '0') {
        $w[] = array(1, $col*2);
    }
    shuffle($w);
    $work[$w[0][0]][$w[0][1]] = '1';
}
?>

　どう書く？orgに投稿。

　お題は文字のセンタリングです。

　文字列を指定のカラム幅にセンタリング配置する関数を示してください。文字列の長さが指定した幅より長い場合には文字列の両端をできるだけ均等に切り落して指定幅に収めてください。1文字は1カラムに収まるものと仮定してかまいません。

　最初、文字列と幅を比較して、幅に収まるようなら前後にスペースをWhileで追加、幅を超えるようなら前後をWhileで切り飛ばしていくという力任せ的なコード書いたんですけど、マニュアル読んだらPHPには本件にうってつけの関数が既に用意されていました。
　str_padは前後にスペース(文字種指定可)を追加するのみでなく、文字列の切り飛ばしも行ってくれるのですが、今回のお題のように「前後から均等に」という仕様ではないのでifで処理分けてます。

　以下投稿したコード。選択した言語はPHP。シンプルでわかりやすいと思う。

<?php
function Centering($str, $width)
{
    $slen = strlen($str);
    if ($slen < $width) {
        $str = str_pad($str, $width, ' ', STR_PAD_BOTH);
    } else {
        $str = substr($str, (int)(($slen - $width)/2), $width);
    }
    return $str;
}
?>

　どう書く？orgに投稿。

お題は与えられた並べ替えを実現するあみだくじの生成です。

　0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。

制約条件

• あみだの横棒は縦棒をまたぐことはできません。常に隣接する縦棒同士の交換となります 。
• 同じ行に複数の横棒があっても良いですが、ひとつの縦棒の同じ点からふたつ横棒が出ることはありません。

　最初、ここやここを読んで、どうやってロジック組むかと考えたのですが、前回投稿した『あみだくじ』を組んだ際、ソートすれば良い事に気づきました。
　パラメータで渡されるリストの先頭から隣り合う要素同士を比較し、その大小によって要素を入れ替え、これをリスト末端まで試行します。要素入れ替えの発生はあみだくじの横棒になります。これを1ステップとして記録し、ソートが完了するまで繰り返します。
　このソート方法はバブルソートに似ていますが、バブルソートと異なる点は、入れ替えが発生した要素は、そのステップ内ではもう動かしてはいけないという点です。
　ソートが完了したら、記録したソート過程（ステップ）を逆順とし、これをあみだくじのパターンとします。

　以下、投稿したコード。選択した言語はPHP。パラメータとして渡すリストは文字列型にする必要があります。また、お題では数字のリストという事ですが、英数字に対応した関数となっています。

<?php
function CreateAmida($org)
{
    if (!ctype_alnum($org) ||
        count(array_unique(str_split($org))) != count(str_split($org))) {
        return NULL;
    }
    $bridge_num = strlen($org)-1;
    $p = $org;
    $step = array();
    while (1) {
        $chg = FALSE;
        $step_buf = array_fill(0, $bridge_num, ' ');
        for ($i = 0; $i < $bridge_num; $i++) {
            if ($p[$i] > $p[$i+1]) {
                $sub = array($p[$i]=>$p[$i+1], $p[$i+1]=>$p[$i]);
                $p = strtr($p, $sub);
                $step_buf[$i] = '-';
                $i++;
                $chg = TRUE;
            }
        }
        if ($chg) {
            $step[] = '|'.implode('|', $step_buf).'|';
        } else {
            break;
        }
    }
    $res = implode(' ', str_split($p))."\n";
    $res .= implode("\n", array_reverse($step))."\n";
    $res .= implode(' ', str_split($org))."\n";
    return $res;
}
?>

　どう書く？orgに投稿。

　お題はあみだくじです。

次のような書式で与えられた「あみだくじ」があります。
(あみだくじはコード中に埋め込んでも、標準入力や外部ファイルから読み込んでも、書きやすい方法でかまいません)

A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |

このあみだくじをたどって

A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |
B D C A E

のように結果を表示させるプログラムを作ってください。

　以下、投稿したコード。選択した言語はPHP。ファイルパスを渡すと結果付きで返却する。

<?php
function Amida($file_path)
{
    if (!file_exists($file_path)) {
        return NULL;
    }
    $lines = file($file_path);
    $org = array_shift($lines);
    $p = $org;
    foreach ($lines as $line) {
        for ($i = 1; $i < strlen(trim($line)); $i+=2) {
            if ($line[$i] == '-') {
                $sub = array($p[$i+1]=>$p[$i-1], $p[$i-1]=>$p[$i+1]);
                $p = strtr($p, $sub);
            }
        }
    }
    return $org.implode('', $lines).$p;
}
?>

echo sprintf('<pre>%s</pre>', Amida('./amida.txt'));
このような形で使用する。

　strtr()、初めて使用した。
　if内の入れ替え処理、よくあるバッファを用いたものより、直感的にわかりやすくなっている（かも）。

　どう書く？orgに初めて投稿しました。
 
お題はポーカーの役判定です。

引数に手札を与えると、ポーカーの役を表示するプログラムを作ってください。

条件：

• スートはS,D,H,C、ランクはA,2～9,T,J,Q,Kのそれぞれ一文字で表します。
• 手札は S2D5H3CQS9 のように10文字で指定されます。特にソートはされていません。
• 手札にジョーカーは含まれません。
• ストレートで取りうるランクの種類はA2345, 23456 ... 9TJQK, TJQKAの10種類で、JQKA2のようにK-A-2をまたぐものはストレートではありません。

　以下、投稿したコード。選択した言語はPHP。自分でも気持ちの悪い箇所が幾つかあるが、勇気を出して投稿してみた。

<?php
function Poker($c)
{
    CSort($c);
    if (IsFlush($c)) {
        if (IsStraight($c)) {
            if ($c[1] == 'A') {
                return 'Royal flush';
            }
            return 'Straight flush';
        }
        return 'Flush';
    } else {
        if (IsStraight($c)) {
            return 'Straight';
        }
        $wk = array();
        $wk[$c[1]]++;
        $wk[$c[3]]++;
        $wk[$c[5]]++;
        $wk[$c[7]]++;
        $wk[$c[9]]++;
        arsort($wk);
        switch (array_shift($wk).array_shift($wk)) {
        case '41':    return 'Four of a kind';
        case '32':    return 'Full house';
        case '31':    return 'Three of a kind';
        case '22';    return 'Two pair';
        case '21';    return 'One pair';
        }
    }
    return 'No pair';
}

function IsFlush($c)
{
    if ($c[0] == $c[2] && $c[0] == $c[4] && $c[0] == $c[6] && $c[0] == $c[8]) {
        return TRUE;
    }
    return FALSE;
}

function IsStraight($c)
{
    $rank = 'A23456789TJQK';
    $num = $c[1].$c[3].$c[5].$c[7].$c[9];
    if (strpos($rank, $num) !== FALSE || $num == 'ATJQK') {
        return TRUE;
    }
    return FALSE;
}

function CSort(&$c)
{
    $rep = array('1'=>'A', '10'=>'T', '11'=>'J', '12'=>'Q', '13'=>'K');
    $wk = array($c[0].$c[1] => $c[1], $c[2].$c[3] => $c[3],
                $c[4].$c[5] => $c[5], $c[6].$c[7] => $c[7],
                $c[8].$c[9] => $c[9]);
    $wk = str_ireplace($rep, array_flip($rep), $wk);
    asort($wk);
    $c = '';
    foreach ($wk as $key => $value) {
        $c .= $key;
    }
}
?>