Advent of Code 2020 - Day 7

Learning Questions & Discussions Coding Challenges
,
1

This topic is about Day 7 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

I become busy this week, so I may not be able to create such topics in time. Apologies in advance.

2

I tried a too clever solution first… but I rolled back to this one… took some tries to get right, so it is not that polished yet :slight_smile:

defmodule Aoc2020.Day07 do
  def part1(input) do
    rules =
      input
      |> Enum.into(%{})

    for {color, specs} <- rules, color != "shiny gold", reduce: 0 do
      sum ->
        if find(rules, specs, "shiny gold") do
          sum + 1
        else
          sum
        end
    end
  end

  def part2(input) do
    rules =
      input
      |> Enum.into(%{})

    count_bags(rules, "shiny gold") - 1
  end

  def find(rules, [], _), do: false
  def find(rules, [{_, color} | rest], color), do: true

  def find(rules, [{_, child_color} | rest], color),
    do: find(rules, rest, color) || find(rules, Map.get(rules, child_color, []), color)

  def count_bags(rules, color) do
    specs = Map.get(rules, color, [])

    for {quantity, color} <- specs, reduce: 1 do
      sum ->
        sum + quantity * count_bags(rules, color)
    end
  end

  def input_stream(path) do
    File.stream!(path)
    |> Stream.map(&parse/1)
  end

  def parse(line) do
    line
    |> String.replace(["bags", "contain", "bag"], "")
    |> String.replace(~r/\s+|\./, " ")
    |> String.trim()
    |> String.split(",")
    |> Enum.map(fn part -> String.trim(part) |> String.split(" ") end)
    |> create_rule()
  end

  def create_rule([[mod, color | rule] | rules]) do
    {"#{mod} #{color}", parse_spec([rule | rules])}
  end

  defp parse_spec([["no", "other"]]), do: []
  defp parse_spec([]), do: []

  defp parse_spec([[quantity, mod, color] | rest]) do
    [{String.to_integer(quantity), "#{mod} #{color}"} | parse_spec(rest)]
  end
end

input = Aoc2020.Day07.input_stream("input.txt")

Aoc2020.Day07.part1(input)
|> IO.inspect(label: "part1")

Aoc2020.Day07.part2(input)
|> IO.inspect(label: "part2")
1 Like
3

I used :digraph for the first one :smiley: still doing the second one (the way I found ended up counting leaves), your solution does give me a little hint :wink: so thank you.

2 Likes
4

Same here. But now it’s working:

1 Like
5

Finally done with number 2. Here’s how I did it. Used :digraph for the first one.

1 Like
6

They get uglier every day!

defmodule Day07.Fns do
  # revmap: map a bag to the list of bags that contain it
  def revmap(_container, [], bagmap), do: bagmap

  def revmap(container, [bag | bags], bagmap) do
    bag = String.replace(bag, ".", "")

    # ugly
    bagmap = Map.update(bagmap, bag, [container], fn cur -> [container | cur] end)

    revmap(container, bags, bagmap)
  end

  # map a bag to a map of bags it contains, and how many
  # %{"wavy lavender" => %{"light magenta" => 1, "striped cyan" => 2}}
  def nummap(_container, [], bagmap), do: bagmap

  def nummap(container, [bag | bags], bagmap) do
    bag = String.replace(bag, ".", "")

    [count, containedbag] =
      Regex.scan(~r/(\d+)\s(.*)/, bag, capture: :all_but_first)
      |> hd()

    # ugly
    bagmap =
      Map.update(bagmap, container, %{containedbag => String.to_integer(count)}, fn cur ->
        Map.put(cur, containedbag, String.to_integer(count))
      end)

    nummap(container, bags, bagmap)
  end

  def cancontain(_bagmap, [], mapset), do: Enum.count(mapset)

  def cancontain(bagmap, [bag | bags], mapset) do
    containers =
      Map.get(bagmap, bag, [])
      |> Enum.reject(fn nextbag -> nextbag == bag or nextbag in mapset end)

    newmapset =
      containers
      |> MapSet.new()
      |> MapSet.union(mapset)

    cancontain(bagmap, bags ++ containers, newmapset)
  end

  def totalbags(bagmap, bag) do
    contains = Map.get(bagmap, bag, %{})

    # ugly, not tail-recursive
    if contains == %{} do
      0
    else
      immediate =
        Map.values(contains)
        |> Enum.sum()

      inside =
        Enum.map(contains, fn {ibag, icount} -> icount * totalbags(bagmap, ibag) end)
        |> Enum.sum()

      immediate + inside
    end
  end
end

defmodule Day07 do
  alias Day07.Fns

  def readinput() do
    File.read!("7.input.txt")
    |> String.replace(~r/ bag(s)?/, "")
    |> String.replace(", ", ".")
    |> String.split("\n", trim: true)
    |> Enum.reject(fn s -> String.contains?(s, "no other") end)
  end

  def part1(input \\ readinput()) do
    input
    |> Enum.map(&String.replace(&1, ~r/(\d+) /, ""))
    |> Enum.map(&String.split(&1, " contain "))
    |> Enum.map(fn [container, contains] ->
      [container, String.split(contains, ".", trim: true)]
    end)
    |> Enum.reduce(%{}, fn [container | [contains | _]], acc ->
      Fns.revmap(container, contains, acc)
    end)
    |> Fns.cancontain(["shiny gold"], MapSet.new())
  end

  def part2(input \\ readinput()) do
    input
    |> Enum.map(&String.split(&1, " contain "))
    |> Enum.map(fn [container, contains] ->
      [container, String.split(contains, ".", trim: true)]
    end)
    |> Enum.reduce(%{}, fn [container | [contains | _]], acc ->
      Fns.nummap(container, contains, acc)
    end)
    |> Fns.totalbags("shiny gold")
  end
end
1 Like
7

:notes: Oh luggage tree, oh luggage tree… :luggage::christmas_tree:

I implemented most of part 2 accidentally during part 1.

  1. Build a tree representing the parent → child relationships.
    Question asks for the ancestors, so invert the tree and walk it to find them.
  2. Now it wants the descendants. Walk the tree from part 1.

Part 1

def count_ancestors([], bags, _itree), do: Enum.count(bags)

def count_ancestors([name | rest], bags, itree) do
  case Map.fetch(itree, name) do
    :error -> count_ancestors(rest, bags, itree)
    {:ok, names} -> count_ancestors(names ++ rest, MapSet.union(bags, MapSet.new(names)), itree)
  end
end

Part 2

def count_descendants(tree, name) do
  Enum.reduce(tree[name], 0, fn {size, child_name}, count ->
    count + size + size * count_descendants(tree, child_name)
  end)
end

Full code.

8

This one was easier for me than last 2 for some reason :slight_smile: Didn’t use anything fancy at all.
https://github.com/Damirados/AoC/blob/master/lib/event7.ex

Part1

def get_parents(rules, child) do
    parents =
      Enum.flat_map(rules, fn {bag, bag_rules} ->
        Enum.find_value(bag_rules, [], fn
          {_n, b} when b == child -> [bag]
          _ -> false
        end)
      end)

    Enum.flat_map(parents, &get_parents(rules, &1)) ++ parents
  end

Part 2

  def count_children(rules, parent) do
    bag_rules = Enum.find_value(rules, fn {bag, bag_rules} -> bag == parent && bag_rules end)
    1 + (Enum.map(bag_rules, fn {n, bag} -> n * count_children(rules, bag) end) |> Enum.sum())
  end
9

I was first afraid there could be loops or sth. but seems fine. Here second solution:

#!/usr/bin/env elixir
my_bag = "shiny gold"

defmodule Day7 do
  def parse(rest) do
    case rest do
      ~w(no other bags.) -> []
      [count, shade, color, _bags] -> [{shade <> " " <> color, count}]
      [count, shade, color, _bags | rest] -> [{shade <> " " <> color, count} | parse(rest)]
    end
  end

  def count(_tree, nil), do: 0
  def count(_tree, []), do: 0
  def count(tree, [{node, cnt} | nodes]) do
    cnt = String.to_integer(cnt)
    cnt + (cnt * count(tree, tree[node])) + count(tree, nodes)
  end
end

tree = File.read!("7.csv")
|> String.split("\n", trim: true)
|> Enum.map(fn row ->
  [shade, color, "bags", "contain" | rest] = String.split(row)

  key = shade <> " " <> color
  contents = Day7.parse(rest)
  {key, contents}
end)
|> Map.new()

Day7.count(tree, tree[my_bag])
|> IO.inspect()
1 Like
10

Used the libgraph library.

GitHub

