code puzzles

Puzzles.scala

object Puzzles {
  
  /**
   * 8 queens
   * https://en.wikipedia.org/wiki/Eight_queens_puzzle
   * generalized to any N
   */
  object Queens {
    
    /**
     * entry point
     */
    def queens(n: Int): Int = {
      if (n < 2) 1
      else queensRec(0, n, Nil)
    }
    
    def queensRec(currentRow: Int,
                  boardWidth: Int,
                  placements: List[Int]): Int = {
      if (currentRow == boardWidth - 1){
        if ((0 until boardWidth).find(column => !placements.contains(column)).exists(canPlaceQueen(placements, currentRow))) 1
        else 0
      }
      else (0 until boardWidth).collect { case col if !placements.contains(col) && canPlaceQueen(placements, currentRow)(col) =>
        queensRec(currentRow + 1, boardWidth, col :: placements)
      }.sum
    }
    
    def canPlaceQueen(queens: List[Int], row: Int): Int => Boolean = col => {
      queens.foldRight(true -> 0){ case (queenCol, (validSoFar, queenRow)) =>
        (validSoFar && !(row - queenRow == math.abs(col - queenCol)), queenRow + 1)
      }._1
    }
  }
  
  /**
   * Given a string of a logical expression without parenthesis,
   * that consists only of the characters T,F for true and false,
   * and boolean operators: &,|,^ for AND, OR, XOR,
   * return the ratio of possible evaluations of entire expression as true,
   * and the number of evaluations as false,
   * when non-benign parenthesis are added per evaluation.
   */
  object EvaluationRatio {
    
    /**
     * entry point
     */
    def countEval(expr: String, result: Boolean): (Int, Int) = {
      if (expr.isEmpty) 0 -> 0
      else {
        require(expr.matches("([FT][\\|\\&\\^])*[FT]"), "expression must be all bools separated by operators")
        dynCountEval(expr.toList, Map.empty)._1
      }
    }
    
    def dynCountEval(expr: List[Char], cache: Map[String, (Int, Int)]): ((Int, Int), Map[String, (Int, Int)]) = expr match {
      case 'F' :: Nil => (1, 0) -> cache
      case 'T' :: Nil => (0, 1) -> cache
      case lst =>
      val opIndices = (1 until lst.length by 2)
      opIndices.foldLeft(((0, 0), cache)) { case (((fCnt, tCnt), currCache), opIndex) =>
        val (pexp, op :: sexp) = lst.splitAt(opIndex)
        val pkey = pexp.mkString
        val skey = sexp.mkString
        val ((pfcnt, ptcnt), nxt0Cache) = fetchFromCacheOrRecurse(pkey, pexp, currCache)
        val ((sfcnt, stcnt), nxt1Cache) = fetchFromCacheOrRecurse(skey, sexp, nxt0Cache)
        val (nfcnt, ntcnt) = op match {
          case '&' => ((pfcnt * (sfcnt + stcnt)) + (ptcnt * sfcnt), ptcnt * stcnt)
          case '|' => (pfcnt * sfcnt, (ptcnt * (sfcnt + stcnt)) + (pfcnt * stcnt))
          case '^' => ((pfcnt * sfcnt) + (ptcnt * stcnt), (pfcnt * stcnt) + (ptcnt * sfcnt))
        }
        ((fCnt + nfcnt, tCnt + ntcnt), nxt1Cache)
      }
    }
    
    def fetchFromCacheOrRecurse(key: String,
                                    expr: List[Char],
                                    cache: Map[String, (Int, Int)]): ((Int, Int), Map[String, (Int, Int)]) = {
      if (cache.contains(key)) cache(key) -> cache
      else {
        val (counts, nextCache) = dynCountEval(expr, cache)
        counts -> nextCache.updated(key, counts)
      }
    }
  }
}