Wednesday, May 20, 2015

5 problems in an hour

@svpino posted a nice chalenge: solve 5 problems within an hour or denounce your title of software engineer.

It took me 40 minutes, of which 10 minutes was fighting around a limitation of the scala REPL.

Here are my solutions. They can all be pasted as is in the Scala REPL.

///////////////////////////////////////// // Problem 1 (Yuc! This is not a Scala problem!) def p1_for(xs: Seq[Int]): Int = { var s = 0; for (x <- xs) s += x; s } def p1_while(xs: Seq[Int]): Int = { var s = 0; var i = 0; while (i < xs.length) {s += xs(i); i+=1}; s } def p1_rec(xs: Seq[Int]): Int = if (xs.isEmpty) 0 else xs.head + p1_rec(xs.tail) def p1_proper(xs: Seq[Int]): Int = xs.foldLeft(0)(_+_) // :) scala> p1_for(Seq(1,2,3)) res0: Int = 6 scala> p1_while(Seq(1,2,3)) res1: Int = 6 scala> p1_rec(Seq(1,2,3)) res2: Int = 6 ///////////////////////////////////////// // Problem 2 def p2[A,B](a: Seq[A], b: Seq[B]): Seq[Any] = a.zip(b).flatMap { case (a,b) => Seq(a,b) } scala> p2(Seq("a","b","c"), Seq(1,2,3)) res3: Seq[Any] = List(a, 1, b, 2, c, 3) ///////////////////////////////////////// // Problem 3 def fibonaci: Iterator[Int] = Iterator.iterate((0,1)) { case (a,b) => (b, a+b) }.map(_._1) scala> fibonaci.take(100).mkString(", ") res79: String = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 55... ///////////////////////////////////////// // Problem 4 def p4(n: Seq[Int]): Int = n.map(_.toString).sorted.reverse.mkString("").toInt scala> p4(Seq(50,2,1,9)) res73: Int = 95021 ///////////////////////////////////////// // Problem 5 sealed trait Expr { def evaluate: Int def show: String } case class Plus(e1: Expr, e2: Expr) extends Expr { def evaluate: Int = e1.evaluate + e2.evaluate def show: String = e1.show + " + " + e2.show } case class Min(e1: Expr, e2: Expr) extends Expr { def evaluate: Int = e1.evaluate - e2.evaluate def show: String = e1.show + " - " + e2.show } case class Literal(v: Int) extends Expr { def evaluate: Int = v def show: String = v.toString } def appendToLastLiteral(e: Expr, append: Int): Expr = e match { case Plus(e1, e2) => Plus(e1, appendToLastLiteral(e2, append)) case Min(e1, e2) => Min(e1, appendToLastLiteral(e2, append)) case Literal(v) => Literal((v.toString + append.toString).toInt) } def loop(e: Expr, todo: Seq[Int]): Unit = { if (todo.isEmpty) { if (e.evaluate == 100) println(e.show) } else { loop(Plus(e, Literal(todo.head)), todo.tail) loop(Min(e, Literal(todo.head)), todo.tail) loop(appendToLastLiteral(e, todo.head), todo.tail) } } scala> loop(Literal(1), Seq(2, 3, 4, 5, 6, 7, 8, 9)) 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 1 + 2 + 34 - 5 + 67 - 8 + 9 1 + 23 - 4 + 5 + 6 + 78 - 9 1 + 23 - 4 + 56 + 7 + 8 + 9 12 + 3 + 4 + 5 - 6 - 7 + 89 12 + 3 - 4 + 5 + 67 + 8 + 9 12 - 3 - 4 + 5 - 6 + 7 + 89 123 + 4 - 5 + 67 - 89 123 + 45 - 67 + 8 - 9 123 - 4 - 5 - 6 - 7 + 8 - 9 123 - 45 - 67 + 89

Thanks @svpino, this was fun!