defmodule Aoc.Y2020.D7 do
  use Aoc.Boilerplate,
    transform: fn raw ->
      raw
      |> String.split("\n")
      |> Enum.reduce(Graph.new(), fn line, graph ->
        [main, others] = line |> String.split(" contain ")
        main_parsed = main |> String.replace(" bags", "")

        others
        |> String.split([", ", "."], trim: true)
        |> Enum.map(fn other_str ->
          other_str
          |> String.replace([" bags", "bag"], "", global: true)
          |> Integer.parse()
          |> case do
            :error -> {0, "no bags"}
            {n, bag} -> {n, String.trim(bag)}
          end
        end)
        |> Enum.reduce(graph, fn {count, bag}, graph_acc ->
          case count do
            0 -> graph_acc
            _ -> Graph.add_edge(graph_acc, main_parsed, bag, label: count)
          end
        end)
      end)
    end

  def part1(graph \\ processed()) do
    graph
    |> Graph.reaching_neighbors(["shiny gold"])
    |> Enum.count()
  end

  def part2(graph \\ processed()) do
    count_bags(graph, "shiny gold") - 1
  end

  defp count_bags(graph, vertex) do
    graph
    |> Graph.out_edges(vertex)
    |> Enum.reduce(1, fn %{v2: vertex, label: n}, total ->
      total + n * count_bags(graph, vertex)
    end)
  end
end
11

part2 bad parse - can be improved

defmodule Advent.Day7b do

  def start(file \\ "/tmp/input2.txt"), do:
    File.stream!(file)
    |> Enum.reduce(%{},
        fn line, acc -> format_map(acc, String.replace(line, ["bag", "bags", ".", "\n", "no other"], "") |> String.split(" contain"))
       end)
    |> process()
    |> elem(1)

  def process(map), do: map |> Map.get("shiny gold") |> process(map, 1, 0)

  def process(nil, _map, mult, total), do: {mult, total}
  def process(bags, map, mult, total) do
    Enum.reduce(bags, {mult, total}, fn {item, qtd}, {_, acc_total} ->
      case Map.get(map, item) do
        nil -> {mult, acc_total + mult * qtd}
        new_bags -> process(new_bags, map, mult * qtd, acc_total + mult * qtd)
      end
    end )
  end

  defp format_map(map, [_bag, "  "]), do: map
  defp format_map(map, [bag, bags]) do
    bags
    |> String.split(",")
    |> Enum.map(fn o -> String.trim(o)
            |> String.split(" ", parts: 2) end)
            |> Enum.filter(fn o -> o !== [[""]] end)
            |> Enum.reduce(map, fn [num, item], acc ->
                v = [{item, String.to_integer(num)}]
                Map.update(acc, String.trim(bag), v, fn lst -> v ++ lst end)
       end)
  end

end
12

Starting to get a little tough. I managed to get this after examining some of the solutions posted here. I had a naive solution for part 1 that was off by one and I can’t figure out why. Since my final solution was derivative of other posts here not posting it but wanted to say thanks for everyone who did post their solutions for providing the guidance.

1 Like
13

That’s a nice implementation of count_bags/2, much more readable than what I managed to do.

14

I modeled the data as directed graph where the edge label is the count of bags inside the source bag using Erlang :digraph and :digraph_utils. Part 2 turned out with similar (not tail-recursive) structure. Not the most elegant but gets the job done:

  def count_bags_from(graph, node) do
    edges =
      for e <- :digraph.out_edges(graph, node) do
        :digraph.edge(graph, e)
      end

    own_counts =
      edges
      |> Enum.map(fn {_e, _from, _to, count} -> count end)
      |> Enum.sum()

    counts =
      for {_e, _from, to, count} <- edges do
        count * count_bags_from(graph, to)
      end

    own_counts + Enum.sum(counts)
  end

The benefit of :digraph is in the solution for first part:

  def part1 do
    graph = read_input()

    result = length(Digraph.reaching(graph, "shiny gold"))
    Digraph.delete(graph)
    result
  end

where Digraph.reaching/2 is defined as:

defmodule AoC2020.Day7.Digraph do
  ...
    def reaching(g, target) do
    :digraph_utils.reaching([target], g) -- [target]
  end
  ...
end
15

Maybe you counted the shiny gold bag.

16

I was one short. I think on the final match I was returning before adding it to the stack, but not sure.

17

I am not doing it every day, so only today I solved Day 7.
Ugly code, I believe.

1 Like
18

Actually, your code is quite readable.

1 Like