Subway system scenario

[dontpullajeff]

Hey there guys,
This scenario I am working with is supposed to be a subway system. The program is supposed to count how many ways a person can go from Station A (column/row 0) to Station L (column/row 11) without going through the same track twice. The person can however go through the same station more than once. I am using an adjacency matrix to solve this, as shown below. The rows and columns are essentially stations A through L. This compiles fine, but ends up giving me an answer in the hundreds of millions when the actual answer is 640. Any help is much appreciated, and thanks in advance!

#include <stdio.h>
int check(int grid[12][12], int row);
int change_matrix(int grid[12][12], int row, int *sum);

int
main(void)
{
        int *sum;
        int subway[12][12] =    {{0,1,0,0,0,0,0,0,0,0,0,0},
                                {1,0,1,1,1,1,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,1,1,0,0,1,1,0,0,0,0},
                                {0,1,0,0,0,0,0,1,0,0,0,0},
                                {0,0,0,0,1,0,0,0,0,0,1,0},
                                {0,0,0,0,1,1,0,0,1,1,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,1,1,1,1,0,1},
                                {0,0,0,0,0,0,0,0,0,0,1,0}};

        change_matrix(subway, 0, 0);
        printf("%d", sum);
        return 0;
}

//Checks a row in the grid for a "1" and returns the column of the first "1" it finds.
//If there is no "1" in the row, this will return the value "12"
int
check(int grid[12][12], int row)
{
        int i;

        for(i = 0; i < 12; i++){
                if(grid[i][row] == 1)
                        return i;
                else if(i == 11)
                        return 12;
                }
}

//If the position is at station L (column 11), the number of paths is increased by 1. If there
//were no other stations to go to (value of 12), then the program terminates. The program will
//then call itself again to complete the row and move on to the next station.
int
change_matrix(int grid[12][12], int row, int *sum)
{
        int col;

        col = check(grid, row);
        if(row == 11){
                sum++;
                return 0;}
        else if(col == 12)
                return 0;
        else    {grid[col][row] = 0;
                grid[row][col] = 0;
                change_matrix(grid, row, sum);
                row = col;
                change_matrix(grid, row, sum);}
}

[Zaita]

Your using a pointer to sum that's not allocated.

change:
line 8 int sum = 0;
line 46: change_matrix(int grid[12][12], int row, int &sum)

[helios]

How do you tell tracks, stations, and walls apart with a binary system? Or are walls and stations the same thing?

[guestgulkan]

Pointer problem.

I've only looked at it for obvious errors, and I see that sum is int* (pointer to int), but on line 52 you have sum++.
That will increment the pointer, not the variable it points to.
So line 52 should be (*sum)++.

On line 23 printf("%d", sum); this prints the value of the pointer
which is why you get such a large number.

(Not only that the pointer does not point to a valid integer variable - that is it
is uninitialised).

[dontpullajeff]

Thanks for the help, but now I am getting a seg fault. Saddening. My experience with seg faults is somewhat lacking, how do I fix it?

#include <stdio.h>
int check(int grid[12][12], int row);
int change_matrix(int grid[12][12], int row, int *sum);

int
main(void)
{
        int sum = 0;
        int subway[12][12] =    {{0,1,0,0,0,0,0,0,0,0,0,0},
                                {1,0,1,1,1,1,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,1,1,0,0,1,1,0,0,0,0},
                                {0,1,0,0,0,0,0,1,0,0,0,0},
                                {0,0,0,0,1,0,0,0,0,0,1,0},
                                {0,0,0,0,1,1,0,0,1,1,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,1,1,1,1,0,1},
                                {0,0,0,0,0,0,0,0,0,0,1,0}};

        change_matrix(subway, 0, 0);
        printf("%d", sum);
        return 0;
}

//Checks a row in the grid for a "1" and returns the column of the first "1" it finds.
//If there is no "1" in the row, this will return the value "12"
int
check(int grid[12][12], int row)
{
        int i;

        for(i = 0; i < 12; i++){
if(grid[i][row] == 1)
                        return i;
                else if(i == 11)
                        return 12;
                }
}

//If the position is at station L (column 11), the number of paths is increased by 1. If there
//were no other stations to go to (value of 12), then the program terminates. The program will
//then call itself again to complete the row and move on to the next station.
int
change_matrix(int grid[12][12], int row, int *sum)
{
        int col;

        col = check(grid, row);
        if(row == 11){
                (*sum)++;
                return 0;}
        else if(col == 12)
                return 0;
        else    {grid[col][row] = 0;
                grid[row][col] = 0;
                change_matrix(grid, row, sum);
                row = col;
                change_matrix(grid, row, sum);}
}

[Zaita]

Change:
Line 3 & 46: int *sum too int &sum
Line 22: change_matrix(subway, 0, sum);
Line 52: sum++;

[dontpullajeff]

Oh and each 1 in the grid represents a station connecting to the other station associated to it. (ex: col. 1 row 3 would mean that B and D are connected). A track is going from one station to another or in the opposite direction. That's why I replace 2 of the values with 0, so the person can not go back in those directions.

