Discussion on: Advent of code - Day 7

View post

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 • Dec 8 '20 • 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 • Dec 8 '20

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)

Quentin Ménoret • Dec 8 '20

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 • Dec 8 '20

oh yes right :)