//-std=c99 -Wall -Wextra -Wpedantic -Wshadow

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

static inline int largestOfThree(int a, int b, int c)
{
    if(a>b)
    {
        if(a>c) return a;
        else return c;
    }
    else if(b>c) return b;
    else return c;
}

int main()
{

    char str1[]="ACCGTGTCA";
    char str2[]="GCCGTGTCGACC";
    
    int match = 1;
    int mismatch = -1;
    int gap = -2;
    
    unsigned int lenStr1 = strlen(str1);
    unsigned int lenStr2 = strlen(str2);
    
    int tbl[lenStr2+1][lenStr1+1];
    
    unsigned int i,z;
    
    int scoreLeft, scoreUp, scoreDiagonal;
    
    
    //initialize the table
    
    tbl[0][0] = 0;
    
    for(i=1;i<lenStr1+1;++i)
    {
       tbl[0][i] = tbl[0][i-1] + gap; 
    }

    for(i=1;i<lenStr2+1;++i)
    {
       tbl[i][0] = tbl[i-1][0] + gap; 
    }
    
    //scores
    
    for(z=1;z<lenStr2+1;++z)
    {
        for(i=1;i<lenStr1+1;++i)
        {
            
            scoreLeft = tbl[z][i-1] + gap;
            scoreUp = tbl[z-1][i] + gap;
            
            if(str1[i-1]==str2[z-1])
                scoreDiagonal = tbl[z-1][i-1] + match;
            else
                scoreDiagonal = tbl[z-1][i-1] + mismatch;
            
            tbl[z][i] = largestOfThree(scoreLeft, scoreUp, scoreDiagonal);
            
        }
    }

//TEST:
//>>>>>>>>>> print table >>>>>>>>>>

    printf("\t\t");
    
    for(i=0;i<lenStr1;++i)
    {
        printf("%c\t",str1[i]);
    }
    
    printf("\n");

    for(z=0;z<lenStr2+1;++z)
    {
        if (!z) printf("\t");
        else printf("%c\t",str2[z-1]);

        for(i=0;i<lenStr1+1;++i)
        {
            printf("%d\t",tbl[z][i]); 
        }
        printf("\n"); 
    }

//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<


//TODO: find all paths

    
    return 0;
}
 
/*
output:

		A	C	C	G	T	G	T	C	A	
	0	-2	-4	-6	-8	-10	-12	-14	-16	-18	
G	-2	-1	-3	-5	-5	-7	-9	-11	-13	-15	
C	-4	-3	0	-2	-4	-6	-8	-10	-10	-12	
C	-6	-5	-2	1	-1	-3	-5	-7	-9	-11	
G	-8	-7	-4	-1	2	0	-2	-4	-6	-8	
T	-10	-9	-6	-3	0	3	1	-1	-3	-5	
G	-12	-11	-8	-5	-2	1	4	2	0	-2	
T	-14	-13	-10	-7	-4	-1	2	5	3	1	
C	-16	-15	-12	-9	-6	-3	0	3	6	4	
G	-18	-17	-14	-11	-8	-5	-2	1	4	5	
A	-20	-17	-16	-13	-10	-7	-4	-1	2	5	
C	-22	-19	-16	-15	-12	-9	-6	-3	0	3	
C	-24	-21	-18	-15	-14	-11	-8	-5	-2	1

*/