Need help debugging my code

Hey, I was presented with a problem that goes like this:

You have to find out how many blocks of the same height you can stack in a pyramid way. The "pyramid" must be built in a way that a block A on top of a block B has smaller or equal sides. You can turn the blocks to make them fit.

The site will give you an input, with a pre determined format, that is:

Quote:

---

3
100 100
1000 2000
2000 500
0

---

The first line determines how many blocks you're given (you're given n blocks), the next n lines are the sides of the block and the last line must be a zero.

There can be more that one pyramid:

Quote:

---

3
100 100
1000 2000
2000 500
6
3 4
5 7
7 5
1 5
4 4
10 2
0

---

I hope you can understand the problem I just described. If not please say.

So what I'm doing is finding the areas of the blocks and sorting them from bigger to smaller. If the block with the second biggest area has smaller or equal sides than the one with the biggest area the number of blocks in the pile increases.

If one of the sizes of the top block is bigger than the ones of the smaller one you go and compare the first with the third one and so on.

Here's the code I have so far, it's just crashing and closing. Some of the variable names in it are in portuguese, but I don't beleive that it will be difficult for you to understand the code.

Code:

---

#include <stdio.h>

int main ()
{
    FILE *fp;
    int start = 1, num, arrayX[100], arrayY[100], arrayArea[100], i, x, y, n;
    int maiorArea = -1, velhoY = 0, velhoX = 0, novoX, novoY, teste = 1, numeroBlocos;
    fp = fopen("entrada.txt", "r");
   
    if (!fp)
    {
      printf("Erro ao ler o arquivo!");
      return 1;
    }

    while (true)
    {
          if (start)
          {
              fscanf(fp, "%d", num);
             
              if (!num || feof(fp))
              {
                fclose(fp);
                return 0;
              }
               
              !start;
          } else {
              numeroBlocos = 0;
             
              for (i = 0; i < num; i++)
              {
                  fscanf(fp, "%d %d", arrayX[i], arrayY[i]);
                  arrayArea[i] = arrayX[i] * arrayY[i];
              }
             
              while (num-- > 0)
              {
                  for (n = 0; n <= i; n++)
                  {
                      if (arrayArea[n] > maiorArea && maiorArea != n)
                          maiorArea = n;
                  }
                  arrayArea[maiorArea] = 0;
                  novoX = arrayX[maiorArea];
                  novoY = arrayY[maiorArea];
                 
                  if ((velhoX == 0 && velhoY == 0) || (novoX <= velhoX && novoY <= velhoY) || (novoX <= velhoY && novoY >= velhoX))
                  {
                      velhoX = novoX;
                      velhoY = novoY;
                      numeroBlocos++;
                  }
              }
             
              printf("Teste %d\n %d\n\n", teste++, numeroBlocos);
              velhoX = velhoY = 0;
              !start;
          }
    }
    fclose(fp);
    return 0;
}

---

Oh and the output must follow this rule:

Teste n // test n (n being the pyramid id)
x // x is the number of blocks that can be stacked according to the rules
// empty line

-----------------------------------

By the way I'd like to know how do you guys debug your code... Do you disassemble it? Is there a way to debug the code in C language?

Thank you for your help.

Code:

---

fscanf(fp, "%d", num);
. . .
fscanf(fp, "%d %d", arrayX[i], arrayY[i]);

---

You aren't passing pointers to fscanf like you're supposed to.

Well then how should I pass the pointers?

Is this the correct way of reading a file line by line?

The point is that you *aren't* passing pointers, and you should be.

The proper way to read in an integer is:

Code:

---

fscanf(fp, "%d", &num);

---

The & is important as it means the difference between passing the value of the integer value num (which gets implicitly converted to a pointer), or passing the address of the variable num (which IS a pointer).

Oh, thanks for the explanation. The code is not crashing anymore.

It ain't working yet =P But atleast I can now see what's going wrong.

And as for this:

Code:

---

fscanf(fp, "%d %d", &arrayX[i], &arrayY[i]);

---

