## 101 - The Blocks Problem

Moderator: Board moderators

globi
New poster
Posts: 15
Joined: Wed Apr 23, 2003 2:44 pm
Location: Warsaw
Contact:
1) Could you move your code into "C++" statements ? It will be readable.

3) Possibly, the error occurs, because you are using classes in some uncompatible
style. This problem is realy easy, so you musn't use classes. One array should be enought.

Yo

kareltje333
New poster
Posts: 2
Joined: Fri May 16, 2003 1:07 pm

### 101 move a onto b problem

Lets suppose i've created this situation in a matrix:

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

What happens if i get the command "move 1 onto 4"?

After returning any blocks on 1 to their initial state, the 3 goes to row 3, the 2 to row 2. I suppose should give:
0: 0
1: 1
2: 2
3: 4 5 3
4:
5:
6: 6
7: 7

Then I suppose all blocks above 4 are returned to their initital posititon?
but what happens to 3 which is on row 3? and what happens to 5?

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Before asking this question, perhaps you should think about whether you could arrive at such a situation using the instructions available.

seg10
New poster
Posts: 4
Joined: Thu May 29, 2003 7:49 am

### 101: So confused... Invalid Memory Reference!

This code that I've written for this problem is completely straight forward, and I had fully expected a correct answer... and yet I managed die a dishonorable death by a sig11 wielding an invalid memory reference. I'd be extremely greatful if a guru or code mage would spend the small insignificant amount of time likely needed to decipher my work and point out my problem. Thanks alot!
[c]
#include <stdio.h>

struct b_node {
int magnitude;
struct b_node *previous;
struct b_node *next;
};

void return_all_on_top(struct b_node *base);
struct b_node *top(struct b_node *base);

int main(){
int counter;
int max;
int bufferA;
int bufferB;
char com_bufferA[8];
char com_bufferB[8];

struct b_node b_index[25];

struct b_node *current;

scanf("%d", &max);
for(counter = 0; counter < max; counter++){
b_index[counter].next = NULL;
b_index[counter].previous = NULL;
b_index[counter].magnitude = counter;
}

while(scanf("%s %d %s %d", &com_bufferA, &bufferA, &com_bufferB, &bufferB) > 1){
if(b_index[bufferA].previous != NULL){
b_index[bufferA].previous->next = NULL;
}

if(com_bufferA[0] == 'm'){

return_all_on_top(b_index[bufferA].next);

if(com_bufferB[1] == 'n'){
/* 'move onto' */
return_all_on_top(b_index[bufferA].next);
return_all_on_top(b_index[bufferB].next);

b_index[bufferA].previous = &b_index[bufferB];
b_index[bufferA].previous->next = &b_index[bufferA];
}else{
/* 'move over' */
return_all_on_top(b_index[bufferA].next);

b_index[bufferA].previous = top(&b_index[bufferB]);
b_index[bufferA].previous->next = &b_index[bufferA];
}
}else{
if(com_bufferB[1] == 'n'){
/* 'pile onto' */
return_all_on_top(b_index[bufferB].next);
b_index[bufferA].previous = &b_index[bufferB];
b_index[bufferA].previous->next = &b_index[bufferA];
}else{
/* 'pile over' */
b_index[bufferA].previous = &b_index[bufferB];
b_index[bufferA].previous->next = &b_index[bufferA];
}
}
}

for(counter = 0; counter < max; counter++){
printf("%d:", counter);

current = &b_index[counter];
if(current->previous == NULL){
while(current != NULL){
printf(" %d", current->magnitude);
current = current->next;
}
}
printf("\n");
}
}
void return_all_on_top(struct b_node *source){
if(source != NULL){
return_all_on_top(source->next);

if(source->previous != NULL){
source->previous->next = NULL;
}else{
source->previous = NULL;
}
source->next = NULL;
}
}
struct b_node *top(struct b_node *base){
if(base->next == NULL){
return base;
}else{
}
}
[/c]

seg10
New poster
Posts: 4
Joined: Thu May 29, 2003 7:49 am

### Problem with the bot?

