101 - The Blocks Problem

[chinaluoqi]

Can someone help me out?
My program get a WA, but it works well with the sample input.
I'm a newbie here.
Thanks.


[cpp]
#include <iostream>
#include <memory>
#include <string>
using namespace std;

int _a [25] [25];
int _na [25];
int n;

void Return (int pos, int ord)
{
// assume : the card is on the top
int ace = _a [pos] [ord];
_a [ace] [_na [ace] ] = ace;
_na [ace] ++;
_na [pos] --;
}

void ReturnAll (int pos, int ord)
{
int i;
for (i = _na [pos] - 1; i >= ord; i--)
Return (pos, i);
}

void MoveAll (int posA, int ordA, int posB, int ordB)
{
int i;
for (i=ordA; i < _na [posA]; i ++)
{
_a [posB] [_na[posB] ] = _a [posA] ;
_na [posB] ++;
}
_na [posA] = ordA;
}

void Get (int ace, int& pos, int& ord)
{
for (pos = 0; pos < n; pos ++)
for (ord = 0; ord < _na [pos]; ord ++)
{
if (ace == _a [pos] [ord]) return;
}
}

main()
{
int op, a, b, i, j;
string word;
cin >> n;
for (i = 0; i < n; i++)
{
_na = 1;
_a [0] = i;
}
while (cin >> word, word != "quit")
{
op = 0;
if (word == "pile") op += 2;
cin >> a >> word >> b;
if (word == "over") op += 1;
// execute the operation
int posA, ordA, posB, ordB;
Get (a, posA, ordA);
Get (b, posB, ordB);
if (posA == posB) continue;
if (op & 1 == 0)
ReturnAll (posB, ordB + 1);
if (op & 2 == 0)
ReturnAll (posA, ordA + 1);
MoveAll (posA, ordA, posB, ordB);
}
// output
for (i = 0; i < n; i++)
{
cout << i << ':';
for (j = 0; j < _na ; j++)
cout << ' ' << _a [j];
cout << endl;
}
}
[/cpp]

[epsilon0]

i compiled and tested your program, and it doesn't work.

i could notice that:

"move" behaves like "pile"
"onto" behaves like "over"

the problem is perhaps in your Return function....
i didn't take time to understand how you store the blocks info, but it seems that u forget to delete the blocks when u return them? the weird thing is that blocks don't seem to duplicate like they would if you did such an error...

anyway you know what's wrong, now go fix it

[epsilon0]

if (!(op%2))
ReturnAll (posB, ordB + 1);
if (op<2)
ReturnAll (posA, ordA + 1);

i changed this and recompiled and now it works... dunno what was wrong with your '&' tests...

[epsilon0]

if ((op & 1) == 0)
ReturnAll (posB, ordB + 1);
if ((op & 2) == 0)
ReturnAll (posA, ordA + 1);

see, this works. your error was lack of parenthesis.

because it seems '==' has a higher precedence priority than '&'

so 1 == 0 was evaluated to 0 and then op & 0 was always 0 of course. so both tests were always FALSE and the ReturnAll function was never called. thus the problem you had.

i always use parenthesis when i'm unsure. because as you can see, the prcedence of operators is sometimes counter-intuitive, like this is the case here. take my advice and do the same.

[chinaluoqi]

Thank you. I think I have got you idea.
After I added the '(' & ')', my program did every thing well.
Thank you very much, my friend.

[veena]

Could someone kindly tell me how to test for 101 without using fopen, but just using scanf? I can't go furthur than "move 9 onto 1" on the command prompt.

Thanks a lot and Have a nice day,

veena.

[Dominik Michniewski]

1) write input commands into file, i.e. input.txt
2) run your program in this way, i.e. p101.exe <input.txt >output.txt
3) results are in output.txt

It's working under Windows and Unix (any I think) ...
You can use only scanf/printf as IO method (without fopen, fclose and so on) ....

Best regards
Dominik

[SilVer DirectXer]

