## 102 - Ecological Bin Packing

Moderator: Board moderators

Balon
New poster
Posts: 8
Joined: Tue Nov 26, 2002 6:00 am
Have you noted follow sentence in problem?
If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.
I think you note the sentence , but your code got wrong order,
the write order to if() compares should be follow:
[cpp]
min = sum[2];
if(sum[1] < min)
{
min = sum[1];
j = 1;
}
if(sum[4] < min)
{
min = sum[4];
j = 4;
}
if(sum[6] < min)
{
min = sum[6];
j = 6;
}
if(sum[3] < min)
{
min = sum[3];
j = 3;
}
if(sum[5] < min)
{
min = sum[5];
j = 5;
}
[/cpp]
then try again

BTW. you should use a more readable style in your code, isn't the code in the follow more comprehensible ?
if you do so, we can read your code more easier, and you'll got more and useful help
[cpp]
// B is index 0
// G is index 1
// C is index 2

// here I use myMin because min is declared in C++ <algorithm> lib
int myMin = sum[0];

sum[1] = sum[0] - glass[0][0] - glass[1][2] - glass[2][1]; // BGC
sum[2] = sum[0] - glass[0][0] - glass[1][1] - glass[2][2]; // BCG
sum[3] = sum[0] - glass[0][2] - glass[1][0] - glass[2][1]; // CBG
sum[4] = sum[0] - glass[0][2] - glass[1][1] - glass[2][0]; // CGB
sum[5] = sum[0] - glass[0][1] - glass[1][0] - glass[2][2]; // GBC
sum[6] = sum[0] - glass[0][1] - glass[1][2] - glass[2][0]; // GCB

for(int i=1; i<=6; ++i)
{
if(sum < myMin)
{
myMin = sum;
j = i;
}
}

switch(j)
{
case 1:
printf("BCG");
break;
case 2:
printf("BGC");
break;
case 3:
printf("CBG");
break;
case 4:
printf("CGB");
break;
case 5:
printf("GBC");
break;
default:
printf("GCB");
}
printf(" %d\n", myMin);
[/cpp]

Balon
New poster
Posts: 8
Joined: Tue Nov 26, 2002 6:00 am
same error occurs more than once:
/*"BCG";*/
menora[0]=caixas[1]+caixas[2]+caixas[3]+caixas[4]+caixas[6]+caixas[8];
/*"BGC";*/
menora[5]=caixas[1]+caixas[2]+caixas[3]+caixas[5]+caixas[6]+caixas[7];
/*"CBG";*/
menora[1]=caixas[0]+caixas[1]+caixas[4]+caixas[5]+caixas[6]+caixas[8];
/*"CGB";*/
menora[4]=caixas[0]+caixas[1]+caixas[3]+caixas[5]+caixas[7]+caixas[8];
/*"GBC";*/
menora[3]=caixas[0]+caixas[2]+caixas[4]+caixas[5]+caixas[6]+caixas[7];
/*"GCB";*/
menora[2]=caixas[0]+caixas[2]+caixas[3]+caixas[4]+caixas[7]+caixas[8];
should be:

[cpp]
/*"BCG";*/
menora[0]=caixas[1]+caixas[2]+caixas[3]+caixas[4]+caixas[6]+caixas[8];
/*"BGC";*/
menora[1]=caixas[1]+caixas[2]+caixas[3]+caixas[5]+caixas[6]+caixas[7];
/*"CBG";*/
menora[2]=caixas[0]+caixas[1]+caixas[4]+caixas[5]+caixas[6]+caixas[8];
/*"CGB";*/
menora[3]=caixas[0]+caixas[1]+caixas[3]+caixas[5]+caixas[7]+caixas[8];
/*"GBC";*/
menora[4]=caixas[0]+caixas[2]+caixas[4]+caixas[5]+caixas[6]+caixas[7];
/*"GCB";*/
menora[5]=caixas[0]+caixas[2]+caixas[3]+caixas[4]+caixas[7]+caixas[8];
[/cpp]

passwd
New poster
Posts: 14
Joined: Thu Dec 05, 2002 11:20 pm

### P 102 - Worg answer, why ?

hi,

I'm trying to solve problem 102 , but I'm getting wrong answer and I
don't know why , it seem to be correct ...
I'm sendind the source code, please, if someone can help me ...

