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 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    let target = b"northpole object storage";
62
63    for &Room { name, sector_id } in input {
64        let bytes = name.as_bytes();
65
66        // Quickly eliminate most rooms as the length of words doesn't change.
67        if bytes.len() == target.len() && bytes[9] == b'-' && bytes[16] == b'-' {
68            let rotate = (sector_id % 26) as u8;
69            let matches = bytes.iter().zip(target).all(|(&b, &t)| {
70                t == if b == b'-' { b' ' } else { (b - b'a' + rotate) % 26 + b'a' }
71            });
72            if matches {
73                return sector_id;
74            }
75        }
76    }
77
78    unreachable!()
79}
80
81/// Check each pair making sure that the frequency is non-increasing and that there are
82/// no letters in between (`fof` should be zero for all intervening frequencies).
83/// If the frequency is equal then also make sure letters are in alphabetical order.
84fn rules(checksum: &[u8], freq: &[usize], fof: &mut [i32]) -> bool {
85    checksum.windows(2).all(|w| {
86        let end = freq[to_index(w[0])];
87        let start = freq[to_index(w[1])];
88        fof[end] -= 1;
89        !(start > end
90            || (start == end && w[1] <= w[0])
91            || (start + 1..end + 1).any(|i| fof[i] != 0))
92    })
93}
94
95fn to_index(b: u8) -> usize {
96    (b - b'a') as usize
97}
aoc/year2016/day04.rs

aoc/year2016/
day04.rs
