Pierre's PIN

PIN.md

brute force approach

Generate all possible 4-digit codes with no repeat numbers ($10*9*8*7 = 5040$) and filter these so that each one must contain at least one digit from every provided guess. The resulting list has only one entry: 4-3-2-1.

def bruteForce(guesses: List[List[Int]]): List[Int] =
  // first, generate the candidate solutions:
  // all possible 4-digit PINs without repeat digits.
  val all = for
    a <- 0 to 9
    b <- 0 to 9 if b != a
    c <- 0 to 9 if c != b && c != a
    d <- 0 to 9 if d != c && d != b && d != a
  yield List(a, b, c, d)

  // filter these candidate PINs by iterating over each guess and removing candidates that don't
  // contain at least one digit that matches the digit at the same position in the guess.
  // with a guess of (1,2,3,4):
  //   * a candidate of (1,5,6,7) would pass because the first digit matches
  //   * a candidate of (5,1,6,7) would be removed because there is no matching digit at any index
  guesses
    .foldLeft(all): (candidates, guess) =>
      candidates.filter: digits =>
        digits
          .zip(guess)
          .exists: (a, b) =>
            a == b
    .head // at this point (with the challenge input) we only have 1 candidate left, and we have our solution (4, 3, 2, 1) 

guess enumeration approach

Use the provided guesses and the knowledge that each one contains 1 correct digit to construct a list of possible PINs.

First of all, transpose the list of guesses (each having length 4) to create 4 lists representing the guessed digits at each position in the PIN.

From these list of candidate digits, generate possible PINs by selecting a digit from the first position, then appending numbers at subsequent positions, avoiding duplicates and selections of more than 1 digit from the same guess, since we know each guess only contains 1 correct digit. There were 74 of these possible PINs.

Filter this list of possible PINs as we did in the brute-force approach, so that each one contains at least one digit from all of the input guesses. As above, the resulting list has only one entry: 4-3-2-1.

Note that this approach works with PINs of any length; we'd have to update the generation logic in the brute-force approach to support this.

case class GuessedDigit(digit: Int, guessNumber: Int):
  override def equals(obj: Any): Boolean = obj match
    case b: GuessedDigit => digit == b.digit
    case _               => false

  // using the digit (and ignoring the guess number) for the `hashCode`
  // makes it easier to only add unique digits to guessed PINs.
  override def hashCode(): Int = digit.hashCode()

def solve(guesses: List[List[Int]]): List[ListSet[Int]] =
  def go(
      digitCandidates: List[ListSet[GuessedDigit]],
      pin: ListSet[GuessedDigit],
      found: ListSet[ListSet[Int]]
  ): ListSet[ListSet[Int]] =
    digitCandidates match
      case digits :: remaining =>
        digits
          .filterNot:
            case GuessedDigit(_, guessNumber) => pin.map(_.guessNumber).contains(guessNumber)
          .flatMap: digit =>
            go(remaining, pin + digit, found)

      case Nil =>
        val digits = pin.map(_.digit)
        if (digits.size == guesses.head.length) found + digits
        else found

  val transposedGuesses = guesses.zipWithIndex
    .map:
      case (digits, guess) => digits.map(d => GuessedDigit(d, guess))
    .transpose
    .map(ListSet.from)

  go(transposedGuesses, ListSet.empty, ListSet.empty)
    .filter: pin =>
      guesses.forall: guess =>
        guess
          .zip(pin)
          .exists:
            case (a, b) => a == b
    .toList // with the challenge input, we have a single result: `List(ListSet(4,3,2,1))`

generating problem input

Randomly generate a correct PIN, then generate incorrect guesses that have exactly one digit from the correct PIN.

A couple of subtleties here:

1. we need to ensure that every digit from the correct PIN is contained in at least one of the guesses. I achieve this by iterating over the desired number of guesses and using the index as the position to store the correct digit. The first generated guess gets the first digit right (and the rest wrong), the second generated guess gets the 2nd digit correct, etc.
2. each guess must not have more than 1 correct digit. Using simple randomness (without checking) does not guarantee this, so I add 1 to the digit from the correct PIN instead.

def generateGuesses(pinLength: Int = 4, numGuesses: Int = 6): (List[Int], List[List[Int]]) =
    import scala.util.Random
    def randomList = Random.shuffle((0 to 9).toList).take(pinLength)

    val pin = randomList

    val guesses = Random.shuffle:
      (0 until numGuesses)
        .map: i =>
          val correctIndex = i % pinLength // the index where the guessed digit will be correct
          randomList.zipWithIndex.map: (digit, index) =>
            if (index == correctIndex) pin(index) // select the correct digit at the correct index
            else (pin(index) + 1) % 10 // at other indexes, add 1 to the correct PIN to ensure it is a different digit (using randomness would involve looping until we have a different number which i couldn't be bothered to do)
        .toList

    (pin, guesses)