Big Bang

6 files changed, 239 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..30233e7
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+bin/
+files/
\ No newline at end of file
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..f138b07
--- /dev/null
+++ b/README.md
@@ -0,0 +1,12 @@
+### Markov Chains
+
+This is a simple implementation of markov chains
+
+### Build
+
+To build use
+``` ./build.sh ```
+to build and run use
+``` ./build.sh run ```
+
+See the build.sh file for more info
diff --git a/build.sh b/build.sh
new file mode 100755
index 0000000..988ee24
--- /dev/null
+++ b/build.sh
@@ -0,0 +1,39 @@
+#!/bin/sh
+
+cd ${0%/*} # go to project root
+
+FLAGS="-Wall -Wextra -g -pedantic"
+SRCD="src"
+BIN="bin"
+FILES="files"
+RUN=0
+
+function __run__ {
+    RUN=1
+}
+
+function __clean__ {
+    rm -rf $BIN
+    rm -rf  files
+    kill $( ps -q $$ -o pgid= ) # exit
+}
+
+set -xe
+
+if ! { [[ $# -eq 0 ]]; } 2> /dev/null
+then
+    __$1__
+fi
+
+
+mkdir -p $BIN
+mkdir -p $FILES
+
+gcc -o $BIN/main      $FLAGS $SRCD/main.c
+gcc -o $BIN/gen_chain $FLAGS $SRCD/gen_chain.c
+
+if ! { [[ $RUN -eq 0 ]]; } 2> /dev/null
+then
+    $BIN/gen_chain
+    $BIN/main
+fi
diff --git a/src/gen_chain.c b/src/gen_chain.c
new file mode 100644
index 0000000..636d3ea
--- /dev/null
+++ b/src/gen_chain.c
@@ -0,0 +1,32 @@
+#include <stdio.h>
+
+#define PRINT_ITEM_FREQUENCY
+// #define PRINT_ON_WALK
+#define SAVE_TO_FILE_ON_WALK "files/chain.txt"
+#define WALK_LEN 100000
+
+#define ITEM_CAP 3
+int ITEMS = 3;
+
+double chain[ITEM_CAP][ITEM_CAP] = {
+    { 0.2, 0.6, 0.2 },
+    { 0.3, 0.0, 0.7 },
+    { 0.5, 0.0, 0.5 }
+};
+
+char item_names[ITEM_CAP][64] = {
+    "burger",
+    "pizza",
+    "hotdog"
+};
+
+#include "markov.h"
+
+int main(void)
+{
+    srand(time(NULL));
+
+    print_chain();
+    take_walk();
+    return 0;
+}
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..e1a942e
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+
+#define PRINT_ITEM_FREQUENCY
+// #define PRINT_ON_WALK
+// #define SAVE_TO_FILE_ON_WALK "walk.txt"
+#define WALK_LEN 1000000
+
+#define ITEM_CAP 30
+int ITEMS = 0;
+
+double chain[ITEM_CAP][ITEM_CAP] = {0};
+char item_names[ITEM_CAP][64] = {0};
+
+#include "markov.h"
+
+int main(void)
+{
+    srand(time(NULL));
+    generate_chain("files/chain.txt");
+
+    print_chain();
+    take_walk();
+    return 0;
+}
diff --git a/src/markov.h b/src/markov.h
new file mode 100644
index 0000000..052af53
--- /dev/null
+++ b/src/markov.h
@@ -0,0 +1,130 @@
+#ifndef MARKOV_H
+#define MARKOV_H
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <time.h>
+
+extern int ITEMS;
+extern double chain[][ITEM_CAP];
+extern char item_names[][64];
+
+void generate_chain(char *file_path)
+{
+    FILE *fp = fopen(file_path, "r");
+    if(!fp) {
+        fprintf(stderr, "ERROR: Could not open file %s\n", file_path);
+        exit(EXIT_FAILURE);
+    }
+
+    int items_seen[ITEM_CAP][ITEM_CAP] = {0};
+    int cur_item = -1;
+
+    char line[256] = {0};
+    while((fgets(line, sizeof(line), fp)) != NULL)
+    {
+        if(line[strlen(line)-1] == '\n')
+            line[strlen(line)-1] = '\0';
+
+        int item = ITEMS;
+
+        for(int i = 0; i < ITEMS; i++)
+        {
+            if(strcmp(line, item_names[i]) == 0)
+                item = i;
+        }
+
+        if(item == ITEMS) {
+            ITEMS++;
+            strcpy(item_names[item], line);
+        }
+
+        if(cur_item != -1)
+            items_seen[cur_item][item]++;
+
+        cur_item = item;
+    }
+
+    fclose(fp);
+
+    for(int i = 0; i < ITEMS; i++)
+    {
+        int all = 0;
+        for(int j = 0; j < ITEMS; j++)
+            all += items_seen[i][j];
+
+        for(int j = 0; j < ITEMS; j++)
+            chain[i][j] = (double)items_seen[i][j]/all;
+    }
+}
+
+int walk_step(int item)
+{
+    int item_lim = 0;
+    int r = rand();
+
+    for(int i = 0; i < ITEMS; i++)
+    {
+        item_lim += RAND_MAX * chain[item][i];
+        if(r <= item_lim) return i;
+    }
+
+    return -1;
+}
+
+void take_walk()
+{
+#ifdef SAVE_TO_FILE_ON_WALK
+    FILE *fp = fopen(SAVE_TO_FILE_ON_WALK, "w");
+    if(!fp) {
+        fprintf(stderr, "ERROR: Could not open file %s\n", SAVE_TO_FILE_ON_WALK);
+        exit(EXIT_FAILURE);
+    }
+#endif
+
+    int items_seen[ITEM_CAP] = {0};
+    int cur_item = rand() % ITEMS;
+
+    for(size_t i = 0; i < WALK_LEN; i++)
+    {
+    #ifdef PRINT_ON_WALK
+        puts(item_names[cur_item]);
+    #endif
+    #ifdef SAVE_TO_FILE_ON_WALK
+        fprintf(fp, "%s\n", item_names[cur_item]);
+    #endif
+        items_seen[cur_item]++;
+        int ni = walk_step(cur_item);
+        assert(ni != -1);
+        cur_item = ni;
+    }
+
+#ifdef SAVE_TO_FILE_ON_WALK
+    fclose(fp);
+    printf("Saved file with %d items at %s\n", WALK_LEN, SAVE_TO_FILE_ON_WALK);
+#endif
+
+#ifdef PRINT_ITEM_FREQUENCY
+    puts("Item Frequency:");
+    for(int i = 0; i < ITEMS; i++)
+        printf("%f %s\n", (double)items_seen[i]/WALK_LEN, item_names[i]);
+    puts("");
+#endif
+}
+
+void print_chain()
+{
+    puts("Chain Matrix:");
+    for(int i = 0; i < ITEMS; i++)
+    {
+        printf("{");
+        for(int j = 0; j < ITEMS; j++)
+            printf(" %f,", chain[i][j]);
+        printf("}\n");
+    }
+    puts("");
+}
+
+#endif