/*
 * I wrote parts of this when I was 17.  I wrote some of the rest
 * when I was in my 30's.  I'll let you decide which parts are which.
 * Tim Showalter, 2011
 */

/*

 *	The Monopoly Project
 *	"Reverse-Engineer" Probability Program v2
 *	Ported from 1992 RESA6 RAI version to ANSI-standard C
 *	Tim Showalter, 1994

 * goals of v4
 *
 * A long time ago, in a childhood far, far away, I wrote this.  I was 17, I
 * think.  It was okay but it was still, maybe, my first attempt to do
 * something useful in C.
 *
 * This code is derived from that program, with most of the stupider things
 * I thought were funny at the time removed, and the code is generally a little
 * better organized and simpler.
 *
 * This version cleans up some of the things that I've learned in the previous
 * 14 or so years.
 *
 * "v1" was a QBASIC program.
 * "v2" was the mp2.c file that had bugs.
 * "v3" was never useful, and is abandoned.
 * "v4" is this.
 *
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <sysexits.h>
#include <unistd.h>
#include <sys/time.h>

#define VERSION "v4.1"

typedef unsigned long long count_t;

static count_t total_rentable_hits;

#define HERE() (fprintf(stderr, "at %s:%d\n", __FILE__, __LINE__))

struct space_info {
    unsigned is_rentable : 1;
    const char *name;
};

static const unsigned NSPACES = 40;
static const struct space_info space_infos[] = {

    { 0, "Go", },
    { 1, "Mediterranean Avenue", },
    { 0, "Community Chest (1)", },
    { 1, "Baltic Avenue", },
    { 0, "Income Tax", },
    { 1, "Reading Railroad", },
    { 1, "Oriental Avenue", },
    { 0, "Chance (1)", },
    { 1, "Vermont Avenue", },
    { 1, "Connecticut Avenue", },
    { 0, "In Jail/Just Visiting", },
    { 1, "St. Charles Place", },
    { 1, "Electric Company", },
    { 1, "States Avenue", },
    { 1, "Virginia Avenue", },
    { 1, "Pennsylvania Railroad", },
    { 1, "St. James Place", },
    { 0, "Community Chest (2)", },
    { 1, "Tennessee Avenue", },
    { 1, "New York Avenue", },
    { 0, "Free Parking", },
    { 1, "Kentucky Avenue", },
    { 0, "Chance (2)", },
    { 1, "Indiana Avenue", },
    { 1, "Illinois Avenue", },
    { 1, "B. & O. Railroad", },
    { 1, "Atlantic Avenue", },
    { 1, "Ventnor Avenue", },
    { 1, "Water Works", },
    { 1, "Marvin Gardens", },
    { 0, "Go To Jail", },
    { 1, "Pacific Avenue", },
    { 1, "North Carolina Avenue", },
    { 0, "Community Chest (3)", },
    { 1, "Pennsylvania Avenue", },
    { 1, "Short Line", },
    { 0, "Chance (3)", },
    { 1, "Park Place", },
    { 0, "Luxury Tax", },
    { 1, "Boardwalk", },
};

struct sim_state {
    count_t space_hits[40];
    count_t total_chance;
    count_t total_chance_moves;
    count_t total_chest;
    count_t total_chest_moves;
    count_t total_moves;        /* total number of overall moves */
    count_t total_triple_doubles;
    unsigned position;
};

struct sim_setup {
    count_t inc;                /* increment between reports */
    count_t limit;              /* total iterations to do */
    int seed;                   /* for PNRG */
    
};

void init_sim_state(struct sim_state *st)
{
    memset(st, 0, sizeof(*st));
}

struct space_data {
    unsigned char number;       /* space number, index into sim_state array */
    count_t hits;
};

static int compare_space_data_by_hits(const struct space_data *pd1,
                                      const struct space_data *pd2)
{
    /* Do this the boring way, since anything cute could cause overflow */
    if (pd1->hits < pd2->hits) {
        return -1;
    } else if (pd1->hits > pd2->hits) {
        return 1;
    }
    return 0;
}