Code: Select all

``````[c]
#include <stdio.h>

int main() {

unsigned long int b[3];
unsigned long int g[3];
unsigned long int c[3];

while( scanf("%d %d %d %d %d %d %d %d %d",&b[0],&g[0],&c[0],
&b[1],&g[1],&c[1],&b[2],&g[2],&c[2]) !=-1) {

char seq[3]={'B','C','G'};
unsigned long int min;
unsigned long int bcg=b[1]+b[2]+c[0]+c[2]+g[0]+g[1];
unsigned long int bgc=b[1]+b[2]+g[0]+g[2]+c[0]+c[1];
unsigned long int cbg=c[1]+c[2]+b[0]+b[2]+g[0]+g[1];
unsigned long int cgb=c[1]+c[2]+g[0]+g[2]+b[0]+b[1];
unsigned long int gbc=g[1]+g[2]+b[0]+b[2]+c[0]+c[1];
unsigned long int gcb=g[1]+g[2]+c[0]+c[2]+b[0]+b[1];

min=bcg;
if(bgc<min) { min=bgc; seq[0]='B'; seq[1]='G'; seq[2]='C'; };
if(cbg<min) { min=cbg; seq[0]='C'; seq[1]='B'; seq[2]='G'; };
if(cgb<min) { min=cgb; seq[0]='C'; seq[1]='G'; seq[2]='B'; };
if(gbc<min) { min=gbc; seq[0]='G'; seq[1]='B'; seq[2]='C'; };
if(gcb<min) { min=gbc; seq[0]='G'; seq[1]='C'; seq[2]='B'; };

printf("%c%c%c %d\n",seq[0],seq[1],seq[2],min);
}

return 0;
}
[/c]``````

thank's ..
[/c]

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### Re: P 102 - Worg answer, why ?

passwd wrote: hi,

I'm trying to solve problem 102 , but I'm getting wrong answer and I
don't know why , it seem to be correct ...
I'm sendind the source code, please, if someone can help me ...

Code: Select all

``````[c]
min=bcg;
if(bgc<min) { min=bgc; seq[0]='B'; seq[1]='G'; seq[2]='C'; };
if(cbg<min) { min=cbg; seq[0]='C'; seq[1]='B'; seq[2]='G'; };
if(cgb<min) { min=cgb; seq[0]='C'; seq[1]='G'; seq[2]='B'; };
if(gbc<min) { min=gbc; seq[0]='G'; seq[1]='B'; seq[2]='C'; };
if(gcb<min) { min=gbc; seq[0]='G'; seq[1]='C'; seq[2]='B'; };

[/c]``````

thank's ..
[/c]
the problem says
If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.
i think u can smell it

passwd
New poster
Posts: 14
Joined: Thu Dec 05, 2002 11:20 pm

### Re: Re: P 102 - Worg answer, why ?

I know that the problem says if more than one order of brown, green,
and clear bins yields the minimum number of movements then
the alphabetically first string representing a minimal configuration
should be printed

but I don

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### Re: Re: P 102 - Worg answer, why ?

[quote="passwd"]
but I don

james-b
New poster
Posts: 6
Joined: Sat Dec 07, 2002 2:48 pm

### Prolem 102: Why Out Limit Exceeded??

I don't quite understand why I got this result...

[c]
#include<stdio.h>
#include<string.h>
void main()
{
int k;
long sum,tmp;
long B[3],G[3],C[3];
while(scanf("%D%D%D%D%D%D%D%D%D",&B[0],&G[0],&C[0],&B[1],&G[1],&C[1],&B[2],&G[2],&C[2])!=EOF)
{
sum=B[1]+B[2]+C[0]+C[2]+G[0]+G[1];
tmp=sum;
k=1;
sum=B[1]+B[2]+G[0]+G[2]+C[0]+C[1];
if(tmp>sum)
{
tmp=sum;
k=2;
}
sum=C[1]+C[2]+B[0]+B[2]+G[0]+G[1];
if(tmp>sum)
{
tmp=sum;
k=3;
}
sum=C[1]+C[2]+G[0]+G[2]+B[0]+B[1];
if(tmp>sum)
{
tmp=sum;
k=4;
}
sum=G[1]+G[2]+B[0]+B[2]+C[0]+C[1];
if(tmp>sum)
{
tmp=sum;
k=5;
}
sum=G[1]+G[2]+C[0]+C[2]+B[0]+B[1];
if(tmp>sum)
{
tmp=sum;
k=6;
}
switch(k)
{
case 1:
printf("BCG");
break;
case 2:
printf("BGC");
break;
case 3:
printf("CBG");
break;
case 4:
printf("CGB");
break;
case 5:
printf("GBC");
break;
case 6:
printf("GCB");
break;
default:
printf("\0");
}
printf(" %ld\n",tmp);
}
}[/c][/c]

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
the printf("\0"); is a bit weird, but i wouldn't mind about it.

