Advent of Code 2021

— 4194 palabras — 23 min

It’s december again, it feels like the last AoC was a couple months ago. This blog post will be updated whenever I solve a puzzle. You can bookmark it if you want to follow or subscribe to the RSS Feed.

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

More on their about page ⧉.

I’m really trying to finish this year, I’ll be on vacation. I’m hoping for the best because I really love these kind of puzzles.

You can also visit my progress and read the source of my solutions in the GitHub repository ⧉.

Table of Contents

Template

I use this template on the repository I use to solve the puzzles. It’s quite simple really.

One method for each part, assertions and data to verify the hint provided, and a method to read the final data input.

# utils.rb
require 'test/unit'
include Test::Unit::Assertions

def psol(part, solution)
  puts "Solution for part #{part}: #{solution}"
end

# template.rb
require_relative '../lib/utils'

input = IO.readlines('day01.txt', chomp: true)

test_input = []

# --- Part One ---

def solve_1(input)
end

assert_equal solve_1(test_input), 7
psol '1', solve_1(input)

# --- Part Two ---

def solve_2(input)
end

assert_equal solve_2(test_input), 5
psol '2', solve_2(input)

Solutions

Day 1: Sonar Sweep

test_input = [199, 200, 208, 210, 200, 207, 240, 269, 260, 263]

Part 1

def solve_1(input)
  sum = 0
  input.each_with_index do |m, i|
    sum += 1 if m > input[i - 1]
  end
  sum
end

assert_equal solve_1(test_input), 7
psol '1', solve_1(input)

Part 2

def solve_2(input)
  sum = 0
  input.each_with_index do |m, i|
    next if input[i + 3] == nil
    window_a = [m, input[i + 1], input[i + 2]].inject(:+)
    window_b = [input[i + 1], input[i + 2], input[i + 3]].inject(:+)
    sum += 1 if window_b > window_a
  end
  sum
end

assert_equal solve_2(test_input), 5
psol '2', solve_2(input)

Day 2: Dive!

test_input = [
  "forward 5",
  "down 5",
  "forward 8",
  "up 3",
  "down 8",
  "forward 2",
]

Part 1

def solve_1(input)
  x, y = 0, 0
  input.each do |line|
    direction, distance = line.split
    case direction
    when 'up'
      y -= distance.to_i
    when 'down'
      y += distance.to_i
    when 'forward'
      x += distance.to_i
    end
  end
  x * y
end

assert_equal solve_1(test_input), 150
psol '1', solve_1(input)

Part 2

def solve_2(input)
  x, y, z = 0, 0, 0
  input.each do |line|
    direction, distance = line.split
    case direction
    when 'up'
      z -= distance.to_i
    when 'down'
      z += distance.to_i
    when 'forward'
      x += distance.to_i
      y += z * distance.to_i
    end
  end
  x * y
end

assert_equal solve_2(test_input), 900
psol '2', solve_2(input)

Day 3: Binary Diagnostic

test_input = %w(
  00100
  11110
  10110
  10111
  10101
  01111
  00111
  11100
  10000
  11001
  00010
  01010
)

Part 1

def solve_1(input)
  gama = []
  epsilon = []
  input.first.size.times do |i|
    column = input.map { |line| line[i] }
    values = { 0 => column.count('0'), 1 => column.count('1') }.sort_by { |_k, v| v }
    epsilon << values[0][0]
    gama << values[1][0]
  end

  gama_rate = gama.join('').to_i(2)
  epsilon_rate = epsilon.join('').to_i(2)

  [gama_rate, epsilon_rate].inject(:*)
end

assert_equal solve_1(test_input), 198
psol '1', solve_1(input)

Part 2

def solve_2(input)
  calculate = -> (input, i, inv = false) do
    column = input.map { |line| line[i] }
    values = { 0 => column.count('0'), 1 => column.count('1') }.sort_by { |_k, v| v }

    values.reverse! if inv

    result = input.select { |line| line[i] == values[1][0].to_s }
    return result.first if result.size == 1

    calculate.call(result, i + 1, inv)
  end

  oxygen = calculate.call(input, 0).to_i(2)
  co2 = calculate.call(input, 0, true).to_i(2)

  [oxygen, co2].inject(:*)
end

assert_equal solve_2(test_input), 230
psol '2', solve_2(input)

Day 4: Giant Squid

This one was a pain because of how I handled the input data. I spent more time parsing it to be useful than solving the problem.

input = IO.readlines('day04.txt', chomp: true).map { |n| n.split(' ') }.reject(&:empty?).flatten

test_input = %w[
7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1

22 13 17 11  0
 8  2 23  4 24
21  9 14 16  7
 6 10  3 18  5
 1 12 20 15 19

 3 15  0  2 22
 9 18 13 17  5
19  8  7 25 23
20 11 10 24  4
14 21 16 12  6

14 21 17 24  4
10 16 15  9 19
18  8 23 26 20
22 11 13  6  5
 2  0 12  3  7
]
# --- Shared ---

def process_input(input)
  input = input.dup
  bingo_input = input.shift.split(',')
  bingo_boards = input.each_slice(25).map do |board|
    board.each_slice(5).to_a
  end

  [bingo_input, bingo_boards]
end

def check_for_bingo(board)
  board.each_with_index do |row, i|
    return true if row.uniq.length == 1
  end

  board.transpose.each_with_index do |col, i|
    return true if col.uniq.length == 1
  end

  false
end

Part 1

def solve_1(input)
  process_boards = -> (bingo_input, bingo_boards) do
    bingo_input.each do |number|
      bingo_boards.each do |board|
        board.each do |row|
          row.each do |cell|
            row[row.index(cell)] = 'X' if cell == number
          end
        end

        return [number, board] if check_for_bingo(board)
      end
    end
  end


  bingo_input, bingo_boards = process_input(input)
  number, board = process_boards.call(bingo_input, bingo_boards)

  board.flatten.reject { |cell| cell == 'X' }.map(&:to_i).inject(:+) * number.to_i
end

assert_equal solve_1(test_input), 4512
psol '1', solve_1(input)

Part 2

def solve_2(input)
  process_boards = -> (bingo_input, bingo_boards) do
    winning_numbers = []
    winning_boards_index = []
    bingo_input.each do |number|
      bingo_boards.each_with_index do |board, i|
        board.each do |row|
          row.each do |cell|
            if cell == number && !winning_boards_index.include?(i)
              row[row.index(cell)] = 'X'
            end
          end
        end

        if check_for_bingo(board) && !winning_boards_index.include?(i)
          winning_numbers << number
          winning_boards_index << i
        end
      end
    end

    return [winning_numbers.last, winning_boards_index.last]
  end

  bingo_input, bingo_boards = process_input(input)
  winning_number, winning_board_index = process_boards.call(bingo_input, bingo_boards)
  board = bingo_boards[winning_board_index]

  board.flatten.reject { |cell| cell == 'X' }.map(&:to_i).inject(:+) * winning_number.to_i
end

assert_equal solve_2(test_input), 1924
psol '2', solve_2(input)

Day 5: Hydrothermal Venture

I remember past editions so I asummed a couple of things, that’s why I created a class to handle grid methods. This kept my code tidy.

I would love to hear about another kind of solution to draw lines or an alternative to my Integer#midto method.

test_input = [
  '0,9 -> 5,9',
  '8,0 -> 0,8',
  '9,4 -> 3,4',
  '2,2 -> 2,1',
  '7,0 -> 7,4',
  '6,4 -> 2,0',
  '0,9 -> 2,9',
  '3,4 -> 1,4',
  '0,0 -> 8,8',
  '5,5 -> 8,2',
]
# --- Shared ---

class Integer
  def midto(other, &block)
    return self.downto(other, &block) if self > other
    self.upto(other, &block)
  end
end

class Grid
  def initialize
    @grid = []
  end

  def draw_line(x1, y1, x2, y2)
    x1.midto(x2) do |x|
      y1.midto(y2) do |y|
        @grid[y] ||= []
        if @grid[y][x].nil?
          @grid[y][x] = 1
        else
          @grid[y][x] += 1
        end
      end
    end
  end

  def draw_diagonal(x1, y1, x2, y2)
    xs = x1.midto(x2).to_a
    ys = y1.midto(y2).to_a

    xs.zip(ys).each do |x, y|
      @grid[y] ||= []
      if @grid[y][x].nil?
        @grid[y][x] = 1
      else
        @grid[y][x] += 1
      end
    end
  end

  def count
    @grid.flatten.compact.count { |x| x >= 2 }
  end
end

Part 1

