Daily Challenge #33 - Did you mean...?

/**
 * Find the Levenshtein distance between two strings
 * (see https://en.wikipedia.org/wiki/Levenshtein_distance)
 * @param {String} a  First string to compare
 * @param {String} b  Second string to compare
 */
function lev(a, b) {
  const _step = (i, j) => (
    Math.min(i, j) === 0 ? Math.max(i, j) :
    Math.min(
      _step(i-1, j) + 1,
      _step(i, j-1) + 1,
      _step(i-1, j-1) + (a[i-1] === b[j-1] ? 0 : 1)
    )
  )
  return _step(a.length, b.length)
}

/**
 * Find the most similar word in the dictionary to the provided word
 * @param {String[]} dict   Array of strings to use as dictionary
 * @param {String} word     Word to correct
 */
function findMostSimilar (dict, word) {
  const [, closest] = dict.reduce(([min, best], next) => {
    const dist = lev(word, next)
    return dist < min ? [dist, next] : [min, best]
  }, [Infinity, ''])
  return closest
}

// Tests
const a1 = ['cherry', 'pineapple', 'melon', 'strawberry', 'raspberry']
const a2 = ['stars', 'mars', 'wars', 'codec', 'codewars']
const a3 = ['javascript', 'java', 'ruby', 'php', 'python', 'coffeescript']

const testCases = [
  [a1, 'strawbery', 'strawberry'],
  [a1, 'berry', 'cherry'],
  [a2, 'code', 'codec'],
  [a2, 'starwars', 'stars'],
  [a3, 'script', 'javascript'],
  [a3, 'cofcript', 'coffeescript']
]

let caseNum = 1
for (const [dict, input, expected] of testCases) {
  const output = findMostSimilar(dict, input)
  const [status, style] = (
    output === expected
      ? ['✔', 'color: green']
      : ['❌', 'color: red']
  )
  console.log(`${caseNum++}: ${input} should match ${expected} %c${status}`, style)
  if (output !== expected) {
    console.log(`    returned ${output} instead`)
  }
}

fruits = ['cherry', 'pineapple', 'melon', 'strawberry', 'raspberry']

def find_most_similar(word):
    counts = []
    for fruit in fruits:
        count = 0
        if word == fruit:
            return fruit
        else:
            for i in range(min(len(word), len(fruit))):
                count += abs(ord(word[i]) - ord(fruit[i])) + max(0, len(fruit)-len(word))
        counts.append(count)
    min_count = min(counts)
    return fruits[counts.index(min_count)]

let findClosest = (str, arr) => {
    let maxSimilarity = 0;
    let tempWord = '';
    for (let p of arr) {
        let count = 0;
        p.split('').forEach(x => {
            if (str.indexOf(x) > -1)
                count++;
        });
        if (count > maxSimilarity) {
            maxSimilarity = count;
            tempWord = p;
        }
    }
    return tempWord;
}

let result = findClosest('hp', ['javascript', 'java', 'ruby', 'php', 'python', 'coffeescript']);
console.log(result);

(define (lev a b)
  (define (lev_ i j)
    (cond
      ((zero? (min i j))
       (max i j))
      (else
       (min (+ 1 (lev_ (- i 1) j))
            (+ 1 (lev_ i (- j 1)))
            (+ (if (char=? (string-ref a i) (string-ref b j))
                   0
                   1)
               (lev_ (- i 1) (- j 1)))))))
  (lev_ (- (string-length a) 1) (- (string-length b) 1)))

(define (mostSimilar arr word)
  (define (mostSimilar_ arr acc_word acc_lev)
    (cond
      ((null? arr) acc_word)
      (else
       (let ((new_lev (lev (car arr) word)))
         (if (> acc_lev new_lev)
           (mostSimilar_ (cdr arr) (car arr) new_lev)
           (mostSimilar_ (cdr arr) acc_word acc_lev))))))
  (mostSimilar_ (cdr arr) (car arr) (lev (car arr) word)))

(format #t "Result: ~a~%"
  (mostSimilar
    (list "strawberry" "bean" "banana" "cherry")
    "berry"))

lev :: (Eq a) => [a] -> [a] -> Int
lev a b = let memoed = [ [ lev' levmemo i' j' | j' <- [0..] ] | i' <- [0..] ]
              levmemo i j = memoed !! i !! j
          in levmemo (length a) (length b)
          where lev' f i j
                  | min i j == 0 = max i j
                  | otherwise = let n = f (i-1) j + 1
                                    m = f i (j-1) + 1
                                    q = f (i-1) (j-1) + if (a!!(i-1)) == (b!!(j-1)) then 0 else 1
                                in min n $ min m q

mostSimilar :: (Eq a) => [[a]] -> [a] -> [a]
mostSimilar list word = fst $ foldl1 smallestDistance $ zip list $ map (lev word) $ list
              where smallestDistance a@(minel, mindst) b@(el, dst) =
                      if dst < mindst then b
                      else a

defmodule Closest do
  def find(candidates, word) do
    Enum.min_by(
      candidates,
      &(&1
        |> String.myers_difference(word)
        |> Enum.count())
    )
  end
end