101 - The Blocks Problem

Moderator: Board moderators

zolto
New poster
Posts: 3
Joined: Wed Jan 21, 2004 7:09 pm
Thanks for all the help, it works now. There were some minor (stupid) errors.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Not really helpful.. but here's a tip:

Most people on this forum solved volume 1 questions quite some time ago and most don't remember the specifics...

The best way to get a response is to make a sample test data with all the data you think MAY trip your program. Post the test data and your test output and hopefully someone will post their output and if there is any discrepancies, you can use that to debug...

I hate to say it, but most people just can't find the time to re-solve a question just to help someone else debug their program... it's cruel, but it's human nature.

Anyway, try these:

Moving a empty stack
Moving onto an empty stack
etc.

Usually TLE/WA for this kind of simple simulation questions is due to boundary errors.

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am
You can also use the search feature and just type in "101" there a quite a few topics already and test data that has tripped up others. Also http://people.eecs.ku.edu/~rucker/valladolid/p101.exe heres a test generator and answer program. It will give an input and give the solution to that input. Just run the input through your program to see if you get the same output. If not then debug.

Happy Coding.

New poster
Posts: 5
Joined: Mon Jan 12, 2004 12:44 pm

Problem 101 - Runtime error (SIGSEGV)

[cpp]

#include <string>
#include <iostream>
using namespace std;

const int MAXNUM = 25;

enum Boolean { FALSE, TRUE };
void Reset( int *block[], int row_a, int a );
void Move( int *block[], int row_a, int a, int b );
int Find( int *block[], int a, int n );
void Initialise( int *block[], int n ) ;
void Display( int *block[], int n );
void Pile( int *block[], int row_a, int a, int row_b );

int main() {
string action, prep;
int *block[MAXNUM];
int n;
int i;
int a, b;
int row_a, row_b;

cin >> n;
for( i = 0; i < n; i++ )
block = (int *) malloc( 25 * sizeof(int) );

Initialise( block, n );
while( TRUE ) {
cin >> action;
if( action == "quit" ) break;
cin >> a >> prep >> b;
if( a == b ) continue;

row_a = Find( block, a, n );
/* find the row where block a is in */
row_b = Find( block, b, n );
if( row_a == row_b )
continue;
if( action == "move" ) {
if( prep == "onto" ) {
Reset( block, row_a, a );
Reset( block, row_b, b );
Move( block, row_a, a, row_b );
}
else if( prep == "over" ) {
Reset( block, row_a, a );
Move( block, row_a, a, row_b );
}
}
else if( action == "pile" ) {
if( prep == "onto" ) {
Reset( block, row_b, b );
Pile( block, row_a, a, row_b );
}
else if( prep == "over" )
Pile( block, row_a, a, row_b );
}

}

Display( block, n );
return 1;

}

int Find( int *block[], int a, int n ) {
int i, j;

for( i = 0; i < n; i++ )
for( j = 0; j < MAXNUM; j++ )
if( block[j] == a )
return i;
return( FALSE );
}

void Reset( int *block[], int row_a, int a ) {
int i, temp;

for( i = 0; block[row_a] != a; i++ )
;

i++;
for( ; block[row_a] != -1; i++ ) {
temp = block[row_a];
block[temp][0] = temp;
block[row_a] = -1;
}

}

void Move( int *block[], int row_a, int a, int row_b) {

int i;

for( i = 0; block[row_a] != a; i++ )
;

block[row_a] = -1;

for( i = 0; block[row_b] != -1; i++ )
;

block[row_b] = a;
i++;
block[row_b][i] = -1;
}

