puzzles exbm

gistfile1.scala

/* Given a list of numbers 0 to 10,000, return all those whose digits sum up to 20
 * Digits cannot repeat. Search space should be reduced.
 */

def get20s(): Seq[Seq[Int]] = {
  val ns = for {
    i <- 0 to 6
    j <- 1 to 7
    k <- 2 to 8
    if i + j + k == 11
  } yield i :: j :: k :: 9 :: Nil

  ns.flatMap(_.permutations)
}

/* Convert roman numerals to ints */
def roman2Int(s: String): Int = {
  val reg = "(IV)|(IX)|(XL)|(XC)|(CD)|(CM)|(V)|(X)|(L)|(C)|(D)|(M)|(I+)".r

  val romans = Map[String, Int](
    "IV" -> 4,
    "IX" -> 9,
    "XL"-> 40,
    "XC" -> 90,
    "CD" -> 400,
    "CM" -> 900,
    "I" -> 1,
    "II" -> 2,
    "III" -> 3,
    "V" -> 5,
    "X" -> 10,
    "L" -> 50,
    "C" -> 100,
    "D" -> 500,
    "M" -> 1000
  )

  val gs = reg.findAllIn(s).toList
  gs.foldLeft[Int](0){(acc, x) => romans(x) + acc}
}

/*
 * Given a list of numbers sort it in a way
 * so that odd numbers go to the left and even numbers to the right
 * Should be O(n) running time and O(1) memory (hence mutable list)
 */

  def oddSort(xs: mutable.MutableList[Int]): mutable.MutableList[Int] = {
    var idx = -1
    val n = xs.length - 1

    for(i <- 0 to n) {
      if(xs(i) % 2 == 0) {
        while(xs(n+idx) % 2 == 0) idx -= 1
        if (n+idx > i) {
          val tmp = xs(n+idx)
          xs(n+idx) = xs(i)
          xs(i) = tmp
        }
      }
    }

    xs
  }

  println(oddSort(mutable.MutableList(12, 1,2,3,4,5,6,7,8,9,10)))

 // MutableList(9, 1, 7, 3, 5, 4, 6, 2, 8, 12, 10)