Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
puzzles exbm
/* 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