Day 17 - Advent of Code 2015

Mix.install([:kino, :benchee])

:ok

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Livebook

Prompt

--- Day 17: No Such Thing as Too Much ---

The elves bought too much eggnog again - 150 liters this time. To fit it all into your refrigerator, you'll need to move it into smaller containers. You take an inventory of the capacities of the available containers.

For example, suppose you have containers of size 20, 15, 10, 5, and 5 liters. If you need to store 25 liters, there are four ways to do it:

• 15 and 10
• 20 and 5 (the first 5)
• 20 and 5 (the second 5)
• 15, 5, and 5

Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?

To begin, get your puzzle input.

--- Part Two ---

While playing with all the containers in the kitchen, another load of eggnog arrives! The shipping and receiving department is requesting as many containers as you can spare.

Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?

In the example above, the minimum number of containers was two. There were three ways to use that many containers, and so the answer there would be 3.

Although it hasn't changed, you can still get your puzzle input.

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()

"50\n44\n11\n49\n42\n46\n18\n32\n26\n40\n21\n7\n18\n43\n10\n47\n36\n24\n22\n40"

Solution

defmodule Day17 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input, goal \\ 150) do
    input
    |> parse()
    |> Enum.with_index()
    |> find_all(goal)
    |> List.flatten()
    |> length()
  end

  def part2(input, goal \\ 150) do
    input
    |> parse()
    |> Enum.with_index()
    |> find_all(goal)
    |> List.flatten()
    |> Enum.group_by(&tuple_size/1)
    |> Enum.min_by(&elem(&1, 0))
    |> elem(1)
    |> length()
  end

  def find_all(remaining, list \\ [], goal, sum \\ 0)
  def find_all(_, list, goal, goal), do: List.to_tuple(list)
  def find_all(_, _, goal, sum) when sum > goal, do: nil

  def find_all(remaining, list, goal, sum) do
    remaining
    |> Enum.with_index()
    |> Enum.map(fn {{n, x}, i} ->
      find_all(
        Enum.slice(remaining, (i + 1)..-1),
        [{n, x} | list],
        goal,
        sum + n
      )
    end)
    |> Enum.reject(&is_nil/1)
  end

  defmodule Input do
    def parse(input) when is_binary(input) do
      input
      |> String.split("\n")
      |> parse()
    end

    def parse(input) when is_list(input) do
      Enum.map(input, &parse_line/1)
    end

    def parse_line(line) do
      String.to_integer(line)
    end
  end
end

{:module, Day17, <<70, 79, 82, 49, 0, 0, 16, ...>>,
 {:module, Day17.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

Filling all containers entirely, how many different combinations of containers can exactly fit all 150 liters of eggnog?

Your puzzle answer was 654.

Day17.part1(input)

654

Find the minimum number of containers that can exactly fit all 150 liters of eggnog. How many different ways can you fill that number of containers and still hold exactly 150 litres?

Your puzzle answer was 57.

Day17.part2(input)

57

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, you should return to your Advent calendar and try another puzzle.

If you still want to see it, you can get your puzzle input.

Tests

ExUnit.start(auto_run: false)

defmodule Day17Test do
  use ExUnit.Case, async: false

  setup_all do
    [
      input: "20\n15\n10\n5\n5"
    ]
  end

  describe "part1/1" do
    test "returns expected value", %{input: input} do
      assert Day17.part1(input, 25) == 4
    end
  end

  describe "part2/1" do
    test "returns expected value", %{input: input} do
      assert Day17.part2(input, 25) == 3
    end
  end
end

ExUnit.run()

..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures

Randomized with seed 948125

%{excluded: 0, failures: 0, skipped: 0, total: 2}

Benchmarking

# https://github.com/bencheeorg/benchee

Benchee.run(%{
  "Part 1" => fn -> Day17.part1(input) end,
  "Part 2" => fn -> Day17.part2(input) end
})

nil

Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.14.2
Erlang 25.1.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s

Benchmarking Part 1 ...
Benchmarking Part 2 ...

Name             ips        average  deviation         median         99th %
Part 1        366.70        2.73 ms     ±3.91%        2.68 ms        2.97 ms
Part 2        364.07        2.75 ms     ±3.80%        2.70 ms        2.98 ms

Comparison: 
Part 1        366.70
Part 2        364.07 - 1.01x slower +0.0197 ms

nil