"Traffic Jam Riddler source code" - Views: 431 · Hits: 431 - Type: Unlisted

// TrafficJam.cpp : Defines the entry point for the console application.
// http://somedisagree.com/2016/02/06/the-538-riddler-traffic-jam/

#include "stdafx.h"
#include <algorithm>
#include "InfInt.h"

using namespace std;

#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);
}

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

    for(int i = 0; i < carCount; i++)
    {
        int speed = 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); 
}

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); 
}


int _tmain(int argc, _TCHAR* argv[])
{
    for(int carCount = 1; carCount <= 9; carCount++)
    {
        TrafficJamPerm(carCount);
    }
    for(int carCount = 1; carCount <= 10; carCount++)
    {
        TrafficJamMath(carCount);
    }

    TrafficJamMath(100);
    TrafficJamMath(1000);
    TrafficJamMath(10000);

    return 0;
}

/*

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
*/