codeiq

gistfile1.php

<?php

class Node
{
    public $linked = array();
    public $name;

    public function __construct($name)
    {
        $this->name = $name;
    }

    public function link_to(Node $node, $also = true)
    {
        if (!$this->linked($node)) $this->linked[] = $node;
        if ($also) $node->link_to($this, false);
    }

    public function linked(Node $node)
    {
        foreach ($this->linked as $l) { if ($l->name === $node->name) return true; }
        return false;
    }

    public function not_visit_yet(Array $visited_names)
    {
        $ret = array();
        foreach ($this->linked as $l) { if (!in_array($l->name, $visited_names)) $ret[] = $l; }
        return $ret;
    }
}

class Graph
{
    public $nodes = array();
    public $favorites;
    public function __construct(Favorites $favorites)
    {
        $this->favorites = $favorites;
        $this->build();
    }

    private function setNodeIfNotExists($nodeName)
    {
        if (!isset($this->nodes[$nodeName])) $this->nodes[$nodeName] = new Node($nodeName);
    }

    public function build()
    {
        foreach ($this->favorites->orders as $o) {
            list($s, $t) = preg_split('//', $o, null, PREG_SPLIT_NO_EMPTY);
            $this->setNodeIfNotExists($s);
            $this->setNodeIfNotExists($t);

            $this->nodes[$s]->link_to($this->nodes[$t]);
        }
    }

    public function get_orders(Node $node, $path = '', $visited = array())
    {
        $visited[] = $node->name;
        $not_visit_yet = $node->not_visit_yet($visited);
        if (empty($not_visit_yet)) {
            return array("{$path}{$node->name}");
        }

        $ret = array();
        foreach ($not_visit_yet as $n) {
            $ret = array_merge($ret, $this->get_orders($n, $path . $node->name, $visited));
        }
        return $ret;
    }
}

class Favorites
{
    public $orders = array();
    public function set($filename)
    {
        try {
            $file = new SplFileObject($filename);
            foreach ($file as $line) {
                if ($line === '') continue;
                if (!in_array($line, $this->orders)) $this->orders[] = trim($line);
            }
        } catch (RuntimeException $e) {
            die($e->getMessage());
        }
    }

    public function compromise($order)
    {
        $ret = array();
        for ($i = 0; $i < strlen($order) - 1; $i++) {
            $target = substr($order, $i, 2);
            foreach ($this->orders as $o) {
                if (strrev($o) === $target) {
                    $ret[] = $o;
                    break;
                }
            }
        }
        return $ret;
    }
}

$favorites = new Favorites();
$favorites->set(__DIR__ . '/hiroki.txt');
$favorites->set(__DIR__ . '/yayoi.txt');

$graph = new Graph($favorites);
$orders = $graph->get_orders($graph->nodes['R']);

$best_order = '';
$best_compromise = array();
foreach ($orders as $o) {
    $compromise = $favorites->compromise($o);
    if (count($compromise) < count($best_compromise) || $best_order === '') {
        $best_order = $o;
        $best_compromise = $compromise;
    }
}

var_dump($best_order, $best_compromise);