On a side note if you're using gcc, if you compile with -Wall or -pedantic, or both, you'll catch many errors that can be difficult to spot. I believe passing non-pointers to fscanf would have emitted a warning then.

Yes, any compiler should complain about this because you're doing implicit conversion from int to int* (int to pointer).
And if you'd compile it as C++ code, it simply wouldn't compile at all.

lala, do you have a link to the original problem text that I could look at?

Sure, but it's in portuguese:

http://olimpiada.ic.unicamp.br/prati...ivel2/piramide

So how did it go? Did you solve it?

Well.... I really don't understand why it's not working...

I beleive I know where the error is, just don't know what's wrong...

Code:

---

#include <stdio.h>

int main ()
{
    FILE *fp;
    int start = 1, num, arrayX[100], arrayY[100], arrayArea[100], i,n, areaMaior = 0;
    int maiorArea = -1, velhoY = 0, velhoX = 0, novoX, novoY, teste = 1, numeroBlocos, num2, nn;
    fp = fopen("entrada.txt", "r");
   
    if (!fp)
    {
      printf("Erro ao ler o arquivo!");
      return 1;
    }

    while (true)
    {
          if (start)
          {
              fscanf(fp, "&#37;d", &num);
              num2 = num;
             
              if (!num || feof(fp))
              {
                fclose(fp);
                return 0;
              }
               
              start = 0;
          } else {

              numeroBlocos = 0;
             
              for (i = 0; i < num2; i++)
              {
                  fscanf(fp, "%d %d", &arrayX[i], &arrayY[i]);
                  arrayArea[i] = arrayX[i] * arrayY[i];
                  // printf("%d*%d = %d\n", arrayX[i], arrayY[i], arrayArea[i]);
              }

              while (num-- > 0)
              {                 
                  for (n = 0; n < num2; n++)
                  {
                      printf ("%d ", arrayArea[n]);
                      if (arrayArea[n] > maiorArea)
                      {
                          maiorArea = arrayArea[n];
                          nn = n;
                      }
                  }

                  printf("\n");
                  arrayArea[nn] = 0;
                 
                  if ((velhoX == 0 && velhoY == 0) || (novoX <= velhoX && novoY <= velhoY) || (novoX <= velhoY && novoY >= velhoX))
                  {
                      velhoX = novoX;
                      velhoY = novoY;
                      numeroBlocos++;
                  }
              }
             
              printf("Teste %d\n%d\n\n", teste++, numeroBlocos);
         
              velhoX = velhoY = 0;
              maiorArea = -1;
              start = 1;
          }
    }
    fclose(fp);
    return 0;
}

---

The part in red is the part I beleive is wrong.

The code outputs: (all these numbers are there just to help finding the bug)

Quote:

---

10000 2000000 1000000
10000 0 1000000
10000 0 1000000
Teste 1
3

12 35 35 5 16 20
12 0 35 5 16 20
12 0 35 5 16 20
12 0 35 5 16 20
12 0 35 5 16 20
12 0 35 5 16 20
Teste 2
6

---

But it should output something like this:

Quote:

---

10000 2000000 1000000
10000 0 1000000
10000 0 0
Teste 1
3

12 35 35 5 16 20
12 0 35 5 16 20
12 0 0 5 16 20
12 0 0 5 16 0
12 0 0 5 0 0
0 0 0 5 0 0
Teste 2
6

---

Maybe it's because I've been working on this for a while, but I just can't the error.

Should you reset maiorArea at the start of the while (num--) loop?

Thank you! It worked, now the numbers are being removed from the array.

I'll try to make the algo work now.

I'm confused right now... I beleive I've fixed the program, and it seems to be working now, but when I submit my program to the website it tells me my solution is incorrect.

*The website gets my source file, compiles it and then runs it with some pre determined numbers and test if my program outputs the results is should output.

The site made 10 tests and I got them all wrong. I don't really know what to do right now =P
I'll post my code as it is right now, and I'd like to ask you to try out some numbers and see if the output is incorrect.

I left a line that will display the blocks that will be on the pyramid from top to bottom:

