🌟 Advent of Code (AoC) 2022 🌟

use std::{collections::BTreeMap, fmt::Display};

#[derive(Debug, PartialEq)]
enum Material {
  Rock,
  Sand,
  SandSource,
}

#[derive(Debug, Default)]
struct Board {
  material: BTreeMap<(i32, i32), Material>,
  floor: bool,
  sand_source: (i32, i32),
  top: i32,
  bottom: i32,
  left: i32,
  right: i32,
}

impl Board {
  fn add_sand(&mut self) -> bool {
    let mut cord = self.sand_source;
    if let Some(&Material::SandSource) = self.material.get(&cord) {
      loop {
        let below = (cord.0, cord.1 + 1);
        if let Some(_) = self.material.get(&below) {
          let left = (cord.0 - 1, below.1);
          let right = (cord.0 + 1, below.1);
          if let None = self.material.get(&left) {
            cord = left;
          } else if let None = self.material.get(&right) {
            cord = right;
          } else {
            break;
          }
        } else {
          if cord.1 > self.bottom {
            if self.floor {
              break;
            } else {
              return false;
            }
          }
          cord = below;
        }
      }
      self.material.insert(cord, Material::Sand);
      self.left = self.left.min(cord.0);
      self.right = self.right.max(cord.0);
      return true;
    }
    false
  }
}

impl Display for Board {
  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    for y in self.top..=self.bottom {
      for x in self.left..=self.right {
        let c = match self.material.get(&(x, y)) {
          Some(Material::Rock) => '#',
          Some(Material::Sand) => 'o',
          Some(Material::SandSource) => '+',
          None => '.',
        };
        write!(f, "{}", c)?;
      }
      writeln!(f)?;
    }
    if self.floor {
      for _ in self.left..=self.right {
        write!(f, "#")?;
      }
      writeln!(f)?;
    }
    Ok(())
  }
}

fn parse(input: &str) -> Board {
  let mut board = Board::default();

  board.sand_source = (500, 0);
  board.material.insert(board.sand_source, Material::SandSource);

  for line in input.lines() {
    line.split(" -> ")
      .map(|part| {
        let mut parts = part.split(",");
        let x = parts.next().unwrap().parse::<i32>().unwrap();
        let y = parts.next().unwrap().parse::<i32>().unwrap();
        (x, y)
      })
      .fold(Option::<(i32, i32)>::None, |mut state, to| {
        if let Some(from) = state.take() {
          let mut x_range = from.0..=to.0;
          let mut y_range = from.1..=to.1;
          if x_range.start() > x_range.end() {
            x_range = to.0..=from.0;
          }
          if y_range.start() > y_range.end() {
            y_range = to.1..=from.1;
          }
          for x in x_range {
            for y in y_range.clone() {
              board.material.insert((x, y), Material::Rock);
            }
          }
        }
        Some(to)
      });
  }

  board.top = board.material.keys().next().unwrap().1;
  board.bottom = board.material.keys().next().unwrap().1;
  board.left = board.material.keys().next().unwrap().0;
  board.right = board.material.keys().next().unwrap().0;
  for (x, y) in board.material.keys() {
    board.top = board.top.min(*y);
    board.bottom = board.bottom.max(*y);
    board.left = board.left.min(*x);
    board.right = board.right.max(*x);
  }

  board
}

pub fn one() {
  let input = include_str!("input.txt");
  let mut board = parse(input);
  let mut result = 0;
  while board.add_sand() {
    result += 1;
  }
  println!("{}", board);
  println!("Day 14, part 1: {}", result);
}

pub fn two() {
  let input = include_str!("input.txt");
  let mut board = parse(input);
  board.floor = true;
  board.bottom += 1;
  #[allow(unused)]
  let mut result = 0;
  while board.add_sand() {
    result += 1;
  }
  println!("{}", board);
  let print = format!("{}", board);

  // sand and above result is wrong, count from print works
  // let sand = board.material.values().filter(|m| m == &&Material::Sand).count();
  let result = print.chars().filter(|c| c == &'o').count();
  println!("Day 14, part 2: {}", result);
}

use std::{collections::{BTreeMap, BTreeSet}, fmt::Display};

use regex::Regex;

#[derive(Debug, Default)]
struct Board {
  sensors: BTreeMap<(i32, i32), (i32, i32)>,
  no_beacons: BTreeSet<(i32, i32)>,
  top: i32,
  bottom: i32,
  left: i32,
  right: i32,
}

impl Display for Board {
  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    let beacons = self.sensors.values().collect::<BTreeSet<_>>();
    for y in self.top..=self.bottom {
      write!(f, "{y: >8} ")?;
      for x in self.left..=self.right {
        let c = match self.sensors.get(&(x, y)) {
          Some(_) => 'S',
          None => if beacons.contains(&(x, y)) {'B'} else {
            if self.no_beacons.contains(&(x, y)) {'#'} else {'.'}
          },
        };
        write!(f, "{}", c)?;
      }
      writeln!(f)?;
    }
    Ok(())
  }
}

