ChainReactionSolver

//
//  main.c
//  ChainReactionSolver
//
//  Created by Evan Andersen on 12-04-08.
//  Copyright (c) 2012 charliehorse55. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <pthread.h>
#include <time.h>
#include <math.h>
#include <string.h>

#ifdef __MACH__
#include <mach/mach.h>
#include <mach/mach_time.h>
#endif

//wrappers
void* xmalloc(size_t size);

//Threading
void* threadInit(void* arguments);
int createThread(pthread_t* theThread, uint8_t* problem, uint8_t problemSize, uint8_t* allPaths, int* blockCount, long maxBlockCount, pthread_mutex_t* mutex, uint8_t blockPathLength, uint8_t* connections);
void generateBlockArray(uint8_t* path, uint8_t position, uint8_t* problem, uint8_t problemSize, uint8_t pathLength, long* solutionCount, uint8_t* connections, uint8_t* allPaths);
void copyPathToArray(uint8_t* path, uint8_t* allPaths, uint8_t pathLength, long arrayPosition);

//Solving
uint8_t isValid(uint8_t a, uint8_t b);
void findNextPathStep(uint8_t i, uint8_t j, uint8_t position, uint8_t* problem, uint8_t problemSize, uint8_t pathLength, long* solutionCount, uint8_t* connections);
long solveProblem(uint8_t* problem, uint8_t problemSize, uint8_t maxThreadCount);
uint8_t* createConnections(uint8_t* problem, uint8_t problemSize, double* averageNumConnections);

//Printing
void printHelp(void);
void printProblem(uint8_t* problem, uint8_t problemSize);

//Problem Loading
uint8_t* readProblem(const char* path, uint8_t* size);
uint8_t* randomProblem(uint8_t problemSize);


//Performance tweaking constants
const int kDefaultThreads = 4;
const int kMaxThreads = 64;
const int kBlockSize = 19;


//=======================================================================================================================================
// Malloc wrapper
//
// Ensures that malloc returns a valid pointer, else quits with an error
//=======================================================================================================================================
void* xmalloc(size_t size)
{
    void* pointer = malloc(size);
    if(!pointer)
    {
        printf("Malloc could not allocate memory of size %lu\n", size);
        exit(-1);
    }
    return pointer;
}


//=======================================================================================================================================
// Multi-threading
//=======================================================================================================================================
struct thread_info
{
    uint8_t position;
    uint8_t* problem;
    uint8_t problemSize;
    uint8_t pathLength;
    uint8_t* allPaths;
    uint8_t blockPathLength;
    int* blockCount;
    long maxBlockCount;
    pthread_mutex_t* mutex;
    uint8_t* connections;
};

void* threadInit(void* arguments)
{
    struct thread_info *args = arguments;
    long* theResult = xmalloc(sizeof(long));
    *theResult = 0;

    //keep loading blocks until they are all done
    while(1)
    {
        //block other threads from accessing blockCount
        pthread_mutex_lock(args->mutex);
        if(*(args->blockCount) < args->maxBlockCount)
        {
            //store it for later
            int tempBlockCount = *(args->blockCount);

            //increment so the next thread takes the next block in the queue
            (*(args->blockCount))++;

            //allow other threads to access the blockCount again
            pthread_mutex_unlock(args->mutex);

            //mark the problem array
            uint8_t col, row;
            for (int i = 1; i < args->blockPathLength; i++)
            {
                col = (args->allPaths)[tempBlockCount*args->blockPathLength*2 + i*2];
                row = (args->allPaths)[tempBlockCount*args->blockPathLength*2 + i*2 + 1];
                (args->problem)[col*args->problemSize*2 + row*2 + 1] = 1;
            }
            findNextPathStep(col, row, args->blockPathLength - 1, args->problem, args->problemSize, args->pathLength, theResult, args->connections);

            if(!(tempBlockCount % 10))
            {
                printf("Block %d/%ld solved\n", tempBlockCount, args->maxBlockCount);
            }
            //reset the travelled path to it's default state, all 0 (except 0,0)
            for (int i = 1; i < args->blockPathLength; i++)
            {
                //mark the problem array
                col = (args->allPaths)[tempBlockCount*args->blockPathLength*2 + i*2];
                row = (args->allPaths)[tempBlockCount*args->blockPathLength*2 + i*2 + 1];
                (args->problem)[col*args->problemSize*2 + row*2 + 1] = 0;
            }
        }
        else
        {
            pthread_mutex_unlock(args->mutex);
            break;
        }
    }
    //free the problem
    free(args->problem);

    //free the info struct
    free(args);

    pthread_exit(theResult);
}

