From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Wed, 15 Dec 2021 15:47:34 +0000 (+0000)
Subject: Day 15 faster version and initial part 2
X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2021.git/commitdiff_plain/2937ee52f420ee229ec5801508afeee4dbdd8a73

Day 15 faster version and initial part 2
---

diff --git a/day15/risk.sh b/day15/risk.sh
index be993fb..7b013ad 100755
--- a/day15/risk.sh
+++ b/day15/risk.sh
@@ -9,14 +9,13 @@ max_y=0
 max_x=0
 declare -A map
 declare -A tentative
-declare -A lowest_distance
+declare -A lowest_distance=()
 
 while read -u 3 line; do
     if [ "x$line" != "x" ]; then
         max_x=${#line}
         for (( a=0; a<$max_x; a++ )); do
             map[$a,$max_y]=${line:$a:1}
-            tentative[$a,$max_y]=-1
         done
         ((max_y+=1))
     fi
@@ -31,61 +30,53 @@ tentative["0,0"]=0
 cur_x=0
 cur_y=0
 
-echo
-echo -n "Progress:  0%"
-
-# bad implementation of djikstra's algorithm
-while [ "${tentative[$max_x,$max_y]+abc}" ]; do
-    echo -n -e "\rProgress: "
-    printf "%2d" $((100 - ((${#tentative[@]}*100) / $total_points)))
-    echo -n "%"
-    # where we are, we have the lowest_cost for this space, so
-    lowest_distance[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
-    unset tentative[$cur_x,$cur_y]
-    # now check to the left / right / up / down from our current node
-    # and give them tentative values
-    # lets do the calcs for the left
-    test_x=$((cur_x-1))
-    if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
-        new_cost=${lowest_distance[$cur_x,$cur_y]}
-        ((new_cost+=${map[$test_x,$cur_y]}))
-        if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ] || [ "${tentative[$test_x,$cur_y]}" -eq -1 ]; then
-            tentative[$test_x,$cur_y]=$new_cost
-        fi
-    fi
-    # and the right
-    test_x=$((cur_x+1))
-    if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
-        new_cost=${lowest_distance[$cur_x,$cur_y]}
-        ((new_cost+=${map[$test_x,$cur_y]}))
-        if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ] || [ "${tentative[$test_x,$cur_y]}" -eq -1 ]; then
-            tentative[$test_x,$cur_y]=$new_cost
-        fi
-    fi
-    # above
-    test_y=$((cur_y-1))
-    if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
-        new_cost=${lowest_distance[$cur_x,$cur_y]}
-        ((new_cost+=${map[$cur_x,$test_y]}))
-        if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ] || [ "${tentative[$cur_x,$test_y]}" -eq -1 ]; then
-            tentative[$cur_x,$test_y]=$new_cost
-        fi
-    fi
-    # below
-    test_y=$((cur_y+1))
-    if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
-        new_cost=${lowest_distance[$cur_x,$cur_y]}
-        ((new_cost+=${map[$cur_x,$test_y]}))
-        if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ] || [ "${tentative[$cur_x,$test_y]}" -eq -1 ]; then
-            tentative[$cur_x,$test_y]=$new_cost
-        fi
-    fi
+do_cost() {
+    echo -n "Progress:  0%"
 
-    # find the new lowest tentative
-    new_location="-1,-1"
-    new_value=-1
-    for location in "${!tentative[@]}"; do
-        if [ "${tentative[$location]}" -gt -1 ]; then
+    # bad implementation of djikstra's algorithm
+    while [ ! "${lowest_distance[$max_x,$max_y]+abc}" ]; do
+        echo -n -e "\rProgress: "
+        printf "%2d" $((((${#lowest_distance[@]}*100) / $total_points)))
+        echo -n "%"
+        lowest_distance[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
+        unset tentative[$cur_x,$cur_y]
+        # now check to the left / right / up / down from our current node
+        # and give them tentative values
+        for test_x in $((cur_x-1)) $((cur_x+1)); do
+            if [ "${map[$test_x,$cur_y]+abc}" ]; then
+                if [ ! "${lowest_distance[$test_x,$cur_y]+abc}" ]; then
+                    new_cost=${lowest_distance[$cur_x,$cur_y]}
+                    ((new_cost+=${map[$test_x,$cur_y]}))
+                    if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
+                        if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ]; then
+                            tentative[$test_x,$cur_y]=$new_cost
+                        fi
+                    else
+                        tentative[$test_x,$cur_y]=$new_cost
+                    fi
+                fi
+            fi
+        done
+        for test_y in $((cur_y-1)) $((cur_y+1)); do
+            if [ "${map[$cur_x,$test_y]+abc}" ]; then
+                if [ ! "${lowest_distance[$cur_x,$test_y]+abc}" ]; then
+                    new_cost=${lowest_distance[$cur_x,$cur_y]}
+                    ((new_cost+=${map[$cur_x,$test_y]}))
+                    if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
+                        if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ]; then
+                            tentative[$cur_x,$test_y]=$new_cost
+                        fi
+                    else
+                        tentative[$cur_x,$test_y]=$new_cost
+                    fi
+                fi
+            fi
+        done
+
+        # find the new lowest tentative
+        new_location="-1,-1"
+        new_value=-1
+        for location in "${!tentative[@]}"; do
             if [ $new_location == "-1,-1" ]; then
                 new_location=$location
                 new_value=${tentative[$location]}
@@ -93,15 +84,88 @@ while [ "${tentative[$max_x,$max_y]+abc}" ]; do
                 new_location=$location
                 new_value=${tentative[$location]}
             fi
+        done
+        if [ "$new_location" == "-1,-1" ]; then
+            break
         fi
+        cur_x=${new_location%,*}
+        cur_y=${new_location#*,}
     done
-    if [ "$new_location" == "-1,-1" ]; then
-        break
-    fi
-    cur_x=${new_location%,*}
-    cur_y=${new_location#*,}
-done
-echo -e "\rProgress: 100%"
+    echo -e "\rProgress: 100%"
 
 # if we've reached here, we've got the lowest risk route to the bottom right
-echo "Lowest route cost: ${lowest_distance[$max_x,$max_y]}"
+    echo "Lowest route cost: ${lowest_distance[$max_x,$max_y]}"
+}
+
+display_map() {
+    for (( y=0; y<=$max_y; y++ )); do
+        for (( x=0; x<=$max_x; x++ )); do
+            echo -n ${map[$x,$y]}
+        done
+        echo
+    done
+}
+
+echo "Part 1"
+do_cost
+
+# first, work left to right on the map on the first iteration, that gets this up to 5 wide
+x_width=$((max_x+1))
+y_height=$((max_y+1))
+for cell in $(seq 2 5); do
+    for (( y=0; y<$y_height; y++ )); do
+        for (( x=0; x<$x_width; x++ )); do
+            old_x=$((($x_width*($cell-2))+$x))
+            new_x=$((($x_width*($cell-1))+$x))
+            new_value=$((${map[$old_x,$y]} + 1))
+            if [ $new_value -gt 9 ]; then
+                new_value=1
+            fi
+            map[$new_x,$y]=$new_value
+        done
+    done
+done
+# now, we work on the second to 5th y iteration
+# in each case, we can take the 2-5 cells of above
+# and copy them, then just do the actual work on the 5th
+# cell
+for y_rep in $(seq 2 5); do
+    y_copy_offset=$((($y_rep - 2)*$y_height))
+    y_offset=$((($y_rep - 1)*$y_height))
+    for (( y=0; y<$y_height; y++ )); do
+        for (( x=0; x<$x_width*4; x++ )); do
+            old_x=$((x+$x_width))
+            value=${map[$old_x,$(($y_copy_offset+$y))]}
+            map[$x,$(($y_offset+$y))]=$value
+        done
+        # now we want to just copy the left one + 1, ish
+        for (( x=0; x<$x_width; x++ )); do
+            new_x=$((($x_width*4)+$x))
+            old_x=$((($x_width*3)+$x))
+            new_value=$((${map[$old_x,$(($y_offset+$y))]}))
+            ((new_value+=1))
+            if [ $new_value -gt 9 ]; then
+                new_value=1
+            fi
+            map[$new_x,$(($y_offset+$y))]=$new_value
+        done
+    done
+done
+
+# we now have a 5*5 grid of the evil! lets change max_x, max_y, and total_points
+max_x=$((($x_width * 5) - 1))
+max_y=$((($y_height * 5) - 1))
+total_points=$(($max_x*$max_y))
+
+unset tentative
+unset lowest_distance
+declare -A tentative=()
+declare -A lowest_distance=()
+
+tentative[0,0]=0
+cur_x=0
+cur_y=0
+
+echo "Part 2"
+#display_map
+do_cost