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 e0bf9597eddbc6fd345d4f88e55e9d6d95ad132b..d0600bba598825981976175bfdceda7cd7fcc35c 100755 (executable)
--- a/day10/check_asteroids.sh
+++ b/day10/check_asteroids.sh
@@ -4,216 +4,56 @@ set -u
 set -e
 
 basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
 set -e
 
 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=debug_line
+fi

 
 debug_line() {
     line="$@"
 
 debug_line() {
     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 ] && [ $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 ] && [ $((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 ] && [ $cur_y -eq $vector1_y ]; then
-            debug_line "Collision!"
-            return 0
-        fi
-    done
-
-    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 ] && [ $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"
-        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)))
+# 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 backwards
-            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"
-                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 set $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