ECE NTUA Computer Languages (Γλώσσες Προγραμματισμού) hopping Dynamic Programming Algorithm.

hopping.c

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

//Declare infinite limit for the DP array
//all the valid answers in the DP array are NUMBER % 1000000009 so smaller than this number
#define limit 1000000010

int N, K, B;
//Steps you can take
int *Steps;
//small size array for broken steps
int *Broken;
//DP array for storing the answer so far in a top down order
unsigned int *Apanthseis;

//Dynamic Programming logic we traverse each step and depending whether it is special ie. Broken, Out of Bounds or our Goal we procces it
//we try recursively to find the different ways to reach our goal and we memoize (store) the answers so far to avoid overlapping subproblems hell
unsigned int traverse(int step) {
	if (Broken[step]) {
		//if we reach a broken step we step back with no new way
		return 0;
	} else if (step > N) {
		//if we overstep our goal we step back with no new way
		return 0;
	} else if (step == N) {
		//if we find our goal we step back with plus one way
		return 1;
	} else {
		//else we solve recursively the problem or we use the DP array
		//if the DP array has infinite answer then we have not checked this step and we check again recursively 
		if (Apanthseis[step] == limit) {
			unsigned long int sum = 0;
			for (int i = 0; i < K; i++) {
				sum += traverse(step + Steps[i]);
				//fear the overflows
				sum %= 1000000009;
			}
			//memoize the answer
			Apanthseis[step] = sum;
			return sum;
		} else {
			//we have the answer for this step we dont need to check again so no overlapping subproblems
			return Apanthseis[step];
		}
	}
}

int main(int argc, char **argv) {
	//check if given input file
	if (argc < 2) {
		printf("Usage ./hopping <in>\n");
		exit(1);
	}
	//open input file as readonly (fails otherwise)
	FILE *fp;
	fp = fopen(argv[1], "r");
	if (fp == NULL) {
		printf("Null pointer did not open file successfully\n");
		exit(1);
	}
	//read N, K, B
	if (fscanf(fp, "%d %d %d\n",&N, &K, &B) < 1) {
		printf("Not a number\n");
		fclose(fp);
		exit(1);
	}
	//read the steps you can take
	Steps = malloc(sizeof(int) * K);
	for (int i = 0; i < K; i++) {
		if (fscanf(fp, "%d\n", &Steps[i]) < 1) {
			printf("Not a number\n");
			fclose(fp);
			exit(1);
		}
	}
	//initialize a value indexed array (pseudo-hash table) on 0 for broken steps
	Broken = malloc(sizeof(int) * N);
	for (int i = 1; i < N + 1; i++) {
		//0 means this step works fine
		Broken[i] = 0;
	}
	//update the broken steps hash table
	for (int i = 0; i < B; i++) {
		int brokenstep;
		if (fscanf(fp, "%d ", &brokenstep) < 1) {
			printf("Not a number \n");
			fclose(fp);
			exit(1);
		}
		//1 means this step doesnt work fine
		Broken[brokenstep] = 1;
	}
	//DP array initialization
	Apanthseis = malloc(sizeof(unsigned int) * N);
	for (int i = 1; i < N; i++) {
		//trying to gain some space :P
		if (!Broken[i])
			//infinite distance so far meaning not yet reached
			Apanthseis[i] = limit;
	}
	//to infinite and beyond
	//from step one to our goal
	printf("%d", traverse(1));
	fclose(fp);
	return 0;
}