void print_space_data(struct space_data *branch, count_t total)
{
    /* ((double)(branch->score)/total)*100 ); */
    double percent_hit          = branch->hits * 100.0 / total;
    if (space_infos[branch->number].is_rentable) {
        double rentable_hit = branch->hits * 100.0 / total_rentable_hits;
        printf("%2d %30s   %llu\t%f%%\t%f%%\n",
               branch->number,
               space_infos[branch->number].name,
               branch->hits,
               percent_hit,
               rentable_hit);
    } else {
        printf("%2d %30s   %llu\t%f%%\t    \n",
               branch->number,
               space_infos[branch->number].name,
               branch->hits,
               percent_hit);
    }
}

int xrand(int limit)
{
    /* This doesn't quite do the right thing and throw away the extra numbers
     * between limit*(~0 % limit) and ~0.  Uh, that's in the noise, I guess.
     */
#if 0
    u_int32_t r32 = arc4random();
    return r32 % limit;
#else
    u_int32_t r = rand() % limit;
    return r;
#endif
}

static void usage(const char *av0) {
    fprintf(stderr,
            ("\
%s: compute Monopoly probabilities\n\
\n\
  usage:\n\
    -l LIMIT       set cap on number of moves; 0 is infinite (default)\n\
    -i INCREMENT   generate output after this many iterations (default 1000)\n\
    -s SEED        (broken) set random number seed\n\
    -r FILE        (broken) read state from file\n\
    -w FILE        (broken) write state to file\n\
\n\
  If running -l 0, killing this is the only way to stop it.\n\
\n\
  Monopoly is a trademark of Parker Brothers for its real-estate trading\n\
  game equipment.\n\
"
        ), 
            av0);

    exit(EX_USAGE);
}

count_t die_roll_counts[] = {0, 0, 0, 0, 0, 0};
inline int d6(void)
{
    int r = xrand(6);
    die_roll_counts[r]++;
    return r + 1;
}

/*
 * See if the die rolls are balanced.  This isn't nearly good enough.
 */ 
void analyze_die_frequency()
{
    int i;
    count_t lo_count = die_roll_counts[0];
    count_t hi_count = die_roll_counts[0];

    printf(" die roll analysis\n");
    
    for(i=1;i<6;i++)
    {
        if (die_roll_counts[i]>hi_count) hi_count = die_roll_counts[i];
        if (die_roll_counts[i]<lo_count) lo_count = die_roll_counts[i];
    }
    for(i=0;i<6;i++) {
        printf("\t roll %u =  %llu \t%f%% %f%%\n",
               i+1, die_roll_counts[i],
               (double)(hi_count-die_roll_counts[i])/die_roll_counts[i],
               (double)(die_roll_counts[i]-lo_count)/die_roll_counts[i] );
    }
}

int roll_to_get_out_of_jail = 0; /* try to get out of jail by rolling doubles */
int chance_deck_has_jailfree = 1; /* chance deck still has Get Out of Jail Free
                                     card */
int chest_deck_has_jailfree = 1; /* chest deck still has Get Out of Jail Free
                                    card */

static void move_forward(int shift_pos,
                  struct sim_state *st,
                  count_t *moves);

static void move_to(int new_pos,
                    struct sim_state *st,
                    count_t *moves)
{
    int card;

    st->position = new_pos;
    st->space_hits[new_pos]++;
    (*moves)++;

    switch (new_pos) {
    case 30:            /* go to jail */
        move_to(10, st, moves);
        return;
                
    case 7:             /* chance 1 */
    case 22:            /* chance 2 */
    case 36:            /* chance 3 */
        st->total_chance++;
        st->total_chance_moves++;
        card = xrand(16);

        switch (card) {
        case 0: move_to(24, st, moves); return; /* Illinos Ave */
        case 1: move_to(11, st, moves); return; /* St. Charles */
        case 2: move_to(10, st, moves); return; /* go to jail, go
                                                  directly to jail, do
                                                  not pass go, do not
                                                  collect $200 */
        case 3: move_to( 5, st, moves); return; /* take a ride on the Reading */
        case 4: move_to(39, st, moves); return; /* adv to Boardwalk */
        case 5: move_to( 0, st, moves); return; /* adv to Go */
        case 6:                                 /* next utility */
            move_to((st->position == 22) ? 13 : 29, st, moves);
            return;
        case 7:                 /* next railroad */
        case 8:                 /* next railroad duplicate */
            switch (st->position) {
            case 7:  move_to(15, st, moves); return;
            case 22: move_to(25, st, moves); return; 
            case 36: move_to( 5, st, moves); return;
            default:
                abort();        /* can't happen */
            }
        case 9:                 /* go back 3 spaces */
            move_forward(-3, st, moves);
            return;
            
        default:                /* 10..15 */
            /* no movement -- pay property tax, second prize in a beauty
             * contest, etc.
             */
            st->total_chance_moves--;
            return;
        }

    case 2:             /* CC on side 0 */
    case 17:            /* CC on side 1 */
    case 33:            /* CC on side 3 */
        /* community chest, which can be called from 2 places */
        card = xrand(16);
        st->total_chest++;
        st->total_chest_moves++;
        switch (card) {
        case 0:	move_to(10, st, moves); return; /* go to jail */
        case 1:	move_to( 0, st, moves); return; /* advance to go */
        default:
            /* no move */
            st->total_chest_moves--;
            return;
        }

    default:            /* space other than chance, cc, go-to-jail */
        /* no special handling */
        break;
    }
}

static void move_forward(int shift_pos,
                  struct sim_state *st,
                  count_t *moves)
{
    int new_pos = (st->position + shift_pos) % NSPACES;
    move_to(new_pos, st, moves);
}


static void print_report(const struct sim_state *const st,
                         const struct sim_setup *const setup)
{
    int i;
    count_t total_space_hits = 0; /* double-check */
    struct space_data properties[40];
    
    printf("\nTHE MONOPOLY PROJECT, program %s\n\n", VERSION);
    total_rentable_hits = 0;
    for (i = 0; i < NSPACES; i++) {
        properties[i].number = i;
        properties[i].hits = st->space_hits[i];
        if (space_infos[i].is_rentable) {
            total_rentable_hits += st->space_hits[i];
        }
    }
    qsort(properties, NSPACES, sizeof(struct space_data),
          (int (*)(const void*,const void*))compare_space_data_by_hits);

    printf("\
 #           name of space           hits      %% total hits  %% rentable hits\
\n"
        );
    for (i = NSPACES; --i >= 0; ) {
        print_space_data(&properties[i], st->total_moves);
        total_space_hits += st->space_hits[i];
    }

    printf("\n");
    printf("Totals                             %llu\n",
           total_space_hits);
    /*123456789012345678901234567890123456789012*/
    printf("\n");
    printf("\ttotal iterations completed       =  %llu\n", st->total_moves);
    printf("\tincriment between displays       =  %llu\n", setup->inc);
    // printf("\tactual iterations this incriment =  %llu\n", moves);
    // printf("\textra iterations this incriment  =  %llu\n", moves-inc);
    printf("\ttotal chance  cards              =  %llu\n", st->total_chance);
    printf("\ttotal chance  card  moves        =  %llu\n", st->total_chance_moves);
    printf("\ttotal chest   cards              =  %llu\n", st->total_chest);
    printf("\ttotal chest   card  moves        =  %llu\n", st->total_chest_moves);
    printf("\ttotal triple doubles             =  %llu\n", st->total_triple_doubles);
    printf("\n");

    analyze_die_frequency();
    printf("\n");

    if (setup->limit != 0)
    {
        count_t total_iterations = ceil((double)(setup->limit)/setup->inc)*setup->inc;
        double remaining_incs = (double)(setup->limit - st->total_moves) / setup->inc;
        printf("\ttotal iterations to be completed =  %llu\n", setup->limit);
        printf("\titerations before complete       =  %llu\n", setup->limit - st->total_moves);
        printf("\tincriment between displays       =  %llu\n", setup->inc);
        printf("\n\tremaining increments             =  %f\n", remaining_incs);
        printf("\t                                 => %llu\n", (count_t)ceil(remaining_incs));
        printf("\tremaining iterations             =  %f\n",   remaining_incs * setup->inc);
        printf("\t                                 => %llu\n", (count_t)ceil(remaining_incs) * setup->inc);
        printf("\ttrue total iterations            =  %llu\n", total_iterations);
        printf("\textra iterations                 =  %llu\n", total_iterations - setup->limit);
    }
    else
    {
        printf("\ttotal iterations to be completed =  infinite\n");
        printf("\t--  (invalidates  iterative information)  --\n");
    }
    printf("\tseed                             =  %d\n", setup->seed);

    printf("roll doubles to get out of jail?  %s\n",
           roll_to_get_out_of_jail ? "yes" : "no");

    printf("\n");
    fflush(stdout);
}