[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>

int world[25][25];
int num_o_b;
char command1[6],command2[6];
int com_1,com_2;
void getcommand1(void);
void getcommand2(void);
void move_over(void);
void move_onto(void);
void pile_onto(void);
void pile_over(void);
void cleantop(int);
void display(void);
int findtop(int X);
int checkdo(void);


void main(void)
{
int i,j,result,do_or_not=0;
char dummy;

cin>>num_o_b;

for (i=0;i<num_o_b;i++)
for (j=0;j<num_o_b;j++)
world[j]=-1;
for (i=0;i<num_o_b;i++)
world[0]=i;

while (1)
{

getcommand1();
result=strcmp("quit",command1);
if (result==0)
break;
scanf("%d",&com_1);
scanf("%c",&dummy);
getcommand2();
scanf("%d",&com_2);
scanf("%c",&dummy);
do_or_not=checkdo();
if (do_or_not!=1)
{
pile_over();
pile_onto();
move_over();
move_onto();
}


}

display();

}

void getcommand1(void)
{
int k=0;
while(1)
{
command1[k++]=getchar();
if (command1[k-1]=='\n' || command1[k-1]==' ')
break;
}
command1[k-1]='\0';

}

void getcommand2(void)
{
int k=0;
while(1)
{
command2[k++]=getchar();
if (command2[k-1]=='\n' || command2[k-1]==' ')
break;
}
command2[k-1]='\0';

}

void move_onto(void)
{
int i,j,Y1,X1,X2,Y2,result1,result2;
result1=strcmp("move",command1);
result2=strcmp("onto",command2);
if (result1==0 && result2==0)
{
cleantop(com_1);
cleantop(com_2);

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_1 && j!=num_o_b)
break;
if (world[j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_2 && j!=num_o_b)
break;
if (world[j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;

world[X2][Y2+1]=com_1;
world[X1][Y1]=-1;



}
}
void move_over(void)
{
int Y1,X1,i,j,result1,result2,top,X2,Y2;
result1=strcmp("move",command1);
result2=strcmp("over",command2);
if (result1==0 && result2==0)
{
cleantop(com_1);
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_1 && j!=num_o_b)
break;
if (world[j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_2 && j!=num_o_b)
break;
if (world[j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;

top=findtop(X2);
world[X2][top]=world[X1][Y1];
world[X1][Y1]=-1;


}
}

void pile_onto(void)
{
int Y2,X2,i,j,result1,result2,X1,Y1,top1,top2;
result1=strcmp("pile",command1);
result2=strcmp("onto",command2);
if (result1==0 && result2==0)
{
cleantop(com_2);
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_2 && j!=num_o_b)
break;
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_1 && j!=num_o_b)
break;
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

top1=findtop(X1);
top2=findtop(X2);
for (i=0;i<top1-Y1;i++)
{
world[X2][top2+i]=world[X1][Y1+i];
world[X1][Y1+i]=-1;
}

}

}

void pile_over(void)
{
int result1,result2,X1,X2,Y1,Y2,i,j,top1,top2;
result1=strcmp("pile",command1);
result2=strcmp("over",command2);
if (result1==0 && result2==0)
{
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_2 && j!=num_o_b)
break;
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_1 && j!=num_o_b)
break;
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

top1=findtop(X1);
top2=findtop(X2);

for (i=0;i<top1-Y1;i++)
{
world[X2][top2+i]=world[X1][Y1+i];
world[X1][Y1+i]=-1;
}
}
}

void cleantop(int num)
{
int i,j,k,X,Y;

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==num && j!=num_o_b)
break;
}
if (world[i][j]==num && j!=num_o_b)
break;
}

X=i;
Y=j;
k=j;
while (world[X][++j]!=-1)
{
world[world[X][j]][0]=world[X][j];
world[X][j]=-1;
}

}

void display(void)
{
int i,j;
for (i=0;i<num_o_b;i++)
{
cout<<i<<":";
for (j=0;j<num_o_b;j++)
if (world[i][j]!=-1)
cout<<" "<<world[i][j];
cout<<"\n";
}
}

int findtop(int X)
{
int i,j,k;

for (j=0;j<num_o_b;j++)
if(world[X][j]==-1)
break;

return j;
}

int checkdo(void)
{
int i,j,X1,X2;

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
if (world[i][j]==com_1 && j!=num_o_b)
break;
}

X1=i;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
if (world[i][j]==com_2 && j!=num_o_b)
break;
}

X2=i;
if (X1==X2)
return 1;
return 0;
}

[/cpp]
Help....run time error, what's wrong?

[Dominik Michniewski]

Are you sure that you in proper way handle incorrect commands, like "pile 1000 over 300" ?

Maybe this help you ....

Dominik

[SilVer DirectXer]

thanks u so much !

[SilVer DirectXer]

i edited the code so that it can ignore the num that is not at the range.
However, run time error still occur....
can any one help me to see see which case it will make a run time error?
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <string.h>

int world[30][30];
int num_o_b;
char command1[6],command2[6];
int com_1,com_2;
void getcommand1(void);
void getcommand2(void);
void move_over(void);
void move_onto(void);
void pile_onto(void);
void pile_over(void);
void cleantop(int);
void display(void);
int findtop(int X);
int checkdo(void);


void main(void)
{
int i,j,result,do_or_not=0;
char dummy;

cin>>num_o_b;

for (i=0;i<num_o_b;i++)
for (j=0;j<num_o_b;j++)
world[j]=-1;
for (i=0;i<num_o_b;i++)
world[0]=i;

while (1)
{

getcommand1();
result=strcmp("quit",command1);
if (result==0)
break;
scanf("%d",&com_1);
scanf("%c",&dummy);
getcommand2();
scanf("%d",&com_2);
scanf("%c",&dummy);
do_or_not=checkdo();
if (do_or_not!=1)
{
pile_over();
pile_onto();
move_over();
move_onto();
}


}

display();

}

