Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Sep 28th, 2006, 12:59 AM   #1
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,076
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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;
}

Last edited by Sane; Sep 28th, 2006 at 1:21 AM.
Sane is online now   Reply With Quote
Old Sep 28th, 2006, 3:15 AM   #2
Polyphemus_
Expert Programmer
 
Polyphemus_'s Avatar
 
Join Date: Aug 2005
Location: Rotterdam, the Netherlands
Posts: 942
Rep Power: 4 Polyphemus_ is on a distinguished road
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
Polyphemus_ is offline   Reply With Quote
Old Sep 28th, 2006, 5:08 AM   #3
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
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'".
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Sep 28th, 2006, 5:48 AM   #4
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
Cottonpickin' edit expired. From my notions of continuity, it appears that a third pair, CE, will also break the continuity.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Sep 28th, 2006, 7:55 AM   #5
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,076
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.

Last edited by Sane; Sep 28th, 2006 at 8:12 AM.
Sane is online now   Reply With Quote
Old Sep 28th, 2006, 8:15 AM   #6
Eoin
Hobbyist Programmer
 
Eoin's Avatar
 
Join Date: Jun 2006
Location: Ireland
Posts: 152
Rep Power: 3 Eoin is on a distinguished road
I think so too, btw are the vecters one way only? I.e. left to right letter maybe?
__________________
Visit my website BinaryNotions.
Eoin is offline   Reply With Quote
Old Sep 28th, 2006, 9:24 AM   #7
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
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.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Sep 28th, 2006, 10:47 AM   #8
Polyphemus_
Expert Programmer
 
Polyphemus_'s Avatar
 
Join Date: Aug 2005
Location: Rotterdam, the Netherlands
Posts: 942
Rep Power: 4 Polyphemus_ is on a distinguished road
Quote:
Originally Posted by Sane View Post
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 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;

Last edited by Polyphemus_; Sep 28th, 2006 at 11:00 AM.
Polyphemus_ is offline   Reply With Quote
Old Sep 28th, 2006, 12:04 PM   #9
DaWei
Resident Grouch
 
DaWei's Avatar
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 DaWei is on a distinguished road
There's absolutely no need for the "**". EOF works very well.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers
DaWei is offline   Reply With Quote
Old Sep 28th, 2006, 1:09 PM   #10
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,076
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
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.

Last edited by Sane; Sep 28th, 2006 at 1:25 PM.
Sane is online now   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Simple, contrived programming exercise DaWei Coder's Corner Lounge 16 Jun 14th, 2006 11:56 AM
Critique my exercise somehollis Python 8 Jun 12th, 2006 6:18 PM
C++ exercise - need ideas of how to go about it. codylee270 C++ 34 Apr 9th, 2006 5:31 PM
Exercise C++ Exercise taken from AP Computer Science 1995 Exam, Free-response in C++. pr0gm3r C++ 4 Jul 31st, 2005 3:58 PM
Having trouble with an exercise in the C book. linuxpimp20 C 6 Jul 6th, 2005 8:22 AM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 11:57 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC