import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

List<List<Point<num>>> getBots(List<String> lines) {
  var bots = lines
      .map((e) => RegExp(r'(-?\d+)')
          .allMatches(e)
          .map((m) => int.parse(m.group(0)!))
          .toList())
      .map((p) => [Point<num>(p[0], p[1]), Point<num>(p[2], p[3])])
      .toList();
  return bots;
}

// Solve system of congruences using the Chinese Remainder Theorem
int crt(int r1, int m1, int r2, int m2) {
  int inv = m1.modInverse(m2);
  int solution = (r1 + m1 * ((r2 - r1) % m2) * inv) % (m1 * m2);
  return (solution + (m1 * m2)) % (m1 * m2); // Ensure the result is positive
}

void moveBy(List<List<Point<num>>> bots, int t, int w, int h) {
  for (var b in bots) {
    b.first += b.last * t;
    b.first = Point(b.first.x % w, b.first.y % h);
  }
}

part1(List<String> lines, [width = 11, height = 7]) {
  var bots = getBots(lines);
  moveBy(bots, 100, width, height);
  var w = width ~/ 2, h = height ~/ 2;
  var quads = Multiset.fromIterable(
      bots.map((b) => (b.first.x.compareTo(w), b.first.y.compareTo(h))));
  return [(-1, -1), (-1, 1), (1, -1), (1, 1)]
      .map((k) => quads[k])
      .reduce((s, t) => s * t);
}

part2(List<String> lines, [width = 101, height = 103]) {
  var bots = getBots(lines);
  var t = 0;
  int rmax = 0, cmax = 0, rt = 0, ct = 0;
  while (t < width * height) {
    t += 1;
    moveBy(bots, 1, width, height);
    var r = Multiset.fromIterable(bots.map((e) => e.first.x)).counts.max;
    var c = Multiset.fromIterable(bots.map((e) => e.first.y)).counts.max;
    if (r > rmax) (rmax, rt) = (r, t);
    if (c > cmax) (cmax, ct) = (c, t);
  }
  t = crt(rt, width, ct, height);
  bots = getBots(lines);
  moveBy(bots, t, width, height);
  // printGrid(height, width, bots);
  return t;
}

  

 nim

    
type
  Vec2 = tuple[x,y: int]
  Robot = object
    pos, vel: Vec2

var
  GridRows = 101
  GridCols = 103

proc examine(robots: seq[Robot]) =
  for y in 0..<GridCols:
    for x in 0..<GridRows:
      let c = robots.countIt(it.pos == (x, y))
      stdout.write if c == 0: '.' else: char('0'.ord + c)
    stdout.write '\n'
    stdout.flushFile()

proc solve(input: string): AOCSolution[int, int] =
  var robots: seq[Robot]
  for line in input.splitLines():
    let parts = line.split({' ',',','='})
    robots.add Robot(pos: (parts[1].parseInt,parts[2].parseInt),
                     vel: (parts[4].parseInt,parts[5].parseInt))

  block p1:
    var quads: array[4, int]
    for robot in robots:
      let
        newX = (robot.pos.x + robot.vel.x * 100).euclmod GridRows
        newY = (robot.pos.y + robot.vel.y * 100).euclmod GridCols
        relRow = cmp(newX, GridRows div 2)
        relCol = cmp(newY, GridCols div 2)
      if relRow == 0 or relCol == 0: continue
      inc quads[int(relCol>0)*2 + int(relRow>0)]

    result.part1 = quads.foldl(a*b)

  block p2:
    if GridRows != 101: break p2
    var interesting = 99
    var interval = 101

    var i = 0
    while true:
      for robot in robots.mitems:
        robot.pos.x = (robot.pos.x + robot.vel.x).euclmod GridRows
        robot.pos.y = (robot.pos.y + robot.vel.y).euclmod GridCols
      inc i

      if i == interesting:
        robots.examine()
        echo "Iteration #", i, "; Do you see an xmas tree?[N/y]"
        if stdin.readLine().normalize() == "y":
          result.part2 = i
          break
        interesting += interval


  

    
import numpy as np
from pathlib import Path
from collections import Counter
cwd = Path(__file__).parent


def parse_input(file_path):
  with file_path.open("r") as fp:
    robot_info = fp.readlines()

  _split = lambda x,p: [int(x.split(' ')[p].split(',')[0].split('=')[-1]),
                        int(x.split(' ')[p].split(',')[-1])]

  robot_pos = np.array([_split(x, 0) for x in robot_info])
  robot_vel = np.array([_split(x, 1) for x in robot_info])

  return robot_pos, robot_vel


def solve_problem1(file_name, nrows, ncols, nmoves):

  robot_pos, robot_vel = parse_input(Path(cwd, file_name))

  final_pos = robot_pos + nmoves*robot_vel
  final_pos = [(x[0]%ncols, x[1]%nrows) for x in list(final_pos)]

  pos_counts = Counter(final_pos)
  coords = np.array(list(pos_counts.keys()))[:,::-1] #x is cols, y is rows
  coords = tuple(coords.T)

  grid = np.zeros((nrows, ncols), dtype=int)
  grid[coords] += list(pos_counts.values())

  counts = [np.sum(grid[:nrows>>1, :ncols>>1]),
            np.sum(grid[:nrows>>1, -(ncols>>1):]),
            np.sum(grid[-(nrows>>1):, :ncols>>1]),
            np.sum(grid[-(nrows>>1):, -(ncols>>1):])]

  return int(np.prod(counts))


