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}
aoc/year2015/day20.rs

aoc/year2015/
day20.rs