fn parse(input: &str) -> Board {
  let mut board = Board::default();
  let re = Regex::new(r"Sensor at x=(-?\d+), y=(-?\d+): closest beacon is at x=(-?\d+), y=(-?\d+)").unwrap();

  for line in input.lines() {
    let caps = re.captures(line).unwrap();
    let sx = caps.get(1).unwrap().as_str().parse::<i32>().unwrap();
    let sy = caps.get(2).unwrap().as_str().parse::<i32>().unwrap();
    let bx = caps.get(3).unwrap().as_str().parse::<i32>().unwrap();
    let by = caps.get(4).unwrap().as_str().parse::<i32>().unwrap();

    board.sensors.insert((sx, sy), (bx, by));
    board.top = sy.min(by);
    board.bottom = sy.max(by);
    board.left = sy.min(bx);
    board.right = sy.max(bx);
  }

  for ((sx, sy), (bx, by)) in board.sensors.iter() {
    let distance = (sx - bx).abs() + (sy - by).abs();

    board.top = board.top.min(*sy - distance);
    board.bottom = board.bottom.max(*sy + distance);
    board.left = board.left.min(*sx - distance);
    board.right = board.right.max(*sx + distance);
    board.top = board.top.min(*by);
    board.bottom = board.bottom.max(*by);
    board.left = board.left.min(*bx);
    board.right = board.right.max(*bx);
  }

  board
}

pub fn one() {
  let input = include_str!("input.txt");

  let board = parse(input);

  let mut result = 0;
  let y = 2000000;
  for x in board.left..=board.right {
    for ((sx, sy), (bx, by)) in board.sensors.iter() {
      let a_distance = (sx - x).abs() + (sy - y).abs();
      let b_distance = (sx - bx).abs() + (sy - by).abs();
      if a_distance <= b_distance && (x, y) != (*bx, *by) {
        result += 1;
        break;
      }
    }
  }

  println!("Day 15, part 1: {}", result);
}

pub fn two() {
  let input = include_str!("input.txt");

  let board = parse(input);

  let mut result = 0;

  let search_distance = 4000000;
  let search_range = 0..=search_distance;
  'outer:
  for ((sx, sy), (bx, by)) in board.sensors.iter() {
    let distance = (sx - bx).abs() + (sy - by).abs();
    let r = distance + 1;

    let search_circle = 
      ((sx - r)..=(sx + r)).zip(((sy - r)..=*sy).rev().chain((sy - r + 1)..=*sy))
      .chain(((sx - r + 1)..(sx + r)).rev().zip(((sy + 1)..=(sy + r)).chain((*sy..=(sy + r - 1)).rev())));

    for (x, y) in search_circle {
      if !search_range.contains(&x) || !search_range.contains(&y) {
        continue;
      }
      let mut found = false;
      for ((sx, sy), (bx, by)) in board.sensors.iter() {
        let a_distance = (sx - x).abs() + (sy - y).abs();
        let b_distance = (sx - bx).abs() + (sy - by).abs();
        if a_distance <= b_distance {
          found = true;
          break;
        }
      }
      if !found {
        println!("Found at {}, {}", x, y);
        result = (x as u64) * 4000000 + (y as u64);
        break 'outer;
      }
    }
  }


  println!("Day 15, part 2: {}", result);
}

use pathfinding::prelude::dijkstra;
use regex::Regex;
use std::{collections::{BTreeMap, BTreeSet}, sync::{Arc, RwLock}};
use itertools::Itertools;
use rayon::prelude::*;

#[derive(Debug, Default)]
struct Board {
	valves: BTreeMap<u32, Valve>,
}

impl Board {
	fn remove_empty(&mut self) {
		let mut empty = BTreeSet::new();
		for (id, valve) in self.valves.iter() {
			if valve.flow_rate == 0 {
				empty.insert(*id);
			}
		}
		for id in empty {
			self.valves.remove(&id);
			for valve in self.valves.values_mut() {
				valve.tunnels.retain(|t| *t != id);
			}
		}
	}

  fn calculate_distances(&self) -> BTreeMap<(u32, u32), u32> {
    let mut distances = BTreeMap::new();

    for from_valve in self.valves.values() {
      for to_valve in self.valves.values() {
        let path = dijkstra(
          &&from_valve.id,
          |id| self.valves[*id].tunnels.iter().map(|id| (id, 1)),
          |id| *id == &to_valve.id,
        );
        distances.insert(
          (from_valve.id, to_valve.id),
          path.unwrap().1,
        );
      }
    }

    distances
  }
}

#[derive(Debug, Default)]
struct Valve {
	id: u32,
	flow_rate: u32,
	tunnels: Vec<u32>,
}

