お題

子どもの宿題で「Frankenstein」に含まれる文字を使って別の英単語をできるだけたくさん見つけるというものが出されたので、プログラムで解いてみようと思った。
言語はGolang。最近は仕事でJavaばかり書いていて、だいぶ書き方を忘れている気がするので、リハビリの意味も込めて。

開発環境

# OS

$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="17.10 (Artful Aardvark)"

# 言語

$ go version
go version go1.10 linux/amd64

# マシンスペック

CPUプロセッサー数：４

$ cat /proc/cpuinfo | grep physical
physical id : 0
address sizes   : 39 bits physical, 48 bits virtual
physical id : 0
address sizes   : 39 bits physical, 48 bits virtual
physical id : 0
address sizes   : 39 bits physical, 48 bits virtual
physical id : 0
address sizes   : 39 bits physical, 48 bits virtual

CPU１プロセッサーあたりのコア数：２

$ cat /proc/cpuinfo | grep cores
cpu cores   : 2
cpu cores   : 2
cpu cores   : 2
cpu cores   : 2

Memory

$ free -h
              total        used        free      shared  buff/cache   available
Mem:           7.7G        1.1G        5.7G        224M        876M        6.2G
Swap:          2.0G        997M        1.0G

実践

■組み合わせを洗い出す

■■まずお試しに、愚直に１字から５字くらいの範囲での組み合わせを洗い出す

ソースの全量は下記。
https://github.com/sky0621/compito/blob/3916e5b454bb7e485a1ecc0be8fd37e60c89716d/main.go

プログラム引数として英単語文字列を受け取りスライスへ。

    args := os.Args
    word := args[1]
    lowerWord := strings.ToLower(word)
    aryWords := strings.Split(lowerWord, "")

重複排除用にセットを定義しておく。

func newSet() *set {
    m := map[string]struct{}{}
    s := &set{}
    s.m = m
    return s
}

type set struct {
    m map[string]struct{}
}

func (s *set) list() []string {
    r := []string{}
    // ignore worning
    for k, _ := range s.m {
        r = append(r, k)
    }
    return r
}

func (s *set) add(v string) {
    s.m[v] = struct{}{}
}

英単語を１字ずつ処理し、重複のないセットに詰めていく。

    set := newSet()
    parentString := ""
    for i, w := range aryWords {
        set.add(fmt.Sprintf("%s%s", parentString, w))

        parentString2 := fmt.Sprintf("%s%s", parentString, w)
        for i2, w2 := range aryWords {
            if i2 == i {
                continue
            }
            set.add(fmt.Sprintf("%s%s", parentString2, w2))

　　　　　　　　　　　　　　　　　〜〜〜３字目から５字目まで繰り返す〜〜〜
        }
    }

この内容で例えば「ant」の組み合わせを表示してみる。

$ go run main.go ant
word:ant

a
an
ant
at
atn
n
na
nat
nt
nta
t
ta
tan
tn
tna

いわゆる順列で、１字から３字までのラインナップなので以下の足し算の計１５通り。
・３つの字から１つを選ぶのは、３通り
・３つの字から２つを選んで一列に並べる並べ方は、３✕２で６通り
・３つの字から３つを選んで一列に並べる並べ方は、３✕２✕１で６通り

３字くらいなら、目視でも合っていることが簡単に確認できる。

■■何文字の英単語でも大丈夫なように組み合わせ算出を高階関数化

ソースの全量は下記。
https://github.com/sky0621/compito/blob/fc7451e75cc5ebaa1245725d96e1d4eff4b61d82/main.go

さすがに１字から５字限定というわけにもいかないし、じゃあ１０字といってループの入れ子を増やすのも下手すぎる。
ので、ループの入れ子で表現していたところを下記のように高階関数にしてみる。

func combi(parentCharacter string, characters []string, resultSet *set, len int, skipIndex []int) {
    if len == 0 {
        return
    }

    thistimeSkipIndex := skipIndex
    for i, c := range characters {
        addTargetWord := fmt.Sprintf("%s%s", parentCharacter, c)
        thistimeSkipIndex = append(skipIndex, i)
        skipFlg := false
        for _, skip := range skipIndex {
            if i == skip {
                skipFlg = true
            }
        }
        if skipFlg {
            continue
        }
        resultSet.add(addTargetWord)

        combi(addTargetWord, characters, resultSet, len-1, thistimeSkipIndex)
    }
}

呼び出し部分は以下の通り。

    set := newSet()
    combi("", aryWords, set, len(aryWords), []int{})

呼び出し部分は簡素になったものの、 combi 関数、ひどく拙い気がする・・・。
すでに登場した字を単語の一部に加えないようスキップするくだりなど、やっつけ感がすごい。
が、下記の通り、ひとまず高階関数化前のロジックと「ant」から計算した組み合わせは一致した。
これで、何字の英単語でも組み合わせが表示できる。

$ go run main.go ant
word:ant
aryWords:[a n t]

a
an
ant
at
atn
n
na
nat
nt
nta
t
ta
tan
tn
tna
===========================
最初から単語の組み合わせ作成まで 0.000046秒
最初から最後の標準出力まで       0.000108秒
===========================

※ちなみに、処理時間の計測も加えてみた。

■■「Frankenstein」を試す。

「ant」の３字は一瞬で結果が出たが、字数が多いと当然処理時間にハネることが予想されたので、いきなり「Frankenstein」でなく「Franken」を試してみる。

$ go run main.go Franken
word:Franken
aryWords:[f r a n k e n]

a
ae
aef
aefk

〜省略〜

rnnkfa
rnnkfae
rnnkfe
rnnkfea
===========================
最初から単語の組み合わせ作成まで 0.063128秒
最初から最後の標準出力まで       0.084830秒
===========================

まだ、１秒かからず返ってくる。　が、３字の 0.001 秒に対し、６字は 0.08 秒と８０倍になっている。

次は、９字の「Frankenste」で試す。

$ go run main.go Frankenste
word:Franken
aryWords:[f r a n k e n s t e]

a
ae
aee
aeef
aeefi
aeefik

〜省略〜

tsrnnkifea
tsrnnkifeae
tsrnnkifee
tsrnnkifeea
===========================
最初から単語の組み合わせ作成まで 88.289876秒
最初から最後の標準出力まで       359.340624秒
===========================

これは、マズいね。
最後に「Frankenstein」をやってみたのだけど、メモリが足りずに失敗。

まとめ

この実装では（端末スペックにも依存するかもしれないけど）１２字は、こなせないことがわかった。
というわけで、組み合わせ算出のためのアルゴリズムをちゃんと考えよう。
続きは次回。

Golangでアナグラム（未完成）

お題