aoc/year2015/
day10.rs

1//! # Elves Look, Elves Say
2//!
3//! There is a trick to solve this problem in constant time and space. While this is not possible
4//! for any arbitrary sequence, in Advent of Code *we only need to solve for our given input*.
5//!
6//! Examining the input shows that it consists of one of Conway's
7//! [atomic elements](https://en.wikipedia.org/wiki/Look-and-say_sequence#Cosmological_decay).
8//! Each element breaks down into other elements that do not interact with each other. This means
9//! that we only need to track the *count* of each element, rather than deal with the sequence
10//! as a whole. Each step we replace the count of each element with its decay products. For example
11//! if we had five `Ni` then next step we would decay to five `Zn` and five `Co`.
12//!
13//! Computing the result is simply multiplying the number of each element by its length. There are
14//! 92 elements total so we can use a fixed-size array to store the decay chain information.
15//!
16//! It would be possible (but less fun) to precompute all possible 92 answers into a
17//! lookup table.
18use crate::util::hash::*;
19
20const ELEMENTS: &str = "\
2122 -> H -> H
2213112221133211322112211213322112 -> He -> Hf Pa H Ca Li
23312211322212221121123222112 -> Li -> He
24111312211312113221133211322112211213322112 -> Be -> Ge Ca Li
251321132122211322212221121123222112 -> B -> Be
263113112211322112211213322112 -> C -> B
27111312212221121123222112 -> N -> C
28132112211213322112 -> O -> N
2931121123222112 -> F -> O
30111213322112 -> Ne -> F
31123222112 -> Na -> Ne
323113322112 -> Mg -> Pm Na
331113222112 -> Al -> Mg
341322112 -> Si -> Al
35311311222112 -> P -> Ho Si
361113122112 -> S -> P
37132112 -> Cl -> S
383112 -> Ar -> Cl
391112 -> K -> Ar
4012 -> Ca -> K
413113112221133112 -> Sc -> Ho Pa H Ca Co
4211131221131112 -> Ti -> Sc
4313211312 -> V -> Ti
4431132 -> Cr -> V
45111311222112 -> Mn -> Cr Si
4613122112 -> Fe -> Mn
4732112 -> Co -> Fe
4811133112 -> Ni -> Zn Co
49131112 -> Cu -> Ni
50312 -> Zn -> Cu
5113221133122211332 -> Ga -> Eu Ca Ac H Ca Zn
5231131122211311122113222 -> Ge -> Ho Ga
5311131221131211322113322112 -> As -> Ge Na
5413211321222113222112 -> Se -> As
553113112211322112 -> Br -> Se
5611131221222112 -> Kr -> Br
571321122112 -> Rb -> Kr
583112112 -> Sr -> Rb
591112133 -> Y -> Sr U
6012322211331222113112211 -> Zr -> Y H Ca Tc
611113122113322113111221131221 -> Nb -> Er Zr
6213211322211312113211 -> Mo -> Nb
63311322113212221 -> Tc -> Mo
64132211331222113112211 -> Ru -> Eu Ca Tc
65311311222113111221131221 -> Rh -> Ho Ru
66111312211312113211 -> Pd -> Rh
67132113212221 -> Ag -> Pd
683113112211 -> Cd -> Ag
6911131221 -> In -> Cd
7013211 -> Sn -> In
713112221 -> Sb -> Pm Sn
721322113312211 -> Te -> Eu Ca Sb
73311311222113111221 -> I -> Ho Te
7411131221131211 -> Xe -> I
7513211321 -> Cs -> Xe
76311311 -> Ba -> Cs
7711131 -> La -> Ba
781321133112 -> Ce -> La H Ca Co
7931131112 -> Pr -> Ce
80111312 -> Nd -> Pr
81132 -> Pm -> Nd
82311332 -> Sm -> Pm Ca Zn
831113222 -> Eu -> Sm
8413221133112 -> Gd -> Eu Ca Co
853113112221131112 -> Tb -> Ho Gd
86111312211312 -> Dy -> Tb
871321132 -> Ho -> Dy
88311311222 -> Er -> Ho Pm
8911131221133112 -> Tm -> Er Ca Co
901321131112 -> Yb -> Tm
91311312 -> Lu -> Yb
9211132 -> Hf -> Lu
9313112221133211322112211213322113 -> Ta -> Hf Pa H Ca W
94312211322212221121123222113 -> W -> Ta
95111312211312113221133211322112211213322113 -> Re -> Ge Ca W
961321132122211322212221121123222113 -> Os -> Re
973113112211322112211213322113 -> Ir -> Os
98111312212221121123222113 -> Pt -> Ir
99132112211213322113 -> Au -> Pt
10031121123222113 -> Hg -> Au
101111213322113 -> Tl -> Hg
102123222113 -> Pb -> Tl
1033113322113 -> Bi -> Pm Pb
1041113222113 -> Po -> Bi
1051322113 -> At -> Po
106311311222113 -> Rn -> Ho At
1071113122113 -> Fr -> Rn
108132113 -> Ra -> Fr
1093113 -> Ac -> Ra
1101113 -> Th -> Ac
11113 -> Pa -> Th
1123 -> U -> Pa";
113
114type Result = (usize, usize);
115
116pub fn parse(input: &str) -> Result {
117    let elements: Vec<_> = ELEMENTS
118        .lines()
119        .map(|line| {
120            let (sequence, rest) = line.split_once(" -> ").unwrap();
121            let (name, decay) = rest.split_once(" -> ").unwrap();
122            (sequence, name, decay)
123        })
124        .collect();
125
126    // Map both sequence and element name to indices.
127    let indices: FastMap<_, _> = elements
128        .iter()
129        .enumerate()
130        .flat_map(|(i, &(sequence, name, _))| [(sequence, i), (name, i)])
131        .collect();
132
133    // Build list of decay chains.
134    let sizes: Vec<_> = elements.iter().map(|(sequence, ..)| sequence.len()).collect();
135    let decays: Vec<_> = elements
136        .iter()
137        .map(|&(_, _, decay)| decay.split_ascii_whitespace().map(|name| indices[name]).collect())
138        .collect();
139
140    // Each input is a single element.
141    let mut current = [0; 92];
142    current[indices[input.trim()]] = 1;
143
144    for _ in 0..40 {
145        current = step(&current, &decays);
146    }
147    let part1 = length(&current, &sizes);
148
149    for _ in 0..10 {
150        current = step(&current, &decays);
151    }
152    let part2 = length(&current, &sizes);
153
154    (part1, part2)
155}
156
157pub fn part1(input: &Result) -> usize {
158    input.0
159}
160
161pub fn part2(input: &Result) -> usize {
162    input.1
163}
164
165fn step(current: &[usize], decays: &[Vec<usize>]) -> [usize; 92] {
166    let mut next = [0; 92];
167
168    for (&count, decay) in current.iter().zip(decays) {
169        if count > 0 {
170            for &element in decay {
171                next[element] += count;
172            }
173        }
174    }
175
176    next
177}
178
179fn length(current: &[usize], sizes: &[usize]) -> usize {
180    current.iter().zip(sizes).map(|(c, s)| c * s).sum()
181}
aoc/year2015/day10.rs

aoc/year2015/
day10.rs
