問題設定
㌍ や ㍍ などの組み文字を使って、特定の文字列が実現可能かどうか調べる
組み文字変換さん が楽しい。
そんな上記サービスでは、
クリリンノコトカア -> クリリンノコトカー
というゆらぎ?をサポートしている。
しかしこのゆらぎ、変換できる場所が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は、このように状態を複製しながら処理を進めていく際に、
途中経過を返すことができる。
そのため、「みつかったら終了」系の探索系の処理に向いていそうだ。