Nearest Vowel.md

Distance to nearest vowel

Write a function that takes a string as argument. Each character in the string will be a letter. The function should return a sequence containing the distances from each corresponding letter in the string to the nearest vowel in the string.

For example:

(nearest-vowels "aeiou") ;=> [0 0 0 0 0]  ;; if the letter is a vowel, the distance is 0
(nearest-vowels "babbb") ;=> [1 0 1 2 3]
(nearest-vowels "babbba") ;=> [1 0 1 2 1 0]

Notes:

• All input strings will contain at least one vowel and all letters.
• Vowels are a, e, i, o, and u.

(defn isVowel? [c] ((set "aiueo") c))

(defn vowel_positions [letters]
  (keep-indexed #(when (isVowel? %2) %1) letters))

(defn findvowel [idx pos]
  (reduce min (map #(Math/abs (- idx %)) pos)))

;; Slow but readable, Quadratic ish, nLetters * nVowels approach, nearest_vowels.
(defn nearest-vowels [letters]
  (let [vpos (vowel_positions letters)]
    (map #(findvowel % vpos) (range (count letters)))))

(defn updown [[start stop]]
  (let [up (range (+ 1 (- stop start)))]
    (drop-last (map min up (reverse up)))))

;; * Linear ish, nearest_vowelz.
(defn nearest-vowelz [letters]
  (let [vowel_pos  (vowel_positions letters)
        first_pos  (first vowel_pos)
        last_pos   (last  vowel_pos)
        left       (map #(- first_pos %) (range first_pos))
        middle     (mapcat updown (partition 2 1 vowel_pos))
        right      (range (- (count letters) last_pos))]
     (concat left middle right)))
     
;;The idea is to break the problem into the following steps:

(nearest-vowelz "cdefghijkabc")

;;- Find the vowel positions: (2 6 9)
;;- Solve for the left part, on the left side of 2: (2 1)
;;- Solve for the pairs of vowels in the middle: ((2 6) (6 9))
;;      * Fill the range between these pair of vowels with symmetrical up and down sequence. 
;;      * For example for those two pairs ((0 1 2 1 0) (0 1 1 0))
;;      * Concatenating middle, skip duplicates (0 1 2 1 0 (1 1 0))
;;- Solve for the right, after 9 : (0 1 2)
;;- Concatenate them all 

(2 1 0 1 2 1 0 1 1 0 1 2)

;; Handling random generated letters up to million under a sec

(def timed (let [n 1000000
                   s (gen/generate (gen/vector gen/char-alpha) n)]
           (time (doall (nearest-vowelz s)))))

;;"Elapsed time: 515.240426 msecs"

Same logic in scala

def vowel_pos(letters: String)   = {
  letters.zipWithIndex.flatMap { 
    case (c, idx) if "aiueo".contains(c) => idx :: Nil
    case _ => Nil
  } 
}

def updown(start:Int, stop:Int) = {
    val range = (start to stop)
    range.reverse.zip(range).map{
      case (a,b) => Math.min(a,b) - start
    } init
}

def leftOf(start:Int) = (0 to start).toList.tail.reverse
def rightOf(start:Int, to:Int) = (0 to (to - start)).init.toList

def nearestVowel(letters: String) = {
    val vowels = vowel_pos(letters)
    val middle = vowels.sliding(2,1).flatMap {
      case Vector(a,b) => updown(a,b)
    }.toList
    
    leftOf(vowels(0)) ::: middle ::: rightOf(vowels.last, letters.length)
    
}