Uva 101 - The Blocks Problem

Problem: 101 - The Blocks Problem

Explain: Let we have a box (in any time)
0: 0
1: 1
2: 2
3: 3 4 5
4:
5:
[1] move a onto b : puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.

move 1 onto 2
0: 0
1:
2: 2 1
3: 3 4 5
4:
5:
(Note: puts block a onto block b)
move 4 onto 2
0: 0
1: 1 (return their initial position)
2: 2 4
3: 3
4:
5: 5 (return their initial position)
(note: .....  after returning any blocks that are stacked on top of blocks a and b to their initial positions)



[2]  move a over b : puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
Let, Condition of the stack:

0: 0
1:
2: 2 1
3: 3 4 5
4:
5:
move 3 over 2 

0: 0
1:
2: 2 1 3 (top of stack containing 2)
3:
4: 4 (return their initial position)
5: 5 (return their initial position)

[3] pile a onto b - 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.

Let, Condition of the stack:
0:
1:
2: 2 1 0
3: 3 4 5
4:
5:
 pile 1 onto 3
0:
1:
2: 2
3: 3 1 0 (stack with 1)
4: 4 (return their initial position)
5: 5 (return their initial position)

[4] pile a over b -  puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. (so no block return their initial position)
Let, Condition of the stack:
0:
1:
2: 2 1 0
3: 3 4 5
4:
5:

pile 1 over 3


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

[Now code it]


Critical Input: 

21
move 2 onto 1
move 3 onto 2
move 4 onto 3
move 5 over 1
pile 1 over 10
move 9 over 8
move 11 over 8
pile 3 over 8
pile 8 over 3
move 20 over 19
pile 19 over 18
pile 18 onto 15
move 15 over 3
pile 20 onto 19
pile 19 onto 18
pile 18 over 17
quit

Output:

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

Explain:

move 2 onto 1


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



move 3 onto 2


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



move 4 onto 3


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



move 5 over 1


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



pile 1 over 10


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



move 9 over 8


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



move 11 over 8


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



pile 3 over 8


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



pile 8 over 3


Invalid Command!!

move 20 over 19


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



pile 19 over 18


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



pile 18 onto 15


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



move 15 over 3


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



pile 20 onto 19


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



pile 19 onto 18


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



pile 18 over 17


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



quit


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

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
pile 2 over 1
pile 4 over 9
quit

Output:

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

Explain:

move 9 onto 1


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



move 8 over 1


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



move 7 over 1


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



move 6 over 1


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



pile 8 over 6


Invalid Command!!

pile 8 over 5


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



pile 2 over 1


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



pile 4 over 9


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



quit


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

Code:

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

#define s 25

int block[s][s];
int result[s];
int n;

int find(int val,int &pos)
{
  int position =0,i,j,flag=1;

  for(i=0;i<n && flag;i++)
	  for(j=0;j<result[i];j++)
		  if(block[i][j]==val)
		  {
		    pos=j;
			position=i;
			flag=0;
			break;
		  }
   return position;
}


void return_to_initial(int row, int p)
{
  int val;

  for(p;p<result[row];p++)
  {
    val=block[row][p];
	block[val][result[val]]=block[row][p];
	result[val]++;
  }
}



int main()
{
  char input[50],x[10],y[10];
  int i,j,a,b,pos1,pos2,p;
  //freopen("b.in","r",stdin);



  while((scanf("%d\n",&n))==1)
  {
      /*initialize*/
	for(i=0;i<n;i++)
	{
	  block[i][0]=i;
	  result[i]=1;
	}


	while(gets(input))
	{

	  sscanf(input,"%s %d %s %d\n",&x,&a,&y,&b);

	  if(strcmp(x,"quit")==0)
		  break;

	  if(a==b|| a>=n || b>=n)
		  continue;


	  i=find(a,pos1);
	  j=find(b,pos2);

	  if(i==j)
		  continue;



	  if(strcmp(x,"move")==0)
	  {
	    return_to_initial(i,pos1+1);

		result[i]=pos1;
		if(strcmp(y,"onto")==0)
		{
		  return_to_initial(j,pos2+1);
		  result[j]=pos2+1;
		}

		block[j][result[j]++]=a;
	  }

	  else if(strcmp(x,"pile")==0)
	  {
	    if(strcmp(y,"onto")==0)
		{
		  return_to_initial(j,pos2+1);
		  result[j]=pos2+1;
		}
   	    for(p=pos1;p<result[i];p++)
		  block[j][result[j]++]=block[i][p];

        result[i]=pos1;
	  }
	}
    for(i=0;i<n;i++)
	{
	  printf("%d:",i);

	  if(!result[i])
	  {
	    printf("\n");
		continue;
	  }

	  for(j=0;j<result[i];j++)
		  printf(" %d",block[i][j]);
	  printf("\n");
	}
  }
  return 0;
}