r dailyprogrammer challenge 232 intermediate Grandma's House

grannyshouse_dnc.c

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <limits.h>
    #include <time.h>


    /*Finds length of longest line in file*/
    int charcount(char *filename)
    {
        FILE    *fp;
        int count = 0, maxcount = 0;
        char c;
       
        fp = fopen (filename, "r");
        if (fp == NULL)
        {
            fputs ("Failed to open file.\n", stderr);
            return 0;
        }

        do
        {
            c = fgetc( fp );
            if( c == '\n')
            {
                if( count > maxcount)
                    maxcount=count;
                count = 0;
            }
            if (count+1<INT_MAX)
            {
                count++;
            }
            else
            {
                fputs ("Integer about to overrun. Aborting.\n", stderr);
                return 0;
            }
            
        }
        while (c!=EOF);

        fclose(fp);
        return maxcount;
    }

    /* Calculates distance between points. */
    static double distance_between_points(double x1, double y1, double x2, double y2)
    {
        return (fabs(x1 - x2) * fabs(x1 - x2)) + (fabs(y1 - y2) * fabs(y1 - y2));
    }

    /* Compare function for qsort */
    int cmp_x(const void *a, const void *b)
    {
        double *pa = *((double **) a);
        double *pb = *((double **) b);

        return (*pa > *pb) - (*pa < *pb); 
    }

    /* Performs bruteforce check of array within bounds given by lowloop and highloop, to find smallest distance */
    void bruteforce(int lowloop, int highloop, double *smallest_distance, int *smallest_lc0, int *smallest_lc1, double ***coordinates)
    {
        double xdist;
        double current_distance= 0.0;
        int lc0, lc1;

        for(lc0=lowloop; lc0 < highloop; lc0++)
        {

            for(lc1=lc0+1; lc1 < highloop; lc1++)
            {
                xdist = (*coordinates)[lc1][0] - (*coordinates)[lc0][0];
                // Since list is sorted, as soon as we encounter a deltax
                // larger than smallest_distance, we already know not to process it
                if( lc0!=lc1 && ((xdist * xdist) <= *smallest_distance) )
                {
                    current_distance = distance_between_points( (*coordinates)[lc0][0], (*coordinates)[lc0][1], (*coordinates)[lc1][0], (*coordinates)[lc1][1]);

                    if (current_distance < *smallest_distance)
                    {
                        *smallest_distance=current_distance;
                        *smallest_lc0=lc0;
                        *smallest_lc1=lc1;
                    }
                }
            }
        }
    }

    /*Processes the input file for coordinates*/
    int process_file(char *filename)
    {
        FILE    *fp;
        int number_of_lines_to_process = 0, lc0, rowcounter;
        int maxlinelength;
        char *buffer;
        double **coordinates;

        struct timespec tick, tock;
        double duration;

        maxlinelength=charcount(filename);

        clock_gettime(CLOCK_MONOTONIC, &tick);
        
        if (maxlinelength > 0)
        {

            buffer=malloc( maxlinelength+2 * sizeof(char *));
            if(buffer==NULL)
            {
                fputs("Error: memory not allocated for buffer.\n", stderr);
                return 1;
            }
            fp = fopen (filename, "r");
            if (fp == NULL)
            {
                fputs ("Failed to open file.\n", stderr);
                return 1;
            }

            while(fgets(buffer, maxlinelength+2, fp) != NULL)
            {
                if(buffer[strlen(buffer)-1]=='\n')
                    buffer[strlen(buffer)-1]='\0';
                
                if(sscanf(buffer, "%i", &number_of_lines_to_process)==1)
                {
                    rowcounter = 0;
                    
                    long pos=ftell(fp);
                    int tempcounter = 0, scanfresult=0;
                    double tempcoord1=0.0, tempcoord2=0.0;
                    char tempbuffer[maxlinelength+2];
                    
                    
                    while (fgets(tempbuffer, maxlinelength+2, fp)!= NULL)
                    {
                        if(tempbuffer[strlen(tempbuffer)-1]=='\n')
                            tempbuffer[strlen(tempbuffer)-1]='\0';
                        scanfresult = sscanf(tempbuffer, "(%lf, %lf)", &tempcoord1, &tempcoord2);
                        if (scanfresult == 2)
                            tempcounter++;
                        else
                            break;
                    }
                    
                    if (number_of_lines_to_process!=tempcounter)
                    {
                        fprintf(stderr, "Error: Expected %i, found %i. Processing %i...\n", number_of_lines_to_process, tempcounter, tempcounter);
                        number_of_lines_to_process=tempcounter;
                    }
                    fseek(fp, pos, SEEK_SET);

                    coordinates=malloc( number_of_lines_to_process * sizeof(double) );
                    if(coordinates==NULL)
                    {
                        fputs("Error: memory not allocated for array - d1.\n", stderr);
                        return 1;
                    }
                    else
                    {
                        for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                        {
                            coordinates[lc0]=malloc( 2 * sizeof(double) );
                            if(coordinates[lc0]==NULL)
                            {
                                fputs("Error: memory not allocated for array - d2.\n", stderr);
                                return 1;
                            }
                        }
                    }
                }
                if (
                    (coordinates != NULL && coordinates[rowcounter] != NULL) && 
                    (number_of_lines_to_process > 0 && rowcounter < number_of_lines_to_process) && 
                    sscanf(buffer, "(%lf, %lf)", &coordinates[rowcounter][0], &coordinates[rowcounter][1])==2
                   )
                {
                    rowcounter++;
                }
                if(rowcounter == number_of_lines_to_process)
                {
                    int smallest_lc0=0, smallest_lc1=1, middle=number_of_lines_to_process/2;

                    double smallest_distance = 10.0;
                    double midpoint = coordinates[middle][0];
                    double delta_left = midpoint - smallest_distance;
                    double delta_right = midpoint + smallest_distance;
                    
                    int lc_left=0, lc_right=0;

                    
                    qsort( coordinates, number_of_lines_to_process, sizeof(double *), cmp_x );

                    bruteforce(0, middle, &smallest_distance, &smallest_lc0, &smallest_lc1, &coordinates);

                    bruteforce(middle-1, number_of_lines_to_process, &smallest_distance, &smallest_lc0, &smallest_lc1, &coordinates);

                    for(lc0=middle; lc0 > 0; lc0--)
                    {
                        if (coordinates[lc0][0] > delta_left)
                        {
                            lc_left++;
                        }
                        else
                        {
                            break;
                        }
                    }
                    for(lc0=middle; lc0 < number_of_lines_to_process; lc0++)
                    {
                        if (coordinates[lc0][0] < delta_right)
                        {
                            lc_right++;
                        }
                        else
                        {
                            break;
                        }
                    }
                    
                    if (lc_left > 0 && lc_right > 0)
                    {
                        bruteforce(middle-lc_left, lc_right, &smallest_distance, &smallest_lc0, &smallest_lc1, &coordinates);
                    }

                    printf("(%0.15f, %0.15f) (%0.15f, %0.15f)\n", coordinates[smallest_lc1][0], coordinates[smallest_lc1][1], coordinates[smallest_lc0][0], coordinates[smallest_lc0][1] );
                    
                    //free array
                    
                    for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                    {
                        free(coordinates[lc0]);
                    }
                    free(coordinates);
                }
            }

            fclose(fp);
            free(buffer);
            
            clock_gettime(CLOCK_MONOTONIC, &tock);
            duration=(tock.tv_sec - tick.tv_sec);
            duration = duration + (tock.tv_nsec - tick.tv_nsec) / 1000000000.0;
            if (duration < 60.0)
                printf("Elapsed: %f seconds\n", duration);
            else if (duration >= 60.0 && duration < 60.0*60.0)
                printf("Elapsed: %f minutes\n", duration/60.0 );
            else if (duration >= 60.0*60.0)
                printf("Elapsed: %f hours\n", duration/(60.0*60.0) );
        }
        

        return 0;
    }


    int main(int argc, char **argv)
    {
        if(argc > 1 && strlen(argv[1]) > 1)
        {
            process_file(argv[1]);
        }
        else if (argc == 1)
        {
            fputs ("Please supply a valid file name for the argument.\n", stderr);
        }

        return 0;
    }

