advent-2025/p9/p9.org

Solution to p9, aka the shitshow

Load the data

  (with-temp-buffer
    (insert-file-contents "input")
    (advent/replace-multiple-regex-buffer
     '(("," . " ")
       ("^" . "(")
       ("$" . ")")))
    (goto-char (point-min))
    (insert "(setq data '(")
    (goto-char (point-max))
    (insert "))")
    (eval-buffer))

General preparation; the area is symmetric so I consider only half of the pairs of vertices.

  (defun area (el)
    (let ((a (car el))
  	(b (cdr el)))
      (* (1+ (abs (- (car a) (car b))))
         (1+ (abs (- (cadr a) (cadr b)))))))

  (defun symmetric-pairs (list)
    (apply #'append (--map-indexed (-map (lambda (other) (cons it other))
  				       (-drop (1+ it-index) list))
  				 list)))

This is for part 1. Easy.

  (-max (-map 'area (symmetric-pairs data)))

4737096935

For part 2, we begin by doing some preparation. We collect corners and edges.

  (setq data-prev (-rotate 1 data)
        data-next (-rotate -1 data)
        data-edges (-zip-lists data data-next)
        data-pv (-zip-lists data data-prev data-next))

  (defun normalize (x)
    (if (= x 0) 0
      (/ x (abs x))))

  (defun cornerize (a b)
    (list (normalize (- (car b) (car a)))
          (normalize (- (cadr b) (cadr a)))))

  (defun hor-or-ver (a b)
    (if (= (car a) (car b)) 'vertical
      'horizontal))

  (setq data-corners
        (--map (cons (car it)
                     (cons (cornerize (cadr it) (car it))
                           (cornerize (car it) (caddr it))))
               data-pv))

  (setq data-horizontal-edges (--filter (eq 'horizontal (apply #'hor-or-ver it)) data-edges)
        data-vertical-edges (--filter (eq 'vertical (apply #'hor-or-ver it)) data-edges))

  ;; Let us sort the edges
  (setq data-horizontal-edges (--sort (< (cadar it) (cadar other)) data-horizontal-edges)
        data-vertical-edges (--sort (< (caar it) (caar other)) data-vertical-edges))

We do some sanity check: is there any vertex that is not a corner?

  (--remove (= 0 (advent/dot (cadr it) (cddr it))) data-corners)

No, that's good. Now check if all vertices are distinct.

  (= (length (-distinct data)) (length data))

t

That's good. This eliminates some corner cases. Now examine the orientation; the result can be 1 or -1 if it is 1, then the domain is always to the right of the edges if it is -1, then the domain is always to the left of the edges

  (setq orientation (normalize (apply '- (-map #'cadr (car data-vertical-edges)))))

1

Now we cook up a function to check if a given point X Y is inside or outside

  ;; The next two functions could be sped up by using bisection.
  ;; See if it is necessary

    (defun vertical-edges-up-to (x)
      (--take-while (<= (caar it) x) data-vertical-edges))

    (defun horizontal-edges-up-to (y)
      (--take-while (<= (cadar it) y) data-horizontal-edges))

    (defun vertical-edge-goes-through (edge y)
      (let ((miny (min (cadar edge) (cadadr edge)))
            (maxy (max (cadar edge) (cadadr edge))))
        (and (< miny y) (< y maxy))))

    (defun horizontal-edge-goes-through (edge x)
      (let ((minx (min (caar edge) (caadr edge)))
            (maxx (max (caar edge) (caadr edge))))
        (and (< minx x) (< x maxx))))

    (defun odd-p (n)
      (= 1 (logand n 1)))

    (defun even-p (n)
      (= 0 (logand n 1)))

    (defun inside-p (x y)
      (let* ((horizontal-head (horizontal-edges-up-to y))
             (vertical-head (vertical-edges-up-to x))
             (x (+ x 0.5))
             (y (+ y 0.5))
             (filtered-horizontal-head (--filter (horizontal-edge-goes-through it x) horizontal-head))
             (filtered-vertical-head (--filter (vertical-edge-goes-through it y) vertical-head)))
        (and (odd-p (length filtered-horizontal-head))
             (odd-p (length filtered-vertical-head)))))

Of course it would be too costly to check for every square in the candidate rects, so we first remove rectangles that cannot work for a number of reasons; since vertices are unique, if a vertex sits strictly inside a rectangle, the rectangle must have some bad tiles inside. We call a rect reasonable if such a thing does not happen.

  (setq rects (symmetric-pairs data))

  (defun strictly-contains-p (rect p)
    (let ((minx (min (caar rect) (cadr rect)))
          (maxx (max (caar rect) (cadr rect)))
          (miny (min (cadar rect) (caddr rect)))
          (maxy (max (cadar rect) (caddr rect)))
          (px (car p))
          (py (cadr p)))
      (and (< minx px) (< px maxx)
           (< miny py) (< py maxy))))

  (setq reasonable-rects
        (-remove (lambda (rect) (--any (strictly-contains-p rect it) data)) rects))

  (length reasonable-rects)

Nice, that is an OK number. Since a rectangle is reasonable, possible edges that cut through it would have to do through all of it. We can thus check along the edges only

  (defun whole-rect-inside-p (rect)
  (let ((minx (min (caar rect) (cadr rect)))
        (maxx (max (caar rect) (cadr rect)))
        (miny (min (cadar rect) (caddr rect)))
        (maxy (max (cadar rect) (caddr rect))))
    ;; Check along the minx column and miny row
    (and (--every (inside-p minx it) (-iota (- maxy miny) miny))
         (--every (inside-p it miny) (-iota (- maxx minx) minx)))))

  (setq sorted-reasonable-rects (--sort (> (area it) (area other)) reasonable-rects))

Grab some popcorn, this will take a while

  (let ((num 0))
    (setq largest-good-rect (--first (progn
                                       (message (format "%d" (setq num (1+ num))))
                                       (whole-rect-inside-p it))
                                     sorted-reasonable-rects)))
(area largest-good-rect)

1644094530

what follows is an alternative way… first realize what the shape looks like

  (setq svg-preamble "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>
  <svg
     version=\"1.1\"
     id=\"svg1\"
     width=\"1000\"
     height=\"1000\"
     sodipodi:docname=\"tmp.svg\"
     xmlns=\"http://www.w3.org/2000/svg\"
     xmlns:svg=\"http://www.w3.org/2000/svg\">
    <defs
       id=\"defs1\" />
    <sodipodi:namedview
       id=\"namedview1\"
       pagecolor=\"#ffffff\"
       bordercolor=\"#666666\"
       borderopacity=\"1.0\"
       inkscape:showpageshadow=\"2\"
       inkscape:pageopacity=\"0.0\"
       inkscape:pagecheckerboard=\"0\"
       inkscape:deskcolor=\"#d1d1d1\"
       showgrid=\"false\"
       inkscape:zoom=\"1\"
       inkscape:cx=\"150\"
       inkscape:cy=\"75.067024\"
       inkscape:window-width=\"1000000\"
       inkscape:window-height=\"1000000\"
       inkscape:window-x=\"0\"
       inkscape:window-y=\"0\"
       inkscape:window-maximized=\"1\"
       inkscape:current-layer=\"svg1\" />")

  (defun scale-coordinate  (x)
    (* .01 x))

  (defun draw-svg ()
    (with-temp-buffer
     (let ((minx (-min (-map #'car data)))
           (maxx (-max (-map #'car data)))
           (miny (-min (-map #'cadr data)))
           (maxy (-max (-map #'cadr data))) )
       (insert svg-preamble) ; (format "<svg height=%d width=%d xmlns=\"http://www.w3.org/2000/svg\">" (+ maxy miny) (+ maxx minx))
       (--each data-edges (insert (format "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" style=\"stroke:#000;stroke-width:0.1\"/>\n"
                                         (scale-coordinate (caar it))
                                         (scale-coordinate (cadar it))
                                         (scale-coordinate (caadr it))
                                         (scale-coordinate (cadadr it)))))
       (insert "</svg>")
       )
     (write-file "tmp.svg")))
  (draw-svg)

Oh motherfucker;

Find the two possible vertices

      ;; find the two longest horizontal edges
      (defun edge-width (it)
        (abs (- (caadr it) (caar it))))

      (setq special-two-edges (-take 2 (--sort (> (edge-width it) (edge-width other)) data-horizontal-edges))
            special-two-vertices (--map (list (max (caar it) (caadr it)) (cadar it)) special-two-edges))

      ;; the maximal rectangle will have one of these two as its vertex

      ;; let us now find the height at which the x cuts the outer shape
      (defun vertical-edge-goes-through (edge y)
          (let ((miny (min (cadar edge) (cadadr edge)))
                (maxy (max (cadar edge) (cadadr edge))))
            (and (<= miny y) (<= y maxy))))

        (defun horizontal-edge-goes-through (edge x)
          (let ((minx (min (caar edge) (caadr edge)))
                (maxx (max (caar edge) (caadr edge))))
            (and (<= minx x) (<= x maxx))))

      ;; this only gives two edges. We are lucky.  These are the two y-coordinates
      (setq y-range (-map #'cadar (-difference (--filter (horizontal-edge-goes-through it (caar special-two-vertices)) data-horizontal-edges) special-two-edges)))

      ;; now we filter the other vertices
      (setq candidates-top (--filter (and (>= (cadr it) (car y-range)) (< (cadr it) 50000) (< (car it) 50000)) data)
            candidates-bottom (--filter (and (<= (cadr it) (cadr y-range)) (> (cadr it) 50000) (< (car it) 50000)) data))


      (car (-sort '> (-map #'area (--map (cons (cadr special-two-vertices) it) candidates-bottom))))
      1643916742

      (-sort '> (-map #'area (--map (cons (car special-two-vertices) it) candidates-top)))
    candidates-bottom

  (cadr (--map (cons (cadr special-two-vertices) it) candidates-bottom))

(94532 50249)

5639

68743

Then we can go from here…