int createThread(pthread_t* theThread, uint8_t* problem, uint8_t problemSize, uint8_t* allPaths, int* blockCount, long maxBlockCount, pthread_mutex_t* mutex, uint8_t blockPathLength, uint8_t* connections)
{
    //create a new version of the problem array asd copy the values in
    uint8_t* newProblem = xmalloc(sizeof(uint8_t**)*problemSize*problemSize*2);
    for(int i = 0; i < problemSize; i++)
    {
        for(int j = 0; j < problemSize; j++)
        {
            newProblem[i*problemSize*2 + j*2]  = problem[i*problemSize*2 +j*2];
            newProblem[i*problemSize*2 + j*2 + 1]  = problem[i*problemSize*2 + j*2 + 1];
        }
    }

    //each thread needs it's own copy of the problem array
    struct thread_info* info  = xmalloc(sizeof(struct thread_info));
    info->position = 1;
    info->problem = newProblem;
    info->problemSize = problemSize;
    info->pathLength = problemSize*problemSize - 1;
    info->allPaths = allPaths;
    info->blockPathLength = blockPathLength;
    info->blockCount = blockCount;
    info->maxBlockCount = maxBlockCount;
    info->mutex = mutex;
    info->connections = connections;

    return pthread_create(theThread, NULL, &threadInit, (void*)info);
}

//=======================================================================================================================================
// Block generator
//
// Break the problem into smaller chunks that can be seperatley processed by threads
//=======================================================================================================================================
void generateBlockArray(uint8_t* path, uint8_t position, uint8_t* problem, uint8_t problemSize, uint8_t pathLength, long* solutionCount, uint8_t* connections, uint8_t* allPaths)
{
    //faster to define a new variable then to do position + 1 four times
    uint8_t newPos = position + 1;

    uint8_t i = path[position*2];
    uint8_t j = path[position*2 + 1];

    uint16_t base = problemSize*problemSize*4*i + j*problemSize*4;

    //compiler should optimize this out, prevents spagetti code
    for(uint8_t z = 1; z <= connections[base]; z++)
    {
        uint8_t currentCol = connections[base + z*2];
        uint8_t currentRow = connections[base + z*2 + 1];
        if(!problem[currentCol*problemSize*2 + currentRow*2 + 1])
        {
            if(isValid(problem[currentCol*problemSize*2 + currentRow*2], problem[i*problemSize*2 + j*2]))
            {
                path[newPos*2] = currentCol;
                path[newPos*2 + 1] = currentRow;

                //if we are at the end of the path, we have found a solution
                if(newPos >= pathLength)
                {
                    copyPathToArray(path, allPaths, pathLength, *solutionCount);

                    (*solutionCount)++;
                }
                else
                {
                    //recurse and mark this square as part of the path
                    problem[currentCol*problemSize*2 + currentRow*2 + 1] = 1;
                    generateBlockArray(path, newPos, problem, problemSize, pathLength, solutionCount, connections, allPaths);
                    problem[currentCol*problemSize*2 + currentRow*2 + 1] = 0;
                }
            }
        }
    }
}

//=======================================================================================================================================
// Copy path to array
//
// self explanatory
//=======================================================================================================================================
void copyPathToArray(uint8_t* path, uint8_t* allPaths, uint8_t pathLength, long arrayPosition)
{
    //copy the current path into it
    pathLength++;
    for(int i = 0; i < pathLength; i++)
    {
        allPaths[arrayPosition*pathLength*2 + i*2] = path[i*2];
        allPaths[arrayPosition*pathLength*2 + i*2 + 1] = path[i*2 + 1];
    }
}

//=======================================================================================================================================
// Shape and Color Testing
//
// Note - it's faster to simply check the 1 case that is illegal vs. the 3 that are legal
//=======================================================================================================================================
uint8_t isValid(uint8_t a, uint8_t b)
{
    switch (a)
    {
        case 0:
            return b != 3;

        case 1:
            return b != 2;

        case 2:
            return b != 1;

        case 3:
            return b != 0;
    }
    return 0;
}

