AoC2020/src/day24.rs

use std::str::FromStr;
use std::collections::{HashMap, VecDeque, HashSet};
use std::io::BufRead;

#[derive(Debug, PartialEq)]
enum TileState {
    Black,
    White,
}

#[derive(Debug, PartialEq)]
enum HexDirection {
    West,
    NorthWest,
    NorthEast,
    East,
    SouthEast,
    SouthWest,
}

impl HexDirection {
    const ALL: &'static [HexDirection] = &[
        HexDirection::West,
        HexDirection::NorthWest,
        HexDirection::NorthEast,
        HexDirection::East,
        HexDirection::SouthEast,
        HexDirection::SouthWest,
    ];
}

impl FromStr for HexDirection {
    type Err = ();
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        match s {
            "w" => Ok(HexDirection::West),
            "nw" => Ok(HexDirection::NorthWest),
            "ne" => Ok(HexDirection::NorthEast),
            "e" => Ok(HexDirection::East),
            "se" => Ok(HexDirection::SouthEast),
            "sw" => Ok(HexDirection::SouthWest),
            _ => Err(())
        }
    }
}

#[derive(Debug, PartialEq, Eq, Hash, Clone)]
struct HexCoord {
    q: isize,
    r: isize,
}

// More info: https://www.redblobgames.com/grids/hexagons/#coordinates-axial
impl HexCoord {
    fn origin() -> HexCoord {
        HexCoord {
            r: 0,
            q: 0,
        }
    }

    fn move_in_direction(&self, direction: &HexDirection) -> HexCoord {
        match direction {
            HexDirection::West => HexCoord { r: self.r, q: self.q - 1 },
            HexDirection::NorthWest => HexCoord { r: self.r - 1, q: self.q },
            HexDirection::NorthEast => HexCoord { r: self.r - 1, q: self.q + 1},
            HexDirection::East => HexCoord { r: self.r, q: self.q + 1},
            HexDirection::SouthEast => HexCoord { r: self.r + 1, q: self.q },
            HexDirection::SouthWest => HexCoord { r: self.r + 1, q: self.q -1 },
        }
    }

    fn follow_path(self, mut directions: VecDeque<HexDirection>) -> HexCoord {
        if directions.len() == 0 {
            self
        } else {
            let next = self.move_in_direction(&directions.pop_front().unwrap());
            HexCoord::follow_path(next, directions)
        }
    }
}

fn parse_line(s: String) -> VecDeque<HexDirection> {
    let mut vertical = String::new();
    let mut directions = VecDeque::new();
    for c in s.chars() {
        match c {
            'n' | 's' => vertical = c.to_string(),
            'w' | 'e' => {
                directions.push_back(HexDirection::from_str(&format!("{}{}", vertical, c)).unwrap());
                vertical = String::new();
            },
            _ => unreachable!()
        }
    }
    directions
}

fn tick(state: HashSet<HexCoord>) -> HashSet<HexCoord> {
    let mut neighbours: HashMap<HexCoord, usize> = HashMap::new();
    for coord in &state {
        for direction in HexDirection::ALL {
            let nb = neighbours.entry(coord.move_in_direction(direction)).or_insert(0);
            *nb += 1;
        }
    }

    neighbours.iter()
        .filter(|(coord, nb_count)| (state.contains(coord) && **nb_count <= 2) || (!state.contains(coord) && **nb_count == 2))
        .map(|(coord, _)| coord.clone())
        .collect()
}

fn place_tiles(mut directions_lines: Vec<VecDeque<HexDirection>>) -> HashSet<HexCoord> {
    let mut tiles: HashMap<HexCoord, TileState> = HashMap::new();
    for line in directions_lines.drain(..) {
        let end = HexCoord::origin().follow_path(line);
        let tile = tiles.get(&end).unwrap_or(&TileState::White);
        if tile == &TileState::White {
            tiles.insert(end, TileState::Black);
        } else {
            tiles.insert(end, TileState::White);
        }
    }

    tiles.iter().filter(|(_, t)| **t == TileState::Black).map(|(c, _)| c.clone()).collect()
}

pub fn part1<F: BufRead> (input: F) {
    let lines = input.lines().map(|line| parse_line(line.unwrap())).collect::<Vec<_>>();
    println!("{}", place_tiles(lines).len())
}

pub fn part2<F: BufRead> (input: F) {
    let lines = input.lines().map(|line| parse_line(line.unwrap())).collect::<Vec<_>>();
    let mut state = place_tiles(lines);
    for _ in 0..100 {
        state = tick(state);
    }
    println!("{}", state.len())
}



#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_parse_line() {
        let line = "nwwswee".to_string();
        let expected: VecDeque<_> = vec![
            HexDirection::NorthWest,
            HexDirection::West,
            HexDirection::SouthWest,
            HexDirection::East,
            HexDirection::East
        ].into();
        assert_eq!(expected, parse_line(line))
    }

    #[test]
    fn test_follow_path() {
        let mut test_cases: Vec<(HexCoord, VecDeque<_>)> = vec![
            (HexCoord { r: 0, q: 0 }, vec![
                HexDirection::NorthWest,
                HexDirection::West,
                HexDirection::SouthWest,
                HexDirection::East,
                HexDirection::East
            ].into()),
            (HexCoord { r: 1, q: 0}, vec![
                HexDirection::East,
                HexDirection::SouthEast,
                HexDirection::West,
            ].into())
        ];
        for (expected, path) in test_cases.drain(..) {
            assert_eq!(expected, HexCoord::origin().follow_path(path));
        }
    }
}