101 - The Blocks Problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rbrogan
New poster
Posts: 3
Joined: Sun Feb 09, 2003 2:57 am

Post by rbrogan »

Here is my code. It is basically simple stack manipulation.

[c]#include <stdio.h>
#ifndef ONLINE_JUDGE
#include <fcntl.h>
#endif

#define FALSE 0
#define TRUE 1
#define NIL 26

typedef struct b_type
{
int block_number;
int stack_number;
struct b_type* block_below;
} block_type;

typedef struct s_type
{
block_type* top;
} stack_type;

block_type blocks[25];
stack_type stacks[25];


void push_single(int s, int b)
{
blocks.block_below = stacks[s].top;
stacks[s].top = &blocks;
blocks.stack_number = s;
}

int pop_single(int s)
{
int b;

if(stacks[s].top == NULL)
{
printf("NIL!\n");
exit(1);
return NIL;
}
else
{
b = stacks[s].top->block_number;
stacks[s].top = blocks.block_below;
blocks.block_below = NULL;

return b;
}
}

void push_stack(int s, int b, int top)
{
block_type* blockP;

blocks.block_below = stacks[s].top;
stacks[s].top = &blocks[top];

blockP = stacks[s].top;
while(blockP->block_number != b)
{
blockP->stack_number = s;
blockP = blockP->block_below;
}
blocks.stack_number = s;
}

int pop_stack(int s, int b)
{
int top;

if((stacks[s].top == NULL) || (blocks.stack_number != s))
{
printf("NIL!\n");
return NIL;
}
else
{
top = stacks[s].top->block_number;

stacks[s].top = blocks.block_below;
blocks.block_below = NULL;
return top;
}
}

void initialize_blocks(int number_of_blocks)
{
int i;

for(i=0; i<number_of_blocks; i++)
{
stacks.top = NULL;
blocks.block_number = i;
blocks.stack_number = NULL;
blocks.block_below = NULL;
push_single(i, i);
}
}

void output_state(int number_of_blocks)
{
int numbers[25];
int i, j, k;
block_type* blockP;

for(i=0; i<number_of_blocks; i++)
{
printf("%d:", i);
blockP = stacks.top;
j=0;
while(blockP != NULL)
{
numbers[j] = blockP->block_number;
j++;
blockP = blockP->block_below;
}
j--;
for(; j>=0; j--)
{
printf(" %d", numbers[j]);
}
printf("\n");
}
}

void return_to_initial_position(int b)
{
int s;

s = blocks[b].stack_number;
pop_single(s);
push_single(b, b);
}

void return_blocks_above(int b)
{
int s;
int c;

s = blocks[b].stack_number;

while(stacks[s].top != &blocks[b])
{
c = pop_single(s);
push_single(c, c);
}
}


int main(int argc, char* argv[])
{
int number_of_blocks;
int a;
int b;
int s, top;
char command[5] = {0,0,0,0,0};
char on_over[5] = {0,0,0,0,0};
int a_over_b;
int b_over_a;

#ifndef ONLINE_JUDGE
close (0); open (argv[1], O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif

scanf("%d\n", &number_of_blocks);

if((number_of_blocks <= 0) || (number_of_blocks >= 25))
{
exit(0);
/* This shouldn't happen because problem statement said it
wouldn't */
}

initialize_blocks(number_of_blocks);

while(scanf("%s %d %s %d\n", command, &a, on_over, &b))
{
if(!strcmp(command, "quit"))
{
break;
}

if(((a < 0) || (a >= number_of_blocks)) ||
((b < 0) || (b >= number_of_blocks)))
{
/* Block number out of bounds, ignored */
continue;
}

b_over_a = FALSE;
a_over_b = FALSE;

if(blocks[b].stack_number == blocks[a].stack_number)
{
int s = blocks[b].stack_number;
block_type* blockP = stacks[s].top;

/* Identified a and b are in the same stack. Start at the top
and work your way down and see which is higher, a or b */
while(blockP != NULL)
{
if(blockP->block_number == b)
{
b_over_a = TRUE;
break;
}

if(blockP->block_number == a)
{
a_over_b = TRUE;
break;
}
blockP = blockP->block_below;
}
}

if(strncmp(command, "pile", 4) == 0)
{
if(b_over_a)
{
continue;
}

if(a_over_b)
{
s = blocks[a].stack_number;
/* Check to see if there are blocks between a and b, if not
then ignore command */
if(!((&blocks[a] == stacks[s].top) && (blocks[a].block_below != &blocks[b])))
{
continue;
}
}

if(strncmp(on_over, "onto", 4) == 0)
{
return_blocks_above(b);
s = blocks[a].stack_number;
top = pop_stack(s, a);
s = blocks[b].stack_number;
push_stack(s, a, top);

} else
if(strncmp(on_over, "over", 4) == 0)
{
s = blocks[a].stack_number;
top = pop_stack(s, a);
s = blocks[b].stack_number;
push_stack(s, a, top);
}
} else
if(strncmp(command, "move", 4) == 0)
{
if(strncmp(on_over, "onto", 4) == 0)
{
return_blocks_above(a);
return_blocks_above(b);
s = blocks[a].stack_number;
pop_single(s);
s = blocks[b].stack_number;
push_single(s, a);
} else
if(strncmp(on_over, "over", 4) == 0)
{
return_blocks_above(a);
s = blocks[a].stack_number;
pop_single(s);
s = blocks[b].stack_number;
push_single(s, a);
}
}
}

output_state(number_of_blocks);
}[/c]
epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 »

it sucks to be insane, better find another hobby :P
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
ElSoloMar
New poster
Posts: 9
Joined: Thu Jan 09, 2003 9:42 am
Contact:

Post by ElSoloMar »

Hey epsilon0!

I believe this comment of your would be very helpful to every body in the board!! :-?
epsilon0 wrote:it sucks to be insane, better find another hobby :P
Izmunuti
New poster
Posts: 10
Joined: Mon Feb 10, 2003 7:22 am

Post by Izmunuti »

"Is this a correct interpretation?"

The problem description states that "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 ingored..."

So you must ignore it, whether the command is workable or not doesn't matter.

Iz
rbrogan
New poster
Posts: 3
Joined: Sun Feb 09, 2003 2:57 am

Post by rbrogan »

You are right. Reading the problem statement carefully is the cure for insanity. Thank you for your help.
Smeagol '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Compile Error on problem 101

Post by Smeagol '_' »

Hi, i wanted to know if somebody could tell me what's wrong with this code... it compiles fine in my computer but the judge won't take it...
thanks! :D
[cpp]
#include <iostream>
#include <cstdio>

using namespace std;

struct action{
unsigned int block1;
unsigned int block2;
char instruction[5];
char where[5];
};

void move(int x[][25], int w[][2], struct action y);
void pile(int x[][25], int w[][2], struct action y);
void print(int x[][25], int y[][2], int blocks);
void return_blocks(int x[][25], int w[][2], int y, int e1);
void pile_stack(int x[][25], int w[][2], int y, int e1, int e2);

int main()
{

action A;
unsigned int num_blocks =0;
int ref_array[25][2];
int block_world[25][25];
char linea[25];

cin >> num_blocks;
for(int i=0;i<num_blocks;i++)
{
block_world[0]=i;
ref_array[0]=i;
ref_array[1]=1;
}

cin.getline(linea,25);

while(strcmp(linea,"quit") != 0)
{
sscanf(linea, "%s %d %s %d", A.instruction, &A.block1,A.where, &A.block2);

if(A.block1!= A.block2 && (A.block1>0) && (A.block1 < 25) && (A.block2>0) && (A.block2 < 25))
{
if(strcmp(A.instruction,"move")==0)
move(block_world,ref_array,A);
else if(strcmp(A.instruction, "pile")==0)
pile(block_world,ref_array,A);
}
cin.getline(linea,25);
}

print(block_world, ref_array, num_blocks);

return 0;

}

void move(int x[][25], int w[][2],struct action y)
{
int e1= w[y.block1][0];
int e2= w[y.block2][0];

if (e1!=e2)
{
if(strcmp(y.where,"onto")==0)
{
return_blocks(x,w,y.block1,e1);
w[e1][1]= w[e1][1] -1;
return_blocks(x,w,y.block2,e2);
x[e2][w[e2][1]]= y.block1;
w[e2][1]= w[e2][1] +1;
w[y.block1][0]=e2;
}
else if(strcmp(y.where,"over")==0)
{
return_blocks(x,w,y.block1,e1);
w[e1][1]= w[e1][1] -1;
x[e2][w[e2][1]]= y.block1;
w[e2][1]=w[e2][1]+1;
w[y.block1][0]= e2;
}
}
}

void return_blocks(int x[][25], int w[][2], int y, int e1)
{
while (true)
{
if(x[e1][w[e1][1]-1] != y)
{
int temp= x[e1][w[e1][1]-1];
x[temp][w[temp][1]] = temp;
w[temp][0]= temp;
w[temp][1]=w[temp][1]+1;
w[e1][1]= w[e1][1]-1;
}
else
break;
}
}

void pile(int x[][25],int w[][2],struct action y)
{
int e2= w[y.block2][0];
int e1= w[y.block1][0];

if (e1!=e2)
{
if(strcmp(y.where,"onto")==0)
{
return_blocks(x,w,y.block2,e2);
pile_stack(x,w,y.block1,e1,e2);
w[e1][1]=w[e1][1]-1;
}
else if(strcmp(y.where,"over")==0)
{
pile_stack(x,w,y.block1,e1,e2);
w[e1][1]=w[e1][1] -1;
}
}
}

void print(int x[][25], int y[][2], int blocks)
{
for(int i=0; i<blocks; i++)
{
cout << i << ":";
if(y[1]!=0)
{
for(int j =0; j< y[1];j++)
cout << " " << x[j];
}
cout << endl;
}
}

void pile_stack(int x[][25],int w[][2], int y, int e1, int e2)
{
int count=0;

while(true)
{
if(x[e1][count] != y)
count++;
else
break;
}

for(int i=count; i<w[e1][1] ;i++)
{
x[e2][w[e2][1]]=x[e1];
w[e2][1]=w[e2][1]+1;
w[x[e1]][0]=e2;
}
w[e1][1]=count+1;

}
[/cpp]
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

Replace
[cpp]#include <cstdio>[/cpp]
with
[cpp]#include <stdio>[/cpp]
This might help.
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

you can use <cstdio>.
the problem is that you use strcmp, but you didn't include <cstring> or <string>.
25258FM
New poster
Posts: 5
Joined: Fri Nov 01, 2002 12:12 pm

Need test cases for 101

Post by 25258FM »

Could any one post some test cases for 101?
Smeagol '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Post by Smeagol '_' »

mmm.. but i thought strcmp didn't work with the string class... i've always used it without that cstring ( iguess :-? )
Smeagol '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Post by Smeagol '_' »

I got AC , you were right !! :D thanks!!
Smeagol '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Post by Smeagol '_' »

how bout ....

25
move 3 onto 3
move -1 over -900
pile 25 over 5
quit
alixx
New poster
Posts: 2
Joined: Mon Feb 17, 2003 11:55 am

101 in java... break my head... dont know why i have a WA

Post by alixx »

here is my code... something wrong???
[java]
import java.util.*;
import java.io.*;
class pos
{
private int x;
private int y;
pos(int posx, int posy)
{
x = posx;
y = posy;
}
void setpos(int posx, int posy)
{
x = posx;
y = posy;
}
int getposx(){return x;}
int getposy(){return y;}
}
class x
{
private int length;
private int[][] block;
private pos[] box;
x(int l)
{
length = l;
block = new int[length][length];
box = new pos[length];
for (int i = 0; i<length; i++)
{
block[0]=i;
box=new pos(i,0);
for (int j = 1; j<length; j++)
{
block[j]=-1;
}
}
}
void show()
{
for (int i = 0; i<length; i++)
{
System.out.print (i+":");
for (int j = 0; j<length; j++)
{
if(block[j]<0)
{
break;
}

System.out.print (" "+block[j]);
}
System.out.print ("\n");
}
}
void action(String s1, String s2, String s3, String s4)
{
int first = Integer.parseInt(s2);
int second = Integer.parseInt(s4);
if( (first!=second) &&
(((first>=0) && (first<=(length-1))) && ((second>=0) && (second<=(length-1)))
)
)
{
if(s1.equals("move"))
{
move(first, s3, second);
}
else if(s1.equals("pile"))
{
pile(first, s3, second);
}
}
}
private void move(int s1, String s3, int s2)
{
int i1 = box[s1].getposx();
int j1 = box[s1].getposy();
int i2 = box[s2].getposx();
int j2 = box[s2].getposy();
for (int i=j1+1; i<length; i++)
{
if(block[i1]<0) break;
block[block[i1]][0]=block[i1];
box[block[i1]].setpos(block[i1],0);
block[i1][i]=-1;
}
if(s3.equals("onto"))
{
for (int i=j2+1; i<length; i++)
{
if(block[i2][i]<0) break;
block[block[i2][i]][0]=block[i2][i];
box[block[i2][i]].setpos(block[i2][i],0);
block[i2][i]=-1;
}
block[i2][j2+1]=block[i1][j1];
block[i1][j1] = -1;
box[s1].setpos(i2,j2+1);
}
else if(s3.equals("over"))
{
for (int i = j2+1; i<length; i++)
{
if(block[i2][i]<0)
{
block[i2][i]=block[i1][j1];
box[block[i2][i]].setpos(i2,i);
block[i1][j1]=-1;
break;
}
}
}
}
private void pile(int s2, String s3, int s4)
{
int i1 = box[s2].getposx();
int i2 = box[s4].getposx();
int j1 = box[s2].getposy();
int j2 = box[s4].getposy();
if(s3.equals("onto"))
{
for (int i=j2+1; i<length; i++)
{
if(block[i2][i]<0) break;
block[block[i2][i]][0]=block[i2][i];
box[block[i2][i]].setpos(block[i2][i],0);
block[i2][i]=-1;
}
}
else if(s3.equals("over"))
{
for (int i = j2; i<length; i++)
{
if(block[i2][i+1]<0)
{
j2 = i;
break;
}
}
}
for (int i = j1, y=1; i<length; i++, y++)
{
if(block[i1][i]<0)break;
block[i2][j2+y]=block[i1][i];
box[block[i1][i]].setpos(block[i2][j2+y],j2+y);
block[i1][i]=-1;
}
}
}
class Main
{
public static void main (String args[]) throws Exception
{
Main myWork = new Main();
myWork.Begin();
}
void Begin() throws Exception
{
StringTokenizer pc;
String command, first;
int l = Integer.parseInt(new StringTokenizer(r.eadln(255)).nextToken());
x b = new x(l);
while (true)
{
command = r.eadln(255);
pc = new StringTokenizer(command);
first = pc.nextToken();
if (first.equals("quit")) break;
b.action(first,pc.nextToken(),pc.nextToken(),pc.nextToken());
}
b.show();
}
}
class r
{
static String eadln (int maxLg) // utility function to read from stdin
{
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));
}
}
[/java]
turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

Looks like you didn't skip illegal operations.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
alixx
New poster
Posts: 2
Joined: Mon Feb 17, 2003 11:55 am

Post by alixx »

what do you mean??? sori... am new here... tnx... :D
turuthok wrote:Looks like you didn't skip illegal operations.

-turuthok-
Post Reply

Return to “Volume 1 (100-199)”