# Advent of Code 2022 - Day 20

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 Aja.Vector

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)

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
``````

I solved this one in javascript instead, 1.2s for part 2  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 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)) {
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.getNumbers();
}

const fs = require("fs");

const numbers = fs
.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

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 