did you consider the fact that scanf could never return EOF, but could return ERROR instead?
try to use something like while(scanf(......) == 9) instead of != EOF

also.. you do not solve all the problem. what happens if several solutions are as good as one another? you should pick up the one that comes first alphabetically. i don't see it in your program.

plus, your program is ugly imagine if there were 10 bins. would you really write 10! tests like this in sequence?

good luck
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
Can I ask a small question?What does "scanf(....)==9" means?Doesnt that means I read 9 stuff with the function scanf?Or 9 is a special constant?(I really don't know this )

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
scanf returns the number of things scanned in, so if you were to scan in 2 things, you would have this:

while ( 2 == scanf( "%d %d", &a, &b ) )

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
ya.I got it.Sorry for asking such a stupid question like this.(I didn't read it very carefully )

james-b
New poster
Posts: 6
Joined: Sat Dec 07, 2002 2:48 pm
Yeah,epsilon.I tried what you said,and I got accepted.
Because the algrithm is easy,I just used an direct program(sure an ugly one).I will try to simplify my program after then.

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

### few tips reqd..

i got AC using the above ugly method.
can u tell me what a better method wud be..

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
you could read my code. note that it's still not very elegant, since i handtyped the table of permutations... if there were more bin, i'd rather generate this table at run time (which is not difficult).

[c]/* Ecological Bin Packing */

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

#define BROWN 0
#define GREEN 1
#define CLEAR 2

char colors[] = "BGC";

int perms[6][3] = { {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };

void get_opti(int *bottles, char *order, int *min)
{
int i,j;
int moves;
char tmp_order[4];
*min = -1;
for (i=0; i<6; i++)
{
moves = bottles[3 + perms[0]] + bottles[6 + perms[0]]
+ bottles[perms[1]] + bottles[6 + perms[1]]
+ bottles[perms[2]] + bottles[3 + perms[2]];

for (j=0;j<3;j++)
tmp_order[j] = colors[perms[j]];
tmp_order[3] = '\0';

if (*min == -1 || moves < *min)
{
*min = moves;
strcpy(order,tmp_order);
}
else if (moves == *min)
if (strcmp(order, tmp_order) > 0)
strcpy(order,tmp_order);
}
}

int main()
{
int bottles[9];
int min;
char order[4];
while(scanf("%d %d %d %d %d %d %d %d %d", &bottles[0], &bottles[1], &bottles[2],
&bottles[3], &bottles[4], &bottles[5],
&bottles[6], &bottles[7], &bottles[8]) == 9)
{
get_opti(bottles,order,&min);
printf("%s %d\n",order,min);
}
return EXIT_SUCCESS;
}
[/c]

the idea behind generating a table of all possible permutations is to use a recursive function, along with a table that you pass as an argument, and which tells you what item has already been used.

such code would look like:

char sequence[] = "0123456789";

void make_perms()
{
char table[10] = {0,0,0,0,0,0,0,0,0,0};
make_perms_2(table,0);
}

void make_perms_2(char *tab, int n)
{
int i;
char new_table[10];
if (n == 10)
{
printf("%s\n",sequence);
return;
}
for (i=0; i<10; i++)
if (!tab)
{
memcpy(new_table,tab,10);
new_table = 1;
sequence[n] = '0'+i;
make_perms_2(new_table,n+1);
}
}

it should print all permutations of numbers 0-9 ... it's easy to modify this code to works with any number of items... please note that i just typed this code, without testing it
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

### thanx ......

thanx for ur reply and data on how to generate permutations
but then my query was r u supposed to do n! permutations and check up or is there a better method.