Skip to content

Instantly share code, notes, and snippets.

@KevOrr
Last active April 18, 2016 03:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save KevOrr/59b2098214b4e17ff1fc48a14a692e05 to your computer and use it in GitHub Desktop.
Save KevOrr/59b2098214b4e17ff1fc48a14a692e05 to your computer and use it in GitHub Desktop.
Simulates zipfian behaviors among paperclips
// Simulates zipfian behaviors among paperclips
// Assumes that all paperclips can be selected with equal probability,
// regardless of the chain size each is in.
#include <stdio.h>
#include <stdlib.h>
struct clip {
int id;
struct clip *prev;
struct clip *next;
};
int connect2(struct clip *clips[], int n_clips, struct clip *chains[], int n_chains) {
// TODO make better random choice code (Try MT19937)
// http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html
struct clip *a = clips[(int)(rand() * n_clips / RAND_MAX)];
struct clip *b = clips[(int)(rand() * n_clips / RAND_MAX)];
// Find the end of a's chain and the beginning of b's
struct clip *a_end, *b_start;
for (a_end = a; a->next != NULL; a = a->next);
for (b_start = b; a->prev != NULL; b = b->prev);
// Connect the 2
a_end->next = b_start;
b_start->prev = a_end;
// Find b_start in chains[] and remove it
int i;
for (i = 0; i < n_chains && chains[i] != b_start; i++);
if (i >= n_chains) {
fputs("Could not find b_start in chains[]\n", stderr);
return -1;
}
chains[i] = NULL;
return 0;
}
void count(struct clip *chains[], int *chain_sizes, int n_chains) {
int i, size;
struct clip *p;
for (i = 0; i < n_chains; i++) {
// Count length of chain[i]
for (size = 0, p = chains[i]; p != NULL; size++, p = p->next);
chain_sizes[i] = size;
}
}
// Returns the actual (possibly new) number of chains
int sort_chains(struct clip *chains[], int n_chains) {
}
void dealloc(struct clip *clips[], int n) {
int i;
for (i=0; i<n; i++)
free(clips[i]);
}
void usage(char *name) {
printf("USAGE: %s [N [STEPS [INT]]]\n\n"
"Simulates zipfian behaviors among paperclips\n"
"N Number of paperclips (must be >= 3)\n"
"STEPS Number of steps before termination\n"
"INT Number of steps between each report\n", name);
}
int main(int argc, char *argv[]) {
int n_clips = 100;
int n_chains = 100;
int steps = 100;
int report_interval = 10;
// Command line options
if (argc > 1) {
if (!(n_clips = atoi(argv[1])) || n_clips < 3) {
usage(argv[0]);
return 1;
}
n_chains = n_clips;
}
if (argc > 2) {
if (!(steps = atoi(argv[2]))) {
usage(argv[0]);
return 1;
}
}
if (argc > 3) {
if (!(report_interval = atoi(argv[3]))) {
usage(argv[0]);
return 1;
}
}
struct clip *clips[n_clips];
struct clip *chains[n_chains];
int chain_sizes[n_chains];
// Create clips
int i;
for (i=0; i<n_clips; i++) {
// Store one clip in each chain
struct clip *new_clip = malloc(sizeof(struct clip));
if (new_clip == NULL) {
fputs("Failed to allocate memory. Download more gigs\n", stderr);
if (i)
dealloc(clips, n_clips);
return 1;
}
// Set members
new_clip->next = NULL;
new_clip->prev = NULL;
new_clip->id = i;
clips[i] = new_clip; // Add to clip array for deallocation later
chains[i] = new_clip; // Add to chains array for chain tracking
chain_sizes[i] = 1; // Each chain size is 1 (all clips are disconnected)
}
// Print initial summary
fputs("0 ", stdout); // Step number
for (i=0; i<n_chains - 1; i++)
printf("%4d ", chain_sizes[i]); // Chain sizes
printf("%4d\n", chain_sizes[n_chains - 1]);
// Main loop
for (i = 0; i < steps; i++) {
int ret = connect2(clips, n_clips, chains, n_chains);
if (ret < 0) {
fputs("Encountered some error in connect2()\n", stderr);
return 1;
}
// TODO print report
}
dealloc(clips, n_clips);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment