DEV Community

loading...
Cover image for Advent of code - Day 7

Advent of code - Day 7

qmenoret profile image Quentin Ménoret ・1 min read

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

Discussion (6)

pic
Editor guide
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 Author

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 Author • 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)