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

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 speed = speedInput * 1000f / 3600f //km/h to m/s
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.

• It does solve the problem yes. It is a rule to post working code here, if I remember correctly.
– Stud
Jul 12, 2018 at 10:09

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.

• Thank you for your answer, it does work nicely. I'm wondering, would it be better to have a function containing computeIdealSpeed to keep allLights in the scope? This way you don't pass allLights to computeIdealSpeed everytime, instead you just call initialComputeIdealSpeed when you want to start all over again, and initialComputeIdealSpeed would call computeIdealSpeed again with the full list. (I hope it is understandable, posting an example code in the comment doesn't work very well I think)
– Stud
Jul 16, 2018 at 12:46
• @Stud yes, you could have computeIdealSpeed(currentSpeed: Float, allLights: List[TrafficLight]) with two parameters, and in its scope it could define a function that does the heavy lifting. That would hide some complexity from the caller, and as such it would be better. Jul 16, 2018 at 19:28