I have to assume from the lack of responses that no one really knows what's wrong with the code. Could it be that the bot that judges problem 101 has a flaw that prohibits it from accepting this program?

BaronSyntax
New poster
Posts: 3
Joined: Fri Jun 06, 2003 11:54 pm
Contact:
I too recieve this message, for reaons I have not yet determined
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.166 seconds.
I have tried all the commands and tested my bounds checking so I know that things are always in bounds.

seg10
New poster
Posts: 4
Joined: Thu May 29, 2003 7:49 am

### problem solved

*edit* what I thought the problem with my program was, isn't. I still have no idea... **sigh**...

Pibben
New poster
Posts: 3
Joined: Sat Jun 14, 2003 9:45 am

### 101 - Memory Limit Exceeded

The code works flawlessly on the given examples. Any ideas?

[cpp] #include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <string>
using namespace std;

typedef vector< list<int> > blocktype;

void printblocks(blocktype b, vector<int> i) {
int c=0;
for(blocktype::iterator bpos = b.begin(); bpos!=b.end(); ++bpos, ++c) {
cout << c << ":";
for(list<int>::iterator lpos = bpos->begin(); lpos!=bpos->end(); ++lpos) {
cout << " " << *lpos;
}
cout << endl;
}
}

void reset(blocktype& block, int alist, int arg, vector<int>& index) {
list<int>::iterator fpos = find(block[alist].begin(), block[alist].end(), arg);

for(list<int>::iterator lpos = ++fpos; lpos!=block[alist].end();++lpos) {
index[*lpos] = *lpos;
block[*lpos].push_back(*lpos);
}
block[alist].erase(fpos,block[alist].end());
}

void updateindex(list<int>& alist, int b, vector<int>& index) {
for(list<int>::iterator lpos = alist.begin(); lpos!=alist.end(); ++lpos) {
index[*lpos] = b;
}
}

int main() {
int num_blocks;

cin >> num_blocks;

blocktype blocks(num_blocks,list<int>(0));
vector<int> index(num_blocks);

int c=0;
for(blocktype::iterator pos = blocks.begin(); pos!=blocks.end(); ++pos, ++c) {
pos->push_back(c);
index[c] = c;
}

while(true) {
string command1, command2;
int arg1,arg2,a,b;

cin >> command1;
if(command1=="quit") {
printblocks(blocks,index);
exit(0);
}

cin >> arg1 >> command2 >> arg2;

if(command1=="move") {
if(command2=="onto") {
a = index[arg1];
b = index[arg2];
reset(blocks,a,arg1,index);
reset(blocks,b,arg2,index);

list<int>::iterator pos = find(blocks[a].begin(),blocks[a].end(),arg1);
blocks.splice(blocks.end(),blocks[a], pos , blocks[a].end());
updateindex(blocks,b,index);
} else if(command2=="over") {
a = index[arg1];
b = index[arg2];
reset(blocks,a,arg1,index);

list<int>::iterator pos = find(blocks[a].begin(),blocks[a].end(),arg1);
blocks.splice(blocks.end(),blocks[a], pos , blocks[a].end());
updateindex(blocks,b,index);
}
} else if(command1=="pile") {
if(command2=="onto") {
a = index[arg1];
b = index[arg2];
reset(blocks,b,arg2,index);

list<int>::iterator pos = find(blocks[a].begin(),blocks[a].end(),arg1);
blocks.splice(blocks.end(),blocks[a], pos , blocks[a].end());
updateindex(blocks,b,index);
} else if(command2=="over") {
a = index[arg1];
b = index[arg2];

list<int>::iterator pos = find(blocks[a].begin(),blocks[a].end(),arg1);
blocks.splice(blocks[b].end(),blocks[a], pos , blocks[a].end());
updateindex(blocks[b],b,index);
}
}
}
}

[/cpp]

undies
New poster
Posts: 1
Joined: Tue Jul 01, 2003 6:16 pm
I had a similar problem - thought I had it right but got segfaults.

I looked in the forums and a found a few test cases - the one below was helpful.

After running this test case I found there were some serious bugs in my code.

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

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:

hope this helps...

