year2016/
day20.rs

1use utils::prelude::*;
2
3/// Finding numbers outside a list of ranges.
4#[derive(Clone, Debug)]
5pub struct Day20 {
6    ranges: Vec<(u32, u32)>,
7}
8
9impl Day20 {
10    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
11        let mut ranges = parser::u32()
12            .then(parser::u32().with_prefix("-"))
13            .map_res(|(min, max)| {
14                if min <= max {
15                    Ok((min, max))
16                } else {
17                    Err("end value cannot be less than start")
18                }
19            })
20            .parse_lines(input)?;
21        ranges.sort_unstable();
22        Ok(Self { ranges })
23    }
24
25    #[must_use]
26    pub fn part1(&self) -> u32 {
27        let mut ip = 0;
28        for &(start, end) in &self.ranges {
29            if ip < start {
30                break;
31            }
32            if end >= ip {
33                ip = end.checked_add(1).expect("no allowed IPs");
34            }
35        }
36        ip
37    }
38
39    #[must_use]
40    pub fn part2(&self) -> u64 {
41        let mut allowed = 0;
42        let mut ip = 0;
43        for &(start, end) in &self.ranges {
44            if ip < start {
45                allowed += u64::from(start - ip);
46            }
47
48            if end >= ip {
49                let Some(next_ip) = end.checked_add(1) else {
50                    // Range end is u32::MAX, no allowed IPs after final range to add
51                    return allowed;
52                };
53                ip = next_ip;
54            }
55        }
56
57        // Add on IPs after the end of the final range
58        allowed + u64::from(u32::MAX - ip) + 1
59    }
60}
61
62examples!(Day20 -> (u32, u64) [
63    // Custom examples
64    {
65        input: "0-409354575\n\
66            1005171202-1792978424\n\
67            2396795992-4166223847\n\
68            361276686-3509736453\n\
69            2979588951-3460902073",
70        part1: 4166223848,
71        part2: 128743448
72    },
73    {
74        input: "",
75        part1: 0,
76        part2: 4294967296,
77    },
78    {
79        input: "0-0",
80        part1: 1,
81        part2: 4294967295,
82    },
83    {
84        input: "4294967295-4294967295",
85        part1: 0,
86        part2: 4294967295,
87    },
88    {
89        input: "0-4294967295",
90        part2: 0,
91    },
92]);