aoc/year2015/
day20.rs

1//! # Infinite Elves and Infinite Houses
2//!
3//! The amount of presents that each house receives in part one is 10 times the
4//! [divisor function](https://en.wikipedia.org/wiki/Divisor_function) `σ`.
5//! For example the divisors of 6 are 1, 2, 3 and 6, so house 6 receives
6//! 10 + 20 + 30 + 60 = 120 presents.
7//!
8//! It's highly likely that the answer will be a
9//! [superabundant number](https://en.wikipedia.org/wiki/Superabundant_number) but there's no way
10//! to easily *prove* that so we brute force check every possible solution. The approach is similar
11//! to a reverse [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes),
12//! iterating first over each elf, then over each house adding the presents.
13//! Somewhat unintuitively the `ln(x)` asymptotic complexity of this approach is much lower
14//! than the `n√n` complexity of finding the factors of each number.
15//!
16//! To speed things up we make one high level optimization and a few low tweaks.
17//!
18//! The high level optimization is an observation from user `warbaque` on the
19//! [Day 20 solution thread](https://www.reddit.com/r/adventofcode/comments/3xjpp2/day_20_solutions/)
20//! that [Robin's inequality](https://en.wikipedia.org/wiki/Divisor_function#Growth_rate)
21//! shows that the `σ(n)` function is lower than `eᵞ * n * ln(ln(n))` for all `n` greater than 5040.
22//! This means that we can determine a starting index close to the final result, skipping over a
23//! huge chunk of numbers.
24//!
25//! The low level tweaks reduce the amount of work that needs to be done.
26//! We break the search range into fixed size blocks from `start` to `end`,
27//! for example 200000 to 299999 with a block size of 100000. Then we can make some observations:
28//!
29//! * Elf 1 visits each house once.
30//! * Elves from `start` to `end` each visit a different house exactly once,
31//!   bringing start, start + 1, ... presents.
32//! * Elves from `end / 2` to `start` skip over all the houses.
33//! * Elves from `block size` to `end / 2` visit *at most* one house as the increment is
34//!   greater than the size of the block.
35//! * Elves from `2` to `block size` may visit any number of times.
36
37// More explicit syntax fits in with surrounding code better.
38#![allow(clippy::needless_range_loop)]
39
40use crate::util::parse::*;
41
42const BLOCK: usize = 100_000;
43
44type Input = (u32, usize);
45
46pub fn parse(input: &str) -> Input {
47    let robins_inequality = [
48        (100000, 4352000),
49        (200000, 8912250),
50        (300000, 13542990),
51        (400000, 18218000),
52        (500000, 22925240),
53        (600000, 27657740),
54        (700000, 32410980),
55        (800000, 37181790),
56        (900000, 41967820),
57        (1000000, 46767260),
58        (1100000, 51578680),
59        (1200000, 56400920),
60        (1300000, 61233020),
61        (1400000, 66074170),
62        (1500000, 70923680),
63        (1600000, 75780960),
64        (1700000, 80645490),
65        (1800000, 85516820),
66        (1900000, 90394550),
67        (2000000, 95278320),
68    ];
69
70    // Find a starting block closer to the answer. Part two presents overall are lower than
71    // part one so the answer will also be after this block.
72    let (target, mut start) = (input.unsigned(), 0);
73
74    for (key, value) in robins_inequality {
75        if target >= value {
76            start = key;
77        } else {
78            break;
79        }
80    }
81
82    assert!(target > 5040);
83    assert!(start > 100000);
84
85    (target, start)
86}
87
88pub fn part1(input: &Input) -> usize {
89    let (target, mut start) = *input;
90    let mut end = start + BLOCK;
91    let mut houses = vec![0; BLOCK];
92
93    loop {
94        // Elves that visit exactly once.
95        for i in 0..BLOCK {
96            houses[i] = 10 * (1 + start + i) as u32;
97        }
98
99        // Elves that visit at most once.
100        for i in BLOCK..end / 2 {
101            let presents = 10 * i as u32;
102            let j = start.next_multiple_of(i) - start;
103
104            if j < BLOCK {
105                houses[j] += presents;
106            }
107        }
108
109        // All remaining elves.
110        for i in 2..BLOCK {
111            let presents = 10 * i as u32;
112            let mut j = start.next_multiple_of(i) - start;
113
114            while j < BLOCK {
115                houses[j] += presents;
116                j += i;
117            }
118        }
119
120        if let Some(found) = houses.iter().position(|&p| p >= target) {
121            break start + found;
122        }
123
124        start += BLOCK;
125        end += BLOCK;
126    }
127}
128
129pub fn part2(input: &Input) -> usize {
130    let (target, mut start) = *input;
131    let mut end = start + BLOCK;
132    let mut houses = vec![0; BLOCK];
133
134    loop {
135        // Elves that visit exactly once (not including elf 1 anymore).
136        for i in 0..BLOCK {
137            houses[i] = 11 * (start + i) as u32;
138        }
139
140        // Elves that visit at most once.
141        for i in BLOCK..end / 2 {
142            let presents = 11 * i as u32;
143            let j = start.next_multiple_of(i) - start;
144
145            if j < BLOCK {
146                houses[j] += presents;
147            }
148        }
149
150        // All remaining elves. We can start higher than 2.
151        for i in start / 50..BLOCK {
152            let presents = 11 * i as u32;
153            let mut j = start.next_multiple_of(i) - start;
154            let mut remaining = 51 - start.div_ceil(i);
155
156            while j < BLOCK && remaining > 0 {
157                houses[j] += presents;
158                j += i;
159                remaining -= 1;
160            }
161        }
162
163        if let Some(found) = houses.iter().position(|&p| p >= target) {
164            break start + found;
165        }
166
167        start += BLOCK;
168        end += BLOCK;
169    }
170}
aoc/year2015/day20.rs

aoc/year2015/
day20.rs
