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

お題

もともとは子どもの宿題で「Frankenstein」に含まれる文字を使って別の英単語をできるだけたくさん見つけるというものが出されたので、プログラムで解いてみようと思ったのがきっかけだった。
けど、前回までの時点で１２文字の処理にローカルマシンスペックが耐えられず、頓挫状態だった。
そうこうしている間に、またまた子どもの宿題で「『treesdeint』を並べ替えて意味のある単語を探す」というのがあったので、解決する課題をこちらにシフト。こっちの方が簡単だし。
（そういえば、そもそもこういう課題をアナグラムと呼ぶのか、わかっていない・・・）

GolangでアナグラムIndex

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

開発環境

# OS

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

# 言語

$ go version
go version go1.11.2 linux/amd64

バージョンの切り替えはgoenvで行っている。

# マシンスペック

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/tree/4968566d2a5e97ead8e8b5931aa4a0c95d58d4b0

■文字組み合わせの洗い出し

まずは結果から。

「cat」の組み合わせ

$ go run main.go cat
入力文字列：cat
入力文字列をスライス化してソート：[a c t]

<処理開始>

<処理結果>
act
atc
cat
cta
tac
tca

処理時間：0.000118秒

「test」の組み合わせ

$ go run main.go test
入力文字列：test
入力文字列をスライス化してソート：[e s t t]

<処理開始>

<処理結果>
estt
etst
etts
sett
stet
stte
test
tets
tset
tste
ttes
ttse

処理時間：0.000166秒

「cloud」の組み合わせ

$ go run main.go cloud
入力文字列：cloud
入力文字列をスライス化してソート：[c d l o u]

<処理開始>

<処理結果>
cdlou
cdluo
　〜省略〜
cuodl
cuold
dclou
dcluo
　〜省略〜
duocl
duolc
lcdou
lcduo
　〜省略〜
luocd
luodc
ocdlu
ocdul
　〜省略〜
oulcd
ouldc
ucdlo
ucdol
　〜省略〜
uolcd
uoldc

処理時間：0.000467秒

「treesdeint」の組み合わせ

お題にある文字群（１０文字）の場合

$ go run main.go treesdeint
入力文字列：treesdeint
入力文字列をスライス化してソート：[d e e e i n r s t t]

<処理開始>

<処理結果>
deeeinrstt
deeeinrtst
deeeinrtts
　〜省略〜
ttsrniedee
ttsrnieede
ttsrnieeed

処理時間：2.848463秒

「Frankenstein」の組み合わせ

一応、前回の宿題にあった課題「Frankenstein」も試してみる。

$ go run main.go Frankenstein
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x4d3170, 0x16)
    /home/koge/.goenv/versions/1.11.2/src/runtime/panic.go:608 +0x72
runtime.sysMap(0xc134000000, 0x10000000, 0x597c98)
    /home/koge/.goenv/versions/1.11.2/src/runtime/mem_linux.go:156 +0xc7
runtime.(*mheap).sysAlloc(0x57f620, 0x10000000, 0xc000049e48, 0xc000049e30)
    /home/koge/.goenv/versions/1.11.2/src/runtime/malloc.go:619 +0x1c7
runtime.(*mheap).grow(0x57f620, 0x62b5, 0x0)
    /home/koge/.goenv/versions/1.11.2/src/runtime/mheap.go:920 +0x42
runtime.(*mheap).allocSpanLocked(0x57f620, 0x62b5, 0x597ca8, 0x13300000134)
    /home/koge/.goenv/versions/1.11.2/src/runtime/mheap.go:848 +0x337
runtime.(*mheap).alloc_m(0x57f620, 0x62b5, 0x7f7556610100, 0x0)
    /home/koge/.goenv/versions/1.11.2/src/runtime/mheap.go:692 +0x119
runtime.(*mheap).alloc.func1()
    /home/koge/.goenv/versions/1.11.2/src/runtime/mheap.go:759 +0x4c
runtime.(*mheap).alloc(0x57f620, 0x62b5, 0xc000010100, 0x42ff45)
    /home/koge/.goenv/versions/1.11.2/src/runtime/mheap.go:758 +0x8a
runtime.largeAlloc(0xc56a000, 0xc000040001, 0x430117)
    /home/koge/.goenv/versions/1.11.2/src/runtime/malloc.go:1019 +0x97
runtime.mallocgc.func1()
    /home/koge/.goenv/versions/1.11.2/src/runtime/malloc.go:914 +0x46
runtime.systemstack(0x0)
    /home/koge/.goenv/versions/1.11.2/src/runtime/asm_amd64.s:351 +0x66
runtime.mstart()
    /home/koge/.goenv/versions/1.11.2/src/runtime/proc.go:1229

goroutine 1 [running]:
runtime.systemstack_switch()
    /home/koge/.goenv/versions/1.11.2/src/runtime/asm_amd64.s:311 fp=0xc02d0e2c68 sp=0xc02d0e2c60 pc=0x44f940
runtime.mallocgc(0xc56a000, 0x4adea0, 0xffffffffffffff01, 0x501dad)
    /home/koge/.goenv/versions/1.11.2/src/runtime/malloc.go:913 +0x896 fp=0xc02d0e2d08 sp=0xc02d0e2c68 pc=0x40b306
runtime.growslice(0x4adea0, 0xc109ca4000, 0x9dee00, 0x9dee00, 0x9dee01, 0xc109ca4000, 0x7e5800, 0x9dee00)
    /home/koge/.goenv/versions/1.11.2/src/runtime/slice.go:204 +0x145 fp=0xc02d0e2d70 sp=0xc02d0e2d08 pc=0x43bd15
github.com/sky0621/compito/util.(*Set).List(0xc00004a2b0, 0x0, 0x0, 0x0)
    /work/src/gomodule/github.com/sky0621/compito/util/util.go:53 +0x19d fp=0xc02d0e2e58 sp=0xc02d0e2d70 pc=0x49bf2d
main.main()
    /work/src/gomodule/github.com/sky0621/compito/main.go:53 +0x2f4 fp=0xc02d0e2f98 sp=0xc02d0e2e58 pc=0x49c464
runtime.main()
    /home/koge/.goenv/versions/1.11.2/src/runtime/proc.go:201 +0x207 fp=0xc02d0e2fe0 sp=0xc02d0e2f98 pc=0x429827
runtime.goexit()
    /home/koge/.goenv/versions/1.11.2/src/runtime/asm_amd64.s:1333 +0x1 fp=0xc02d0e2fe8 sp=0xc02d0e2fe0 pc=0x4518a1
exit status 2

あいかわらず、今のマシンスペックと実装したロジックでは１２文字は捌けない・・・。

■実装方法

簡易説明

１．コンソールで受け取った文字列をスライスにしてソート（ついでに全て小文字に変換）
２．スライスをループし、１字ごとに残りの文字列をスライスにしてループ、・・・残りの文字列がなくなるまでループ。
　（ループを重ねていくたびに文字を結合していき、残りの文字列がない状態になった時点で、完成した結合文字列を”セット”に追加）
　※”セット”は要素の重複がない集合
３．”セット”の中身を標準出力

個別ソース説明

コンソールで受け取った文字列を処理可能な状態にするところまで

これで、文字列「treesdeint」を渡すとスライス「[d e e e i n r s t t]」になる。

[main.go]

func main() {
    args := os.Args
    word := args[1]
    lowerWord := strings.ToLower(word)
    inputCharacters := strings.Split(lowerWord, "")
    sort.Strings(inputCharacters)
    fmt.Printf("入力文字列をスライス化してソート：%s\n\n", inputCharacters)

    〜〜省略〜〜
}

"セット"の定義と初期化

”セット”の初期化

[main.go]

func main() {
    〜〜省略〜〜

    gSet = util.NewSet()

    〜〜省略〜〜
}

”セット”の定義

[util/set.go]

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

type Set struct {
    m   map[string]struct{}
    mux sync.Mutex
}

func (s *Set) List() []string {
    s.mux.Lock()
    defer s.mux.Unlock()
    r := []string{}
    for k := range s.m {
        r = append(r, k)
    }
    return r
}

func (s *Set) Add(v string) {
    s.mux.Lock()
    defer s.mux.Unlock()
    s.m[v] = struct{}{}
}

コンソールで受け取った文字列を並べ替えて、全ての組み合わせを"セット"に詰める

★ここは、初見で理解しづらいので、後ほど解説。

コンソールで受け取った文字列をスライス化したもの（inputCharacters）を渡して処理開始

[main.go]

func main() {
    〜〜省略〜〜

    makeWord(inputCharacters, "")

    〜〜省略〜〜
}

再帰関数。
受け取った文字列スライス（addCharacters）を１文字ずつ処理。
１文字ずつ行う処理は下記。
【１】文字列スライスを”現在処理している文字”と”それ以外の文字群”に分割
【２】結果文字列（resultString）に”現在処理している文字”を追加
【３】”それ以外の文字群”と【２】で追加済みの結果文字列を渡して、再度 makeWord 関数を再帰呼び出し
【４】結果文字列が完成（つまり、”それ以外の文字群”が空になった）したら、その文字列を”セット”に格納

