From 807c911b61384f9479f7c3dbb6fea098d147cba1 Mon Sep 17 00:00:00 2001
From: "Jan \"Yenya\" Kasprzak" <kas@fi.muni.cz>
Date: Wed, 11 Dec 2024 13:17:59 +0100
Subject: [PATCH] Day 11 part 2: rewrite

A simple recursive cached/memoized solution,
runs under 1 second. Oh well.
---
 2024/22.pl | 64 +++++++++++++++---------------------------------------
 1 file changed, 18 insertions(+), 46 deletions(-)

diff --git a/2024/22.pl b/2024/22.pl
index 5819be5..298dfd7 100755
--- a/2024/22.pl
+++ b/2024/22.pl
@@ -4,57 +4,29 @@ use v5.40;
 
 my @st = <> =~ /\d+/g;
 
-sub step {
-	my (@st) = @_;
-	my @new;
-	for my $s (@st) {
-		my $l = length $s;
-		if (!$s) {
-			push @new, 1;
-		} elsif ($l % 2 == 0) {
-			push @new, 0+substr($s, 0, $l/2),
-				0+substr($s, $l/2);
-		} else {
-			push @new, 2024*$s;
-		}
-	}
-	@new;
-}
-
-my %seen;
-my %cache5;
-my @q = @st;
-while (defined (my $s = shift @q)) {
-	next if $seen{$s}++;
-	my @rv = ($s);
-	@rv = step(@rv) for 1 .. 5;
-	for my $r (@rv) {
-		if (!$cache5{$s}{$r}++) {
-			if (!defined $cache5{$r}) {
-				$cache5{$r} = {};
-				push @q, $r;
-			}
-		}
-	}
-}
+my %cache;
+sub stones {
+	my ($s, $steps) = @_;
+	my $k = "$s,$steps";
+	return $cache{$k} if defined $cache{$k};
+	return $cache{$k} = 1 if !$steps;
 
-my %cache = %cache5;
-for (1 .. 14) {
-	my %ncache;
-	for my $s (keys %cache) {
-		for my $d (keys %{ $cache{$s} }){
-			for my $e (keys %{ $cache5{$d} }) {
-				$ncache{$s}{$e} += $cache{$s}{$d} * $cache5{$d}{$e};
-			}
-		}
+	$steps--;
+	my $l = length $s;
+	my $res;
+	if (!$s) {
+		$res = stones(1, $steps);
+	} elsif ($l % 2 == 0) {
+		$res = stones(0+substr($s, 0, $l/2), $steps)
+		     + stones(0+substr($s, $l/2),    $steps);
+	} else {
+		$res = stones(2024*$s, $steps);
 	}
-	%cache = %ncache;
+	return $cache{$k} = $res;
 }
 
 my $sum;
 for my $s (@st) {
-	for my $d (keys %{ $cache{$s} }) {
-		$sum += $cache{$s}{$d};
-	}
+	$sum += stones($s, 75);
 }
 say $sum;
-- 
2.43.5