Puzzle question finding Calvin

Question

How to solve this problem. I have reckoned that I need to take as optimization problem finding minimum value for waiting time. Any suggestions?

Calvin has to cross several signals when he walks from his home to school. Each of these signals operate independently. They alternate every 80 seconds between green light and red light.At each signal, there is a counter display that tells him how long it will be before the current signal light changes. Calvin has a magic wand which lets him turn a signal from red to green instantaneously. However, this wand comes with limited battery life, so he can use it only for a specified number of times.

a. If the total number of signals is 2 and Calvin can use his magic wand only once, then what is the expected waiting time at the signals when Calvin optimally walks from his home to school?

b. What if the number of signals is 3 and Calvin can use his magic wand only once?

Answer 1

Solution to (a) and (b) and the general case can be found in this paper, together with code and a simulation to verify the results. I think it is instructive for those new to statistical modeling.

a. Expected trip time is 8.75 sec. Optimally, wand should be used on red light if the counter is above 20 sec.

b. Expected trip time is 21.32 sec. Optimal wand usage at first light is if the counter is above 31.25 sec, and 20 at the second if there is a charge left.

c. Consult the paper for the recursive 10-line code that solves the general case. For example, if there are 4 lights and Calvin has 2 charges, then the expected trip time is 11.8 sec with the optimal wand usage.

Answer 2

After further thought I think I have the right answer, at least for part a [2 signals; 1 wand]. The previous two answers above were on the right track of thinking but subtle nuances were missing.

So first you need to make some key assumptions:

1. Let's assume that Calvin can only see the signal that is coming up and not the next one. [Since the problem states that the signals are independent you want to structure the problem solving mechanism for that to hold true].

2. Calvin will be following some sort of optimal walking strategy.

3. When they say alternates between Red and Green every 80 seconds, I will assume 40 seconds on Red 40 seconds on green.

4. We have no idea about the synchronization or lag between the two signals.

**

I would suggest using an excel sheet to build a static simulation of all the possible signal combinations. You should have 4 columns. 1st column - counter for signal one, 2nd column colour of signal 1, 3rd and 4th columns, likewise, for signal 2.

i.e. 40R @ signal 1 and 1R @ signal ; 39R @ signal 1 and 1R @ signal 2; .... You should have 6400 combinations or rows in your sheet for each situation.

We will assume a uniform distribution, that is every situation has an equal likelihood of happening, due to our four assumptions. Thus the probability of Calvin being or starting his walk to land on any of those 6400 combinations is 1/6400 = 0.00015625

Note on assumptions: When modeling you always want to setup your model to make the least assumptions possible or the assumptions closest to reality.

Now we move on to the modeling part. Put yourself in Calvin's shoes. If you had to come up with the optimal walking strategy in 60 seconds without a computer, pen, paper or a calculator - how would you come up with a rough answer ? Let's call this first take at the walking strategy as a "Naive Optimal Approach".

As Calvin my thought process would be -

There are 4 combinations:

1. Red at the first signal; Red at the second signal
2. Red at the first signal; Green at the second signal
3. Green at the first signal; Red at the second signal
4. Green at the first signal; Green at the second signal

I need to make a decision to wave at the first signal [if i see Red], or if i should wait at the first signal and then wave at the second signal. Regardless of what is shown at the counter [this is important, because this is why we are calling this the naive approach. The counter is actually providing you with information that is relevant to come up with an approach. We will get to that in the later stage].

So let's do a very simple analysis of the two scenarios:

Scenario 1: I do not wait at signal 1, if i see Red [Wave wand at 1]

1. RR - Wait at R1 = 0; Wait at R2 = x --> Total Wait = x
2. RG - Wait at R1 = 0; Wait at G2 = 0 --> Total Wait = 0
3. GR - Wait at G1 = 0; Wait at R2 = 0 --> Total Wait = 0
4. GG - Wait at G1 = 0; Wait at G2 = 0 --> total Wait = 0

Scenario 2: I wait at signal 1, if I see Red [Wave wand at 2]

1. RR - Wait at R1 = x; Wait at R2 = 0 --> Total Wait = x
2. RG - Wait at R1 = x; Wait at G2 = 0 --> Total Wait = x
3. GR - Wait at G1 = 0; Wait at R2 = 0 --> Total Wait = 0
4. GG - Wait at G1 = 0; Wait at G2 = 0 --> total Wait = 0

So from our naive decision making technique we can see scenario 1 would be more effective since we don't add a wait at signal 1, for scenario "2", because we do not know what is ahead.

Now we stretch that thinking further, seems like the optimal strategy would be to wave at 1, if the counter for red is at, above, or below a number. This is where the ridiculous build of the 6400 combinations come in handy.

Code an if statement, first testing, if the signal at 1 is Red and counter at signal 1 displays 3 [Let's call 3 the 'thresh hold'. We picked an arbitrary start, you will see why]. I will wait. So you only add to your total wait time for if it is Red at signal 1 and the counter is 3, 2, or 1. The wait time at signal two won't be there because it will be green or you will wave your wand.

Now for the important part, nest another if statement where if Signal 1 is Red and the counter is 4, 5, 6,....,40. I will wave my wand at the first. Thus wait time at the first signal will be zero, but add the counter time if signal two is red, if it is green do not add the counter time. Make sure you code this logic right [sounds simple but it is trick; cross check manually 2 or 3 such combinations to see your formula/code is computing the final wait time right].

This is the most important part of the final logic for this. You need to go to the Red and signal 1 and green at signal 2 section. Here you will need to have a separate if statement which is as following. If Signal one is Red and counter is less than or equal to the 'threshold' [3] that you picked, then the wait time is whatever is displayed at the counter, if signal 1 is red and counter higher than the threshold then wait time is 0. Why is this important ?

**Because we are using the counter to make our decision. We are testing at each 'thresh hold' value, if we used that 'thresh hold' as our decision making/optimal walking approach, what would the total expected wait time be for the simulation of all 6400 possible combinations. To help you understand and see how the assumptions tie in. We don't know the synchronization of the signals. We decided if it's red on the first signal and 3 seconds or less on the counter, we would rather wait. To avoid say using the wand on the first and then landing on the second signal with a red and a counter that would most likely be higher than 3 seconds. Thus we actually increase our wait time.

However, that is a guess, because we don't know anything about the synchronization. It is also, just as likely, given it is a uniform distribution and all values have the same probability. That we wait when it's red at the first signal and displaying 3 on the counter, only to land on the second signal and find out it is green. Thus we never really got to use the wand. i.e. hypothetically if we knew the synchronization and we knew the next signal was green we would have used the wand at the first signal and the total wait time for those situations would be - 0 and not the 3, 1, or 1 second of wait as defined by the 'thresh hold'.

Once you are done doing this, multiple the total wait times by the 1/6400 probability and sum the entire array/column. This will be your E(x) when thresh hold is 3. Do this for all thresh holds 1, 2, 3, 4,...., 40. And plot the points. You should get a curve like this. The bottom of the curve is your optimal walking strategy. So from my graph it is 10 seconds. Even though I started with a hypothesis that 3 would be my optimal, turns out i should use 10 seconds as my thresh hold for my optimal walking strategy because when i use that, the E(x) for all 6400 situations is the lowest - 4.5312 seconds.