101 - The Blocks Problem

[beeplove]

Initial state of blocks are:

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

From this state what would be state for each of the following commads?

move 1 onto 5
move 1 over 5
pile 1 onto 5
pile 1 over 5

Your help would be appreciated. Thanks in advance.

[Maarten]

move 1 onto 5:

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

move 1 over 5:

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

pile 1 onto 5:

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

pile 1 over 5:

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


Hope this makes it clear

[beeplove]

Thanks a lot Marteen,

what about this:

Initial state:

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

what would be final state after eaah of the command?

move 6 onto 2

Thanks a lot

[Maarten]

think about the following question:

can you ever arrive at this situation using only the four commands the robot knows ?

[beeplove]

Well, Lets take another example of initial state,
Last time just set up a state quickly. Sorry about that.
This time state is valid !



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

move 0 onto 2

I am not sure where 7 will go. Thats why asking again and again.
Thanks a lot, Marteen

[Maarten]

this one is not valid either

[beeplove]

Yes.. you are right.
I think, I got it to work.

Thanks

[Morning]

this one is not valid either

why it's invalid?Have u ever solve the problem?Please tell me?

[Maarten]

Yes I have solved the problem
Just think about it why it's invalid, I'm sure you will find out. For example, try to find a sequence of commands which leads to the configuration above.. you won't find it!

[Morning]

Code: Select all

import java.io.*;
import java.util.*;

