use crate::input::Input;
use std::cmp::{max, min};
#[cfg(feature = "debug-output")]
use std::env;
fn parse_point_interval(s: &str) -> Result<(u16, u16), String> {
if s.contains("..") {
let parts: Vec<&str> = s.split("..").collect();
if parts.len() != 2 {
return Err("Invalid input".to_string());
}
Ok((
parts[0].parse::<u16>().map_err(|_| "Invalid input")?,
parts[1].parse::<u16>().map_err(|_| "Invalid input")?,
))
} else {
let point = s.parse::<u16>().map_err(|_| "Invalid input")?;
Ok((point, point))
}
}
struct Grid {
cells: Vec<u8>,
width: usize,
height: usize,
}
impl Grid {
fn from(input_string: &str) -> Result<Self, String> {
let mut points: Vec<(u16, u16)> = Vec::new();
let mut x_range = (u16::MAX, u16::MIN);
let mut y_range = (u16::MAX, u16::MIN);
for line in input_string.lines() {
let mut parts: Vec<&str> = line.split(", ").collect();
if parts.len() != 2 || parts[0].len() < 3 || parts[1].len() < 3 {
return Err("Invalid input".to_string());
}
parts.sort_unstable();
let (x_start, x_end) = parse_point_interval(&parts[0][2..])?;
let (y_start, y_end) = parse_point_interval(&parts[1][2..])?;
x_range = (min(x_range.0, x_start), max(x_range.1, x_end));
y_range = (min(y_range.0, y_start), max(y_range.1, y_end));
for x in x_start..=x_end {
for y in y_start..=y_end {
points.push((x, y));
}
}
}
x_range = (x_range.0 - 1, x_range.1 + 1);
let width = ((x_range.1 - x_range.0) + 1) as usize;
let height = ((y_range.1 - y_range.0) + 1) as usize;
let mut cells = vec![b'.'; width * height];
for point in points {
let x = point.0 - x_range.0;
let y = point.1 - y_range.0;
cells[y as usize * width + x as usize] = b'#';
}
let water_x = 500;
if !(x_range.0..x_range.1).contains(&water_x) {
return Err("Spring outside scanned area".into());
}
let water_x_relative = water_x - x_range.0;
cells[water_x_relative as usize] = b'|';
Ok(Self {
cells,
width,
height,
})
}
#[cfg(feature = "debug-output")]
fn print(&self, name: &str) {
if env::var("ADVENT_DEBUG").is_err() {
return;
}
println!("### {}", name);
for y in 0..self.height {
println!(
"{}",
String::from_utf8(self.cells[y * self.width..(y + 1) * self.width].to_vec())
.unwrap_or_else(|_| "Invalid utf-8".to_string())
.replace('.', " ")
.replace('#', "█")
);
}
println!();
}
fn at(&self, x: u16, y: u16) -> u8 {
self.cells[y as usize * self.width + x as usize]
}
fn set_water_at(&mut self, x: u16, y: u16, solid: bool) {
self.cells[y as usize * self.width + x as usize] = if solid { b'w' } else { b'|' };
}
fn dry_at(&mut self, x: u16, y: u16) {
self.cells[y as usize * self.width + x as usize] = b'.';
}
fn wall_in_direction(&self, x_start: u16, y: u16, x_direction: i32) -> bool {
let mut x = (i32::from(x_start) + x_direction) as u16;
loop {
let cell = self.at(x, y);
if !(cell == b'.' || cell == b'w' || cell == b'|') {
break;
}
let below = self.at(x, y + 1);
if !(below == b'#' || below == b'w') {
return false;
}
x = (i32::from(x) + x_direction) as u16;
}
self.at(x, y) == b'#'
}
fn fill_in_direction(&mut self, x_start: u16, y: u16, x_direction: i32, solid: bool) {
let mut x = (i32::from(x_start) + x_direction) as u16;
loop {
let cell = self.at(x, y);
if !(cell == b'.' || cell == b'w' || cell == b'|') {
break;
}
self.set_water_at(x, y, solid);
let below = self.at(x, y + 1);
if !(below == b'#' || below == b'w') {
return;
}
x = (i32::from(x) + x_direction) as u16;
}
}
fn spread_water_at(&mut self, x: u16, y: u16) -> u16 {
self.set_water_at(x, y, false);
if (y as usize) < self.height - 1 {
let below = self.at(x, y + 1);
if below == b'#' || below == b'w' {
let left_wall = self.wall_in_direction(x, y, -1);
let right_wall = self.wall_in_direction(x, y, 1);
let surrounded_by_walls = left_wall && right_wall;
self.fill_in_direction(x, y, -1, surrounded_by_walls);
self.fill_in_direction(x, y, 1, surrounded_by_walls);
if surrounded_by_walls {
self.set_water_at(x, y, true);
}
if surrounded_by_walls && y > 0 {
return self.spread_water_at(x, y - 1);
}
}
}
y
}
fn pour_water(&mut self) {
let mut line = 1;
while line < self.height {
let mut top_y = line;
let mut to_fill = Vec::new();
for x in 0..self.width {
if self.at(x as u16, line as u16 - 1) == b'|'
&& self.at(x as u16, line as u16) == b'.'
{
to_fill.push(x);
}
}
for x in to_fill {
top_y = min(top_y, self.spread_water_at(x as u16, line as u16) as usize);
}
line = top_y + 1;
}
}
fn holds_in_direction(&self, x_start: u16, y: u16, x_direction: i32) -> bool {
let mut x = (i32::from(x_start) + x_direction) as u16;
loop {
let cell = self.at(x, y);
let below = self.at(x, y + 1);
if !(below == b'#' || below == b'w') {
return false;
}
if cell == b'#' {
return true;
}
x = (i32::from(x) + x_direction) as u16;
}
}
fn dry_up(&mut self) {
let mut line = self.height as u16;
while line > 0 {
line -= 1;
for x in 0..self.width {
if self.at(x as u16, line) == b'w' {
let below = if line == (self.height as u16 - 1) {
b'.'
} else {
self.at(x as u16, line + 1)
};
if !((below == b'#' || below == b'w')
&& self.holds_in_direction(x as u16, line, -1)
&& self.holds_in_direction(x as u16, line, 1))
{
self.dry_at(x as u16, line);
}
}
}
}
}
fn count_water(&self) -> usize {
self.cells
.iter()
.fold(0, |n, c| n + usize::from(*c == b'w' || *c == b'|'))
}
fn count_drained_water(&self) -> usize {
self.cells
.iter()
.fold(0, |n, c| n + usize::from(*c == b'w'))
}
}
pub fn solve(input: &Input) -> Result<usize, String> {
let mut grid = Grid::from(input.text)?;
#[cfg(feature = "debug-output")]
grid.print("Initial");
grid.pour_water();
#[cfg(feature = "debug-output")]
grid.print("After pouring");
if input.is_part_one() {
Ok(grid.count_water())
} else {
grid.dry_up();
#[cfg(feature = "debug-output")]
grid.print("After drying up");
Ok(grid.count_drained_water())
}
}
#[test]
fn tests() {
use crate::input::{test_part_one, test_part_two};
test_part_one!(
"x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504"
=> 57
);
test_part_two!(
"x=495, y=2..7
y=7, x=495..501
x=501, y=3..7
x=498, y=2..4
x=506, y=1..2
x=498, y=10..13
x=504, y=10..13
y=13, x=498..504"
=> 29
);
let input = include_str!("day17_input.txt");
test_part_one!(input => 31949);
test_part_two!(input => 26384);
}