101 - The Blocks Problem

[koenigin]

Has anyone tried solving this problem with an array of linked lists? I started doing it that way before realizing that there's the maximum of 25 numbers . . . then I decided to just finish it anyway. Now I'm stuck with tons of bugs though.

Just curious if that's a stupid way of solving the problem. Seems like the most natural data structure for it, but the coding is messy...

How did you implement the problem? fixed-dimension 2-d arrays? dynamic arrays?

[daveon]

I believe this is a simulation question which makes it naturally messy to code.

I used static 2D array with stacks.

If you're getting WA, just recode the whole problem. It works most of the time.

[Raiyan Kamal]

I did it with array of linked lists.

I made a node class and a linked list class. The procedures were mostly manipulation of pointers.

Make sure you understand what pile-over, pile-onto, move-over and move-onto means. When you are moving a over b, you will have to put all the blocks above a back to their initial position. Initial position is the parent pile here, not the pile they are on right now. See other posts and the sample I/O on this problem to make it clear.

Good luck

[Fadia Ismael]

Hello everybody, I'm new in this board and now I'm trying to solve problem#101, I really feel that I'm weak, I need some help, I don't know how much time I must try, and I feel that I will soon give up, may be this is the way to solve the problem.. isn't it????

[daveon]

Hi,

I wouldn't consider problem 101 a problem for beginners.

If you are serious about solving problems, learn algorithms and data structures first.

I usually give up after 3 WAs and come back to it a few days later.

Remember, the more problems you try, the more likely you will get some of them accepted.

[Fadia Ismael]

Can anyone tell me why I get run time error???
Please help...
here is the code- C++

Code: Select all

#include <iostream.h>
#include <string.h>

void returnBlocks(int origin[][26], int ai, int aj){
	int temp;
	while((temp=origin[ai][aj])!=-1){
		origin[temp][0]=temp;
		origin[temp][1]=-1;
		origin[ai][aj]=-1;
		aj++;
	}
	
}
		

