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//! look up 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<Vec<_>> =
118        ELEMENTS.lines().map(|line| line.split_ascii_whitespace().collect()).collect();
119    let mut indices = FastMap::with_capacity(92 * 2);
120
121    // Map both sequence and element name to indices.
122    for (i, tokens) in elements.iter().enumerate() {
123        indices.insert(tokens[0], i);
124        indices.insert(tokens[2], i);
125    }
126
127    // Build list of decay chains.
128    let sizes: Vec<_> = elements.iter().map(|e| e[0].len()).collect();
129    let decays: Vec<Vec<_>> =
130        elements.iter().map(|e| e[4..].iter().map(|t| indices[t]).collect()).collect();
131
132    // Each input is a single element.
133    let mut current = [0; 92];
134    current[indices[input.trim()]] = 1;
135
136    for _ in 0..40 {
137        current = step(&current, &decays);
138    }
139    let part1 = length(&current, &sizes);
140
141    for _ in 0..10 {
142        current = step(&current, &decays);
143    }
144    let part2 = length(&current, &sizes);
145
146    (part1, part2)
147}
148
149pub fn part1(input: &Result) -> usize {
150    input.0
151}
152
153pub fn part2(input: &Result) -> usize {
154    input.1
155}
156
157fn step(current: &[usize], decays: &[Vec<usize>]) -> [usize; 92] {
158    let mut next = [0; 92];
159
160    for (i, &count) in current.iter().enumerate() {
161        if count > 0 {
162            for &element in &decays[i] {
163                next[element] += count;
164            }
165        }
166    }
167
168    next
169}
170
171fn length(current: &[usize], sizes: &[usize]) -> usize {
172    current.iter().zip(sizes.iter()).map(|(c, s)| c * s).sum()
173}
aoc/year2015/day10.rs

aoc/year2015/
day10.rs