SilverSprite
New poster
Posts: 5
Joined: Mon Jul 14, 2003 7:14 am
Location: Windsor Ontario

### 101 -- no idea how to play the game

I have no idea how to play this game. Every time i follow the game instructions.. i never get to the result that the computer outputs. Could someone play this game and show me the step by step? Thanks in advance!
Few are those who see with their own eyes and feel with their own hearts.

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
My code got accepted.
Here is an extended sample (randomly generated).
If you want more samples (or the source code to generate them), email me at SHBouwhuis@Hotmail.com

5
move 4 onto 4
0: 0
1: 1
2: 2
3: 3
4: 4
move 2 over 4
0: 0
1: 1
2:
3: 3
4: 4 2
pile 2 onto 4
0: 0
1: 1
2:
3: 3
4: 4 2
move 1 onto 4
0: 0
1:
2: 2
3: 3
4: 4 1
move 2 onto 0
0: 0 2
1:
2:
3: 3
4: 4 1
move 2 over 3
0: 0
1:
2:
3: 3 2
4: 4 1
move 3 onto 4
0: 0
1: 1
2: 2
3:
4: 4 3
move 3 onto 3
0: 0
1: 1
2: 2
3:
4: 4 3
move 4 over 0
0: 0 4
1: 1
2: 2
3: 3
4:
pile 1 onto 1
0: 0 4
1: 1
2: 2
3: 3
4:
pile 0 over 2
0:
1: 1
2: 2 0 4
3: 3
4:
move 2 onto 0
0:
1: 1
2: 2 0 4
3: 3
4:
pile 1 onto 4
0:
1:
2: 2 0 4 1
3: 3
4:
pile 3 onto 3
0:
1:
2: 2 0 4 1
3: 3
4:
move 4 onto 4
0:
1:
2: 2 0 4 1
3: 3
4:
pile 0 over 3
0:
1:
2: 2
3: 3 0 4 1
4:
move 2 over 1
0:
1:
2:
3: 3 0 4 1 2
4:
pile 1 onto 0
0:
1:
2:
3: 3 0 4 1 2
4:
quit
0:
1:
2:
3: 3 0 4 1 2
4:

wittgens
New poster
Posts: 5
Joined: Wed Jul 16, 2003 6:58 am

### 101 I don't know why is WA?

my source is following statements.
but, I got a Wrong Answer..
I don't know why.
^^*
[cpp]
#include<iostream>
#include<vector>
using namespace std;

int move_onto(vector<int> *block, int n, int a, int b)
{
vector<int>::iterator vi1, vi2;
int i, j;
for(i=0; i<n; i++)
for(vi1=block.begin(); vi1!=block.end(); vi1++)
if(*vi1==a) {
for(j=0; j<n; j++)
for(vi2=block[j].begin(); vi2!=block[j].end(); vi2++)
if(*vi2==b) {
if(i==j) return -1;
if(block.size()>1 && a!=block.back()) {
cout << "return: ";
cout << block.back() << endl;
while(a!=block.back()) {
block[block.back()].push_back(block.back());
block.pop_back();
}
}

if(block[j].size()>1 && b!=block[j].back()) {
while(b!=block[j].back()) {
block[block[j].back()].push_back(block[j].back());
block[j].pop_back();
}
}
block.erase(vi1);
block[j].insert(vi2+1, a);
return 0;
}

break;
} // endof if(*vi1..)

return -1;
}

int move_over(vector<int> *block, int n, int a, int b)
{
vector<int>::iterator vi1, vi2;
int i, j;
for(i=0; i<n; i++)
for(vi1=block[i].begin(); vi1!=block[i].end(); vi1++)
if(*vi1==a) {
for(j=0; j<n; j++)
for(vi2=block[j].begin(); vi2!=block[j].end(); vi2++)
if(*vi2==b) {
if(i==j) return -1;
if(block[i].size()>1 && a!=block[i].back()) {
while(a!=block[i].back()) {
block[block[i].back()].push_back(block[i].back());
block[i].pop_back();
}
}
block[i].erase(vi1);
vi2++;
block[j].push_back(a);
return 0;
}

break;
}
return -1;
}

