As a followup to my earlier question on finding runs of the same character in a string, I would also like to find a functional algorithm to find all substrings of length greater than 2 that are ascending or descending sequences of letters or digits (e,g,: "defgh", "34567", "XYZ", "fedcba", "NMLK", 9876", etc.) in a character string ([Char]). The only sequences that I am considering are substrings of A..Z, a..z, 0..9, and their descending counterparts. The return value should be a list of (zero-based offset, length) pairs. I am translating the "zxcvbn" password strength algorithm from JavaScript (containing imperative code) to Scala. I would like to keep my code as purely functional as possible, for all the usual reasons given for writing in the functional programming style.
My code is written in Scala, but I can probably translate an algorithm in any of Clojure, F#, Haskell, or pseudocode.
Example: For the string qweABCD13987 would return [(3,4),(9,3)].
I have written a rather monsterous function that I will post when I again have access to my work computer, but I am certain that a more elegant solution exists.
Once again, thanks.
I guess a nice solution for this problem is really more complicated than it seems at first. I'm no Scala Pro, so my solution is surely not optimal and nice, but maybe it gives you some ideas.
The basic idea is to compute the difference between two consecutive characters, afterwards it unfortunately gets a bit messy. Ask me if some of the code is unclear!
object Sequences {
val s = "qweABCD13987"
val pairs = (s zip s.tail) toList // if s might be empty, add a check here
// = List((q,w), (w,e), (e,A), (A,B), (B,C), (C,D), (D,1), (1,3), (3,9), (9,8), (8,7))
// assuming all characters are either letters or digits
val diff = pairs map {case (t1, t2) =>
if (t1.isLetter ^ t2.isLetter) 0 else t1 - t2} // xor could also be replaced by !=
// = List(-6, 18, 36, -1, -1, -1, 19, -2, -6, 1, 1)
/**
*
* @param xs A list indicating the differences between consecutive characters
* @param current triple: (start index of the current sequence;
* number of current elements in the sequence;
* number indicating the direction i.e. -1 = downwards, 1 = upwards, 0 = doesn't matter)
* @return A list of triples similar to the argument
*/
def sequences(xs: Seq[Int], current: (Int, Int, Int) = (0, 1, 0)): List[(Int, Int, Int)] = xs match {
case Nil => current :: Nil
case (1 :: ys) =>
if (current._3 != -1)
sequences(ys, (current._1, current._2 + 1, 1))
else
current :: sequences(ys, (current._1 + current._2 - 1, 2, 1)) // "recompute" the current index
case (-1 :: ys) =>
if (current._3 != 1)
sequences(ys, (current._1, current._2 + 1, -1))
else
current :: sequences(ys, (current._1 + current._2 - 1, 2, -1))
case (_ :: ys) =>
current :: sequences(ys, (current._1 + current._2, 1, 0))
}
sequences(diff) filter (_._2 > 1) map (t => (t._1, t._2))
}