From d36523c7851cdd1236340098ee7011c75ebbb706 Mon Sep 17 00:00:00 2001
From: Eric Blake <eblake@redhat.com>
Date: Wed, 20 Dec 2023 14:39:29 -0600
Subject: [PATCH] day 18 part 2

64-bit math, yet again.  Thank goodness I already had an O(n)
algorithm in place; the bear here was adjusting things to work with
math64.m4 in place (including the fact that both 'add64' and 'a1'
macros defined in that file can conflict with arbitrary hex numbers).

~375ms for GNU, ~400ms for POSIX (parsing time is still noticeable,
despite the dominant time being spent on the 64-bit math).
---
 2023/day18.m4 | 38 ++++++++++++++++++++++++--------------
 1 file changed, 24 insertions(+), 14 deletions(-)

diff --git a/2023/day18.m4 b/2023/day18.m4
index e5693d3..0efd76f 100644
--- a/2023/day18.m4
+++ b/2023/day18.m4
@@ -6,25 +6,32 @@ include(`common.m4')ifelse(common(18), `ok', `',
 ')m4exit(1)')
 
 changecom
-define(`input', translit(include(defn(`file')), nl` ()#', `;.'))
+define(`input', translit(include(defn(`file')), nl`RDLUabcdef ()#',
+  `;0123ABCDEF.'))
 changecom(`#', nl)
 
+include(`math64.m4')
+
 # https://en.wikipedia.org/wiki/Shoelace_formula is close for twice area;
 # but we are digging 1x1 squares, not points. There is length/2 additional
 # area oustside each line, and 1/4*(convex-concave) at corners.
 # Assume corner at 0,0 is convex; but int division truncates if it's concave.
-define(`area', 0)define(`perim', 0)define(`corner', 1)
-define(`x', 0)define(`y', 0)define(`o', `R')
-define(`visit', `define(`area', eval(area` + $1*$4 - $2*$3'))define(`perim',
-  eval(perim+$5))define(`corner', eval(defn(`d'o`$6')+corner))define(`x',
-  $3)define(`y', $4)define(`o', `$6')')
-define(`dRD', 1)define(`dDL', 1)define(`dLU', 1)define(`dUR', 1)
-define(`dRU', -1)define(`dUL', -1)define(`dLD', -1)define(`dDR', -1)
-define(`doR', `visit($1, $2, eval(`$1 + $3'), $2, $3, `R')')
-define(`doU', `visit($1, $2, $1, eval(`$2 - $3'), $3, `U')')
-define(`doL', `visit($1, $2, eval(`$1 - $3'), $2, $3, `L')')
-define(`doD', `visit($1, $2, $1, eval(`$2 + $3'), $3, `D')')
-define(`_do', `do$1(x, y, $2)')
+define(`area1', 0)define(`perim1', 0)define(`corner1', 1)
+define(`x1', 0)define(`y1', 0)define(`o1', `0')
+define(`area2', 0)define(`perim2', 0)define(`corner2', 1)
+define(`x2', 0)define(`y2', 0)define(`o2', `0')
+define(`visit', `define(`area$1', add64(area$1, sub64(mul64($2, $5),
+  mul64($3, $4))))define(`perim$1', eval(perim$1+$6))define(`corner$1',
+  eval(defn(`o'o$1`$7')+corner$1))define(`x$1', $4)define(`y$1',
+  $5)define(`o$1', `$7')')
+define(`o01', 1)define(`o12', 1)define(`o23', 1)define(`o30', 1)
+define(`o03', -1)define(`o32', -1)define(`o21', -1)define(`o10', -1)
+define(`do0', `visit($1, $2, $3, eval(`$2 + $4'), $3, $4, `0')')
+define(`do1', `visit($1, $2, $3, $2, eval(`$3 + $4'), $4, `1')')
+define(`do2', `visit($1, $2, $3, eval(`$2 - $4'), $3, $4, `2')')
+define(`do3', `visit($1, $2, $3, $2, eval(`$3 - $4'), $4, `3')')
+define(`_do', `do$1(1, x1, y1, $2)first(`do'eval(`0x$3%4'))(2, x2, y2,
+  eval(`0x$3/16'))')
 define(`do', `_$0(translit(`$1', `.', `,'))')
 
 ifdef(`__gnu__', `
@@ -39,7 +46,10 @@ ifdef(`__gnu__', `
   chew(len(defn(`input')), defn(`input'))
 ')
 
-define(`part1', translit(eval(area/2 + perim/2 + corner/4), `-'))
+define(`_half', `substr(`$1', 0, decr(len(`$1')))')
+define(`half', `_$0(mul64(`$1', 5))')
+define(`part1', eval(translit(area1, `-')/2 + perim1/2 + corner1/4))
+define(`part2', add64(half(translit(area2, `-')), eval(perim2/2 + corner2/4)))
 
 divert`'part1
 part2
-- 
2.11.4.GIT