mirror of
https://github.com/wezm/advent-of-code.git
synced 2024-12-18 18:29:55 +00:00
103 lines
2.6 KiB
Rust
103 lines
2.6 KiB
Rust
use std::env;
|
|
use std::fs::File;
|
|
use std::io::{BufRead, BufReader};
|
|
|
|
type BoxError = Box<dyn std::error::Error>;
|
|
|
|
fn main() -> Result<(), BoxError> {
|
|
let input_path = env::args_os()
|
|
.skip(1)
|
|
.next()
|
|
.ok_or("missing input file path")?;
|
|
let file = BufReader::new(File::open(input_path)?);
|
|
|
|
let mut state = Vec::new();
|
|
let mut combinations = Vec::new();
|
|
let mut part1 = 0;
|
|
for line in file.lines() {
|
|
let line = line?;
|
|
if line.is_empty() {
|
|
continue;
|
|
}
|
|
let (pattern, info) = line.split_once(' ').ok_or("unable to split line")?;
|
|
|
|
let info = info
|
|
.split(',')
|
|
.map(|n| n.parse::<u32>())
|
|
.collect::<Result<Vec<_>, _>>()?;
|
|
|
|
// generate all combinations of wildcards
|
|
combinations.clear();
|
|
state.clear();
|
|
generate(pattern.as_bytes(), &mut state, &mut combinations, &info);
|
|
// dbg!(&combinations);
|
|
part1 += combinations.len();
|
|
}
|
|
|
|
println!("Part 1: {part1}");
|
|
|
|
Ok(())
|
|
}
|
|
|
|
fn matches(s: &str, pattern: &str) -> bool {
|
|
s.chars()
|
|
.zip(pattern.chars())
|
|
.all(|(a, b)| a == b || b == '?')
|
|
}
|
|
|
|
fn generate(
|
|
pattern: &[u8],
|
|
state: &mut Vec<u8>,
|
|
combinations: &mut Vec<String>,
|
|
contiguous: &[u32],
|
|
) {
|
|
if pattern.is_empty() {
|
|
let candidate = String::from_utf8(state.clone()).unwrap();
|
|
let candidate_info = count_contiguous(&candidate);
|
|
if candidate_info == contiguous {
|
|
combinations.push(candidate);
|
|
}
|
|
return;
|
|
}
|
|
|
|
match pattern[0] {
|
|
b'.' | b'#' => {
|
|
state.push(pattern[0]);
|
|
generate(&pattern[1..], state, combinations, contiguous);
|
|
state.pop().unwrap();
|
|
}
|
|
b'?' => {
|
|
state.push(b'.');
|
|
generate(&pattern[1..], state, combinations, contiguous);
|
|
state.pop().unwrap();
|
|
state.push(b'#');
|
|
generate(&pattern[1..], state, combinations, contiguous);
|
|
state.pop().unwrap();
|
|
}
|
|
_ => unreachable!("unexpected char"),
|
|
}
|
|
}
|
|
|
|
fn count_contiguous(s: &str) -> Vec<u32> {
|
|
let mut counts = Vec::new();
|
|
let mut in_contiguous = false;
|
|
let mut count: u32 = 0;
|
|
for c in s.chars() {
|
|
match c {
|
|
'#' if in_contiguous => count += 1,
|
|
'#' => {
|
|
in_contiguous = true;
|
|
count = 1;
|
|
}
|
|
'.' if in_contiguous => {
|
|
counts.push(count);
|
|
in_contiguous = false;
|
|
}
|
|
_ => {}
|
|
}
|
|
}
|
|
if in_contiguous {
|
|
counts.push(count);
|
|
}
|
|
counts
|
|
}
|