algorithm - 繰り返し文字を見つけるための関数型プログラミング アルゴリズム

Question

「zxcvbn」パスワード強度アルゴリズムを JavaScript から Scalaに変換しています。文字列内の繰り返し文字のシーケンスを見つけるための純粋な関数型アルゴリズムを探しています。

JavaScript から命令型バージョンを翻訳できることはわかっていますが、関数型プログラミングに通常与えられるすべての理由から、これをできるだけ副作用のないようにしたいと考えています。

アルゴリズムは、Scala、Clojure、Haskell、F#、さらには疑似コードで作成できます。

ありがとう。

Answer 1

Haskell の標準的な高階関数を使用する:

• Data.List.groupリスト内の等しい要素の連続を見つけます:

  > group "abccccdefffg"
  ["a","b","cccc","d","e","fff","g"]
  

• 要素自体ではなく、これらの実行の長さを気にします。

  > let ls = map length $ group "abccccdefffg"
  > ls
  [1,1,4,1,1,3,1]
  

• 次に、各グループの開始位置が必要です。これはグループの長さの部分的な合計であり、次を使用して計算できますscanl。

  > scanl (+) 0 ls
  [0,1,2,6,7,8,11,12]
  

• これら 2 つのリストを圧縮すると、開始位置と対応する長さのすべてのペアが得られます。

  > zip (scanl (+) 0 ls) ls
  [(0,1),(1,1),(2,4),(6,1),(7,1),(8,3),(11,1)]
  

• 最後に、長さが 3 未満のグループを削除します。

  > filter ((>= 3) . snd) $ zip (scanl (+) 0 ls) ls
  [(2,4),(8,3)]
  

これをまとめると：

import Data.List (group)

findRuns :: Eq a => [a] -> [(Int, Int)]
findRuns xs = filter ((>= 3) . snd) $ zip (scanl (+) 0 ls) ls 
  where ls = map length $ group xs

Answer 2

これが別のScalaソリューションです

def findRuns(password: String): List[(Int, Int)] = {
  val zipped = password.zipWithIndex
  val grouped = zipped groupBy { case (c, i) => c }
  val filtered = grouped.toList.filter{ case (c, xs) => xs.length >= 3 }
  val mapped = filtered map { case (c, xs) => xs }
  val result = mapped map (xs => (xs.head._2, xs.length))
  result.sorted
}

Answer 3

Clojureのhammarのアルゴリズムのバージョン

 (defn find-runs [s]
    (let [ls (map count (partition-by identity s))]
        (filter #(>= (% 1) 3) 
                (map vector (reductions + 0 ls) ls))))

Answer 4

これが私が思いついたScalaソリューションです。

def repeatMatch(password: String): List[(Int, Int)] = {
  val length = password.length

  @tailrec
  def loop(offset: Int,
           result: List[(Int, Int)]): List[(Int, Int)] = {
    if (offset >= length) result.reverse
    else {
      val candidate = password.charAt(offset)
      val run = password.substring(offset).zip(Array.fill(length)(candidate)).
        takeWhile{case (first, second) => first == second}.length
      if (run > 2) loop(offset + run, (offset, run) :: result)
      else loop(offset + 1, result)
    }
  }

  loop(0, List.empty[(Int, Int)])
}

テスト ケース の場合repeatMatch("abccccdefffg")、結果は次のようになります。List((2,4), (8,3))

たぶん、計算runが改善される可能性があります。