aoc/year2015/day20.rs
1//! # Infinite Elves and Infinite Houses
2//!
3//! ## Part One
4//!
5//! The amount of presents that each house receives is 10 times the
6//! [divisor function](https://en.wikipedia.org/wiki/Divisor_function) `σ`.
7//! For example the divisors of 6 are 1, 2, 3 and 6, so house 6 receives
8//! 10 + 20 + 30 + 60 = 120 presents. The answer will be a
9//! [superabundant number](https://en.wikipedia.org/wiki/Superabundant_number).
10//!
11//! If `n` has the prime factorization `n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ` then the sum of divisors is
12//! `σ(n) = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ... × [(pₖ^(aₖ+1) - 1)/(pₖ - 1)]`
13//! or more compactly `σ(n) = ∏ᵢ₌₁ᵏ [(pᵢ^(aᵢ+1) - 1)/(pᵢ - 1)]`
14//!
15//! For example `n = 12 = 2² × 3¹`
16//!
17//! * `σ(12) = [(2³ - 1)/(2 - 1)] × [(3² - 1)/(3 - 1)]`
18//! * `[(8 - 1)/1] × [(9 - 1)/2] = 7 × 4 = 28`
19//!
20//! Starting from 41 (the largest possible prime encountered in houses up to 50 billion presents)
21//! we recursively try smaller and smaller prime powers, finding the smallest house number that
22//! exceeds the target.
23//!
24//! ## Part Two
25//!
26//! We get a list of all possible house numbers that have divisor sums that exceed the value.
27//! Checking in ascending order, each house is broken down into its factors, including only those
28//! where the second elf will actually deliver.
29use crate::util::hash::*;
30use crate::util::parse::*;
31
32/// Covers all possible scenarios up to 50 billion presents for part one.
33/// Checked by brute forcing all solutions that the highest prime factor is 41.
34const PRIMES: [u32; 13] = [41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2];
35
36pub fn parse(input: &str) -> u32 {
37 input.unsigned()
38}
39
40pub fn part1(input: &u32) -> u32 {
41 // Recursively compute the divisor sum greater than the target.
42 fn divisor_sum(cache: &mut FastMap<(u32, u32), u32>, primes: &[u32], target: u32) -> u32 {
43 if primes.is_empty() {
44 return target;
45 }
46
47 // Cache previously seen states.
48 let key = (primes[0], target);
49 if let Some(&value) = cache.get(&key) {
50 return value;
51 }
52
53 // Try not including this prime.
54 let mut result = divisor_sum(cache, &primes[1..], target);
55 let mut power = 1;
56 let mut sum = 1;
57
58 // Try increasing powers of this prime until the divisor sum exceeds the target.
59 while sum < target {
60 power *= primes[0];
61 sum += power;
62
63 let next = power * divisor_sum(cache, &primes[1..], target.div_ceil(sum));
64 result = result.min(next);
65 }
66
67 cache.insert(key, result);
68 result
69 }
70
71 divisor_sum(&mut FastMap::new(), &PRIMES, input.div_ceil(10))
72}
73
74pub fn part2(input: &u32) -> u32 {
75 // Differences from part one:
76 // * Return all possible house numbers.
77 // * Remove cache since each state is unique so it slows things down.
78 fn divisor_sum(candidates: &mut Vec<u32>, primes: &[u32], house: u32, target: u32) -> u32 {
79 if primes.is_empty() {
80 if target == 1 {
81 candidates.push(house);
82 }
83 return target;
84 }
85
86 // Try not including this prime.
87 let mut result = divisor_sum(candidates, &primes[1..], house, target);
88 let mut power = 1;
89 let mut sum = 1;
90
91 // Try increasing powers of this prime until the divisor sum exceeds the target.
92 while sum < target {
93 power *= primes[0];
94 sum += power;
95
96 let ds = divisor_sum(candidates, &primes[1..], house * power, target.div_ceil(sum));
97 result = result.min(power * ds);
98 }
99
100 result
101 }
102
103 let target = input.div_ceil(11);
104 let mut candidates = Vec::new();
105
106 // Get list of all house numbers that meet or exceed the target value in ascending order.
107 divisor_sum(&mut candidates, &PRIMES, 1, target);
108 candidates.sort_unstable();
109
110 // Find the first house taking into account the 50 present limit.
111 candidates.into_iter().find(|&house| factor_sum(&PRIMES, house, 1) >= target).unwrap()
112}
113
114/// Combine prime factors into all factors, only counting those where the elf will still deliver.
115fn factor_sum(primes: &[u32], house: u32, factor: u32) -> u32 {
116 if primes.is_empty() {
117 // Check if the elf reached this house.
118 if 50 * factor >= house { factor } else { 0 }
119 } else {
120 (0..31)
121 .map(|exp| primes[0].pow(exp))
122 .take_while(|&prime_power| house.is_multiple_of(prime_power))
123 .map(|prime_power| factor_sum(&primes[1..], house, factor * prime_power))
124 .sum()
125 }
126}