use euclid::default::*;
use regex::Regex;

fn parse(input: &str) -> Vec<(Point2D<i32>, Vector2D<i32>)> {
    let re = Regex::new(r"p=(\d+),(\d+) v=(-?\d+),(-?\d+)").unwrap();
    re.captures_iter(input)
        .map(|cap| {
            let (_, [p0, p1, v0, v1]) = cap.extract();
            (
                Point2D::new(p0.parse().unwrap(), p1.parse().unwrap()),
                Vector2D::new(v0.parse().unwrap(), v1.parse().unwrap()),
            )
        })
        .collect()
}

const ROOM: Size2D<i32> = Size2D::new(101, 103);
const TIME: i32 = 100;

fn part1(input: String) {
    let robots = parse(&input);
    let new_pos: Vec<Point2D<i32>> = robots.iter()
        .map(|&(p, v)| (p + v * TIME).rem_euclid(&ROOM))
        .collect();

    assert_eq!(ROOM.width % 2, 1);
    assert_eq!(ROOM.height % 2, 1);
    let mid_x = ROOM.width / 2;
    let mid_y = ROOM.height / 2;
    
    let mut q = [0u32; 4];
    for p in new_pos {
        use std::cmp::Ordering::*;
        match (p.x.cmp(&mid_x), p.y.cmp(&mid_y)) {
            (Less, Less) => q[0] += 1,
            (Greater, Less) => q[1] += 1,
            (Less, Greater) => q[2] += 1,
            (Greater, Greater) => q[3] += 1,
            _ => {}
        };
    }
    let prod = q[0] * q[1] * q[2] * q[3];
    println!("{prod}");
}

fn print_map(map: &[Vec<bool>]) {
    for row in map {
        for p in row {
            if *p { print!("#") } else { print!(".") }
        }
        println!();
    }
    println!();
}


fn part2(input: String) {
    let mut robots = parse(&input);
    let mut map = vec![vec![false; ROOM.width as usize]; ROOM.height as usize];
    for i in 1.. {
        let mut overlap = false;
        for (p, v) in &mut robots {
            *p = (*p + *v).rem_euclid(&ROOM);
            if map[p.y as usize][p.x as usize] {
                // Found two robots on the same spot,
                // which is used as a heuristic for detecting the easter egg.
                overlap = true;
            } else {
                map[p.y as usize][p.x as usize] = true;
            }
        }
        if !overlap {
            print_map(&map);
            println!("Round: {i}");
            break;
        }
        for row in &mut map {
            row.fill(false);
        }
    }
}

util::aoc_main!();

import Data.Maybe
import Text.ParserCombinators.ReadP
import qualified Data.Map.Strict as M

type Coord = (Int, Int)
type Robot = (Coord, Coord)

int :: ReadP Int
int = fmap read $ many1 $ choice $ map char $ '-' : ['0' .. '9']

coord :: ReadP Coord
coord = (,) <$> int <*> (char ',' *> int)

robot :: ReadP Robot
robot = (,) <$> (string "p=" *> coord) <*> (string " v=" *> coord)

robots :: ReadP [Robot]
robots = sepBy robot (char '\n')

simulate :: Coord -> Int -> Robot -> Coord
simulate (x0, y0) t ((x, y), (vx, vy)) =
    ((x + t * vx) `mod` x0, (y + t * vy) `mod` y0)

quadrant :: Coord -> Coord -> Maybe Int
quadrant (x0, y0) (x, y) = case (compare (2*x + 1) x0, compare (2*y + 1) y0) of
    (LT, LT) -> Just 0
    (LT, GT) -> Just 1
    (GT, LT) -> Just 2
    (GT, GT) -> Just 3
    _        -> Nothing

freqs :: (Foldable t, Ord a) => t a -> M.Map a Int
freqs = foldr (\x -> M.insertWith (+) x 1) M.empty

solve :: Coord -> Int -> [Robot] -> Int
solve grid t = product . freqs . catMaybes . map (quadrant grid . simulate grid t)

showGrid :: Coord -> [Coord] -> String
showGrid (x0, y0) cs = unlines
    [ [if (x, y) `M.member` m then '#' else ' ' | x <- [0 .. x0]]
    | let m = M.fromList [(c, ()) | c <- cs]
    , y <- [0 .. y0]
    ]

main :: IO ()
main = do
    rs <- fst . last . readP_to_S robots <$> getContents
    let g = (101, 103)
    print $ solve g 100 rs
    sequence_
        [ writeFile ("tree_" ++ show t) $ showGrid g $ map (simulate g t) rs
        | t <- [0 .. 10000]
        ]

import Control.Arrow
import Data.Bifunctor hiding (first, second)
import Control.Monad

import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Maybe as Maybe

parse :: String -> [((Int, Int), (Int, Int))]
parse = map (break (== ' ') >>> second (drop 1) >>> join bimap (drop 2) >>> join bimap (break (== ',')) >>> join bimap (second (drop 1)) >>> join bimap (join bimap read)) . filter (/= "") . lines

moveRobot ((px, py), (vx, vy)) t = (px + t * vx, py + t * vy)

constrainCoordinates (mx, my) (px, py) = (px `mod` mx, py `mod` my)

coordinateConstraints = (101, 103)

robotQuadrant (mx, my) (px, py)
        | px > middleX && py < middleY = Just 1 -- upper right
        | px > middleX && py > middleY = Just 2 -- lower right
        | px < middleX && py > middleY = Just 3 -- lower left
        | px < middleX && py < middleY = Just 4 -- upper left
        | otherwise = Nothing
        where
                middleX = (mx `div` 2)
                middleY = (my `div` 2)

