Finally, Directed Weighted Graphs have made their way to the Advent Of Code 2020 on Day 7. If you are unfamiliar with graphs then I highly recommend you to go through the below articles:
This above article will give you enough information to get you started with today’s problem. On this note, let’s start with today’s problem.
We reached the regional office in time, even before time. But now there seems to be a new problem with the luggage processing.
Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be colour-coded and must contain specific quantities of other colour-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 contents of the 9 bag types. In the above example, every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded blue bags and 6 dotted black bags) and so on…
So, here’s our problem,
You have a shiny gold bag. How many bags would be valid to carry it?
For example – shiny gold bag is can be carried by muted yellow bag, muted yellow bag can be carried inside dark orange bag. Therefore, shiny bag can be carried inside dark orange bag.
I hope the problem is much clear with the above example.
How many bag colors can eventually contain one shiny gold bag?
Where would you start?
Table of Contents
Part One – Find all the bags that can contain one shiny gold bag
This time I’m going to use JAVA because it’s all going to be Classes and Objects (in short, object-oriented) and what’s better than Java (after version 8 :p) when it comes to object-oriented programming.
When I first saw this question the first thing that came to my mind was a Weighted Graph. So, I started from there. I highly recommend you read the following article if you have not worked with graphs before.
The represent the graph, I’ll use Adjacency List Representation (Talked in detail in the above article).
Weighted Graph
This is how my WeightedGraph class looks like:
Here’s the code for the same. I’ve used the Bag here as a data structure to hold other bags. Although it suits the context of the problem, but Bag is actually a data structure which is used in Graphs.
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class WeightedGraph {
int totalEdges = 0;
private Map<String, Bag<WeightedEdge>> edges;
public WeightedGraph() {
edges = new HashMap<>();
}
public void addEdge(WeightedEdge edge) {
if (edges.containsKey(edge.getV1()))
edges.get(edge.getV1()).add(edge);
else {
final Bag<WeightedEdge> bag = new Bag<>();
bag.add(edge);
edges.put(edge.getV1(), bag);
}
totalEdges += 1;
}
public int totalEdges() {
return totalEdges;
}
public List<WeightedEdge> adj(String v) {
return edges.getOrDefault(v, Bag.empty());
}
public int totalVertices() {
return edges.size();
}
public void print() {
this.edges.forEach((key, val) ->
System.out.println(key + " -> " + val.stream()
.map(WeightedEdge::getV2)
.collect(Collectors.joining(" "))));
}
public Map<String, List<WeightedEdge>> get() {
return Collections.unmodifiableMap(edges);
}
}I’m not going to bore you here by explaining my code. Go through the code yourself, its pretty explanatory and if you do not understand something then do call out in the comments below.
So moving on…
Now, that we have the weighted graph data structure ready, all we need is a builder that will parse the input and build the graph for us.
Let’s build the WeightedGraphBuilder next.
Weighted Graph Builder
There are two types of lines that we have to parse.
light red bags contain 1 bright white bag, 2 muted yellow bags.
.
.
.
dotted black bags contain no other bags.Here are the parsing rules that I have used in the code:
- There is only one bag to the left of the word “contain”.
- There could be multiple bags after the word “contain”. All bags to the right of ‘contain’ is separated via comma (,).
- The keyword
bagorbagshave no role to play in the problem so will filter those. - Bag names are separated by whitespaces.
- The first part contains the count of the bag (weight),
- the middle part contains the colour of the bag,
- the last part can be simply ignored as it always ends with either bag or bags.
- Whenever the right part contains
no other bagsit means this is our leaf node.
Cool!!! So with all these rules laid out, let’s write our graph builder.
Here’s how the class structure looks like:
And here’s the code for the same.
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class WeightedGraphBuilder {
/**
* Sample Input
* ----------------
* 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.
*
* @param filePath
* @return
*/
public static final String CONTAIN_REGEX = " contain ";
public static final int ZERO = 0;
public static final String BAG_REGEX = "bag";
public static final String COMMA_REGEX = ",";
public WeightedGraph buildFromFileInput(Path filePath) {
WeightedGraph wg = new WeightedGraph();
try {
Files.readAllLines(filePath).forEach(line ->
buildEdge(parseV1(line), line.split(CONTAIN_REGEX)[1].split(COMMA_REGEX))
.forEach(wg::addEdge));
} catch (IOException e) {
// never do this in production code
e.printStackTrace();
}
return wg;
}
private String parseV1(String line) {
// Line: light red bags contain 1 bright white bag, 2 muted yellow bags.
// After Split: light red bags
// After Substring: light red
return line.split(CONTAIN_REGEX)[ZERO]
.substring(ZERO, line.split(CONTAIN_REGEX)[ZERO]
.indexOf(BAG_REGEX))
.trim();
}
private List<WeightedEdge> buildEdge(String from, String[] edgesParts) {
return Arrays.stream(edgesParts)
.map(vw -> new WeightedEdge(from, vw.trim()))
.collect(Collectors.toList());
}
}If you are wondering how I’m so sure if the above code works great. Well, I’ve got the test cases for that in place. And you should have them too. I will not share the test case here but if you are interested in the entire code at one place then you can check out my GitHub (@vslala) for the same.
Great!!! with that let’s move to the next part of the puzzle and that is to process the graph for the required information.
Weighted Graph Processor
Processors are always different from the graph because you can process the same graph in multiple ways for different information. Therefore, keeping the processing logic outside of the graph always helps to make you code extendable.
This is the class which needs a little bit of explanation I guess, as it involves the main logic for solving the problem, the depth-first search on the weighted graph. So, before jumping into the logic part directly, let me show you the structure of the class. I think that way it would be easier to understand what’s going on in the code at a very high-level.
Here’s the code for the same.
import lombok.RequiredArgsConstructor;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;
@RequiredArgsConstructor
public class WeightedGraphProcessor {
private final WeightedGraph graph;
private final AtomicBoolean isBagFound = new AtomicBoolean(false);
private final Set<String> part1 = new HashSet<>();
public int findAllBagsContainingBag(String bagColor) {
Set<String> vertices = graph.get().keySet();
vertices.forEach(vertex -> {
isBagFound.set(false);
dfs(vertex, graph, bagColor);
});
return part1.size();
}
private void dfs(String vertex, WeightedGraph graph, String bagColor) {
if (isBagFound.get() || vertex.equals(bagColor)) {
isBagFound.set(true);
return;
}
if (vertex.isEmpty()) return;
graph.adj(vertex).forEach(edge -> {
dfs(edge.other(vertex), graph, bagColor);
if (isBagFound.get())
part1.add(vertex);
});
}
public int countAllBagsInsideABag(String bagColor) {
return countTotalBags(bagColor);
}
}So as always let’s take the actual example to understand the logic of the code.
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.In the above example, if we plot the directed graph from left to right bags, this is what we get till shiny gold. So, the depth -first search will be done from each vertex (bag) till we reach an empty bag or shiny gold.
And while doing that we will keep track of the edges that led to the shiny gold bag and that will be our answer.
Let’s say you start from Light Red, you will visit Bright White to Shiny Gold, then you will go from Muted Yellow to Shiny Gold. This way you know that Light Red, Bright White and Muted Yellow can contain shiny gold bag.
Wait, I have one more diagram for you. The Sequence Diagram.
After this sequence diagram, I think most of the things will be clear and if there is anything that you want me to explain then please do comment below.
For Part One, I will leave it here.
By the way, the answer was correct. You can call method findAllBagsContainingBag("shiny gold") to get the answer.
Let’s start with the Part Two.
Part Two – Count total bags inside single shiny gold bag recursively
This is the extension of the existing problem. And this will be easy now because we made the Directed Weighted Graph in the first part itself.
In this part, we have to count all the bags inside shiny gold bag recursively. So, it’s a depth-first search that will start from the “shiny gold” bag and keep on adding the weights to the sum. This is similar to the formula they have explained in the example i.e. 1 + 1*7 + 2 + 2*11 = 32 bags!
Here’s the code that we need to write to find the total count of the bags inside “shiny gold”.
public int countAllBagsInsideABag(String bagColor) {
return countTotalBags(bagColor);
}
private int countTotalBags(String bagColor) {
if (graph.adj(bagColor).isEmpty())
return 0;
else
return graph.adj(bagColor)
.stream()
.mapToInt(edge -> (int) (edge.getW() * (1 + countTotalBags(edge.other(bagColor)))))
.sum();
}This code calls the countTotalBags recursively and adds the count to the count returned from the function. At the end you get the total bags count.
Here’s the sequence diagram for the above code.
This article grew a lot bigger than I expected. But I hope you understand the concept and hopefully learned something new through this problem.
Let me know how you find it in the comments below.