X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2019.git/blobdiff_plain/8d19ec771c083ce8bbfff9b075d42f15ad704831..3e8dd8ef406fe4f224dfedabca1fe6f306702bd5:/day10/check_asteroids.sh diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh index 84958ed..d0600bb 100755 --- a/day10/check_asteroids.sh +++ b/day10/check_asteroids.sh @@ -4,208 +4,56 @@ set -u set -e basedir=$(dirname $(readlink -f ${BASH_SOURCE})) + +. $basedir/common.sh + filename=${1:-$basedir/3_4_8.txt} -exec 3<$filename +read_file $filename -declare -A asteroids 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="$@" - #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 echo "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 + echo "$line" >&2 } -# 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 +# 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 -#for asteroid in 9,0; do - ast1_x=${asteroid%,*} - ast1_y=${asteroid#*,} + percent=$((100*$cur_ast_num / $total_asts)) + printf '\r%02d%% complete' $percent + # get a full list of angles for each other asteroid + declare -A asteroid_angles for asteroid2 in ${!asteroids[@]}; do - #for asteroid2 in 4,5; do - if [ $asteroid2 == $asteroid ]; then + if [ $asteroid == $asteroid2 ]; 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 - 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)) - 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 - -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 - debug_line "$asteroid: ${asteroids[$asteroid]}" + asteroid[$asteroid]=${#asteroid_angles[@]} + unset asteroid_angles + cur_ast_num=$((cur_ast_num+1)) 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