Nagoya.php vol.7 「分岐と行き止まり」

Nagoya.php_vol.7_分岐と行き止まり.md

What's this?

Nagoya.php vol.7 で行ったハンズオンの解答例です。

「オフラインリアルタイムどう書く」 の過去問から 分岐と行き止まり を取り上げて実践しました。

手続き型サンプルコード.php

<?php
$map = [
    '1' => ['a', 'g'],
    '2' => ['d', 'h'],
    '3' => ['b', 'f'],
    'a' => ['b'],
    'b' => ['c', '5'],
    'c' => ['4', '6'],
    'd' => ['c', 'e'],
    'e' => ['5'],
    'f' => ['g'],
    'g' => ['c', 'e', 'h'],
    'h' => ['4', 'i'],
    'i' => ['6'],
    '4' => [],
    '5' => [],
    '6' => [],
];

// 入力.
$stdin = trim(fgets(STDIN));
$blockers = str_split($stdin);

// 判定.
$output = [];
foreach (['1', '2', '3'] as $origin) {
    foreach (trace($origin, $blockers) as $arrivable) {
        $output[] = $origin . $arrivable;
    }
}

// 出力.
if (count($output) === 0) {
    echo '-' . PHP_EOL;
} else {
    sort($output);
    echo implode(',', $output) . PHP_EOL;
}

// 今いる場所から到達可能な終点を配列で返す.
function trace($point, $blockers)
{
    global $map;
    $nexts = $map[$point];

    // 次点がなければ終点.
    if (count($nexts) === 0) {
        return [$point];
    }

    $arrivables = [];
    foreach ($nexts as $next) {
        // 次点が通行禁止地点でなければ、次点について再帰処理.
        if (!in_array($next, $blockers)) {
            $arrivables = array_merge($arrivables, trace($next, $blockers));
        }
    }
    return array_unique($arrivables);
}

手続き型サンプルコード_自動テスト版.php

<?php
$map = [
    '1' => ['a', 'g'],
    '2' => ['d', 'h'],
    '3' => ['b', 'f'],
    'a' => ['b'],
    'b' => ['c', '5'],
    'c' => ['4', '6'],
    'd' => ['c', 'e'],
    'e' => ['5'],
    'f' => ['g'],
    'g' => ['c', 'e', 'h'],
    'h' => ['4', 'i'],
    'i' => ['6'],
    '4' => [],
    '5' => [],
    '6' => [],
];

// テストデータ.
$samples = [
    ['befi', '14,16,24,26'],
    ['abc', '14,15,16,24,25,26,34,35,36'],
    ['de', '14,15,16,24,26,34,35,36'],
    ['fghi', '14,15,16,24,25,26,34,35,36'],
    ['abcdefghi', '-'],
    ['ag', '24,25,26,34,35,36'],
    ['dh', '14,15,16,34,35,36'],
    ['bf', '14,15,16,24,25,26'],
    ['ch', '15,25,35'],
    ['be', '14,16,24,26,34,36'],
    ['ci', '14,15,24,25,34,35'],
    ['cgi', '15,24,25,35'],
    ['acgi', '24,25,35'],
    ['cdefghi', '15,35'],
    ['acdefghi', '35'],
    ['cdegi', '15,24,35'],
    ['bcdegi', '24'],
    ['afh', '14,15,16,24,25,26,34,35,36'],
    ['abfh', '14,15,16,24,25,26'],
    ['dfh', '14,15,16,34,35,36'],
    ['cdfh', '15,35'],
    ['deh', '14,15,16,34,35,36'],
    ['cdeh', '15,35'],
    ['abefgh', '24,26'],
    ['abdefgh', '-'],
    ['acfghi', '25,35'],
    ['acdfghi', '35'],
    ['cegi', '15,24,35'],
    ['abcfhi', '15,25'],
    ['abcefhi', '-'],
    ['abdi', '14,15,16,24,34,35,36'],
    ['abdfi', '14,15,16,24'],
    ['bdi', '14,15,16,24,34,35,36'],
    ['bdfi', '14,15,16,24'],
    ['adfh', '14,15,16,34,35,36'],
    ['adfgh', '34,35,36'],
    ['acdfhi', '15,35'],
    ['bcdfgi', '24'],
    ['bcdfghi', '-'],
    ['defi', '14,15,16,24,34,35,36'],
    ['defhi', '14,15,16,34,35,36'],
    ['cdefg', '15,24,26,35'],
    ['cdefgi', '15,24,35'],
    ['bdefg', '24,26'],
    ['bdefgi', '24'],
];

// テストデータの実行結果をチェック.
foreach ($samples as $sample) {

    // 入力.
    $blockers = str_split($sample[0]);

    // 判定.
    $output = [];
    foreach (['1', '2', '3'] as $origin) {
        foreach (trace($origin, $blockers) as $arrivable) {
            $output[] = $origin . $arrivable;
        }
    }

    // 出力.
    if (count($output) === 0) {
        $outputed = '-';
    } else {
        sort($output);
        $outputed = implode(',', $output);
    }

    // 実行結果表示.
    echo sprintf('%10s : ', $sample[0]) . ($sample[1] === $outputed ? '[OK]' : '[NG] ' . $outputed) . PHP_EOL;
}

// 今いる場所から到達可能な終点を配列で返す.
function trace($point, $blockers)
{
    global $map;
    $nexts = $map[$point];

    // 次点がなければ終点.
    if (count($nexts) === 0) {
        return [$point];
    }

    $arrivables = [];
    foreach ($nexts as $next) {
        // 次点が通行禁止地点でなければ、次点について再帰処理.
        if (!in_array($next, $blockers)) {
            $arrivables = array_merge($arrivables, trace($next, $blockers));
        }
    }
    return array_unique($arrivables);
}