/* License: AGPLv3 or later. https://www.gnu.org/licenses/licenses.html
 * 
 * Exercise 9 - Dynamic Programming: Crazy Eights (Week 10)
 * Name: Manish
 * Student Login: *****
 * 
 * Compile as:
 * $ gcc -std=c11 -Wall -o ex9 ex9.c
 */

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

int max(int i, int j);

int main(void)
{
    printf("Enter file name: ");
    // Assuming filename/file path will not be longer than 256 characters
    char filename[257];
    scanf("%s", filename);

    FILE* file = fopen(filename, "r");
    if (!file)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }
    
    // 0th index is dummy card
    char cards[53][2];
    int size = 0;
    int length[53] = {0}; // all get initialized to 0;
    int parent[53] = {0}; // all get initialized to 0;
    int max_leaf = 0; // index of last card of longest chain
    
    // Dummy card as first card
    cards[size][0] = '8';
    cards[size++][1] = 'S';

    // Read and add cards
    while (fscanf(file, " %2c ", cards[size++]) != EOF)
    {
    }
    
    int current_length;
    int current_parent;
    for (int i=1; i < size; i++)
    {
        current_length = 1;
        current_parent = 0;
        for (int j = i-1; j >= 0; j--)
        {
            if (cards[i][0] == cards[j][0]
                || cards[i][1] == cards[j][1]
                || cards[i][0] == '8'
                || cards[j][0] == '8'
            )
            {
                if (current_length < length[j]+1)
                {
                    current_length = length[j]+1;
                    current_parent = j;
                }
            }
        }
        length[i] = current_length;
        parent[i] = current_parent;
        if (length[max_leaf] < current_length)
            max_leaf = i;
    }

    // find first card of longest chain
    int first = max_leaf;
    while (parent[first] != 0)
        first = parent[first];
    
    printf(
        "Longest sequence length: %d\n"
        "First card in longest sequence: %.2s\n"
        "Last card in longest sequence: %.2s\n",
        length[max_leaf],
        cards[first],
        cards[max_leaf]
          );
    
    fclose(file);

    return 0;
}