trjhtr

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.

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.