int pile_onto(vector<int> *block, int n, int a, int b)
{
vector<int>::iterator vi1, vi2, old_ei;
vector<int> tmp;
int i, j;
for(i=0; i<n; i++)
for(vi1=block[i].begin(); vi1!=block[i].end(); vi1++)
if(*vi1==a) {
tmp.insert(tmp.begin(), vi1, block[i].end());
for(j=0; j<n; j++)
for(vi2=block[j].begin(); vi2!=block[j].end(); vi2++)
if(*vi2==b) {
if(i==j) return -1;
block[i].erase(vi1, block[i].end());
block[j].insert(vi2+1, tmp.begin(), tmp.end());
return 0;
} //end of if(*vi2..)
} //end of if(*vi1==..)
return -1;
}

int pile_over(vector<int> *block, int n, int a, int b)
{
vector<int>::iterator vi1, vi2, old_ei;
vector<int> tmp;
int i, j;
for(i=0; i<n; i++)
for(vi1=block[i].begin(); vi1!=block[i].end(); vi1++)
if(*vi1==a) {
tmp.insert(tmp.begin(), vi1, block[i].end());
for(j=0; j<n; j++)
for(vi2=block[j].begin(); vi2!=block[j].end(); vi2++)
if(*vi2==b) {
if(i==j) return -1;
block[i].erase(vi1, block[i].end());
block[j].insert(block[j].end(), tmp.begin(), tmp.end());
return 0;
}
} //end of if(*vi1==a)
return -1;
}

void output(vector<int> *v, int n)
{
vector<int>::iterator vi;
for(int i=0; i<n; i++) {
cout << i << ": ";
for(vi=v[i].begin(); vi!=v[i].end(); vi++)
cout << *vi << " ";
cout << endl;
}
}

int parse_command(char *c1, int a, char *c2, int b)
{
if(!strcmp(c1, "move")) {
if(!strcmp(c2, "onto")) {
return 1;
}
else if(!strcmp(c2, "over")) {
return 2;
}
else return -1;
}
else if(!strcmp(c1, "pile")) {
if(!strcmp(c2, "onto")) {
return 3;
}
else if(!strcmp(c2, "over")) {
return 4;
}
else return -1;
}
else {
return -1;
}
}

void initiate(vector<int> *v, int n)
{
for(int i=0; i<n; i++) v[i].push_back(i);
}

int main()
{
int n, a, b, cmd_num;
char command1[5];
char command2[5];

cin >> n;
if(n>26) exit(0);
vector<int> block[n];
initiate(block, n); //initate
while(!cin.eof()) {
cin >> command1;
if(!strcmp(command1,"quit")) break;
cin >> a; cin >> command2; cin >> b;
while(cin.get() != '\n') ;

if(a==b) {
continue;
}
cmd_num=parse_command(command1, a, command2, b);
switch(cmd_num) {
case 1:
move_onto(block, n, a, b);
break;
case 2:
move_over(block, n, a, b);
break;
case 3:
pile_onto(block, n, a, b);
break;
case 4:
pile_over(block, n, a, b);
break;
default:
break;
}
}
output(block, n);
return 0;
}
[/cpp][/cpp]

Grey
New poster
Posts: 2
Joined: Sun Jul 20, 2003 6:13 pm

### 101-always WA,don't know why?

I'm wondering if anybody would be kind enough to take a look of my program.

I found some tests posted on the board before,and my program worked successfully.

[c]

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

