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.