Day 15 part 1

[advent-of-code-2021.git] / day15 / risk.sh

diff --git a/day15/risk.sh b/day15/risk.sh
new file mode 100755 (executable)
index 0000000..be993fb
--- /dev/null
+++ b/day15/risk.sh
@@ -0,0 +1,107 @@
+#!/bin/bash
+
+set -u
+
+filename="${1:-example.txt}"
+exec 3<"$filename"
+
+max_y=0
+max_x=0
+declare -A map
+declare -A tentative
+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
+done
+
+((max_x-=1))
+((max_y-=1))
+total_points=$(($max_x*$max_y))
+
+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
+
+    # find the new lowest tentative
+    new_location="-1,-1"
+    new_value=-1
+    for location in "${!tentative[@]}"; do
+        if [ "${tentative[$location]}" -gt -1 ]; then
+            if [ $new_location == "-1,-1" ]; then
+                new_location=$location
+                new_value=${tentative[$location]}
+            elif [ "${tentative[$location]}" -lt $new_value ]; then
+                new_location=$location
+                new_value=${tentative[$location]}
+            fi
+        fi
+    done
+    if [ "$new_location" == "-1,-1" ]; then
+        break
+    fi
+    cur_x=${new_location%,*}
+    cur_y=${new_location#*,}
+done
+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]}"