Code:

---

#include <stdio.h>

int main ()
{
    FILE *fp;
    int start = 1, num, arrayX[100], arrayY[100], arrayArea[100], i,n, areaMaior = 0;
    int maiorArea = -1, velhoY = 0, velhoX = 0, novoX, novoY, teste = 1, numeroBlocos, num2, nn;
    fp = fopen("entrada.txt", "r");
   
    if (!fp)
    {
      printf("Erro ao ler o arquivo!");
      return 1;
    }

    while (true)
    {
          if (start)
          {
              fscanf(fp, "&#37;d", &num);
              num2 = num;
             
              if (!num || feof(fp))
              {
                fclose(fp);
                return 0;
              }
             
              velhoX = velhoY = 0;
              start = 0;
          } else {

              numeroBlocos = 0;
             
              for (i = 0; i < num2; i++)
              {
                  fscanf(fp, "%d %d", &arrayX[i], &arrayY[i]);
                  arrayArea[i] = arrayX[i] * arrayY[i];
              }

              while (num--)
              {                 
                  maiorArea = -1;
                 
                  for (n = 0; n < num2; n++)
                  {
                      if (arrayArea[n] > maiorArea)
                      {
                          maiorArea = arrayArea[n];
                          nn = n;
                      }
                  }

                  arrayArea[nn] = 0;
                  novoX = arrayX[nn];
                  novoY = arrayY[nn];
                 
                  if ((velhoX == 0 && velhoY == 0) || (novoX <= velhoX && novoY <= velhoY) || (novoX <= velhoY && novoY <= velhoX))
                  {
                      velhoX = novoX;
                      velhoY = novoY;
                      numeroBlocos++;
                      printf("%d, %d\n", velhoX, velhoY);
                  }
              }

              printf("Teste %d\n%d\n\n", teste++, numeroBlocos);
         
              start = 1;
          }
    }
    fclose(fp);
    return 0;
}

---

Consider the four blocks: 10x10 (100), 6x6 (36), 5x7 (35), 3x7 (21). Your program finds the first two as a stack, and then since neither 5x7 nor 3x7 fit that's it. However, blocks 1, 3, and 4 stack nicely, meaning the answer should be 3.

A brute force algorithm could be used, but i would like to see a nice description of your own once you find one.

Lala, I have to admit, I'm a little bit of a junkie when it comes to programming problems, which is why I asked you to post a link to the problem.

Getting over the terrible altavista babelfish translation of that site, I managed to get the gist of the problem and wrote a solution. It works for all the cases. If you want to discuss the problem let me know, although I know that it would be much more satisfying if you figured it out yourself.

Google's Translator is far better than Babelfish, so you know.

Quote:

---

Originally Posted by Elysia

Yes, any compiler should complain about this because you're doing implicit conversion from int to int* (int to pointer).
And if you'd compile it as C++ code, it simply wouldn't compile at all.

---

Shure, a compiler can diagnose if parameters to the the scanf family of functions are not pointers but only if the compiler treats diagnosing this functions differently.
Generally it is impossible for the compiler to check the type of parameters that are passed to functions that use variable argument lists. Also there is no way for the compiler to know if a paramiter is an output parameter ( must be a pointer ) or an input parameter ( could be a pointer ).
Kurt

arpsmack

I'd really like to see your solution... I've been struggling with this problem for a while and haven't gotten anywhere =/

Perhaps you could just describe your algo and let me try to implement it....

BTW did you submit your solution? Did you score all points?

Dam.... I just realised... How is the site going to input my program?

There's nowhere telling me how...I'm reading from a file but how am I supposed to know if they're using a file too? And if so what's the files name?

site will redirect stdinput and output, so your program should read from stdinput and output to stdoutput

Vart

So should I start the program with something like:

Code:

---

char str[1000];
scanf("%1000s", str);

---

And then break that string into the numbers I need? Is there a way to know the length of the input?

Note that you should specify the size of your buffer - 1 to scanf because it will read the number of chars you specify. You need space for the NULL char too.
Instead of writing from a file, read chunks from stdin instead, just as if inputting info from a user.
I believe this is what it's all about.

