問題設定

㌍や㍍などの組み文字を使って、特定の文字列が実現可能かどうか調べる
組み文字変換さんが楽しい。

そんな上記サービスでは、

クリリンノコトカア -> クリリンノコトカー

というゆらぎ?をサポートしている。

しかしこのゆらぎ、変換できる場所がNあると、
2^Nものパターンを考えなくてはならない。

例：コウコウセイ
-> コウコウセイ
-> コウコウセー
-> コーコウセー
-> コーコーセー
-> コウコーセー
-> コーコウセイ
-> コーコーセイ
-> コウコーセイ

こういう、再帰っぽく分岐していく問題に対して、generatorが有効だ。
generatorは無数のパターンを必要に応じて生成するので効率がよい。

コウコウセイのサンプル

まず、簡単のため、下記のように変換ルールを定義しておく。

const rules = [
  // [from, to]
    ['コウ', 'コー'],
    ['セイ', 'セー'],
]

generator 使わないと...

generatorを使わないでコウコウセイ問題を解こうとすると、こうなった。

function convert(str, rules, pos = 0) {

    let results = []
    results.push(str)

    for (let i = 0; i < rules.length; i++) {

        const [from, to] = rules[i]

        pos = str.indexOf(from, pos)

        while (pos !== -1) {
            let converted = str.slice(0, pos) + to + str.slice(pos + from.length)
            results = results.concat(convert(converted, rules.slice(i), pos + 1))
            pos = str.indexOf(from, pos + 1)
        }
    }
    return results
}
console.log(convert('コウコウセイ', rules))

ロジックは多少難解だ。
convertメソッドは、変換したい文字列のほか、

どこまでのルールを適用したか
文字列のどの部分にルールを適用したか

という、ループの内部状態を再帰で複製していくというものだ。

generator 使う

ではgeneratorを使って解いてみよう。

function* convert(str, rules, pos = 0) {

    yield str

    for (let i = 0; i < rules.length; i++) {

        const [from, to] = rules[i]

        pos = str.indexOf(from, pos)

        while (pos !== -1) {
            let converted = str.slice(0, pos) + to + str.slice(pos + from.length)
            yield* convert(converted, rules.slice(i), pos + 1)
            pos = str.indexOf(from, pos + 1)
        }
    }
}

なんと実は、ほとんど変わらないのだ！

結果に格納する部分が
results.push(str) から yield str になり、
結果をつなぎ合わせる部分が
results.concat() から yield* になり、
戻り値のreturnをやめただけだ。

利用の仕方にメリット

だから、まあgeneratorは、定義で楽できるわけではない感じだ。

しかし、利用の柔軟さが売りだ。
ではさきほどのgeneratorを利用してみよう。

const gen = convert('コウコウセイ', rules)

while (true) {
    const {done, value} = gen.next()
    if (done) break
    console.log(value)
}

gen.next().valueで、目的の文字列を順に取得可能だ。
全計算結果を待たずに利用できる。無駄がない！

と思うけどwhile(true)なんて嫌だ、lintもflowも怒ってくる、という人のために、
衝撃的に便利なアクセス方法を。

const iter = convert('コウコウセイ', rules)

for (const str of iter) {
    console.log(value)
}

for of でいけた！
こっちのほうが断然オススメですね！

動的計画法に便利

generatorは、このように状態を複製しながら処理を進めていく際に、
途中経過を返すことができる。
そのため、「みつかったら終了」系の探索系の処理に向いていそうだ。

ES2015 generatorを使ってコウコウセイをコーコーセーにする