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 7db1edac277556f16b304a191b76d8727420c2b7..d2c8647483189b3aa39ee66669939304e5a85589 100755 (executable)
--- 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
 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 "."
                     ;;
                 0)
                     echo -n "."
                     ;;


@@ -50,27 +49,27 @@ display_map() {
     done
 }
 
     done
 }
 

-declare -a map
+declare -A map

 
 # now build 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#*,}
 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#*=}
 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)
 
     case $axis in
         x)


@@ -78,23 +77,21 @@ fold() {
             if [ $point -gt $new_max_x ]; then
                 new_max_x=$point
             fi
             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
             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
                     if [ $x_1 -lt 0 ]; then

-                        offset_1=$offset_2
+                        x_1=$x_2

                     fi
                     if [ $x_2 -ge $max_x  ]; then
                     fi
                     if [ $x_2 -ge $max_x  ]; then

-                        offset_2=$offset_1
+                        x_2=$x_1

                     fi
                     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
                 done
             done

-            map=("${new_map[@]}")

             max_x=$new_max_x
             ;;
         y)
             max_x=$new_max_x
             ;;
         y)


@@ -102,47 +99,43 @@ fold() {
             if [ $point -gt $new_max_y ]; then
                 new_max_y=$point
             fi
             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
             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
                 if [ $y_1 -lt 0 ]; then

-                    offset_1=$offset_2
+                    y_1=$y_2

                 fi
                 if [ $y_2 -ge $max_y  ]; then
                 fi
                 if [ $y_2 -ge $max_y  ]; then

-                    offset_2=$offset_1
+                    y_2=$y_1

                 fi
                 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
                 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
                 done
             done

-            map=("${new_map[@]}")

             max_y=$new_max_y
             ;;
     esac
             max_y=$new_max_y
             ;;
     esac

+
+    for k in "${!new_map[@]}"; do
+        map[$k]=${new_map[$k]}
+    done

 }
 
 get_points_count() {
     local count=0
 }
 
 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
 }
 
     done
 
     echo $count
 }
 

-#display_map
-

 # do first fold
 # do first fold

+echo "Doing first fold"

 fold "${folds[0]}"
 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[@]}"
 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[@]}"