Programming Forums - An Exercise In C

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C (http://www.programmingforums.org/forum60.html)

- - An Exercise In C (http://www.programmingforums.org/showthread.php?t=11418)

An Exercise In C

All right, so I'm pretty much brand new to C. I've been learning it in class for about a week now. I finished an assignment that was to span an entire week, in a day. So now... my teacher decided to put me ahead. I plan on writing a competition for the University of Waterloo and Algonquin College.

So I learned pointers, dynamic memory allocation and reallocation, file input and output, and pointer arithmatic. But I still haven't even looked at much code on the net yet.

For an exercise, my teacher asked me to write a program from a previous competition at Waterloo. The exercise is...

Given an indefinite number of points (A-Z), and an indefinite number of lines between those points, output which line can be removed to make vector AB discontinuous. There can be none, or multiple solutions.

The data is to be stored in a data file like so:

bomb.in

AD        

AE

CE      

CF

ED

GF

BG

HB

GH

**

Now, if you draw out these vectors, you will see that removing CF, or GF will both break the continuity between AB. Therefore, the solutions are CF and GF.

This was a fun exercise to do. I got to puzzle a bit over dynamic memory allocation. I actually think I did pretty well, memory-wise, for only one prior assignment in C.

But this obviously isn't good enough. I'm going to be competing against people with years of experience in C. I still don't know some of the finer details that can take a long time to learn. I need to somehow catch up to the position where I'm 100% comfortable with what I know I need to do.

Could you please fix any stupid things my code does, or see if there are any memory leaks? Possibly tell me anything that could help me learn about the alternatives in C. I don't need any logical corrections, because it works perfectly.

Please don't just give me logical alternatives either. I know there are many ways I could have arranged the while loop while parsing the data file. Unless there's something exorbitantly inefficient, I'm most likely already aware of the ability to swap logical instructions around.

Save the previously mentioned data as "bomb.in", then run this.

#include <stdio.h>

#include <stdlib.h>



#define START_POINT 'A'

#define END_POINT 'B'



#define DATA_FILE "bomb.in"



void bombRoad(int *roads, int road, int *result, int size)

{

    // remove a road from roads

    int i;



    for (i=0; i < road; i++)

        *(result+i) = *(roads+i);

    

    for (i; *(roads+i+1); i++)

        *(result+i) = *(roads+i+1);

    

    for (i; i<size; i++)   

        *(result+i) = 0;

}



void checkRoad(int *roads, char at, int size, int *continuous)

{

    // recursively check to see if the road we destroyed made it discontinuous

    printf("."); // to see the cycles

    

    /* it's not returning int, because it needs to recurse an unknown

    number of times for each depth of recursion.

     

    so we don't return the result of recursion, we just keep spawning 

    child recurses instead. */

    

    /* roads (what used to be result in the parent function), is never

    modified. It's the newly allocated memory, result that is modified.

    

    so we don't need to worry about giving a copy of result to

    the child recurse, since it's not going to be fiddled with */

    

    int road, point, temp;

    // need to start a new var for the next recurse

    int *result;

    result = malloc(size*sizeof(int)); // allocate to _size_

        

    for (road=0; *(roads+road); road++)

    {

        for (point=0; point<2; point++) // check both points for _at_

        {

            temp = point ? *(roads+road)%256 : *(roads+road)/256; // extract the appropriate component, according to the iterator of the loop

                

            if (temp == at)

            {

                if (temp == START_POINT)

                {

                    *continuous = 1; // there was a path to the end

                    free(result);

                    return;

                }

                else

                {

                    // bomb the road

                    bombRoad(roads, road, result, size);

                    

                    // check to see if the road still works

                    checkRoad(result, point ? *(roads+road)/256 : *(roads+road)%256, size, continuous); // take the compliment of _at_

                    

                    if (*continuous) // if the apex of recursion found continuity

                      break; // we can now exit, don't bother starting any more child functions

                }

            }

        }

        if (*continuous)

          break; // exit the nested loop to follow the intent of prior-mentioned break statement

    }

    

    free(result); // out of roads to travel down, we can now free up memory

}



void bomb(int *roads, int size)

{

    int *result;

    int road, continuous;

    

    for (road = 0; *(roads+road); road++)

    {

        printf("%c%c ", *(roads+road)/256, *(roads+road)%256);

        

        result = malloc(size*sizeof(int)); // allocate to _size_

        

        // bomb the road 

        bombRoad(roads, road, result, size);

        

        // check to see if the road still works

        continuous = 0;

        checkRoad(result, END_POINT, size, &continuous);

        if (continuous)

            printf(" No\n");

        else

            printf(" Will break continuity!\n");

            

        free(result); // it is done being used, so free it

        // don't free roads, it's being freed in the parent function

    }   

    printf("\n");

}



int main()

{

    printf(""); // I sometimes need to clear the output stream

    

    char buf[2]; // one for one character, one for the null terminator fgets adds

    int size;

    int *roads;

    FILE *stream;

    

    roads = malloc(sizeof(int));

    stream = fopen(DATA_FILE, "r");

    

    size = 0;

    while (1) 

    {

        fgets(buf,sizeof(buf),stream);

        *(roads+size) = buf[0]*256;     // store in hex to make memory managing more simple



        fgets(buf,sizeof(buf),stream);  // ...manage only one chunk, instead of a struct, or array

        *(roads+size) += buf[0];

        

        if (*(roads+size) == 10794) // two asterisks, 42*256 + 42

            break;

        else

        {

            while (buf[0] != '\n') fgets(buf,sizeof(buf),stream); // find the next line



            size ++;

            roads = realloc(roads, (size+1)*sizeof(int)); // reallocate one ahead to avoid over-writing previously declared data

        }

    }

    fclose(stream);

    *(roads+size) = 0; // over-write the two asterisks with a 0

    

    bomb(roads, size);

    free(roads);



    system("PAUSE");

    return 0;

}

Ok, your code has some weird thingies, which I will post this afternoon as I have not much time right now ;). First things first, your memory management. In your main loop, you are constantly re-allocating your roads array. When allocating data, a piece of memory is searched which is big enough to use as the array with the desired size. The process of finding this takes some time (not that much, but it does).
A better way of doing what you want is by starting the array with a size of 16, and when you have over 16 entries you increase its size with 16 again, etcetera. Another way would be looping through the file twice - the first time to count the number of lines, then you allocate the array, and finally you populate the array with the actual content of the file.

Another thing in your main loop is where you read and parse the content. You are doing things way too difficult there, and a little unreliable:

        fgets(buf,sizeof(buf),stream);   // Why not read the line at once? Besides that, if you are reading one character at a time I would personally use getchar.

        *(roads+size) = buf[0]*256;     // A structure would be easier.



        fgets(buf,sizeof(buf),stream);  // 

        *(roads+size) += buf[0]; //

        

        if (*(roads+size) == 10794) // two asterisks, 42*256 + 42 <- An unreliable comparison, buf[0] could always contain some weird values which happen to equal your comparison value.

            break;

        else

        {

            while (buf[0] != '\n')

              fgets(buf,sizeof(buf),stream); // find the next line



            size ++;

            roads = realloc(roads, (size+1)*sizeof(int)); // OK, realloc thing I mentioned earlier

        }



        // You never check for the end of file - what if the file doesn't end with two asterixes?

OK, really gotta go now - I'll post my approach this afternoon ;)

Even if your code doesn't have egregious errors, if you don't want ideas about honing the logic, you aren't going to survive against experienced people. Just a thought. Recall my old signature, "Functionality rules, clarity matters; if you can work a little elegance in there, you're stylin'".

Cottonpickin' edit expired. From my notions of continuity, it appears that a third pair, CE, will also break the continuity.

Polyphemus: No, it needs to be constantly reallocated. If you look at what's happening to it. Each child recurse of checkRoad will modify "roads" differently. Therefore, each recurse needs a copy, and not an address. If you follow it closely, you'll see it's allocating everything it needs. But I think, if you're talking about the allocation in "bomb"'s loop, I probably could take that out. Since that argument does not get modified by checkRoad. And the reason I parse so tediously, is to filter out the garbage. Like white space after each vector. Regardless, there is probably a better way to do it. Like I said, I've never really looked at other people's C code... haha.

DaWei: Are you positive? The solution on the actual contest listed only the two vectors I mentioned.

I think so too, btw are the vecters one way only? I.e. left to right letter maybe?

A, D, and E are the vertices of a triangle at one end. G, B, and H are the vertices of a triangle at the other end. The sides of the triangles are the vectors. E is connected to G through vectors EC, CF, and FG. Remove any of those, you break continuity between A and B.

I haven't even looked at the code, but it looks like too much; particularly given recursion.

Quote:

Originally Posted by Sane (Post 115178)

I was talking about the file-read-loop. There are no calls to other functions there. I don't mean you shouldn't reallocate at all - I mean you shouldn't reallocate 4 bytes more at a time - make bigger steps.

And, as promised:

    define struct {

        char a,

        char b

    } vector;



    char buf[16];

    vector *roads = malloc(16 * sizeof(vector);

    int size = 0;



    while (!feof(stream)) {

        fgets(buf, sizeof(buf), stream); // Get a whole line from the file



        if(strncmp(buf, "**", 2) == 0)

            break;



        roads[size].a = buf[0];

        roads[size].b = buf[1];

        

        size++;

        if((size & 0xF) == 0) {

            roads = realloc(roads, (size + 0xF) * sizeof(vector));

        }

    }

Dunno if this code compiles, don't know whether it is bug free either - it's just some sample code.

EDIT:
Small note:

temp = point ? *(roads+road)%256 : *(roads+road)/256; // extract the appropriate component, according to the iterator of the loop

The code above is usually done using bitshifting, which is a little faster and looks cleaner:

temp = point ? roads[road] & 0xFF : roads[road] >> 8;

though using my code, it would be even easier:

temp = point ? roads[road].a : roads[road].b;

There's absolutely no need for the "**". EOF works very well.

Wow... NOTE : I can't believe I missed this... I left out line "AC" in the first post. That's why you have a conflicting answer. Without AC, all of these lines caused discontinuity: AD, AE, CE, CF and GF. Sorry about that. That would explain why my program might not have outputted the "correct" answers for anyone who tried to compile it.

@DaWei: Yes, it needs to end with '**'. It was in the actual question.

And it's pretty short for what it's doing. The comments take up a bit of space. Try to program it, or at least the pseudo code, it has to do quite a bit, and a lot of memory copying.

@Eoin: Maybe I should have called them lines. They can go both ways.

@Polyphemus_: Thanks for the tips. I tried to use a structure initially, but was having problems dynamically allocating the memory for it. I should have thought about that bit shifting, so obvious, gah. I also didn't know there was code that retrieved a whole line at once, that's a much better idea. Thanks.