う〜ん、わかりづらい・・・。

[main.go]

func makeWord(addCharacters []string, resultString string) {
    if len(addCharacters) == 0 {
        gSet.Add(resultString)
        return
    }
    for loopIdx, addCharacter := range addCharacters {
        targetCharacter, remains := util.Separate(addCharacters, loopIdx)
        makeWord(remains, resultString+targetCharacter)
    }
}

文字列スライスを”現在処理している文字”と”それ以外の文字群”に分割する関数

[separate.go]

func Separate(chars []string, idx int) (string, []string) {
    if idx < 0 {
        return "", []string{}
    }
    if chars == nil {
        return "", []string{}
    }
    if len(chars) == 0 {
        return "", []string{}
    }
    if len(chars) <= idx {
        return "", []string{}
    }
    var target string
    var remaining []string
    for i, c := range chars {
        if i == idx {
            target = c
        } else {
            remaining = append(remaining, c)
        }
    }
    return target, remaining
}

全ての組み合わせを詰め終わった"セット"の中身を標準出力

[main.go]

func main() {
    〜〜省略〜〜

    l := gSet.List()
    sort.Strings(l)

    for _, s := range l {
        fmt.Println(s)
    }
}

★並べ替えロジック解説★

例えば、「cat」を入力値とした場合、

    makeWord([]string{"a", "c", "t"}, "")

のような呼び出しになる。　呼び出された関数側は、

[makeWord関数の定義に実際の引数を当て込んだ場合の疑似コード]

func makeWord([]string{"a", "c", "t"}, "") {
    〜省略〜
    for loopIdx, addCharacter := range []string{"a", "c", "t"} {
        "a", []string{"c", "t"} := util.Separate([]string{"a", "c", "t"}, loopIdx)
        makeWord([]string{"c", "t"}, "" + "a")
    }
}

となり、ループ処理される "a", "c", "t" それぞれの中で、例えば "a" の場合はもともとのスライス（[]string{"a", "c", "t"}）を "a" と []string{"c", "t"} に分けられ、再帰呼出しされる makeWord 関数の引数になる。

[makeWord関数の定義に実際の引数を当て込んだ場合の疑似コード]

func makeWord([]string{"c", "t"}, "a") {
    〜省略〜
    for loopIdx, addCharacter := range []string{"c", "t"} {
        "c", []string{"t"} := util.Separate([]string{"c", "t"}, loopIdx)
        makeWord([]string{"t"}, "a" + "c")
    }
}

↑で再帰呼び出しされる makeWord 関数は、こうなる。

[makeWord関数の定義に実際の引数を当て込んだ場合の疑似コード]

func makeWord([]string{"t"}, "ac") {
    〜省略〜
    for loopIdx, addCharacter := range []string{"t"} {
        "t", []string{} := util.Separate([]string{"t"}, loopIdx)
        makeWord([]string{}, "ac" + "t")
    }
}

そして、さらに、↑で再帰呼び出しされる makeWord 関数は、こうなる。

[makeWord関数の定義に実際の引数を当て込んだ場合の疑似コード]

func makeWord([]string{}, "act") {
    if len([]string{}) == 0 {
        gSet.Add("act")
        return
    }
    〜省略〜
}

実はこれまで「〜省略〜」と書いていた部分には再帰呼び出しの終了判定ロジックがあった。
追加する文字列がもう空になった場合は、その時点で溜め込んでいた結果文字列を”セット”に詰めて処理を終える。（もう再帰呼び出ししない）
これが、１つの単語を作るまでの過程。
この例では、"a", "c", "t" のループの１つ目である "a" から始めて、残った "c", "t" から "c" を文字列として追加（結果、この時点で "ac" となる）し、さらに、残った "t" から "t" を文字列として追加（結果、"act" となる）して、この呼び出し分としては終了となる。
当然、ループ処理の中で "c" から始まる一連の文字列生成と "t" から始まる一連の文字列生成もある。
同じ "a" から始まるケースでも、次に、"c", "t" の中から "c" でなく "t" を選択するループもある。（その場合の結果文字列は "atc" となる）

一連のループ（及び再帰呼び出し）処理を乱暴に表現してみると↓のような感じかな。

[a][c][t]を１字ずつ処理。

