101 - The Blocks Problem

[globi]

1) Could you move your code into "C++" statements ? It will be readable.

2) Remove comments from your code.

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]

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]

Before asking this question, perhaps you should think about whether you could arrive at such a situation using the instructions available.

[seg10]

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{
return top(base->next);
}
}
[/c]

[seg10]

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]

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]

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

[Pibben]

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]

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

answer should be

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]

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!

[El-idioto]

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]

my source is following statements.
but, I got a Wrong Answer..
I don't know why.
please, tell me 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]

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.

I can't find where the problem is. Please help me,thanx.

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

[Grey]

Or,
give me more complex test samples.

I think as more as I could.

Thanx,again.

[wittgens]

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.