Advent of Code 2020: Day 10 (Ruby solution)

Puzzles of 10th day of Advent of Code 2020 event are tricky.

The input file contains above hundred of integers. The order is random and there is no continuity between them. The difference between the two following numbers can be 1, 2, or 3.

The first task is about counting how many differences are 1 and 3. You are asked for product of their numbers. This part is easy:

file = File.read('inputs/day10.txt')
numbers = [0]
numbers += file.lines.map(&:to_i)
numbers.sort!
numbers << numbers.last + 3
gaps = {1 => 0, 2 => 0, 3 => 0}

numbers.drop(1).each_with_index do |number, index|
  gaps[number - numbers[index]] += 1
end

puts "First task answer: #{gaps[1] * gaps[3]}"

The second puzzle is problematic. You have to find total number of distinct subsets such that the difference between two following numbers still does not exceed 3. I wrote following recuresive algorithm:

def count_arrangements numbers, start_index
  arrangements = 1
  numbers.each_with_index do |number, index|
    if index > start_index && index < numbers.size - 1
      arrangements += count_arrangements(numbers - [number], index-1) if numbers[index + 1] - numbers[index - 1] <= 3
    end
  end
  arrangements
end

It was good with sample inputs but when it came to my file it took ages! Then I remembered the principle of divide and conquer. I split my input where the difference was 3. I used my recursive algorithm on each part of them and multiplied the obtained results. It succeeded!

def split numbers
  splitted = []
  tmp = []
  numbers.each_with_index do |number, index|
    tmp << number
    if index == numbers.size - 1 || numbers[index+1] - number == 3
      splitted << tmp
      tmp = []
    end
  end
  splitted
end

puts "Second task answer: #{split(numbers).map { |ns| count_arrangements(ns, 0) }.reduce(:*)}"