オフラインリアルタイムどう書く E06 の回答 (PHP)

オフラインリアルタイムどう書くE06 で実装したコードです。
問題はこちらです。
http://qiita.com/mtsmfm/items/7a0bfd2ac5b7674ce8c7

stable_arsort 関数の実装は下記を利用しました。
http://stackoverflow.com/questions/12676521/how-to-have-a-stable-sort-in-php-with-arsort

```php:main.php
<?php

function main($input)
{
    $data = parse($input);
    // echo json_encode($data), "\n";

    $n = count($data);
    $victory = array_fill(0, $n, 0);
    for ($i = 0; $i < $n; ++$i) {
        for ($j = $i + 1; $j < $n; ++$j) {
            $win = battle($data[$i], $data[$j]);
            if ($win === 1) {
                ++$victory[$i];
            } elseif ($win === -1) {
                ++$victory[$j];
            } else {
                // Nothing to do
            }
        }
    }

    $sorted = stable_arsort($victory);
    $result = array_map(function ($i) { return $i + 1; },
        array_keys($sorted));
    return implode(',', $result);
}

function parse($input)
{
    $result = [];

    $players = explode(',', $input);
    foreach ($players as $p) {
        $arr = str_split($p);
        $c = [];
        for ($i = 0; $i < count($arr); $i += 2) {
            $level = (int) $arr[$i];
            $type = $arr[$i + 1];
            if ($level < 1 || 9 < $level) {
                echo "Error: level = $level\n";
                exit;
            }
            if ($type != 'R' && $type != 'G' && $type != 'B') {
                echo "Error: type = $type\n";
                exit;
            }
            $c[] = [ 'level' => $level, 'type' => $type ];
        }
        $result[] = $c;
    }

    return $result;
}

// プレイヤー $d1 とプレイヤー $d2 で戦う
// $d1 が勝ったら 1, $d2 が勝ったら -1, 引き分けは 0 とする
function battle($d1, $d2)
{
    $n1 = count($d1);
    $n2 = count($d2);
    $i1 = 0;
    $i2 = 0;
    $h1 = $d1[$i1]['level'];
    $h2 = $d2[$i2]['level'];
    while ($i1 < $n1 && $i2 < $n2) {
        list ($win, $rest) = battle_one($d1[$i1], $h1, $d2[$i2], $h2);
        if ($win === 1) {
            ++$i2;
            $h1 = $rest;
            if ($i2 < $n2) {
                $h2 = $d2[$i2]['level'];
            }
        } elseif ($win === -1) {
            ++$i1;
            if ($i1 < $n1) {
                $h1 = $d1[$i1]['level'];
            }
            $h2 = $rest;
        } else {
            ++$i1;
            if ($i1 < $n1) {
                $h1 = $d1[$i1]['level'];
            }
            ++$i2;
            if ($i2 < $n2) {
                $h2 = $d2[$i2]['level'];
            }
        }
    }

    $result = ($i1 < $n1 ? 1 : 0) - ($i2 < $n2 ? 1 : 0);
    return $result;
}

// $m1 (残り $h1) と $m2 (残り $h2) で戦う
// $m1 が勝ったら 1, $d2 が勝ったら -1, 相打ちは 0 とする
function battle_one($m1, $h1, $m2, $h2)
{
    $l1 = $m1['level'];
    $l2 = $m2['level'];
    $t1 = $m1['type'];
    $t2 = $m2['type'];
    // echo "($t1,$h1) vs ($t2,$h2)";

    while ($h1 > 0 && $h2 > 0) {
        if ($l1 > $l2) {
            $h2 -= damage($t1, $t2);
            if ($h2 > 0) {
                $h1 -= damage($t2, $t1);
            }
        } elseif ($l1 < $l2) {
            $h1 -= damage($t2, $t1);
            if ($h1 > 0) {
                $h2 -= damage($t1, $t2);
            }
        } else {
            $h1 -= damage($t2, $t1);
            $h2 -= damage($t1, $t2);
        }
    }

    $win = ($h1 > 0 ? 1 : 0) - ($h2 > 0 ? 1 : 0);
    if ($h1 > 0) {
        $rest = $h1;
    } elseif ($h2 > 0) {
        $rest = $h2;
    } else {
        $rest = 0;
    }
    // echo "  $win, $rest\n";
    return [$win, $rest];
}

$damages = [
    'R' => ['R' => 2, 'G' => 4, 'B' => 1],
    'G' => ['R' => 1, 'G' => 2, 'B' => 4],
    'B' => ['R' => 4, 'G' => 1, 'B' => 2],
];
function damage($t1, $t2)
{
    global $damages;
    return $damages[$t1][$t2];
}

function stable_arsort($array)
{
    $temp = array();
    $i = 0;
    foreach ($array as $key => $value) {
        $temp[] = array($i, $key, $value);
        $i++;
    }

    uasort($temp, function($a, $b) {
        return $a[2] === $b[2] ? ($a[0] > $b[0]) : ($a[2] < $b[2] ? 1 : -1);
    });

    $array = array();
    foreach ($temp as $val) {
        $array[$val[1]] = $val[2];
    }

    return $array;
}
```

テストコードは以下です。

```php:test.php
<?php
require_once __DIR__ . '/main.php';

function test($input, $expected)
{
    $actual = main($input);
    if ($actual !== $expected) {
        echo "NG: $input, $expected, $actual\n";
    }
}

/*0*/ test("9B,3R2G,1R2B3G", "1,3,2");
/*1*/ test("1G", "1");
/*2*/ test("1G,1R,1B", "1,2,3");

// 以下省略
```