Find an unpaired number in an array

Problem

If you were to group each number of an array with another one of itself, would there be any that cannot be grouped?

Solution

def findUnpairedItem[T](a: Array[T]): Option[T] = {
  a.foldLeft[Set[T]](Set.empty)({
      case (set, n) if set.contains(n) =>
        set - n
      case (set, n) =>
        set + n
    })
    .headOption
}

Test cases

assert(findUnpairedItem(Array(1, 2, 1)).contains(2))
assert(findUnpairedItem(Array(1, 2, 1, 1, 1)).contains(2))
assert(findUnpairedItem(Array(1, 1, 1, 1, 1)).contains(1))
assert(findUnpairedItem(Array(1, 1, 1, 1)).isEmpty)
assert(findUnpairedItem(Array(1, 2, 3, 1, 2)).contains(3))
assert(findUnpairedItem(Array(1, 2, 3, 3, 1, 2)).isEmpty)

Scala Concepts

foldLeft and foldRight

A 'fold' allows you to perform the equivalent of a for-loop, but with a lot less code.

def foldMutable[I, O](
    initialState: O
)(items: List[I])(f: (O, I) => O): O = {
  var result: O = initialState
  items.foreach { item => result = f(result, item) }
  result
}

Becomes:

def foldMutable[I, O](initialState: O)(items: List[I])(f: (O, I) => O): O =
  items.foldLeft(initialState)(f)

So you can see how ta Scala solution that is immutable can be represented in a mutable form. Reverse is also possible.

The big difference is that to the user it is immutable, because you only specify the next value by adding an item to an accumulator.

This presents many possibilities, most important of which is to be able to develop code in a highly predictable and obvious manner, whereas in standard for-loops, many complications can arise (wrong indices, unexpected mutations).

def getUniqueCharacters(string: String): Set[Char] = {
  var setOfCharacters = Set.empty[Char]
  string.foreach { character =>
    setOfCharacters = setOfCharacters + character
  }
  setOfCharacters
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

And in an immutable fashion:

def getUniqueCharacters(string: String): Set[Char] = {
  string.foldLeft(Set.empty[Char])(_ + _)
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

The rule of thumb is: if you want a single result, use `foldLeft`, if you want a set of intermediate results, use scanLeft and scanRight.

Option Type

The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!

Some examples:

final case class Page(title: String, mainCategory: Option[String])

val pages = List(
  Page(title = "Tail Recursion", mainCategory = None /** No category **/ ),
  Page(title = "Option", mainCategory = Some("standard library")),
  Page(title = "zip", mainCategory = Some("standard library"))
)

val categories: Set[String] = pages.flatMap(_.mainCategory).toSet

assert(categories == Set("standard library"))

def pageCategory(title: String): Option[String] = {
  for {
    page <- pages.find(_.title == title)
    category <- page.mainCategory
  } yield category
}

def pageCategory2(title: String): Option[String] =
  pages.find(_.title == title).flatMap(_.mainCategory)

def pageCategory3(title: String): Option[String] =
  pages.collectFirst {
    case Page(`title`, mainCategory) => mainCategory
  }.flatten

assert(pageCategory("zip").contains("standard library"))

assert(pageCategory("zip") == Some("standard library"))

assert(pageCategory("zip") == Some("standard library"))

assert(pageCategory2("zip") == pageCategory("zip"))

assert(pageCategory3("zip") == pageCategory("zip"))

assert(List[String]("X").headOption == Some("X"))

assert(List[String]().headOption.isEmpty)

val startWithT: String = Option("Some test") match {
  case Some(value) if value.startsWith("T") => value
  case Some(value)                          => s"T${value}"
  case None                                 => "T"
}

assert(startWithT == "TSome test")
Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

Explanation

This problem firstly does not specifically have to be on numbers - it applies in fact to any type, which is why we use generic types of Scala to implement the solution.

The solution approach is to create a Set, and as soon as an item is encountered, remove it from the set if it is there, and append to the set if it is not -- then any item remaining in the set is basically the unpaired item.

This provides us with the ability to be more precise because a type T cannot be accidentally mixed up with an Int.

The Scala approach we use is to run a 'foldLeft' - a 'foldLeft' is basically an iteration over all the values with a function, and a final result. See 'Concepts' below for explanation.