//This is a maze solver coded in C which will print you the solution in a text file. input is first line <no. of mazes>, second line <no. of paths>, <no. of edges>, third line is <edge #1>, <connected to edge #2>, <cost>. NO COMMAS
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
struct node{
        int path1;
        int path2;
        int cost;
        };

int neighbor( int x, int node, struct node paths[]);
void cleanfgets(char input[]);
int deadend(int badnodes[],int neighbors[], int node, int prevnode,int badcount);
int badneighbor(int badnodes[],int neighbors[],int node, int prevnode, int badcount,int x);
int getcost(int nodepaths[],struct node paths[],int totaledges);

int getcost(int nodepaths[],struct node paths[],int totaledges) //insert the path here and it gives back the cost
{
int x=0;
int y=0;
int cost=0;
while( nodepaths[x] != totaledges)
{
    y=0;
    while(1)
    {
    if( (nodepaths[x]==paths[y].path1 || nodepaths[x]==paths[y].path2) && (nodepaths[x+1]==paths[y].path1 || nodepaths[x+1]==paths[y].path2) )
        break;
    y++;
    }       //find the cost of path A to B by first finding where A to B is in struct paths[]
    cost+=paths[y].cost;
x++;
}
return cost;
}



int badneighbor(int badnodes[],int neighbors[],int node, int prevnode, int badcount,int x)
{
int y=0;                //bad neighbor prevents us from hopping to a node that's already bad/done or already traversed
while(y<badcount)
    {
        if(neighbors[x]==badnodes[y])
            return 1;
        y++;
    }

    if (neighbors[x]==prevnode)
        return 1;

return 0;
}


int deadend(int badnodes[],int neighbors[], int node, int prevnode,int badcount)
{
    int x=0;
    int y=0;        //this function tells us if we are stuck in a corner with done nodes or traversed nodes
    int goodneighbors=4;
    while(x<4)
    {
        if(neighbors[x]==prevnode)
            goodneighbors-=1;

        y=0;
        while(y < badcount)
        {
            if(neighbors[x]==badnodes[y])       //goodneighbors is always 4, if the current neighbor is either a done node, a traversed node, or a -1 meaning an empty neighbor we subtract 1
                goodneighbors-=1;
            y++;
        }
        if(neighbors[x]==-1)
            goodneighbors-=1;
        x++;
    }
if (goodneighbors==0)       //if all the neighbors are invalid then we are at a dead end
    return 1;
else return 0;

}
int neighbor( int x, int node, struct node paths[])
{
        if( paths[x].path1==node || paths[x].path2==node )
            return 1;

        else return 0;
}
void cleanfgets(char input[])
{
    int x=0;
    while(input[x])
    x++;
    input[x-1]='\0';
}
int main(void)
{
FILE* fp = fopen("mazesolution","w"); //file name here

char input[20];
int totalmazes;
int totalnodes;
int totaledges;
int prevnode;
int badcount=0;         //keeping track of how many bad neighbors
int v=0;
int w=0;    //for maze traversing
int x=0;
int y=0;    //for total mazes
int z=0;
int neighborcount=0;    //for counting neighbors
int node;
int nodecounter=0;
int neighbors[4];
int *badnodes;
int *nodepaths;
struct node *paths;
memset(neighbors,-1,sizeof(neighbors));
fgets(input,sizeof(input),stdin);
    sscanf(input,"%d",&totalmazes);

    while(y<totalmazes)     //run the entire loop as many times as there are mazes
    {
        fgets(input,sizeof(input),stdin);
            sscanf(input,"%d %d",&totalnodes,&totaledges);

        badnodes=malloc(sizeof(int) * totaledges);      //these initialize the badnodes, nodepath arrays depending on how large the maze is
        memset(badnodes,-1,sizeof(badnodes));           //having 0 as a node means they should be initialized to some other default value to prevent confusion
        paths=malloc(sizeof(struct node) * totaledges);
        nodepaths=malloc(sizeof(int) * totaledges);
        memset(nodepaths,-1,sizeof(nodepaths));
        badcount=0;
        node=0;
        prevnode=-5;    //having -1 as default member of the arrays and since the maze contains 0 as a node, the default value should be something negative thats less than -1
        x=0;
        nodecounter=0;

        while(x<totaledges)
                {
                fgets(input,sizeof(input),stdin);
                sscanf(input,"%d %d %d", &paths[x].path1,&paths[x].path2,&paths[x].cost);
                x++;
                }           //store the maze in paths[]
        x=0;


        while(node!=totaledges) //start of maze solving
            {

            memset(nodepaths,-1,sizeof(nodepaths));
            node=0;
            prevnode=-5;
            w=0;
            while(w<totaledges)     //node travelling loop
                {

                nodepaths[w]=node;      //nodepaths takes note of the path taken so that if we find the solution we just print this out
                    neighborcount=0;
                    memset(neighbors,-1,sizeof(neighbors));
                    x=0;
                    while(x<totaledges)             //find neighbors and store into neighbor array
                            {
                            if(neighbor(x,node,paths)==1){
                                if(node==paths[x].path1)
                                neighbors[neighborcount]=paths[x].path2;

                                else
                                neighbors[neighborcount]=paths[x].path1;

                                neighborcount++;
                            }

                            x++;
                            }

                    if(node==totaledges)    {
                        break;  }       //found solution if this happens and it should break out of the bigger loop too
                    if(deadend(badnodes,neighbors,node,prevnode,badcount)==1) {

                        badnodes[badcount]=node;        //get out if theres no neighbors left to check
                        badcount++;                     // bad/done nodes are nodes that are checked already
                        node=0; prevnode=-5;
                        break;
                        }



                        x=0;
                        while(badneighbor(badnodes, neighbors, node, prevnode,badcount,x)==1)   //node travelling
                            {
                            x++;
                            }
                        prevnode=node;          //reassign the current working node
                        node=neighbors[x];
                                    neighborcount=0;
                    memset(neighbors,-1,sizeof(neighbors));
                    x=0;
                    while(x<totaledges)             //find neighbors and store into neighbor array
                            {
                            if(neighbor(x,node,paths)==1){
                                if(node==paths[x].path1)
                                neighbors[neighborcount]=paths[x].path2;

                                else
                                neighbors[neighborcount]=paths[x].path1;

                                neighborcount++;
                            }

                            x++;
                            }


                    w++;
                }
                if(node==totaledges)
                    break;
                z++;
            }
            x=0;
            fprintf(fp,"Maze #%d\n",(y+1));
            fprintf(fp,"Cost: %d \n",getcost(nodepaths,paths,totaledges));
            while(nodepaths[x]<totaledges)          //nodepaths contains the solution
            {
            fprintf(fp,"%d ",nodepaths[x]);
            x++;
            }
            fprintf(fp,"%d\n",nodepaths[x]);

            fprintf(fp,"%d Nodes traversed\n\n", (x+1) );
                free(badnodes);     //delete arrays, re-running loop will initialize new ones with proper allocatoins using malloc
                free(nodepaths);
                free(paths);
        y++;
    }                   fclose(fp);

return 0;
}