Nagoya.php #11 プログラミング問題回答例

01.nagoyaphp11.php

<?php
// 家系図全体の定義.
// 配列の最初の要素は親、それ以降の要素は子を表す.
$tree = [
    1  => [null, 2, 3, 4],
    2  => [1, 5, 6, 7],
    3  => [1, 8, 9, 10],
    4  => [1, 11, 12, 13],
    5  => [2, 14, 15, 16],
    6  => [2, 17, 18, 19],
    7  => [2, 20, 21, 22],
    8  => [3, 23, 24, 25],
    9  => [3, 26, 27, 28],
    10 => [3, 29, 30, 31],
    11 => [4, 32, 33, 34],
    12 => [4, 35, 36, 37],
    13 => [4, 38, 39, 40],
    14 => [5],
    15 => [5],
    16 => [5],
    17 => [6],
    18 => [6],
    19 => [6],
    20 => [7],
    21 => [7],
    22 => [7],
    23 => [8],
    24 => [8],
    25 => [8],
    26 => [9],
    27 => [9],
    28 => [9],
    29 => [10],
    30 => [10],
    31 => [10],
    32 => [11],
    33 => [11],
    34 => [11],
    35 => [12],
    36 => [12],
    37 => [12],
    38 => [13],
    39 => [13],
    40 => [13],
];

$input = '5->2';

// 入力の解釈.
list($me, $you) = explode('->', $input);
$me = intval($me);
$you = intval($you);

// 自分と相手それぞれの先祖（自身を含む）を列挙.
$ancestorsOf = [];
foreach ([$me, $you] as $who) {
    $current = $who;
    $ancestorsOf[$who][] = $who;
    while (($parent = $tree[$current][0]) !== null) {
        $ancestorsOf[$who][] = $current = $parent;
    }
}

// Most Recent Common Ancestor: 最も近い共通祖先.
$MRCA = array_values(array_intersect($ancestorsOf[$me], $ancestorsOf[$you]))[0];

// 自分と相手それぞれから見たMRCAの親等を算出.
$degreeFrom = [];
foreach ([$me, $you] as $who) {
    $degreeFrom[$who] = array_search($MRCA, $ancestorsOf[$who]);
}

// 自分から見たMRCAの親等と、相手から見たMRCAの親等によって、自分と相手の関係が決まる.
switch (true) {
    case $degreeFrom[$me] === 0 && $degreeFrom[$you] === 0:
        $kinship = 'me';
        break;
    case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 0:
        $kinship = 'mo';
        break;
    case $degreeFrom[$me] === 0 && $degreeFrom[$you] === 1:
        $kinship = 'da';
        break;
    case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 1:
        $kinship = 'si';
        break;
    case $degreeFrom[$me] === 2 && $degreeFrom[$you] === 1:
        $kinship = 'au';
        break;
    case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 2:
        $kinship = 'ni';
        break;
    case $degreeFrom[$me] === 2 && $degreeFrom[$you] === 2:
        $kinship = 'co';
        break;
    default:
        $kinship = '-';
        break;
}
echo $kinship . PHP_EOL;

02.nagoyaphp-wtih-tests.php

<?php
// 家系図全体の定義.
// 配列の最初の要素は親、それ以降の要素は子を表す.
$tree = [
    1  => [null, 2, 3, 4],
    2  => [1, 5, 6, 7],
    3  => [1, 8, 9, 10],
    4  => [1, 11, 12, 13],
    5  => [2, 14, 15, 16],
    6  => [2, 17, 18, 19],
    7  => [2, 20, 21, 22],
    8  => [3, 23, 24, 25],
    9  => [3, 26, 27, 28],
    10 => [3, 29, 30, 31],
    11 => [4, 32, 33, 34],
    12 => [4, 35, 36, 37],
    13 => [4, 38, 39, 40],
    14 => [5],
    15 => [5],
    16 => [5],
    17 => [6],
    18 => [6],
    19 => [6],
    20 => [7],
    21 => [7],
    22 => [7],
    23 => [8],
    24 => [8],
    25 => [8],
    26 => [9],
    27 => [9],
    28 => [9],
    29 => [10],
    30 => [10],
    31 => [10],
    32 => [11],
    33 => [11],
    34 => [11],
    35 => [12],
    36 => [12],
    37 => [12],
    38 => [13],
    39 => [13],
    40 => [13],
];

$tests = [
    '5->2'   => 'mo',
    '28->10' => 'au',
    '1->1'   => 'me',
    '40->40' => 'me',
    '27->27' => 'me',
    '7->2'   => 'mo',
    '40->13' => 'mo',
    '9->3'   => 'mo',
    '4->1'   => 'mo',
    '1->3'   => 'da',
    '12->35' => 'da',
    '3->8'   => 'da',
    '6->19'  => 'da',
    '38->40' => 'si',
    '9->8'   => 'si',
    '4->2'   => 'si',
    '15->16' => 'si',
    '40->12' => 'au',
    '10->4'  => 'au',
    '21->5'  => 'au',
    '8->2'   => 'au',
    '3->5'   => 'ni',
    '11->39' => 'ni',
    '2->13'  => 'ni',
    '13->32' => 'ni',
    '14->22' => 'co',
    '40->34' => 'co',
    '5->8'   => 'co',
    '12->10' => 'co',
    '1->27'  => '-',
    '8->1'   => '-',
    '12->22' => '-',
    '2->40'  => '-',
    '32->31' => '-',
    '13->14' => '-',
];

foreach ($tests as $input => $expected) {
    echo $input . "\t" . (solve($input, $expected) ? 'OK' : '_NG_') . PHP_EOL;
}

function solve($input, $expected) {
    global $tree;
    
    // 入力の解釈.
    list($me, $you) = explode('->', $input);
    $me = intval($me);
    $you = intval($you);
    
    // 自分と相手それぞれの先祖（自身を含む）を列挙.
    $ancestorsOf = [];
    foreach ([$me, $you] as $who) {
        $current = $who;
        $ancestorsOf[$who][] = $who;
        while (($parent = $tree[$current][0]) !== null) {
            $ancestorsOf[$who][] = $current = $parent;
        }
    }
    
    // Most Recent Common Ancestor: 最も近い共通祖先.
    $MRCA = array_values(array_intersect($ancestorsOf[$me], $ancestorsOf[$you]))[0];
    
    // 自分と相手それぞれから見たMRCAの親等を算出.
    $degreeFrom = [];
    foreach ([$me, $you] as $who) {
        $degreeFrom[$who] = array_search($MRCA, $ancestorsOf[$who]);
    }
    
    // 自分から見たMRCAの親等と、相手から見たMRCAの親等によって、自分と相手の関係が決まる.
    switch (true) {
        case $degreeFrom[$me] === 0 && $degreeFrom[$you] === 0:
            $kinship = 'me';
            break;
        case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 0:
            $kinship = 'mo';
            break;
        case $degreeFrom[$me] === 0 && $degreeFrom[$you] === 1:
            $kinship = 'da';
            break;
        case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 1:
            $kinship = 'si';
            break;
        case $degreeFrom[$me] === 2 && $degreeFrom[$you] === 1:
            $kinship = 'au';
            break;
        case $degreeFrom[$me] === 1 && $degreeFrom[$you] === 2:
            $kinship = 'ni';
            break;
        case $degreeFrom[$me] === 2 && $degreeFrom[$you] === 2:
            $kinship = 'co';
            break;
        default:
            $kinship = '-';
            break;
    }
    
    return $kinship === $expected;
}