# Advent of Code 2022, Day 20: Grove Positioning System

## Part A

On Day 20 we have a chance to build a linked list. Or at least that’s what I did.

We have the following input:

``````1
2
-3
3
-2
0
4
``````

We need to iterate over each item and then shift it forward or backward by the amount equal to it’s value. So 1 should be moved 1 unit forward, 2 should be moved 2 units forward and -3 three units backward. If we get to the end or beginning we should wrap to another end.

Here is the process from puzzle page:

``````Initial arrangement:
1, 2, -3, 3, -2, 0, 4

1 moves between 2 and -3:
2, 1, -3, 3, -2, 0, 4

2 moves between -3 and 3:
1, -3, 2, 3, -2, 0, 4

-3 moves between -2 and 0:
1, 2, 3, -2, -3, 0, 4

3 moves between 0 and 4:
1, 2, -2, -3, 0, 3, 4

-2 moves between 4 and 1:
1, 2, -3, 0, 3, 4, -2

0 does not move:
1, 2, -3, 0, 3, 4, -2

4 moves between -3 and 0:
1, 2, -3, 4, 0, 3, -2
``````

After mixing the input list we need to return the sum of 1000th, 2000th and 3000th (including wrapping) numbers after the value 0.

Ruby array class has `rotate` method that we can use for moving elements forward or backward, but doing it in the array we will need to shift a lot of other elements and such operationts will be slow. And our real input has thousands of numbers.

We need to implement something faster and one possible solution is to have a linked list. Or actually double linked list.

Each node of such list can be represented by `Node` class:

``````class Node
attr_accessor :value
attr_accessor :original_index
attr_accessor :next
attr_accessor :prev
end
``````

`original_index` is the position in the initial list, so we now which element should be moved next. `next` is the pointer to next element on the list and `prev` is the pointer to previous elements. `value` is just the number we are storing.

We can build our list using the following code:

``````@data = File.readlines("20.txt", chomp: true).map(&:to_i)
@size = @data.size

root = nil
current = nil

@data.each_with_index do |element, index|
if root.nil?
root = Node.new
root.value = element
root.original_index = index
root.prev = root
root.next = root

current = root
else
successor = current.next
node = Node.new
node.value = element
node.original_index = index
node.prev = current
node.next = successor

current.next = node
successor.prev = node

current = node
end
end
``````

Let’s now implement the method for moving element forward:

``````def forward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = next_node

(steps - 1).times do
current = current.next
end

next_node = current.next

current.next = node
next_node.prev = node

node.prev = current
node.next = next_node
end
``````

First line is the optimization to now wrap around list multiple times. If we have a list of 10 items and we need to move forward by 100 we can use modulo to calculate final position and move by less than 10.

Btw, our first and last elements are also connected, so this linked list is circular. There is no need to implement some wrap around logic. But then you never know which element is the first one.

So in our `forward` method first we calculate the actual number of steps we need to move. We save our current previous and next nodes. We link them together, so the current element is kind of removed from the list.

Then we move forward to the next element until we move required number of steps. We insert our current element in that place, updating all necessary pointers.

Method to move backward is basically the same, but you need to update pointers in a different way:

``````def backward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = prev_node

(steps - 1).times do
current = current.prev
end

prev_node = current.prev

current.prev = node
prev_node.next = node

node.prev = prev_node
node.next = current
end
``````

I guess it is possible to use `forward` method to move backward by moving forward with wrap around.

Then we can write some helper methods:

``````def find_index(node, index)
while node.original_index != index
node = node.next
end

return node
end

def find_value(node, value)
while node.value != value
node = node.next
end

return node
end

def nth_successor(node, n)
n.times do
node = node.next
end

node
end
``````

`find_index` is used to find next element to move by it’s original index. `find_value` will be used to find element with value 0 and `nth_successor` to find 1000th next element after 0 and so on.

And here is full code of our solution:

``````require "debug"

@size = @data.size

class Node
attr_accessor :value
attr_accessor :original_index
attr_accessor :next
attr_accessor :prev
end

root = nil
current = nil

@data.each_with_index do |element, index|
if root.nil?
root = Node.new
root.value = element
root.original_index = index
root.prev = root
root.next = root

current = root
else
successor = current.next
node = Node.new
node.value = element
node.original_index = index
node.prev = current
node.next = successor

current.next = node
successor.prev = node

current = node
end
end

def forward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = next_node

(steps - 1).times do
current = current.next
end

next_node = current.next

current.next = node
next_node.prev = node

node.prev = current
node.next = next_node
end

def backward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = prev_node

(steps - 1).times do
current = current.prev
end

prev_node = current.prev

current.prev = node
prev_node.next = node

node.prev = prev_node
node.next = current
end

def find_index(node, index)
while node.original_index != index
node = node.next
end

return node
end

def find_value(node, value)
while node.value != value
node = node.next
end

return node
end

def nth_successor(node, n)
n.times do
node = node.next
end

node
end

def mix(node)
next_node = node
current_index = 0

@data.size.times do
current = find_index(next_node, current_index)
next_node = current.next
current_index += 1

if current.value < 0
backward(current, -current.value)
elsif current.value > 0
forward(current, current.value)
end
end
end

mix(root)

zero = find_value(root, 0)
puts [nth_successor(zero, 1000).value, nth_successor(zero, 2000).value, nth_successor(zero, 3000).value].sum
``````

## Part B

Second part is not that different. You need to multiple each input number by 811589153 and mix input 10 times. You can probably see that having this tiny optimization with modulo is necessary. Otherwise you will be doing a lot if pointless moves.

Here is the full code for Part B. Just few lines changed:

``````require "debug"

@data = File.readlines("20.txt", chomp: true).map(&:to_i).map { |elem| elem * 811589153 }

@size = @data.size

class Node
attr_accessor :value
attr_accessor :original_index
attr_accessor :next
attr_accessor :prev
end

root = nil
current = nil

@data.each_with_index do |element, index|
if root.nil?
root = Node.new
root.value = element
root.original_index = index
root.prev = root
root.next = root

current = root
else
successor = current.next
node = Node.new
node.value = element
node.original_index = index
node.prev = current
node.next = successor

current.next = node
successor.prev = node

current = node
end
end

def forward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = next_node

(steps - 1).times do
current = current.next
end

next_node = current.next

current.next = node
next_node.prev = node

node.prev = current
node.next = next_node
end

def backward(node, steps)
steps = steps % (@size - 1)

prev_node = node.prev
next_node = node.next

prev_node.next = next_node
next_node.prev = prev_node

current = prev_node

(steps - 1).times do
current = current.prev
end

prev_node = current.prev

current.prev = node
prev_node.next = node

node.prev = prev_node
node.next = current
end

def find_index(node, index)
while node.original_index != index
node = node.next
end

return node
end

def find_value(node, value)
while node.value != value
node = node.next
end

return node
end

def nth_successor(node, n)
n.times do
node = node.next
end

node
end

def mix(node)
next_node = node
current_index = 0

@data.size.times do
current = find_index(next_node, current_index)
next_node = current.next
current_index += 1

if current.value < 0
backward(current, -current.value)
elsif current.value > 0
forward(current, current.value)
end
end
end

10.times do
mix(root)
end

zero = find_value(root, 0)
puts [nth_successor(zero, 1000).value, nth_successor(zero, 2000).value, nth_successor(zero, 3000).value].sum
``````