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    let to_index = |b: u8| (b - b'a') as usize;
20
21    'outer: for line in input.lines() {
22        // The sector id and checksum are fixed size leaving whatever is left over as the name.
23        let size = line.len();
24        let name = &line[..size - 11];
25        let sector_id = (&line[size - 10..size - 7]).unsigned();
26        let checksum = &line.as_bytes()[size - 6..size - 1];
27
28        // Count the frequency of each digit, the frequency of each frequency `fof` and the
29        // highest total frequency.
30        let mut freq = [0; 26];
31        let mut fof = [0; 64];
32        let mut highest = 0;
33
34        for b in name.bytes() {
35            if b != b'-' {
36                let index = to_index(b);
37                let current = freq[index];
38                let next = freq[index] + 1;
39
40                freq[index] = next;
41                fof[current] -= 1;
42                fof[next] += 1;
43
44                highest = highest.max(next);
45            }
46        }
47
48        // Initial check.
49        if freq[to_index(checksum[0])] != highest {
50            continue;
51        }
52
53        // Check each pair making sure that the frequency is non-increasing and that there are
54        // no letters in between (`fof` should be zero for all intervening letters).
55        // If the frequency is equal then also make sure letters are in alphabetical order.
56        for w in checksum.windows(2) {
57            let end = freq[to_index(w[0])];
58            let start = freq[to_index(w[1])];
59
60            if start > end || (start == end && w[1] <= w[0]) {
61                continue 'outer;
62            }
63
64            if (start + 1..end).any(|i| fof[i] != 0) {
65                continue 'outer;
66            }
67        }
68
69        valid.push(Room { name, sector_id });
70    }
71
72    valid
73}
74
75pub fn part1(input: &[Room<'_>]) -> u32 {
76    input.iter().map(|room| room.sector_id).sum()
77}
78
79pub fn part2(input: &[Room<'_>]) -> u32 {
80    for &Room { name, sector_id } in input {
81        let bytes = name.as_bytes();
82
83        // Quickly eliminate most rooms as the length of words doesn't change.
84        if bytes.len() == 24 && bytes[9] == b'-' && bytes[16] == b'-' {
85            let mut buffer = String::with_capacity(24);
86
87            // Decrypt potential candidates.
88            for b in name.bytes() {
89                if b == b'-' {
90                    buffer.push(' ');
91                } else {
92                    let rotate = (sector_id % 26) as u8;
93                    let decrypted = (b - b'a' + rotate) % 26 + b'a';
94                    buffer.push(decrypted as char);
95                }
96            }
97
98            if buffer == "northpole object storage" {
99                return sector_id;
100            }
101        }
102    }
103
104    unreachable!()
105}
aoc/year2016/day04.rs

aoc/year2016/
day04.rs
