Day 3: Binary Diagnostic

Day #3 problem description │ Problem input

This challenge mostly just requires filtering arrays and counting elements satisfying a condition.

Setup

The first thing we do is read the input file into a ndarray::Array2<bool> of size (n_rows, n_cols), where a true value corresponds to a 1 character in the input, and a false to a 0. We also created a function that converts a binary vector, most significant digit first, to a (decimal) number (see the Setup section). For example, given 10011, we compute [1, 0, 0, 1, 1] .* [16, 8, 4, 2, 1] = [16, 0, 0, 2, 1], whose sum is 19. (This is just how positional notation works.)

use crate::{utils::to_decimal, Answer};
use ndarray::prelude::*;

fn read_input(input: &str) -> Option<ndarray::Array2<bool>> {
	let mut lines = input.lines();
	let mut bit_vec = Vec::new();

	let first_line = lines.next()?;
	let line_length = first_line.len();

	for line in std::iter::once(first_line).chain(lines) {
		for c in line.bytes() {
			bit_vec.push(c == b'1');
		}
	}

	let n_lines = bit_vec.len() / line_length;
	Array2::from_shape_vec((n_lines, line_length), bit_vec).ok()
}

fn ans_for_input(input: &str) -> Answer<u32, u32> {
	let mat = read_input(input).unwrap();
	(3, (pt1(&mat), pt2(&mat))).into()
}

pub fn ans() -> Answer<u32, u32> {
	ans_for_input(include_str!("input.txt"))
}

Part 1

We are asked to find two numbers, gamma_rate ( $\gamma$ ) and epsilon_rate ( $\varepsilon$ ). $\gamma$ is the value of the binary number whose $k$ ^th digit is the most common digit in column $k$ of the array of values. $\varepsilon$ is computed using the same idea, but with the least common digit instead. (It is assumed that there will be no ties.)

Since there are only two digits to choose from, the most common digit and the least common digit in each column will be opposites, and so $\gamma + \varepsilon = \text{all 1s} = 2^{\text{\texttt{line\textunderscore{}width}}}-1$ . In other words we don’t need to compute $\varepsilon$ “the long way”; once we have $\gamma$ , we immediately have $\varepsilon$ .

fn pt1(mat: &Array2<bool>) -> u32 {
	let (n_rows, n_cols) = mat.dim();

	let n_ones = mat.map(|x| usize::from(*x)).sum_axis(Axis(0));
	let n_zeros = n_ones.map(|n| n_rows - n);

	let col_has_more_ones_than_zeros = ndarray::Zip::from(&n_ones)
		.and(&n_zeros)
		.map_collect(|n_o, n_z| n_o > n_z)
		.into_shape((n_cols,))
		.unwrap();

	let gamma_rate = to_decimal(col_has_more_ones_than_zeros.to_vec());
	let epsilon_rate = (2u32.pow(u32::try_from(n_cols).unwrap()) - 1) - gamma_rate;

	gamma_rate * epsilon_rate
}

Part 2

We are asked to find two new numbers, the oxygen scrubber rating oxy_rate and the CO2 scrubber rating co2_rate. The procedure to find the oxy_rate is as follows:

Initialize the list of candidate values to the full list of rows in elems as defined above.
With $k$ ranging from the leftmost column index in elems to the rightmost column index (most significant digit to least):
1. Successively narrow down the list of candidates by keeping only those remaining candidates whose $k$ ^th digit is the most common $k$ ^th digit of the remaining candidates, with a tie between 0 and 1 going to 1.
  - For instance, when $k=5$ , then keep only the remaining candidates whose 5^th digit is the most common 5^th digit (0 or 1, ties going to 1) of all remaining candidates at that stage.
2. Stop when only one candidate remains. (This is guaranteed to happen as long as the rows are all distinct.)

The procedure for co2_rate is the same, except that the list of candidates is filtered down according to the least common digit in each position, with ties going to 0.

fn value_of_line_chosen_by_criterion(
	mat: &Array2<bool>,
	cmp_predicate: impl Fn(usize, usize) -> bool,
) -> u32 {
	let (n_rows, n_cols) = mat.dim();
	let mut candidates = Array1::<_>::from_shape_simple_fn((n_rows,), || true);
	for i in 0..n_cols {
		let n_candidates_remaining = candidates.mapv(|c| if c { 1usize } else { 0 }).sum();

		if n_candidates_remaining == 1 {
			break;
		}

		let column = mat.index_axis(Axis(1), i);
		let digit_sum = column
			.iter()
			.enumerate()
			.filter_map(|(i, &x)| {
				if candidates[[i]] {
					Some(usize::from(x))
				} else {
					None
				}
			})
			.sum::<usize>();

		let most_common_digit = cmp_predicate(2 * digit_sum, n_candidates_remaining);

		candidates = ndarray::Zip::from(&candidates)
			.and(&column)
			.map_collect(|&candidate, &digit| candidate && digit == most_common_digit);
	}

	let index = candidates
		.into_iter()
		.enumerate()
		.find_map(|(i, x)| if x { Some(i) } else { None })
		.unwrap();
	let line = mat.index_axis(Axis(0), index);

	to_decimal(line.to_vec())
}

fn pt2(mat: &Array2<bool>) -> u32 {
	let [oxy_rate, co2_rate] =
		[|x, y| x >= y, |x, y| x < y].map(|op| value_of_line_chosen_by_criterion(mat, op));

	oxy_rate * co2_rate
}