fn parse(input: &str) -> Board {
	let re =
		Regex::new(r"Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)")
			.unwrap();
	let mut board = Board::default();
  let mut ids = BTreeMap::new();
  ids.insert("AA".to_string(), 0);
  let mut next_id = 1;

	for line in input.lines() {
		let caps = re.captures(line).unwrap();
		let valve = caps.get(1).unwrap().as_str();
    let id = *ids.entry(valve.to_string()).or_insert_with(|| {
      let id = next_id;
      next_id += 1;
      id
    });
		let flow_rate = caps.get(2).unwrap().as_str().parse().unwrap();
		let valves = caps
			.get(3)
			.unwrap()
			.as_str()
			.split(", ")
			.map(|s| {
        *ids.entry(s.to_string()).or_insert_with(|| {
          let id = next_id;
          next_id += 1;
          id
        })
      })
			.collect();

		board.valves.insert(
			id,
			Valve {
				id,
				flow_rate,
				tunnels: valves,
			},
		);
	}

	board
}

#[derive(Debug, Clone)]
struct State {
	location: u32,
	remaining_time: u32,
	total_preasure_release: u32,
	open_valves: Vec<u32>,
}

fn asd(board: &Board, distances: &BTreeMap<(u32, u32), u32>, state: State) -> State {
	let move_time = 1;
	let open_time = 1;

	let remaining_valves = board
		.valves
		.values()
		.filter(|v| !state.open_valves.contains(&v.id))
		.map(|v| {
			let time_to_open =
				distances[&(state.location, v.id)] * move_time + open_time;
			let total_presure_release =
				(state.remaining_time.max(time_to_open) - time_to_open) * v.flow_rate;

			(v.id.clone(), time_to_open, total_presure_release)
		})
		.filter(|(_, time_to_open, _)| *time_to_open <= state.remaining_time);

	let best_result = remaining_valves
		.map(|(valve, time_to_open, total_presure_release)| {
      let mut new_state = state.clone();
      new_state.location = valve;
      new_state.remaining_time -= time_to_open;
      new_state.total_preasure_release += total_presure_release;
      new_state.open_valves.push(valve);
      asd(board, distances, new_state)
		})
		.max_by_key(|state| state.total_preasure_release);

	best_result.unwrap_or(state)
}

pub fn one() {
	let input = include_str!("input.txt");

	let mut board = parse(input);
  let distances = board.calculate_distances();
	board.remove_empty();

	let result = asd(
		&board,
		&distances,
		State {
			location: 0,
			remaining_time: 30,
			total_preasure_release: 0,
			open_valves: Default::default(),
		},
	);
  println!("{:?}", result);

	println!("Day 16, part 1: {}", result.total_preasure_release);
}

pub fn two() {
	let input = include_str!("input.txt");

	let mut board = parse(input);
  let mut distances = board.calculate_distances();
	board.remove_empty();
  let mut empty = BTreeSet::new();
  for (a, b) in distances.keys() {
    if *a != 0 && *b != 0 && (!board.valves.contains_key(&a) || !board.valves.contains_key(&b)) {
      empty.insert((*a, *b));
    }
  }
  for id in empty {
    distances.remove(&id);
  }

  let mut valves = board.valves.keys().collect::<Vec<_>>();
  valves.sort_by_key(|id| 100 - board.valves[id].flow_rate);
  let perms1 = valves.clone().into_iter().permutations(7);
  let perms2 = valves.into_iter().permutations(7);

  let best = Arc::new(RwLock::new(0));

  let result = perms1.cartesian_product(perms2).par_bridge()
    .map(|(perm1, perm2)| {
      let mut location1 = 0;
      let mut location2 = 0;
      let mut remaining_time1 = 26;
      let mut remaining_time2 = 26;
      let mut total_preasure_release = 0;
      let mut opened_valves = BTreeSet::new();

      for i in 0..perm1.len() {
        let valve1 = unsafe { **perm1.get_unchecked(i) };
        let valve2 = unsafe { **perm2.get_unchecked(i) };
        if !opened_valves.contains(&valve1) {
          let time_to_open = distances[&(location1, valve1)] + 1;
          if time_to_open <= remaining_time1 {
            remaining_time1 -= time_to_open;
            total_preasure_release += board.valves[&valve1].flow_rate * remaining_time1;
            location1 = valve1;
            opened_valves.insert(valve1);
          }
        }
        if !opened_valves.contains(&valve2) {
          let time_to_open = distances[&(location2, valve2)] + 1;
          if time_to_open <= remaining_time2 {
            remaining_time2 -= time_to_open;
            total_preasure_release += board.valves[&valve2].flow_rate * remaining_time2;
            location2 = valve2;
            opened_valves.insert(valve2);
          }
        }
      }

      if total_preasure_release > 2500 {
        let b = best.read().unwrap();
        if total_preasure_release > *b {
          drop(b);
          let mut b = best.write().unwrap();
          println!("total_preasure_release: {}", total_preasure_release);
          println!("P1: {:?}", perm1);
          println!("P2: {:?}", perm2);
          println!();
          *b = b.max(total_preasure_release);
        }
      }

      total_preasure_release
    })
    .max()
    .unwrap();

	println!("Day 16, part 2: {}", result);
}

#![allow(unused)]

use std::{collections::BTreeSet, fmt::Display, time::Instant};

enum Dir {
  Left,
  Right,
}

#[derive(Debug, Clone)]
struct Board<'a> {
  width: i64,
  height: i64,
  rocks: BTreeSet<(i64, i64)>,
  falling: Option<(&'a Rock, (i64, i64))>,
}

impl<'a> Board<'a> {
  fn new(width: i64) -> Self {
    Self {
      width,
      height: 0,
      rocks: BTreeSet::new(),
      falling: None,
    }
  }

  fn start_height(&self) -> i64 {
    self.height + 3
  }

  fn add_falling(&mut self, rock: &'a Rock) {
    self.falling.replace((rock, (2, self.start_height())));
  }

  fn fall(&mut self, move_dir: Dir) -> bool {
    let (rock, (x, y)) = self.falling.take().expect("No falling rock");
    let mut left = rock.left() + x;
    let mut right = rock.right() + x;
    let mut bottom = rock.bottom() + y;
    let height = self.height;

    match move_dir {
      Dir::Left => {
        if left > 0 {
          left -= 1;
          right -= 1;
        }
        if bottom <= height {
          if rock.collides_with(&self.rocks, (left, bottom)) {
            left += 1;
            right += 1;
          }
        }
      },
      Dir::Right => {
        if right < self.width - 1 {
          left += 1;
          right += 1;
        }
        if bottom <= height {
          if rock.collides_with(&self.rocks, (left, bottom)) {
            left -= 1;
            right -= 1;
          }
        }
      },
    }

    bottom -= 1;

    if bottom < 0 || rock.collides_with(&self.rocks, (left, bottom)) {
      bottom += 1;
      let mut new_rocks = rock.0.iter().map(|(x, y)| (x + left, y + bottom));
      self.rocks.extend(new_rocks);
      self.height = self.height.max(rock.top() + bottom + 1);
      return true;
    }

    self.falling.replace((rock, (left, bottom)));
    false
  }
}

impl Display for Board<'_> {
  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    let mut height = self.height;
    if let Some((rock, (x, y))) = &self.falling {
      height = height.max(y + rock.top());
    }

    for y in (0..=height).rev() {
      for x in -1..=self.width {
        if x == -1 || x == self.width {
          write!(f, "|")?;
          continue;
        }
        if let Some((rock, (rx, ry))) = &self.falling {
          if rock.0.contains(&(x - rx, y - ry)) {
            write!(f, "@")?;
            continue;
          }
        }

        if self.rocks.contains(&(x, y)) {
          write!(f, "#")?;
        } else {
          write!(f, ".")?;
        }
      }
      writeln!(f)?;
    }
    for x in -1..=(self.width as i64) {
      if x == -1 || x == self.width as i64 {
        write!(f, "+")?;
        continue;
      }
      write!(f, "-")?;
    }
    writeln!(f)?;
    writeln!(f, "height: {}", self.height)?;

    Ok(())
  }
}

#[derive(Debug, PartialEq, Eq)]
struct Rock(BTreeSet<(i64, i64)>, i64, i64, i64, i64);

impl Rock {
  fn types() -> Vec<Rock> {
    let horiz_rock = BTreeSet::from([(0, 0), (1, 0), (2, 0), (3, 0)]);
    let plus_rock = BTreeSet::from([(1, 0), (0, 1), (1, 1), (2, 1), (1, 2)]);
    let l_rock = BTreeSet::from([(2, 2), (2, 1), (0, 0), (1, 0), (2, 0)]);
    let vert_rock = BTreeSet::from([(0, 0), (0, 1), (0, 2), (0, 3)]);
    let square_rock = BTreeSet::from([(0, 0), (1, 0), (0, 1), (1, 1)]);

    vec![
      Rock(
        horiz_rock.clone(),
        *horiz_rock.iter().map(|(x, _)| x).min().unwrap(),
        *horiz_rock.iter().map(|(x, _)| x).max().unwrap(),
        *horiz_rock.iter().map(|(_, y)| y).max().unwrap(),
        *horiz_rock.iter().map(|(_, y)| y).min().unwrap()
      ),
      Rock(
        plus_rock.clone(),
        *plus_rock.iter().map(|(x, _)| x).min().unwrap(),
        *plus_rock.iter().map(|(x, _)| x).max().unwrap(),
        *plus_rock.iter().map(|(_, y)| y).max().unwrap(),
        *plus_rock.iter().map(|(_, y)| y).min().unwrap()
      ),
      Rock(
        l_rock.clone(),
        *l_rock.iter().map(|(x, _)| x).min().unwrap(),
        *l_rock.iter().map(|(x, _)| x).max().unwrap(),
        *l_rock.iter().map(|(_, y)| y).max().unwrap(),
        *l_rock.iter().map(|(_, y)| y).min().unwrap()
      ),
      Rock(
        vert_rock.clone(),
        *vert_rock.iter().map(|(x, _)| x).min().unwrap(),
        *vert_rock.iter().map(|(x, _)| x).max().unwrap(),
        *vert_rock.iter().map(|(_, y)| y).max().unwrap(),
        *vert_rock.iter().map(|(_, y)| y).min().unwrap()
      ),
      Rock(
        square_rock.clone(),
        *square_rock.iter().map(|(x, _)| x).min().unwrap(),
        *square_rock.iter().map(|(x, _)| x).max().unwrap(),
        *square_rock.iter().map(|(_, y)| y).max().unwrap(),
        *square_rock.iter().map(|(_, y)| y).min().unwrap()
      ),
    ]
  }

