advent_of_code/year2021/
day03.rs

1use crate::input::Input;
2
3/// Constructs a u16 with the lowest n bits set.
4///
5/// Does not work for n == 0.
6fn set_lowest_bits(n: u8) -> u16 {
7    u16::MAX >> (u16::BITS as u16 - u16::from(n))
8}
9
10fn is_bit_mostly_set(numbers: &[u16], bit_idx: usize) -> bool {
11    numbers.iter().fold(0, |acc, x| {
12        acc + if x & (1 << bit_idx) == 0 { -1 } else { 1 }
13    }) >= 0
14}
15
16fn keep_one_according_to_bitset_criteria(
17    candidates: &mut [u16],
18    num_bits: usize,
19    criteria_wants_most: bool,
20) -> Result<u16, String> {
21    let mut num_candidates = candidates.len();
22    for current_bit_idx in (0..num_bits).rev() {
23        let mostly_set = is_bit_mostly_set(&candidates[0..num_candidates], current_bit_idx);
24        let mut current_candidate_idx = 0;
25        while current_candidate_idx < num_candidates {
26            let is_bit_set = (candidates[current_candidate_idx] & (1 << current_bit_idx)) != 0;
27            if (is_bit_set == mostly_set) == criteria_wants_most {
28                current_candidate_idx += 1;
29            } else {
30                num_candidates -= 1;
31                candidates.swap(current_candidate_idx, num_candidates);
32            }
33        }
34        if num_candidates == 1 {
35            return Ok(candidates[0]);
36        }
37    }
38
39    Err("Bit criteria did not result in single number".to_string())
40}
41
42pub fn solve(input: &Input) -> Result<u32, String> {
43    const MAX_BITS: usize = u16::BITS as usize;
44
45    let num_bits = input.text.lines().next().map(str::len).unwrap_or_default();
46    if num_bits == 0 || num_bits > MAX_BITS {
47        return Err(format!(
48            "Invalid number of bits - must be between 1 and {MAX_BITS}"
49        ));
50    }
51
52    if input.is_part_one() {
53        let set_bits_at_position = &mut [0; 16][0..num_bits];
54        for line in input.text.lines() {
55            if line.len() != num_bits {
56                return Err("All lines does not have equal length".to_string());
57            }
58            for (idx, byte) in line.bytes().rev().enumerate() {
59                set_bits_at_position[idx] += if byte == b'1' { 1 } else { -1 };
60            }
61        }
62
63        let gamma: u16 = set_bits_at_position
64            .iter()
65            .enumerate()
66            .filter_map(|(bit_idx, &count)| (count >= 0).then_some(1 << bit_idx))
67            .sum();
68        let epsilon = !gamma & set_lowest_bits(num_bits as u8);
69        Ok(u32::from(gamma) * u32::from(epsilon))
70    } else {
71        let mut numbers = input
72            .text
73            .lines()
74            .enumerate()
75            .map(|(line_idx, line)| {
76                u16::from_str_radix(line, 2)
77                    .map_err(|_| format!("Line {}: Not a binary integer", line_idx + 1))
78            })
79            .collect::<Result<Vec<u16>, _>>()?;
80
81        let oxygen_generator_rating =
82            keep_one_according_to_bitset_criteria(&mut numbers, num_bits, true)?;
83        let co2_scrubber_rating =
84            keep_one_according_to_bitset_criteria(&mut numbers, num_bits, false)?;
85        Ok(u32::from(oxygen_generator_rating) * u32::from(co2_scrubber_rating))
86    }
87}
88
89#[test]
90fn test_set_bits() {
91    assert_eq!(set_lowest_bits(1), 0b0001);
92    assert_eq!(set_lowest_bits(2), 0b0011);
93    assert_eq!(set_lowest_bits(3), 0b0111);
94    assert_eq!(set_lowest_bits(16), u16::MAX);
95}
96
97#[test]
98pub fn tests() {
99    let example = "00100
10011110
10110110
10210111
10310101
10401111
10500111
10611100
10710000
10811001
10900010
11001010";
111    test_part_one!(example => 198);
112    test_part_two!(example => 230);
113
114    let real_input = include_str!("day03_input.txt");
115    test_part_one!(real_input => 3_985_686);
116    test_part_two!(real_input => 2_555_739);
117}
advent_of_code/year2021/day03.rs

advent_of_code/year2021/
day03.rs
