From: Brett Parker Date: Tue, 14 Dec 2021 21:17:32 +0000 (+0000) Subject: Make day 13 much much quicker X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2021.git/commitdiff_plain/39130f89f58490298b833e8f9e0036a4844f4a3e?ds=sidebyside Make day 13 much much quicker - Use an associative array rather than an indexed array - Work from the fold outwards rather than the edge inwards --- diff --git a/day13/fold.sh b/day13/fold.sh index 7db1eda..d2c8647 100755 --- a/day13/fold.sh +++ b/day13/fold.sh @@ -36,8 +36,7 @@ done display_map() { for (( y=0; y<$max_y; y++ )); do for (( x=0; x<$max_x; x++ )); do - offset=$(((y*$max_x) + $x)) - case "${map[$offset]}" in + case "${map[$x,$y]}" in 0) echo -n "." ;; @@ -50,27 +49,27 @@ display_map() { done } -declare -a map +declare -A map # now build a map -for (( a=0; a<$(($max_x * $max_y)); a++ )); do - map[$a]=0 +for (( y=0; y<$max_y; y++ )); do + for (( x=0; x<$max_x; x++ )); do + map["$x,$y"]=0 + done done for point in "${points[@]}"; do x=${point%,*} y=${point#*,} - offset=$((($y*$max_x)+$x)) - map[$offset]=1 + map["$x,$y"]=1 done fold() { local line="$1" local axis=${line%=*} local point=${line#*=} - local dot="." - declare -a new_map=() + declare -A new_map=() case $axis in x) @@ -78,23 +77,21 @@ fold() { if [ $point -gt $new_max_x ]; then new_max_x=$point fi - local adj=$((max_x % 2)) for (( y=0; y<$max_y; y++ )); do for (( x=0; x<$new_max_x; x++ )); do - x_1=$(($point - $new_max_x + $x)) - x_2=$(($max_x - ($new_max_x - $point) - $x - $adj)) - offset_1=$((($y * $max_x) + $x_1)) - offset_2=$((($y * $max_x) + $x_2)) + # be sensible instead of insane, work from the middle out + x_1=$(($point-$x-1)) # always one left of the point + x_2=$(($point+$x+1)) # always one right of the point if [ $x_1 -lt 0 ]; then - offset_1=$offset_2 + x_1=$x_2 fi if [ $x_2 -ge $max_x ]; then - offset_2=$offset_1 + x_2=$x_1 fi - new_map+=($((${map[$offset_1]} | ${map[$offset_2]}))) + new_x=$(($new_max_x-$x-1)) # work from the right of the new image, left + new_map["$new_x,$y"]=$((${map["$x_1,$y"]} | ${map["$x_2,$y"]})) done done - map=("${new_map[@]}") max_x=$new_max_x ;; y) @@ -102,47 +99,43 @@ fold() { if [ $point -gt $new_max_y ]; then new_max_y=$point fi - local adj=$((max_y % 2)) for (( y=0; y<$new_max_y; y++ )); do - # do the y offsets here - y_1=$(($point - $new_max_y + $y)) - y_2=$(($max_y - ($new_max_y - $point) - $y - $adj)) - offset_1=$(($y_1 * $max_x)) - offset_2=$(($y_2 * $max_x)) + y_1=$(($point-$y-1)) # always above the fold + y_2=$(($point+$y+1)) # always below the fold if [ $y_1 -lt 0 ]; then - offset_1=$offset_2 + y_1=$y_2 fi if [ $y_2 -ge $max_y ]; then - offset_2=$offset_1 + y_2=$y_1 fi + new_y=$(($new_max_y-$y-1)) # work from the bottom of the new image, up for (( x=0; x<$max_x; x++ )); do - off_1=$(($offset_1+$x)) - off_2=$(($offset_2+$x)) - new_map+=($((${map[$off_1]} | ${map[$off_2]}))) + new_map["$x,$new_y"]=$((${map["$x,$y_1"]} | ${map["$x,$y_2"]})) done done - map=("${new_map[@]}") max_y=$new_max_y ;; esac + + for k in "${!new_map[@]}"; do + map[$k]=${new_map[$k]} + done } get_points_count() { local count=0 - for point in "${map[@]}"; do - ((count+=$point)) + for (( y=0; y<$max_y; y++ )); do + for (( x=0; x<$max_x; x++ )); do + ((count+=${map[$x,$y]})) + done done echo $count } -#display_map - # do first fold +echo "Doing first fold" fold "${folds[0]}" -echo -#display_map -echo echo "There are $(get_points_count) dots visible after first fold" for (( f=1; f<${#folds[@]}; f++ )); do echo "Doing fold $((f+1)) of ${#folds[@]}"