void Initialise( int *block[], int n ) {
int i, j;

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

void Display( int *block[], int n ) {
int i, j;

for( i = 0; i < n; i++ ) {
cout << i << ":";
for( j = 0; block[i][j] != -1; j++ )
cout << " " << block[i][j] ;
cout << endl;
}

void Pile( int *block[], int row_a, int a, int row_b ) {
int i;

for( i = 0; block[row_a][i] != a; i++ )
;
for( ; block[row_a][i] != -1; i++ ) {
Move( block, row_a, block[row_a][i], row_b );
block[row_a][i] = -1;
}

}
[/cpp]

my code is running just fine for the sample input....without any sort of runtime errors....
can anybody plssss.....tell me what the problem could be......
i
thanx.

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm

101 Compile Error.

I use gcc 3.2.2, and compiled it successfully.
[cpp]#include <iostream>
#include <vector>

using namespace std;

class Blocks
{
typedef vector<short> cvectype;
vector<cvectype> vec;
class block_pos
{
public:
short row;
short column;
block_pos(short r, short c):row(r), column(c){}
};

block_pos block_find(short block_value)
{
register short row, column;
for (row = 0; row < vec.size(); row++)
for (column = 0; column < vec[row].size(); column++)
if (vec[row][column] == block_value) return block_pos(row, column);
}

void block_delete(block_pos block)
{
vector<short>::iterator iter = vec[block.row].begin();
vec[block.row].erase(iter);
}

void pile_delete(block_pos begin_b)
{
vector<short>::iterator iter = vec[begin_b.row].begin();
vec[begin_b.row].erase(iter, vec[begin_b.row].end());
}

void block_return(block_pos block)
{
short value = vec[block.row][block.column];
block_delete(block);
vec[value].push_back(value);
}

void pile_return(block_pos begin_b)
{
register short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
block_return(block_pos(begin_b.row, i));
pile_delete(begin_b);
}

short blocks_at_same_row(block_pos a, block_pos b)
{
if (a.row == b.row) return 1;
else return 0;
}

short block_can_return(block_pos block)
{
if (vec[vec[block.row][block.column]].empty()) return 1;
else return 0;
}

short pile_can_return(block_pos begin_b)
{
register short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
if (!block_can_return(block_pos(begin_b.row, i))) return 0;
return 1;
}

void move_a_onto_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

// return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}

if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void move_a_over_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
//return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void pile_a_onto_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

//return.
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

//pile.
register short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

void pile_a_over_b(short a, short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;

//pile.
register short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

public:
Blocks(short n)
{
register short i;
vector<short> cvec;
for (i = 0; i < n; i++)
{
cvec.push_back(i);
vec.push_back(cvec);
cvec.clear();
}
}

void print()
{
register short index, index1;
for (index = 0; index < vec.size(); index++)
{
cout << ' ' << index << " : ";
for (index1 = 0; index1 < vec[index].size(); index1++)
cout << vec[index][index1] << ' ';

cout << "\n";
}
}

void command(string action, short a, string grep, short b)
{
if (action == "move")
{
if (grep == "onto") move_a_onto_b(a, b);
else if (grep == "over") move_a_over_b(a, b);
}
else if (action == "pile")
{
if (grep == "onto") pile_a_onto_b(a, b);
else if (grep == "over") pile_a_over_b(a, b);
}
}
};

int main(){
short n, a, b;
string action, grep;
cin >> n;
Blocks block = Blocks(n);
cin >> action;
while (action != "quit")
{
cin >> a >> grep >> b;
block.command(action, a, grep, b);
cin >> action;
}

block.print();
return 0;
}[/cpp]

New poster
Posts: 5
Joined: Mon Jan 12, 2004 12:44 pm
Hi JW,

Try compiling with
gcc -Wall -pedantic and remove all the warnings.....
I had a similar problem earlier. My code was compiling but with some warnings and the online judge was giving me a compiler error.....if you want it will send you the detailed compiler error message on your email id.......that should help...and dont forget to get rid of ALL the warnings

Even i am working on problem 101 but getting a runtime error (SIGSEGV} with Illegal Memory Reference.
Could you please send me some tricky test inputs??

My code is as below :

[cpp]

#include <string>
#include <cstdlib>

#include <fstream>
using std::ifstream;

#include <iostream>
using namespace std;

const int MAXNUM = 25;
enum Boolean { FALSE, TRUE };

void Reset( int row_a, int a );
void Move( int row_a, int a, int row_b );
int Find( int a );
void Initialise( ) ;
void Display();
void Pile( int row_a, int a, int row_b );

int top[MAXNUM];
int n;
int *block[MAXNUM];

int main() {
string action, prep;
int i;
int a, b;
int row_a, row_b;
ifstream infile( "input.txt", ios::in );

if( !infile ) {
exit( 1 );
}

infile >> n;
if( n >= MAXNUM || ( n <= 0 ) ) exit(1);
for( i = 0; i < n; i++ )
block = new int[n];
Initialise();
while( TRUE ) {
infile >> action;
if( action == "quit" ) break;
infile >> a >> prep >> b;

if( (a >= n) || (b >= n) || ( a == b) || (a < 0) || (b < 0) )
continue;
row_a = Find( a );
row_b = Find( b ); /* find the rows in which a and b are present */
if( row_a == row_b ) continue;
if( action == "move" ) {
if( prep == "onto" ) {
Reset( row_a, a );
Reset( row_b, b );
Move( row_a, a, row_b );
}
else if( prep == "over" ) {
Reset(row_a, a );
Move(row_a, a, row_b );
}
}
else if( action == "pile" ) {
if( prep == "onto" ) {
Reset(row_b, b );

Pile( row_a, a, row_b );
}
else if( prep == "over" )
Pile( row_a, a, row_b );
}

}

Display( );
return 0;

}

int Find( int a ) {
int i, j;

for( i = 0; i < n; i++ )
for( j = 0; j <= top; j++ )
if( block[j] == a )
return i;
return( FALSE );
}

void Reset( int row_a, int a ) {
int i, temp, itop;

for( i = 0; ( block[row_a] != a) && (i < n); i++ )
;
itop = i;
i++;
for( ; i <= top[row_a]; i++ ) {
temp = block[row_a];
block[ block[row_a] ][0] = block[row_a];
top[temp]++;
}
top[row_a] = itop;

}

void Move( int row_a, int a, int row_b) {

int i;

for( i = 0; (block[row_a] != a) && (i < n); i++ )
;
if( i == n ) cout << "Illegal Memory Address";
i--;
top[row_a] = i;
for( i = 0; i <= top[row_b]; i++ )
;
block[row_b] = a;
top[row_b]++;
}

void Initialise( ) {
int i;

for( i = 0; i < n; i++ ) {
top = 0;
block[i][0] = i;
}
}

void Display( ) {
int i, j;

for( i = 0; i < n; i++ ) {
cout << i << ":";
for( j = 0; j <= top[i]; j++ )
cout << " " << block[i][j] ;
cout << endl;
}

for( i = 0; i < n; i++ )
delete [] block[i];
}

void Pile(int row_a, int a, int row_b ) {
int i, itop;
int j;

itop = top[row_a];
for( i = 0; (block[row_a][i] != a) && (i < n); i++ )
;
for( ; i <= itop; i++, j++ )
Move( row_a, block[row_a][i], row_b );

top[row_a] = i - j - 1;
}

[/cpp]

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm
Thank aditya. I used "-Wall" keyword to compile my program, I found some warnings, and I have already fixed it. However, it still got a "compile error".

I saw your code use file to input. Don't use file, just use keyboard to input, and output the result to screen.

JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm
My new code is below.
[cpp]#include <iostream>
#include <vector>

using namespace std;

class Blocks
{
typedef vector<unsigned short> cvectype;
vector<cvectype> vec;
class block_pos
{
public:
unsigned short row;
unsigned short column;
block_pos(unsigned short r, unsigned short c):row(r), column(c){}
};

block_pos block_find(unsigned short block_value)
{
register unsigned short row, column;
for (row = 0; row < vec.size(); row++)
for (column = 0; column < vec[row].size(); column++)
if (vec[row][column] == block_value) return block_pos(row, column);

// can't find.
return block_pos(26, 26);
}

void block_delete(block_pos block)
{
vector<unsigned short>::iterator iter = vec[block.row].begin();
vec[block.row].erase(iter);
}

void pile_delete(block_pos begin_b)
{
vector<unsigned short>::iterator iter = vec[begin_b.row].begin();
vec[begin_b.row].erase(iter, vec[begin_b.row].end());
}

void block_return(block_pos block)
{
unsigned short value = vec[block.row][block.column];
block_delete(block);
vec[value].push_back(value);
}

void pile_return(block_pos begin_b)
{
register unsigned short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
block_return(block_pos(begin_b.row, i));
pile_delete(begin_b);
}

unsigned short blocks_at_same_row(block_pos a, block_pos b)
{
if (a.row == b.row) return 1;
else return 0;
}

unsigned short block_can_return(block_pos block)
{
if (vec[vec[block.row][block.column]].empty()) return 1;
else return 0;
}

unsigned short pile_can_return(block_pos begin_b)
{
register unsigned short i;
for (i = begin_b.column; i < vec[begin_b.row].size(); i++)
if (!block_can_return(block_pos(begin_b.row, i))) return 0;
return 1;
}

void move_a_onto_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

// return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}

if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void move_a_over_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
if (!pile_can_return(posap)) return;
}
//return.
if (posa.column != vec[posa.row].size() - 1)
{
block_pos posap = block_pos(posa.row, posa.column + 1);
pile_return(posap);
}
//end of return.

vec[posb.row].push_back(vec[posa.row][posa.column]);
block_delete(posa);
}

void pile_a_onto_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
if (!pile_can_return(posbp)) return;
}

//return.
if (posb.column != vec[posb.row].size() - 1)
{
block_pos posbp = block_pos(posb.row, posb.column + 1);
pile_return(posbp);
}
//end of return.

//pile.
register unsigned short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

void pile_a_over_b(unsigned short a, unsigned short b)
{
block_pos posa = block_find(a);
block_pos posb = block_find(b);
if (blocks_at_same_row(posa, posb)) return;

//pile.
register unsigned short i;
for (i = posa.column; i < vec[posa.row].size(); i++)
vec[posb.row].push_back(vec[posa.row]);
pile_delete(posa);
//end of pile.
}

public:
Blocks(unsigned short n)
{
register unsigned short i;
vector<unsigned short> cvec;
for (i = 0; i < n; i++)
{
cvec.push_back(i);
vec.push_back(cvec);
cvec.clear();
}
}

void print()
{
register unsigned short index, index1;
for (index = 0; index < vec.size(); index++)
{
cout << ' ' << index << " : ";
for (index1 = 0; index1 < vec[index].size(); index1++)
cout << vec[index][index1] << ' ';

cout << "\n";
}
}

void command(string action, unsigned short a, string grep, unsigned short b)
{
if (action == "move")
{
if (grep == "onto") move_a_onto_b(a, b);
else if (grep == "over") move_a_over_b(a, b);
}
else if (action == "pile")
{
if (grep == "onto") pile_a_onto_b(a, b);
else if (grep == "over") pile_a_over_b(a, b);
}
}
};

