IvanoBulo
BAN USERFP implementation in Scala. It is lazily evaluated so it should consume very little memory.
1. transform tree into rows (BFS)
2. generate sequence for traversal and map to rows
case class BTree[+T](left: Option[BTree[T]], right: Option[BTree[T]], value: T)
object SpiralTraversal {
def traverse[T](tree: BTree[T]): Iterator[T] = {
type BT = BTree[T]
def visit(nodes: Stream[BT]): (Stream[T], Stream[BT]) = {
nodes.foldLeft((Stream.empty[T], Stream.empty[BT])) {
case ((outT, outRow), node) =>
val nextRow = Stream(node.left, node.right).flatMap {
case Some(subtree) => Stream(subtree)
case _ => Stream.empty
}
(outT ++ Stream(node.value), outRow ++ nextRow)
}
}
def makeRows(trees: Stream[BT]): List[Stream[T]] = {
if (trees.isEmpty) {
return List.empty
}
val (rowT, nextRow) = visit(trees)
List(rowT) ++ makeRows(nextRow)
}
def comb(n: Int, m: Int): Stream[(Int, Boolean)] =
if (n > m) {
Stream.empty
} else if (n == m) {
Stream((n, false))
} else {
(n, false) #::(m, true) #:: comb(n + 1, m - 1)
}
val rows = makeRows(Stream(tree))
comb(0, rows.size - 1).flatMap {
case (rowNumber, reversed) =>
val row = rows(rowNumber)
if (reversed) row.reverse else row
}.iterator
}
}
As some mentioned above the recursive solution is the most efficient. Here is my solution in Scala. Wrote it in 'gedit' :)
def add(a: List[Int], b: List[Int]): List[Int] = {
def addint(pos:Int, carry: Int, a: List[Int], b: List[Int], acc: List[Int]): List[Int] = pos match {
case i if (i > -1) =>
val sum = a(pos) + b(pos) + carry
addint(pos - 1, sum / 10, a, b, sum % 10 :: acc)
case _ =>
acc
}
addint(a.size - 1, 0, a, b, Nil)
}
To try it paste it to Scala REPL and run:
scala> add(List(1,5), List(2,7))
Look at the perspective that the cost of moving a group of people is a (distanceX+distanceY)*amount. So we need to calculate the minimal cost moving by X and then by Y axis.
public static class Location {
public int x;
public int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
public static class MeetingLocation extends Location {
public int amountOfPeople;
public MeetingLocation(int x, int y, int amountOfPeople) {
super(x, y);
this.amountOfPeople = amountOfPeople;
}
}
public static Location moveLowestCost(int n, int m, MeetingLocation... meetingLocations) {
Location newLocation = new Location(0, 0);
int minCostX = Integer.MAX_VALUE, minCostY = Integer.MAX_VALUE;
for (int x = 0; x < m; x++) {
int costX = 0;
for (MeetingLocation location : meetingLocations) {
costX += location.amountOfPeople * calculateAbsDistance(x, location.x);
}
if (minCostX > costX) {
minCostX = costX;
newLocation.x = x;
}
}
for (int y = 0; y < n; y++) {
int costY = 0;
for (MeetingLocation location : meetingLocations) {
costY += location.amountOfPeople * calculateAbsDistance(y, location.y);
}
if (minCostY > costY) {
minCostY = costY;
newLocation.y = y;
}
}
return newLocation;
}
public static int calculateAbsDistance(int x, int x1) {
if (x >= x1) {
return x - x1;
} else {
return x1 - x;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
final Location newLoc = moveLowestCost(3, 4, new MeetingLocation(0, 1, 4), new MeetingLocation(1, 3, 3), new MeetingLocation(2, 0, 5));
System.out.println("X = " + newLoc.x + "; Y = " + newLoc.y);
}
Scala version. Returns SearchResult with tree node and sum of its direct child values. Because it is binary tree there is no need to search on the left if the right node is present.
case class Tree[+T](value:T, left:Option[Tree[T]], right:Option[Tree[T]])
case class SearchResult(t:Tree[Int], sum:Int)
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None => 0
case Some(t)=>t.value
}
def findNodeWithBiggestSum(t:Option[Tree[Int]]):Option[SearchResult] = {
def _compare(t1:Option[SearchResult], t2:Option[SearchResult]):Option[SearchResult] = {
if (t1.isEmpty) return t2
if (t2.isEmpty) return t1
//Both not empty
if (t1.get.sum > t2.get.sum) t1 else t2
}
def _computeResult(t:Option[Tree[Int]]):Option[SearchResult] = t match {
case None=>None
case Some(tree)=>
val leftValue = zeroIfNone(tree.left)
val rightValue = zeroIfNone(tree.right)
Some(SearchResult(tree, leftValue + rightValue))
}
def _find(t:Option[Tree[Int]], soFar:Option[SearchResult]):Option[SearchResult] = t match {
case None=>soFar
case Some(t)=> t.right match {
case None => _compare(_computeResult(Some(t)), _find(t.left, soFar))
case Some(rightTree)=>
_compare(_computeResult(Some(t)), _find(t.right, soFar))
}
}
_find(t, None)
}
Scala version
def printSpecial(s:String)= {
val charRange = ('a' to 'z') ++ ('A' to 'Z')
val numberRange = ('0' to '9')
def _group(todo:List[Char], chars:List[Char], specialChars:List[Char], sum:Int, fOnFinish:(List[Char], List[Char], Int)=>Unit):Unit = {
todo match {
case head::tail=>
if (charRange contains head) {
_group(tail, chars :+ head, specialChars, sum, fOnFinish)
} else if (numberRange contains head) {
_group(tail, chars, specialChars, sum + head.asDigit, fOnFinish)
} else {
_group(tail, chars, specialChars :+ head, sum, fOnFinish)
}
case _ => fOnFinish(chars,specialChars,sum)
}
}
_group(s.toList, Nil, Nil, 0, (chars, special, sum) => {
print(chars.sortBy(_.asDigit).foldLeft("")(_+_))
print(sum)
println(special.foldLeft("")(_+_))
})
}
Here is my solution using Scala. Time complexity around N*logN.
def find(m:Array[Array[Int]]):Option[Array[Int]] = {
def _find(m:Array[Array[Int]], range:(Int, Int) ):Option[Array[Int]] = {
if (range._1 >= m.size) return None //out of the border
val median = if (range._1 == range._2) {
range._1 //range reduced to one column
} else {
range._1 + ((range._2 - range._1) / 2) //find the range median
}
val rows:Array[Array[Int]] = m.filter {(row)=>row(median) == 0} //locate rows with '0' at median position
rows.size match {
case notFound if (notFound == 0) => _find(m, (median+1, range._2)) //try the right side
case one if (one == 1)=> Some(rows(0)) //found it!
case _ =>
if (median == 0) return Some(rows(0)) //first column
_find(m, (range._1, median-1)) //more to explore on the left side
}
}
_find(m, (0, m.size))
}
It also handles situation when no rows with zero's. And even when all of them are zeroes :)
- IvanoBulo February 29, 2012I have also end up with same solution using Scala
case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None=>0
case Some(t)=>t.value
}
def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
case None => None
case Some(t) => {
val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
Some(Tree(newValue, sum(t.left), sum(t.right)))
}
}
I have also end up with same solution using Scala
case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None=>0
case Some(t)=>t.value
}
def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
case None => None
case Some(t) => {
val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
Some(Tree(newValue, sum(t.left), sum(t.right)))
}
}
Highly inefficient. Time complexity is O(h^2 * w) (h - tree height, w - tree width).
- IvanoBulo December 12, 2015