class  Main
{
	static String ReadLn (int maxLg)  
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	
	public static void main(String[] args) 
	{
		String input="";
		String action="";
		String prop="";
		StringTokenizer idata;
		int blockNumber,iLoop,jLoop;
		int temp;
		int i=-1;
		int j=-1;
		int a=-1;
		int b=-1;
		int ai=-1;
		int aj=-1;
		int bi=-1;
		int bj=-1;
		input=ReadLn(255);
		idata=new StringTokenizer(input);
		blockNumber = Integer.parseInt (idata.nextToken());
		int [][] matrix=new int[blockNumber][blockNumber];
		
		for(jLoop=0;jLoop<blockNumber;jLoop++)
				matrix[0][jLoop]=jLoop;

		for(jLoop=0;jLoop<blockNumber;jLoop++)
			for(iLoop=1;iLoop<blockNumber;iLoop++)
				matrix[iLoop][jLoop]=-3;
		
		while ((input = Main.ReadLn (255)) != null)
		{
			
			idata=new StringTokenizer(input);
			
			action=idata.nextToken();
			
			if (action.equals("quit"))
			{
				break;
			}
			
			a = Integer.parseInt (idata.nextToken());
            
			prop=idata.nextToken();
			
			b = Integer.parseInt (idata.nextToken());
			
			if (a==b)
			{
				continue;
			}

			for(iLoop=0;iLoop<blockNumber;iLoop++)
				for(jLoop=0;jLoop<blockNumber;jLoop++)
				{	
					if(matrix[iLoop][jLoop]==a) i=jLoop;
					if(matrix[iLoop][jLoop]==b) j=jLoop;
				}
			if(i==j)
			{
				continue;
				
			}

			
			if (action.equals("move"))
			{
				if(prop.equals("onto"))
				{
					for(jLoop=0;jLoop<blockNumber;jLoop++)
						for(iLoop=0;iLoop<blockNumber;iLoop++)
						{	
							if(matrix[iLoop][jLoop]==a)
							{
								ai=iLoop;
								aj=jLoop;
							}
							if(matrix[iLoop][jLoop]==b)
							{
								bi=iLoop;
								bj=jLoop;
							}
						}
					
					for(i=ai+1;matrix[i][aj]!=-3;i++)
					{
						temp=i;
						for(i=0;matrix[i][(matrix[temp][aj])]!=-3;i++){}
						matrix[i][(matrix[temp][aj])]=matrix[temp][aj];
						matrix[temp][aj]=-3;
						i=temp;
					}

					matrix[bi+1][bj]=matrix[ai][aj];
					matrix[ai][aj]=-3;
					
				}
				if(prop.equals("over"))
				{
					for(jLoop=0;jLoop<blockNumber;jLoop++)
						for(iLoop=0;iLoop<blockNumber;iLoop++)
						{	
							if(matrix[iLoop][jLoop]==a)
							{
								ai=iLoop;
								aj=jLoop;
							}
							if(matrix[iLoop][jLoop]==b)
							{
								bj=jLoop;
								temp=iLoop;
								for(iLoop=0;iLoop<blockNumber;iLoop++)
								{
									if(matrix[iLoop][jLoop]==-3)
									{
										bi=iLoop;
										iLoop=temp;
										break;
									}
								}
							}
						}
				
					for(i=ai+1;matrix[i][aj]!=-3;i++)
					{
						temp=i;
						for(i=0;matrix[i][(matrix[temp][aj])]!=-3;i++){}
						matrix[i][(matrix[temp][aj])]=matrix[temp][aj];
						matrix[temp][aj]=-3;
						i=temp;
					}

					matrix[bi][bj]=matrix[ai][aj];
					matrix[ai][aj]=-3;
					
				}
			}
			
			if(action.equals("pile"))
			{
				if(prop.equals("onto"))
				{
					for(jLoop=0;jLoop<blockNumber;jLoop++)
						for(iLoop=0;iLoop<blockNumber;iLoop++)
						{	
							if(matrix[iLoop][jLoop]==a)
							{
								ai=iLoop;
								aj=jLoop;
							}
							if(matrix[iLoop][jLoop]==b)
							{
								bi=iLoop;
								bj=jLoop;
							}
						}
					
					for(i=bi+1;matrix[i][bj]!=-3;i++)
					{
						temp=i;
						for(i=0;matrix[i][(matrix[temp][bj])]!=-3;i++){}
						matrix[i][(matrix[temp][bj])]=matrix[temp][bj];
						matrix[temp][bj]=-3;
						i=temp;
					}

					
					
					
					for(bi=bi+1;matrix[ai][aj]!=-3;ai++)
					{
						matrix[bi][bj]=matrix[ai][aj];
						matrix[ai][aj]=-3;
						bi=bi+1;
					}
				}
				if(prop.equals("over"))
				{
					for(jLoop=0;jLoop<blockNumber;jLoop++)
						for(iLoop=0;iLoop<blockNumber;iLoop++)
						{	
							if(matrix[iLoop][jLoop]==a)
							{
								ai=iLoop;
								aj=jLoop;
							}
							if(matrix[iLoop][jLoop]==b)
							{
								bj=jLoop;
								temp=iLoop;
								for(iLoop=0;iLoop<blockNumber;iLoop++)
								{
									if(matrix[iLoop][jLoop]==-3)
									{
										bi=iLoop;
										iLoop=temp;
										break;
									}
								}
							}
						}
				
					for(;matrix[ai][aj]!=-3;ai++)
					{
						matrix[bi][bj]=matrix[ai][aj];
						matrix[ai][aj]=-3;
						bi=bi+1;
					}
				}
				
			}
		}
				
			
		
		for(jLoop=0;jLoop<blockNumber;jLoop++)
		{
			System.out.print(jLoop+":");
			for(iLoop=0;iLoop<blockNumber;iLoop++)
			{
				if(matrix[iLoop][jLoop]==-3) continue;
				
				System.out.print(" "+matrix[iLoop][jLoop]);
			}
			System.out.println();
		}
	}
}

What's wrong with it?who can help me?in which situation can i know it is wrong?

[nonstop]

what's the result alfter "pile 4 onto 1":

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

I am not sure where 5,2 wll perform.....

[Morning]

this situation is impossible
who can a 5 goto 2: alone?

[Morning]

i solve it myself

[nonstop]

so,this situation i mentioned is invalid.
I can ignore that.....right?

[Maarten]

yep