Binary search in Scala

Question

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 = {
        val goaldir = getDirection(readLine)

        //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)
}

Answer 1

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 ;-)