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//! [highly abundant number](https://en.wikipedia.org/wiki/Highly_abundant_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//! It is easy enough to pre-generate a list of highly-abundant numbers, or
21//! even just grab one from [OEIS A002093](https://oeis.org/A002093/b002093.txt).
22//! Inspecting that list shows that between house numbers `540_540` and `1_201_200`,
23//! there are only 28 candidates.  In turn, it is easy to precompute their
24//! sum of divisors, turning this into a LUT (look-up table) on the target,
25//! sufficient to cover the range of all known puzzle inputs (30-40 million).
26//!
27//! ## Part Two
28//!
29//! As with part one, an offline brute force search showed that for all house numbers between
30//! `540_540` and `1_201_200`, there are only 46 record-holders; just use another LUT.
31use crate::util::parse::*;
32
33struct Mapping {
34    sum: u32,
35    house: u32,
36}
37
38pub fn parse(input: &str) -> u32 {
39    input.unsigned()
40}
41
42pub fn part1(input: &u32) -> u32 {
43    #[expect(clippy::decimal_literal_representation)]
44    const MAPPING: [Mapping; 28] = [
45        Mapping { sum: 22_579_200, house: 540_540 },
46        Mapping { sum: 24_373_440, house: 554_400 },
47        Mapping { sum: 24_624_000, house: 582_120 },
48        Mapping { sum: 25_206_720, house: 589_680 },
49        Mapping { sum: 25_296_000, house: 604_800 },
50        Mapping { sum: 25_727_520, house: 609_840 },
51        Mapping { sum: 26_208_000, house: 622_440 },
52        Mapping { sum: 26_956_800, house: 637_560 },
53        Mapping { sum: 28_435_680, house: 655_200 },
54        Mapping { sum: 29_260_800, house: 665_280 },
55        Mapping { sum: 29_760_000, house: 718_200 },
56        Mapping { sum: 32_497_920, house: 720_720 },
57        Mapping { sum: 33_611_760, house: 776_160 },
58        Mapping { sum: 34_137_600, house: 786_240 },
59        Mapping { sum: 36_902_400, house: 831_600 },
60        Mapping { sum: 38_263_680, house: 887_040 },
61        Mapping { sum: 38_304_000, house: 914_760 },
62        Mapping { sum: 39_213_720, house: 917_280 },
63        Mapping { sum: 41_783_040, house: 942_480 },
64        Mapping { sum: 43_052_800, house: 982_800 },
65        Mapping { sum: 43_908_480, house: 997_920 },
66        Mapping { sum: 44_640_960, house: 1_048_320 },
67        Mapping { sum: 46_425_600, house: 1_053_360 },
68        Mapping { sum: 48_384_000, house: 1_081_080 },
69        Mapping { sum: 49_133_760, house: 1_108_800 },
70        Mapping { sum: 50_889_600, house: 1_164_240 },
71        Mapping { sum: 51_226_560, house: 1_179_360 },
72        Mapping { sum: 51_663_360, house: 1_201_200 },
73    ];
74    lookup(&MAPPING, *input)
75}
76
77pub fn part2(input: &u32) -> u32 {
78    #[expect(clippy::decimal_literal_representation)]
79    const MAPPING: [Mapping; 46] = [
80        Mapping { sum: 22_103_774, house: 540_540 },
81        Mapping { sum: 22_113_630, house: 544_320 },
82        Mapping { sum: 23_818_179, house: 554_400 },
83        Mapping { sum: 23_841_125, house: 574_560 },
84        Mapping { sum: 23_909_886, house: 579_600 },
85        Mapping { sum: 24_259_015, house: 582_120 },
86        Mapping { sum: 24_668_490, house: 589_680 },
87        Mapping { sum: 24_969_868, house: 604_800 },
88        Mapping { sum: 25_587_870, house: 609_840 },
89        Mapping { sum: 25_755_345, house: 622_440 },
90        Mapping { sum: 25_941_795, house: 635_040 },
91        Mapping { sum: 26_623_905, house: 637_560 },
92        Mapping { sum: 27_800_157, house: 655_200 },
93        Mapping { sum: 28_413_770, house: 665_280 },
94        Mapping { sum: 28_899_255, house: 693_000 },
95        Mapping { sum: 29_002_446, house: 705_600 },
96        Mapping { sum: 29_370_187, house: 718_200 },
97        Mapping { sum: 31_358_250, house: 720_720 },
98        Mapping { sum: 31_476_060, house: 766_080 },
99        Mapping { sum: 31_811_010, house: 771_120 },
100        Mapping { sum: 33_007_425, house: 776_160 },
101        Mapping { sum: 33_161_590, house: 786_240 },
102        Mapping { sum: 33_297_495, house: 803_880 },
103        Mapping { sum: 33_717_915, house: 819_000 },
104        Mapping { sum: 35_780_206, house: 831_600 },
105        Mapping { sum: 35_856_513, house: 856_800 },
106        Mapping { sum: 35_960_155, house: 876_960 },
107        Mapping { sum: 36_191_925, house: 884_520 },
108        Mapping { sum: 37_523_640, house: 887_040 },
109        Mapping { sum: 37_915_955, house: 914_760 },
110        Mapping { sum: 38_520_735, house: 917_280 },
111        Mapping { sum: 40_459_650, house: 942_480 },
112        Mapping { sum: 40_676_757, house: 970_200 },
113        Mapping { sum: 41_762_798, house: 982_800 },
114        Mapping { sum: 42_620_655, house: 997_920 },
115        Mapping { sum: 42_768_110, house: 1_028_160 },
116        Mapping { sum: 42_774_270, house: 1_043_280 },
117        Mapping { sum: 43_788_360, house: 1_048_320 },
118        Mapping { sum: 45_111_990, house: 1_053_360 },
119        Mapping { sum: 46_486_825, house: 1_081_080 },
120        Mapping { sum: 47_636_358, house: 1_108_800 },
121        Mapping { sum: 47_682_250, house: 1_149_120 },
122        Mapping { sum: 48_218_247, house: 1_159_200 },
123        Mapping { sum: 49_585_250, house: 1_164_240 },
124        Mapping { sum: 49_742_385, house: 1_179_360 },
125        Mapping { sum: 50_193_682, house: 1_201_200 },
126    ];
127    lookup(&MAPPING, *input)
128}
129
130fn lookup(data: &[Mapping], target: u32) -> u32 {
131    let idx = data.partition_point(|entry| entry.sum < target);
132    data[idx].house
133}
aoc/year2015/day20.rs

aoc/year2015/
day20.rs