void getcommand1(void)
{
int k=0;
while(1)
{
command1[k++]=getchar();
if (command1[k-1]=='\n' || command1[k-1]==' ')
break;
}
command1[k-1]='\0';

}

void getcommand2(void)
{
int k=0;
while(1)
{
command2[k++]=getchar();
if (command2[k-1]=='\n' || command2[k-1]==' ')
break;
}
command2[k-1]='\0';

}

void move_onto(void)
{
int i,j,Y1,X1,X2,Y2,result1,result2;
result1=strcmp("move",command1);
result2=strcmp("onto",command2);
if (result1==0 && result2==0)
{
cleantop(com_1);
cleantop(com_2);

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_1 && j!=num_o_b)
break;
if (world[j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_2 && j!=num_o_b)
break;
if (world[j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;

world[X2][Y2+1]=com_1;
world[X1][Y1]=-1;



}
}
void move_over(void)
{
int Y1,X1,i,j,result1,result2,top,X2,Y2;
result1=strcmp("move",command1);
result2=strcmp("over",command2);
if (result1==0 && result2==0)
{
cleantop(com_1);
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_1 && j!=num_o_b)
break;
if (world[j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[j]==com_2 && j!=num_o_b)
break;
if (world[j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;

top=findtop(X2);
world[X2][top]=world[X1][Y1];
world[X1][Y1]=-1;


}
}

void pile_onto(void)
{
int Y2,X2,i,j,result1,result2,X1,Y1,top1,top2;
result1=strcmp("pile",command1);
result2=strcmp("onto",command2);
if (result1==0 && result2==0)
{
cleantop(com_2);
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_2 && j!=num_o_b)
break;
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_1 && j!=num_o_b)
break;
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

top1=findtop(X1);
top2=findtop(X2);
for (i=0;i<top1-Y1;i++)
{
world[X2][top2+i]=world[X1][Y1+i];
world[X1][Y1+i]=-1;
}

}

}

void pile_over(void)
{
int result1,result2,X1,X2,Y1,Y2,i,j,top1,top2;
result1=strcmp("pile",command1);
result2=strcmp("over",command2);
if (result1==0 && result2==0)
{
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_2 && j!=num_o_b)
break;
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
X2=i;
Y2=j;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
if (world[i][j]==com_1 && j!=num_o_b)
break;
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
X1=i;
Y1=j;

top1=findtop(X1);
top2=findtop(X2);

for (i=0;i<top1-Y1;i++)
{
world[X2][top2+i]=world[X1][Y1+i];
world[X1][Y1+i]=-1;
}
}
}

void cleantop(int num)
{
int i,j,k,X,Y;

for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==num && j!=num_o_b)
break;
}
if (world[i][j]==num && j!=num_o_b)
break;
}

X=i;
Y=j;
k=j;
while (world[X][++j]!=-1)
{
world[world[X][j]][0]=world[X][j];
world[X][j]=-1;
}

}

void display(void)
{
int i,j;
for (i=0;i<num_o_b;i++)
{
cout<<i<<":";
for (j=0;j<num_o_b;j++)
if (world[i][j]!=-1)
cout<<" "<<world[i][j];
cout<<"\n";
}
}

int findtop(int X)
{
int j;

for (j=0;j<num_o_b;j++)
if(world[X][j]==-1)
break;

return j;
}

int checkdo(void)
{
int i,j,X1,X2;

if (com_1 >= num_o_b || com_2 >= num_o_b)
return 1;
if (com_1 <0 || com_2 <0)
return 1;
if (com_1==com_2)
return 1;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==com_1 && j!=num_o_b)
break;
}
if (world[i][j]==com_1 && j!=num_o_b)
break;
}

X1=i;
for (i=0;i<num_o_b;i++)
{
for (j=0;j<num_o_b;j++)
{
if (world[i][j]==com_2 && j!=num_o_b)
break;
}
if (world[i][j]==com_2 && j!=num_o_b)
break;
}

X2=i;
if (X1==X2)
return 1;

return 0;
}


[/cpp]

[Nick]

#include <stdio.h>

#define MAX 26


int block[MAX][MAX];


int _cmpstring(const char *str, const char *str2)
{
int i;
for (i=0;str!=NULL&&str2!=NULL;i++)
{
if (str!=str2) return 1;
}
return 0;
}


int search(int n)
{
int i,j;
for (i=0;i<MAX;i++)
for (j=0;j<MAX;j++)
{
if (block[j]==-1) break;
if (block[j]==n) return i;
}

return -1;
}

