aoc/year2016/
day04.rs

1//! # Security Through Obscurity
2//!
3//! We can quickly eliminate decoys without needing an expensive sort by checking that the
4//! frequency of checksum letters is non-increasing, letters of equal frequency are in alphabetical
5//! order and that there are no intervening letters in between any two frequencies.
6//!
7//! In part two as the [Caesar cipher](https://en.wikipedia.org/wiki/Caesar_cipher) does
8//! not change the length of words, we can also eliminate most candidates with a simple length
9//! check and only decrypt a much smaller number of strings.
10use crate::util::parse::*;
11
12pub struct Room<'a> {
13    name: &'a str,
14    sector_id: u32,
15}
16
17pub fn parse(input: &str) -> Vec<Room<'_>> {
18    let mut valid = Vec::new();
19
20    for line in input.lines() {
21        // The sector id and checksum are fixed size leaving whatever is left over as the name.
22        let size = line.len();
23        let name = &line[..size - 11];
24        let checksum = &line.as_bytes()[size - 6..size - 1];
25
26        // Count the frequency of each digit, the frequency of each frequency `fof` and the
27        // highest total frequency.
28        let mut freq = [0; 26];
29        let mut fof = [0; 26];
30        let mut highest = 0;
31
32        for b in name.bytes() {
33            if b != b'-' {
34                let index = to_index(b);
35                let current = freq[index];
36                let next = freq[index] + 1;
37
38                freq[index] = next;
39                fof[current] -= 1;
40                fof[next] += 1;
41
42                highest = highest.max(next);
43            }
44        }
45
46        // Filter real rooms vs decoys.
47        if freq[to_index(checksum[0])] == highest && rules(checksum, &freq, &mut fof) {
48            let sector_id = (&line[size - 10..size - 7]).unsigned();
49            valid.push(Room { name, sector_id });
50        }
51    }
52
53    valid
54}
55
56pub fn part1(input: &[Room<'_>]) -> u32 {
57    input.iter().map(|room| room.sector_id).sum()
58}
59
60pub fn part2(input: &[Room<'_>]) -> u32 {
61    for &Room { name, sector_id } in input {
62        let bytes = name.as_bytes();
63
64        // Quickly eliminate most rooms as the length of words doesn't change.
65        if bytes.len() == 24 && bytes[9] == b'-' && bytes[16] == b'-' {
66            let mut buffer = String::with_capacity(24);
67
68            // Decrypt potential candidates.
69            for b in name.bytes() {
70                if b == b'-' {
71                    buffer.push(' ');
72                } else {
73                    let rotate = (sector_id % 26) as u8;
74                    let decrypted = (b - b'a' + rotate) % 26 + b'a';
75                    buffer.push(decrypted as char);
76                }
77            }
78
79            if buffer == "northpole object storage" {
80                return sector_id;
81            }
82        }
83    }
84
85    unreachable!()
86}
87
88/// Check each pair making sure that the frequency is non-increasing and that there are
89/// no letters in between (`fof` should be zero for all intervening frequencies).
90/// If the frequency is equal then also make sure letters are in alphabetical order.
91fn rules(checksum: &[u8], freq: &[usize], fof: &mut [i32]) -> bool {
92    checksum.windows(2).all(|w| {
93        let end = freq[to_index(w[0])];
94        let start = freq[to_index(w[1])];
95        fof[end] -= 1;
96        !(start > end
97            || (start == end && w[1] <= w[0])
98            || (start + 1..end + 1).any(|i| fof[i] != 0))
99    })
100}
101
102fn to_index(b: u8) -> usize {
103    (b - b'a') as usize
104}
aoc/year2016/day04.rs

aoc/year2016/
day04.rs