grannyshouse_novarify.c

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <limits.h>
    #include <time.h>


    /* Calculates distance between points. */
    static double distance_between_points(double x1, double y1, double x2, double y2)
    {
        return (fabs(x1 - x2) * fabs(x1 - x2)) + (fabs(y1 - y2) * fabs(y1 - y2));
    }

    /* Compare function for qsort */
    int cmp_x(const void *a, const void *b)
    {
        double *pa = *((double **) a);
        double *pb = *((double **) b);

        return (*pa > *pb) - (*pa < *pb); 
    }

    /*Processes the input file for coordinates*/
    int process_file(char *filename)
    {
        FILE    *fp;
        int number_of_lines_to_process = 0, lc0, lc1, rowcounter;
        int maxlinelength;
        char buffer[256];
        double **coordinates;

        struct timespec tick, tock;
        double duration;

        int smallest_lc0=0, smallest_lc1=1;
        double smallest_distance = 10.0;
        double current_distance= 0.0;
        double xdist;



        maxlinelength=(int)sizeof(buffer);

        clock_gettime(CLOCK_MONOTONIC, &tick);
        
        fp = fopen (filename, "r");
        if (fp == NULL)
        {
            fputs ("Failed to open file.\n", stderr);
            return 1;
        }

        while(fgets(buffer, maxlinelength, fp) != NULL)
        {
            if(buffer[strlen(buffer)-1]=='\n')
                buffer[strlen(buffer)-1]='\0';
            
            if(sscanf(buffer, "%i", &number_of_lines_to_process)==1)
            {
                coordinates=malloc( number_of_lines_to_process * sizeof(double) );
                if(coordinates==NULL)
                {
                    fputs("Error: memory not allocated for array - d1.\n", stderr);
                    return 1;
                }
                else
                {
                    for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                    {
                        coordinates[lc0]=malloc( 2 * sizeof(double) );
                        if(coordinates[lc0]==NULL)
                        {
                            fputs("Error: memory not allocated for array - d2.\n", stderr);
                            return 1;
                        }
                    }
                }
                rowcounter=0;
            }
            if (
                (number_of_lines_to_process > 0 && rowcounter < number_of_lines_to_process) && 
                sscanf(buffer, "(%lf, %lf)", &coordinates[rowcounter][0], &coordinates[rowcounter][1])==2
               )
            {
                rowcounter++;
            }

            if(rowcounter == number_of_lines_to_process)
            {
                qsort( coordinates, number_of_lines_to_process, sizeof(double *), cmp_x );

                //now find closest coordinates

                for(lc0=0; lc0 < number_of_lines_to_process; lc0++)
                {
                    for(lc1=lc0 + 1; lc1 < number_of_lines_to_process; lc1++)
                    {
                        xdist = coordinates[lc1][0] - coordinates[lc0][0];
                        // Since list is sorted, as soon as we encounter a deltax
                        // larger than smallest_distance, we already know not to process it
                        if( lc0 != lc1 && ((xdist * xdist) <= smallest_distance) )
                        {
                            current_distance = distance_between_points(coordinates[lc0][0], coordinates[lc0][1], coordinates[lc1][0], coordinates[lc1][1]);

                            if (current_distance < smallest_distance)
                            {
                                smallest_distance=current_distance;
                                smallest_lc0=lc0;
                                smallest_lc1=lc1;
                            }
                        }
                    }
                }
                printf("(%0.15f, %0.15f) (%0.15f, %0.15f)\n", coordinates[smallest_lc0][0], coordinates[smallest_lc0][1], coordinates[smallest_lc1][0], coordinates[smallest_lc1][1] );
                
                //free array
                
                for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                {
                    free(coordinates[lc0]);
                }
                free(coordinates);
                
                number_of_lines_to_process=0;
            }
        }

        fclose(fp);
        
        clock_gettime(CLOCK_MONOTONIC, &tock);
        duration=(tock.tv_sec - tick.tv_sec);
        duration = duration + (tock.tv_nsec - tick.tv_nsec) / 1000000000.0;
        if (duration < 60.0)
            printf("Elapsed: %f seconds\n", duration);
        else if (duration >= 60.0 && duration < 60.0*60.0)
            printf("Elapsed: %f minutes\n", duration/60.0 );
        else if (duration >= 60.0*60.0)
            printf("Elapsed: %f hours\n", duration/(60.0*60.0) );

        return 0;
    }


    int main(int argc, char **argv)
    {
        if(argc > 1 && strlen(argv[1]) > 1)
        {
            process_file(argv[1]);
        }
        else if (argc == 1)
        {
            fputs ("Please supply a valid file name for the argument.\n", stderr);
        }

        return 0;
    }

