462 PurelyFunctional.tv Newsletter

Odd One Out.md

Odd One Out

Write a function that takes a list of words (Strings). The function should return true if exactly 1 word differs in length from the others. It should return false in all other cases.

Examples

(odd-one? ["a" "b" "c"]) ;=> false
(odd-one? ["a" "b" "cc"]) ;=> true
(odd-one? ["abc" "aa" "xyz" "jj"]) ;=> false

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn odd-one? [input]
(= [1 (dec (count input))]
(sort (keys (frequencies (map count input))))))

(defn odd-one? [strings]
  (let [n (map count strings)]
    (some #(= 1 (count (remove #{%} n))) 
          (take 2 n))))

(defn odd-one? [xs]
  (->> xs
       (partition-by count)
       (count)
       (= 2)))

(defn odd-one? [coll]
   (->> (group-by count coll)
        (filter (fn [[_ v]]  (< (count v) 2)))
        (count)
        (= 1)))

This is indeed a non-trivial task if the code is to do this with the minimal effort.

odd1 xs = 
  case nub (map legth xs)
     of { [_,_] -> True ; 
          _ -> False }

in Haskell, the complexity is hidden behind "correctly maximally lazy" implementation of the pattern matching primitive case, and of the built-in function nub (removing duplicates from a list) working in unison.

@WillNess Does that work on the list ["aa", "aa", "bbb", "bbb", "bbb"]? It should return False but yours returns True.

You're right. I've made an error there. This should fix it:

odd1 xs =
  case (group . sort
          . map length) xs
    of { [_:b,_:d]
          | null b || null d
           -> True
       ; _ -> False }

seems to be right, but it's not minimal:

> odd1 ["aa", "bbb", "ccc"]
True

> odd1 ["aa", "bbb", "bbbc", "ccc"]
False

> odd1 ["aa", "bbb", "bbbc", undefined]
*** Exception: Prelude.undefined

In the latter case we know the result is False already after inspecting the third element in the list, so the minimal code would have stopped at that point, without any further work.

(defn odd-one? [words]
  (let [kount->ws (->> words 
                      (group-by count))]
    (and (= 2 (count kount->ws))
         (->> kount->ws keys (apply -) (#{1 -1}))
         (->> kount->ws vals (map count) (some #(= 1 %)) (#(or % false))))))

Nim:

import std/[tables, sequtils]

func oddOne(words: openArray[string]): bool =
  let wordsLen = 
    words
    .mapIt(it.len) # step 1
    .toCountTable # step 2
  
  (wordsLen.len == 2) and # step 3
  (1 in wordsLen.values.toseq) # step 4