def solve_1(input)
  grid = Grid.new
  input.each do |line|
    from, to = line.split(' -> ')
    x1, y1 = from.split(',').map(&:to_i)
    x2, y2 = to.split(',').map(&:to_i)

    next unless x1 == x2 || y1 == y2

    grid.draw_line(x1, y1, x2, y2)
  end

  grid.count
end

assert_equal solve_1(test_input), 5
psol '1', solve_1(input)

Part 2

def solve_2(input)
  grid = Grid.new
  input.each do |line|
    from, to = line.split(' -> ')
    x1, y1 = from.split(',').map(&:to_i)
    x2, y2 = to.split(',').map(&:to_i)

    if x1 == x2 || y1 == y2
      grid.draw_line(x1, y1, x2, y2)
    else
      grid.draw_diagonal(x1, y1, x2, y2)
    end
  end

  grid.count
end

assert_equal solve_2(test_input), 12
psol '2', solve_2(input)

Day 6: Lanternfish

Sneaky devs. I’m sure they had a laugh when they wrote this one, but it’s also increidibly smart to assume 99% of the people will do a memory-hungry implementation. I’m part of the 99%.

Took me by surprise when I tried to run my first part unchanged, but I also laughed out loud. Of course something like that was coming.

By taking the problem by a different angle, you should be able to avoid an exponentially growing array of fishes. My part 2 is my take on how to solve it, but I’ve seen way more elengant solutions out there.

This was fun as hell.

input = File.open('day06.txt', &:readline).split(',').map(&:to_i)

test_input = [3, 4, 3, 1, 2]

Part 1

def solve_1(input, days)
  input = input.dup

  step = -> (input) do
    input.dup.each_with_index do |n, i|
      if n == 0
        input[i] = 6
        input.push(8)
      else
        input[i] -= 1
      end
    end
  end

  days.times { |i| step.call(input) }
  input.count
end

assert_equal solve_1(test_input, 18), 26
assert_equal solve_1(test_input, 80), 5934
psol '1', solve_1(input, 80)

Part 2

def solve_2(input, days)
  dic = Hash.new(0).tap { |h| input.each { |i| h[i] += 1 } }

  days.times do |day|
    tdic = Hash.new(0)

    tdic[0] = 0
    tdic[6] = dic[0]
    tdic[8] = dic[0]

    (0..7).each do |i|
      tdic[i] += dic[i + 1]
    end

    dic = tdic
  end

  dic.values.inject(:+)
end

assert_equal solve_2(test_input, 256), 26984457539
psol '2', solve_2(input, 256)

Day 7: Treachery of Whales

Love when Ruby excels on its methods. I liked that I use some simple math to solve this problem. I feel proud of myself.

Part 1

def solve_1(input)
  min, max = input.min, input.max
  (min..max).map do |i|
    input.map { |n| (n - i).abs }.inject(:+)
  end.min
end

assert_equal solve_1(test_input), 37
psol '1', solve_1(input)

Part 2

def solve_2(input)
  min, max = input.min, input.max
  (min..max).map do |i|
    input.map do |n|
      m = (n - i).abs
      m * (m + 1) / 2
    end.inject(:+)
  end.min
end

Maybe I was tired, but couldn’t finish Part 2. The Part 1 was pretty easy to achieve, but couldn’t wrap my mind around the second part, which is the interesting part of this problem.

Part 1

def solve_1(input)
  appearances = Hash.new(0)
  input.each do |line|
    output = line.split(' | ').last
    output.split(' ').each do |word|
      next unless [2, 3, 4, 7].include?(word.size)
      appearances[word.size] += 1
    end
  end
  appearances.values.inject(:+)
end

assert_equal solve_1(test_input), 26
psol '1', solve_1(input)

Day 9: Smoke Basin

Another one I failed Part 2. I tried to recycle the same kind of solution from the first part, but I took very long to execute. I deleted my solution so I can try again fresh in the future.

Part 1

def solve_1(input)
  data = Ary.new(input.map { |i| Ary.new(i) })
  row_size, col_size = input.size, input[0].size
  low_points = []

  row_size.times do |i|
    col_size.times do |j|
      n = data[i][j]
      adjacents = [
        data.dig(i - 1, j), # up
        data.dig(i + 1, j), # down
        data.dig(i, j - 1), # left
        data.dig(i, j + 1)  # right
      ].compact
      low_points << n + 1 if adjacents.reject { |a| n < a }.size == 0
    end
  end

  low_points.inject(:+)
end