grannyshouse_orig.c

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <limits.h>
    #include <time.h>


    /*Finds length of longest line in file*/
    int charcount(char *filename)
    {
        FILE    *fp;
        int count = 0, maxcount = 0;
        char c;
       
        fp = fopen (filename, "r");
        if (fp == NULL)
        {
            fputs ("Failed to open file.\n", stderr);
            return 0;
        }

        do
        {
            c = fgetc( fp );
            if( c == '\n')
            {
                if( count > maxcount)
                    maxcount=count;
                count = 0;
            }
            if (count+1<INT_MAX)
            {
                count++;
            }
            else
            {
                fputs ("Integer about to overrun. Aborting.\n", stderr);
                return 0;
            }
            
        }
        while (c!=EOF);

        fclose(fp);
        return maxcount;
    }

    /* Calculates distance between points. */
    static double distance_between_points(double x1, double y1, double x2, double y2)
    {
        return (fabs(x1 - x2) * fabs(x1 - x2)) + (fabs(y1 - y2) * fabs(y1 - y2));
    }

    /* Compare function for qsort */
    int cmp_x(const void *a, const void *b)
    {
        double *pa = *((double **) a);
        double *pb = *((double **) b);

        return (*pa > *pb) - (*pa < *pb); 
    }

    /* Performs bruteforce check of array within bounds given by lowloop and highloop, to find smallest distance */
    void bruteforce(int lowloop, int highloop, double *smallest_distance, int *smallest_lc0, int *smallest_lc1, double ***coordinates)
    {
        double xdist;
        double current_distance= 0.0;
        int lc0, lc1;

        for(lc0=lowloop; lc0 < highloop; lc0++)
        {

            for(lc1=lc0+1; lc1 < highloop; lc1++)
            {
                xdist = (*coordinates)[lc1][0] - (*coordinates)[lc0][0];
                // Since list is sorted, as soon as we encounter a deltax
                // larger than smallest_distance, we already know not to process it
                if( lc0!=lc1 && ((xdist * xdist) <= *smallest_distance) )
                {
                    current_distance = distance_between_points( (*coordinates)[lc0][0], (*coordinates)[lc0][1], (*coordinates)[lc1][0], (*coordinates)[lc1][1]);

                    if (current_distance < *smallest_distance)
                    {
                        *smallest_distance=current_distance;
                        *smallest_lc0=lc0;
                        *smallest_lc1=lc1;
                    }
                }
            }
        }
    }

    /*Processes the input file for coordinates*/
    int process_file(char *filename)
    {
        FILE    *fp;
        int number_of_lines_to_process = 0, lc0, rowcounter;//lc1, 
        int maxlinelength;
        char *buffer;
        double **coordinates;

        int smallest_lc0=0, smallest_lc1=1;
        double smallest_distance = 10.0;
        //double current_distance= 0.0;
        //double xdist;

        struct timespec tick, tock;
        double duration;

        maxlinelength=charcount(filename);

        clock_gettime(CLOCK_MONOTONIC, &tick);
        
        if (maxlinelength > 0)
        {

            buffer=malloc( maxlinelength+2 * sizeof(char *));
            if(buffer==NULL)
            {
                fputs("Error: memory not allocated for buffer.\n", stderr);
                return 1;
            }
            fp = fopen (filename, "r");
            if (fp == NULL)
            {
                fputs ("Failed to open file.\n", stderr);
                return 1;
            }

            while(fgets(buffer, maxlinelength+2, fp) != NULL)
            {
                if(buffer[strlen(buffer)-1]=='\n')
                    buffer[strlen(buffer)-1]='\0';
                
                if(sscanf(buffer, "%i", &number_of_lines_to_process)==1)
                {
                    rowcounter = 0;
                    
                    long pos=ftell(fp);
                    int tempcounter = 0, scanfresult=0;
                    double tempcoord1=0.0, tempcoord2=0.0;
                    char tempbuffer[maxlinelength+2];
                    
                    
                    while (fgets(tempbuffer, maxlinelength+2, fp)!= NULL)
                    {
                        if(tempbuffer[strlen(tempbuffer)-1]=='\n')
                            tempbuffer[strlen(tempbuffer)-1]='\0';
                        scanfresult = sscanf(tempbuffer, "(%lf, %lf)", &tempcoord1, &tempcoord2);
                        if (scanfresult == 2)
                            tempcounter++;
                        else
                            break;
                    }
                    
                    if (number_of_lines_to_process!=tempcounter)
                    {
                        fprintf(stderr, "Error: Expected %i, found %i. Processing %i...\n", number_of_lines_to_process, tempcounter, tempcounter);
                        number_of_lines_to_process=tempcounter;
                    }
                    fseek(fp, pos, SEEK_SET);

                    coordinates=malloc( number_of_lines_to_process * sizeof(double) );
                    if(coordinates==NULL)
                    {
                        fputs("Error: memory not allocated for array - d1.\n", stderr);
                        return 1;
                    }
                    else
                    {
                        for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                        {
                            coordinates[lc0]=malloc( 2 * sizeof(double) );
                            if(coordinates[lc0]==NULL)
                            {
                                fputs("Error: memory not allocated for array - d2.\n", stderr);
                                return 1;
                            }
                        }
                    }
                }
                if (
                    (coordinates != NULL && coordinates[rowcounter] != NULL) && 
                    (number_of_lines_to_process > 0 && rowcounter < number_of_lines_to_process) && 
                    sscanf(buffer, "(%lf, %lf)", &coordinates[rowcounter][0], &coordinates[rowcounter][1])==2
                   )
                {
                    rowcounter++;
                }

                if(rowcounter == number_of_lines_to_process)
                {
                    qsort( coordinates, number_of_lines_to_process, sizeof(double *), cmp_x );

                    //now find closest coordinates

                    bruteforce(0, number_of_lines_to_process, &smallest_distance, &smallest_lc0, &smallest_lc1, &coordinates);

                    printf("(%0.15f, %0.15f) (%0.15f, %0.15f)\n", coordinates[smallest_lc1][0], coordinates[smallest_lc1][1], coordinates[smallest_lc0][0], coordinates[smallest_lc0][1] );
                    
                    //free array
                    
                    for (lc0=0; lc0 < number_of_lines_to_process; lc0++)
                    {
                        free(coordinates[lc0]);
                    }
                    free(coordinates);
                }
            }

            fclose(fp);
            free(buffer);
            
            clock_gettime(CLOCK_MONOTONIC, &tock);
            duration=(tock.tv_sec - tick.tv_sec);
            duration = duration + (tock.tv_nsec - tick.tv_nsec) / 1000000000.0;
            if (duration < 60.0)
                printf("Elapsed: %f seconds\n", duration);
            else if (duration >= 60.0 && duration < 60.0*60.0)
                printf("Elapsed: %f minutes\n", duration/60.0 );
            else if (duration >= 60.0*60.0)
                printf("Elapsed: %f hours\n", duration/(60.0*60.0) );
        }
        

        return 0;
    }


    int main(int argc, char **argv)
    {
        if(argc > 1 && strlen(argv[1]) > 1)
        {
            process_file(argv[1]);
        }
        else if (argc == 1)
        {
            fputs ("Please supply a valid file name for the argument.\n", stderr);
        }

        return 0;
    }