[dontpullajeff]

When I replace 3 and 46, it complains thus (my name is the first line, so they are moved down 1):

subway.c:4: error: expected ';', ',' or ')' before '&' token
subway.c:47: error: expected ';', ',' or ')' before '&' token

[Zaita]

Line 3 would read: int change_matrix(int grid[12][12], int row, int &sum);
Line 46: change_matrix(int grid[12][12], int row, int &sum)

[dontpullajeff]

Ya mine looks the exact same. Here's the code, see if it works with your compiler. Maybe that's the problem. I'm still getting the same error.

#include <stdio.h>
int check(int grid[12][12], int row);
int change_matrix(int grid[12][12], int row, int &sum);

int
main(void)
{
        int sum = 0;
        int subway[12][12] =    {{0,1,0,0,0,0,0,0,0,0,0,0},
                                {1,0,1,1,1,1,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,1,1,0,0,1,1,0,0,0,0},
                                {0,1,0,0,0,0,0,1,0,0,0,0},
                                {0,0,0,0,1,0,0,0,0,0,1,0},
                                {0,0,0,0,1,1,0,0,1,1,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,1,1,1,1,0,1},
                                {0,0,0,0,0,0,0,0,0,0,1,0}};

        change_matrix(subway, 0, sum);

        printf("%d", sum);
        return 0;
}

//Checks a row in the grid for a "1" and returns the column of the first "1" it finds.
//If there is no "1" in the row, this will return the value "12"
int
check(int grid[12][12], int row)
{
        int i;

        for(i = 0; i < 12; i++){
                if(grid[i][row] == 1)
                        return i;
                else if(i == 11)
                        return 12;
                }
}

//If the position is at station L (column 11), the number of paths is increased by 1. If there
//were no other stations to go to (value of 12), then the program terminates. The program will
//then call itself again to complete the row and move on to the next station.
int
change_matrix(int grid[12][12], int row, int &sum)
{
        int col;

        col = check(grid, row);
        if(row == 11){
                sum++;
                return 0;}
        else if(col == 12)
                return 0;
        else    {grid[col][row] = 0;
                grid[row][col] = 0;
                change_matrix(grid, row, sum);
                row = col;
                change_matrix(grid, row, sum);}
}

[Zaita]

Compiles with warnings that both change_matrix and check don't return a value by default. I'm using Mingw (G++ 3.4.5)

[dontpullajeff]

It may be the compiler then. Can you think of a way to do it with pointers instead of the assignment like that?

[jordanwn]

Someone is in ECS40 at UC davis!

If you're getting an answer in the millions your program is working backwards as well as forwards.

[dontpullajeff]

Haha soooo? You can take a look at it, I think it's only going forwards because it starts at the beginning and erases tracks it's been on. I'm going to the office hours later tonight.

[dontpullajeff]

Now I can get it to compile alright, but the answers are much too low. I can't seem to figure out why, but it only gives me an answer of 1. The program is supposed to explore every possible path and sum up the ones that end in column 11, station L.

#include <stdio.h>
//#include <string.h>
int check(int grid[12][12], int row);
int change_matrix(int grid[12][12], int row, int &sum);
//int print_str(int string);

int
main(void)
{
        int sum = 0;
        int subway[12][12] =    {{0,1,0,0,0,0,0,0,0,0,0,0},
                                {1,0,1,1,1,1,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,0,0,1,0,0,0,0,0,0,0},
                                {0,1,1,1,0,0,1,1,0,0,0,0},
                                {0,1,0,0,0,0,0,1,0,0,0,0},
                                {0,0,0,0,1,0,0,0,0,0,1,0},
                                {0,0,0,0,1,1,0,0,1,1,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,0,1,0,0,1,0},
                                {0,0,0,0,0,0,1,1,1,1,0,1},
                                {0,0,0,0,0,0,0,0,0,0,1,0}};

        change_matrix(subway, 0, sum);
        printf("%d\n", sum);
        return 0;
}

//Checks a row in the grid for a "1" and returns the column of the first "1" it finds.
//If there is no "1" in the row, this will return the value "12"
int
check(int grid[12][12], int row)
{
        int i;

        for(i = 0; i < 12; i++){
                if(grid[i][row] == 1){
                        printf("%d %d\n", i, row);
                        return i;}
                else if(i == 11)
                        return 12;
                }
}

//If the position is at station L (column 11), the number of paths is increased by 1. If there
//were no other stations to go to (value of 12), then the program terminates. The program will
//then call itself again to complete the row and move on to the next station.
int
change_matrix(int grid[12][12], int row, int &sum)
{
        int col;

        col = check(grid, row);
        if(row == 11){
/*              strcat(string, "11");
                print_str(string);*/
                sum++;
                return 0;}
        else if(col == 12)
                return 0;
        else    {grid[col][row] = 0;
                grid[row][col] = 0;
                change_matrix(grid, row, sum);
                change_matrix(grid, col, sum);}
        return 0;
}