From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Tue, 14 Dec 2021 21:17:32 +0000 (+0000)
Subject: Make day 13 much much quicker
X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2021.git/commitdiff_plain/39130f89f58490298b833e8f9e0036a4844f4a3e?ds=sidebyside

Make day 13 much much quicker

  - Use an associative array rather than an indexed array
  - Work from the fold outwards rather than the edge inwards
---

diff --git a/day13/fold.sh b/day13/fold.sh
index 7db1eda..d2c8647 100755
--- a/day13/fold.sh
+++ b/day13/fold.sh
@@ -36,8 +36,7 @@ done
 display_map() {
     for (( y=0; y<$max_y; y++ )); do
         for (( x=0; x<$max_x; x++ )); do
-            offset=$(((y*$max_x) + $x))
-            case "${map[$offset]}" in
+            case "${map[$x,$y]}" in
                 0)
                     echo -n "."
                     ;;
@@ -50,27 +49,27 @@ display_map() {
     done
 }
 
-declare -a map
+declare -A map
 
 # now build a map
-for (( a=0; a<$(($max_x * $max_y)); a++ )); do
-    map[$a]=0
+for (( y=0; y<$max_y; y++ )); do
+    for (( x=0; x<$max_x; x++ )); do
+        map["$x,$y"]=0
+    done
 done
 
 for point in "${points[@]}"; do
     x=${point%,*}
     y=${point#*,}
-    offset=$((($y*$max_x)+$x))
-    map[$offset]=1
+    map["$x,$y"]=1
 done
 
 fold() {
     local line="$1"
     local axis=${line%=*}
     local point=${line#*=}
-    local dot="."
 
-    declare -a new_map=()
+    declare -A new_map=()
 
     case $axis in
         x)
@@ -78,23 +77,21 @@ fold() {
             if [ $point -gt $new_max_x ]; then
                 new_max_x=$point
             fi
-            local adj=$((max_x % 2))
             for (( y=0; y<$max_y; y++ )); do
                 for (( x=0; x<$new_max_x; x++ )); do
-                    x_1=$(($point - $new_max_x + $x))
-                    x_2=$(($max_x - ($new_max_x - $point) - $x - $adj))
-                    offset_1=$((($y * $max_x) + $x_1))
-                    offset_2=$((($y * $max_x) + $x_2))
+                    # be sensible instead of insane, work from the middle out
+                    x_1=$(($point-$x-1)) # always one left of the point
+                    x_2=$(($point+$x+1)) # always one right of the point
                     if [ $x_1 -lt 0 ]; then
-                        offset_1=$offset_2
+                        x_1=$x_2
                     fi
                     if [ $x_2 -ge $max_x  ]; then
-                        offset_2=$offset_1
+                        x_2=$x_1
                     fi
-                    new_map+=($((${map[$offset_1]} | ${map[$offset_2]})))
+                    new_x=$(($new_max_x-$x-1)) # work from the right of the new image, left
+                    new_map["$new_x,$y"]=$((${map["$x_1,$y"]} | ${map["$x_2,$y"]}))
                 done
             done
-            map=("${new_map[@]}")
             max_x=$new_max_x
             ;;
         y)
@@ -102,47 +99,43 @@ fold() {
             if [ $point -gt $new_max_y ]; then
                 new_max_y=$point
             fi
-            local adj=$((max_y % 2))
             for (( y=0; y<$new_max_y; y++ )); do
-                # do the y offsets here
-                y_1=$(($point - $new_max_y + $y))
-                y_2=$(($max_y - ($new_max_y - $point) - $y - $adj))
-                offset_1=$(($y_1 * $max_x))
-                offset_2=$(($y_2 * $max_x))
+                y_1=$(($point-$y-1)) # always above the fold
+                y_2=$(($point+$y+1)) # always below the fold
                 if [ $y_1 -lt 0 ]; then
-                    offset_1=$offset_2
+                    y_1=$y_2
                 fi
                 if [ $y_2 -ge $max_y  ]; then
-                    offset_2=$offset_1
+                    y_2=$y_1
                 fi
+                new_y=$(($new_max_y-$y-1)) # work from the bottom of the new image, up
                 for (( x=0; x<$max_x; x++ )); do
-                    off_1=$(($offset_1+$x))
-                    off_2=$(($offset_2+$x))
-                    new_map+=($((${map[$off_1]} | ${map[$off_2]})))
+                    new_map["$x,$new_y"]=$((${map["$x,$y_1"]} | ${map["$x,$y_2"]}))
                 done
             done
-            map=("${new_map[@]}")
             max_y=$new_max_y
             ;;
     esac
+
+    for k in "${!new_map[@]}"; do
+        map[$k]=${new_map[$k]}
+    done
 }
 
 get_points_count() {
     local count=0
-    for point in "${map[@]}"; do
-        ((count+=$point))
+    for (( y=0; y<$max_y; y++ )); do
+        for (( x=0; x<$max_x; x++ )); do
+            ((count+=${map[$x,$y]}))
+        done
     done
 
     echo $count
 }
 
-#display_map
-
 # do first fold
+echo "Doing first fold"
 fold "${folds[0]}"
-echo
-#display_map
-echo
 echo "There are $(get_points_count) dots visible after first fold"
 for (( f=1; f<${#folds[@]}; f++ )); do
     echo "Doing fold $((f+1)) of ${#folds[@]}"