Advent of Code 2022, Day 13: Distress Signal

Part A

Day 13 is about comparing lists. List can contain integers or another list. Input file looks like this:

[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

There are pairs of lists separated by an empty line. What we need to do is to compare each pair, figure out if it is in the right order and then output the sum of indices that are in the right order. But what right order means?

When comparing two values, the first value is called left and the second value is called right. Then:

• If both values are integers, the lower integer should come first. If the left integer is lower than the right integer, the inputs are in the right order. If the left integer is higher than the right integer, the inputs are not in the right order. Otherwise, the inputs are the same integer; continue checking the next part of the input.
• If both values are lists, compare the first value of each list, then the second value, and so on. If the left list runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue checking the next part of the input.
• If exactly one value is an integer, convert the integer to a list which contains that integer as its only value, then retry the comparison. For example, if comparing [0,0,0] and 2, convert the right value to 2; the result is then found by instead comparing [0,0,0] and [2].

Because lists are nested we can use recursion to solve this task. First let’s read and parse the input:

data = File.readlines("13.txt", chomp: true)
pairs = []

index = 0

data.each do |line|
  if line == ""
    index += 1
  else
    pairs[index] ||= []
    pairs[index].push(eval(line))
  end
end

Again I am being lazy and using eval here. Since those lists in input file has the same syntax as Ruby array I can just eval them to build proper Ruby objects.

Next let’s build recursive method to compare two objects (be it a list, integer or else). It will return -1 if left is smaller, 0 if left and right are the same, and 1 if right is smaller. -1 represents the right order.

def compare(left, right)
  types = [left.class, right.class]

  if types == [Integer, Integer]
    return left <=> right
  elsif types == [Array, Integer]
    return compare(left, [right])
  elsif types == [Integer, Array]
    return compare([left], right)
  elsif types == [Array, Array]
    size = [left.size, right.size].max
    size.times do |index|
      case compare(left[index], right[index])
      when -1
        return -1
      when 0
        next
      when 1
        return 1
      end
    end
  elsif types[0] == NilClass
    return -1
  elsif types[1] == NilClass
    return 1
  end

  return 0
end

First case is comparing two integers, here we can just use Ruby spaceship <=> operator.

The next two conditions are comparing list and single integer. In that case we need to convert integer into list with just this integer and compare both lists.

Forth condition is comparing two lists. First we are fetching both sizes and using larger one to iterate. We are comparing recursively elements of both lists at the same index. In case there are the same values we continue to the next one.

Because in forth condition we can have lists of different sizes, the recursive call can receive nil value on one side. If nil is on the left we return -1 because that is the right order. And we return 1 if right side is nil, it means right list is shorter.

Finally we can calculate our solution:

sum = 0

pairs.each_with_index do |(left, right), index|
  if compare(left, right) == -1
    sum += (index + 1)
  end
end

puts sum

And here is the full code:

data = File.readlines("13.txt", chomp: true)
pairs = []

index = 0

data.each do |line|
  if line == ""
    index += 1
  else
    pairs[index] ||= []
    pairs[index].push(eval(line))
  end
end

def compare(left, right)
  types = [left.class, right.class]

  if types == [Integer, Integer]
    return left <=> right
  elsif types == [Array, Integer]
    return compare(left, [right])
  elsif types == [Integer, Array]
    return compare([left], right)
  elsif types == [Array, Array]
    size = [left.size, right.size].max
    size.times do |index|
      case compare(left[index], right[index])
      when -1
        return -1
      when 0
        next
      when 1
        return 1
      end
    end
  elsif types[0] == NilClass
    return -1
  elsif types[1] == NilClass
    return 1
  end

  return 0
end

sum = 0

pairs.each_with_index do |(left, right), index|
  if compare(left, right) == -1
    sum += (index + 1)
  end
end

puts sum

Part B

In Part B we need to sort all packets in the right order disregarding empty lines and then find indexes of divider packets ([[2]] and [[6]]) and multiply them together.

From Part A we already have a method to compare two packets with each other, so we can just pass it to Ruby builtin sort method and we will get packets sorted:

data.sort { |a, b| compare(a, b) }

Our compare method is returning -1, 0 or 1 which is exactly what sort method expects. Now it’s time to find divider packets in this sorted array and output our solution. Here is the full code:

data = File.readlines("13.txt", chomp: true).reject { |line| line == "" }.map { |line| eval(line)}

data.push([[2]])
data.push([[6]])

def compare(left, right, depth = 0)
  types = [left.class, right.class]

  if types == [Integer, Integer]
    return left <=> right
  elsif types == [Array, Integer]
    return compare(left, [right], depth + 1)
  elsif types == [Integer, Array]
    return compare([left], right, depth + 1)
  elsif types == [Array, Array]
    size = [left.size, right.size].max
    size.times do |index|
      case compare(left[index], right[index], depth + 1)
      when -1
        return -1
      when 0
        next
      when 1
        return 1
      end
    end
  elsif types[0] == NilClass
    return -1
  elsif types[1] == NilClass
    return 1
  end

  return 0
end

divider = nil

data.sort { |a, b| compare(a, b) }.each_with_index do |packet, index|
  if packet == [[2]]
    divider = index + 1
  elsif packet == [[6]]
    puts "Decoder key is #{divider * (index + 1)}"
  end
end