101 - The Blocks Problem

[Krzysztof Duleba]

Your code is too big to find a single mistake in it. It is much more complex than necessary. It looks much too slow as well.
All operations can be coded in O(h), where h it the height of the stack the operation is done on.
As for the example input you asked for, try to search the forum for it. There are many posts about problem 101.

[El-idioto]

My app got accepted. I included part of my app below (the functions to handle the commands).

[cpp]
// 1. Any blocks on top of the source block are restored to their original stack.
// 2. Any blocks on top of the destination block are restored to their original stack.
// 3. Move the source block on top of the destination block
void CBlockStack::Cmd_MoveOnto(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the source block to their original stack
RestoreBlocksToOriginalStack(i16SrcStack, i16SrcPos + 1);

// Restore any blocks on top of the destination block to their original stack
RestoreBlocksToOriginalStack(i16DstStack, i16DstPos + 1);

// Move the source block on top of the destination block
m_ppi16Blocks[i16DstStack][i16DstPos+1] = i16SrcBlock;
m_ppi16Blocks[i16SrcStack][i16SrcPos] = -1;
}
}
}


//------------------------------------------------------------------------------------


// 1. Any blocks on top of the source block are restored to their original stack.
// 2. Move the source block to the top of the destination stack
void CBlockStack::Cmd_MoveOver(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the source block to their original stack
RestoreBlocksToOriginalStack(i16SrcStack, i16SrcPos + 1);

// Move the source block on top of the destination stack
m_ppi16Blocks[i16DstStack][GetTopOfStack(i16DstStack)+1] = i16SrcBlock;
m_ppi16Blocks[i16SrcStack][i16SrcPos] = -1;
}
}
}


//------------------------------------------------------------------------------------


// 1. Any blocks on top of the destination block are restored to their original stack.
// 2. The source block and any blocks above it are picked up.
// 3. The picked up blocks are placed on top of the stack of the destination block
void CBlockStack::Cmd_PileOnto(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Restore any blocks on top of the destination block to their original stack
RestoreBlocksToOriginalStack(i16DstStack, i16DstPos + 1);

// The destination block is now the top block of its stack, so we can pile the source block over the destination block
Cmd_PileOver(i16SrcBlock, i16DstBlock);
}
}
}


//------------------------------------------------------------------------------------


// 1. The source block and any blocks above it are picked up.
// 2. The picked up blocks are placed on top of the stack of the destination block.
void CBlockStack::Cmd_PileOver(int16 i16SrcBlock, int16 i16DstBlock)
{
// Do we have valid input parameters?
if(IsValidBlock(i16SrcBlock) && IsValidBlock(i16DstBlock))
{
int16 i16SrcStack, i16SrcPos, i16DstStack, i16DstPos, i16BlocksToMove;

// Get the positions of the source and destination blocks
FindBlock(i16SrcBlock, &i16SrcStack, &i16SrcPos);
FindBlock(i16DstBlock, &i16DstStack, &i16DstPos);

// Do we have different blocks and stacks?
if(i16SrcBlock != i16DstBlock && i16SrcStack != i16DstStack)
{
// Get the amount of blocks to move
i16BlocksToMove = GetTopOfStack(i16SrcStack) - i16SrcPos + 1;

// Copy the pile to the top of the destination stack
memcpy(&m_ppi16Blocks[i16DstStack][GetTopOfStack(i16DstStack)+1], &m_ppi16Blocks[i16SrcStack][i16SrcPos], i16BlocksToMove * sizeof(int16));

// Remove the pile from the source stack
memset(&m_ppi16Blocks[i16SrcStack][i16SrcPos], -1, i16BlocksToMove * sizeof(int16));
}
}
}
[/cpp]

If you need more help, let me know.

[El-idioto]

In case anyone wants to test this problem, I wrote a test case generator for my own app (helped me to get accepted):

[cpp]
#define TOT_ELEMS 20
#define TOT_ACTIONs 25

FILE *pfDst;

if(pfDst = fopen("Input.txt", "w"))
{
fprintf(pfDst, "%i\n", TOT_ELEMS);
srand((unsigned int)time(NULL));
for(int32 i32=0;i32<TOT_ACTIONS;i32++)
{
// Create a random action
fprintf(pfDst,
"%s %i %s %i\n",
rand() % 2 ? "move" : "pile",
rand() % TOT_ELEMS,
rand() % 2 ? "onto" : "over",
rand() % TOT_ELEMS);
}
fprintf(pfDst, "quit");
fclose(pfDst);
}
[/cpp]

[Ruslan Shevelyov]

Those char act1[4],act2[4] look suspiciously. Looks like you forgot to reserve space for trailing zero.
On my machine your program just leaves these boxes as is.

[palespower]

Plz I've submit my program on the blocks problem and I'm getting this message....

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.006 seconds.

Can any body help me?????

[InOutMoTo]

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

I don't think it will happen.
"3" cannot be the first block in No.2 area.
"4" cannot be 3's first place , either.

Think of the constructions and u will found that

I got AC without considering special cases.

It's not too difficult.

GoOd LuCk.

[Krzysztof Duleba]

