maennchen

Advent of Code 2022 - Day 16

Ok, that was a rough one today.

I haven’t found a way to improve the algorithm further. Part 1 runs in .5 seconds, Part 2 in ~ 5 minutes.

maennchen/advent-of-code/blob/main/2022/16/1_depressurize.exs

#!/usr/bin/env elixir

initial_position = "AA"
available_minutes = 30

valves =
  IO.stream()
  |> Enum.map(
    &Regex.run(
      ~r/^Valve (?<valve>[A-Z]{2}) has flow rate=(?<flow_rate>\d+); tunnels? leads? to valves? (?<tunnels>([A-Z]{2})(, [A-Z]{2})*)/,
      &1,
      capture: ["valve", "flow_rate", "tunnels"]
    )
  )
  |> Map.new(fn [valve, flow_rate, tunnels] ->
    {valve,
     %{
       valve: valve,
       flow_rate: String.to_integer(flow_rate),
       tunnels: String.split(tunnels, ", ")

This file has been truncated. show original

github.com

maennchen/advent-of-code/blob/main/2022/16/2_depressurize_with_elephant.exs

#!/usr/bin/env elixir

initial_position = "AA"
available_minutes = 26

valves =
  IO.stream()
  |> Enum.map(
    &Regex.run(
      ~r/^Valve (?<valve>[A-Z]{2}) has flow rate=(?<flow_rate>\d+); tunnels? leads? to valves? (?<tunnels>([A-Z]{2})(, [A-Z]{2})*)/,
      &1,
      capture: ["valve", "flow_rate", "tunnels"]
    )
  )
  |> Map.new(fn [valve, flow_rate, tunnels] ->
    {valve,
     %{
       valve: valve,
       flow_rate: String.to_integer(flow_rate),
       tunnels: String.split(tunnels, ", ")

This file has been truncated. show original

I went the way of precalculating all possible paths between non-zero flow rate valves using :digraph.get_short_path/3. Then I recursively calculate the best step. That works find for 1 actor / 30 iterations. For 2 actors / 26 iterations, that is however still a bit much.

Does anybody have a prettier solution?

12 comments

#advent-of-code #2022

3 1761 12

2022-12-27 19:21:54 UTC

Most Liked

kwando

This one was annoying to get right…
Part 1 is more or less instant, part 2 is super duper slow. Would probably work to memoize some computations, but I just let it run embarrassingly long instead, ~30min

github.com

kwando/AoC2022/blob/main/16/day16.livemd

# Day 16

```elixir
Mix.install([:kino])
```

## Part 1



```elixir
parse_line = fn line ->
  result =
    Regex.run(~r/Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.*)/, line)
    |> Enum.drop(1)

  [from, rate, to] = result
  {from, String.to_integer(rate), String.split(to, ", ")}
end

This file has been truncated. show original

Post #2

lud

I have this solution that runs in 5 or 10 seconds according on how much you want to cheat.

Here I have the correct solution in 5 seconds with keeping the 50_000 best paths but ymmv.

Oh and I did not refactor so it is ugly

github.com

lud/adventofcode/blob/main/lib/solutions/2022/day_16.ex

defmodule Aoe.Y22.Day16 do
  alias Aoe.Input, warn: false

  @type input_path :: binary
  @type file :: input_path | %Aoe.Input.FakeFile{}
  @type part :: :part_one | :part_two
  @type input :: binary | File.Stream.t()
  @type problem :: any

  defmodule S1 do
    @enforce_keys [:pos, :pressure, :minute, :map, :history]
    defstruct @enforce_keys
  end

  defmodule S2 do
    @enforce_keys [:me_pos, :el_pos, :pressure, :me_minute, :el_minute, :map, :history]
    defstruct @enforce_keys
  end

  @spec read_file!(file, part) :: input

This file has been truncated. show original

Post #3

Where Next?

View thread on forum (has 12 responses!)

advent-of-code

2022

Home Learning Resources>Coding Challenges

#advent-of-code #2022

3 1763 12

Last post

Advent of Code 2022 - Day 16

maennchen

Advent of Code 2022 - Day 16

Most Liked

kwando

lud

Where Next?

Popular in Challenges

Advent of Code 2019 - Day 12

Advent of Code - Day 2

Advent of Code 2020 - Day 1

Advent of Code 2020 - Day 11

Advent of Code 2021 - Day 3

Advent of Code 2022 - Day 6

Advent Of Code 2022 - Day 3

Advent of Code 2023 - Day 21

Advent of Code 2023 - Day 3

Advent of Code 2020 - Day 10

Other popular topics

Import a module from a file into IEX

How to convert Date to DateTime which Ecto needs

Oban - Reliable and Observable Job Processing

Updating a field using Ecto one-liner?

Enumerables - how does Enum.reduce work with maps

Web scraping tools

Deploying Elixir into ECS causing many "'global' at node :"xxxxx@10.0.X.X" requested disconnect from node :"xxxx@10.0.X.X" in order to prevent overlapping partitions"

Removing spaces and characters from string

Formatting a string to PEM with headers and line breaks

Elixir for game development

Learning Resources>Coding Challenges

Latest on Elixir Forum

Sponsor Spotlight

Our Sponsors

Categories:

Sub Categories:

Forums

Our Sponsors

We're in Beta