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
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]}
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
projects / advent-of-code-2021.git / blobdiff