in pset3,fifteen.c

Question

When the won function is working.

check50 gives the following result:

And after intentionally making the won function wrong ,the result through check50 is:

Now,it's obvious that to win the game ,won should return true and then the main function should return 0. Then why in the first screenshot(when won function is correct)is it that check50 is expecting prompt for input after attaining winning configuration??? And in the second screenshot(when won is faulty) , why check50 is expecting return code for 0. Both the situations are contradicting..

won() function:

define _XOPEN_SOURCE 500

include

include

include

include

// constants

define DIM_MIN 3

define DIM_MAX 9

// board int board[DIM_MAX][DIM_MAX];

// dimensions int d;

int g,h;

// prototypes void clear(void); void greet(void); void init(void); void draw(void); bool move(int tile); bool won(void);

int main(int argc, string argv[]) { // ensure proper usage if (argc != 2) { printf("Usage: fifteen d\n"); return 1; }

// ensure valid dimensions
d = atoi(argv[1]);
if (d < DIM_MIN || d > DIM_MAX)
{
    printf("Board must be between %i x %i and %i x %i, inclusive.\n",
        DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX);
    return 2;
}

// open log
FILE* file = fopen("log.txt", "w");
if (file == NULL)
{
    return 3;
}

// greet user with instructions
greet();

// initialize the board
init();

// accept moves until game is won

 g = d-1;

 h = d-1;

while (true)
{
    // clear the screen
    clear();

    // draw the current state of the board
    draw();

    // log the current state of the board (for testing)
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            fprintf(file, "%i", board[i][j]);
            if (j < d - 1)
            {
                fprintf(file, "|");
            }
        }
        fprintf(file, "\n");
    }
    fflush(file);

    // check for win


    if (won())
    {
        printf("ftw!\n");
        break;
    }

    // prompt for move
    printf("Tile to move: ");
    int tile = GetInt();

    // quit if user inputs 0 (for testing)
    if (tile == 0)
    {
        break;
    }



    // log move (for testing)
    fprintf(file, "%i\n", tile);
    fflush(file);

    // move if possible, else report illegality
    if (!move(tile))
    {
        printf("\nIllegal move.\n");
        usleep(500000);
    }





    // sleep thread for animation's sake
    usleep(500000);




}

// close log
fclose(file);

// success
return 0;

}

/** * Clears screen using ANSI escape sequences. */ void clear(void) { printf("\033[2J"); printf("\033[%d;%dH", 0, 0); }

/** * Greets player. */ void greet(void) { clear(); printf("WELCOME TO GAME OF FIFTEEN\n"); usleep(2000000); }

/** * Initializes the game's board with tiles numbered 1 through d*d - 1 * (i.e., fills 2D array with values but does not actually print them).
*/ void init(void) {

if(d%2 != 0)

{ int l = (d*d) -1 ;

    for(int i =0;i<d;i++)

    {
        for(int j= 0;j<d;j++)

        {
            board[i][j] = l;

            l--;
        }
    }
} 

 else 

     {
          int l = (d*d) -1 ;

    for(int i =0;i<d;i++)

    {
        for(int j= 0;j<d;j++)

        {
            board[i][j] = l;

            l--;
        }
    }

    int temp = board[d-1][d-2];

    board[d-1][d-2] = board[d-1][d-3];

    board[d-1][d-3] = temp;

     }

}

/** * Prints the board in its current state. */ void draw(void) {

 for(int i =0;i<d;i++)

    {
        for(int j= 0;j<d;j++)

        {
            printf("%2d   ",board[i][j]); 

        }

        printf("\n");
    }

}

/** * If tile borders empty space, moves tile and returns true, else * returns false. */ bool move(int tile) {

if(tile == board[g][h+1])
{
    board[g][h+1] = 0;

    board[g][h] = tile;

h = h+1;

 return true;   


}

 else if(tile == board[g+1][h])

  {
      board[g+1][h] = 0;

      board[g][h] = tile;

    g = g+1;

     return true;

  }

    else if(tile == board[g-1][h])

   {
       board[g-1][h] = 0;

       board[g][h] = tile;

       g=g-1;

       return true;


   }

    else if(tile == board[g][h-1])

{
    board[g][h-1] = 0;

    board[g][h] = tile;

    h=h-1;

    return true;

}
else
{
    return false;


}    
}

/** * Returns true if game is won (i.e., board is in winning configuration), * else false. */ bool won(void) {

int c=0,i,j;

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


    {


        for(j= 0;j<d-1;j++)

        {
            if(board[i][j] < board[i][j+1]) 

              c++;                 
        }



      if(i != d-1) 

          {

          if (board[i][j] < board[i+1][0])

           c++;

          }        

    }
if(c == (d*d) - 2)

return true;

else

return false;

}

Answer 1

Interesting. This error is purely a logic flaw. The win() function is capable of producing false positives. This is best demonstrated with an example. If you run the following command: ./fifteen 3 <~cs50/pset3/3x3.txt it will get to a point where the table looks like this:

1 2 3
4 5 8
0 6 7

The win function will look at this and say that it is a win. The false positive results because of two interacting tests. First, the 8 will be compared to the 0, and will not increment c. BUT, 0 will be compared to 6 and will increment c, exactly offsetting the missing increment. Finally, there's no test for 0 in the last position.

So, while I was mistaken in my original answer about exactly why, the win function is indeed at fault. When I first read the win() code, I was suspicious that this could fail, but didn't dig deep enough. Now, I see what has happened. While on the surface, comparing tile a to tile b to see that one is larger than the other seems like a good idea, but as demonstrated, there are ways that it can be defeated. Wouldn't it be much more effective and safer to compare each tile to the value it should be? It should be a simple matter to compare each tile to a single variable that would increment after each test.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)