## --- Day 20: Infinite Elves and Infinite Houses ---

In this puzzle we have to find the lowest house number of the house to get at least as many presents as the number in our puzzle input.

## Table of Contents

## Part 1

In the first part we need to figure out which the lowest house number gets as many presents as our input number.

If we look at an example, we can see that it looks like a sum of divisors.

```
House 1 got 10 presents. | 1 => 1 (1)
House 2 got 30 presents. | 2 => 3 (1 + 2)
House 3 got 40 presents. | 3 => 4 (1 + 3)
House 4 got 70 presents. | 4 => 7 (1 + 2 + 4)
House 5 got 60 presents. | 5 => 6 (1 + 5)
House 6 got 120 presents. | 6 => 12 (1 + 2 + 3 + 6)
House 7 got 80 presents. | 7 => 8 (1 + 7)
House 8 got 150 presents. | 8 => 15 (1 + 2 + 4 + 8)
House 9 got 130 presents. | 9 => 13 (1 + 3 + 9)
```

We need to create this function. You can ignore the `limit`

parameter, we will need it in the second part.

```
private static int GetDivisorsSum(int n, int limit = -1)
{
var sum = 0;
var iterations = 1;
for (var i = 1; i <= Math.Sqrt(n); i++)
{
if (limit != -1 && iterations >= limit)
break;
if (n % i != 0)
continue;
sum += i;
iterations++;
if (n / i == i)
continue;
sum += n / i;
iterations++;
}
return sum;
}
```

And to find the lowest house number we can brute force the answer by getting the sum of the divisors on each house number (**1**, **2**, **3**…) until we get the number that is greater than the input value. And that will give us an answer to the first part.

```
public object Part1(IEnumerable<string> lines)
{
var input = int.Parse(lines.FirstOrDefault());
var calculatedValue = 0;
var houseNumber = 0;
while (input > calculatedValue)
{
houseNumber++;
calculatedValue = GetDivisorsSum(houseNumber) * 10;
}
return houseNumber.ToString();
}
```

## Part 2

In the second part, we can’t visit an infinite number of houses, so we need some sort of limit.

In `GetDivisorsSum`

we already have a `limit`

parameter that we can pass. The main thing that will change, is that we’ll stop iterating after we set `limit`

.

```
if (limit != -1 && iterations >= limit)
break;
```

But otherwise the solution looks exactly the same as in the first part. Oh, we also have to multiply by `11`

instead of `10`

. And that will be our solution for the second part.

```
public object Part2(IEnumerable<string> lines)
{
var input = int.Parse(lines.FirstOrDefault());
var calculatedValue = 0;
var houseNumber = 0;
while (input > calculatedValue)
{
houseNumber++;
calculatedValue = GetDivisorsSum(houseNumber, 50) * 11;
}
return houseNumber.ToString();
}
```

Links: