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.
15use crate::util::hash::*;
16
17const ELEMENTS: &str = "\
1822 -> H -> H
1913112221133211322112211213322112 -> He -> Hf Pa H Ca Li
20312211322212221121123222112 -> Li -> He
21111312211312113221133211322112211213322112 -> Be -> Ge Ca Li
221321132122211322212221121123222112 -> B -> Be
233113112211322112211213322112 -> C -> B
24111312212221121123222112 -> N -> C
25132112211213322112 -> O -> N
2631121123222112 -> F -> O
27111213322112 -> Ne -> F
28123222112 -> Na -> Ne
293113322112 -> Mg -> Pm Na
301113222112 -> Al -> Mg
311322112 -> Si -> Al
32311311222112 -> P -> Ho Si
331113122112 -> S -> P
34132112 -> Cl -> S
353112 -> Ar -> Cl
361112 -> K -> Ar
3712 -> Ca -> K
383113112221133112 -> Sc -> Ho Pa H Ca Co
3911131221131112 -> Ti -> Sc
4013211312 -> V -> Ti
4131132 -> Cr -> V
42111311222112 -> Mn -> Cr Si
4313122112 -> Fe -> Mn
4432112 -> Co -> Fe
4511133112 -> Ni -> Zn Co
46131112 -> Cu -> Ni
47312 -> Zn -> Cu
4813221133122211332 -> Ga -> Eu Ca Ac H Ca Zn
4931131122211311122113222 -> Ge -> Ho Ga
5011131221131211322113322112 -> As -> Ge Na
5113211321222113222112 -> Se -> As
523113112211322112 -> Br -> Se
5311131221222112 -> Kr -> Br
541321122112 -> Rb -> Kr
553112112 -> Sr -> Rb
561112133 -> Y -> Sr U
5712322211331222113112211 -> Zr -> Y H Ca Tc
581113122113322113111221131221 -> Nb -> Er Zr
5913211322211312113211 -> Mo -> Nb
60311322113212221 -> Tc -> Mo
61132211331222113112211 -> Ru -> Eu Ca Tc
62311311222113111221131221 -> Rh -> Ho Ru
63111312211312113211 -> Pd -> Rh
64132113212221 -> Ag -> Pd
653113112211 -> Cd -> Ag
6611131221 -> In -> Cd
6713211 -> Sn -> In
683112221 -> Sb -> Pm Sn
691322113312211 -> Te -> Eu Ca Sb
70311311222113111221 -> I -> Ho Te
7111131221131211 -> Xe -> I
7213211321 -> Cs -> Xe
73311311 -> Ba -> Cs
7411131 -> La -> Ba
751321133112 -> Ce -> La H Ca Co
7631131112 -> Pr -> Ce
77111312 -> Nd -> Pr
78132 -> Pm -> Nd
79311332 -> Sm -> Pm Ca Zn
801113222 -> Eu -> Sm
8113221133112 -> Gd -> Eu Ca Co
823113112221131112 -> Tb -> Ho Gd
83111312211312 -> Dy -> Tb
841321132 -> Ho -> Dy
85311311222 -> Er -> Ho Pm
8611131221133112 -> Tm -> Er Ca Co
871321131112 -> Yb -> Tm
88311312 -> Lu -> Yb
8911132 -> Hf -> Lu
9013112221133211322112211213322113 -> Ta -> Hf Pa H Ca W
91312211322212221121123222113 -> W -> Ta
92111312211312113221133211322112211213322113 -> Re -> Ge Ca W
931321132122211322212221121123222113 -> Os -> Re
943113112211322112211213322113 -> Ir -> Os
95111312212221121123222113 -> Pt -> Ir
96132112211213322113 -> Au -> Pt
9731121123222113 -> Hg -> Au
98111213322113 -> Tl -> Hg
99123222113 -> Pb -> Tl
1003113322113 -> Bi -> Pm Pb
1011113222113 -> Po -> Bi
1021322113 -> At -> Po
103311311222113 -> Rn -> Ho At
1041113122113 -> Fr -> Rn
105132113 -> Ra -> Fr
1063113 -> Ac -> Ra
1071113 -> Th -> Ac
10813 -> Pa -> Th
1093 -> U -> Pa";
110
111type Result = (usize, usize);
112
113pub fn parse(input: &str) -> Result {
114    let elements: Vec<Vec<_>> =
115        ELEMENTS.lines().map(|line| line.split_ascii_whitespace().collect()).collect();
116    let mut indices = FastMap::with_capacity(92);
117
118    for (i, tokens) in elements.iter().enumerate() {
119        indices.insert(tokens[2], i);
120    }
121
122    let mut sequence = [""; 92];
123    let mut decays = [[None; 6]; 92];
124
125    for (i, tokens) in elements.iter().enumerate() {
126        sequence[i] = tokens[0];
127        for (j, &token) in tokens.iter().skip(4).enumerate() {
128            decays[i][j] = Some(indices[token]);
129        }
130    }
131
132    let mut current = initial_state(input, &sequence);
133    for _ in 0..40 {
134        current = step(&current, &decays);
135    }
136
137    let result1 = length(&current, &sequence);
138    for _ in 0..10 {
139        current = step(&current, &decays);
140    }
141
142    let result2 = length(&current, &sequence);
143    (result1, result2)
144}
145
146pub fn part1(input: &Result) -> usize {
147    input.0
148}
149
150pub fn part2(input: &Result) -> usize {
151    input.1
152}
153
154fn initial_state(input: &str, sequence: &[&str]) -> [usize; 92] {
155    let input = input.trim();
156    let start = sequence.iter().position(|&s| s == input).unwrap();
157
158    let mut current = [0; 92];
159    current[start] += 1;
160    current
161}
162
163fn step(current: &[usize; 92], decays: &[[Option<usize>; 6]; 92]) -> [usize; 92] {
164    let mut next = [0; 92];
165
166    for i in 0..92 {
167        let c = current[i];
168        if c > 0 {
169            let mut iter = decays[i].iter();
170            while let Some(Some(index)) = iter.next() {
171                next[*index] += c;
172            }
173        }
174    }
175
176    next
177}
178
179fn length(current: &[usize; 92], sequence: &[&str; 92]) -> usize {
180    current.iter().zip(sequence.iter()).map(|(c, s)| c * s.len()).sum()
181}
aoc/year2015/day10.rs

aoc/year2015/
day10.rs
