101 - The Blocks Problem

[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]

it sucks to be insane, better find another hobby

[ElSoloMar]

Hey epsilon0!

I believe this comment of your would be very helpful to every body in the board!!

it sucks to be insane, better find another hobby

[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]

You are right. Reading the problem statement carefully is the cure for insanity. Thank you for your help.

[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!
[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]

Replace
[cpp]#include <cstdio>[/cpp]
with
[cpp]#include <stdio>[/cpp]
This might help.

[Adrian Kuegel]

you can use <cstdio>.
the problem is that you use strcmp, but you didn't include <cstring> or <string>.

[25258FM]

Could any one post some test cases for 101?

[Smeagol '_']

mmm.. but i thought strcmp didn't work with the string class... i've always used it without that cstring ( iguess )

[Smeagol '_']

I got AC , you were right !! thanks!!

[Smeagol '_']

how bout ....

25
move 3 onto 3
move -1 over -900
pile 25 over 5
quit

[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]

Looks like you didn't skip illegal operations.

-turuthok-

[alixx]

what do you mean??? sori... am new here... tnx...

Looks like you didn't skip illegal operations.

-turuthok-