ちょっと前GDD 2010のdev quiz用に書いたGoのコードを公開してみる。当日は出張で出席できないことがわかってたので、実際に申し込んではいないからあってるかどうかは定かでない。とりあえずLevel 2まではそれっぽい答が出てるのは確認した。Level 3は時間がかかりすぎるパスを先に切らないと常識的な時間で終わらなかったはず。
ちなみに、元々はPythonで書いたのをGoに書き直したコードだったりする。実行時間的には4分かかってた処理が20秒くらいに縮まった。
コード
package main
import (
"flag"
"os"
"log"
"bufio"
"fmt"
"strings"
"container/vector"
)
var logTag string = ""
var logger *log.Logger = log.New(os.Stdout, logTag, 0)
func ExtractFirstAndLastLetter(word string) string {
first := word[0]
last := word[len(word)-1]
return fmt.Sprintf("%c%c", first, last)
}
var CHAR_LIST string = "abcdefghijklmnopqrstuvwxyz"
type StringList struct {
list vector.StringVector
}
func (l *StringList) add(s string) {
l.list.Push(s)
}
func (l *StringList) copy() StringList {
copied := l.list.Copy()
return StringList { copied }
}
func (l *StringList) delete(index int) {
l.list.Delete(index)
}
func (l *StringList) size() int {
return l.list.Len()
}
func (l *StringList) join(sep string) string {
return strings.Join(l.list, sep)
}
type WordDictionary map[byte] StringList
func (d WordDictionary) copy() WordDictionary {
newDict := make(WordDictionary)
for key,val := range d {
newDict[key] = val.copy()
}
return newDict
}
const (
WIN = 0
LOSE = 1
)
func DoShiritoriToEnd(dict WordDictionary, word string, wordPath StringList, depth int) {
depth += 1
endIndex := len(word)-1
lastChar := word[endIndex]
wordList := dict[lastChar]
if wordList.size() == 0 {
joined := wordPath.join("-")
winLose := depth % 2
if winLose == WIN {
logger.Print(" WIN:"+joined)
} else {
logger.Print("LOSE:"+joined)
}
}
for i, nextWord := range wordList.list {
copiedDict := dict.copy()
copiedList := copiedDict[lastChar]
copiedPath := wordPath.copy()
copiedPath.add(nextWord)
copiedList.delete(i)
copiedDict[lastChar] = copiedList
DoShiritoriToEnd(copiedDict, nextWord, copiedPath, depth)
}
}
func main() {
inFilePath := flag.String("in","","input data file")
flag.Parse()
if *inFilePath == "" {
logger.Print("Input file not spepcified")
return
}
// open input and output files
logger.Printf("Input file: %s\n", *inFilePath)
inFile,err := os.Open(*inFilePath, os.O_RDONLY, 0)
if err != nil {
logger.Print(err)
return
}
defer func() {
inFile.Close()
}()
// get the first word
reader := bufio.NewReader(inFile)
line, err := reader.ReadString('\n')
if err != nil {
logger.Print(err)
return
}
firstWord := ExtractFirstAndLastLetter(line[0:len(line)-1])
startDict := make(WordDictionary, len(CHAR_LIST))
for {
line, err = reader.ReadString('\n')
if err != nil {
//logger.Print("Error while reading file")
break
}
if len(line) == 1 {
continue
}
word := line[0:len(line)-1]
word = ExtractFirstAndLastLetter(word)
//logger.Print(word)
firstLetter := word[0]
list := startDict[firstLetter]
list.add(word)
startDict[firstLetter] = list
}
//logger.Print(startDict)
var list StringList
DoShiritoriToEnd(startDict, firstWord, list, 0)
}
入力（level1.txt）
xrdjgorj jctbqs jkrshfcilv jorsezhajk jmuholsxrc sfdpdioerpv silpaavk vtvauxgju vogmqa vnofdnnc vdruy uemxza udbjf uvtpf aszhnuvn awmhkgyd alhjlmioar ngzmjyd nznxgp dvvcghudkww dwivxpujzdo deqwbye wotaaadgpo wgaiqosarg wyeflkkwxg wzltrkb oqyjlgapkih oeqgb hwfnhx kcofl lubhgkf fywggvxnixm mxmlqukzcp pfliwzwot pzgilzqvwr teytvanbrsw tonhvlvg gnsxomhwdz zsxyei ihcsq ckxuhuty ydlwmlwskf rkaqnmnb btjryytmvye ezdfvkx xmzxpvq
実行結果
$ ./shiritori -in=level1.txt Input file: level1.txt WIN:js-sv-vu-ua-an-nd-dw-wo-oh-hx-xq LOSE:js-sv-vu-ua-an-nd-dw-wo-ob-be-ex-xq WIN:js-sv-vu-ua-an-nd-dw-wg-gz-zi-iq WIN:js-sv-vu-ua-an-nd-dw-wg-gz-zi-iq WIN:js-sv-vu-ua-an-nd-dw-wb-be-ex-xq LOSE:js-sv-vu-ua-an-nd-do-oh-hx-xq （後略）
