c – Monte Carlo Simulation of Percolation is not Giving Expected Results

I’ve started working my way through the Princeton Algorithms course on Coursera. The course uses Java, but I decided to follow along with C as it is what I am most comfortable with. One of the assignments has you write a program to estimate the value of the percolation threshold via a Monte Carlo simulation (https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php.) I have written all the code, but my program’s output is not the same as the one on the site (it is not completely off, but still incorrect.) eg

Their implementation:

~/Desktop/percolation> java-algs4 PercolationStats 200 100
mean                    = 0.5929934999999997
stddev                  = 0.00876990421552567
95% confidence interval = [0.5912745987737567, 0.5947124012262428]

~/Desktop/percolation> java-algs4 PercolationStats 2 100000
mean                    = 0.6669475
stddev                  = 0.11775205263262094
95% confidence interval = [0.666217665216461, 0.6676773347835391]

Mine:

~/percolation> ./percolation_stats 200 100
mean                    = 0.628564
stddev                  = 0.206286
95% confidence interval = [0.588132, 0.668996]

~/percolation> ./percolation_stats 2 100000
mean                    = 0.728548
stddev                  = 0.189745
95% confidence interval = [0.727371, 0.729724]

Here is my code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "percolation.h"

double mean(double *, int);
double stddev(double *, int);
double confidencelo(double *, int);
double confidencehi(double *, int);

int main(int argc, char **argv) {
    int n, T, row, col;
    percolation *p;
    double *samp;

    srand((unsigned) time(NULL));
    sscanf(argv[1], "%d", &n);
    sscanf(argv[2], "%d", &T);
    samp = malloc(T * sizeof *samp);
    for (int i = 0; i < T; ++i) {
        p = creategrid(n);
        while (!percolates(p)) {
            do {
                row = rand() % n + 1;
                col = rand() % n + 1;
            } while (is_open(p, row, col));
            open(p, row, col);
        }
        samp[i] = (double) number_of_open_sites(p) / (n * n);
    }
    printf("mean                    = %gn", mean(samp, T));
    printf("stddev                  = %gn", stddev(samp, T));
    printf("95%% confidence interval = [%g, %g]n", confidencelo(samp, T),
           confidencehi(samp, T));
    return 0;
}

// mean: sample mean of percolation threshold
double mean(double *a, int len) {
    double sum = 0.0;

    for (int i = 0; i < len; ++i) {
        sum += a[i];
    }
    return sum / len;
}

// stddev: sample standard deviation of percolation threshold
double stddev(double *a, int len) {
    double mean(double *, int);
    double sum = 0.0;
    double avg = mean(a, len);

    for (int i = 0; i < len; ++i) {
        sum += (a[i] - avg) * (a[i] - avg);
    }
    return sqrt(sum / (len - 1));
}

// confidencelo: low endpoint of 95% confidence interval
double confidencelo(double *a, int len) {
    double mean(double *, int);
    double stddev(double *, int);

    return mean(a, len) - (1.96 * stddev(a, len)) / sqrt(len);
}

// confidencehi: high endpoint of 95% confidence interval
double confidencehi(double *a, int len) {
    double mean(double *, int);
    double stddev(double *, int);

    return mean(a, len) + (1.96 * stddev(a, len)) / sqrt(len);
}
#include <stdbool.h>

typedef struct percolation percolation;

percolation *creategrid(int);
void open(percolation *, int, int);
bool is_open(percolation *, int, int);
bool is_full(percolation *, int, int);
int number_of_open_sites(percolation *);
bool percolates(percolation *);
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "quick_union.h"

#define pos(p, x, y) (((x) - 1) * (p)->width + ((y) - 1))

typedef struct percolation {
    int width;
    int open_sites;
    UF *uf;
    bool *open;
} percolation;

// creategrid: creates n-by-n grid, with all sites initially blocked
percolation *creategrid(int n) {
    if (n <= 0) {
        fprintf(stderr, "open: illegal argumentn");
        exit(1);
    }
    percolation *p;

    p = malloc(sizeof *p);    
    p->width = n;
    p->open_sites = 0;
    p->uf = createuf(n * n + 2);
    p->open = malloc(n * n * sizeof *p->open);
    for (int i = 0; i < n * n; ++i) {
        p->open[i] = false;
    }
    for (int i = 0; i < n; ++i) {
        connect(p->uf, n * n, pos(p, 1, i));
        connect(p->uf, n * n + 1, pos(p, n, i));
    }
    return p;
}