Quote:

---

So should I start the program with something like:

---

No

Quote:

---

Is there a way to know the length of the input?

---

No, and no need.
When you read a number of blocks and it is zero - exit your main loop

So in pseudocode it will be something like

Code:

---

while(read number)
{
  if(number == 0) break;
  for(i=0;i<number;i++)
  {
      read line;
      split it in block sizes;
  }
  order blocks;
  count piramid hight and ouput it;
}

---

Thanks! Now I finally scored something =P I got 20/100 points, now I beleive the problem is only whithin my algorithm.

In case anyone wants to know:

Code:

---

#include <stdio.h>

struct caixas
{
    unsigned int x[5000];
    unsigned int y[5000];
    unsigned int area[5000]; 
};

int main (int argc, char *argv[])
{
    struct caixas caixa;
    int start = 1, num, i, n, maiorArea, velhoY = 0;
    int velhoX = 0, teste = 1, numeroBlocos, num2, nn;

    while (true)
    {
          if (start)
          {             
              if (scanf("&#37;d", &num) == EOF || !num)
                return 0;
               
              num2 = num;
              velhoX = velhoY = 0;
              start = 0;
          } else {

              numeroBlocos = 0;
             
              for (i = 0; i < num2; i++)
              {
                  scanf("%d %d", &caixa.x[i], &caixa.y[i]);
                  caixa.area[i] = caixa.x[i] * caixa.y[i];
              }

              while (num--)
              {                 
                  maiorArea = 0;

                  for (n = 0; n < num2; n++)
                  {
                      if (caixa.area[n] > maiorArea)
                      {
                          maiorArea = caixa.area[n];
                          nn = n;
                      }
                  }

                  caixa.area[nn] = 0;
                 
                  if ((!velhoX && !velhoY) || (caixa.x[nn] <= velhoX && caixa.y[nn] <= velhoY) || (caixa.x[nn] <= velhoY && caixa.y[nn] <= velhoX))
                  {
                      velhoX = caixa.x[nn];
                      velhoY = caixa.y[nn];
                      numeroBlocos++;
                  }
              }

              printf("Teste %d\n%d\n\n", teste++, numeroBlocos);
         
              start = 1;
          }
    }
    return 0;
}

---

I got one more question now though...

Since I altered the program to read from stdin I can not test it here... How do I make the input?

Just put the input set in a text file (like boxes.txt) and execute your program on the command line like this:

boxes < boxes.txt

Ok now here's a description of how I solved the problem:

Code:

---

1) Read in N (the number of boxes)
2) Read in each box's length and width into an array (I used an array of structs)
  If a box's length is less than its width, swap the two values
  (this is needed to make sorting easier)
4) Sort (in increasing order) the array of boxes by their largest dimension, if two boxes have
  the same largest dimension, sort by the sum of their dimensions
5) See the following pseudo-code:

  // stacks[n] = the number of boxes in the stack with box n at the bottom
  // This is initialized to all 1's since each box is initially in its own stack
  stacks = integer array of size N
  globalMax = 1
  for j in 1 to N-1
      localMax = stacks[j]
      for k in 0 to j-1
        if box[k] fits on top of box[j]
            localMax = max(localMax, stacks[k] + stacks[j]);
      stacks[j] = localMax
      globalMax = max(globalMax, localMax)

6) The answer is now in globalMax

Here's a basic skeleton of my program:

int main(void) {
  // declare variables

  while (1) {
      // read in N
      if (N == 0) break;

      // create an array big enough to hold N boxes (optionally you could just use
      // a statically allocated array large enough to hold the max value for N)

      // read in boxes

      // sort boxes

      // do algorithm

      // print result
  }
}

---

The algorithmic part operates in O(N^2) (approximately N^2 / 2). The sort, assuming you use a decent sorting algorithm, should take O(n log n). Is this the optimal solution? Probably not. But it works, and yes I submitted it and it gets all 100 points.

Amazing =) Thank you.