int main(int argc, char *argv[])
{
    struct sim_state st;
    struct sim_setup setup;

    unsigned doubles = 0;       /* consecutive doubles counter */

    setup.inc = 100;            /* iterations between prints */
    setup.limit = 10000;        /* iterations before ending */
    setup.seed = 0;

    init_sim_state(&st);
    
    printf("\n\nTHE MONOPOLY PROJECT, program %s\n",VERSION);
    printf("Tim Showalter, 1994, 2008, 2009; public domain.\n\n");

    /* handle arguments */

    {
        int ch;
        char *rest;
        while (-1 != (ch = getopt(argc, argv, "hl:i:s:dD"))) {

            switch(ch) {

            case 'D':
                roll_to_get_out_of_jail = 0;
                break;

            case 'd':
                fprintf(stderr, "roll to get out of jail not implemented\n");
                roll_to_get_out_of_jail = 1;
                break;
                
            case 'h':
                usage(argv[0]);
                exit(EX_USAGE);

            case 'l':
                setup.limit = strtoul(optarg, &rest, 10);
                if (rest == optarg) {
                    fprintf(stderr, "error parsing argument -l\n");
                    exit(EX_USAGE);
                }
                break;

            case 'i':
                setup.inc = strtoul(optarg, &rest, 10);
                if (rest == optarg) {
                    fprintf(stderr, "error parsing argument -i\n");
                    exit(EX_USAGE);
                }
                break;

            case 's':
                setup.seed = strtoul(optarg, &rest, 10);
                if (rest == optarg) {
                    fprintf(stderr, "error parsing argument -s\n");
                    exit(EX_USAGE);
                }
                break;

            default:
                fprintf(stderr, "%s: unrecognized switch %c; use -h for help\n",
                        argv[0], ch);
                exit(EX_USAGE);
            }
        }
    }

    /* seed PRNG */

    if (setup.seed == 0) {
        struct timeval tv;
        pid_t pid = getpid();
        if (gettimeofday(&tv, 0) < 0) {
            fprintf(stderr, "gettimeofday failed; get a real computer\n");
            exit(EX_OSERR);
        }
        /* it would be nice to use /dev/random here... but it's not fast
           enough.  This should be pretty arbitrary across extra runs. */
        setup.seed = (tv.tv_sec ^ tv.tv_usec ^ tv.tv_usec << 16
                      ^ (tv.tv_usec >> 16) ^ (tv.tv_sec << 4)
                      ^ pid ^ (pid << 4) ^ (pid << 13));
    }
    srand (setup.seed);

    /*
     * Main loop.
     */ 

    /* forever if limit==0, otherwise until total>=limit. */
    while (setup.limit == 0 || st.total_moves < setup.limit) {

        count_t moves = 0;      /* iterations between display */

        /* inner movement loop */
        
        while (moves < setup.inc) {
            unsigned die[2];
            
            die[0] = d6();
            die[1] = d6();

            if (die[0]==die[1]) doubles++;
            else doubles=0;

            if (doubles == 3) {
                // three doubles in a row, go to jail
                doubles = 0;
                st.total_triple_doubles++;
                move_to(10, &st, &moves);
                continue;
            }

            move_forward(die[0] + die[1], &st, &moves);
        }

        st.total_moves += moves;

        print_report(&st, &setup);
    }

    return 0;
}