基礎からの覆面算

verbal_arith_01.scala

  // as straight forward as possible
  def solve1 = {
    val digits = 0 to 9
    def num(ds: Int*) = ds.foldLeft(0){10 * _ + _}
    for {
      // send
      s <- digits diff Seq(0)
      e <- digits diff Seq(s)
      n <- digits diff Seq(s, e)
      d <- digits diff Seq(s, e, n)
      // more
      m <- digits diff Seq(0, s, e, n, d)
      o <- digits diff Seq(s, e, n, d, m)
      r <- digits diff Seq(s, e, n, d, m, o)
      // money
      y <- digits diff Seq(s, e, n, d, m, o, r)
      // conform to verbal?
      send = num(s, e, n, d)
      more = num(m, o, r, e)
      money = num(m, o, n, e, y)
      if (send + more == money)
    } yield (send, more, money)  
  }

verbal_arith_02.scala

  // prune brunches
  def solve2 = {
    val digits = 0 to 9
    def num(ds: Int*) = ds.foldLeft(0){10 * _ + _}
    for {
      // one's digits
      d <- digits diff Seq()
      e <- digits diff Seq(d)
      y <- digits diff Seq(d, e)
      if ((num(d) + num(e)) % 10 == num(y))
        
      // ten's digits
      n <- digits diff Seq(d, e, y)
      r <- digits diff Seq(d, e, y, n)
      if ((num(n, d) + num(r, e)) % 100 == num(e, y))
        
      // hundred's digits
      o <- digits diff Seq(d, e, y, n, r)
      if ((num(e, n, d) + num(o, r, e)) % 1000 == num(n, e, y))
        
      // thousand's digits
      s <- digits diff Seq(0, d, e, y, n, r, o)
      m <- digits diff Seq(0, d, e, y, n, r, o, s)
      send = num(s, e, n, d)
      more = num(m, o, r, e)
      money = num(m, o, n, e, y)
      if (send + more == money)
    } yield (send, more, money)  
  }

verbal_arith_03.scala

  // generic solver
  def solve3(bottom: String, parts: String*) = {
    val digits = 0 to 9
    
    val all = bottom +: parts
    val nonZeroChars = all.map{_.head}.toSet
    val maxDigit = all.map{_.size}.max
    val rall = all map {_.reverse}
    val pow10 = Array.iterate(1, maxDigit)(_ * 10)
    
    def checkDigit(d: Int, dict: Map[Char, Int]): List[(Seq[Int], Int)] = {
      def verbalToNumeric(verbal: String) = 
        verbal.takeRight(d).foldLeft(0){10 * _ + dict(_)}
      
      val numBottom = verbalToNumeric(all.head)
      val numParts = all.tail.map(verbalToNumeric)

      if (d == maxDigit) List((numParts, numBottom)) filter {case (p, b) => p.sum == b}
      else if (numBottom != numParts.sum % pow10(d)) List()
      else {
        val alphas = rall flatMap {_.lift(d)} filterNot dict.isDefinedAt distinct
        val ret = for {
          cmb <- (digits diff dict.values.toSeq).combinations(alphas.size)
          prm <- cmb.permutations
          newPairs = alphas zip prm
          if newPairs forall {case (alp, num) => num != 0 || !nonZeroChars(alp)}
        } yield (checkDigit(d + 1, dict ++ newPairs))
        ret.toList.flatten
      }
    }
    checkDigit(0, Map.empty[Char, Int])
  }

