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"
@data = File.readlines("20.txt", chomp: true).map(&:to_i)
@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
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