// open: opens the site (row, col) if it is not open already
void open(percolation *p, int row, int col) {
    if (row < 1 || row > p->width || col < 1 || col > p->width) {
        fprintf(stderr, "open: illegal argumentn");
        exit(1);
    }
    if (p->open[pos(p, row, col)]) {
        return;
    }
    p->open[pos(p, row, col)] = true;
    ++p->open_sites;
    if (col > 1 && p->open[pos(p, row, col - 1)]) {
        connect(p->uf, pos(p, row, col), pos(p, row, col - 1));
    }
    if (col < p->width && p->open[pos(p, row, col + 1)]) {
        connect(p->uf, pos(p, row, col), pos(p, row, col + 1));
    }
    if (row > 1 && p->open[pos(p, row - 1, col)]) {
        connect(p->uf, pos(p, row, col), pos(p, row - 1, col));
    }
    if (row < p->width && p->open[pos(p, row + 1, col)]) {
        connect(p->uf, pos(p, row, col), pos(p, row + 1, col));
    }
}

// is_open: is the site (row, col) open?
bool is_open(percolation *p, int row, int col) {
    if (row < 1 || row > p->width || col < 1 || col > p->width) {
        fprintf(stderr, "is_open: illegal argumentn");
        exit(1);
    }
    return p->open[pos(p, row, col)];
}

// is_full: is the site (row, col) full?
bool is_full(percolation *p, int row, int col) {
    if (row < 1 || row > p->width || col < 1 || col > p->width) {
        fprintf(stderr, "is_full: illegal argumentn");
        exit(1);
    }
    return !p->open[pos(p, row, col)];
}

// number_of_open_sites: returns the number of open sites
int number_of_open_sites(percolation *p) {
    return p->open_sites;
}

// percolates: does the system percolate?
bool percolates(percolation *p) {
    return connected(p->uf, p->width * p->width, p->width + p->width + 1);
}
#include <stdbool.h>

typedef struct UF UF;

UF *createuf(int);
void connect(UF *, int, int);
bool connected(UF *, int, int);
int find(UF *, int);
#include <stdlib.h>
#include <stdbool.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))

typedef struct UF {
    int count;
    int *id;
    int *sz;
    int *largest;
} UF;

// createuf: return pointer to UF with n elements
UF *createuf(int n) {
    UF *uf;

    uf = malloc(sizeof *uf);
    uf->count = n;
    uf->id = malloc(n * sizeof *uf->id);
    uf->sz = malloc(n * sizeof *uf->sz);
    uf->largest = malloc(n * sizeof *uf->largest);
    for (int i = 0; i < n; ++i) {
        uf->id[i] = uf->largest[i] = i;
        uf->sz[i] = 1;
    }
    return uf;
}

// connect: connect elements p and q
void connect(UF *uf, int p, int q) {
    int root(UF *, int);
    int i = root(uf, p);
    int j = root(uf, q);

    if (i == j) {
        return;
    }
    if (uf->sz[i] <= uf->sz[j]) {
        uf->id[i] = j;
        uf->sz[j] += uf->sz[i];
        uf->largest[j] = max(uf->largest[i], uf->largest[j]);
    } else {
        uf->id[j] = i;
        uf->sz[i] += uf->sz[j];
        uf->largest[i] = max(uf->largest[j], uf->largest[i]);
    }
}

// connected: return true if elements p and q are connected
bool connected(UF *uf, int p, int q) {
    int root(UF *, int);

    return root(uf, p) == root(uf, q);
}

// find: return largest element in i's connected component
int find(UF *uf, int i) {
    int root(UF *, int);

    return uf->largest[root(uf, i)];
}

// root: return root element of i
int root(UF *uf, int i) {
    while (i != uf->id[i]) {
        uf->id[i] = uf->id[uf->id[i]];
        i = uf->id[i];
    }
    return i;
}

Where did I go wrong?

Leave a Comment