// Arup Guha
// 1/14/2014
// Example of a restricted drunkard's walk.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define NUMMOVES 1000000
#define NUMBARS 21
#define STARTBAR 10

int main() {

    int bars[NUMBARS];
    int i;

    // Set initial number of times each bar is visited.
    for (i=0; i<NUMBARS; i++)
        bars[i] = 0;
    bars[STARTBAR] = 1;
    int curPos = STARTBAR;

    // Stumble left or right!!!
    for (i=0; i<NUMMOVES; i++) {

        // Must move right.
        if (curPos == 0)
            curPos = 1;

        // Must move left.
        else if (curPos == NUMBARS-1)
            curPos = NUMBARS-2;

        // Randomly choose a bar to go to!
        else {
            int num = rand()%2;
            if (num == 0)
                curPos--;
            else
                curPos++;
        }

        // Update how many times we've visited this bar.
        bars[curPos]++;
    }

    // Print out a relative frequency chart.
    for (i=0; i<NUMBARS; i++) {
        printf("%d\t%lf\n", i, 1.0*bars[i]/NUMMOVES);
    }

    return 0;
}