DEV Community

Cover image for Advent of code - Day 7
Quentin Ménoret
Quentin Ménoret

Posted on

Advent of code - Day 7

#javascript #typescript #adventofcode

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);
Enter fullscreen mode Exit fullscreen mode

Feel free to share your solution in the comments!

Photo by Markus Spiske on Unsplash

Top comments (5)

Collapse
 
oguimbal profile image
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 )
Enter fullscreen mode Exit fullscreen mode
Collapse
 
qmenoret profile image
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);
Enter fullscreen mode Exit fullscreen mode
Collapse
 
oguimbal profile image
Olivier Guimbal •

oh yes right :)

Collapse
 
qmenoret profile image
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!

Collapse
 
oguimbal profile image
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)