From 243fb1bb4deaea8d1bf6a95409f722816ca9f7a7 Mon Sep 17 00:00:00 2001
From: Thomas Voss <mail@thomasvoss.com>
Date: Sat, 7 Dec 2024 16:45:08 +0100
Subject: Make the implementation much faster

---
 2024/07/puzzles.awk | 44 +++++++++++++++++++++++++++++++-------------
 1 file changed, 31 insertions(+), 13 deletions(-)

(limited to '2024/07')

diff --git a/2024/07/puzzles.awk b/2024/07/puzzles.awk
index 491a1b5..53b23d3 100644
--- a/2024/07/puzzles.awk
+++ b/2024/07/puzzles.awk
@@ -1,19 +1,37 @@
-#!/usr/bin/awk -f
+#!/usr/bin/gawk -f
 
-function eval(i, acc)
+@load "intdiv"
+
+# START PART 2
+function pow(x, e,    n)
+{
+	n = 1
+	while (e--)
+		n *= x
+	return n
+}
+# END PART 2
+
+function eval(i, acc,    a)
 {
-	if (acc > $1)
+	if (acc <= 0)
 		return 0
-	if (i == NF + 1)
-		return acc == $1
-# START PART 1
-	return eval(i + 1, acc * $i) || eval(i + 1, acc + $i)
-# END PART 1 START PART 2
-	return eval(i + 1, (acc $i) + 0) || eval(i + 1, acc * $i) ||
-		eval(i + 1, acc + $i)
+	if (i == 2)
+		return acc == $2
+
+# START PART 2
+	intdiv(acc, pow(10, length($i)), a)
+	if (a["remainder"] == $i && eval(i - 1, a["quotient"]))
+		return 1
 # END PART 2
+
+	intdiv(acc, $i, a)
+	if (a["remainder"] == 0 && eval(i - 1, a["quotient"]))
+		return 1
+
+	return eval(i - 1, acc - $i)
 }
 
-BEGIN       { FS = ":? " }
-eval(3, $2) { n += $1 }
-END         { print n }
\ No newline at end of file
+BEGIN        { FS = ":? " }
+eval(NF, $1) { n += $1 }
+END          { print n }
\ No newline at end of file
-- 
cgit v1.2.3