aoc2025_day9part2.e1

--https://adventofcode.com/2025/day/9
-- Timing on my machine (Intel i7-10710U):
-- When run directly via "e1 prog.e1" ("interpreted" mode):           42.9 seconds
-- When compiled via Racket ("e1 --rkt prog.e1; raco exe prog.rkt"):  14.5 seconds
-- When translated into Python  
--   https://gist.github.com/thedeemon/d8df30420f3e57bcb853250b6c06ab5c
-- Python 3.12.10:                                                   513.5 seconds
-- Python 3.14.2:                                                    262.9 seconds
-- Translated to Swift:                                                2.1 seconds

import String { byLine, splitBy }
import Sort { sortInPlaceBy }
import List { List, Cons, Nil }

type Point { x: Int; y: Int  }

toPoints line = do
  v = line ^splitBy ',' ^map{s => parseInt s ?? (-1)} ^toVector
  Point v[0] v[1]

points = "input9.txt" ^readText ?? "" ^byLine ^map toPoints ^toVector

abs x = if x < 0 then -x else x

area i j = do
  a = points[i]
  b = points[j]
  (abs (a.x-b.x) +1) * (abs (a.y-b.y) + 1)

np = length points

type Border { bx : Int; up : Bool }

lines : Array (List Border)
lines = makeArray 100000 { i => Nil }

drawVertLine x first last goingUp =
  for y in first .. last+1:
    lines[y] := Cons (Border x goingUp) lines[y]

for i in 0..np: do
  j = (i+1) % np
  pi = points[i]; pj = points[j]
  goingUp = pi.y > pj.y
  if pi.x == pj.x then drawVertLine pi.x (min pi.y pj.y) (max pi.y pj.y) goingUp


processLine lst = do
  arr = getIterator lst ^toArray
  sortInPlaceBy { a b => a.bx < b.bx } arr
  iota (length arr) ^filter { i => if i==0 then True else arr[i].up != arr[i-1].up }
    ^map { i => arr[i] } ^toVector

fits st en line =
  iota (length line - 1) ^ any { i => line[i].up && !line[i+1].up && line[i].bx <= st && line[i+1].bx >= en }

spans = lines ^map processLine ^toVector

type Rect { a : Int; b : Int; area : Int }

rectFits r = do
  p1 = points[r.a]; p2 = points[r.b]
  st = min p1.x p2.x; en = max p1.x p2.x
  y0 = min p1.y p2.y; y1 = max p1.y p2.y
  for y in y0 .. y1+1:
    if !(fits st en spans[y]) then break False
  else: True

rects = iota (np-1) ^ map {i => iota (i+1) ^ map {j => Rect j (i+1) (area j (i+1)) }} ^ flatten
          ^filter rectFits ^toArray

sortInPlaceBy { a b => a.area > b.area } rects
rects[0].area ^println