# Binary search in Scala

Another exercise in Scala in which the goal is to find the target position as fast as possible. The initial input provides the grid size and the initial position. Each turn, this code provide a new position using println and the direction to the target is given back as a string ("UR" up-right, "DL" down-left, etc). The exercise does not require to end the infinite loop.

import math._
import scala.util._

object Player extends App {
def getDirection(input: String): (Int, Int) = {
input match {
case "U" => (0, -1)
case "UR" => (1, -1)
case "R" => (1, 0)
case "DR" => (1, 1)
case "D" => (0, 1)
case "DL" => (-1, 1)
case "L" => (-1, 0)
case "UL" => (-1, -1)
}
}

def findNewRelativePositionOnAxis(direction: Int, min : Int, max : Int, current : Int) : Int = {
direction match {
case 1 => (max - current + 1 ) / 2
case -1 => if(current == 1) -1 else (min - current - 1 ) / 2    //edge case for when the goal is at position 0
case _ => 0
}
}

def loop(x: Int, y: Int, minX: Int, minY: Int, maxX: Int, maxY: Int): Nothing = {

//Update min and max values to narrow down the search
val newMaxX = if(goaldir._1 == -1) x else maxX
val newMaxY = if(goaldir._2 == -1) y else maxY
val newMinX = if(goaldir._1 == 1) x else minX
val newMinY = if(goaldir._2 == 1) y else minY

//Compute the next position
val newX = x + findNewRelativePositionOnAxis(goaldir._1, newMinX, newMaxX, x)
val newY = y + findNewRelativePositionOnAxis(goaldir._2, newMinY, newMaxY, y)

//Send the result
println(newX + " " + newY)

loop(newX, newY, newMinX, newMinY, newMaxX, newMaxY)
}

// w: width of the building.
// h: height of the building.
val Array(width, height) = for(i <- readLine split " ") yield i.toInt
val Array(x0, y0) = for(i <- readLine split " ") yield i.toInt

loop(x0, y0, 0, 0, width, height)
}


Your code can be much improved by adding a few data structures:

case class Point(x: Int, y: Int)
case class Interval(min: Int, max: Int)
case class Dimensions(horizontal: Interval, vertical: Interval)
case class Direction(relX: Int, relY: Int)


Further you should start to introduce functions everywhere you have a comment now, for instance:

def updateSearchSpace(space: Dimensions, pos: Position, dir: Direction): Dimensions


Since this is a function that receives Dimensions and returns Dimensions as well, it is an ideal candidate to make it a method of the Dimensions class.

In order to simplify the method it is helpful to add a convenience method to Interval first:

case class Interval(min: Int, max: Int) {
def shrink(newBound: Int, dir: Int) = Interval(
min = if (dir == 1) newBound else min,
max = if (dir == -1) newBound else max
)
}


This allows you to shrink Dimensions pretty elegantly.

case class Dimensions(horizontal: Interval, vertical: Interval) {
def shrink(pos: Position, dir: Direction) = Dimensions(
horizontal.shrink(pos.x, dir.relX),
vertical.shrink(pos.y, dir.relY)
)
}


Your new data structures also give you much nicer signatures for your methods in general.

def loop(x: Int, y: Int, minX: Int, minY: Int, maxX: Int, maxY: Int): Nothing


becomes

def loop(pos: Position, searchSpace: Dimensions): Nothing


Your function findNewRelativePositionOnAxis(...) looks like it wants to be a member of Interval. I'll leave this one for you as an exercise ;-)