//=======================================================================================================================================
// The Recursive Solution Finder
//
// Only checks valid moves based on the cache in the connection array
//=======================================================================================================================================
void findNextPathStep(uint8_t i, uint8_t j, uint8_t position, uint8_t* problem, uint8_t problemSize, uint8_t pathLength, long* solutionCount, uint8_t* connections)
{
    //faster to define a new variable then to do position + 1 four times
    uint8_t newPos = position + 1;

    uint16_t base = problemSize*problemSize*4*i + j*problemSize*4;

    if(newPos >= pathLength)
    {
        for(uint8_t z = 1; z <= connections[base]; z++)
        {
            //compiler should optimize this out, prevents spagetti code
            uint8_t currentCol = connections[base + z*2];
            uint8_t currentRow = connections[base + z*2 + 1];
            if(!problem[currentCol*problemSize*2 + currentRow*2 + 1] && isValid(problem[currentCol*problemSize*2 + currentRow*2], problem[i*problemSize*2 + j*2]))
            {
                (*solutionCount)++;
            }
        }
    }
    else
    {
        for(uint8_t z = 1; z <= connections[base]; z++)
        {
            uint8_t currentCol = connections[base + z*2];
            uint8_t currentRow = connections[base + z*2 + 1];
            if(!problem[currentCol*problemSize*2 + currentRow*2 + 1])
            {
                if(isValid(problem[currentCol*problemSize*2 + currentRow*2], problem[i*problemSize*2 + j*2]))
                {
                    //recurse and mark this square as part of the path
                    problem[currentCol*problemSize*2 + currentRow*2 + 1] = 1;
                    findNextPathStep(currentCol, currentRow, newPos, problem, problemSize, pathLength, solutionCount, connections);
                    problem[currentCol*problemSize*2 + currentRow*2 + 1] = 0;
                }
            }
        }
    }
}

//=======================================================================================================================================
// Solve Problem
//
// Returns the exact total number of solutions for a given problem
//=======================================================================================================================================
long solveProblem(uint8_t* problem, uint8_t problemSize, uint8_t maxThreadCount)
{
    double averageConnections;
    uint8_t* possibleConnections = createConnections(problem, problemSize, &averageConnections);

    printf("\nAverage of %.3lf of %d possible connections\n\n", averageConnections, problemSize*2 - 2);


    //calculate the path length to calculate the blocks from
    int blockPathLength = problemSize*problemSize - kBlockSize;

    //should not be less than 2
    if (blockPathLength < 2)
    {
        blockPathLength = 2;
    }

    //count how many blocks we need
    long blockCount = 0;
    findNextPathStep(0, 0, 0, problem, problemSize, blockPathLength - 1, &blockCount, possibleConnections);

    //init an array to hold all of the blocks
    uint8_t* allPaths = xmalloc(sizeof(uint8_t)*blockCount*blockPathLength*2);

    //fill the array
    //make a new path
    uint8_t* path = xmalloc(sizeof(uint8_t)*blockPathLength*2);

    //start of the path is always 0
    path[0] = 0;
    path[1] = 0;

    long pathCount = 0;
    generateBlockArray(path, 0, problem, problemSize, blockPathLength - 1, &pathCount, possibleConnections, allPaths);

    printf("\nCreated %ld blocks to solve\n\n", blockCount);

    //create the specified number of threads and start handing out tasks
    pthread_t* threads = xmalloc(sizeof(pthread_t)*maxThreadCount);

    //variable to synchronize the blocks between threads
    int currentBlock = 0;

    //create a mutex for thread synchronization
    pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

    int threadCount = 0;
    while(threadCount < maxThreadCount && threadCount < blockCount)
    {
        createThread(&(threads[threadCount]), problem, problemSize, allPaths, &currentBlock, blockCount, &mutex, blockPathLength, possibleConnections);
        threadCount++;
    }

    printf("\nCreated %d threads\n", threadCount);

    //wait for threads to finish and count the solutions
    long solutionCount = 0;
    for(uint8_t i = 0; i < threadCount; i++)
    {
        void* returnValue;
        pthread_join(threads[i], &returnValue);
        solutionCount += *(long*)returnValue;

        //free the result variable
        free(returnValue);
    }

    //free stuff
    free(threads);
    free(possibleConnections);
    free(path);
    free(allPaths);

    return solutionCount;
}

