Find an ideal speed to cross all traffic lights when they are green

Question

As a second exercise with Scala I tried to solve another puzzle. In this puzzle, we have to find the highest speed that allows a driver to cross all the traffic lights when they are green, without committing speeding. Each traffic light is defined by its distance from the start and its duration. All the lights start green, stay green during the given duration and then turn red for the given duration, etc.

Example of input:

50       //Max speed for this road
1        //Number of traffic lights on the road
200 15   //Distance and duration for the traffic light

My strategy is to start with the max speed and to try to reach as many traffic lights as possible. If I cross the road of a red light, I calculate the highest speed that allows me to reach it at the beginning of its next cycle (right when it turns green again), then I go back from the start with this new speed.

import math._
import scala.util._

object Solution extends App {

class TrafficLight(distance: Integer, duration: Integer) {

    val fullCycleDuration = 2*duration

    def getIdealSpeed(currentSpeed: Float) : Float = {
        //The number of seconds to go from start to this light 
        val timeToReachLight = distance.toFloat / currentSpeed
        //The number of seconds that passed since the light went green
        val timeOfArrivalInCycle = timeToReachLight % fullCycleDuration
        //If we reach the green light in time with this speed, leave it as it is
        if(timeOfArrivalInCycle < duration) {
            currentSpeed
        }
        else {
            //We need to slow down the speed to arrive when it is green again
            val newTravelTime = fullCycleDuration * (timeToReachLight.toInt / Math.round(fullCycleDuration.toInt) + 1)
            //New speed
            distance.toFloat / newTravelTime.toFloat
        }
    }
}

def parseTrafficLight(input: String): TrafficLight = {
    val fields = input.split(" ")
    new TrafficLight(fields(0).toInt, fields(1).toInt)
}    

def computeIdealSpeed(currentSpeed: Float, currentId : Integer, allLights: List[TrafficLight]): Float = {
    if(currentId >= lights.length) {
        currentSpeed
    }
    else {
        val newSpeed = lights(currentId).getIdealSpeed(currentSpeed)
        if(newSpeed == currentSpeed)
        {
            computeIdealSpeed(currentSpeed, currentId + 1, allLights)
        }
        else {
            computeIdealSpeed(newSpeed, 0, allLights)
        }
        /*newSpeed match {
            case currentSpeed => computeIdealSpeed(currentSpeed, currentId + 1, lights.tail)
            case _ => computeIdealSpeed(newSpeed, 0, allLights)
        }*/
    }
}

val speedInput = readInt
val speed = speedInput * 1000f / 3600f //km/h to m/s
val lightcount = readInt
var lights = (0 until lightcount).map(_ => parseTrafficLight(readLine)).toList

// Write an action using println
// To debug: Console.err.println("Debug messages...")
val idealSpeed = computeIdealSpeed(speed, 0, lights)

println(Math.round(idealSpeed * 3.6)) //m/s to km/h
}

The code above works correctly but I feel like it could be much better. For example, I wanted to use List.tail for the recursion, but I couldn't find how to get the whole list back when I needed to restart the recursion. This is why I used an id in the recursion. I'd love some suggestions on this part.

Answer 1

I wanted to use List.tail for the recursion, but I couldn't find how to get the whole list back when I needed to restart the recursion.

Easy! You can pass the whole list as an additional parameter.

My Scala is a bit rusty, but I think you can write like this using pattern matching:

def computeIdealSpeed(currentSpeed: Float, lights: List[TrafficLight], allLights: List[TrafficLight]): Float = {
    lights match {
        case light::tail => {
            val newSpeed = light.getIdealSpeed(currentSpeed)
            if (newSpeed != currentSpeed) {
                computeIdealSpeed(newSpeed, allLights, allLights)
            } else {
                computeIdealSpeed(newSpeed, tail, allLights)
            }
        }
        case nil => currentSpeed
    }
}

And then call the method with:

val idealSpeed = computeIdealSpeed(speed, lights, lights)

I'm not sure this is any better though. I would nitpick on the placement of braces and spacing around conditional statements, and the lack of indentation of the body of App.