From 667694b94a6758e3ce751c565309ae980e76a931 Mon Sep 17 00:00:00 2001 From: Brett Parker Date: Tue, 8 Dec 2020 20:55:31 +0000 Subject: [PATCH] Optimisation v1 for asteroid checks --- day10/check_asteroids.sh | 151 +++++++++++++++++++++++++++++++-------- 1 file changed, 120 insertions(+), 31 deletions(-) diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh index e0bf959..8faf834 100755 --- a/day10/check_asteroids.sh +++ b/day10/check_asteroids.sh @@ -4,6 +4,7 @@ set -u set -e basedir=$(dirname $(readlink -f ${BASH_SOURCE})) + filename=${1:-$basedir/3_4_8.txt} exec 3<$filename @@ -25,9 +26,15 @@ while read -u 3 line; do ln=$((ln+1)) done +debug_line=true # default to not actually outputting any debug info + +if [ ${DEBUG:-0} -gt 0 ]; then + debug_line=debug_line +fi + debug_line() { line="$@" - #echo "$line" >&2 + echo "$line" >&2 } get_vector() { @@ -47,7 +54,7 @@ check_collision() { local vector1=$1 local vector2=$2 - debug_line Comparing: $vector1 $vector2 + $debug_line Comparing: $vector1 $vector2 vector1_x=${vector1%,*} vector1_y=${vector1#*,} @@ -65,38 +72,37 @@ check_collision() { vector2_y_val=${vector2_y#-} minimum_number=$vector2_x_val - if ( [ $vector2_x_val -gt $vector2_y_val ] && [ $vector2_y_val -gt 0 ] ) || - [ $minimum_number -eq 0 ]; then + if [ $vector2_x_val -gt $vector2_y_val -a $vector2_y_val -gt 0 ] || [ $minimum_number -eq 0 ]; then minimum_number=$vector2_y_val fi - debug_line "Min number: $minimum_number" + $debug_line "Min number: $minimum_number" minstep_x=$vector2_x minstep_y=$vector2_y for (( a=$minimum_number; a>0; a-- )); do - if [ $((vector2_x % $a)) -eq 0 ] && [ $((vector2_y % $a)) -eq 0 ]; then + if [ $((vector2_x % $a)) -eq 0 -a $((vector2_y % $a)) -eq 0 ]; then minstep_x=$((vector2_x / $a)) minstep_y=$((vector2_y / $a)) break fi done - debug_line "Have minsteps: $minstep_x,$minstep_y" + $debug_line "Have minsteps: $minstep_x,$minstep_y" # in all other cases, we're at least heading in the right direction cur_x=$vector2_x cur_y=$vector2_y - debug_line "Looking for: $vector1_x,$vector1_y" - debug_line "Start: $cur_x,$cur_y" + $debug_line "Looking for: $vector1_x,$vector1_y" + $debug_line "Start: $cur_x,$cur_y" # from the starting point, add the min steps until we're past the other asteroid while keep_going $cur_x $cur_y $minstep_x $minstep_y $vector1_x $vector1_y; do cur_x=$((cur_x+$minstep_x)) cur_y=$((cur_y+$minstep_y)) - debug_line "Step: $cur_x,$cur_y" - if [ $cur_x -eq $vector1_x ] && [ $cur_y -eq $vector1_y ]; then - debug_line "Collision!" + $debug_line "Step: $cur_x,$cur_y" + if [ $cur_x -eq $vector1_x -a $cur_y -eq $vector1_y ]; then + $debug_line "Collision!" return 0 fi done @@ -104,6 +110,86 @@ check_collision() { return 1 } +fast_checks() { + asteroid=$1 + start_x=${asteroid%,*} + start_y=${asteroid#*,} + + hitblocker=0 + + max_x=$width + max_y=$ln + + # first, head left of the asteroid + for (( x=$((start_x-1)); x>=0; x-- )); do + do_blocker_check $asteroid $x $start_y + done + hitblocker=0 # this gets updated in do_blocker_check, reset it + + # now head right of the asteroid + for (( x=$(($start_x+1)); x<= $width; x++ )); do + do_blocker_check $asteroid $x $start_y + done + hitblocker=0 # this gets updated in do_blocker_check, reset it + + # head upwards + for (( y=$((start_y-1)); y>=0; y-- )); do + do_blocker_check $asteroid $start_x $y + done + hitblocker=0 # this gets updated in do_blocker_check, reset it + + # head down + for (( y=$((start_y+1)); y<=$ln; y++ )); do + do_blocker_check $asteroid $start_x $y + done +} + +do_blocker_check() { + asteroid=$1 + x=$2 + y=$3 + + if [ ${asteroids[$x,$y]+a} ]; then + if [ $hitblocker -eq 0 ]; then + cansee[$asteroid,$x,$y]=1 + cansee[$x,$y,$asteroid]=1 + hitblocker=1 + else + cantsee[$asteroid,$x,$y]=1 + cantsee[$x,$y,$asteroid]=1 + fi + fi +} + +possibly_in_way() { + source_x=$1 + source_y=$2 + sink_x=$3 + sink_y=$4 + blocker_x=$5 + blocker_y=$6 + + # first check the horizontal and vertical planes + if [[ ( $source_x -eq $sink_x && $sink_x -eq $blocker_x ) && ( $sink_y -gt $blocker_y && $blocker_y -gt $source_y ) || ( $sink_y -lt $blocker_y && $blocker_y -lt $source_y ) ]] || + [[ ( $source_y -eq $sink_y && $sink_y -eq $blocker_y ) && ( $sink_x -gt $blocker_x && $blocker_x -gt $source_x ) || ( $sink_x -lt $blocker_x && $blocker_x -lt $source_x ) ]]; then + return 0 + fi + + # if our source asteroid is further to the right thank our sink, then to stand half a chance + # of being in the way, the blocker has to be x > $sink_x and x < source_x + # apply the same rule for y + # reverse the direction and do the same checks. + # So if source_x < sink_x then blocker_x has to be < sink_x > source_x + if [ $source_x -gt $sink_x -a $blocker_x -gt $sink_x -a $blocker_x -lt $source_x ] || + [ $source_y -gt $sink_y -a $blocker_y -gt $sink_y -a $blocker_y -lt $source_y ] || + [ $source_x -lt $sink_x -a $blocker_x -lt $sink_x -a $blocker_x -gt $source_x ] || + [ $source_y -lt $sink_y -a $blocker_y -lt $sink_y -a $blocker_y -gt $source_y ]; then + return 0 + fi + + return 1 +} + keep_going() { local cur_x=$1 local cur_y=$2 @@ -112,19 +198,11 @@ keep_going() { local ast_x=$5 local ast_y=$6 - if [ $minstep_x -lt 0 ] && [ $cur_x -lt $ast_x ]; then - # past the asteroid, we missed - debug_line "stop cond 1" - return 1 - elif [ $minstep_y -lt 0 ] && [ $cur_y -lt $ast_y ]; then - # past the asteroid, we missed - debug_line "stop cond 2" - return 1 - elif [ $minstep_x -gt 0 ] && [ $cur_x -gt $ast_x ]; then - debug_line "stop cond 3" - return 1 - elif [ $minstep_y -gt 0 ] && [ $cur_y -gt $ast_y ]; then - debug_line "stop cond 4" + if [ $minstep_x -lt 0 -a $cur_x -lt $ast_x ] || + [ $minstep_y -lt 0 -a $cur_y -lt $ast_y ] || + [ $minstep_x -gt 0 -a $cur_x -gt $ast_x ] || + [ $minstep_y -gt 0 -a $cur_y -gt $ast_y ]; then + $debug_line "keepgoing finished" return 1 fi @@ -139,9 +217,13 @@ start_count=${#asteroids[@]} for asteroid in ${asteroid_loop[@]}; do ast1_x=${asteroid%,*} ast1_y=${asteroid#*,} - cur_count=${#asteroid_loop[@]} percent=$((100-(100*$cur_count / $start_count))) + + $debug_line "Doing fast checks" + fast_checks $asteroid + $debug_line "Running main loops" + printf '\r%02d%% complete' $percent for asteroid2 in ${asteroid_loop[@]}; do if [ $asteroid2 == $asteroid ]; then @@ -157,18 +239,25 @@ for asteroid in ${asteroid_loop[@]}; do continue fi - if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards + if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this for asteroid3 in "${!asteroids[@]}"; do if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then continue fi ast3_x=${asteroid3%,*} ast3_y=${asteroid3#*,} - debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3" + + # if this asteroid can't be in the way, continue the loop + if ! possibly_in_way $ast1_x $ast1_y $ast2_x $ast2_y $ast3_x $ast3_y; then + $debug_line "Apparently $ast1_x $ast1_y to $ast2_x $ast2_y cannot be blocked by $ast3_x $ast3_y" + continue + fi + + $debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3" vector2=$(get_vector $ast1_x $ast1_y $ast3_x $ast3_y) if ( check_collision $vector1 $vector2 ); then # path is blocked go on to next in outer loop - debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid" + $debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid" cantsee[$asteroid2,$asteroid]=1 cantsee[$asteroid,$asteroid2]=1 continue 2 @@ -176,7 +265,7 @@ for asteroid in ${asteroid_loop[@]}; do done fi # nothing blocked the view of asteroid2 from asteroid1 - debug_line "Apparently $asteroid can set $asteroid2" + $debug_line "Apparently $asteroid can see $asteroid2" asteroids[$asteroid]=$((${asteroids[$asteroid]}+1)) asteroids[$asteroid2]=$((${asteroids[$asteroid2]}+1)) cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path @@ -194,7 +283,7 @@ for asteroid in ${!asteroids[@]}; do best_count=$count best_ast=$asteroid fi - debug_line "$asteroid: ${asteroids[$asteroid]}" + $debug_line "$asteroid: ${asteroids[$asteroid]}" done echo "Best asteroid: $best_ast which can see $best_count asteroids" -- 2.39.5