//=======================================================================================================================================
// Connection Array
//
// Creates an array holding all possible connections between blocks
//=======================================================================================================================================
uint8_t* createConnections(uint8_t* problem, uint8_t problemSize, double* averageNumConnections)
{
    //cache all possible connections

    uint8_t leadingDim = problemSize*problemSize*4;

    //create the cache array
    uint8_t* possibleConnections = xmalloc(sizeof(uint8_t)*leadingDim*problemSize);

    //fill the cache array
    uint32_t totalConnections = 0;

    //for each row
    for(int i = 0; i < problemSize; i++)
    {
        //for each col
        for(int j = 0; j < problemSize; j++)
        {
            int numConnections = 0;
            //test the row
            for(int z = 0; z < problemSize; z++)
            {
                if(z != j && isValid(problem[i*problemSize*2 + j*2], problem[i*problemSize*2 + z*2]))
                {
                    numConnections++;
                    possibleConnections[i*leadingDim + j*problemSize*4 + numConnections*2] = i;
                    possibleConnections[i*leadingDim + j*problemSize*4 + numConnections*2 + 1] = z;
                }
            }
            //test the column
            for(int z = 0; z < problemSize; z++)
            {
                if(z != i && isValid(problem[i*problemSize*2 + j*2], problem[z*problemSize*2 +j*2]))
                {
                    numConnections++;
                    possibleConnections[i*leadingDim + j*problemSize*4 + numConnections*2] = z;
                    possibleConnections[i*leadingDim + j*problemSize*4 + numConnections*2 + 1] = j;
                }
            }
            //store the number of found connections
            possibleConnections[i*leadingDim + j*problemSize*4] = numConnections;
            totalConnections += numConnections;
        }
    }
    if(averageNumConnections)
    {
        *averageNumConnections = (double)totalConnections / (problemSize*problemSize);
    }

    return possibleConnections;
}


//=======================================================================================================================================
// Read problems from the hard drive
//
// Note - problems are currently stored as 2 bit ints on the HD. Feel free to modify to read Cr, Cb, etc if you want
//=======================================================================================================================================
uint8_t* readProblem(const char* path, uint8_t* problemSize)
{
    //open the file for reading only
    FILE* problemFile = fopen(path, "r");

    *problemSize = 0;

    if(problemFile)
    {
        //scan the number of elements on the first line
        char input[32];
        fgets(input, sizeof(input), problemFile);

        for(int i = 0; input[i] != '\n' && i < sizeof(input); i++)
        {
            if(input[i] >= '0' && input[i] <= '3')
            {
                (*problemSize)++;
            }
        }

        //sanity check
        if (*problemSize > 12)
        {
            printf("Badly formatted file at %s\n\n", path);
            exit(-1);
        }

        //alloc the 3D problem array
        uint8_t* problem = xmalloc(sizeof(uint8_t**)*(*problemSize)*(*problemSize)*2);

        //read in the array from the file
        int temp = 0;

        fseek(problemFile, 0, SEEK_SET);
        for(int j = 0; (j < *problemSize); j++)
        {
            for(uint8_t i = 0; i < *problemSize; i++)
            {
                if(fscanf(problemFile, "%d", &temp) && temp >= 0 && temp <= 3)
                {
                    problem[i*(*problemSize)*2 + j*2] = (uint8_t)temp;
                    problem[i*(*problemSize)*2 + j*2 + 1] = 0;
                }
            }
        }

        //always close a file when you are done with it
        fclose(problemFile);

        return problem;
    }
    else
    {
        printf("\nError reading file at %s\n\n", path);
        exit(-1);
    }

}

//=======================================================================================================================================
// Random Problem
//
// Returns a random problem of the specified size
//=======================================================================================================================================
uint8_t* randomProblem(uint8_t problemSize)
{
    uint8_t* problem = xmalloc(sizeof(uint8_t)*problemSize*problemSize*2);
    for(int i = 0; i < problemSize; i++)
    {
        for(int j = 0; j < problemSize; j++)
        {
            problem[i*problemSize*2 + j*2] = rand() % 4;
            problem[i*problemSize*2 + j*2 + 1] = 0;
        }
    }
    return problem;
}

//=======================================================================================================================================
// Print Problem
//
// Prints the problem
//=======================================================================================================================================
void printProblem(uint8_t* problem, uint8_t problemSize)
{
    for(int i = 0; i < problemSize; i++)
    {
        printf("      ");
        for(int j = 0; j < problemSize; j++)
        {
            printf("%hhu ", problem[j*problemSize*2 + i*2]);
        }
        printf("\n");
    }
    printf("\n");
}


//=======================================================================================================================================
// Help Function
//
// Prints details on how to propely use this program
//=======================================================================================================================================
void printHelp()
{
    printf("\n-------------------Chain Reaction Solver 1.0-------------------\n\n");
    printf("Options:\n");
    printf("           -f, --filename <filename> Specify a filename to use as input\n\n");
    printf("           -t, --threads <count> Specifies the number of threads to create.\n");
    printf("              Valid numbers are between 1 and 64\n\n");
    printf("           -h, --help Print the help\n\n");
}

//=======================================================================================================================================
// Main Function
//
// Reads command line options and decides what to do with them
//=======================================================================================================================================
int main (int argc, const char * argv[])
{
    int maxThreads = kDefaultThreads;
    const char* filename = NULL;

    srand(time(NULL));

    //parse command line options
    for(int i = 1; i < argc; i++)
    {
        if(argv[i][0] == '-')
        {
            //found the file
            if(!strcmp(argv[i], "-f") || !strcmp(argv[i], "--filename"))
            {
                if(filename)
                {
                    printHelp();
                    printf("\nError - multiple input files specified\n");
                    exit(-1);
                }

                if((i + 1) < argc)
                {
                    filename = argv[i + 1];
                }

                //no need to try and parse it further
                continue;
            }

            //thread count
            if(!strcmp(argv[i], "-t") || !strcmp(argv[i], "--threads"))
            {
                int threadCount = 0;
                if((i + 1) < argc)
                {
                    threadCount = atoi(argv[i + 1]);
                }
                else
                {
                    printHelp();
                    printf("\nInvalid Thread Count\n");
                    exit(-1);
                }

                if (threadCount > 0 && threadCount <= kMaxThreads)
                {
                    maxThreads = threadCount;
                }
                else
                {
                    printHelp();
                    printf("\nInvalid Thread Count\n");
                    exit(-1);
                }

                continue;
            }
            if (!strcmp(argv[i], "-h") || !strcmp(argv[i], "--help"))
            {
                printHelp();
                exit(0);
            }
            printHelp();
            printf("\nInvalid Option, %s\n\n", argv[i]);
            exit(-1);
        }
    }

    uint8_t problemSize;
    uint8_t* problem;

    //if we are here and filename is null it was not found
    if(filename)
    {
        //load the problem
        problem = readProblem(filename, &problemSize);
        printf("Read in problem from file:\n\n");
        printProblem(problem, problemSize);
    }
    else
    {
        printf("\nNo file name specified, using a random 5x5 problem:\n\n");
        problemSize = 5;
        problem = randomProblem(problemSize);
        printProblem(problem, problemSize);
    }

    //start timing how fast the solution takes to generate (on OSX only)
#ifdef __MACH__
    uint64_t start = mach_absolute_time();
#endif

    //path always starts in the upper left, prime the path cache
    problem[1] = 1;

    //SOVLE IT
    long solutionCount;
    solutionCount = solveProblem(problem, problemSize, maxThreads);

    //on OSX
#ifdef __MACH__
    double elapsedTime = (double)(mach_absolute_time() - start) / 1e9;
    uint32_t minutes = elapsedTime/60;
    double seconds = elapsedTime - minutes*60;

    printf("\n\nFound %ld solutions in %u minutes and %.4f seconds\n", solutionCount, minutes, seconds);

    //other platforms
#else
    printf("\n\nFound %ld solutions\n", solutionCount);

#endif

    //free the problem
    free(problem);

    //Cave Johnson, we're done here
    return 0;
}