Last active
August 29, 2015 14:22
-
-
Save yankov/f196236fe5691873901e to your computer and use it in GitHub Desktop.
puzzles exbm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment