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         done
  20         ((max_y+=1))
  21     fi
  22 done
  23
  24 ((max_x-=1))
  25 ((max_y-=1))
  26 total_points=$(($max_x*$max_y))
  27
  28 tentative["0,0"]=0
  29
  30 cur_x=0
  31 cur_y=0
  32
  33 do_cost() {
  34     echo -n "Progress:  0%"
  35
  36     # bad implementation of djikstra's algorithm
  37     while [ ! "${lowest_distance[$max_x,$max_y]+abc}" ]; do
  38         echo -n -e "\rProgress: "
  39         printf "%2d" $((((${#lowest_distance[@]}*100) / $total_points)))
  40         echo -n "%"
  41         lowest_distance[$cur_x,$cur_y]="${tentative["$cur_x,$cur_y"]}"
  42         unset tentative[$cur_x,$cur_y]
  43         # now check to the left / right / up / down from our current node
  44         # and give them tentative values
  45         for test_x in $((cur_x-1)) $((cur_x+1)); do
  46             if [ "${map[$test_x,$cur_y]+abc}" ]; then
  47                 if [ ! "${lowest_distance[$test_x,$cur_y]+abc}" ]; then
  48                     new_cost=${lowest_distance[$cur_x,$cur_y]}
  49                     ((new_cost+=${map[$test_x,$cur_y]}))
  50                     if [ "${tentative[$test_x,$cur_y]+abc}" ]; then
  51                         if [ $new_cost -lt ${tentative[$test_x,$cur_y]} ]; then
  52                             tentative[$test_x,$cur_y]=$new_cost
  53                         fi
  54                     else
  55                         tentative[$test_x,$cur_y]=$new_cost
  56                     fi
  57                 fi
  58             fi
  59         done
  60         for test_y in $((cur_y-1)) $((cur_y+1)); do
  61             if [ "${map[$cur_x,$test_y]+abc}" ]; then
  62                 if [ ! "${lowest_distance[$cur_x,$test_y]+abc}" ]; then
  63                     new_cost=${lowest_distance[$cur_x,$cur_y]}
  64                     ((new_cost+=${map[$cur_x,$test_y]}))
  65                     if [ "${tentative[$cur_x,$test_y]+abc}" ]; then
  66                         if [ $new_cost -lt ${tentative[$cur_x,$test_y]} ]; then
  67                             tentative[$cur_x,$test_y]=$new_cost
  68                         fi
  69                     else
  70                         tentative[$cur_x,$test_y]=$new_cost
  71                     fi
  72                 fi
  73             fi
  74         done
  75
  76         # find the new lowest tentative
  77         new_location="-1,-1"
  78         new_value=-1
  79         for location in "${!tentative[@]}"; do
  80             if [ $new_location == "-1,-1" ]; then
  81                 new_location=$location
  82                 new_value=${tentative[$location]}
  83             elif [ "${tentative[$location]}" -lt $new_value ]; then
  84                 new_location=$location
  85                 new_value=${tentative[$location]}
  86             fi
  87         done
  88         if [ "$new_location" == "-1,-1" ]; then
  89             break
  90         fi
  91         cur_x=${new_location%,*}
  92         cur_y=${new_location#*,}
  93     done
  94     echo -e "\rProgress: 100%"
  95
  96 # if we've reached here, we've got the lowest risk route to the bottom right
  97     echo "Lowest route cost: ${lowest_distance[$max_x,$max_y]}"
  98 }
  99
 100 display_map() {
 101     for (( y=0; y<=$max_y; y++ )); do
 102         for (( x=0; x<=$max_x; x++ )); do
 103             echo -n ${map[$x,$y]}
 104         done
 105         echo
 106     done
 107 }
 108
 109 echo "Part 1"
 110 do_cost
 111
 112 # first, work left to right on the map on the first iteration, that gets this up to 5 wide
 113 x_width=$((max_x+1))
 114 y_height=$((max_y+1))
 115 for cell in $(seq 2 5); do
 116     for (( y=0; y<$y_height; y++ )); do
 117         for (( x=0; x<$x_width; x++ )); do
 118             old_x=$((($x_width*($cell-2))+$x))
 119             new_x=$((($x_width*($cell-1))+$x))
 120             new_value=$((${map[$old_x,$y]} + 1))
 121             if [ $new_value -gt 9 ]; then
 122                 new_value=1
 123             fi
 124             map[$new_x,$y]=$new_value
 125         done
 126     done
 127 done
 128 # now, we work on the second to 5th y iteration
 129 # in each case, we can take the 2-5 cells of above
 130 # and copy them, then just do the actual work on the 5th
 131 # cell
 132 for y_rep in $(seq 2 5); do
 133     y_copy_offset=$((($y_rep - 2)*$y_height))
 134     y_offset=$((($y_rep - 1)*$y_height))
 135     for (( y=0; y<$y_height; y++ )); do
 136         for (( x=0; x<$x_width*4; x++ )); do
 137             old_x=$((x+$x_width))
 138             value=${map[$old_x,$(($y_copy_offset+$y))]}
 139             map[$x,$(($y_offset+$y))]=$value
 140         done
 141         # now we want to just copy the left one + 1, ish
 142         for (( x=0; x<$x_width; x++ )); do
 143             new_x=$((($x_width*4)+$x))
 144             old_x=$((($x_width*3)+$x))
 145             new_value=$((${map[$old_x,$(($y_offset+$y))]}))
 146             ((new_value+=1))
 147             if [ $new_value -gt 9 ]; then
 148                 new_value=1
 149             fi
 150             map[$new_x,$(($y_offset+$y))]=$new_value
 151         done
 152     done
 153 done
 154
 155 # we now have a 5*5 grid of the evil! lets change max_x, max_y, and total_points
 156 max_x=$((($x_width * 5) - 1))
 157 max_y=$((($y_height * 5) - 1))
 158 total_points=$(($max_x*$max_y))
 159
 160 unset tentative
 161 unset lowest_distance
 162 declare -A tentative=()
 163 declare -A lowest_distance=()
 164
 165 tentative[0,0]=0
 166 cur_x=0
 167 cur_y=0
 168
 169 echo "Part 2"
 170 #display_map
 171 do_cost