4
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ It does solve the problem yes. It is a rule to post working code here, if I remember correctly. \$\endgroup\$ – Stud Jul 12 '18 at 10:09
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Stud Jul 16 '18 at 12:46
  • \$\begingroup\$ @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. \$\endgroup\$ – janos Jul 16 '18 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.