year2015/
day10.rs

1use utils::prelude::*;
2
3/// Look-and-say sequence.
4///
5/// See <https://en.wikipedia.org/wiki/Look-and-say_sequence#Cosmological_decay>. The input is an
6/// "atomic element" and each atomic element always follows a fixed sequence, so each iteration only
7/// needs to calculate how many of each element there are.
8#[derive(Clone, Debug)]
9pub struct Day10 {
10    part1: u32,
11    part2: u32,
12}
13
14const ATOMIC_ELEMENTS: [&str; 92] = [
15    "22",
16    "13112221133211322112211213322112",
17    "312211322212221121123222112",
18    "111312211312113221133211322112211213322112",
19    "1321132122211322212221121123222112",
20    "3113112211322112211213322112",
21    "111312212221121123222112",
22    "132112211213322112",
23    "31121123222112",
24    "111213322112",
25    "123222112",
26    "3113322112",
27    "1113222112",
28    "1322112",
29    "311311222112",
30    "1113122112",
31    "132112",
32    "3112",
33    "1112",
34    "12",
35    "3113112221133112",
36    "11131221131112",
37    "13211312",
38    "31132",
39    "111311222112",
40    "13122112",
41    "32112",
42    "11133112",
43    "131112",
44    "312",
45    "13221133122211332",
46    "31131122211311122113222",
47    "11131221131211322113322112",
48    "13211321222113222112",
49    "3113112211322112",
50    "11131221222112",
51    "1321122112",
52    "3112112",
53    "1112133",
54    "12322211331222113112211",
55    "1113122113322113111221131221",
56    "13211322211312113211",
57    "311322113212221",
58    "132211331222113112211",
59    "311311222113111221131221",
60    "111312211312113211",
61    "132113212221",
62    "3113112211",
63    "11131221",
64    "13211",
65    "3112221",
66    "1322113312211",
67    "311311222113111221",
68    "11131221131211",
69    "13211321",
70    "311311",
71    "11131",
72    "1321133112",
73    "31131112",
74    "111312",
75    "132",
76    "311332",
77    "1113222",
78    "13221133112",
79    "3113112221131112",
80    "111312211312",
81    "1321132",
82    "311311222",
83    "11131221133112",
84    "1321131112",
85    "311312",
86    "11132",
87    "13112221133211322112211213322113",
88    "312211322212221121123222113",
89    "111312211312113221133211322112211213322113",
90    "1321132122211322212221121123222113",
91    "3113112211322112211213322113",
92    "111312212221121123222113",
93    "132112211213322113",
94    "31121123222113",
95    "111213322113",
96    "123222113",
97    "3113322113",
98    "1113222113",
99    "1322113",
100    "311311222113",
101    "1113122113",
102    "132113",
103    "3113",
104    "1113",
105    "13",
106    "3",
107];
108
109impl Day10 {
110    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
111        let index = ATOMIC_ELEMENTS
112            .iter()
113            .position(|&x| x == input)
114            .ok_or_else(|| InputError::new(input, 0, "expected atomic element"))?;
115
116        let mut decays = [0u32; 92];
117        decays[index] = 1;
118
119        for _ in 0..40 {
120            decays = Self::step(&decays);
121        }
122        let part1 = Self::length(&decays);
123
124        for _ in 0..10 {
125            decays = Self::step(&decays);
126        }
127        let part2 = Self::length(&decays);
128
129        Ok(Self { part1, part2 })
130    }
131
132    #[must_use]
133    pub fn part1(&self) -> u32 {
134        self.part1
135    }
136
137    #[must_use]
138    pub fn part2(&self) -> u32 {
139        self.part2
140    }
141
142    #[rustfmt::skip]
143    fn step(d: &[u32; 92]) -> [u32; 92] {
144        // Generated from Wikipedia's table
145        [
146            d[0] + d[1] + d[20] + d[30] + d[39] + d[57] + d[72],
147            d[2],
148            d[1] + d[3],
149            d[4],
150            d[5],
151            d[6],
152            d[7],
153            d[8],
154            d[9],
155            d[10],
156            d[11] + d[32],
157            d[12],
158            d[13],
159            d[14] + d[24],
160            d[15],
161            d[16],
162            d[17],
163            d[18],
164            d[19],
165            d[1] + d[3] + d[20] + d[30] + d[30] + d[39] + d[43] + d[51] + d[57] + d[61] + d[63] + d[68] + d[72] + d[74],
166            d[21],
167            d[22],
168            d[23],
169            d[24],
170            d[25],
171            d[26],
172            d[20] + d[27] + d[57] + d[63] + d[68],
173            d[28],
174            d[29],
175            d[27] + d[30] + d[61],
176            d[31],
177            d[3] + d[32] + d[74],
178            d[33],
179            d[34],
180            d[35],
181            d[36],
182            d[37],
183            d[38],
184            d[39],
185            d[40],
186            d[41],
187            d[42],
188            d[39] + d[43],
189            d[44],
190            d[45],
191            d[46],
192            d[47],
193            d[48],
194            d[49],
195            d[50],
196            d[51],
197            d[52],
198            d[53],
199            d[54],
200            d[55],
201            d[56],
202            d[57],
203            d[58],
204            d[59],
205            d[60],
206            d[11] + d[50] + d[61] + d[67] + d[82],
207            d[62],
208            d[30] + d[43] + d[51] + d[63],
209            d[64],
210            d[65],
211            d[66],
212            d[14] + d[20] + d[31] + d[44] + d[52] + d[64] + d[67] + d[85],
213            d[40] + d[68],
214            d[69],
215            d[70],
216            d[71],
217            d[1] + d[72],
218            d[73],
219            d[72] + d[74],
220            d[75],
221            d[76],
222            d[77],
223            d[78],
224            d[79],
225            d[80],
226            d[81],
227            d[82],
228            d[83],
229            d[84],
230            d[85],
231            d[86],
232            d[87],
233            d[88],
234            d[30] + d[89],
235            d[90],
236            d[1] + d[20] + d[72] + d[91],
237            d[38],
238        ]
239    }
240
241    fn length(d: &[u32; 92]) -> u32 {
242        d.iter()
243            .zip(ATOMIC_ELEMENTS)
244            .map(|(&count, s)| count * s.len() as u32)
245            .sum()
246    }
247}
248
249examples!(Day10 -> (u32, u32) [
250    // Example generated from https://oeis.org/A006715
251    {input: "3", part1: 95798, part2: 1355550},
252]);
year2015/day10.rs

year2015/
day10.rs
