Problem185.scala

package euler

import collection.immutable.TreeMap
import collection.mutable

/**
 * Developed with pleasure
 * User: hamsterofdeath
 * Date: 03.10.12
 * Time: 22:01
 */
object Problem185 {

  def main(args: Array[String]) {
    type Guess = IndexedSeq[(Int, Int)]
    type Leaf = (List[(Int, Int)], Map[Int, Set[Int]])
    val test = List(90342L -> 2, 70794L -> 0, 39458L -> 2, 34109L -> 1, 51545L -> 2, 12531L -> 1)
    val tricky = List.tabulate(9)(_.toLong -> 0)
    val realData = List(5616185650518293L -> 2,
      3847439647293047L -> 1, 5855462940810587L -> 3, 9742855507068353L -> 3,
      4296849643607543L -> 3, 3174248439465858L -> 1, 4513559094146117L -> 2,
      7890971548908067L -> 3, 8157356344118483L -> 1, 2615250744386899L -> 2,
      8690095851526254L -> 3, 6375711915077050L -> 1, 6913859173121360L -> 1,
      6442889055042768L -> 2, 2321386104303845L -> 0, 2326509471271448L -> 2,
      5251583379644322L -> 2, 1748270476758276L -> 3, 4895722652190306L -> 1,
      3041631117224635L -> 3, 1841236454324589L -> 3, 2659862637316867L -> 2)
    def solutionOf(input: List[(Long, Int)]) = {
      val digitCount = input.head._1.toString.length
      val invalids = Array.fill(digitCount)(mutable.BitSet.empty:mutable.Set[Int])
      def recur(guessesLeft: List[(Guess, Int)],
                assumedValids: mutable.HashSet[(Int, Int)],
                assumedInvalids: Array[mutable.Set[Int]],
                usedSlots: mutable.Set[Int]): Traversable[Leaf] = {
        if (guessesLeft.isEmpty) {
          val invalid = assumedInvalids.zipWithIndex.map(e => e.swap.copy(_2 = e._1.toSet))
          Some(assumedValids.toList.sortBy(_._2) -> TreeMap.apply(invalid: _*))
        } else {
          val (guess, correct) = guessesLeft.head
          val allDigits = guess.filterNot(assumedValids)
          val combinationSize = correct - (guess.length - allDigits.length)
          val buildCombinationsOf = allDigits.filterNot(digit => {
            usedSlots.contains(digit._2) || assumedInvalids(digit._2)(digit._1)
          })
          buildCombinationsOf.combinations(combinationSize).flatMap(assumeCorrect => {
            //prepare incomplete solution for the next level...
            val blockedIndicesBelowThis = assumeCorrect.map(_._2)
            val lookUp = mutable.BitSet.empty ++= blockedIndicesBelowThis // faster on long numbers
            val additionalInvalids = allDigits.filterNot(e => {
              assumedInvalids(e._2)(e._1) || lookUp(e._2)
            })
            val invalidsForCase = {
              //caution, assumedInvalids is modified here! "assumedInvalids" and "invalidsForCase" are now the same
              additionalInvalids.foldLeft(assumedInvalids)((acc, e) => {acc(e._2) += e._1; acc})
            }
            //caution: "assumedValids" has been modified and is the same as enhancedSolution
            val enhancedSolution = assumeCorrect.foldLeft(assumedValids)((acc, e) => acc += e)

            //if we didn't contradict the numbers so far, go a level deeper
            val isValid = assumedValids.forall(digit => !invalidsForCase(digit._2).contains(digit._1))
            if (isValid) {
              //caution, mutable magic again!
              val myUsedSlots = usedSlots ++= blockedIndicesBelowThis
              val result = recur(guessesLeft.tail, enhancedSolution, invalidsForCase, myUsedSlots)
              //cleanup since we are not pure here :(
              assumeCorrect.foldLeft(assumedValids)((acc, e) => acc -= e)
              usedSlots --= blockedIndicesBelowThis
              additionalInvalids.foldLeft(assumedInvalids)((acc, e) => {acc(e._2) -= e._1; acc})
              result
            } else {
              Nil
            }
          }).toList // force evaluation now, otherwise we'll get a huge mess up because of the mutable stuff...
        }
      }
      val prepared = input.sortBy(_._2).map(e => e._1.toString.map(_.getNumericValue).zipWithIndex -> e._2)
      val suggestions = recur(prepared, mutable.HashSet.empty[(Int, Int)], invalids, mutable.BitSet.empty)
      suggestions.toList
    }
    def pretty(leaf: Leaf) = {
      val mustBe = (0 until 16).map(i => {
        leaf._1.find(t => t._2 == i).map(_._1.toString).getOrElse("X")
      }).mkString
      val cantBe = (for (digit <- 0 to 9; position <- 0 until 16)
      yield ({
          val invalids = leaf._2.get(position).getOrElse(Set.empty)
          (if (invalids.contains(digit)) digit.toString else "-")
        })).grouped(16).map(e => "Can't be: " + e.mkString)
      "Must be:  " + mustBe + "\n" + cantBe.mkString("\n")
    }
    //BenchHelper.benchIt("dslkfslj",1000,1000,solutionOf(test))
    val step2 = BenchHelper.timed(solutionOf(realData))
    step2.foreach(e => println(pretty(e)))
  }
}