The awnser is actually much more complicated than what I had imagined :P

I'll now go and try to implement arpsmack's solution but before that I have one more problem I couldn't solve =/

This one is so easy... I'm actually ashamed for having to ask for help in this one...

He says that he'll give a list in this format:

Code:

---

4
4 5 3 1
10
9 8 7 6 1 4 3 2 12 10
0

---

He then asks you to identify where the number equals it's position in the list. The correct output would be:

Code:

---

Teste 1
3

Teste 2
10

---

So I came up with this:

Code:

---

#include <stdio.h>

int main(int argc, char *argv[])
{
    unsigned int start = 1, numero = 0, num,  c, posicao = 1, teste = 1;
    while (1)
    {
        if (scanf("&#37;d", &num) == EOF || !num)
            return 0;

        posicao = 1;
        while ((c = getc(stdin)) != '\n')
        {
            if (c == 32) // if c equals space
            {
                if (numero == posicao++)
                {
                    printf("Teste %d\n%d\n\n", teste++, posicao - 1);
                    break;
                }
                numero = 0;
            } else
                numero = numero*10 + (c - 48); // (c - 48) turns '9' into 9
          }
    }
    return 0;
}

---

Wich seemed to work, but when I submitted my solution I only got 10/50 points... Any help would be really appreciated.

Here's the link to the problem: http://olimpiada.ic.unicamp.br/prati...vel2/quermesse

c - 48
better write

c-'0' - and you do not need your comment


where do you use the num? You need it to decide that the line is over...

Also shouldn't it be 2 empty lines between tests?

vart

Quote:

---

where do you use the num? You need it to decide that the line is over...

---

I'm not using it, should I? I'm determining when line ends with this comparisson:

while ((c = getc(stdin)) != '\n')

But it could be altered if you think that's the problem...

Quote:

---

Also shouldn't it be 2 empty lines between tests?

---

I beleive the spaces are correct.

Are you guaranteed that the numbers will all be on one line?

And in any event, using the num as your loop guard will allow you to not have to read in numbers character by character.

Also, are you sure you want to do a break in your loop? You'll have to keep reading to read in the rest of the numbers. --Also a reason to use num as your loop guard.

Tabstop

I understand the problem now. Just couldn't solve it....



I came up with this, but it enters into an infinite loop:

Code:

---

#include <stdio.h>

int main(int argc, char *argv[])
{
    unsigned int start = 1, numero = 0, n,  c, posicao = 1, teste = 1;
    scanf("&#37;d", &n);
    while (n > 0)
    {
        posicao = 1;
        while (posicao <= n + 1)
        {
            c = getc(stdin);
            if (c == 32) // if c equals space
            {
                if (numero == posicao++)
                    printf("Teste %d\n%d\n\n", teste++, posicao - 1);

                numero = 0;
            } else
                numero = numero*10 + (c - '0');
        }
        scanf("%d", &n);
    }
    return 0;
}

---

Since you only process a number when you see a space, this will only work if every number (even the last one on a line) has a space after it. Hint: there is no good (or even neutral) reason to use getc in this program.

If you're given a fixed number for N, use a for loop!

Code:

---

while (1)
  // read in N

  for (i = 1; i <= N; i++)
      // read in a number (you don't need to use getc)
      // is that number equal to i?
        // yes?  -  print answer
        // no? - ignore it

---

Keep in mind though, you can't just break out of the for loop when you find the answer or you won't read in the rest of the line.

I got it! Thank you so much guys, you really helped me out here.

Here's the solution in case anyone wants it, it's so dam simple =P

Code:

---

#include <stdio.h>

int main(int argc, char *argv[])
{
    unsigned int start = 1, numero = 0, n, i, posicao = 1, teste = 1;
    scanf("&#37;d", &n);
    while (n > 0)
    {
        posicao = 1;
        for (i = 0; i < n; i++)
        {
            scanf("%d", &numero);
            if (numero == posicao++)
              printf("Teste %d\n%d\n\n", teste++, numero);
        }
        scanf("%d", &n);
    }
    return 0;
}

---