Minor refactor start

[advent-of-code-2019.git] / day10 / check_asteroids.sh

diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh
old mode 100644 (file)
new mode 100755 (executable)
index d333a33..efda359
--- a/day10/check_asteroids.sh
+++ b/day10/check_asteroids.sh
@@ -3,7 +3,11 @@
 set -u
 set -e
 
 set -u
 set -e
 

-filename=${1:-small_grid.txt}
+basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
+
+. $basedir/common.sh
+
+filename=${1:-$basedir/3_4_8.txt}

 
 exec 3<$filename
 
 
 exec 3<$filename
 


@@ -24,21 +28,15 @@ while read -u 3 line; do
     ln=$((ln+1))
 done
 
     ln=$((ln+1))
 done
 

-debug_line() {
-    line="$@"
-    #echo "$line" >&2
-}
+debug_line=true # default to not actually outputting any debug info

 
 

-get_vector() {
-    local x1=$1
-    local y1=$2
-    local x2=$3
-    local y2=$4
+if [ ${DEBUG:-0} -gt 0 ]; then
+    debug_line=debug_line
+fi

 
 

-    x_diff=$(($x1 - $x2))
-    y_diff=$(($y1 - $y2))
-
-    echo "$x_diff,$y_diff"
+debug_line() {
+    line="$@"
+    echo "$line" >&2

 }
 
 check_collision() {
 }
 
 check_collision() {


@@ -46,7 +44,7 @@ check_collision() {
     local vector1=$1
     local vector2=$2
 
     local vector1=$1
     local vector2=$2
 

-    debug_line Comparing: $vector1 $vector2
+    $debug_line Comparing: $vector1 $vector2

 
     vector1_x=${vector1%,*}
     vector1_y=${vector1#*,}
 
     vector1_x=${vector1%,*}
     vector1_y=${vector1#*,}


@@ -64,38 +62,37 @@ check_collision() {
     vector2_y_val=${vector2_y#-}
 
     minimum_number=$vector2_x_val
     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
 
         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
 
     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
             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
 
 
     # 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))
 
     # 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 echo "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
             return 0
         fi
     done


@@ -103,6 +100,97 @@ check_collision() {
     return 1
 }
 
     return 1
 }
 

+fast_checks() {
+    asteroid=$1
+    start_x=${asteroid%,*}
+    start_y=${asteroid#*,}
+
+    max_x=$width
+    max_y=$ln
+
+    # directions:
+    # -1, 0 - left
+    #  1, 0 - right
+    #  0, 1 - up
+    #  0,-1 - down
+    # -1, 1 - diagonal left down
+    # -1,-1 - diagonal left up
+    #  1, 1 - diagonal right down
+    #  1,-1 - diagonal right up
+    for direction in -1,0 1,0 0,1 0,-1 -1,1 -1,-1 1,1 1,-1; do
+    #for direction in "-1,0" "1,0" "0,1" "0,-1"; do
+        stepx=${direction%,*}
+        stepy=${direction#*,}
+        do_blocker_check $start_x $start_y $stepx $stepy
+    done
+}
+
+do_blocker_check() {
+    startx=$1
+    starty=$2
+    stepx=$3
+    stepy=$4
+
+    hitblocker=0
+
+    if [ $stepx -eq 0 -a $stepy -eq 0 ]; then
+        echo "Somehow got 0 and 0 as steps"
+        return
+    fi
+
+    local x=$startx
+    local y=$starty
+
+    # add the steps before we start the loop to not be
+    # on ourselves
+    x=$((x+$stepx))
+    y=$((y+$stepy))
+
+    while [ $x -le $width -a $x -ge 0 -a $y -le $ln -a $y -ge 0 ]; do
+        if [ ${asteroids[$x,$y]+a} ]; then
+            if [ $hitblocker -eq 0 ]; then
+                cansee[$asteroid,$x,$y]=1
+                cansee[$x,$y,$startx,$starty]=1
+                hitblocker=1
+            else
+                cantsee[$startx,$starty,$x,$y]=1
+                cantsee[$x,$y,$startx,$starty]=1
+            fi
+        fi
+        x=$((x+$stepx))
+        y=$((y+$stepy))
+    done
+}
+
+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
 keep_going() {
     local cur_x=$1
     local cur_y=$2


@@ -111,19 +199,11 @@ keep_going() {
     local ast_x=$5
     local ast_y=$6
 
     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
 
         return 1
     fi
 


@@ -132,13 +212,21 @@ keep_going() {
 
 # we check for if the first asteroid is blocked viewing the second asteroid
 # by the third asteroid, if not we add 1 to it's total
 
 # we check for if the first asteroid is blocked viewing the second asteroid
 # by the third asteroid, if not we add 1 to it's total

-for asteroid in ${!asteroids[@]}; do
-#for asteroid in 9,0; do
+asteroid_loop=("${!asteroids[@]}")
+index=0
+start_count=${#asteroids[@]}
+for asteroid in ${asteroid_loop[@]}; do

     ast1_x=${asteroid%,*}
     ast1_y=${asteroid#*,}
     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"

 
 

-    for asteroid2 in ${!asteroids[@]}; do
-    #for asteroid2 in 4,5; do
+    printf '\r%02d%% complete' $percent
+    for asteroid2 in ${asteroid_loop[@]}; do

         if [ $asteroid2 == $asteroid ]; then
             continue
         fi
         if [ $asteroid2 == $asteroid ]; then
             continue
         fi


@@ -152,18 +240,25 @@ for asteroid in ${!asteroids[@]}; do
             continue
         fi
 
             continue
         fi
 

-        if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards
-            for asteroid3 in ${!asteroids[@]}; do
+        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#*,}
                 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
                 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
                     cantsee[$asteroid2,$asteroid]=1
                     cantsee[$asteroid,$asteroid2]=1
                     continue 2


@@ -171,11 +266,15 @@ for asteroid in ${!asteroids[@]}; do
             done
         fi
         # nothing blocked the view of asteroid2 from asteroid1
             done
         fi
         # nothing blocked the view of asteroid2 from asteroid1

-        debug_line "Apparently $asteroid can set $asteroid2"
-        asteroids[$asteroid]=$((asteroids[$asteroid]+1))
+        $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
     done
         cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path
     done

+    unset asteroid_loop[$index]
+    index=$((index+1))

 done
 done

+echo -n $'\r'"                 "$'\r'

 
 best_ast=
 best_count=0
 
 best_ast=
 best_count=0


@@ -185,7 +284,7 @@ for asteroid in ${!asteroids[@]}; do
         best_count=$count
         best_ast=$asteroid
     fi
         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"
 done
 
 echo "Best asteroid: $best_ast which can see $best_count asteroids"