Be sure that all your pointers are set correctly. Check twice your writing/reading from arrays, maby some indexes are inproper, the same for the iterators. This kind of error is quite easy to find, you shouldn't have any problem.

[Ji-Yung]

Though I've tried a lot of examples
I still can't find what's wrong in my code
Would somebody likes to help me?


[c]
/* @JUDGE_ID: 33940RW 101 C "101" */
#include<string.h>
#include<stdio.h>
typedef enum{MOVE_ONTO,MOVE_OVER,PILE_ONTO,PILE_OVER} ACTION;

char blocks[25][26];
int n_blocks =0;
char indexs[25][2];
char tempb[26];
char tempa[26];

void move(char a,char b,ACTION act)
{
int i =1;
int Xa=indexs[a][0];
int Ya=indexs[a][1];
int Xb=indexs[0];
int Yb=indexs[1];
int pile =1;

memcpy(tempb,&blocks[Xb],26);
memcpy(tempa,&blocks[Xa],26);
if (act==PILE_ONTO||act==PILE_OVER)
{
printf("called");
pile=tempa[0]-Ya+1;

if (act==PILE_OVER)
{
memcpy(&blocks[Xb][tempb[0]+1],&tempa[Ya],25-tempb[0]);
}
else
{
memcpy(&blocks[Xb][Yb+1],&tempa[Ya],25-Yb);
memcpy(&blocks[Xb][Yb+1+pile],&tempb[Yb+1],25-Yb-pile);
}

memset(&blocks[Xa][Ya],26,pile);

}else if (act==MOVE_OVER)
{
blocks[Xb][tempb[0]+1]=a;
memcpy(&blocks[Xa][Ya],&tempa[Ya+1], tempa[0] - Ya+1);

}else
{
blocks[Xb][Yb+1]=a;
memcpy(&blocks[Xb][Yb+2],&tempb[Yb+1],tempb[0]-Yb);
memcpy(&blocks[Xa][Ya],&tempa[Ya+1] , tempa[0] - Ya+1);
}

while (blocks[Xb][Yb+i]<26)
{
indexs[blocks[Xb][Yb+i]][1]=Yb +i;
indexs[blocks[Xb][Yb+i]][0]=Xb ;
i++;
}

if (act==MOVE_ONTO||act==MOVE_OVER)
{
i=1;
while (tempa[Ya+i]<26)
{
indexs[tempa[Ya+i]][1] --;
i++;
}
}

blocks[Xb][0]+=pile;
blocks[Xa][0]-=pile;

}

void output()
{
int i=0;
int j=0;

while( n_blocks>i)
{
printf("%d:",i);
for(j=1;j<25 && blocks[j]!=26;j++)
{
printf(" %d",blocks[j]);
}
i++;
printf("\n");
}
}


int main(int argc, char *argv[])
{

char cmd1[5];
char cmd2[5];
int a = 0;
int b = 0;
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
freopen("output","w", stdout);
#endif

scanf("%d",&n_blocks);
memset(blocks,26,sizeof(blocks));

for(;a<n_blocks;a++ )
{
blocks[a][0] = 1;
blocks[a][1] = a;
indexs[a][0] = a;
indexs[a][1] = 1;
}

while (scanf("%s %d %s %d",&cmd1,&a,&cmd2,&b)==4)
{

if (indexs[0]!= indexs[a][0])
{

if (cmd1[0]=='m' )
{
if (cmd2[2]=='e')
{
move(a,b,MOVE_OVER);
}else{
move(a,b,MOVE_ONTO);
}
}else if (cmd2[2]=='t')
{
move(a,b,PILE_ONTO);
}else if (cmd2[2]=='e')
{
move(a,b,PILE_OVER);
}
}
}
output();
return 0;
}

[/c]

Sorry because I am a newbie
I 've re-typesetting my codes

[xbeanx]

Your code is hard to read. Try editing it and adding tags to format it.

For example, stick [ cpp ] and [ /cpp ] in your message around your code.

[calinous]

I have the same problem. And it is not related to pointers or anything else - the code run flawlessly on both Visual C++6 and djgpp, ver 3.31 C compiler.
I assume it is related to the C compiler version of the jury - or maybe the runtime system

[calinous]

You can use freopen - works at least in Visual C++ 6

[Krzysztof Duleba]

No. Which version of MS Windows do you use? I bet it's none of the NT family. Am I right?

[calinous]

You just lost the bet, I am using Windows 2000.

But I was able to solve the runtime error - now I get WA. I assume my program was accessing bad indexes in an array (like a[-1][0], let's say). I don't know where the error is, but this is much better.

[Krzysztof Duleba]

Strange - Win2k should have noticed that you tried to access unreserved, protected memory. In such cases my Win2k dumps the core.

Anyway, the problem definitely was related to pointers

[Six of Three]

[c]printf("%2i:", pos);[/c]

This is similar to the Pascal code
[pascal]write(pos:2,':');[/pascal]
which reproduces the sample output with leading blanks in front of 0-9, but generates a presentation error. The correct output should be achieved by

[c]printf("%i:", pos);[/c]

or the Pascal version
[pascal]write(pos:1,':');[/pascal]

Such a trap door in the second problem... looks like if somebody wanted to tell us not to believe in sample outputs