Goを使って全探索で最長しりとりを解く

この記事はtomowarkar ひとりAdvent Calendar 2019の2日目の記事です。

Golangを書き始めて1ヶ月が過ぎた頃なのでアルゴリズム的な問題を解いてみようということで、最長しりとりを解くアルゴリズムを書いてみました。

今回全探索を使って最長しりとりを解くので、パフォーマンス最適ではありません。
計算量は最大で$O(n!)$になると思われます(自信ない)。

実務でしりとりを解きたいという場合は(???)数理計画法などを使って解くことをお勧めします。

考え方

1. 単語プールの中からしりとりの開始文字を決め、開始文字をしりとりプールに移す
2. 残りの単語プールの中からしりとりが繋がる文字を探す。
3. しりとりが繋がる場合、単語プールからしりとりプールに移動し、2に戻る。
4. しりとりが繋がらない場合、そこでしりとりは終了する。
5. 終了したしりとりプールの中で一番長いしりとりプールが求める最長しりとり。

コード全文

コード全文をのせると長くなるので、折りたたんで載せておきます。

コード全文

main.go

package main

import (
	"fmt"
	"strings"
	"time"
)

// Word は単語の頭と尻の文字を格納します.
type Word struct {
	word string
	head string
	tail string
}

// Words は Wordの配列とその長さを格納します.
type Words struct {
	length int
	words  []Word
}

// Result は しりとりの結果を格納します.
var Result Words

// Append は Wordsに要素を追加します.
func (ws *Words) Append(w string) {
	ww := Word{
		word: w,
		head: string(w[0]),
		tail: string(w[len(w)-1]),
	}
	ws.words = append(ws.words, ww)
	ws.length++
}

// shiritori は メインの探索アルゴリズムです.
func shiritori(chain, words []Word) {
	tail := chain[len(chain)-1].tail
	flag := false
	for i, w := range words {
		if w.head == tail {
			flag = true
			tmp := append([]Word{}, words...)
			shiritori(append(chain, []Word{w}...), append(tmp[:i], tmp[i+1:]...))
		}
	}
	if !flag {
		if len(chain) > Result.length {
			Result.words = chain
			Result.length = len(chain)
		}
	}
}

// solver はしりとり結果を返します.
func solver(target []string) []string {
	var ans []string
	ws := Words{}

	for _, ta := range target {
		ws.Append(ta)
	}

	for i, w := range ws.words {
		tmp := append([]Word{}, ws.words...)
		shiritori([]Word{w}, append(tmp[:i], tmp[i+1:]...))
	}
	
	for _, r := range Result.words {
		ans = append(ans, r.word)
	}
	return ans
}

func main() {
	target := "hc, radish, ginger, egg, apple, tuna, nut, onion, tomato, carrot"
	targetArr := strings.Split(target, ", ")
	start := time.Now()

	ans := solver(targetArr)

	fmt.Printf("%d個: %f秒\n", len(targetArr), (time.Now().Sub(start)).Seconds())
	fmt.Println("in: ", strings.Join(targetArr, " "))
	fmt.Println("out:", strings.Join(ans, " "))
}

考慮しなかったこと

コード解説に入る前に今回考慮しなかったことをあげておきます。

同じ単語の場合

同じ単語を使うことを許容しています。許容しない場合はAppendにコードを追加すればできそうです。

終了文字

日本語でしりとりをする場合は「ん」がついたらそこで終了しますが、ローマ字の場合はどうなるのでしょうかね？

コード解説

solver

単語スライスtargetを渡すと、最長のしりとりスライスを返します。

1. 単語スライスtargetを単語プールWordsに格納。
2. 各単語毎に後に続くしりとりを探索。
3. 最長のしりとりプールResult.wordsをstringのsliceに変換して返す。

solver.go

// solver はしりとり結果を返します.
func solver(target []string) []string {
	var ans []string
	ws := Words{}

	for _, ta := range target {
		ws.Append(ta)
	}

	for i, w := range ws.words {
		tmp := append([]Word{}, ws.words...)
		shiritori([]Word{w}, append(tmp[:i], tmp[i+1:]...))
	}
	
	for _, r := range Result.words {
		ans = append(ans, r.word)
	}
	return ans
}

shiritori

1. しりとりプールchainの一番最後の文字を取得。
2. 単語プールwordsの中からしりとりができる単語を探す。
3. しりとりができる単語がある場合、その単語を単語プールwordsからしりとりプールchainに移動し、再帰的にしりとりを探索する。
4. しりとりができる単語があった場合その長さを評価し、最長しりとりResultを取得する。

shiritori.go

// shiritori は メインの探索アルゴリズムです.
func shiritori(chain, words []Word) {
    tail := chain[len(chain)-1].tail
    flag := false
    for i, w := range words {
        if w.head == tail {
            flag = true
            tmp := append([]Word{}, words...)
            shiritori(append(chain, []Word{w}...), append(tmp[:i], tmp[i+1:]...))
        }
    }
    if !flag {
        if len(chain) > Result.length {
            Result.words = chain
            Result.length = len(chain)
        }
    }
}

動作確認

それでは動作確認をしてみます。

$ go run main.go
10個: 0.000114秒
in:  hc radish ginger egg apple tuna nut onion tomato carrot
out: hc carrot tomato onion nut tuna apple egg ginger radish

パフォーマンス最適ではないと言いながら、なかなか早く結果が出てきました。
これはしりとりとして繋がりうる選択肢が限られているため、早めに枝切りされた結果ということが考察できます。

試しに"a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z"をぶち込んでみても

26個: 0.000081秒
in:  a b c d e f g h i j k l m n o p q r s t u v w x y z
out: a

早いですね。

次に逆のパターンをみてみます。
しりとりとして繋がりうる選択肢を最大化した場合なので、"a, a, a, a, a, a, a, a, a, a"で探索してみます。

10個: 2.340494秒
in:  a a a a a a a a a a
out: a a a a a a a a a a

一番最初の結果と比べてみても同じ単語数(10個)なのにも関わらず、探索時間が大きく変わることがわかりますね。
これは全ての単語の頭と尻が繋がりうるので、全て探索する必要があり時間がかかると考えられます。

ざっくりまとめ

文字列	しりとり長さ	探索時間
"hc, radish, ginger, egg, apple, tuna, nut, onion, tomato, carrot"	10個	0.000114秒
"a, a, a, a, a, a, a, a, a, a"	10個	2.340494秒
"a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z"	26個	0.000081秒
計算量を考えてアルゴリズムを組む大切さがよくわかりますね。

まとめ

• 全探索で最長しりとりを解いた。
• 探索する単語によって探索時間が大きく変わる。
• 計算量を考えてアルゴリズムを組む重要性がわかった。

以上明日も頑張ります！！
tomowarkar ひとりAdvent Calendar Advent Calendar 2019