Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- use std::env;
- use std::io::{self, prelude::*, BufReader};
- use std::fs::File;
- use std::collections::{HashSet,HashMap};
- use point2d::point2d::Point2D;
- #[derive(Clone)]
- struct Pipe {
- dirs: [Direction; 2]
- }
- impl Pipe {
- pub fn goes(&self, dir: &Direction) -> bool {
- self.dirs.iter().any(|d| d == dir)
- }
- }
- #[derive(Debug,PartialEq,Copy,Clone)]
- enum Direction {
- North,
- South,
- East,
- West,
- Nowhere,
- }
- fn opposite_dir(dir: Direction) -> Direction {
- use Direction::*;
- match dir {
- North => South,
- South => North,
- East => West,
- West => East,
- _ => panic!(),
- }
- }
- fn pipe_kind(ch: char) -> Pipe {
- use Direction::*;
- match ch {
- '|' => Pipe { dirs: [North,South] },
- '-' => Pipe { dirs: [East,West] },
- 'L' => Pipe { dirs: [North,East] },
- 'J' => Pipe { dirs: [North,West] },
- '7' => Pipe { dirs: [South,West] },
- 'F' => Pipe { dirs: [South,East] },
- '.' => Pipe { dirs: [Nowhere,Nowhere] },
- 'S' => Pipe { dirs: [Nowhere,Nowhere] },
- _ => panic!("Unexpected pipe map character: {ch}"),
- }
- }
- fn move_to(from: &Point2D, dir: &Direction) -> Point2D {
- use Direction::*;
- match dir {
- North => Point2D { x: from.x, y: from.y - 1 },
- South => Point2D { x: from.x, y: from.y + 1 },
- East => Point2D { x: from.x + 1, y: from.y },
- West => Point2D { x: from.x - 1, y: from.y },
- _ => panic!(),
- }
- }
- fn new_dir(dir: Direction, pipe: &Pipe) -> Direction {
- let from = opposite_dir(dir);
- if pipe.dirs[0] == from { pipe.dirs[1] } else { pipe.dirs[0] }
- }
- fn solve(input: &str) -> io::Result<()> {
- let file = File::open(input).expect("Input file not found.");
- let reader = BufReader::new(file);
- // The pipe configuration at S is not determined programmatically.
- // Must be specified per input file.
- let start_pipe = match input {
- "input.txt" => Pipe { dirs: [Direction::South,Direction::East] },
- "sample.txt" => Pipe { dirs: [Direction::South,Direction::East] },
- "sample2.txt" => Pipe { dirs: [Direction::South,Direction::East] },
- "sample3.txt" => Pipe { dirs: [Direction::South,Direction::East] },
- "sample4.txt" => Pipe { dirs: [Direction::South,Direction::West] },
- _ => panic!("Must specify pipe type at S for each input file."),
- };
- // Input
- let input: Vec<String> = match reader.lines().collect() {
- Err(err) => panic!("Unknown error reading input: {err}"),
- Ok(result) => result,
- };
- // Build map
- let mut start: Point2D = Point2D { x: -1, y: -1 };
- let mut pipes: HashMap<Point2D,Pipe> = HashMap::new();
- for (y,line) in input.iter().enumerate() {
- for (x,ch) in line.chars().enumerate() {
- let pt = Point2D { x: x as i64, y: y as i64 };
- if ch == 'S' {
- start = pt;
- pipes.insert(pt,start_pipe.clone());
- } else {
- pipes.insert(pt,pipe_kind(ch));
- }
- }
- }
- // Trace path and calculate part 1
- let mut steps = 0;
- let mut current = start;
- let mut direction = Direction::East;
- let mut path_map: HashMap<Point2D,Pipe> = HashMap::new();
- path_map.insert(start,start_pipe.clone());
- loop {
- let next_pt = move_to(¤t,&direction);
- let pipe_next = pipes.get(&next_pt).unwrap();
- path_map.insert(next_pt,pipe_next.clone());
- direction = new_dir(direction, pipe_next);
- current = next_pt;
- steps += 1;
- if current == start { break }
- }
- println!("Part 1: {}",steps/2); // 6864
- // Calculate map extents for part 2
- let xmax = pipes.keys().map(|pt| pt.x).max().unwrap();
- let ymax = pipes.keys().map(|pt| pt.y).max().unwrap();
- let yinf = ymax + 1;
- // Part 2
- let mut enclosed_points: HashSet<Point2D> = HashSet::new();
- for x in 0..=xmax {
- 'y_lp: for y in 0..=ymax {
- let pt_check = Point2D { x: x, y: y };
- // Skip points that are on the path
- if path_map.contains_key(&pt_check) { continue 'y_lp }
- // Even-Odd Rule (https://en.wikipedia.org/wiki/Even%E2%80%93odd_rule)
- // Draw vector directly South to infinity (ymax+1) from every point not
- // already part of the path. Count the number of times this vector
- // crosses pipes that go east and pipes that go west.
- // If the minimum of these two counts is odd, point is enclosed.
- let mut crosses_east = 0;
- let mut crosses_west = 0;
- for ynew in y..=yinf {
- if let Some(pt) = path_map.get(&Point2D { x: x, y: ynew }) {
- if pt.goes(&Direction::East) { crosses_east += 1 }
- if pt.goes(&Direction::West) { crosses_west += 1 }
- }
- }
- // Check for odd number of crosses
- if std::cmp::min(crosses_west,crosses_east) % 2 != 0 {
- enclosed_points.insert(pt_check);
- }
- }
- }
- let part2 = enclosed_points.len();
- println!("Part 2: {part2}"); // 349
- Ok(())
- }
- fn main() {
- let args: Vec<String> = env::args().collect();
- let filename = &args[1];
- solve(&filename).unwrap();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement