## DEV Community is a community of 636,824 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Advent of code - Day 7

Are you participating in the Advent of code this year?

If you don't know what the advent of code is, it's a website where you'll find a daily challenge (every day it gets harder). It's a really fun event, you should participate!

I try to solve the exercises using either JavaScript or TypeScript and will share my solutions daily (with one day delay so no one can cheat!). I only share the solution for the second part.

For day #7, I created a sort a tree like structure, but flat (I'm lazy), represented by a Record. Basically, for each color, you know which colors you can contains.

Once you have such a structure, finding the answer is just a matter of a small recursion:

``````const tree = input.reduce((tree, line) => {
const color = /(^.*) bags contain/.exec(line)[1];
tree[color] = [];

const matches = line.matchAll(/,? (\d+) ([^,.]*) bags?/g);
for (const match of matches) {
for (let i = 0; i < parseInt(match[1]); i++) {
tree[color].push(match[2]);
}
}
return tree;
}, {});

const depth = (color) => {
if (tree[color] === []) return 1;
return tree[color].reduce((acc, color) => acc + depth(color), 1);
};

console.log(depth("shiny gold") - 1);
``````

Photo by Markus Spiske on Unsplash

## Discussion (6)

Olivier Guimbal

For once, the JS version is compact :) - where's part 2, though ? 😊

A flat structure is indeed simpler to manage, given that we have to traverse the graph both ways (part 1 is basically "count all my parents" and part 2 "count all my descendents")

Haskell version (of both part 1 & 2)

``````norm = filter isAlphaNum

ruleOf r =
let [color, bagStr] = splitOn " bags contain " r
in splitOn ", " bagStr
& filter (/= "no other bags.")
& map (unwords . init . words)
& map norm
& map (break isAlpha)
& map (\(a, b) -> (norm color, (read a :: Int, b)))

allContainers rules color =
let containers = map fst \$ filter ((== norm color) . snd . snd) rules
in color : concatMap (allContainers rules) containers

allContained rules color =
let contained = map snd \$ filter ((== norm color) . fst) rules
in 1 + sum (map (\c -> fst c * (allContained rules . snd) c) contained)

ans = do
rules <- concatMap ruleOf . lines <\$> readFile "./data.txt"
return (
Set.size . Set.fromList . filter (/= "shiny gold") \$ allContainers rules "shiny gold",
allContained rules "shiny gold" - 1
)
``````
Quentin Ménoret

This is part 2!

Actually I always traversed in the same order. I just bruteforced in part 1, trying all possible start point 😂 This is my part 1 solution:

``````const tree = input.reduce((tree, line) => {
const color = /(^.*) bags contain/.exec(line)[1];
tree[color] = [];

const matches = line.matchAll(/,? \d+ ([^,.]*) bags?/g);
for (const match of matches) {
tree[color].push(match[1]);
}
return tree;
}, {});

const canContainGold = (color) => {
if (tree[color].includes("shiny gold")) return true;
return tree[color].some((color) => canContainGold(color));
};

const filtered = Object.keys(tree).filter((color) => {
return canContainGold(color);
});

console.log(filtered.length);
``````
Quentin Ménoret • Edited

Damn, it's been a long time I haven't written a single line of Haskell...
I thought doing it with Haskell but... Pretty sure I would have given up already!
Good job!

Olivier Guimbal

Advent of code is quite a good occasion to practice or learn. So I figured "given that you like hurting yourself, why not doing it in Haskell ?" (I dont use it often)