From: Brett Parker 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?ds=sidebyside 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