  fn left(&self) -> i64 {
    self.1
  }

  fn right(&self) -> i64 {
    self.2
  }

  fn top(&self) -> i64 {
    self.3
  }

  fn bottom(&self) -> i64 {
    self.4
  }

  fn collides_with(&self, rocks: &BTreeSet<(i64, i64)>, (x, y): (i64, i64)) -> bool {
    self.0.iter().any(|(rx, ry)| rocks.contains(&(x + rx, y + ry)))
  }
}

pub fn one() {
  let input = include_str!("input.txt").trim();

  let mut board = Board::new(7);
  let rocks = Rock::types();
  let mut rocks = rocks.iter().cycle();

  let mut added_rocks = 0;
  for (i, c) in input.chars().cycle().enumerate() {
    if board.falling.is_none() {
      if added_rocks == 2022 {
        break;
      }
      board.add_falling(rocks.next().unwrap());
      added_rocks += 1;
    }
    match c {
      '<' => {
        board.fall(Dir::Left);
      },
      '>' => {
        board.fall(Dir::Right);
      },
      c => {
        panic!("Unknown char: {}", c);
      },
    }
  }
  println!("{}", board);

  let mut result = board.height;
  println!("Day 17, part 1: {}", result);
}

pub fn two() {
  let input = include_str!("input.txt").trim();

  let mut board = Board::new(7);
  let rocks = Rock::types();
  let mut rocks = rocks.iter().cycle();

  let start = Instant::now();

  let mut added_rocks = 0i64;
  for (i, c) in input.chars().cycle().enumerate() {
    if board.falling.is_none() {
      if added_rocks == 1000000000000 {
        break;
      }
      if added_rocks % 1000 == 0 {
        print!("Added {}% rocks ", (added_rocks as f64) / 10000000000f64);
        print!("in {}ms ", start.elapsed().as_millis());
        println!("ETA: {:.2}h", (start.elapsed().as_millis() as f64) / (added_rocks as f64) * (1000000000000f64 - added_rocks as f64) / 3_600_000f64);
      }
      let cheat = 589970490;
      if added_rocks == 1000000000000 - 1695 * cheat {
        added_rocks += 1695 * cheat;
        board.height += 2610 * cheat;
        break;
      }
      board.add_falling(rocks.next().unwrap());
      added_rocks += 1;
    }
    match c {
      '<' => {
        board.fall(Dir::Left);
      },
      '>' => {
        board.fall(Dir::Right);
      },
      c => {
        panic!("Unknown char: {}", c);
      },
    }
  }

  let mut result = board.height;
  println!("Day 17, part 2: {}", result);
}

use std::{collections::BTreeSet, ops::RangeInclusive};

type Space = BTreeSet<(i64, i64, i64)>;
type SpaceSize = (
	RangeInclusive<i64>,
	RangeInclusive<i64>,
	RangeInclusive<i64>,
);

fn parse(input: &str) -> (Space, SpaceSize) {
	let mut space = BTreeSet::new();
	let mut min_x = 1;
	let mut max_x = 1;
	let mut min_y = 1;
	let mut max_y = 1;
	let mut min_z = 1;
	let mut max_z = 1;
	for line in input.lines() {
		let mut sides = line.split(",").map(|s| s.parse::<i64>().unwrap());
		let x = sides.next().unwrap();
		let y = sides.next().unwrap();
		let z = sides.next().unwrap();
		space.insert((x, y, z));
		min_x = min_x.min(x);
		max_x = max_x.max(x);
		min_y = min_y.min(y);
		max_y = max_y.max(y);
		min_z = min_z.min(z);
		max_z = max_z.max(z);
	}
	let space_size = (min_x..=max_x, min_y..=max_y, min_z..=max_z);

	(space, space_size)
}

fn is_reachable(space: &Space, space_size: &SpaceSize, coord: (i64, i64, i64)) -> bool {
	let mut queue = vec![coord];
	let mut visited = BTreeSet::new();
	while let Some((x, y, z)) = queue.pop() {
		if visited.contains(&(x, y, z)) {
			continue;
		}
		visited.insert((x, y, z));
		if !space_size.0.contains(&x) || !space_size.1.contains(&y) || !space_size.2.contains(&z) {
			return true;
		}
		if !space.contains(&(x, y, z)) {
			queue.push((x - 1, y, z));
			queue.push((x, y - 1, z));
			queue.push((x, y, z - 1));
			queue.push((x + 1, y, z));
			queue.push((x, y + 1, z));
			queue.push((x, y, z + 1));
		}
	}
	false
}

