Click here to Skip to main content
15,399,959 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
You land at the regional airport in time for your next flight. In fact, it looks like you'll even have time to grab some food: all flights are currently delayed due to issues in luggage processing. Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!

For example, consider the following rules:

light red bags contain 1 bright white bag, 2 muted yellow bags.

dark orange bags contain 3 bright white bags, 4 muted yellow bags.

bright white bags contain 1 shiny gold bag.

muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.

shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.

dark olive bags contain 3 faded blue bags, 4 dotted black bags.

vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.

faded blue bags contain no other bags.

dotted black bags contain no other bags.

These rules specify the required contents for 9 bag types. In this example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue and 6 dotted black), and so on.

You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag? (In other words: how many colors can, eventually, contain at least one shiny gold bag?)

In the above rules, the following options would be available to you:

A bright white bag, which can hold your shiny gold bag directly.

A muted yellow bag, which can hold your shiny gold bag directly, plus some other bags.

A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.

A light red bag, which can hold bright white and muted yellow bags, either of which could then hold your shiny gold bag.

So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4.

How many bag colors can eventually contain at least one shiny gold bag? (The list of rules is quite long; make sure you get all of it.

Input Format

light red bags contain 1 bright white bag, 2 muted yellow bags.

dark orange bags contain 3 bright white bags, 4 muted yellow bags.

bright white bags contain 1 shiny gold bag.

muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.

shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.

dark olive bags contain 3 faded blue bags, 4 dotted black bags.

vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.

faded blue bags contain no other bags.

dotted black bags contain no other bags.

Constraints

bag type1 contain m bag type2, n bag type 3 ... where n is >1

Output Format

1<=COUNT

What I have tried:

its very difficult in solving in c
Here is what I tried.
import re
from collections import defaultdict
import networkx as nx
# Parse data
bags = defaultdict(dict)
for l in lines:
    bag = re.match(r'(.*) bags contain', l).groups()[0]
    for count, b in re.findall(r'(\d+) (\w+ \w+) bag', l):
        bags[bag][b] = { 'weight': int(count)}
# Create a graph in networkx
G = nx.DiGraph(bags)
def part1():
    # Reverse edges
    RG = G.reverse()
    # Get predecessors
    predecessors = nx.dfs_predecessors(RG, 'shiny gold')
    # Count predecessors
    return len(predecessors)
print(part1())
def part2():
    def search(node):
        count = 1
        # Iterate neighbors for node
        for n in G.neighbors(node):
            # Multiply weight with recursive search
            count += G[node][n]['weight'] * search(n)
        return count
    return search('shiny gold') - 1
print(part2())
Posted
Updated 22-Mar-22 3:43am
v3
Comments
PIEBALDconsult 19-Jan-22 9:05am
   
We won't do your homework for you.
Rick York 19-Jan-22 11:28am
   
That does not look at all like C to me and it appears to have very little to do with your problem.

Here are a few tips. Write some logic to check the rules. You can then feed it the test inputs you have. First you should determine an input parameter format though. It appears to me the format is a given colored bag which contains other bags and in your description of the inputs, n appears to be 2. You could set that up to be unlimited but if your inputs only have two I wouldn't bother. I would then make an enumeration of the types of bags and I would lose the adjectives. The simple values red, white, yellow, gold, orange, black, blue, olive, and plum are adequate for the task. If you have to output the colors with the adjectives then do that only for output.

Here are a couple of structures that could be useful.
C++
struct oneBag
{
    Color   color;
    int     count;
};

struct bags
{
    oneBag  thisbag;
    oneBag  contents[ MaxBags ];
};
and as I mentioned, I think MaxBags can be 2 but you should be probably verify that. If it has to be flexible then you can make oneBag a list item with a pointer to the next bag in the list but that requires you to know about linked lists. The Color item would be the aforementioned enumeration.

Anyway, back to this structure - one of your input items is this :
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
In terms of the bags structure it would be this :
C++
thisbag =
{
   color = yellow
   count = 2
   contents[0] =
   {
      color = gold
      count = 2
   };
   contents[1] =
   {
      color = blue
      count = 9
   };
};
One thing I have found after many years of doing this is if you make the appropriate data structures you can greatly simplify the code so I spend quite a bit of time figuring that part out first before writing any code. Then be prepared to adjust the data as needed. This is just a first pass after a quick glance over your problem statement. It might need adjustment.
   
Comments
Maged Derar 19-Jan-22 20:07pm
   
yes
Yes, I can do it: the important question is "will I - or anyone else - do it for you?"
And the answer to that is "No."

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.
What you appear to have done so far is find a similar exercise with a solution in Python, and are offering it up as "your work so far" - which isn't likely to be true at all. So ask yourself: "Why would anyone want to do my homework for me given I appear to be lying to them?"

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
   
Sure! Lots of people can.

The point of the assignment is, though, can YOU?
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900