102 - Ecological Bin Packing

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Balon
New poster
Posts: 8
Joined: Tue Nov 26, 2002 6:00 am

Post by Balon » Wed Nov 27, 2002 2:53 pm

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 :wink: , 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 ? 8)
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

Post by Balon » Wed Nov 27, 2002 3:18 pm

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 ?

Post by passwd » Thu Dec 05, 2002 11:27 pm

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]

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

Re: P 102 - Worg answer, why ?

Post by rakeb » Sat Dec 07, 2002 6:17 pm

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 :wink:

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

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

Post by passwd » Sat Dec 07, 2002 7:34 pm

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

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

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

Post by rakeb » Sun Dec 08, 2002 11:57 am

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

Post by james-b » Thu Dec 19, 2002 5:49 am

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.

Post by epsilon0 » Thu Dec 19, 2002 11:08 am

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

Post by FlyDeath » Thu Dec 19, 2002 2:27 pm

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 :o )

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Dec 19, 2002 2:31 pm

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

Post by FlyDeath » Thu Dec 19, 2002 2:44 pm

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

Post by james-b » Thu Dec 19, 2002 5:17 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.

Thanks for your help !!

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

few tips reqd..

Post by off_algos » Thu Dec 26, 2002 10:47 am

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.

Post by epsilon0 » Fri Dec 27, 2002 9:27 am

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 :P
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 ......

Post by off_algos » Sun Dec 29, 2002 8:58 am

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.

Post Reply

Return to “Volume 1 (100-199)”