thecoded.prof
Advent of Code
1use atoi_simd::parse as parse_u64;
2
3pub fn main() -> anyhow::Result<()> {
4 crate::run("Gift Shop", "inputs/day2.txt", parse, part_a, part_b)
5}
6
7pub fn parse(input: &[u8]) -> Vec<u64> {
8 let mut out = Vec::new();
9 let mut start = 0;
10
11 while start < input.len() {
12 let rest = &input[start..];
13 let end = memchr::memchr2(b',', b'\n', rest).map_or(input.len(), |i| start + i);
14 let range = &input[start..end];
15
16 let dash = memchr::memchr(b'-', range).expect("invalid input: missing '-'");
17
18 let min = parse_u64::<u64>(&range[..dash]).expect("invalid input: invalid min");
19 let max = parse_u64::<u64>(&range[dash + 1..]).expect("invalid input: invalid max");
20
21 out.extend(min..=max);
22 start = if end == input.len() { end } else { end + 1 };
23 }
24
25 out
26}
27
28pub fn part_a(input: Vec<u64>) -> usize {
29 input.iter().fold(0, |acc, x| {
30 acc + if is_valid_id_a(x.clone()) {
31 0
32 } else {
33 *x as usize
34 }
35 })
36}
37
38fn is_valid_id_a(id: u64) -> bool {
39 // invalid ID's are identifiable due to them being made up from some sequences being repeated
40 // eg: 11 -> [1, 1] invalid
41 // eg: 123123 -> [123, 123] invalid
42 // eg: 123456 -> [123456] valid
43 let digits = id.ilog10() + 1;
44 if digits % 2 == 1 {
45 return true;
46 }
47
48 let div = 10u64.pow(digits / 2);
49
50 let left = id / div;
51 let right = id % div;
52 left != right
53}
54
55fn is_valid_id_b(mut id: u64) -> bool {
56 // invalid ID's are identifiable due to them being made up from some sequences being repeated
57 // eg: 11 -> [1, 1] invalid
58 // eg: 123123 -> [123, 123] invalid
59 // eg: 121212 -> [12, 12, 12] invalid
60 // eg: 111 -> [1, 1, 1] invalid
61 // eg: 123456 -> [123456] valid
62 let mut digits = [0u8; 10];
63 let mut len = 0;
64
65 if id == 0 {
66 digits[0] = b'0';
67 len = 1;
68 } else {
69 while id > 0 {
70 digits[len] = b'0' + (id % 10) as u8;
71 len += 1;
72 id /= 10;
73 }
74 digits[..len].reverse();
75 }
76
77 if len < 2 {
78 return true;
79 }
80
81 let mut pi = [0usize; 10];
82 for i in 1..len {
83 let mut j = pi[i - 1];
84 while j > 0 && digits[i] != digits[j] {
85 j = pi[j - 1];
86 }
87 if digits[i] == digits[j] {
88 j += 1;
89 }
90 pi[i] = j;
91 }
92
93 let smallest_period = len - pi[len - 1];
94 !(smallest_period < len && len % smallest_period == 0)
95}
96
97pub fn part_b(input: Vec<u64>) -> usize {
98 input.iter().fold(0, |acc, x| {
99 acc + if is_valid_id_b(x.clone()) {
100 0usize
101 } else {
102 *x as usize
103 }
104 })
105}