void main(void)
{
char command[20],command2[10];
int i,j,n,ri,rj,count,k,l;


scanf("%d",&n);


for (i=0;i<n;i++)
{
for (j=1;j<MAX;j++)
block[j]=-1;

block[0]=i;
}

if (n>0&&n<MAX+1)
{

do
{
scanf("%s",command);

if (_cmpstring(command,"move")==0)
{
scanf("%d %s %d",&i,command2,&j);


if (i==j) continue;
ri=search(i);
rj=search(j);

if (ri==-1||rj==-1) continue;
if (ri-rj==0) continue;
else
{
for (count=0;count<n;count++)
{
if (block[ri][count]==i) break;
}
for (k=count+1;k<n;k++)
{
if (block[ri][k]!=-1) {block[block[ri][k]][0]=block[ri][k];
block[block[ri][k]][1]=-1;
block[ri][k]=-1;
}
}

block[ri][count]=-1;
if (_cmpstring(command2,"over")==0)
{

for (count=0;count<n;count++)
{
if (block[rj][count]==-1) break;
}
block[rj][count]=i;
block[rj][count+1]=-1;
}

else if (_cmpstring(command2,"onto")==0)
{
for (count=0;count<n;count++)
{
if (block[rj][count]==j) break;
}
for (k=count+1;k<n;k++)
{
if (block[rj][k]!=-1) {block[block[rj][k]][0]=block[rj][k];

block[block[rj][k]][1]=-1;
block[rj][k]=-1;

}
}
block [rj][count+1]=i;
block [rj][count+2]=-1;
}
}
}

else if (_cmpstring(command,"pile")==0)
{
scanf("%d %s %d",&i,command2,&j);

if (i==j) continue;
ri=search(i);
rj=search(j);

if (ri==-1||rj==-1) continue;
if (ri-rj==0) continue;
else
{
if (_cmpstring(command2,"onto")==0)
{
for (count=0;count<n;count++)
{
if (block[rj][count]==j) break;
}
for (k=count+1;k<n;k++)
{
if (block[rj][k]!=-1) {block[block[rj][k]][0]=block[rj][k];
block[block[rj][k]][1]=-1;
block[rj][k]=-1;
}
}

for (k=0;k<n;k++)
{
if (block[ri][k]==i) break;
}
for (l=0;l<n&&block[ri][k+l]!=-1;l++)
{
block[rj][count+1+l]=block[ri][k+l];
}
block[rj][count+1+l]=block[ri][k]=-1;
}
else if (_cmpstring(command2,"over")==0)
{
for (k=0;k<n&&block[rj][k]!=-1;k++);

for (count=0;count<n;count++)
{
if (block[ri][count]==i) break;
}

for (l=0;l<n&&block[ri][count+l]!=-1;l++)
{
block[rj][k+l]=block[ri][count+l];
block[ri][count+l]=-1;
}
block[rj][k+l]=block[ri][count]=-1;
}

}
}


}
while(_cmpstring(command,"quit")!=0);

for (i=0;i<n;i++)
{
printf("%d:",i);
for (j=0;j<n&&block[j]!=-1;j++)
{
printf(" %d",block[j]);
}
if (i<n-1) printf("\n");
}
}


}

[cplusplus]

I made a time expensive solution for this problem, basically working with an struct with two integers, storing the pile and the pile position do the n indexes of my struct array, and spend a lot of time debugging my program.

Are lists the fastest way to do it? if (true) how do I work with lists?

I use array to simulate lists....
this may be fatster.....
how much time does your program spend?

[Nick]

a lot of unnecessary code were lying around in my program up there, I know. But i've finally found what's really wrong with it and fixed it. Now i've solved the problem

[rbrogan]

* Edit - the problem was I tried to handle cases where a and b are on the same stack even though the problem statement says they are illegal. Thanks to those who helped. *

I cannot figure out why I am getting wrong answer. Here is a list of things I've checked.

1) Number of blocks greater than 0 and less than 25.
2) Each block in the commands greater than 0 and less than number of blocks.
3) Stop processing on quit command
4) Output is in correct format, no trailing spaces.
5) 134 test cases of commands including the following variables -
A in original position, B in original position, A above B, B above A, blocks above A, blocks below A, blocks above B, blocks below B.

I went through the output of each of the test cases and there is only on kind where it is ambiguous as to whether the behavior is correct.

"pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved. "

Normally pile commands involving a and b on the same stack either have no effect or should be illegal but I believe there is a case where a and b are on the same stack and the pile command should have an effect.

0: 0
1: 1
2: 2 3 4
3:
4:

pile 4 onto 2

0: 0
1: 1
2: 2 4
3: 3
4:

Is this a correct interpretation? If this is correct I cannot think of where my code could be going wrong.