0

Pset3 won-function successfully passed this test ./fifteen 3 < ~cs50/pset3/3x3.txt only for a 3 × 3 board. For a 4x4 board the program's output is:

   1   2   3   4

   5   6   7   _

   9  10  12   8

  13  11  15  14

ftw!

The blank space is d*d. The won function contains 2 nested for-loops and inside the one long condition:

for(int i = 0; i < d; i++)
{                     
   for(int j = 0; j < d; j++)
   {
       if (i + 1 < d && i - 1 >= 0 && j + 1 <= d && j - 1 >= 0 && board[i][j - 1] ==    board[i][j] - 1 && board[i][j + 1] == board[i][j] + 1 && board[i - 1][j] == board[i][j] - d && board[i + 1][j] == board[i][j] + d)
       {
           return true;                   
       }           
   }             
}                
return false;
Improve this question
7

As correctly pointed out by Kareem it is quite confusing when you start to debug the long 'if' condition and it may also at times give you wrong answer.

I would suggest an alternative approach to such problems which require comparisons. You might want to initiate a counter that increments every time an array element matches the winning array element of a winning combination.

As pointed in the shorts, one such algorithm to determine the correct array element is board[i][j] == ( (d*i)+(j+1) ), i.e. each array element is correct if its value is equal to sum of total number of rows times current row number (row number starts from 0) and the current column number plus 1 (column number also starts from 0). If such condition occurs you can then increment your counter. In the end if the counter value matches (d*d-1) i.e. the counter has been incremented correct number of times then you can return true.

Given below is the implementation using such logic.

bool won(void)
{
    int i,j,total=0;

        for (i = 0; i < d; i++)
        {
            for (j = 0; j < d; j++)
            {
                if (board[i][j] == ( (d*i)+(j+1) ))
                {
                    total++;
                }
            }
        }

    if (total == (d*d)-1)
    { return true; }
    else
    { return false; }
}
Improve this answer
3
  • Thanks so much for pointing me in the right direction. Your comment helped me finish Fifteen! In your post you mentioned that one of the shorts covered the algorithm. Can you tell me which week and short that was? I'd like to go back and review it now. Thanks again! – user2299 Aug 27 '14 at 11:27
  • what is the name of the algorithm you reference @vatsal ? – shutdown23 Sep 6 '14 at 22:26
  • Very creative Vatsal, thanks! I was stuck thinking how I was going to iterate through the nested loops, but then how and what code would execute if the conditions were true. You thought of something to execute. ;) – Azurespot Sep 20 '14 at 17:16
4

Following your code, there are some issues.

First, it's not a good practice to have such looong line of code. It's recommended by the CS50 staff that your line shouldn't exceed 80 characters.

Second, the purpose of won() is to check whether the tiles are in ascending order followed by the blank tile. If you've tried to follow your code, or probably use gdb to figure out what is happening, you'd probably find that as soon as your long condition is evaluated to true, this function will return true and end execution no matter how many tiles are left without checking.

Third, what do you think i + 1 and j + 1 are evaluated to when i = d - 1 and j = d - 1. They're gonna be d, right? But unfortunately, d is beyond our 2-dimensional array (i.e., board). So you might run through some errors because of that too.

Lastly, try to write some pseudocode for the successful scenario of how won() should work!

You may update your answer with your pseudocode so that we can help you identify any bugs (if exist)!

Good luck!

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .