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    input
19        .lines()
20        .filter_map(|line| {
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 = current + 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            let valid = freq[to_index(checksum[0])] == highest && rules(checksum, &freq, &mut fof);
48            valid.then(|| Room { name, sector_id: line[size - 10..size - 7].unsigned() })
49        })
50        .collect()
51}
52
53pub fn part1(input: &[Room<'_>]) -> u32 {
54    input.iter().map(|room| room.sector_id).sum()
55}
56
57pub fn part2(input: &[Room<'_>]) -> u32 {
58    let target = b"northpole object storage";
59
60    for &Room { name, sector_id } in input {
61        let bytes = name.as_bytes();
62
63        // Quickly eliminate most rooms as the length of words doesn't change.
64        if bytes.len() == target.len() && bytes[9] == b'-' && bytes[16] == b'-' {
65            let rotate = (sector_id % 26) as u8;
66            let matches = bytes.iter().zip(target).all(|(&b, &t)| {
67                t == if b == b'-' { b' ' } else { (b - b'a' + rotate) % 26 + b'a' }
68            });
69            if matches {
70                return sector_id;
71            }
72        }
73    }
74
75    unreachable!()
76}
77
78/// Check each pair making sure that the frequency is non-increasing and that there are
79/// no letters in between (`fof` should be zero for all intervening frequencies).
80/// If the frequency is equal then also make sure letters are in alphabetical order.
81fn rules(checksum: &[u8], freq: &[usize], fof: &mut [i32]) -> bool {
82    checksum.array_windows().all(|&[a, b]| {
83        let end = freq[to_index(a)];
84        let start = freq[to_index(b)];
85        fof[end] -= 1;
86        !(start > end || (start == end && b <= a) || (start + 1..=end).any(|i| fof[i] != 0))
87    })
88}
89
90fn to_index(b: u8) -> usize {
91    usize::from(b - b'a')
92}
aoc/year2016/day04.rs

aoc/year2016/
day04.rs
