This post tells that tale of the Advent of Code’s Day 20 problem part 1. The challenge tells the story of Santa telling all his elves to visit houses for him and deliver presents. However, there’s a little twist. Each elf can only visit house numbers that are evenly divisible by the elf’s number. The algorithm should return the lowest house number for a given number of presents you give it as a parameter. It’s an interesting challenge. If you haven’t done the challenge, then I highly recommend you give it a whirl before going any further. It’s a fun challenge.

Time to break out the loops right?

Your first gut instinct would tell you we need to iterate through a giant array of numbers hoping for the best result. Beware this approach. Let’s look closer at the relationships between house number, elf number, and the total number of presents each house receives.

house 1 = 10 presents
house 2 = 10 + 20 presents
house 3 = 10 + 30 presents
house 4 = 10 + 20 + 40 presents
house 5 = 10 + 50 presents
house 6 = 10 * ( 1 + 2+ 3 + 6 ) presents

Did you catch it? There is a direct connection between the factors of the house and the total number of presents the house received. Now this question becomes a factorization problem.

Enter the algorithm

To start we want to find the factors of a given number. There is nothing ground breaking going on here. A basic implementation will look like the following:

class Integer #we will extend the integer class to include this
  def factors
    factors = 1.upto(self).select { |i| (self % i).zero?}
    factors.inject([]) do |factor_arr, i|
      factor_arr << self / i unless i == self / i
      factor_arr << i
    end
  end
end

This algorithm is poorly suited for our challenge. Please do not use this as is. We do not need to go all the way through the range 1 to the number we provide for the input. Nor do we need to persist these factors.

Let’s remove the array inside the inject method, and just keep the sum. Another optimization is that we only need to traverse the range 1 to square root the input. Why? You can check out the simple explanations at Stack Overflow here. Our new factorizing method would look like this:

class Integer
  def factors_sum
    factors = 1.upto(Math.sqrt(self)).select{|i| (self % i).zero?}
    factors.inject(0) do |factors_sum, i|
      factors_sum += self / i unless i == self / i
      f += i
    end
  end
end

Now at least we are cutting things down to O(n**1/2) by not going through only the square root of the number.

All we have left is to piece together our factorization method with the house presents search. Since everything is multiplied by ten, I’ll bring that out front in place of doing the multiplication in each iteration. Hold onto your butts…

def elf_house_present_counter(magic_num)
  magic_num /= 10
  return 'House #1' if magic_num < 11
  (2..magic_num).each do |house_num|
    house_factors_sum = house_num.factors_sum
    if house_factors_sum >= magic_num
      return "The House you are looking for is:  ##{house_num}\n +
             "It has #{house_factors_sum} presents!"
    end
  end
end

Taking a closer look, it seems our time complexity approaches O( n**1.5 ). This algorithm is really an expansion on prime factorization. I hope you found this useful!