bjorng

Erlang Core Team

Advent of Code 2021 - Day 18

This topic is about Day 18 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

8 comments

#advent-of-code

6 1434 8

2021-12-22 20:11:08 UTC

Most Liked

ramuuns

soo much tedious debugging of recursion, but I love the fact that the parsing is pretty much just a Code.eval_string

also I’m pretty sure I shot myself in the foot for having each node be a {depth, [left, right]} as I think this was making some of the recursion annoying and it was easy to accidentally create the node wrong and whatnot.

Anyhow, both parts run in about 100ms - aoc/day-18.ex at 1542d38365d74533b324c4f790699767ce81b8e9 · ramuuns/aoc · GitHub

Update:
since I hate myself and apparently “enjoy spending a few more hours debugging recursion”, I implemented another version, that runs slightly faster where each node is a {depth, needs_split?, [left, right]}. Besides the ~10% perf improvement, it does slightly simplify the splitting operation at the cost of having to keep track if a node (or any of its children) need to be split. Code for the “improved” version: aoc/day-18.ex at 3419958dee43037aded833dc46c4fde183443add · ramuuns/aoc · GitHub

Post #3

zevv

No sir, I did not at all like today’s puzzle sir. Every year there is at least one like those: too much text describing a tedious arbitrary process that’s a PITA to debug because you missed one of the many rules.

Anyway, I fought with a solution for too long where the numbers were stored as nested lists, but the recursion caused a pain behind my eyes. I fell back to just storing the numbers in a list, and exploding them by keeping track of a left and right carry that gets added to the next number to arrive. It suits nice with pattern matching, the end result is not too bad IMHO (even though some of the code looks more like Perl then Elixir), and fits in under a 100 lines,

github.com

zevv/aoc2021/blob/master/lib/day18.ex


defmodule Day18 do

  def explode(l, d, cr, done) do
    case {done, d, l} do
      {false, 4, ["[", n1, ",", n2, "]" | r]} ->
        {r, _} = explode(r, d, n2, true)
        {["0" | r], n1}
      {_, _, ["," | r]} ->
        {r, cl} = explode(r, d, cr, done)
        {["," | r], cl}
      {_, _, ["[" | r]} ->
        {r, cl} = explode(r, d+1, cr, done)
        {["[" | r], cl}
      {_, _, ["]" | r]} ->
        {r, cl} = explode(r, d-1, cr, done)
        {["]" | r], cl}
      {_, _, [n | r]} ->
        {r, cl} = explode(r, d, "0", done)
        v = Enum.map([n, cr, cl], &String.to_integer/1) |> Enum.sum

This file has been truncated. show original

Post #4

bjorng

Erlang Core Team

Here is my solution:

github.com

bjorng/advent-of-code-2021/blob/9a147ea3fb10fe6ae2eda8a567e06f11d779ab6f/day18/lib/day18.ex

defmodule Day18 do
  def part1(input) do
    parse(input)
    |> Enum.reduce(fn n, sum ->
      reduce([sum, n])
    end)
    |> magnitude
  end

  def part2(input) do
    numbers = parse(input)

    Enum.reduce(numbers, 0, fn n1, highest ->
      Enum.reduce(numbers -- [n1], highest, fn n2, highest ->
        max(highest, reduce([n1, n2]) |> magnitude)
      end)
    end)
  end

  @doc """

This file has been truncated. show original

UPDATE: I’ve also implemented a solution in Erlang with a different internal representation that simplifies the explode operation.

Post #2

stevensonmt

Quite late, but I really struggled with getting the explode logic to work. I also overcomplicated things implementing a tree structure rather than just using nested lists. I am excited that I was finally able to make it work though because I’ve always struggled with tree logic and I think this exercise helped solidify it a bit. I still don’t quite understand why I had to rebuild the tree after each update of the left side in the explode function. Really adds to the time complexity (would be O(n) at least anyway, but with that it’s at least O(3n) with n = length(steps). I also only really figured it out after I broke down and wrote tests for each step along the way. First time I’ve really written somewhat non-trivial tests from scratch in elixir.

github.com

stevensonmt/advent_of_code/blob/37f92f115f5d61c9eefb564d4562b8b1bf0d7270/2021/day18/lib/day18.ex

defmodule Day18 do
  @moduledoc """
  Solution for AoC `Day18`.
  """

  defmodule Tree do
    defstruct [:left, :right]

    @type t :: %__MODULE__{
            left: nil | integer() | t(),
            right: nil | integer() | t()
          }
    def new() do
      %Tree{}
    end

    def new(n, tree \\ %Tree{})

    def new([a, b], tree) do
      case {is_integer(a), is_integer(b)} do

This file has been truncated. show original

Post #9

Where Next?

View thread on forum (has 8 responses!)

advent-of-code

Home Learning Resources>Coding Challenges

#advent-of-code

6 1435 8

Last post

Advent of Code 2021 - Day 18

bjorng

Advent of Code 2021 - Day 18

Most Liked

ramuuns

zevv

bjorng

stevensonmt

Where Next?

Popular in Challenges

Advent of Code 2021 - Day 4

Advent of Code 2021 - Day 16

Advent of Code 2019 - Day 3

Advent of Code 2019 - Day 2

Advent of Code 2020 - Day 14

Advent of Code 2020 - Day 7

Advent Of Code 2022 - Day 13

Advent of Code 2021 - Day 1

Advent of Code 2024 - Day 5

Advent Of Code 2018

Other popular topics

How to convert Date to DateTime which Ecto needs

Oban - Reliable and Observable Job Processing

How to fix *Bad argument in call to erlang:'++'(<<"xxx/crash.log">>, ".3") in lager_rotator_default:rotate_logfile/2 line 84*

Drab: remote controlled frontend framework for Phoenix

(EXIT) no process: the process is not alive or there's no process currently associated with the given name, possibly because its application isn't started

Transform a list into an map with indexes using Enum module

What are the main benefits of Elixir compared to Clojure?

Installing elixir via asdf shows zsh: command not found: iex

Elixir vs Python

How can I write a raw sql query?

Learning Resources>Coding Challenges

Latest on Elixir Forum

Sponsor Spotlight

Our Sponsors

Categories:

Sub Categories:

Forums

Our Sponsors

We're in Beta

How to fix Bad argument in call to erlang:'++'(<<"xxx/crash.log">>, ".3") in lager_rotator_default:rotate_logfile/2 line 84