The 538 Riddler: Traffic Jam

Hello reader(s)! Well, I’m 4-for-4 on the Riddlers so far and I’m having a lot of fun writing the code and talking about my approach, and also reading about the approaches that others have taken. I hope to keep doing this.

This week’s Riddler concerns my daily commute to work on most mornings, seemingly. Here it is:

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be Ngroups — no car ever gets stuck behind a slower car.

So my first approach to this was just to get some ballpark answers so I would know what kind of real answers to expect. I think a real mathematician would have taken a very different route to get to this answer, but I’m a programmer, so the first thing I did was write a Monte Carlo to just simulate what was happening on the road, man.

int TrafficJam(int carCount)
{
    int currentSpeed = 0;
    int packs = 0;
    int packSize = 0;

    for(int i = 0; i < carCount; i++)
    {
        int speed = 1 + rand();
        if((speed < currentSpeed) || (currentSpeed == 0))
        {
            if(packSize > 0)
            {
                //printf("%d cars in pack.\n", packSize);
            }
            packs++;
            currentSpeed = speed;
            //printf("New pack forming at %d, ", speed);
            packSize = 1;
        }
        else
        {
            packSize++;
        }
    }
    //printf("%d cars in pack.\n", packSize);
    //printf("With %d cars, %d packs formed.\n\n", carCount, packs);
    return packs;
}

void TrafficJamMC(int carCount)
{
    const int c_nTrials = 10000;
    int totalPacks = 0;
    for(int i = 0; i < c_nTrials; i++)
    {
        totalPacks += TrafficJam(carCount);
    }

    double avgPacks = (double)totalPacks / (double)c_nTrials;
    printf("After %d trials, average pack count with %d cars is %.3f or %.3fn\n"
        , c_nTrials, carCount, avgPacks, avgPacks / (double)carCount); 
}

 

Here’s the output for up to 25 cars:

After 10000 trials, average pack count with 1 cars is 1.000 or 1.000n
After 10000 trials, average pack count with 2 cars is 1.504 or 0.752n
After 10000 trials, average pack count with 3 cars is 1.826 or 0.609n
After 10000 trials, average pack count with 4 cars is 2.087 or 0.522n
After 10000 trials, average pack count with 5 cars is 2.302 or 0.460n
After 10000 trials, average pack count with 6 cars is 2.462 or 0.410n
After 10000 trials, average pack count with 7 cars is 2.572 or 0.367n
After 10000 trials, average pack count with 8 cars is 2.725 or 0.341n
After 10000 trials, average pack count with 9 cars is 2.824 or 0.314n
After 10000 trials, average pack count with 10 cars is 2.922 or 0.292n
After 10000 trials, average pack count with 11 cars is 3.016 or 0.274n
After 10000 trials, average pack count with 12 cars is 3.108 or 0.259n
After 10000 trials, average pack count with 13 cars is 3.170 or 0.244n
After 10000 trials, average pack count with 14 cars is 3.245 or 0.232n
After 10000 trials, average pack count with 15 cars is 3.314 or 0.221n
After 10000 trials, average pack count with 16 cars is 3.363 or 0.210n
After 10000 trials, average pack count with 17 cars is 3.436 or 0.202n
After 10000 trials, average pack count with 18 cars is 3.489 or 0.194n
After 10000 trials, average pack count with 19 cars is 3.522 or 0.185n
After 10000 trials, average pack count with 20 cars is 3.585 or 0.179n
After 10000 trials, average pack count with 21 cars is 3.643 or 0.173n
After 10000 trials, average pack count with 22 cars is 3.693 or 0.168n
After 10000 trials, average pack count with 23 cars is 3.732 or 0.162n
After 10000 trials, average pack count with 24 cars is 3.759 or 0.157n
After 10000 trials, average pack count with 25 cars is 3.816 or 0.153n

 

So this code works ok and gives us reasonable answers, but it has some obvious flaws. As with most Monte Carlos it will never give exact answers.

Also, simulating speeds might be fun, but it’s not really getting to the heart of the problem. What we really want to do is order all the cars and see how many jams would result. For any n number of cars we know that there are n-factorial variations of ordering.

For 2 cars, there are only 2 orders, for 3 cars there are 6 orders, and for 4 cars there are 24 different orders. They produce packs like this:

2 cars:
0 1 – 1 pack
1 0 – 2 packs

3/2 packs

3 cars:
0 1 2 – 1 pack
0 2 1 – 1 pack
1 0 2 – 2 packs
1 2 0 – 2 packs
2 0 1 – 2 packs
2 1 0 – 3 packs
—-
11/6 packs

4 cars:
0 1 2 3 – 1 pack
0 1 3 2 – 1 pack
0 2 1 3 – 1 pack
0 2 3 1 – 1 pack
0 3 1 2 – 1 pack
0 3 2 1 – 1 pack
1 0 2 3 – 2 packs
1 0 3 2 – 2 packs
1 2 0 3 – 2 packs
1 2 3 0 – 2 packs
1 3 0 2 – 2 packs
1 3 2 0 – 2 packs
2 0 1 3 – 2 packs
2 0 3 1 – 2 packs
2 1 0 3 – 3 packs
2 1 3 0 – 3 packs
2 3 0 1 – 2 packs
2 3 1 0 – 3 packs
3 0 1 2 – 2 packs
3 0 2 1 – 2 packs
3 1 0 2 – 3 packs
3 1 2 0 – 3 packs
3 2 0 1 – 3 packs
3 2 1 0 – 4 packs

50/24 packs

Let’s write some code to run through them all and count the jams. Yay, we get to use next_permutation, one of my favorite std algorithms. Here’s a function that will run through all permutations of n-factorial cars and tell you precisely how many jams you have:

#define MAX_CARS_FOR_PERMS 10
void TrafficJamPerm(int carCount)
{
    if(carCount > MAX_CARS_FOR_PERMS)
        return;

    int order[MAX_CARS_FOR_PERMS] = {};
    for(int i = 0; i < carCount; i++)
        order[i] = i;

    int totalPacks = 0;
    int perms = 0;
    do
    {
        int packs = 0;
        int currentSpeed = 0;
        for(int i = 0; i < carCount; i++)
        {
            if(i == 0 || order[i] < currentSpeed)
            {
                packs++;
                currentSpeed = order[i];
            }
        }
        totalPacks += packs;
        perms++;
    }
    while(next_permutation(order, order + carCount));
    
    printf("Using permutations, packs for %d cars = %d / %d = %.3f or %.3fn\n"
        , carCount, totalPacks, perms, (double)totalPacks / (double)perms, ((double)totalPacks / (double)perms) / (double)carCount);
}

 

And here’s the output:

Using permutations, packs for 1 cars = 1 / 1 = 1.000 or 1.000n
Using permutations, packs for 2 cars = 3 / 2 = 1.500 or 0.750n
Using permutations, packs for 3 cars = 11 / 6 = 1.833 or 0.611n
Using permutations, packs for 4 cars = 50 / 24 = 2.083 or 0.521n
Using permutations, packs for 5 cars = 274 / 120 = 2.283 or 0.457n
Using permutations, packs for 6 cars = 1764 / 720 = 2.450 or 0.408n
Using permutations, packs for 7 cars = 13068 / 5040 = 2.593 or 0.370n
Using permutations, packs for 8 cars = 109584 / 40320 = 2.718 or 0.340n
Using permutations, packs for 9 cars = 1026576 / 362880 = 2.829 or 0.314n
Using permutations, packs for 10 cars = 10628640 / 3628800 = 2.929 or 0.293n

 

Ok, cool, but do you see the problem? Yeah, this code only handles up to 10 cars and that’s because factorials get really big, really fast. The first 9 calls to this function return almost immediately but the 10th one starts to chug a little. A 32-bit integer could handle up to 12-factorial and 64 bits could get us to 20-factorial, but it doesn’t matter because we don’t have enough time to run through all those permutations. So this function works and is useful, but… it’s not great.

So there IS a math solution to this problem that doesn’t rely on Monte Carlos or permutations. I found it but I don’t know how to prove it. I’m not really a mathematician, I’m a programmer, so here’s my best explanation:

Average number of packs A(n) is equal to: Num(n) / Denom(n) where:
    Num(1) = 1, Denom(1) = 1.
    Num(n) = Num(n – 1) * n + Denom(n – 1).
    Denom(n) = Denom(n – 1) * n.  (this is n-factorial).

Okay, so I found that because I happened to see the pattern when I was looking at those numerators and denominators. I don’t really know why this is true. I can kind of work it out if I look at the lists of permutations between 2 cars and 3 cars and 4 cars, but I can’t really explain it well.

Anyway, here’s a function to calculate the average number of jams using math. I used a class called InfInt written by Sercan Tutar for this. This allows me to calculate factorials for very large numbers.

void TrafficJamMath(int carCount)
{
    InfInt num = 1;
    InfInt denom = 1;

    for(int i = 2; i <= carCount; i++)
    {
        num *= i;
        num += denom;
        denom *= i;
    }

    num *= 1000000;
    int l = (num / denom).toInt();

    double avg = (double)l / 1000000.0;
    double perN = avg / (double)carCount;

    printf("Using math, number of Traffic Jams for %d cars = %.3f or %.6fn\n", carCount
        , avg, perN); 
}

 

I ran this function to calculate the average traffic jams for 100, 1000, and 10000 cars.

Using math, number of Traffic Jams for 100 cars = 5.187 or 0.051874n
Using math, number of Traffic Jams for 1000 cars = 7.485 or 0.007485n
Using math, number of Traffic Jams for 10000 cars = 9.788 or 0.000979n

 

Let me just say that 10000-factorial is a very large number. It’s kind of interesting how we quickly get to 3 traffic jams with 10 cars, but with 10,000 cars we are still at only about 10 very large, frustrating jams. This explains Southern California freeways pretty well, actually.

Finally, crossing my fingers, but I think I found a pretty good solution for displaying source code in this blog. Special thanks to Alexander Kojevnikov for hilite.me. Here’s the complete source code for this post. You will need the InfInt class linked above.

Thanks for reading!

UPDATE: Alex Mahdavi points out that my really complicated equation can just be written as 1 + 1/2 + 1/3 + 1/4 + … + 1/n, also known as a Harmonic Series. Thanks Alex!

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

6 thoughts on “The 538 Riddler: Traffic Jam”

    1. You’re right! That’s a much better way of describing the problem. My answer is also correct and it’s kind of doing the same thing, just with more work and less clarity.

      In order to add 1 + 1/2 + 1/3 + 1/n you have to get all the fractions with the same denominator, and one way to do that is to multiply all the parts by 1/1 and 2/2 and 3/3 and n/n. Hence the factorials.

  1. Start adding cars slowest to fastest.

    For car k there are k places to place the new car, only one of which will add a new group: adding at the front. Otherwise you’re putting it behind a slower car and it will join that car’s group.

    So:

    Groups(n) = Groups(n – 1) * (n – 1)/n + (Groups(n -1) + 1)/n — the number of groups from before times the chance it isn’t at the fron, and one more than last time, times the chances it is at the front.

    This reduces to:

    Groups(n) = Groups(n-1) + 1/n, which is the harmonic series.

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s