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/

I would also expect any collection of two strings with different lengths to succeed. (odd-one? ["a" "ab"]) ==> true

My ugly transducer version: (revised)

(defn odd-one? [words]
  (transduce (map count)
             (fn ([m c]
                  (if-let [cnt (m c)]
                    (if (> cnt 1)
                      m
                      (if (every? #(= % 1) (vals m))
                        (assoc m c 2)
                        (reduced nil)))
                    (if (< (count m) 2)
                      (assoc m c 1)
                      (reduced nil))))
               ([m] (some #(= % 1) (vals m))))
             {}
             words))

As most things, how hard is a problem is subjective. It's entirely possible to have a readable solution even in old Java (pre-Java 8, which added streams, functional interfaces and varargs). Using the diamond operator for brevity, but everything else is just old collections APIs:

import java.util.*;

public class OddOneOut {

    public static boolean hasOddOne(List<String> words) {
        Map<Integer, Integer> countByLength = new HashMap<>();
        for (String word: words) {
            Integer length = word.length();
            Integer count = countByLength.containsKey(length) ? countByLength.get(length) + 1 : 1;
            countByLength.put(length, count);
        }
        Set<Integer> counts = new HashSet<>();
        counts.addAll(countByLength.values());

        return (counts.contains(1) && (counts.size() == 2 || words.size() == 2));
    }

    public static void main(String[] args) {
        System.out.println(hasOddOne(Arrays.asList(new String[]{"a", "b", "c"}))); // false
        System.out.println(hasOddOne(Arrays.asList(new String[]{"a", "b", "cc"}))); // true
        System.out.println(hasOddOne(Arrays.asList(new String[]{"abc", "aa", "xyz", "jj"}))); // false
        System.out.println(hasOddOne(Arrays.asList(new String[]{"1", "22"}))); // true
        System.out.println(hasOddOne(Arrays.asList(new String[]{"20", "22"}))); // false
    }
}

Edit: minor edit to consider the case of two words of equal/different length

(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