Dazbo's Advent of Code solutions, written in Python

Day 20: Infinite Elves and Infinite Houses

ComprehensionsDefaultdictLRU Cache

An infinite number of elves have been tasked with delivering presents to an infinite number of houses, numbered sequentially as 1, 2, 3, etc. Each elf is numbered, and elves deliver to houses that are a multiple of their elf identifier. E.g.

- Elf #1 delivers to houses 1, 2, 3, 4, etc.
- Elf #2 delivers to houses 2, 4, 6, 8, etc.
- Elf #3 delivers to houses 3, 6, 9, 12, etc.

When an elf visits a given house, it delivers ten times as many presents as its elf identifier. Thus:

House Elf 1 Elf 2 Elf 3 Elf 4 Elf 5 Elf 6Running Total 1 10 - - - - -10 2 10 20 - - - -30 3 10 - 30 - - -40 4 10 20 - 40 - -70 5 10 - - - 50 -60 6 10 20 30 - - 60120

**What is the lowest house number of the house to get at least as many presents as the number in your puzzle input?**

From the table above, we can see that each house is visited by all the elf numbers that are *factors* of that house number. In case you need a reminder: the factors of any given number are the integer values that the number is divible by, leaving no remainder. For example, we can identify the factors of the number 8 as follows:

Integer | 8 integer divided by integer | Remainder | Is a factor? |

1 | 8 | 0 | Yes |

2 | 4 | 0 | Yes |

3 | 2 | 2 | No |

4 | 2 | 0 | Yes |

5 | 1 | 3 | No |

There’s no point in counting any higher, since no number greater than 4 (i.e. `8\\2`

) can be a factor of 8.

In fact, it turns out that we never need to test integer values greater than the square root of 8. Why? Because if we divide our number by any factor that is smaller than the square root of our number, then the result will be the complementary factor that is larger than the square root. For example, the square root of 8 is approximately 2.83. The largest possible integer we need to test is 2. We can divide 8 by 2, and the result is 4. Thus, 4 is a factor of 8. Similarly, 8 is a factor of 8, but we already determined that when we divided 8 by 1.

Why am I telling you all this? Because it turns out that for any given house number `h`

, the number of presents delivered to that house will be the result of the sum of `10f`

, for each factor `f`

of `h`

.

First, let’s create a function that returns all the factors, for a given house number:

```
def get_factors(num: int) -> set[int]:
""" Gets the factors for a given number. Returns a set[int] of factors.
# E.g. when num=8, factors will be 1, 2, 4, 8 """
factors = set()
# Iterate from 1 to sqrt of 8,
# since a larger factor of num must be a multiple of a smaller factor already checked
for i in range(1, int(num**0.5) + 1): # e.g. with num=8, this is range(1, 3)
if num % i == 0: # if it is a factor, then dividing num by it will yield no remainder
factors.add(i) # e.g. 1, 2
factors.add(num//i) # i.e. 8//1 = 8, 8//2 = 4
return factors
```

It works as follows:

- Create a set to store our factors.
- Obtain a range that returns all integers that are smaller than the square root of the supplied number. (Note that raising any number to the power of
`1/2`

is the same as taking the square root of that number.) - For each integer value returned by this range, test if it is factor by dividing
`num`

by this integer. If`num`

is exactly divisible by the this integer, then the integer is a factor. Furthermore, the quotient of the division is also a factor. So we add both factors to our set.

Actually, this seems like a useful reusable function, so I’ve moved it into by `type_defs.py`

module.

Now we call it, like this:

```
# Part 1
presents_dropped, house_num = 0, 0
while presents_dropped < TARGET:
house_num += 1
presents_dropped = sum(factor * 10 for factor in td.get_factors(house_num))
logger.debug("House=%d, presents dropped=%d", house_num, presents_dropped)
logger.info("Part 1: House=%d, presents dropped=%d", house_num, presents_dropped)
```

This works as follows:

- We loop until the number of presents dropped exceeds our target.
- Increment
`house_num`

, and then pass this`house_num`

to`td.get_factors()`

, which returns all the factors for this house number. - Multiply each factor by 10, to give us the number of presents dropped by a given elf.
- Sum up these values, to give the total number of presents dropped at this house.

If we set our target as 200, the result looks like this:

Great! So far, so good.

The elves now each visit a maximum of 50 houses, and each elf drops a number of presents equal to 11 times their elf number, at each house.

As before:

**What is the lowest house number of the house to get at least as many presents as the number in your puzzle input?**

My amended strategy is:

- Count the occurences of each factor, because each factor represents an elf visit to any house.
- When an elf reaches its limit of visits, then ignore this elf factor when calculating present drops.

Here’s the code:

```
def generate_presents_for_house(per_elf_multiplier: int, elf_visit_limit: int = 0):
""" Generator function that returns the number of presents dropped at a given house.
Yields:
[tuple]: Current house number, total presents dropped at this house
"""
house_num = 0
elf_visits = defaultdict(int)
while True: # iterate for each house, yielding each time
house_num += 1
presents_dropped = 0
factors_for_house = td.get_factors(house_num)
# iterate through all the factors for this house
for factor in factors_for_house:
if elf_visit_limit and elf_visits[factor] >= elf_visit_limit:
pass
else:
elf_visits[factor] += 1
presents_dropped += factor * per_elf_multiplier
if logger.isEnabledFor(logging.DEBUG): # avoid expensive sorting
logger.debug("House %d visited by: %s", house_num, sorted(factors_for_house))
logger.debug("Presents dropped: %d", presents_dropped)
# convert defaultdict to dict so we don't print out the default factory information
logger.debug("Factors counter: %s", dict(elf_visits))
yield house_num, presents_dropped
```

A few points to note:

- My function is a generator.
- It has a
`yield`

statement rather than`return`

statement. - It works like an iterator, but - as a generator - it returns each successive value
*on-the-fly*, i.e. returning a single value with each call. It doesn’t need to pre-calculate*all*values. - It persists state between successive calls. So, we can keep track of our elf visits, even between successive calls to the generator.

- It has a
- I’m using a defaultdict to count the number of visits for a given elf. That way, we can increment every time we see a given elf number, but we don’t have to initialise the dictionary.
- I’m using the same
`td.get_factors(house_num)`

as Part 1. - The
`debug`

logging statements are expensive, because they are called frequently, and involve a sort. Even if I set the debug level to`INFO`

, the variables within the`logger.debug()`

statements are still evaluated; even though they are not printed! So, I’ve added a logging level check around these`debug`

statements. It makes a big difference to the overall performance!!

We call the generator function like this:

```
# Part 2
gen = generate_presents_for_house(11, MAX_HOUSES_PER_ELF)
presents_dropped, house_num = 0, 0
while presents_dropped < TARGET:
house_num, presents_dropped = next(gen)
logger.info("Part 2: House=%d, presents dropped=%d", house_num, presents_dropped)
```

To test, I’m going to use these values:

```
logger.setLevel(logging.DEBUG)
TARGET = 200
MAX_HOUSES_PER_ELF = 5
```

And the output looks like this:

With debugging enabled, note how each elf maxes out at 5 drops.

With the real goal, this code takes quite a while to run. So I made an optimisation that halved the time!

I added the `@lru_cache(maxsize=None)`

*decorator* to my `get_factors()`

function. This is a built-in decorator, that comes with the `functools`

module. It is a *memoization* mechanism that automatically caches the results of function executions, based on the arguments supplied. Because Part 1 and Part 2 both require calculation of factors for a huge number of houses starting at house 1, adding the `lru_cache`

means that these factors are only ever calculated once for a given house. If we ask the function to calculate factors for a house that has been passed to the function before, then the result is automatically returned from the cache, rather than being recalculated! This is very efficient.

We add the cache by adding just one line, like this:

```
@lru_cache(maxsize=None)
def get_factors(num: int) -> set[int]:
""" Gets the factors for a given number. Returns a set[int] of factors.
# E.g. when num=8, factors will be 1, 2, 4, 8 """
factors = set()
# Iterate from 1 to sqrt of 8,
# since a larger factor of num must be a multiple of a smaller factor already checked
for i in range(1, int(num**0.5) + 1): # e.g. with num=8, this is range(1, 3)
if num % i == 0: # if it is a factor, then dividing num by it will yield no remainder
factors.add(i) # e.g. 1, 2
factors.add(num//i) # i.e. 8//1 = 8, 8//2 = 4
return factors
```

Without cache:

```
21:35:14.794:elf_delivery - INF: Part 1: House=831600, presents dropped=36902400
21:35:38.804:elf_delivery - INF: Part 2: House=884520, presents dropped=36191925
21:35:38.816:elf_delivery - INF: Execution time: 44.948 seconds
```

With cache:

```
21:36:06.963:elf_delivery - INF: Part 1: House=831600, presents dropped=36902400
21:36:10.792:elf_delivery - INF: Part 2: House=884520, presents dropped=36191925
21:36:10.802:elf_delivery - INF: Execution time: 26.478 seconds
```

Cool, right?