day15/risk.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename="${1:-example.txt}"
   6 exec 3<"$filename"
   7
   8 max_y=0
   9 max_x=0
  10 declare -A map
  11 declare -A tentative
  12 declare -A lowest_distance
  13
  14 while read -u 3 line; do
  15     if [ "x$line" != "x" ]; then
  16         max_x=${#line}
  17         for (( a=0; a<$max_x; a++ )); do
  18             map[$a,$max_y]=${line:$a:1}
  19             tentative[$a,$max_y]=-1
  20         done
  21         ((max_y+=1))
  22     fi
  23 done
  24
  25 ((max_x-=1))
  26 ((max_y-=1))
  27 total_points=$(($max_x*$max_y))
  28
  29 tentative["0,0"]=0
  30
  31 cur_x=0
  32 cur_y=0
  33
  34 echo
  35 echo -n "Progress:  0%"
  36
  37 # bad implementation of djikstra's algorithm
  38 while [ "${tentative[$max_x,$max_y]+abc}" ]; do
  39     echo -n -e "\rProgress: "
  40     printf "%2d" $((100 - ((${#tentative[@]}*100) / $total_points)))
  41     echo -n "%"
  42     # where we are, we have the lowest_cost for this space, so
  43     lowest_distance[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
  44     unset tentative[$cur_x,$cur_y]
  45     # now check to the left / right / up / down from our current node
  46     # and give them tentative values
  47     # lets do the calcs for the left
  48     test_x=$((cur_x-1))
  49     if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
  50         new_cost=${lowest_distance[$cur_x,$cur_y]}
  51         ((new_cost+=${map[$test_x,$cur_y]}))
  52         if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ] || [ "${tentative[$test_x,$cur_y]}" -eq -1 ]; then
  53             tentative[$test_x,$cur_y]=$new_cost
  54         fi
  55     fi
  56     # and the right
  57     test_x=$((cur_x+1))
  58     if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
  59         new_cost=${lowest_distance[$cur_x,$cur_y]}
  60         ((new_cost+=${map[$test_x,$cur_y]}))
  61         if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ] || [ "${tentative[$test_x,$cur_y]}" -eq -1 ]; then
  62             tentative[$test_x,$cur_y]=$new_cost
  63         fi
  64     fi
  65     # above
  66     test_y=$((cur_y-1))
  67     if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
  68         new_cost=${lowest_distance[$cur_x,$cur_y]}
  69         ((new_cost+=${map[$cur_x,$test_y]}))
  70         if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ] || [ "${tentative[$cur_x,$test_y]}" -eq -1 ]; then
  71             tentative[$cur_x,$test_y]=$new_cost
  72         fi
  73     fi
  74     # below
  75     test_y=$((cur_y+1))
  76     if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
  77         new_cost=${lowest_distance[$cur_x,$cur_y]}
  78         ((new_cost+=${map[$cur_x,$test_y]}))
  79         if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ] || [ "${tentative[$cur_x,$test_y]}" -eq -1 ]; then
  80             tentative[$cur_x,$test_y]=$new_cost
  81         fi
  82     fi
  83
  84     # find the new lowest tentative
  85     new_location="-1,-1"
  86     new_value=-1
  87     for location in "${!tentative[@]}"; do
  88         if [ "${tentative[$location]}" -gt -1 ]; then
  89             if [ $new_location == "-1,-1" ]; then
  90                 new_location=$location
  91                 new_value=${tentative[$location]}
  92             elif [ "${tentative[$location]}" -lt $new_value ]; then
  93                 new_location=$location
  94                 new_value=${tentative[$location]}
  95             fi
  96         fi
  97     done
  98     if [ "$new_location" == "-1,-1" ]; then
  99         break
 100     fi
 101     cur_x=${new_location%,*}
 102     cur_y=${new_location#*,}
 103 done
 104 echo -e "\rProgress: 100%"
 105
 106 # if we've reached here, we've got the lowest risk route to the bottom right
 107 echo "Lowest route cost: ${lowest_distance[$max_x,$max_y]}"