Add small README

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

diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh
index 8faf834395650a0e862fa7ef3d78c76a574f5b1c..d0600bba598825981976175bfdceda7cd7fcc35c 100755 (executable)
--- a/day10/check_asteroids.sh
+++ b/day10/check_asteroids.sh
@@ -5,27 +5,15 @@ set -e
 
 basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
 
 
 basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
 

+. $basedir/common.sh
+

 filename=${1:-$basedir/3_4_8.txt}
 
 filename=${1:-$basedir/3_4_8.txt}
 

-exec 3<$filename
+read_file $filename

 
 

-declare -A asteroids

 declare -A cansee
 declare -A cantsee
 
 declare -A cansee
 declare -A cantsee
 

-ln=0
-width=0
-while read -u 3 line; do
-    width=${#line}
-    for (( a=0; a<${#line}; a++ )); do
-        char=${line:$a:1}
-        if [ "${char}" == "#" ]; then
-            asteroids[$a,$ln]=0
-        fi
-    done
-    ln=$((ln+1))
-done
-

 debug_line=true # default to not actually outputting any debug info
 
 if [ ${DEBUG:-0} -gt 0 ]; then
 debug_line=true # default to not actually outputting any debug info
 
 if [ ${DEBUG:-0} -gt 0 ]; then


@@ -37,272 +25,35 @@ debug_line() {
     echo "$line" >&2
 }
 
     echo "$line" >&2
 }
 

-get_vector() {
-    local x1=$1
-    local y1=$2
-    local x2=$3
-    local y2=$4
-
-    x_diff=$(($x1 - $x2))
-    y_diff=$(($y1 - $y2))
-
-    echo "$x_diff,$y_diff"
-}
-
-check_collision() {
-    # we want to know if vector2 is going to get in the way of vector1
-    local vector1=$1
-    local vector2=$2
-
-    $debug_line Comparing: $vector1 $vector2
-
-    vector1_x=${vector1%,*}
-    vector1_y=${vector1#*,}
-    vector2_x=${vector2%,*}
-    vector2_y=${vector2#*,}
-
-    # potentially blocking asteroid
-    # first calculate the minimum x and y steps that are whole numbers
-    # min number first, we'll then halve it and work through the steps
-
-    # work out which asteroid is furthest from use
-    vector1_x_val=${vector1_x#-}
-    vector1_y_val=${vector1_y#-}
-    vector2_x_val=${vector2_x#-}
-    vector2_y_val=${vector2_y#-}
-
-    minimum_number=$vector2_x_val
-    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"
-
-    minstep_x=$vector2_x
-    minstep_y=$vector2_y
-    for (( a=$minimum_number; a>0; a-- )); do
-        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"
-
-    # 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"
-
-    # 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 -a $cur_y -eq $vector1_y ]; then
-            $debug_line "Collision!"
-            return 0
-        fi
-    done
-
-    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
-    local minstep_x=$3
-    local minstep_y=$4
-    local ast_x=$5
-    local ast_y=$6
-
-    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 0
-}
-
-# 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
-asteroid_loop=("${!asteroids[@]}")
-index=0
-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"
-
+# lets be silly and use the stuff from zap to build the lists instead
+best_count=0
+best_ast=
+cur_ast_num=0
+total_asts=${#asteroids[@]}
+for asteroid in ${!asteroids[@]}; do
+    percent=$((100*$cur_ast_num / $total_asts))

     printf '\r%02d%% complete' $percent
     printf '\r%02d%% complete' $percent

-    for asteroid2 in ${asteroid_loop[@]}; do
-        if [ $asteroid2 == $asteroid ]; then
-            continue
-        fi
-        ast2_x=${asteroid2%,*}
-        ast2_y=${asteroid2#*,}
-
-        vector1=$(get_vector $ast1_x $ast1_y $ast2_x $ast2_y)

 
 

-        # if we've got a cached can't see, use it to continue the loop
-        if [ ${cantsee[$asteroid,$asteroid2]+a} ]; then
+    # get a full list of angles for each other asteroid
+    declare -A asteroid_angles
+    for asteroid2 in ${!asteroids[@]}; do
+        if [ $asteroid == $asteroid2 ]; then

             continue
         fi
 
             continue
         fi
 

-        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 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"
-                    cantsee[$asteroid2,$asteroid]=1
-                    cantsee[$asteroid,$asteroid2]=1
-                    continue 2
-                fi
-            done
-        fi
-        # nothing blocked the view of asteroid2 from asteroid1
-        $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
+        angle=$(get_angle $asteroid $asteroid2)
+        asteroid_angles[$angle]=1

     done
     done

-    unset asteroid_loop[$index]
-    index=$((index+1))
-done
-echo -n $'\r'"                 "$'\r'
-
-best_ast=
-best_count=0
-for asteroid in ${!asteroids[@]}; do
-    count=${asteroids[$asteroid]}
+    count=${#asteroid_angles[@]}

     if [ $count -gt $best_count ]; then
         best_count=$count
         best_ast=$asteroid
     fi
     if [ $count -gt $best_count ]; then
         best_count=$count
         best_ast=$asteroid
     fi

-    $debug_line "$asteroid: ${asteroids[$asteroid]}"
+    asteroid[$asteroid]=${#asteroid_angles[@]}
+    unset asteroid_angles
+    cur_ast_num=$((cur_ast_num+1))

 done
 done

+printf '\r                              \r'

 
 

-echo "Best asteroid: $best_ast which can see $best_count asteroids"
-
-#echo -n "+"
-#printf "%.0s-" $(seq 1 $width)
-#echo "+"
-## redraw the board with numbers
-#for (( a=0; a<$ln; a++ )); do
-#    echo -n "|"
-#    for (( b=0; b<$width; b++ )); do
-#        if [ ${asteroids[$b,$a]+a} ]; then
-#            echo -n ${asteroids[$b,$a]}
-#        else
-#            echo -n "."
-#        fi
-#    done
-#    echo "|"
-#done
-#echo -n "+"
-#printf "%.0s-" $(seq 1 $width)
-#echo "+"
+echo "Found $best_ast with $best_count asteroids"
+exit 0