void main(){
	int origin[25][26];
	int n, a, b, ai, aj, bi, bj, i, j,t;
	cin>>n;
	for (i=0; i<n; i++){
		origin[i][0]=i;
		origin[i][1]=-1;}
	char first[5];
	char second[5];
	cin>>first;

	while (strcmp(first, "quit")!=0){
		cin>>a;
		cin>>second;
		cin>>b;
		for (i=0; i<n; i++)
			for (j=0; j<n; j++){
				if (origin[i][j]==a){
					ai=i;
					aj=j;}
				if (origin[i][j]==b){
					bi=i;
					bj=j;}
			}
			if (a==b || ai==bi || a<0 || a>n || b<0 || b>n){
				cin>>first;
				continue;}

		if (strcmp(first,"move")==0 && strcmp(second, "onto")==0){
			returnBlocks(origin,ai,aj+1);
			returnBlocks(origin,bi,bj+1);
			origin[bi][bj+1]=origin[ai][aj];
			origin[bi][bj+2]=-1;
			origin[ai][aj]=-1;
		}

		else
			if(strcmp(first,"move")==0 && strcmp(second,"over")==0){
				returnBlocks(origin,ai,aj+1);
				for(j=bj;origin[bi][j]!=-1;j++);
				origin[bi][j]=a;
				origin[bi][j+1]=-1;
				origin[ai][aj]=-1;
			}
			else 
				if(strcmp(first,"pile")==0 && strcmp(second,"onto")==0){
					returnBlocks(origin,bi,bj+1);
					for(j=bj+1,i=aj;origin[ai][i]!=-1;j++,i++)
						origin[bi][j]=origin[ai][i];
					origin[ai][aj]=-1;
					origin[bi][j]=-1;
				}
				else
					if(strcmp(first,"pile")==0 && strcmp(second,"over")==0){
						for(j=bj;origin[bi][j]!=-1;j++);
						for(i=aj,t=j ;origin[ai][i]!=-1;i++,t++)
							origin[bi][t]=origin[ai][i];
						origin[bi][t]=-1;
						origin[ai][aj]=-1;
					}

		cin>>first;
	}

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

[Fadia Ismael]

Please, Why this code gives me runtime error in the judge, even I have tried it several times without any problems...
Please give a help, here is the code (101, C++):

Code: Select all

#include <iostream.h>
#include <cstring>
#include <stdlib.h>

void returnBlocks(int origin[][26], int ai, int aj){
	int temp;
	while((temp=origin[ai][aj])!=-1){
		origin[temp][0]=temp;
		origin[temp][1]=-1;
		origin[ai][aj]=-1;
		aj++;
	}
	
}
		

void main(){
	int origin[25][26];
	int n, a, b, ai, aj, bi, bj, i, j,t;
	cin>>n;
	if (n<1 || n>25)
		exit(1);
	for (i=0; i<n; i++){
		origin[i][0]=i;
		origin[i][1]=-1;}
	char first[5];
	char second[5];
	cin>>first;

	while (strcmp(first, "quit")!=0){
		cin>>a;
		cin>>second;
		cin>>b;
		for (i=0; i<n; i++)
			for (j=0; j<n; j++){
				if (origin[i][j]==a){
					ai=i;
					aj=j;}
				if (origin[i][j]==b){
					bi=i;
					bj=j;}
			}
			if (a==b || ai==bi || a<0 || a>=n || b<0 || b>=n){
				cin>>first;
				continue;}

		if (strcmp(first,"move")==0 && strcmp(second, "onto")==0){
			returnBlocks(origin,ai,aj+1);
			returnBlocks(origin,bi,bj+1);
			origin[bi][bj+1]=origin[ai][aj];
			origin[bi][bj+2]=-1;
			origin[ai][aj]=-1;
		}

		else
			if(strcmp(first,"move")==0 && strcmp(second,"over")==0){
				returnBlocks(origin,ai,aj+1);
				for(j=bj;origin[bi][j]!=-1;j++);
				origin[bi][j]=a;
				origin[bi][j+1]=-1;
				origin[ai][aj]=-1;
			}
			else 
				if(strcmp(first,"pile")==0 && strcmp(second,"onto")==0){
					returnBlocks(origin,bi,bj+1);
					for(j=bj+1,i=aj;origin[ai][i]!=-1;j++,i++)
						origin[bi][j]=origin[ai][i];
					origin[ai][aj]=-1;
					origin[bi][j]=-1;
				}
				else
					if(strcmp(first,"pile")==0 && strcmp(second,"over")==0){
						for(j=bj;origin[bi][j]!=-1;j++);
						for(i=aj,t=j ;origin[ai][i]!=-1;i++,t++)
							origin[bi][t]=origin[ai][i];
						origin[bi][t]=-1;
						origin[ai][aj]=-1;
					}

		cin>>first;
	}

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

[Fadia Ismael]

Here is the code for 101 C++:

Code: Select all

#include <iostream.h>
#include <string.h>
#include <stdlib.h>

void returnBlocks(int origin[][26], int ai, int aj){
	int temp;
	while((temp=origin[ai][aj])!=-1 && temp>=0 && temp<25){
		origin[temp][0]=temp;
		origin[temp][1]=-1;
		origin[ai][aj]=-1;
		aj++;
	}
	
}
		

void main(){
	int origin[25][26];
	int n, a, b, ai, aj, bi, bj, i, j,t;
	cin>>n;
	if (n<1 || n>25)
		exit(1);
	for (i=0; i<n; i++){
		origin[i][0]=i;
		origin[i][1]=-1;}
	char first[5];
	char second[5];
	cin>>first;

	while (strcmp(first, "quit")!=0){
		cin>>a;
		cin>>second;
		cin>>b;
		if(a==b || a<0 || a>=n || b<0 || b>=n){
				cin>>first;
				continue;}
		for (i=0; i<n; i++)
			for (j=0; j<n; j++){
				if (origin[i][j]==a){
					ai=i;
					aj=j;}
				if (origin[i][j]==b){
					bi=i;
					bj=j;}
			}
			if (ai==bi){
				cin>>first;
				continue;}

		if (strcmp(first,"move")==0 && strcmp(second, "onto")==0){
			returnBlocks(origin,ai,aj+1);
			returnBlocks(origin,bi,bj+1);
			origin[bi][bj+1]=origin[ai][aj];
			origin[bi][bj+2]=-1;
			origin[ai][aj]=-1;
		}

		else
			if(strcmp(first,"move")==0 && strcmp(second,"over")==0){
				returnBlocks(origin,ai,aj+1);
				for(j=bj;origin[bi][j]!=-1;j++);
				origin[bi][j]=a;
				origin[bi][j+1]=-1;
				origin[ai][aj]=-1;
			}
			else 
				if(strcmp(first,"pile")==0 && strcmp(second,"onto")==0){
					returnBlocks(origin,bi,bj+1);
					for(j=bj+1,i=aj;origin[ai][i]!=-1;j++,i++)
						origin[bi][j]=origin[ai][i];
					origin[ai][aj]=-1;
					origin[bi][j]=-1;
				}
				else
					if(strcmp(first,"pile")==0 && strcmp(second,"over")==0){
						for(j=bj;origin[bi][j]!=-1;j++);
						for(i=aj,t=j ;origin[ai][i]!=-1;i++,t++)
							origin[bi][t]=origin[ai][i];
						origin[bi][t]=-1;
						origin[ai][aj]=-1;
					}

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

[mcqsmall]

At the first I use stack,I got runtime error.
Then I use link,but I also got the same result;

[chunyi81]

l would like to quote this sentence from the problem description:

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.

I believe the two of you are making the same mistake. Hope this helps.

Also, to Fadia, your code does not even compile on my PC. You forgot the using namespace std. Also use #include <iostream>, #include<cstring>, #include <cstdlib> instead. And after getting your code to compile, your code give wrong output for the sample input:

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Your program output:
0: 0
1: 1
2:
3: 3
4:
5: 5 8
6:
7:
8:
9:

Correct output:
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

[Fadia Ismael]

I've tried this input and I get the same as your output!!!!!!!! so what is the matter????????????????????

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.

and also I noticed this, and I solved it in my code, now what did you say??

Please help..

[chunyi81]

Have you tried with the inputs give in this board?

Try this one:
24
pile 0 over 23
pile 1 over 23
pile 2 over 23
pile 3 over 23
pile 4 over 23
pile 5 over 23
pile 6 over 23
pile 7 over 23
pile 8 over 23
pile 9 over 23
pile 10 over 23
pile 11 over 23
pile 12 over 23
pile 13 over 23
pile 14 over 23
pile 15 over 23
pile 16 over 23
pile 17 over 23
pile 18 over 23
pile 19 over 23
pile 20 over 23
pile 21 over 23
pile 22 over 23
pile 23 over 23
pile 23 onto 0
quit

Your code give a segmentation fault with this input.

[Fadia Ismael]

Hello, I've tried it and I have this output, with no problems:

0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23: 23 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

whats your opinion????? thanks.

[epsilon]

for some reason, I keep getting "Compile Error" when submit my code thru http. But it compiles just fine on my computer (System: Fedora Core 3) using gcc. I don't know what happened.

And here is my code for the 101 blocks question:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define GARBAGE 37   // should be  a number above 24 or below 0
#define DEBUG_ON 0	 // set to 0 to turn off debuging procedures

void moveOnto(int *Array, int a, int b);
void moveOver(int *Array, int a, int b);
void pileOnto(int *Array, int a, int b);
void pileOver(int *Array, int a, int b);
void search(int matrix[], int position[], int num);


int main(void){

	int n, a, b;
	char input[16];
	char Act1[5], Act2[5];
	int Array[25][25];
	int i, j;
	
	// initialize Array to GARBAGE
	for (i = 0; i <= 24; i++){
		for(j = 0; j <= 24; j++){
			Array[i][j] = GARBAGE;
		}
	}
	
	scanf("%d", &n);
	n = n - 1;
	
	// add values to Array
	for (i = 0; i <= n; i++){
		Array[0][i] = i;
	}
	
	#if DEBUG_ON
		for(i = 0; i <= n; i++){
			printf("%d ", Array[0][i]);
		}
		printf("\n");
	#endif
	
	scanf("%s", Act1);
	
	while (Act1[0] != 'q'){
		scanf("%d", &a);
		scanf("%s", Act2);
		scanf("%d", &b);
		
		#if DEBUG_ON
		printf("this is the Act1: %s\n", Act1);
		printf("this is the a: %d\n", a);
		printf("this is the Act2: %s\n", Act2);
		printf("this is the b: %d\n", b);
		printf("\n");
		#endif
		
		if(Act1[0] == 'm' && Act2[1] == 'n')
			moveOnto(&Array[0][0], a, b);
		if(Act1[0] == 'm' && Act2[1] == 'v')
			moveOver(&Array[0][0], a, b);
		if(Act1[0] == 'p' && Act2[1] == 'n')
			pileOnto(&Array[0][0], a, b);
		if(Act1[0] == 'p' && Act2[1] == 'v')
			pileOver(&Array[0][0], a, b);
			
		scanf("%s", Act1);
		
	}
	
	// print the result
	
	for (j = 0; j <= n; j++){
		printf("%d: ", j);
		for(i = 0; Array[i][j] != GARBAGE; i++){
			printf("%d ", Array[i][j]);
		}
		printf("\n");
	}
	
	return(0);
}

void moveOnto(int *Array, int a, int b){
	int position[2]; // coordinator
	int value; 		   // used to store value when moving blocks
	int i, j;         // coordinator of a in 2 dimesion 
	int n, m;         // coordinator of b in 2 dimesion
	int count = 1;        // counter
	
	search(Array, position, a);
	i = position[0];
	j = position[1];
	
	search(Array, position, b);
	n = position[0];
	m = position[1];
	
	// clean blocks above a
	while ( Array[(i + count) * 25 + j] != GARBAGE){
		value = Array[(i + count) * 25 + j];
		Array[value] = value;
		Array[(i + count) * 25 + j] = GARBAGE;
		count++;
	}
	
	
	
	// clean blocks above b
	count = 1;
	while ( Array[(n + count) * 25 + m] != GARBAGE){
		value = Array[(n + count) * 25 + m];
		Array[value] = value;
		Array[(n + count) * 25 + m] = GARBAGE;
		count++;
	}
	
	Array[(n + 1)*25 + m] = Array[i*25 + j];
	Array[i*25 + j] = GARBAGE;
	
}
void moveOver(int *Array, int a, int b){
	int position[2]; // coordinator
	int value; 		   // used to store value when moving blocks
	int i, j;         // coordinator of a in 2 dimesion 
	int n, m;         // coordinator of b in 2 dimesion
	int count = 1;        // counter
	
	search(Array, position, a);
	i = position[0];
	j = position[1];
	
	search(Array, position, b);
	n = position[0];
	m = position[1];
	
	// clean blocks above a
	while ( Array[(i + count) * 25 + j] != GARBAGE){
		value = Array[(i + count) * 25 + j];
		Array[value] = value;
		Array[(i + count) * 25 + j] = GARBAGE;
		count++;
	}
	
	
	
	// find the top position
	
	for (count = 1; Array[(n+count) * 25 + m] != GARBAGE; count++){
		;
	}
	
	// insert a to the top position
	Array[(n+count) * 25 + m] = Array[i * 25 + j];
	Array[i * 25 + j] = GARBAGE;
	
}

void pileOnto(int *Array, int a, int b){
	int position[2]; // coordinator
	int value; 		   // used to store value when moving blocks
	int i, j;         // coordinator of a in 2 dimesion 
	int n, m;         // coordinator of b in 2 dimesion
	int count;        // counter
	int temp[25];     // temporary array to store the stacks over a
	
	for (count = 0; count <= 24; count++){
		temp[count] = GARBAGE;
	}
	
	search(Array, position, b);
	n = position[0];
	m = position[1];
	
	// search position for a
	search(Array, position, a);
	i = position[0];
	j = position[1];

	// clean blocks above b
	count = 1;
	while (Array[(n + count) * 25 + m] != GARBAGE){
		value = Array[(n + count) * 25 + m];
		Array[value] = value;
		Array[(n + count) * 25 + m] = GARBAGE;
		count++;
	}
	
	
	
	// store blocks above a to temporary array.
	for (count = 0; Array[(i+count) * 25 + j] != GARBAGE; count++){
		temp[count] = Array[(i+count) * 25 + j];
		Array[(i+count) * 25 + j] = GARBAGE;
	}
	
	for (count = 1; temp[count - 1] != GARBAGE; count++){
		Array[(n+count) * 25 + m] = temp[count - 1];
		temp[count - 1] = GARBAGE;
	}
	
}
void pileOver(int *Array, int a, int b){
	int position[2]; // coordinator
	int value; 		   // used to store value when moving blocks
	int i, j;         // coordinator of a in 2 dimesion 
	int n, m;         // coordinator of b in 2 dimesion
	int count;        // counter
	int temp[25];     // temporary array to store the stacks over a
	int count2;		  // for the final count
	
	for (count = 0; count <= 24; count++){
		temp[count] = GARBAGE;
	}
	
	// search position for a
	search(Array, position, a);
	i = position[0];
	j = position[1];
	
	search(Array, position, b);
	n = position[0];
	m = position[1];
	
	// store blocks above a to temporary array.
	for (count = 0; Array[(i+count) * 25 + j] != GARBAGE; count++){
		temp[count] = Array[(i+count) * 25 + j];
		Array[(i+count) * 25 + j] = GARBAGE;
	}
	
	// find the top position of the stack containing b
	for (count = 1; Array[(n+count) * 25 + m] != GARBAGE; count++){
		;
	}
	
	// pile over
	for (count2 = 0; temp[count2] != GARBAGE; count2++){
		Array[(n+count+count2) * 25 + m] = temp[count2];
	}

}

void search(int matrix[], int position[], int num){
	int r, c, i = 0;
	for(;matrix[i] != num; i++);
		c = i%25;
		r = (i-c)/25 + 1;
	position[0] = r - 1;
	position[1] = c;

}

Any help would be appreciated.

Chen

[epsilon]

Sorry. I just found a similar post.