Code Quest

前にも書いたCode Quest、今回は連鎖ノ試練を解いていきます。

geek-out.jp

連鎖の試練

与えられた単語の中からしりとりをできるだけ長く繋ぐようにします。

f:id:yoshiki_utakata:20171211105931p:plain

しりとりはグラフで解ける

しりとりは、ノードが文字、エッジが単語のグラフで書けます。

f:id:yoshiki_utakata:20171211111526p:plain

これでノードを辿っていった時に最長のものを求められれば良いです。

連鎖ノ試練であればもっと簡単で、最長でなくとも20文字以上のが一つでも見つかればOKです。

実際に解いたコードはこういう感じです。

https://github.com/yoshikyoto/php-algorithm/blob/master/test/Graph/ShiritoriTest.php

ノードとエッジの実装

適当にノードとエッジを実装します。PHPで実装しました。

ノード

入ってくるエッジのリスト、出て行くエッジのリスト、idを持っています。

class Node {
    private $id;
    /** @var Edge[] */
    private $outgoing = [];
    /** @var Edge[] */
    private $incoming = [];
    public function __construct($id) {
        $this->id = $id;
    }
    public function addOutgoing(Edge $outgoing) {
        $this->outgoing[] = $outgoing;
    }
    public function addIncoming(Edge $incoming) {
        $this->incoming = $incoming;
    }
    public function getIncoming() {
        return $this->incoming;
    }
    public function getOutgoing() {
        return $this->outgoing;
    }
    public function __toString() {
        return strval($this->id);
    }
}

エッジ

fromとtoを持っています。

class Edge {
    /** @var Node */
    protected $from;
    /** @var Node */
    protected $to;
    public function __construct(Node $from, Node $to) {
        $this->from = $from;
        $this->to = $to;
    }
    public function setFrom(Node $node) {
        $this->node = $node;
    }
    public function getTo() {
        return $this->to;
    }
    public function setTo(Node $to) {
        $this->to = $to;
    }
}

Word

Edgeを継承しています。単語を突っ込むと最初の文字と最後の文字を保持します。同じ単語は二度使えないため、「使った単語かどうか」のフラグも持っています。

class Word extends Edge {
    private $str;
    private $first;
    private $last;
    private $isUsed;
    public function __construct($str) {
        $this->str = $str;
        $this->first = mb_substr($str, 0, 1);
        $this->last = mb_substr($str, mb_strlen($str) - 1, 1);
    }
    public function __toString() {
        return $this->str;
    }
    public function getFirst() {
        return $this->first;
    }
    public function getLast() {
        return $this->last;
    }
    public function isUsed() {
        return $this->isUsed;
    }
    public function used() {
        return $this->isUsed = true;
    }
    public function unused() {
        return $this->isUsed = false;
    }
}

探索

こういう感じでグラフに単語を追加していって、ShiritoriGraph::start() を呼びます。

       $words = [
            "イアラ","ウェイト","オメガロ","ガルヒ","ガングリオンズ","クリオ",
            "ジェノバ","スノウガ","ズビズバ","スペシウム","タグアズ","ドドンパ",
            "トルネ","ネメシス","バイナリル","ハザード","パリピファイア","バルース",
            "ヒラケゴマ","フェイク","プリズマ","ホルーガ","マッハ","マホマホ","ムート",
            "ラリホフ","ランス","ループ","ロールウェイブ","ワロス"
        ];
        $shiritoriGraph = new ShiritoriGraph();
        foreach ($words as $word) {
            $shiritoriGraph->addWord($word);
        }
        $shiritoriGraph->start()

中身は雑に、「各ノードをまず選択し、そのノードからたどれる最長のパスを深さ優先探索で探す」というアルゴリズムになってます。規模がそんなに大きくないので、これでも解けます。

    public function start() {
        $longest = [];
        foreach($this->getNodes() as $start) {
            echo $start . PHP_EOL;
            $words = $this->dfs($start);
            if(count($words) > count($longest)) {
                $longest = $words;
            }
        }
        return $longest;
    }

    public function dfs($node = null, $history = []) {
        $longest = [];
        $candidates = $this->getCandidateWords($node);
        foreach($candidates as $word) {
            $word->used();
            $history[] = $word;
            if(count($history) > 39) {
                echo $this->joinWords($history) . "\t" . count($history) . PHP_EOL;
            }
            $words = array_merge([$word], $this->dfs($word->getTo(), $history));
            $word->unused();
            array_pop($history);
            if(count($words) > count($longest)) {
                $longest = $words;
            }
        }
        return $longest;
    }

    public function getCandidateWords(Node $node) {
        return array_values(array_filter($node->getOutgoing(), function($word) {
            return !$word->isUsed();
        }));
    }