int main(){
unsigned short n, a, b;
string action, grep;
cin >> n;
Blocks block = Blocks(n);
cin >> action;
while (action != "quit")
{
cin >> a >> grep >> b;
block.command(action, a, grep, b);
cin >> action;
}

block.print();
return 0;
}
[/cpp]

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

^^

gits wrote:my code gives:

Code: Select all

``````0: 0
1: 1 2
2:
3:
4:
5: 5 4 6
6:
7: 7 9 3
8: 8
9:
10: 10 11 12
11:
12:
13: 13
14: 14 17
15: 15
16: 16
17:
18: 18
``````
my question is, how do 7 9 3 go over 8 in the end?
Insert this condition. You will get accept.
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks

komunist
New poster
Posts: 4
Joined: Thu Mar 11, 2004 3:20 pm

101 - i am going crazy

my code. It`s WA. I now why. BuTT
when i debug my code on test

4
move 1 onto 0
move 0 onto 1
move 0 onto 2
move 2 onto 1
quit

he otput
0: 0
1: 1 2
2:
3: 3

but when i run my program (klik on .exe file) and input then same test he otput

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

WHY ???????????????
var i,j,k,n,m:longint;

a1,b1:longint;
a,b:array [-1..25] of longint;
s:string;

procedure erase(k:longint);
begin
if (k=a[k]) or (a[k]=-1) then else erase(a[k]);
a[k]:=k;
end;

function prov(a1,b1:longint):longint;
var i,j,k:longint;
begin
i:=1;
if a1=b1 then i:=0 else
if a[a1]<>a1 then
begin
while a[a1]>-1 do
begin
if a[a1]=b1 then i:=0;
a1:=a[a1];
end;
end;
prov:=i;
end;

begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
for i:=1 to n do a[i-1]:=i-1;
while true do
begin
if pos('quit',s)>0 then break;
if pos('move',s)>0 then
begin
delete(s,1,5);val(copy(s,1,pos(' ',s)-1),a1,i);delete(s,1,pos(' ',s));
if pos('onto',s)>0 then
begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(a1);erase(b1);
for i:=0 to n-1 do if a=a1 then a:=-1;
a[a1]:=-1;a[b1]:=a1;
end else begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(a1); a[a1]:=-1;
for i:=0 to n-1 do if a=a1 then a:=-1;
k:=b1;
while (a[k]>=0) and (a[k]<>k) do k:=a[k];
a[k]:=a1;
end;
end else begin
delete(s,1,5);val(copy(s,1,pos(' ',s)-1),a1,i);delete(s,1,pos(' ',s));
if pos('onto',s)>0 then
begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
erase(b1);
for i:=0 to n-1 do if a=a1 then a:=-1;
a[b1]:=a1;
end else begin
delete(s,1,5);val(s,b1,i);
if prov(a1,b1)*prov(b1,a1)=0 then continue;
k:=b1;
for i:=0 to n-1 do if a=a1 then a:=-1;
while (a[k]>=0) and (a[k]<>k) do k:=a[k];
a[k]:=a1;
end;
end;
end;
fillchar(b,sizeof(b),0);
for i:=0 to n-1 do
begin
write(i:2,':');
if (b<>0) or (a=-1) then begin writeln;continue; end;
b[i]:=1;
j:=i;
while j<>-1 do
begin
write(' ',j);
b[j]:=1;
if j=a[j] then break;
j:=a[j];
end;
writeln;
end;
end.

komunist
New poster
Posts: 4
Joined: Thu Mar 11, 2004 3:20 pm
Why program gives 2 diferent reply for 1 test

cthompson
New poster
Posts: 7
Joined: Sat Apr 17, 2004 4:23 am

Time Limit Exceeded

My submission for 101 is coming back time limit exceeded.

The time being usually 10.012 to 10.070 seconds, the limit is 10.000 seconds.

I was trying to shave that hundredth of a second, however it has occured to me that perhaps the online judge automatically stops a program that has been running longer then 10seconds.

ie my program could be exceeding the limit by far more then 10seconds if it were let run.

Is this the case?

Thanks,
Cassie

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Yes, the judge will stop your program from running if it has run longer than 10 seconds.

cthompson
New poster
Posts: 7
Joined: Sat Apr 17, 2004 4:23 am
Thanks.