0
I am working on a recursive code that increases a variable every time I find a solution to my problem (I do not think it is relevant or necessary to explain the problem in question).
Now, the output of my program is supposed to print that counter with the number of solutions.
I’ve already managed to get you to give the right answer. However when removing the printf I had to debug, I realized that if I removed them all, the final result would be 0. After a little more research I realized that I have to have printf("\n\n"); recursive function to print the expected output.
Any reason more general?
EDIT:
already figured out what was giving the bug. there is a part where I am declaring an array int rectLOCAL[8]; but I didn’t start the 0 as I was supposed to, so I was having trouble comparing the next cycle.
By putting memset(rectLOCAL,0,8*sizeof(int)); already makes the code work as expected.
Follows the code:
/*
_____ ____ _____ _____
| | | | | |
| 1 | | | 1 | 2 |
| | | |_____|_____|
----- 3 | | 3 |
| | | |___________|
| 2 | |
|_____|____|
___________
____ _____ | 3 |
| | | |_____ _____|
| | 1 | | | |
| | | | 1 | 2 |
| 3 ----- |_____|_____|
| | |
| | 2 |
|____|_____|
*/
/*
Description
Fitting rectangles is a game where the player is given a set of small rectangles and needs to create a large
rectangle, using all small rectangles exactly once.
For example, if the player is given the following 3 small rectangles: 1,2,3 seen above
A few possible ways to make a large rectangle would be: the 4 combinations above
Your task is to find out how many distinct configurations there are to create a large rectangle given the list
of small rectangles.
DISTINCT* por exemplo se o rectangulo 1 e 2 estiverem trocados não conta como +1 solução.
Two configurations are not distinct if, by removing the indices of the small rectangles, we are not able to
visually distinguish them; this is the case for configurations A and D.
Note that you can rotate rectangles, as can be seen in configuration C
Input
Each test case starts with a line with an integer 1 ≤ n ≤ 8, the number of small rectangles.
The following n lines contain two integers each, w i and h i , the width and height of the ith rectangle
respectively, 1 ≤ i ≤ n .
Output
For each test case, print the number of distinct configurations, it is guaranteed that no more than 10000
solutions exist.
Example
Example input:
3
40 120
50 60
50 60
Example output:
4
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <unistd.h>
/*
rectSizes[][0] -- x
rectSizes[][1] -- y
rectSizes[][2] -- se esta ocupado
*/
int rectSizes[8][3];
int referenceP[9][2];
int nRect;
int rect;
int areaMax;
int teste;
int flagRepetidos;
int placeRect(int mode, int x, int y, int rect, int refPoints[9][2],int RefPoints, int xMax, int yMax);
/*coloca os rectangulos
x,y é o ponto a apagar
rect é o rectangulo a ser ocupado
refPoints atualiza a cada chamada de recursão
o numero max de pontos de ref é nrect+1
*/
int allOcupied(){
int i;
for (i = 0; i<nRect; i++){
if (rectSizes[i][2]==0){
return 0;
}
}
return 1;
}
/*verifica se os rectangulos ja foram todos usados*/
int checkRP(int refPoints[9][2]){
int i;
int counter=0;
/*printf("A verificar PR:\n");*/
for(i=0; i<9;i++){
if(refPoints[i][0]!=0 || refPoints[i][1]!=0){
counter++;
}
}
if (counter==2){
return 1;
}
return 0;
}
/*devolve o index do ponto de referencia seguinte
x,y são os pontos do ponto de referencia a passar
devolve -1 se o ponto de referencia estiver num eixo
*/
int RPdepois(int RP[9][2], int x,int y,int xMax){
int j;
int ponto = -1;
int minX = xMax;
for(j=0;j<9;j++){
if(RP[j][0] == 0 && RP[j][1]==0){break;}
if(RP[j][0] == x && RP[j][1]==y){continue;}
if((RP[j][0]-x)>0 && (RP[j][0]-x)<=minX){
minX = (RP[j][0]-x);
ponto = j;
}
}
return ponto;
}
/*devolve o index do ponto ponto de referencia anterior
x,y são os pontos do ponto de referencia a passar
devolve -1 se o ponto de referencia estiver num eixo
*/
int RPantes(int RP[9][2], int x, int y,int yMax){
int j;
int ponto = -1;
int minY = yMax;
for(j=0;j<9;j++){
if((RP[j][0] == 0 && RP[j][1]==0)){break;}
if((RP[j][0] == x && RP[j][1]==y)){continue;}
if((RP[j][1]-y)>0 && (RP[j][1]-y)<=minY){
minY = (RP[j][1]-y);
ponto = j;
}
}
return ponto;
}
/*faz update do Ymax e Xmax*/
int updatexMax(int h, int w, int x, int y, int xMax){
int l = xMax;
if(l < x+w){
l = x+w;
}
return l;
}
int updateyMax(int h, int w, int x, int y, int yMax){
int l = yMax;
if(l < y+h){
l = y+h;
}
return l;
}
int placeRect(int mode, int x, int y, int rect, int refPoints[9][2],int RefPoints, int xMax, int yMax){
int k = 0;
int j;
int RP[9][2];
int ymaxlocal = yMax;
int xmaxlocal = xMax;
int temp;
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
memcpy(RP, refPoints,18*sizeof(int));
rectSizes[rect][2] = 1;
/*actualiza os maximos X ou Y caso seja necessario*/
xmaxlocal = updatexMax(rectSizes[rect][1], rectSizes[rect][0], x, y, xmaxlocal);
ymaxlocal = updateyMax(rectSizes[rect][1], rectSizes[rect][0], x, y, ymaxlocal);
/* Caso a area com os x,y maximos ultrapasse a area maxima possivel para os rectangulos dados, volta de imediato atras*/
if (areaMax<xmaxlocal*ymaxlocal){
rectSizes[rect][2] = 0;
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
return 0;
}
if(RP[0][0] == 0 && RP[0][1] == 0){
RP[0][0] = rectSizes[rect][0];
RP[1][1] = rectSizes[rect][1];
RefPoints++;
}
else{
while((RP[k][1] != 0) || (RP[k][0] != 0)){
if(RP[k][1] == y && RP[k][0] == x){
int index1 = RPantes(RP, x, y, ymaxlocal);
int index2 = RPdepois(RP, x, y, xmaxlocal);
int height = rectSizes[rect][1];
int width = rectSizes[rect][0];
/*remove ponto de ref e adiciona dois*/
if(RP[k][1] == 0){
if ((RP[k][1]+height) == RP[index1][1]){
RP[k][0] += width;
}
else{
RP[RefPoints][0] = RP[k][0]+rectSizes[rect][0];
RP[RefPoints][1] = RP[k][1];
RP[k][1] += rectSizes[rect][1];
RefPoints++;
}
}
else if(RP[k][0] == 0){
if ((RP[k][0]+width) == RP[index2][0]){
RP[k][1] += height;
}
else{
RP[RefPoints][0] = RP[k][0];
RP[RefPoints][1] = rectSizes[rect][1]+RP[k][1];
RP[k][0] += rectSizes[rect][0];
RefPoints++;
}
}
else{
if(((RP[k][0]+width) == RP[index2][0]) && ((RP[k][1]+height) == RP[index1][1])){
RP[k][1] = 0;
RP[k][0] = 0;
RefPoints--;
}
else if ((RP[k][0]+width) == RP[index2][0]){
RP[k][1] += height;
}
else if ((RP[k][1]+height) == RP[index1][1]){
RP[k][0] += width;
}
else{
RP[k][1] += rectSizes[rect][1];
RP[RefPoints][1] = RP[k][1];
RP[RefPoints][0] = RP[k][0]+rectSizes[rect][0];
RefPoints++;
}
}
break;
}
k++;
}
}
/*condicao de paragem*/
if (allOcupied()){
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
if (areaMax==xmaxlocal*ymaxlocal && checkRP(RP)){
teste+=1;
rectSizes[rect][2] = 0;
return 0;
}
else{
rectSizes[rect][2] = 0;
return 0;
}
}
/* vamos fazer apenas para o caso onde o rectangulo posto é mais pequeno ou igual ou anterior*/
int rectLOCAL[8];
/*EDIT*/
memset(rectLOCAL,0,8*sizeof(int));
int p;
int q;
int flagA;
int flagB;
int mode1b;
int mode1a;
int flag;
int o;
for(j=0;j<nRect;j++){
flag = 0;
if(rectSizes[j][2] == 1){continue;}
/*sem este ciclo, o resultado passa a dar mal no entanto não se altera com a presença do \n*/
for(o=0;o<nRect;o++)
{
if(o==j){
continue;
}
if(rectLOCAL[o]==1){
if((rectSizes[o][0] == rectSizes[j][0] && rectSizes[o][1] == rectSizes[j][1]) || (rectSizes[o][0] == rectSizes[j][1] && rectSizes[o][1] == rectSizes[j][0])){
flag =1;
break;
}
}
}
if(flag==1){continue;}
rectLOCAL[j]=1;
for(k=0;k<RefPoints;k++){
flagA = 0;
flagB = 0;
mode1b = 0;
mode1a = 0;
/*
q index do ponto de referencia anterior ao ponto de referencia x,y
p index do ponto de referencia seguinte ao ponto de referencia x,y
*/
p = RPdepois(RP,RP[k][0],RP[k][1], xmaxlocal);
q = RPantes(RP,RP[k][0],RP[k][1], ymaxlocal);
if(p==-1){
flagA = 1;
}
else {
if(RP[k][0]+rectSizes[j][0] <= RP[p][0]){
mode1a = 1;
flagA = 1;
}
if(RP[k][0]+rectSizes[j][1] <= RP[p][0]){
mode1b = 1;
flagA = 1;
}
}
if(q==-1){
flagB = 1;
}
else{
if(RP[k][1]+rectSizes[j][1] <= RP[q][1]){
mode1a = 1;
flagB = 1;
}
if(RP[k][1]+rectSizes[j][0] <= RP[q][1]){
mode1b = 1;
flagB = 1;
}
}
/*verifica se o rectangulo fica mais alto/comprido do que os rectangulos à sua volta
e caso seja passa o caso à frente*/
if(flagA==1 && flagB==1){
/*caso esteja a ser testado com as coordenadas invertidas*/
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
/*verifica se é um quadrado*/
if(rectSizes[j][0] != rectSizes[j][1]){
if(mode1a==1){placeRect(0,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);}
if(mode1b==1){placeRect(1,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);}
}
else{
/* se for um quadrado só precisa de executar uma vez*/
placeRect(0,RP[k][0],RP[k][1],j,RP,RefPoints,xmaxlocal,ymaxlocal);
}
}
if(mode == 1){
temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;
}
}
}
if(mode == 1){temp = rectSizes[rect][0];
rectSizes[rect][0] = rectSizes[rect][1];
rectSizes[rect][1] = temp;}
rectSizes[rect][2] = 0;
return 0;
}
int main(void)
{
int i;
int rp[9][2];
int o;
memcpy(rp, referenceP,18*sizeof(int));
scanf("%d", &nRect);
int temp;
for(i=0; i<nRect;i++)
{
scanf("%d %d", &rectSizes[i][0],&rectSizes[i][1]);
if(rectSizes[i][0]<rectSizes[i][1]){
temp = rectSizes[i][0];
rectSizes[i][0] = rectSizes[i][1];
rectSizes[i][1] = temp;
}
/*calcular area para saber area maxima*/
areaMax+=rectSizes[i][0]*rectSizes[i][1];
}
for(i=0; i<nRect;i++)
{
for(o=0;o<i;o++){
if(i==o){continue;}
if((rectSizes[o][0] == rectSizes[i][0] && rectSizes[o][1] == rectSizes[i][1]) || (rectSizes[o][0] == rectSizes[i][1] && rectSizes[o][1] == rectSizes[i][0]) ){
flagRepetidos = 1;
}
}
if(flagRepetidos==1){
flagRepetidos = 0;
continue;
}
if(rectSizes[i][0] == rectSizes[i][1]){;
placeRect(0,0,0,i,rp,1,0,0);
}
else{
placeRect(0,0,0,i,rp,1,0,0);
placeRect(1,0,0,i,rp,1,0,0);
}
}
printf("%d\n",teste);
return 0;
}
Joaquim, difficult to say something without seeing the code. Edits the question by placing the snippet of the code that is in trouble.
– Pedro Gaspar
The problem is, I don’t know which specific place is in trouble, other than the printf.. if you do not have a printf(" n") inside the recursive function (has 300 lines this function), it does not return the expected output. print can be anywhere as long as it is executed at least once within each recursive call.
– Joaquim Carvalho
What is the purpose of this recursive function, and what kind of result does it return? You make other calls to the function
printf()in this function? What is the purpose of these calls toprintf()? It is only for debug the function or is part of the purpose of it?– Pedro Gaspar
The recursive function returns an integer that is not crucial, as it is not being saved for anything. however when finding a solution to the problem increases a global variable, this variable being the output of the program. the objectives of the prints are purely DEBUG. The unico output of the program must be an integer, and the printf of that integer is in the main.
– Joaquim Carvalho
You have an example of the expected output, and an example of the wrong output (when taking
printf(\n\n)of the recursive function)?– Pedro Gaspar
I already put a link to the ghostbin with the code and with explanations of where the problem is.
– Joaquim Carvalho
https://ghostbin.com/paste/hzey5 here it is. I have tried to explain the explanation as best as possible in English, I hope it is not a problem. Problematic print is on line 230
– Joaquim Carvalho
I took a look at the code and I couldn’t identify anything that could cause this behavior, it doesn’t make any sense, does it? What happens to thresh the code step by step, when you take the
printf("\n\n)offensive?– Pedro Gaspar
when debugging the code I put prints with n making the printf(" n n") "Useless", because they are called two n inside the recursive function, so I noticed, no matter where they are, since they are called the n 2x inside the recursive function.
– Joaquim Carvalho
after a little more investigation I discovered that if I remove the part of the code of the lines 451-465, in the link I sent, the n stops affecting the final result.
– Joaquim Carvalho
I advise you to try to minimize the code as much as possible by removing all commented code and irrelevant comments, and put it to the question. Preferably focusing and highlighting the function with the problem, explaining which result it gives with and without the
printf. Otherwise I don’t see how I can ever get an answer to your question. Remember that you should try as hard as possible to make it easy for people who pass by in your question to answer it.– Isac
I’ve already edited the code in the ghostbin, cleaned up unnecessary comments and tried to make it perceptible the place that’s giving me trouble
– Joaquim Carvalho
Joaquim, the whole situation is really sinister. I ran the program using that example input (3 -> 40 120 -> 50 60 -> 50 60), and, leaving the
printf("\n\n")within the recursive function, the result was 2, if I comment on theprintfthe result is 3. I also put a counter in the recursive function and noticed that with theprintfthe recursive function is executed 26 times and without theprintfthe same function is executed 36 times. And, indeed, if the code snippet between the lines 451 and 465 is commented, the result is always the same, with or withoutprintf.– Pedro Gaspar
But at no time was the result 4, as described in the example. And I noticed that the
printfdoesn’t have to be specificallyprintf("\n\n"), I put aprintf("count: %d", count), to display the counter, and also had the same behavior of theprintf("\n\n").– Pedro Gaspar
I’m glad you found out about the problem, Joaquim. But for me it follows the mystery of why
printfchanged the output of the function. Is it because when theprintfwas called, internally it copied values to the memory, which would be coincidentally the location of the memory that would be used by its uninitialized array?– Pedro Gaspar
Yeah, I honestly have no idea either. Running my program with Valgrind he accused Conditional jumps or moves... was the only tip I had
– Joaquim Carvalho