Advent of Code 2022 day 14 with backtracking

main.rs

use std::ops::{Index, IndexMut};
use itertools::Itertools;

struct Bitmap {
    rows: usize,
    cols: usize,
    backing: Vec<bool>,
    boundary: bool,
}

impl Index<(usize, usize)> for Bitmap {
    type Output = bool;
    fn index(&self, (x, y): (usize, usize)) -> &Self::Output {
        if y >= self.rows-1 || x >= self.cols - 1 {
            &self.boundary
        } else {
            &self.backing[y * self.cols + x]
        }
    }
}

impl IndexMut<(usize, usize)> for Bitmap {
    fn index_mut(&mut self, (x, y): (usize, usize)) -> &mut Self::Output {
        if y >= self.rows-1 || x >= self.cols - 1 {
            &mut self.boundary
        } else {
            &mut self.backing[y * self.cols + x]
        }
    }
}

impl Bitmap {
    fn new(rows: usize, cols: usize) -> Self {
        let mut backing = Vec::with_capacity(rows * cols);
        backing.resize_with(rows * cols, ||false);
        return Self{ rows, cols, backing , boundary: true};
    }
}

fn main() {
    let input = std::fs::read_to_string("test.txt").ok().unwrap();
    let points = input
        .split('\n')
        .map(|line| {
            line.split(" -> ")
                .filter_map(|pair| {
                    match pair.split(',').next_tuple() {
                        Some((x, y)) => Some((x.parse::<usize>().unwrap(), y.parse::<usize>().unwrap())),
                        None => None,
                    }
                }).collect::<Vec<_>>()
             }).collect::<Vec<_>>();

    let rows = points
        .iter()
        .flat_map(|l| l.iter())
        .max_by(|(_, y1), (_, y2)| y1.cmp(y2))
        .unwrap().1
        +2;

    let cols = points
        .iter()
        .flat_map(|l| l.iter())
        .max_by(|(x1, _), (x2, _)| x1.cmp(x2))
        .unwrap().0
        .max(500 + rows)
        +2;

    let mut field = Bitmap::new(rows + 1, cols + 1);

    points
        .iter()
        .for_each(|line| {
            line.iter().tuple_windows().for_each(|(&(x1, y1), &(x2, y2))| {
                for x in usize::min(x1,x2)..=usize::max(x1,x2) {
                    for y in usize::min(y1,y2)..=usize::max(y1,y2) {
                        field[(x, y)] = true;
                    }
                }
            })
        });

    let part1 = simulate( &mut field, |field, trail| {
        trail.last().unwrap().1 >= field.rows-2
    });
    println!("Part 1: {}", part1);

    let part2 = 1 + part1 + simulate(&mut field, |_, trail| {
        trail.len() == 1
    });
    println!("Part 1: {}", part2);
}


fn simulate(field: &mut Bitmap, condition: impl Fn(&Bitmap, &Vec<(usize, usize)>) -> bool) -> usize{
    let mut trail = vec![(500, 0)];
    let mut count = 0;
    loop {
        let (mut x0, mut y0) = trail.last().unwrap();

        while let Some(x) = [x0, x0-1, x0+1].iter().filter(|x| !field[(**x, y0+1)]).next() {
            (x0, y0) = (*x, y0+1);
            trail.push((x0, y0));
        }

        if condition(field, &trail) { return count; }
        trail.pop();
        field[(x0, y0)] = true;
        count += 1;
    }
}