[a]の場合
　　[c]を結合
　　　　[t]を結合
　　　　　　→"act"
　　[t]を結合
　　　　[c]を結合
　　　　　　→"atc"
[c]の場合
　　[a]を結合
　　　　[t]を結合
　　　　　　→"cat"
　　[t]を結合
　　　　[a]を結合
　　　　　　→"cta"
[t]の場合
　　[a]を結合
　　　　[c]を結合
　　　　　　→"tac"
　　[c]を結合
　　　　[a]を結合
　　　　　　→"tca"

追加処理過程

忘れてた。一応、文字列生成過程をログ出しするモードを追加したんだった。

$ go run main.go -sp cat
入力文字列：cat
入力文字列をスライス化してソート：[a c t]

<処理開始>
[追加前：            ][追加文字：a][追加後：           a]
[追加前：           a][追加文字：c][追加後：          ac]
[追加前：          ac][追加文字：t][追加後：         act]
[追加前：           a][追加文字：t][追加後：          at]
[追加前：          at][追加文字：c][追加後：         atc]

[追加前：            ][追加文字：c][追加後：           c]
[追加前：           c][追加文字：a][追加後：          ca]
[追加前：          ca][追加文字：t][追加後：         cat]
[追加前：           c][追加文字：t][追加後：          ct]
[追加前：          ct][追加文字：a][追加後：         cta]

[追加前：            ][追加文字：t][追加後：           t]
[追加前：           t][追加文字：a][追加後：          ta]
[追加前：          ta][追加文字：c][追加後：         tac]
[追加前：           t][追加文字：c][追加後：          tc]
[追加前：          tc][追加文字：a][追加後：         tca]

<処理結果>
act
atc
cat
cta
tac
tca

処理時間：0.000123秒

■テストコード

ついでに、テストコードも念のため載せる。

”セット”のテストコード

主な観点は、セットなので格納済みの要素を追加格納しても、要素が重複しないことの確認。

[util/set_test.go]

func TestSet(t *testing.T) {
    s := NewSet()
    assert.Equal(t, []string{}, s.List())

    s.Add("Golang")
    assert.Equal(t, []string{"Golang"}, s.List())

    s.Add("Java")
    assert.ElementsMatch(t, []string{"Golang", "Java"}, s.List())

    // 追加済みの要素を再追加
    s.Add("Golang")
    assert.ElementsMatch(t, []string{"Golang", "Java"}, s.List())

    // 追加済みの要素を再追加
    s.Add("Java")
    assert.ElementsMatch(t, []string{"Golang", "Java"}, s.List())
}

スライスをターゲット要素と残り要素に分割する関数のテストコード

バリデーションの必要なケースだったのでテーブルドリブンにしてみた。
いたずらにテストケース数を増やさないという観点では有用なものの、できれば Spock のような表現力が Go のテストツールにも欲しいところ。
https://qiita.com/sky0621/items/34179b357b13231c0027

[util/separate_test.go]

func TestSeparateOK(t *testing.T) {
    factors := []struct {
        in  input
        exp expect
    }{
        {
            in:  input{chars: []string{"c", "a", "t"}, idx: 0},
            exp: expect{target: "c", remaining: []string{"a", "t"}},
        },
        {
            in:  input{chars: []string{"c", "a", "t"}, idx: 1},
            exp: expect{target: "a", remaining: []string{"c", "t"}},
        },
        {
            in:  input{chars: []string{"c", "a", "t"}, idx: 2},
            exp: expect{target: "t", remaining: []string{"c", "a"}},
        },
        {
            in:  input{chars: []string{"c", "a", "t"}, idx: 3},
            exp: expect{target: "", remaining: []string{}},
        },
        {
            in:  input{chars: []string{"c", "a", "t"}, idx: -1},
            exp: expect{target: "", remaining: []string{}},
        },
        {
            in:  input{chars: []string{}, idx: 0},
            exp: expect{target: "", remaining: []string{}},
        },
        {
            in:  input{chars: nil, idx: 0},
            exp: expect{target: "", remaining: []string{}},
        },
    }

    for i, f := range factors {
        t.Run(fmt.Sprintf("case no %d", i), func(t *testing.T) {
            target, remaining := Separate(f.in.chars, f.in.idx)
            assert.Equal(t, f.exp.target, target)
            assert.Equal(t, f.exp.remaining, remaining)
        })
    }
}

type input struct {
    chars []string
    idx   int
}

type expect struct {
    target    string
    remaining []string
}

まとめ

与えられた文字列から並べ替えて作られうる文字列群の洗い出しロジックはこれでOK（とは言え、せいぜい１０文字ぐらいが限界）。
次回は並べ替えて作られた文字列が英単語として成立するものかどうかをチェックするロジックを入れる。

それにしても、記事を書くたびに自分の説明力の無さに唖然とする・・・。