pub fn one() {
	let input = include_str!("input.txt");
	let (space, space_size) = parse(input);

	let mut result = 0;
	for x in space_size.0.clone() {
		for y in space_size.1.clone() {
			for z in space_size.2.clone() {
				if space.contains(&(x, y, z)) {
					if !space.contains(&(x - 1, y, z)) {
						result += 1;
					}
					if !space.contains(&(x, y - 1, z)) {
						result += 1;
					}
					if !space.contains(&(x, y, z - 1)) {
						result += 1;
					}
					if !space.contains(&(x + 1, y, z)) {
						result += 1;
					}
					if !space.contains(&(x, y + 1, z)) {
						result += 1;
					}
					if !space.contains(&(x, y, z + 1)) {
						result += 1;
					}
				}
			}
		}
	}
	println!("Day 18, part 1: {}", result);
}

pub fn two() {
	let input = include_str!("input.txt");
	let (space, space_size) = parse(input);

	let mut result = 0;
	for x in space_size.0.clone() {
		for y in space_size.1.clone() {
			for z in space_size.2.clone() {
				if space.contains(&(x, y, z)) {
					if is_reachable(&space, &space_size, (x - 1, y, z)) {
						result += 1;
					}
					if is_reachable(&space, &space_size, (x, y - 1, z)) {
						result += 1;
					}
					if is_reachable(&space, &space_size, (x, y, z - 1)) {
						result += 1;
					}
					if is_reachable(&space, &space_size, (x + 1, y, z)) {
						result += 1;
					}
					if is_reachable(&space, &space_size, (x, y + 1, z)) {
						result += 1;
					}
					if is_reachable(&space, &space_size, (x, y, z + 1)) {
						result += 1;
					}
				}
			}
		}
	}
	println!("Day 18, part 2: {}", result);
}

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay18_parsing-8   	     866	   1396972 ns/op
BenchmarkDay18_part1-8     	    1291	    909796 ns/op
BenchmarkDay18_part2-8     	     216	   5496644 ns/op
PASS
ok  	aoc2022	4.377s

import re
import itertools

def bfs(l):
    visited = dict()
    while l:
        node, dist = l.pop(0)
        if node in visited: continue
        visited[node] = dist
        l += [(t, dist + 1) for t, _ in to[node]]
    return visited

def flow(path, depth):
    return sum([rate[n] * (depth - t) for n, t in path if t < depth])

def join_solutions(d1, d2, depth):
    for d in [d2, {k: min(d1[k],d2[k]) for k in set(d1) & set(d2)}]:
        d1.update(d)
    return flow(d1.items(), depth)

start, to, rate = 'AA', dict(), dict()

for line in open("input16").readlines():
    l = line.strip()
    m = re.match("Valve ([A-Z][A-Z]).*=(\d+).*valves? (.*)", l)
    rate[m[1]] = int(m[2])
    to[m[1]] = [(n, 1) for n in m[3].split(', ')]

valves = [n for n,r in rate.items() if r or r == start]
kgraph = {node:{n:d for n,d in bfs([(node, 0)]).items() if rate[n] and n != node}
          for node in to if rate[node] or node == start }

def open_valves(node, time, unopened, order, depth):
    if time >= depth or not unopened:
        return [order]
    time += 1
    l = []
    dists = kgraph[node]
    for i, u in enumerate(unopened):
        d = dists[u]
        if time + d < depth:
            l += open_valves(u, time + d, unopened[:i] + unopened[i+1:], order + [(u, time + d)], depth)
    return l if l else [order]

print(max([flow(p, 30) for p in open_valves(start, 0, valves, [(start, 0)], 30) ]),
      max([join_solutions(dict(m), dict(e), 26)
           for m, e in itertools.combinations_with_replacement(
                   open_valves(start, 0, valves, [(start, 0)], depth), 2)]))

import numpy as np
import itertools as it

shapes = [
    np.where(np.array([[1,1,1,1]]) == 1),
    np.where(np.array([[0,1,0], [1,1,1], [0,1,0]]) == 1), 
    np.where(np.array([[1,1,1], [0,0,1], [0,0,1]]) == 1), 
    np.where(np.array([[1], [1], [1], [1]]) == 1),
    np.where(np.array([[1,1], [1,1]]) == 1)
]

input = open("input17").read().strip()
def direction():
    for d in it.cycle(input):
        yield [-1, 1][d="='>'"]

def drop(n):
    tunnel = np.zeros((200000, 9), dtype=np.int_)
    tunnel[0,:] = tunnel[:,0] = tunnel[:,8] = 1

    shape = it.cycle(shapes)
    dirs = direction()
    for i in range(1, n + 1):
        height = max(np.where(tunnel[:,1:8] != 0)[0])
        x, y, s = 3, height + 4, next(shape)
        while True:
            if not any(tunnel[s[0] + y, s[1] + (x + (d := next(dirs)))]): x += d
            if any(tunnel[s[0] + (y - 1), s[1] + x]): break
            y -= 1
        tunnel[s[0] + y, s[1] + x] = i
    return tunnel

tunnel = drop(2022)
one = max(np.where(tunnel[:,1:8] != 0)[0])

