About eight years ago as part of an interview process I was given a take home code challenge. Considering how much it’s changed in the tech world and the fact that company is no longer hirigin I feel comfortable sharing the details of the challenge.

You run a paint shop, and there are a few different colors of paint you can prepare. Each color can be either “gloss” or “matte”. You have a number of customers, and each have some colors they like, either gloss or matte. No customer will like more than one color in matte You want to mix the colors, so that:

  • There is just one batch for each color, and it’s either gloss or matte.
  • For each customer, there is at least one color they like.
  • You make as few mattes as possible (because they are more expensive). Your program should accept an input file as a command line argument, and print a result to standard out. An example input file is:

5
1 M 3 G 5 G
2 G 3 M 4 G
5 M

The first line specifies how many colors there are.

Each subsequent line describes a customer. For example, the first customer likes color 1 in matte, color 3 in gloss and color 5 in gloss.

Your program should read an input file like this, and print out either that it is impossible to satisfy all the customer, or describe, for each of the colors, whether it should be made gloss or matte.

The output for the above file should be:

G G G G M

resolvers += Resolver.sonatypeCentralSnapshots
libraryDependencies += "com.codiff" %% "fairstream" % "0.0-9f9db42-SNAPSHOT"

import com.codiff.fairstream.Fair._

sealed trait Finish
final case object Gloss extends Finish
final case object Matte extends Finish

final case class Color(id: Int)

final case class Paint(color: Color, finish: Finish)

def solve(
    numColors: Int,
    customers: List[List[Paint]]
): Option[Vector[Finish]] = {

  def go(color: Int, assignment: Vector[Finish]): Fair[Vector[Finish]] = {
    // Prune early: if any customer's preferences are all decided and none match
    val dominated = customers.exists { prefs =>
      prefs.nonEmpty && prefs.forall { p =>
        p.color <= assignment.length && assignment(p.color - 1) != p.finish
      }
    }
    if (dominated) empty
    else if (color > numColors) unit(assignment)
    else
      mplus(
        go(color + 1, assignment :+ Gloss),
        go(color + 1, assignment :+ Matte)
      )
  }

  // Enumerate all valid assignments, pick the one with fewest mattes
  val solutions = Fair.runM(None, None, go(1, Vector.empty))
  solutions.minByOption(_.count(_ == Matte))
}