Challenge 8

That was an odd message. What could it mean? The only place aboard the ship to get a cup of coffee is the coffee machine in the Crew Quarters' common room. No one's around so you put the propaganda paper down on the table and start to make a cup of coffee for yourself.

Suddenly, you hear a small high-pitched voice behind you. Out of the corner of your eye, you see what looks like a small Aurawrought being, about 20cm tall.

You whip around, keeping an eye out for some sort of weapon you might be able to use, all while trying not to break eye contact with the creature. Sensing your distress, it quickly tells you that it has come in peace, explaining further that it is a defector from the Aurawrought army. It left the propaganda on the ship in hopes someone would find it and get in touch, because it has important information to share.

The Aurawrought have long devoted themselves to Eos, dangerous goddess of the dawn, and have lamented her imprisonment in the galactic vortex where she has been held for centuries. Recently, however, the scientists among the Aurawrought have come up with a means to free her. This defector insists that it does not share the zealotry of its fellow Aurawroughts and seeks your help to stop its brethren from unleashing a dangerous deity into the universe. You are skeptical, but something in its demeanor convinces you to trust it. The tiny defector says it needs to prepare some documents for you — a map to travel directly to the Aurawroughts, avoiding their army's entire fleet, and the blueprints of the technology they are planning to use to free Eos. It promises to be in touch soon and asks you to wait for it to return with the paperwork.

In the meantime, you look around at the state of the common area. A new shipment of coffee beans had arrived just in time, as there was nothing left from the old shipment besides the handful of beans inside the machine. All the bags of coffee beans are inside a knapsack, waiting to be shelved. To kill time, you decide to take some initiative and stock some coffee.

There are 100 bags of coffee beans in varying sizes from all over Earth, and they will not all fit on the shelf. You scan the inventory list on your holographic tablet, which displays a comma-separated document detailing the shipment: country, bean type, roast, width of the bag, and popularity rating — your puzzle input. You should:

1. Consider an Individual Coffee Bag:
Define a way to group together the country, bean type, roast, width, and popularity rating for each coffee bag.
2. Create a Plan to Organize the Shelf:
Consider a shelf an object that can hold a certain number of coffee bags, remembering it has a fixed width capacity.
3. Stock the Shelf Efficiently:
Implement a method to store the coffee bags on the shelf with the best possible popularity rating while minimizing wasted space.

By organizing the coffee bags this way, you can ensure that the shelf is stocked with the best selection for the crew.

For example, look at a small shelf of70cm:

If you have the following inventory country,bean,roast,width,rating
Jamaica,Arabica,Light Roast,40,5
Brazil,Robusta,French Roast,20,3
Colombia,Typica,French Roast,30,4
Uganda,Arabica,Vienna Roast,10,2
Mexico,MundoNovo,Cinnamon Roast,30,2 To minimize wasted space you should fill the shelf with coffee bags so that their combined widths total as close to 70cm as possible.

Several combinations are possible: Choosing the coffees from Jamaica and Colombia total 70cm, as does combining Jamaica and Mexico. Smaller bags can also reach 70m, such as those from Colombia, Uganda, and Mexico. It is also possible to obtain a high popularity rating while coming up slightly short of 70cm, like with Brazil, Colombia, and Uganda, which total 60cm. With so many options, the goal is to select the combination that yields the highest total popularity rating.

Although several combinations fill the shelf close to 70cm, the combination of Jamaica Arabica Light Roast, Brazil Robusta French Roast, Uganda Arabica Vienna Roast have the best total popularity rating of 10.

Your shelf is 500 cm wide.
Here is the inventory of all the coffee beans: