Advent of Code 2022 - Day 20

Learning Questions & Discussions Coding Challenges
1

Not sure why I could not think clearly with this one. Did quite the scribble with paper and pencil until I took the more “procedural looking” path.

Took 20 seconds to complete when using List (Like I said, procedural path) so I used Aja.Vector and replaced Enum and List and got that under a second, part 2 takes ~6 seconds though.

I am curious to see how others have done it, especially the performance.

Here’s the code:

defmodule AdventOfCode.Y2022.Day20 do
  alias AdventOfCode.Helpers.InputReader
  alias Aja.Vector

  def input, do: InputReader.read_from_file(2022, 20)

  def run(input \\ input()) do
    input = parse(input)

    run_1 = Task.async(fn -> run_1(input) end)
    run_2 = Task.async(fn -> run_2(input) end)

    {Task.await(run_1, :infinity), Task.await(run_2, :infinity)}
  end

  defp run_1(input) do
    compute_grove_sum(input, 1)
  end

  @decryption_key 811_589_153
  def run_2(input) do
    input
    |> Vector.map(fn {v, i} -> {v * @decryption_key, i} end)
    |> compute_grove_sum(10)
  end

  def parse(data \\ input()) do
    data
    |> String.split("\n", trim: true)
    |> Enum.map(&String.to_integer/1)
    |> Enum.with_index()
    |> Vector.new()
  end

  defp compute_grove_sum(input, repeat) do
    n = Vector.size(input) - 1
    sequence = mix(input, n, repeat)
    zero_idx = index_of(sequence, n, 0)
    grove_sum(sequence, n, zero_idx)
  end

  defp grove_sum(sequence, n, zero_idx) do
    [1000, 2000, 3000]
    |> Enum.reduce(0, fn x, acc ->
      {val, _} = sequence[rem(zero_idx + x, n + 1)]
      acc + val
    end)
  end

  defp mix(input, n, repeat) do
    1..repeat
    |> Enum.reduce(input, fn _, repeated_acc ->
      0..n
      |> Enum.reduce(repeated_acc, fn i, acc1 ->
        j =
          Enum.reduce_while(0..n, acc1, fn j, acc2 ->
            {_, idx} = acc1[j]

            case idx do
              ^i -> {:halt, j}
              _ -> {:cont, acc2}
            end
          end)

        {val, _} = acc1[j]
        {_, popped} = Vector.pop_at(acc1, j)
        ins = (j + val) |> Integer.mod(n)
        insert_at(popped, ins, {val, i})
      end)
    end)
  end

  defp insert_at(vector, idx, value) do
    {left, right} = Vector.split(vector, idx)
    left |> Vector.concat([value]) |> Vector.concat(right)
  end

  defp index_of(sequence, n, idx) do
    Enum.reduce_while(0..(n - 1), nil, fn x, acc ->
      case sequence[x] do
        {^idx, _} ->
          {:halt, x}

        _ ->
          {:cont, acc}
      end
    end)
  end
end
2

I solved this one in javascript instead, 1.2s for part 2 :grimacing::see_no_evil: I imagined an algorithm for it and I wasn’t sure how to express that in Elixir… Maybe I’ll try to come up with something later :slight_smile:

Basically I want a double linked list.

class Node {
  constructor(index, value) {
    this.index = index;
    this.value = value;
  }

  setNext(node) {
    this.next = node;
    node.prev = this;
  }

  move(steps) {
    if (steps < 0) {
      throw `steps needs to larger than 0, got ${steps}`;
    }
    this.prev.setNext(this.next);
    let node = this;
    while (steps >= 0) {
      node = node.next;
      steps--;
    }
    node.prev.setNext(this);
    this.setNext(node);
  }

  getNumbers() {
    const seen = new Set();
    let node = this;
    const numbers = [];
    while (!seen.has(node)) {
      seen.add(node);
      numbers.push(node.value);
      node = node.next;
    }
    return numbers;
  }
}

function mixNumbers(numbers, iterations = 1) {
  const nodes = numbers.map((number, index) => new Node(index, number));

  for (let i = 0; i < nodes.length; i++) {
    nodes[i].setNext(nodes[(i + 1) % nodes.length]);
  }
  const cycleLength = numbers.length - 1;
  for (let j = 0; j < iterations; j++) {
    for (let i = 0; i < numbers.length; i++) {
      const steps =
        ((nodes[i].value % cycleLength) + cycleLength) % cycleLength;
      nodes[i].move(steps);
    }
  }

  return nodes[0].getNumbers();
}

const fs = require("fs");

const numbers = fs
  .readFileSync("input.txt")
  .toString()
  .split("\n")
  .map((x) => parseInt(x))
  .filter((x) => !Number.isNaN(x));

const mixedNumbers = mixNumbers(
  numbers.map((n) => n * 811589153),
  10
);
const zeroIndex = mixedNumbers.findIndex((x) => x === 0);

let sum = 0;
for (let i = 1; i <= 3; i++) {
  const value = mixedNumbers[(zeroIndex + i * 1000) % numbers.length];
  sum += value;
}
console.log({ sum });
1 Like
3

Nice! I did think about using doubly linked list but I kept losing ideas on how to maintain the original list, I’ll take another look at your code and try to convert it to Elixir and see if it gets any performance improvements. My one is slow and am not a big fan of what I wrote. Good think I have a bidirectional circular list handy.

This one tortured me more than others, more so because it didn’t seem that hard, but thinking this problem through the lens of Elixir kept blocking me :confused: