#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream>
#include <exception>

using namespace std;

int primes[250] = {0};

struct dictNode {
 int n;
 char* str;
 float prob;

 dictNode* next;

 dictNode(int num, char *s, float p) {
  n = num;
  next = 0;
  strcpy(str, s);
  prob = p;
 }
}*f=0, *r = 0, *dn;


void set_primes() {
 int k = 0;
 for(int i = 2; i<=501; i++) {
  int prime = 1;

  for(int j = 2; j<=i/2; j++) {
   if(i%j == 0) {
    prime = 0;
    break;
   }
  }

  if(prime == 1)
   primes[k++] = i;
 }
}

bool inPrimes(int num) {
 for(int i = 0; primes[i]!=0; i++) {
  if(num == primes[i])
   return true;
 }
 return false;
}

void showDict() {
 dn = f;
 while(dn!=0) {
  printf("%d %s %f", dn->n, dn->str, dn->prob);
  dn = dn->next;
 }
}

void addToDict(int i, char *string, float p) {
 printf("%d \n\n", i);
 getch();
 try
    {
        dn = new dictNode(i, string, p);
        //printf("size: %x\n", &i);
    }
    catch(exception& e) //Takes a reference to an 'exception' object
    {
        cout << "Error allocating memory: " << e.what() << endl;
    }
 printf("here");
 if(f == 0 && r == 0) {
  f = r = dn;
  return;
 }
 r->next = dn;
 r = dn;
 printf("%d %s %f\n", r->n, r->str, r->prob);
 getch();
}

bool existsInDict(int i, char *string) {
 dn = f;
 while(dn!=0) {
  if(f->n == i && strcmpi(string, f->str)==0)
   return true;
 }
 return false;
}

float getProbFromDict(int i, char *string) {
 dn = f;
 while(dn!=0) {
  if(f->n == i && strcmpi(string, f->str)==0)
   return f->prob;
 }
}

float calc_prob(int i, char* string) {
    float prob = 1;
 if(existsInDict(i, string)) {
  return getProbFromDict(i, string);
 }
 char string_0 = string[0];
 if(i == 1) {
  prob = getProbFromDict(i,&string;_0)*calc_prob(i+1, string+1);
 } else if(i==500) {
  prob = getProbFromDict(i, &string;_0)*calc_prob(i-1, string+1);
 } else {
  prob = getProbFromDict(i, &string;_0)*(calc_prob(i+1, string+1)*(0.5) + calc_prob(i-1, string+1)*(0.5));
 }

 addToDict(i, string, prob);
 return prob;
}

int main() {
 set_primes();
 addToDict(5, "P", 1.0/2.0);
 addToDict(7, "N", 5.0/2.0);

 for(int i = 1; i<=501; i++) {
  if(inPrimes(i)) {
   addToDict(i, "P", 2.0/3.0);
   addToDict(i, "N", 1.0/3.0);
  } else {
   //addToDict(i, "P", 1.0/3.0);
   //addToDict(i, "N", 2.0/3.0);
  }
 }

 float result = 0.0;

 for(int i = 1; i<=501; i++) {
  char string[] = "PPPPNNPPPNPPNPN";
  result += calc_prob(i, string);
 }

 printf("The result is: %f", result/500);
 getch();
}