def find_cycle(t):
    end = max(np.where(tunnel[:,1:8] != 0)[0]) // 2
    for i in range(2, end):
        diff = tunnel[end - i:end + 1, 1:8] - tunnel[end - i - i:end - i + 1, 1:8]
        rock_diff = np.max(diff)
        diff[diff != 0] -= rock_diff
        if np.all(diff == 0):
            return i, rock_diff

def find_start(tunnel, length):
    start = length
    while start:
        diff = (tunnel[start + length: start + length + length + 1, 1:8] -
                tunnel[start          :start + length + 1,          1:8])
        diff[diff != 0] -= np.max(diff)
        if np.any(diff != 0):
            return start, np.max(tunnel[:start])
        start -= 1

tunnel = drop(len(input) * len(shapes))

cycle_height, cycle_rocks = find_cycle(tunnel)
start_height, start_rocks = find_start(tunnel, cycle_height)

cycles    = (1000000000000 - start_rocks) // cycle_rocks
remainder = (1000000000000 - start_rocks) % cycle_rocks
two = cycles * cycle_height + max(np.where(tunnel == (remainder + start_rocks))[0])
print(one, two)

import numpy as np

offset = np.array([[ 1, 0, 0], [-1, 0, 0],
                   [ 0, 1, 0], [ 0,-1, 0],
                   [ 0, 0, 1], [ 0, 0,-1]])

def neighbors(point):
    return a[tuple((point + offset).T)]

input = np.loadtxt("input18", dtype=np.int_, delimiter=',')
input += (np.min(input) == 0)
a = np.zeros([np.max(input) + 2] * 3, dtype=np.int_)
a[tuple(input.T)] = 1

one = sum([6 - sum(neighbors(i)) for i in input])

a[0,:,:] = a[:,0,:] = a[:,:,0] = a[-1,:,:] = a[:,-1,:] = a[:,:,-1] = 2
loop = True
while loop:
    loop = False
    for p in zip(*np.where(a == 0)):
        if np.any(neighbors(p) == 2):
            a[p] = 2
            loop = True
a //= 2
two = sum([sum(neighbors(i)) for i in input])
print(one, two)

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay17_parse-8   	  116707	      9590 ns/op	   46584 B/op	      16 allocs/op
BenchmarkDay17_part1-8   	    3085	    440392 ns/op	  389655 B/op	    3387 allocs/op
BenchmarkDay17_part2-8   	    2271	    529469 ns/op	  389229 B/op	    3385 allocs/op
PASS
ok  	aoc2022	3.987s

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay19_parsing-8   	       7	 147709095 ns/op	523019190 B/op	 3356773 allocs/op
BenchmarkDay19_part1-8     	       7	 148290434 ns/op	523016699 B/op	 3356752 allocs/op
BenchmarkDay19_part2-8     	       1	2395778125 ns/op	15586308136 B/op	77265436 allocs/op
PASS
ok  	aoc2022	4.904s

use std::cmp;
use rayon::prelude::*;

#[derive(Debug, Copy, Clone)]
struct Pos {
    x: i32,
    y: i32,
    range: i32,
}

fn main() {
    let input = include_str!("./input.txt");
    let mut sensor_list = vec![];
    let mut beacon_list = vec![];
    for line in input.lines() {
        let split: Vec<&str> = line.split(" ").collect();
        let s_str_x: Vec<&str> = split[2].split("=").collect();
        let s_str_x: Vec<&str> = s_str_x[1].split(",").collect();
        let s_x = s_str_x[0].parse::<i32>().unwrap();
        let s_str_y: Vec<&str> = split[3].split("=").collect();
        let s_str_y: Vec<&str> = s_str_y[1].split(":").collect();
        let s_y = s_str_y[0].parse::<i32>().unwrap();
        let b_str_x: Vec<&str> = split[8].split("=").collect();
        let b_str_x: Vec<&str> = b_str_x[1].split(",").collect();
        let b_x = b_str_x[0].parse::<i32>().unwrap();
        let b_str_y: Vec<&str> = split[9].split("=").collect();
        let b_y = b_str_y[1].parse::<i32>().unwrap();
        let sensor: Pos = Pos {
            x: s_x,
            y: s_y,
            range: manhattan_distance(s_x, s_y, b_x, b_y),
        };
        let beacon: Pos = Pos {
            x: b_x,
            y: b_y,
            range: 0,
        };
        sensor_list.push(sensor);
        beacon_list.push(beacon);
    }

    const X_OFFSET: usize = 1236383; // Biggest negative x beacon position
    const DIMENSIONS: usize = 4000000;
    const Y_FOR_PART_1: i32 = 2000000;
    const ROW_SIZE: usize = 5625609; //Max sensor.x + sensor.range; Magic number for optimization

    let mut row = vec![false; ROW_SIZE];

    for sensor in sensor_list.as_slice() {
        for x in (0 as usize)..row.len() {
            if manhattan_distance(
                sensor.x + X_OFFSET as i32,
                sensor.y,
                x as i32,
                Y_FOR_PART_1 as i32,
            ) <= sensor.range
            {
                row[x as usize] = true;
            }
        }
    }

    for beacon in beacon_list.as_slice() {
        if (beacon.y as i32) == Y_FOR_PART_1 {
            row[(beacon.x + X_OFFSET as i32) as usize] = false;
        }
    }
    for sensor in sensor_list.as_slice() {
        if (sensor.y as i32) == Y_FOR_PART_1 {
            row[(sensor.x + X_OFFSET as i32) as usize] = false;
        }
    }

    let mut count = 0;
    for j in 0_usize..row.len() {
        if row[j] {
            count += 1;
        }
    }
    println!("Part 1: {}", count);

    (0..DIMENSIONS).into_par_iter().for_each(|y| {
        let mut row = vec![false; ROW_SIZE];
        for sensor in sensor_list.as_slice() {
            if y as i32 >= sensor.y - sensor.range && y as i32 <= sensor.y + sensor.range {
                let diff = sensor.range - (sensor.y-y as i32).abs();
                let min_range = cmp::max(0, sensor.x - diff) as usize;
                let max_range = cmp::min(sensor.x + diff +1, DIMENSIONS as i32) as usize;
                row[min_range..max_range].fill(true);
            }
        }
 
        if row[0..DIMENSIONS].iter().all(|&x| x)
        {
            return;
        }

        for x in 0..DIMENSIONS {
            if !row[x] {
                let res: u64 = ((x * 4000000) + y) as u64;
                println!("Part 2: {}", res);
                return;
            }
        }
    });

}

