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);

Feel free to share your solution in the comments!

---

Photo by Markus Spiske on Unsplash

Comments

[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);

[Olivier Guimbal]

oh yes right :)

[Quentin Ménoret]

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)