# 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(:*)}"
```

## No Comments Yet