verbal_arith_04.scala

  // performance tuning
  def solve4(bottom: String, parts: String*) = {
    val digits = 0 to 9
    val maxDigit = parts.map{_.size}.max max bottom.size
    val all = (bottom +: parts) map {_.reverse}
    val cnsTbl = Array.fill[Int](maxDigit)(0)

    def collectSorted = {
      val m = collection.mutable.Map.empty[Char, Int]
      var from = 0
      for (d <- 0 until maxDigit) {
        for (s <- all; c <- s lift d)
          if (!m.isDefinedAt(c)) {
            m(c) = from
            from += 1
          }
        cnsTbl(d) = from
      }
      m
    }
    
    val charToIndices = collectSorted
    val nBottom = bottom map charToIndices toArray
    val nParts = parts map {_ map charToIndices toArray} toArray
    val nonZeroIndices = nParts.map{_.head}.toSet + nBottom.head
    
    val ansTbl = Array.fill[Int](charToIndices.size)(-1)
    
    def checkDigit(d: Int): List[(Seq[Int], Int)] = {
      def toNum(indices: Array[Int]) =
        indices.takeRight(d).foldLeft(0){_ * 10 + ansTbl(_)}
      
      val nbottom = toNum(nBottom)
      val nparts = nParts map toNum
      
      (d, nbottom - nparts.sum) match {
        case (`maxDigit`, 0) => List((nparts, nbottom))
        case (`maxDigit`, _) => List()
        case (_, diff) if diff % math.pow(10, d).toInt != 0 => List()
        case (_, _) => {
          val ofs = cnsTbl lift d - 1 getOrElse 0
          val undet = digits diff (0 until ofs map ansTbl)
          val ndet = cnsTbl(d) - ofs
          val ret = for {
            cmb <- undet.combinations(ndet)
            prm <- cmb.permutations
            idxzero = prm.indexOf(0)
            if idxzero == -1 || !nonZeroIndices(ofs + idxzero)
          } yield {
            0 until ndet foreach {i => ansTbl(i + ofs) = prm(i)}
            checkDigit(d + 1)
          }
          ret.toList.flatten         
        }
      }
    }

    checkDigit(0)
  }

verbal_arith_05.scala

  // performance tuning ver.2
  def solve5(bottom: String, parts: String*) = {
    val digits = 0 to 9
    val maxDigit = parts.map{_.size}.max max bottom.size
    val all = (bottom +: parts) map {_.reverse}
    val cnsTbl = Array.fill[Int](maxDigit)(0)

    def collectSorted = {
      val m = collection.mutable.Map.empty[Char, Int]
      var from = 0
      for (d <- 0 until maxDigit) {
        for (s <- all; c <- s lift d)
          if (!m.isDefinedAt(c)) {
            m(c) = from
            from += 1
          }
        cnsTbl(d) = from
      }
      m
    }
    
    val charToIndices = collectSorted
    val nBottom = bottom map charToIndices toArray
    val nParts = parts map {_ map charToIndices toArray} toArray
    val nonZeroIndices = nParts.map{_.head}.toSet + nBottom.head
    
    val ansTbl = Array.fill[Int](charToIndices.size)(-1)
    
    def checkDigit(d: Int): List[(Seq[Int], Int)] = {

      def toNum(indices: Array[Int]) =
        indices.takeRight(d).foldLeft(0){_ * 10 + ansTbl(_)}
      
      val nbottom = toNum(nBottom)
      val nparts = nParts map toNum
      
      def myPerm(xs: Seq[Int], nrem: Int): Seq[List[Int]] =
        if (nrem == 0) Seq(Nil)
        else for(x <- xs; ys <- myPerm(xs filter {_ != x}, nrem - 1)) yield x :: ys
      
      def myPerm2(xs: Seq[Int], nrem: Int): Seq[List[Int]] = {
        def rec(xs: Seq[Int], nrem: Int, cur: List[Int]): Seq[List[Int]] =
          if (nrem == 0) List(cur)
          else xs flatMap{x => rec(xs filter {_ != x}, nrem - 1, x :: cur)}
        rec(xs, nrem, Nil)
      }
      
      (d, nbottom - nparts.sum) match {
        case (`maxDigit`, 0) => List((nparts, nbottom))
        case (`maxDigit`, _) => List()
        case (_, diff) if diff % math.pow(10, d).toInt != 0 => List()
        case (_, _) => {
          val ofs = cnsTbl lift d - 1 getOrElse 0
          val undet = digits diff (0 until ofs map ansTbl)
          val ndet = cnsTbl(d) - ofs
          val ret = for {
//            cmb <- undet.combinations(ndet)
//            prm <- cmb.permutations
            prm <- myPerm2(undet.view, ndet)
            idxzero = prm.indexOf(0)
            if idxzero == -1 || !nonZeroIndices(ofs + idxzero)
          } yield {
            0 until ndet foreach {i => ansTbl(i + ofs) = prm(i)}
            checkDigit(d + 1)
          }
          ret.toList.flatten         
        }
      }
    }