def solve_problem2(file_name, nrows, ncols):

  robot_pos, robot_vel = parse_input(Path(cwd, file_name))

  grid = np.zeros((nrows, ncols), dtype=object)

  # update all positions in a vectorised manner
  final_positions = robot_pos[None, :, :] + np.arange(1,10000)[:,None,None]*robot_vel[None,:,:]
  final_positions[:,:,0] = final_positions[:,:,0]%ncols
  final_positions[:,:,1] = final_positions[:,:,1]%nrows

  for s in range(final_positions.shape[0]):
    grid[:,:] = 0

    final_pos = map(tuple, tuple(final_positions[s,:,:]))

    pos_counts = Counter(final_pos)
    coords = np.array(list(pos_counts.keys()))[:,::-1] #x is cols, y is rows
    coords = tuple(coords.T)

    grid[coords] += list(pos_counts.values())

    xmarg = np.sum(grid, axis=0)
    tops = set(np.argsort(xmarg)[::-1][:10])
    p_near_center = len(tops.intersection(set(range((ncols>>1)-5, (ncols>>1) + 6))))/10

    ymarg = np.sum(grid, axis=1)
    ysym = 1 - abs(ymarg[:nrows>>1].sum() - ymarg[nrows>>1:].sum())/ymarg.sum()

    if p_near_center>0.5 and ysym<0.8:
      return s+1

  

    
load 'regex'
data_file_name =: '14.data'
raw =: cutopen fread data_file_name
NB. a b sublist y gives elements [a..a+b) of y
sublist =: ({~(+i.)/)~"1 _
parse_line =: monad define
   match =: 'p=(-?[[:digit:]]+),(-?[[:digit:]]+) v=(-?[[:digit:]]+),(-?[[:digit:]]+)' rxmatch y
   2 2 $ ". y sublist~ }. match
)
initial_state =: parse_line"1 > raw
'positions velocities' =: ({."2 ; {:"2) initial_state
steps =: 100
size =: 101 103
step =: (size & |) @: +
travel =: step (steps & *)
quadrant =: (> & (<. size % 2)) - (< & (<. size % 2))
final_quadrants =: quadrant"1 @: travel"1
quadrant_ids =: 4 2 $ 1 1 _1 1 1 _1 _1 _1
result1 =: */ +/"1 quadrant_ids -:"1/ positions final_quadrants velocities

render =: monad define
   |: 'O' (<"1 y)} size $ '.'
)
pair_distances =: monad : 'y (| @: j./ @: -/"1)/ y'
loop =: dyad define
   positions =. positions step"1 (velocities * x)
   for_i. i. 1000 do.
      time_number =. x + i * y
      mean_distance =. (+/ % #) , pair_distances positions
      if. mean_distance < 50 do.
         (render positions) (1!:2) 2
         (": time_number, mean_distance) (1!:2) 2
         (6!:3) 1
      end.
      if. mean_distance < 35 do. break. end.
      positions =. positions step"1 (velocities * y)
   end.
   time_number

result2 =: 11 loop 101

  

 uiua

    
&rs ∞ &fo "input-14.txt"
⊜(↯2_2⋕regex"-?\\d+")≠@\n.
0 # number of seconds to start at
0_0
⍢(◡(≡(⍜⌵(◿101_103)+°⊟⍜⊡₁×):)◌
  ◿[101_103]≡+[101_103]
  ⊙+₁
| ≠⊙(⧻◴)⧻.)
⊙◌◌
-₁

  

 haskell

    
import Data.Bifunctor
import Data.Char
import qualified Data.Set as S
import Data.Functor
import Data.List
import Control.Monad
import Text.ParserCombinators.ReadP
import Data.IORef

bounds = (101, 103)

parseInt :: ReadP Int
parseInt = (*) <$> option 1 (char '-' $> (-1)) <*> (read <$> munch1 isDigit)
parseTuple = (,) <$> parseInt <*> (char ',' *> parseInt)
parseRow = (,) <$> (string "p=" *> parseTuple) <*> (string " v=" *> parseTuple)
parse = fst . last . readP_to_S (endBy parseRow (char '\n'))

move t (x, y) (vx, vy) = bimap (mod (x + vx * t)) (mod (y + vy * t)) bounds

getQuadrant :: (Int, Int) -> Int
getQuadrant (x, y)
    | x == mx || y == my = 0
    | otherwise = case (x > mx, y > my) of
        (True, True) -> 1
        (True, False) -> 2
        (False, True) -> 3
        (False, False) -> 4
  where
    (mx, my) = bimap (`div` 2) (`div` 2) bounds

step (x, y) (vx, vy) = (,(vx, vy)) $ bimap (mod (x + vx)) (mod (y + vy)) bounds

main = do
    p <- parse <$> readFile "input14"

    print . product . fmap length . group . sort . filter (/=0) . fmap (getQuadrant . uncurry (move 100)) $ p

    let l = iterate (fmap (uncurry step)) p

    current <- newIORef 0
    actions <- lines <$> getContents
    forM_ actions $ \a -> do
        case a of
            "" -> modifyIORef current (+1)
            "+" -> modifyIORef current (+1)
            "-" -> modifyIORef current (subtract 1)
            n -> writeIORef current (read n)
        pos <- readIORef current
        putStr "\ESC[2J" -- clear screen
        print pos
        visualize $ fst <$> l !! pos

visualize :: [(Int, Int)] -> IO ()
visualize pos = do
    let p = S.fromList pos
    forM_ [1..(snd bounds)] $ \y -> do
        forM_ [1..(fst bounds)] $ \x -> do
            putChar $ if S.member (x, y) p then '*' else '.'
        putChar '\n'