A Cruise Control Problem
Outline
Today, we’ll be exploring Aneo’s “Cruise Control” problem. The purpose of this piece is to use the process of solving this problem as an example for how to apply a combined set of skills of problem solving, analysis, and programming. Before we dive in, I want to make one thing clear: what I show is only one of many ways to think about this problem. So if you try this problem and realize your way is different from this way, that doesn’t imply you’re wrong. If your code passes the test cases, your equally as correct (and I would love to hear about your approach in the comments) !
Stating the problem
Initial Analysis and Breakdown of the Problem
Formulating the solution - (MATH Starts Here)
Refresher on Intervals
Programming the solution - (CODE Starts Here)
Pseudocode
Important Coding Details
Final Thoughts
Stating the Problem
Below is a screenshot of originally problem. Here is the link to the original page as well (if the link is still active when you click it, feel free to try it out!).
Introductory Analysis and Breakdown
Conceptual Preparation
Start with a process; they are great to streamline your focus on common stages of problem-solving, and conserve mental energy for the unique, problem-specific characteristics that will come. The process we’ll apply along the journey of the entire problem is:
Familiarize + AAQ
Before thinking about answers, make sure to understand the problem well. You should be able to paraphrase, or explain, it to others.
(List Assumptions) + AAQ
List out what things you’re allowed to assume are true. Get these verified through explicit details in the problem, or people with the authority to approve them. Anything you can’t get verified, I’d recommend you not consider an assumption.
(Make Observations) + AAQ
Deduce statements that you think are true and will help build a solution to the problem.
(Create And Test Solution) + AAQ
Create and test your solution to the problem.
(Repeat Some Combination Of 1-4 If Solution Fails) + AAQ
Don’t assume you’ll have a perfect solution the first go around. There may be things you’ve missed, or misunderstood, and that is completely okay. This reality is why it is crucial to have a feedback loop in the form of “testing the answer you’ve created.” This allows you to focus less on “what if this is wrong?” and more on “Is this the part that’s wrong” through iterative tweaks-and-tests to your solution.
AAQ = Ask/Answer Questions. Asking questions, and being resourceful to get answers to them, can become an invaluable part of the problem-solving journey. Some, or more, questions you will probably be the one to answer. If you’re in a collaborative setting, leverage the environment to get the answers.
So let’s move from concept to concrete!
Familiarize
If you’ve driven before, you’ve probably come to an area of 1, or more, lights, where you want pass them all without stopping. This problem puts thought to that idea by making you figure out what speed would you actually need to go to do that.
List Assumptions
The car is going one speed the entire time when in the traffic light area/zone - this is what cruise control means
Traffic lights are green and red only - there is no yellow, and that fact will probably reduce complexity of the problem.
All traffic lights turn green the moment your car enters the zone.
So far, we have 1 question:
(Q1): What exactly does “the second it turns red” mean?
It seems to imply there’s an instantaneous change between green and red (which wouldn’t be true in reality). Since I can’t verify this, I won’t assume it, and we’ll have to test this idea in the solution-creation phase.
Make Observations
The units of some input variables are not consistent (km/h, meters, seconds). This will likely lead to some dimensional analysis, or converting of units. We will have to watch closely to avoid failed solutions due to conversion errors.
There may not be a speed that will pass each light when its green the first time. When reading the problem closely, it technically never says you have to pass each light’s first green light So we can't assume we need to think like that.
Based on “2.” it may be helpful to map when each light is green or red using intervals of time. Since we are given duration-of-time for each light, the duration may be very helpful in doing that
This increases the significance of answer Q1, as these intervals’ boundaries will be dependent on that answer.
The rest of our observations will be developed as we dive more into the formulation.
Create and Test Solutions
We will discuss solution-creation and testing in below sections around Formulation. Solutions will be in the form of python code and tests will be in the form of test cases.
Formulating The Solution
Let’s first take stock of the bits of information we have, in the form of variables.
Variable Glossary
| # | Symbol | Definition | Unit |
|---|---|---|---|
| 1 | \(v_{\text{max}} \) | maximum speed limit | \( \left[\frac{\text{km}}{\text{hr}}\right] \) |
| 2 | \( x \) | The distance from zone's start to the light | \([m]\) |
| 3 | \( t_{D} \) | duration of time the light is green or red | \(\left[s \right] \) |
| 4 | \( t \) | duration of time to reach light starting at zone | \(\left[ \text{hr} \right] \) |
Please note the following details:
- Although we are only focusing on one light here, we can generalize what we are saying here to all lights as well.
- Inconsisent Units - We noticed that to units are not consistent across the variables we have. It will be crucial to make sure to convert everything to similar units before actually programming various calculations
- Example - Note that as we discuss these variables, we informally converted them, and then refer to, \(x = \frac{x}{1000} \) to ensure that \(x\) is in km.
The Solution
We will build our solution around the following question:
(Q2): What is the highest speed \(v \leq v_{\text{max}}\) we can go such that each light will be green when we pass it?
To answer Q2, we need to understanding the relationship between red/green lights and time. This leads to the following question:
(Q3): When are the lights red and green in terms of time?
Since \(t_D\) represents the amount of time a given light is red or green, we can describe the light's timeline. In the timeline, \(0\) represents the car entering the zone, which is equivalent to the point in time all lights turn green simultaneously (refer to Assumption # 3). The timeline looks something like this:
- From time \(t=0\) to maybe right before \( t_D \), the light is green
- From time \(t=t_D\) to maybe right before \( 2t_D \), the light is red
- From time \(t=2t_D\) to maybe right before \( 3t_D \), the light is green
- ... and so on ...
We keep stating "maybe right before" because of our initial question Q1 regarding the boundary points of time, and whether or not that instant is red or green. It leads us to a question that is a derivative of Q1:
(Q4): When time \(t=t_D\) does this exact moment represent a red or green light?
By answer Q4, we can derive the timeline properly. Unfortunately, since the problem itself doesn't make it clear which way to go with this, we are going to try a timeless strategy:
Guess and Test
Guess and Test just means that we will have to make an educated guess on what we think the answer to Q4 is, and then see if our guess will pass the test cases. This works because we have a way to immediate test if our guess works (test cases). If you don't have a way to get immediate feedback like this, you must be cautious when you start with a guess.
So my initial guessed answer to Q4 is:
(A4): When time \(t = t_D\) exactly, the light INSTANTANEOUSLY turns red
I am guessing that the "second it turns red" implies there exists 0 time between the moment it's green, and the moment it turns red (in reality this is not true, but I believe they are ignoring certain real subtleties for simplifcation's sake). Now we can formulate our timeline in terms of semi-closed intervals. Recall intervals have two types of boundary notation: Parentheses "( )" and Brackets "\( [ \text{ } ] \)":
Refresher on Intervals
- \( (a, b) \) means all numbers between \(a\) and \(b\) excluding \(a\) and \(b\). Mathematically if \(x \in (a,b) \rightarrow a < x < b \)
- \( [a, b] \) means all numbers between \(a\) and \(b\) including \(a\) and \(b\). Mathematically, if \(x \in [a,b] \rightarrow a \leq x \leq b \)
- \( [a, b) \) means all numbers between \(a\) and \(b\) including \(a\) and excluding \(b\). Mathematically, if \(x \in [a,b) \rightarrow a \leq x < b \)
Intervals and Patterns
We can update our guessed timeline intervals are in a cleaner fashion now:
- \( [0,t_D) \rightarrow \) green light
- \( [t_D,2t_D) \rightarrow \) red light
- \( [2t_D,3t_D) \rightarrow \) green light
- \( [3t_D,4t_D) \rightarrow \) red light
- ... and so on
Can you notice a pattern in the intervals? I see at least 2 - so you could create a solution based on either of them - but since I wish to focus on green lights, we'll be focusing on the pattern closely tied to green lights: All green-light intervals have an upper bound that is an odd multiple of \(t_D\), and red-light intervals have an upper bound that is an even multiple of \(t_D\). In other words, let \(k \in \{0,1,2,3,...\} \):
- \( \text{if } t \in [2kt_D, (2k+1)t_D) \rightarrow \text{ green light} \)
- \( \text{if } t \in \left[(2k+1)t_D, (2k+2)t_D \right) \rightarrow \text{ red light} \)
- If you'd prefer, the interval could have also been written as: \( \left[(2k+1)t_D, 2(k+1)t_D \right)\)
Our formulation leads to a crucial observation that will lead us into the next section: By having a formulaic timeline of when the light is red and green, we just need to make sure the car is a going a speed that always crosses a light during any of its green-sections. Let's elaborate!
Programming the Solution
In order to actualize our potential solution in the form of a computer program, a crucial first step to coding is psuedocoding
Psuedocode
Psuedocode is intended to be a code-agnostic description of what you’re code is expected to do; it will probably be a mix natural language statements and code-like statements. Ours looks like this:
- Start with the max speed \(v_\text{max} \)
- for each light in the scenario:
- get how long it takes to reach light, \(t \)
- if \(t\) is in a green-light interval, move on to next light in scenario
- if \(t\) is in red-light interval, set new max speed \(v_\text{max}' = v_\text{max}-1 \), and recheck each light's \(t\)
- return the highest speed where all the lights are crossed during green-light intervals.
Coding Details
The Full Code can be found HERE. Here is a screenshot, we are using python (but the actual puzzle allows for other coding languages to be used as well):
A few key notes to make. We consider them nuances of the coding itself that had to be accounted for:
- Line 18: Adding this became a crucial piece in this solution receiving a 100% score. Roundoff error was causing issues in results, so we had to truncate the long floating numbers.
- Lines 20 - 26: To actually test \( \text{if } t \in \left[(2k+1)t_D, (2k+2)t_D \right) \), there were several intermediate steps that had to be included in the computations. These subtleties exist around what happens if \(t\) sits on an red/green intervals' boundary points. There ends up being sub-conditions to test (such as if \(t\) is a whole, fractional, and/or a boundary point number) that combine to satisfy green conditions.
- In an effort to be clear upfront, the code above is focused more on readibility than code-length. So hopefully it makes sense, but if you have any questions or critiques, please comment below!
Final Thoughts
A few closing remarks:
Not The Only Solution
This is not the only solution to this problem. There are definitely other ways to approach this (and there are most likely some far cleverer than this solution). Don’t be discouraged if you don’t think you would arrive at this way of thinking. This post, and excursion, is to only help expose mathematical thinking and processes where you may want to try adopting them, or be inspired to try out your own process.
Reminders of the Process
Verify assumptions and requirements
Ask yourself questions to fill any possible holes you may have in understanding
Keep track of your observations and “answers.” They usually hold crucial details
Remember my guessed Answer (A4)? My original Answer was actually wrong based on a flawed observation. But I didn’t see the flaw in the observation until my solution failed several test cases (and then I proceeded to test my observations closely with the excel file "aneoPuzzleAnalysis.xlsx")
Develop an intuition or a conversational way of discussing the problem/solution before you jump into formulating the problem/solution in mathematical syntax
Other Reminders
Check this Code Repo if you want to see all the source code, test cases, and additional materials I created to solve the problem.
Dance. That is, dance between Summary and Detail. There is no magic formula, but there is a magical skill you can practice to get good at this: Having a Variable Perspective. This is analogous to controlling the zoom on a geographical map. This is about knowing how, and when, to focus on the bigger picture, and when you need to focus on specific details. Problems are finnicky little things, and their solutions will require info from a high-level and granular-level view of it.
Please Feel Free to comment below and discuss any of your thoughts or questions!