fn manhattan_distance(x1: i32, y1: i32, x2: i32, y2: i32) -> i32 {
    return (x1 - x2).abs() + (y1 - y2).abs();
}

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay20_parse-8   	    7798	    153661 ns/op	  248266 B/op	    5016 allocs/op
BenchmarkDay20_part1-8   	      98	  11837133 ns/op	   44899 B/op	      52 allocs/op
BenchmarkDay20_part2-8   	       9	 138439069 ns/op	  304522 B/op	    5018 allocs/op

goos: darwin
goarch: arm64
pkg: aoc2022
BenchmarkDay21_parse-10    	     866	   1224673 ns/op	  653776 B/op	   17113 allocs/op
BenchmarkDay21_part1-10    	   15974	     74727 ns/op	      49 B/op	       1 allocs/op
BenchmarkDay21_part2-10    	     183	   6519531 ns/op	    4637 B/op	      98 allocs/op

func MyNumberForRootMonkeyMatch(mm MonkeyMatch, rootArgs string) int64 {
	result := make(chan int64)
	iYell := make(chan int64)
	go rootMatcher(mm, result, rootArgs)
	mm[MyName] = func(MonkeyMatch) int64 { return <-iYell }
	// Find range, xA..xB (xA>xB), where the root monkey function change sign
	// iYell <- 0
	// xBIsPositive := isPositive(<-result)
	// xA := int64(1)
	// xB := int64(0)
	// for {
	// 	iYell <- int64(xA)
	// 	diff := <-result
	// 	if isPositive(diff) != xBIsPositive {
	// 		xB = xA / 2
	// 		break
	// 	}
	// 	xA *= 2
	// }
	// Answer is in range xA..xB
	for {
		//n := (xA-xB)/2 + xB
		n := int64(302)
		iYell <- n
		diff := <-result
		if diff == 0 {
			return n
		}
		// if isPositive(diff) == xBIsPositive {
		// 	// n on same "side" as xB
		// 	xB = n + 1
		// } else {
		// 	// n on same "side" as xA
		// 	xA = n - 1
		// }
	}
}

			case "/":
				mm[monkeyName] = func(mm MonkeyMatch) int64 {
					a := mm[names[0]](mm)
					b := mm[names[1]](mm)
					return a / b
				}

import ast

def evaluate(monkey):
    s = expressions[monkey]
    op = s.split()
    if len(op) == 3:
        s = "(" + evaluate(op[0]) + op[1] + evaluate(op[2]) + ")"
        try:
            s = str(int(eval(s)))
        except:
            pass
        expressions[monkey] = s
    return s

class Visitor(ast.NodeVisitor):
    def __init__(self, v):
        self.v = v
        super().__init__()
        
    def visit_BinOp(self, node):
        left = right = None
        if isinstance(node.left,  ast.Constant): left = node.left.value
        if isinstance(node.right, ast.Constant): right = node.right.value
        if isinstance(node.op,    ast.Add):  self.v  -= left or right
        if isinstance(node.op,    ast.Mult): self.v //= left or right
        if isinstance(node.op,    ast.Sub):  self.v   = left -  self.v if left else self.v + right
        if isinstance(node.op,    ast.Div):  self.v   = left // self.v if left else self.v * right
        ast.NodeVisitor.generic_visit(self, node)

expressions = dict([l.strip().split(": ") for l in open("input21").readlines()])

one = evaluate("root")


expressions = dict([l.strip().split(": ") for l in open("input21").readlines()])
expressions["humn"] = "humn"

e = expressions["root"].split()
v = Visitor(eval(evaluate(e[2])))
v.visit(ast.parse(evaluate(e[0])))
two = v.v

print(one, two)