countQuadrants (q1, q2, q3, q4) 1 = (succ q1, q2, q3, q4)
countQuadrants (q1, q2, q3, q4) 2 = (q1, succ q2, q3, q4)
countQuadrants (q1, q2, q3, q4) 3 = (q1, q2, succ q3, q4)
countQuadrants (q1, q2, q3, q4) 4 = (q1, q2, q3, succ q4)

part1 = map (flip moveRobot 100 >>> constrainCoordinates coordinateConstraints)
        >>> map (robotQuadrant coordinateConstraints)
        >>> Maybe.catMaybes
        >>> foldl (countQuadrants) (0, 0, 0, 0)
        >>> \ (a, b, c, d) -> a * b * c * d

showMaybe (Just i) = head . show $ i
showMaybe Nothing  = ' '

buildRobotString robotMap = [ [ showMaybe (robotMap Map.!? (x, y))  | x <- [0..fst coordinateConstraints] ] | y <- [0..snd coordinateConstraints]]

part2 rs t = map (flip moveRobot t >>> constrainCoordinates coordinateConstraints)
        >>> flip zip (repeat 1)
        >>> Map.fromListWith (+)
        >>> buildRobotString
        $ rs

showConstellation (i, s) = do
        putStrLn (replicate 49 '#' ++ show i ++ replicate 49 '#')
        putStrLn $ s

main = do
        f <- getContents
        let i = parse f
        print $ part1 i

        let constellations = map (id &&& (part2 i >>> List.intercalate "\n")) . filter ((== 86) . (`mod` 103)) $ [0..1000000]
        mapM_ showConstellation constellations
        print 7502

import fs from "fs";

type Coord = {x: number, y: number};
type Robot = {start: Coord, velocity: Coord};

const SIZE: Coord = {x: 101, y: 103};

const input: Robot[] = fs.readFileSync("./14/input.txt", "utf-8")
    .split(/[\r\n]+/)
    .map(row => /p=(-?\d+),(-?\d+)\sv=(-?\d+),(-?\d+)/.exec(row))
    .filter(matcher => matcher != null)
    .map(matcher => {
        return {
            start: {x: parseInt(matcher[1]), y: parseInt(matcher[2])},
            velocity: {x: parseInt(matcher[3]), y: parseInt(matcher[4])}
        };
    });

console.info("Part 1: " + safetyFactor(input.map(robot => calculatePosition(robot, SIZE, 100)), SIZE));

// Part 2
// Turns out the Christmas tree is arranged the first time none of the robots are overlapping
for (let i = 101; true; i++) {
    const positions = input.map(robot => calculatePosition(robot, SIZE, i));
    if (positions.every((position, index, arr) => arr.findIndex(pos => pos.x === position.x && pos.y === position.y) === index)) {
        console.info("Part 2: " + i);
        break;
    }
}

function calculatePosition(robot: Robot, size: Coord, seconds: number): Coord {
    return {
        x: ((robot.start.x + robot.velocity.x * seconds) % size.x + size.x) % size.x,
        y: ((robot.start.y + robot.velocity.y * seconds) % size.y + size.y) % size.y
    };
}

function safetyFactor(positions: Coord[], size: Coord): number {
    const midX = Math.floor(size.x / 2);
    const midY = Math.floor(size.y / 2);

    let quadrant0 = 0; // Top-left
    let quadrant1 = 0; // Top-right
    let quadrant2 = 0; // Bottom-left
    let quadrant3 = 0; // Bottom-right

    for (const {x,y} of positions) {
        if (x === midX || y === midY) { continue; }

        if (x < midX && y < midY) { quadrant0++; }
        else if (x > midX && y < midY) { quadrant1++; }
        else if (x < midX && y > midY) { quadrant2++; }
        else if (x > midX && y > midY) { quadrant3++; }
    }

    return quadrant0 * quadrant1 * quadrant2 * quadrant3;
}

import Control.Arrow
import Data.Char
import Data.List
import Data.Map qualified as Map
import Data.Maybe
import Text.Parsec

(w, h) = (101, 103)

readInput :: String -> [((Int, Int), (Int, Int))]
readInput = either (error . show) id . parse (robot `endBy` newline) ""
  where
    robot = (,) <$> (string "p=" >> coords) <*> (string " v=" >> coords)
    coords = (,) <$> num <* char ',' <*> num
    num = read <$> ((++) <$> option "" (string "-") <*> many1 digit)

runBots :: [((Int, Int), (Int, Int))] -> [[(Int, Int)]]
runBots = transpose . map botPath
  where
    botPath (p, (vx, vy)) = iterate (incWrap w vx *** incWrap h vy) p
    incWrap s d = (`mod` s) . (+ d)

safetyFactor :: [(Int, Int)] -> Int
safetyFactor = product . Map.fromListWith (+) . map (,1) . mapMaybe quadrant
  where
    cx = w `div` 2
    cy = h `div` 2
    quadrant (x, y)
      | x == cx || y == cy = Nothing
      | otherwise = Just (x `div` (cx + 1), y `div` (cy + 1))

render :: [(Int, Int)] -> [String]
render bots =
  let counts = Map.fromListWith (+) $ map (,1) bots
   in flip map [0 .. h - 1] $ \y ->
        flip map [0 .. w - 1] $ \x ->
          maybe '.' intToDigit $ counts Map.!? (x, y)

isImage :: [String] -> Bool
isImage = (> 4) . length . filter hasRun
  where
    hasRun = any ((> 3) . length) . filter head . group . map (/= '.')

main = do
  positions <- runBots . readInput <$> readFile "input14"
  print . safetyFactor $ positions !! 100
  let (Just (t, image)) = find (isImage . snd) $ zip [0 ..] $ map render positions
  print t
  mapM_ putStrLn image