Go to list of users who liked
More than 5 years have passed since last update.
ES2015 generatorを使ってコウコウセイをコーコーセーにする
問題設定
㌍ や ㍍ などの組み文字を使って、特定の文字列が実現可能かどうか調べる
組み文字変換さん が楽しい。
そんな上記サービスでは、
クリリンノコトカア -> クリリンノコトカーというゆらぎ?をサポートしている。
しかしこのゆらぎ、変換できる場所がNあると、
2^Nものパターンを考えなくてはならない。
例：コウコウセイ-> コウコウセイ-> コウコウセー-> コーコウセー-> コーコーセー-> コウコーセー-> コーコウセイ-> コーコーセイ-> コウコーセイこういう、再帰っぽく分岐していく問題に対して、generatorが有効だ。
generatorは無数のパターンを必要に応じて生成するので効率がよい。
コウコウセイ のサンプル
まず、簡単のため、下記のように変換ルールを定義しておく。
construles=[// [from, to]['コウ','コー'],['セイ','セー'],]generator 使わないと...
generatorを使わないでコウコウセイ問題を解こうとすると、こうなった。
functionconvert(str,rules,pos=0){letresults=[]results.push(str)for(leti=0;i<rules.length;i++){const[from,to]=rules[i]pos=str.indexOf(from,pos)while(pos!==-1){letconverted=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)}}returnresults}console.log(convert('コウコウセイ',rules))ロジックは多少難解だ。
convertメソッドは、変換したい文字列のほか、
- どこまでのルールを適用したか
- 文字列のどの部分にルールを適用したか
という、ループの内部状態を再帰で複製していくというものだ。
generator 使う
ではgeneratorを使って解いてみよう。
function*convert(str,rules,pos=0){yieldstrfor(leti=0;i<rules.length;i++){const[from,to]=rules[i]pos=str.indexOf(from,pos)while(pos!==-1){letconverted=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を利用してみよう。
constgen=convert('コウコウセイ',rules)while(true){const{done,value}=gen.next()if(done)breakconsole.log(value)}gen.next().valueで、目的の文字列を順に取得可能だ。
全計算結果を待たずに利用できる。無駄がない！
と思うけどwhile(true)なんて嫌だ、lintもflowも怒ってくる、という人のために、
衝撃的に便利なアクセス方法を。
constiter=convert('コウコウセイ',rules)for(conststrofiter){console.log(value)}for of でいけた！
こっちのほうが断然オススメですね！
動的計画法に便利
generatorは、このように状態を複製しながら処理を進めていく際に、
途中経過を返すことができる。
そのため、「みつかったら終了」系の探索系の処理に向いていそうだ。
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme