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? [words]
  (let [lengths (->> words
                     (map count)
                     (frequencies)
                     vals)]
    (and (= (count lengths) 2)
         (contains? (set lengths) 1))))

(defn odd-one? [strings]
  (->> strings
       (map count)
       frequencies
       vals
       set
       (= #{1 (dec (count strings))})))

;; roughly the same as above (but found independently)
(defn odd-one? [words]
  (let [m (frequencies (map count words))]
    (and (== (count m) 2)
         (true? (some #(== % 1) (vals m))))))

The solution provided does not necessarily follow from problem statement - Suppose I have words of lengths 3, 3, 4, 4, and 5. There is one word whose length differs from the others but the list would return false under some solutions.

• Problem statement does not say all other words need to have same length to return true
• A list of 2 words with different lengths would violate problem statement in that there would be more than 1 word whose length differs from the others.

@seltzer1717 you're right ... I was too much example-driven :-)

But wait ... 4, 4 are two words differing from 3, 3 and 5 ...

@seltzer1717 I took it to mean that one word is of length X and all other words are of length Y, where X != Y. Further, there are two or more words in the input.

(defn odd-one? [coll]
  (-> (map count coll)
      (frequencies)
      (vals)
      (set)
      (as-> $ (and (> (count $) 1) (contains? $ 1)))))

Not that I love the verbosity of Java's functional libs but I don't think this one is too bad... Just had to try based on your tweet @ericnormand :)

  public static boolean oddOneOut(String[] strings) {
    Map<Integer, List<String>> lengthsPresent =
        Arrays.stream(strings)
            .collect(Collectors.groupingBy(String::length));

    if (lengthsPresent.size() != 2) {
      return false;
    }

    return lengthsPresent.values().stream()
        .map(List::size)
        .anyMatch(size -> size == 1);
  }

@RussellSpitzer Is it hard because collections are hard?

You don't even need streams. Not sure if this compiles.

  public static boolean oddOneOut(String[] strings) {
    Map<Integer, Integer> lengthsPresent = new HashMap<>();
     
   for(String s: strings) {
    if(lengthsPresent.containsKey(s.length))
      lengthsPresent.put(s.length, 1+lengthsPresent.get(s.length));
    else
      lengthsPresent.put(s.length, 1);
    }

    if (lengthsPresent.size() != 2) {
      return false;
    }

    for(int x: lengthsPresent.values()) {
      if(x == 1)
        return true;
    }

    return false;
  }

That looks valid to me, I was responding to functional.tv so I thought I should be a little functional ;)

(defn odd-one? [xs]
 (let [g (group-by count xs)]
  (and
   (= 2 (count g))
   (= 1 (first (sort (map #(count (second %)) g)))))))

So based on linked problem source:

(defn odd-one? [words]
  (-> (map count words)  ; lengths of words
      frequencies  ; map of lengths to word count
      vals  ; word counts
      frequencies  ; map of counts to instances
      (get 1)  ; number of instances of count 1
      (= 1))) ; only 1 instance

Solution maps exactly to problem statement.

My reading of the problem is that a collection of exactly one string should succeed. Same reasoning as (every? true? nil) ==> true.

(defn odd-one? [words]
  (let [fqs (frequencies (map count words))]
    (and (<= (count fqs) 2)
         (= (reduce min 2 (vals fqs)) 1))))

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