Discussion on: JavaScript Challenge

[Avalander]

I know the header says "Javascript", but this is really easy in Haskell (or any language that has built-ins for sorting and grouping collections)

import Data.List (sort, group)

groupFrequencies :: String -> [[Int]]
groupFrequencies = group . sort . map length . group . sort

isLucky :: String -> Bool
isLucky x = length freqs == 1 || isAlmostLucky freqs
  where
    freqs = groupFrequencies x
    isAlmostLucky freqs = length freqs == 2 &&
                          length (last freqs) == 1 &&
                          head (head freqs) + 1 == head (last freqs)

The algorithm is as follows:

1. Sort the characters in the string: "abcabcb" -> "aabbbcc"
2. Group characters: "aabbbcc" -> [ "aa", "bbb", "cc" ]
3. Map outer list to length: [ "aa", "bbb", "cc" ] -> [ 2, 3, 2 ]
4. Sort and group again: [ 2, 3, 2 ] -> [[ 2, 2 ], [ 3 ]]

If the outer array has length of 1, all characters appear with the exact same frequency and we have a lucky string.

If the outer array has a length of 2, the second element has a length of 1, and the element in the second array is one higher than any element in the first array, we have an almost lucky string.

[Avalander]

Of course, we can just implement the same algorithm in Javascript, we just need to implement a group function. In this case, I have implemented it as a reducer function so that I can use it in an array method chain.

const last = arr => arr[arr.length - 1]

const appendToLast = (arr, x) => {
  const lastElement = last(arr)
  lastElement.push(x)
  return arr
}

const group = (prev, x) =>
  prev.length === 0
    ? [[ x ]]
    : last(prev)[0] === x
    ? appendToLast(prev, x)
    : [ ...prev, [ x ]]

// Everything above this line is because Javascript doesn't have group built in.

const length = arr => arr.length

const isAlmostLucky = groupedFreqs =>
  groupedFreqs.length === 2 &&
  groupedFreqs[1].length === 1 &&
  groupedFreqs[1][0] === groupedFreqs[0][0] + 1

const isLucky = str => {
  const groupedFreqs = str.split('')
    .sort()
    .reduce(group, [])
    .map(length)
    .sort()
    .reduce(group, [])
  return groupedFreqs.length === 1 ||
    isAlmostLucky(groupedFreqs)
}