int main(void)
{
char act1[4],act2[4],changeline;
int num,a,b,block[100][100],finda_i,finda_j,findb_i,findb_j;
int i,j,target;

scanf("%d",&num);

scanf("%s",act1);

for (i=0;i<25;i++)
{
for (j=0;j<25;j++)
{
if ((i<num) && (j==0))
block[0] = i;
else block[j] = -1;
}
}

while (strcmp(act1,"quit")!=0)
{
scanf(" %d %s %d",&a,act2,&b);
finda_i = -1;
finda_j = -1;
findb_i = -1;
findb_j = -1;
if ((a>=0) && (b>=0)){
if ((strcmp(act1,"move") == 0) && (a<num) && (b<num) && (a!=b))
{
if (strcmp(act2,"onto") == 0)
{
for (i=0;i<num;i++)
{
for (j=0;j<num;j++)
{
if (block[j] == a)
{
finda_i = i;
finda_j = j;
}else if (block[j] == b)
{
findb_i = i;
findb_j = j;
}
}
}
if (finda_i != findb_i)
{
block[finda_i][finda_j] = -1;
for (j=finda_j+1;j<num;j++)
{
if (block[finda_i][j] != -1)
{
block[block[finda_i][j]][0] = block[finda_i][j];
block[finda_i][j] = -1;
}else break;
}
for (j=findb_j+1;j<num;j++)
{
if (block[findb_i][j] != -1)
{
block[block[findb_i][j]][0] = block[findb_i][j];
block[findb_i][j] = -1;
}else break;
}
block[findb_i][findb_j+1] = a;
}
}else if (strcmp(act2,"over") == 0)
{
for (i=0;i<num;i++)
{
for (j=0;j<num;j++)
{
if (block[j] == a)
{
finda_i = i;
finda_j = j;
}else if (block[j] == b) {
findb_i = i;
findb_j = j;
}
}
}
if (finda_i != findb_i)
{
block[finda_i][finda_j] = -1;
for (j=finda_j+1;j<num;j++)
{
if (block[finda_i][j]!= -1)
{
block[block[finda_i][j]][0] = block[finda_i][j];
block[finda_i][j] = -1;
}else break;
}
for (j=findb_j+1;j<num;j++)
{
if (block[findb_i][j] == -1)
{
block[findb_i][j] = a;
break;
}
}
}
}
}else if ((strcmp(act1,"pile") == 0) && (a<num) && (b<num) && (a!=b))
{
if (strcmp(act2,"onto") == 0)
{
for (i=0;i<num;i++)
{
for (j=0;j<num;j++)
{
if (block[j] == a)
{
finda_i = i;
finda_j = j;
}else if (block[j] == b)
{
findb_i = i;
findb_j = j;
}
}
}
if (finda_i != findb_i)
{
for (j=findb_j+1;j<num;j++)
{
if (block[findb_i][j] != -1)
{
block[block[findb_i][j]][0] = block[findb_i][j];
block[findb_i][j] = -1;
}else break;
}
findb_j++;
for (j=finda_j;j<num;j++)
{
if (block[finda_i][j] != -1)
{
block[findb_i][findb_j] = block[finda_i][j];
findb_j++;
block[finda_i][j] = -1;
}else break;
}
}
}else if (strcmp(act2,"over") == 0)
{
for (i=0;i<num;i++)
{
target =0;
for (j=0;j<num;j++)
{
if (block[j] == a)
{
finda_i = i;
finda_j = j;
}else if (block[j] == b)
target = 1;

if ((target == 1) && (block[i][j] == -1))
{
target = 0;
findb_i = i;
findb_j = j;
}
}
}
if (finda_i != findb_i)
{
for (j=finda_j;j<num;j++)
{
if (block[finda_i][j] != -1)
{
block[findb_i][findb_j] = block[finda_i][j];
findb_j++;
block[finda_i][j] = -1;
}else break;
}
}
}
}}

scanf("%s",act1);
}

for (i=0;i<num;i++)
{
printf("%d:",i);
for (j=0;j<num;j++)
{
if (block[i][j] != -1)
{
printf(" %d",block[i][j]);
}
}
printf("\n");
}
return 0;
}
[/c]
Last edited by Grey on Mon Jul 21, 2003 6:47 am, edited 1 time in total.

Grey
New poster
Posts: 2
Joined: Sun Jul 20, 2003 6:13 pm
Or,
give me more complex test samples.

I think as more as I could.

Thanx,again.

wittgens
New poster
Posts: 5
Joined: Wed Jul 16, 2003 6:58 am

### give me more complex examples

I have many time tested by this source, but I got WA..
I don't know why~
please, give me more complex examples for testing.
Hi, My name is Jeong-soo, Kim.
I'm Korean.
nice to meet you^^*