day10/check_asteroids.sh

   1 #!/bin/bash
   2
   3 set -u
   4 set -e
   5
   6 basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
   7
   8 filename=${1:-$basedir/3_4_8.txt}
   9
  10 exec 3<$filename
  11
  12 declare -A asteroids
  13 declare -A cansee
  14 declare -A cantsee
  15
  16 ln=0
  17 width=0
  18 while read -u 3 line; do
  19     width=${#line}
  20     for (( a=0; a<${#line}; a++ )); do
  21         char=${line:$a:1}
  22         if [ "${char}" == "#" ]; then
  23             asteroids[$a,$ln]=0
  24         fi
  25     done
  26     ln=$((ln+1))
  27 done
  28
  29 debug_line=true # default to not actually outputting any debug info
  30
  31 if [ ${DEBUG:-0} -gt 0 ]; then
  32     debug_line=debug_line
  33 fi
  34
  35 debug_line() {
  36     line="$@"
  37     echo "$line" >&2
  38 }
  39
  40 get_vector() {
  41     local x1=$1
  42     local y1=$2
  43     local x2=$3
  44     local y2=$4
  45
  46     x_diff=$(($x1 - $x2))
  47     y_diff=$(($y1 - $y2))
  48
  49     echo "$x_diff,$y_diff"
  50 }
  51
  52 check_collision() {
  53     # we want to know if vector2 is going to get in the way of vector1
  54     local vector1=$1
  55     local vector2=$2
  56
  57     $debug_line Comparing: $vector1 $vector2
  58
  59     vector1_x=${vector1%,*}
  60     vector1_y=${vector1#*,}
  61     vector2_x=${vector2%,*}
  62     vector2_y=${vector2#*,}
  63
  64     # potentially blocking asteroid
  65     # first calculate the minimum x and y steps that are whole numbers
  66     # min number first, we'll then halve it and work through the steps
  67
  68     # work out which asteroid is furthest from use
  69     vector1_x_val=${vector1_x#-}
  70     vector1_y_val=${vector1_y#-}
  71     vector2_x_val=${vector2_x#-}
  72     vector2_y_val=${vector2_y#-}
  73
  74     minimum_number=$vector2_x_val
  75     if [ $vector2_x_val -gt $vector2_y_val -a $vector2_y_val -gt 0 ] || [ $minimum_number -eq 0 ]; then
  76         minimum_number=$vector2_y_val
  77     fi
  78
  79     $debug_line "Min number: $minimum_number"
  80
  81     minstep_x=$vector2_x
  82     minstep_y=$vector2_y
  83     for (( a=$minimum_number; a>0; a-- )); do
  84         if [ $((vector2_x % $a)) -eq 0 -a $((vector2_y % $a)) -eq 0 ]; then
  85             minstep_x=$((vector2_x / $a))
  86             minstep_y=$((vector2_y / $a))
  87             break
  88         fi
  89     done
  90     $debug_line "Have minsteps: $minstep_x,$minstep_y"
  91
  92     # in all other cases, we're at least heading in the right direction
  93     cur_x=$vector2_x
  94     cur_y=$vector2_y
  95
  96     $debug_line "Looking for: $vector1_x,$vector1_y"
  97     $debug_line "Start: $cur_x,$cur_y"
  98
  99     # from the starting point, add the min steps until we're past the other asteroid
 100     while keep_going $cur_x $cur_y $minstep_x $minstep_y $vector1_x $vector1_y; do
 101         cur_x=$((cur_x+$minstep_x))
 102         cur_y=$((cur_y+$minstep_y))
 103         $debug_line "Step: $cur_x,$cur_y"
 104         if [ $cur_x -eq $vector1_x -a $cur_y -eq $vector1_y ]; then
 105             $debug_line "Collision!"
 106             return 0
 107         fi
 108     done
 109
 110     return 1
 111 }
 112
 113 fast_checks() {
 114     asteroid=$1
 115     start_x=${asteroid%,*}
 116     start_y=${asteroid#*,}
 117
 118     hitblocker=0
 119
 120     max_x=$width
 121     max_y=$ln
 122
 123     # first, head left of the asteroid
 124     for (( x=$((start_x-1)); x>=0; x-- )); do
 125         do_blocker_check $asteroid $x $start_y
 126     done
 127     hitblocker=0 # this gets updated in do_blocker_check, reset it
 128
 129     # now head right of the asteroid
 130     for (( x=$(($start_x+1)); x<= $width; x++ )); do
 131         do_blocker_check $asteroid $x $start_y
 132     done
 133     hitblocker=0 # this gets updated in do_blocker_check, reset it
 134
 135     # head upwards
 136     for (( y=$((start_y-1)); y>=0; y-- )); do
 137         do_blocker_check $asteroid $start_x $y
 138     done
 139     hitblocker=0 # this gets updated in do_blocker_check, reset it
 140
 141     # head down
 142     for (( y=$((start_y+1)); y<=$ln; y++  )); do
 143         do_blocker_check $asteroid $start_x $y
 144     done
 145 }
 146
 147 do_blocker_check() {
 148     asteroid=$1
 149     x=$2
 150     y=$3
 151
 152     if [ ${asteroids[$x,$y]+a} ]; then
 153         if [ $hitblocker -eq 0 ]; then
 154             cansee[$asteroid,$x,$y]=1
 155             cansee[$x,$y,$asteroid]=1
 156             hitblocker=1
 157         else
 158             cantsee[$asteroid,$x,$y]=1
 159             cantsee[$x,$y,$asteroid]=1
 160         fi
 161     fi
 162 }
 163
 164 possibly_in_way() {
 165     source_x=$1
 166     source_y=$2
 167     sink_x=$3
 168     sink_y=$4
 169     blocker_x=$5
 170     blocker_y=$6
 171
 172     # first check the horizontal and vertical planes
 173     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 ) ]] ||
 174        [[ ( $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
 175        return 0
 176     fi
 177
 178     # if our source asteroid is further to the right thank our sink, then to stand half a chance
 179     # of being in the way, the blocker has to be x > $sink_x and x < source_x
 180     # apply the same rule for y
 181     # reverse the direction and do the same checks.
 182     # So if source_x < sink_x then blocker_x has to be < sink_x > source_x
 183     if [ $source_x -gt $sink_x -a $blocker_x -gt $sink_x -a $blocker_x -lt $source_x ] ||
 184        [ $source_y -gt $sink_y -a $blocker_y -gt $sink_y -a $blocker_y -lt $source_y ] ||
 185        [ $source_x -lt $sink_x -a $blocker_x -lt $sink_x -a $blocker_x -gt $source_x ] ||
 186        [ $source_y -lt $sink_y -a $blocker_y -lt $sink_y -a $blocker_y -gt $source_y ]; then
 187        return 0
 188     fi
 189
 190     return 1
 191 }
 192
 193 keep_going() {
 194     local cur_x=$1
 195     local cur_y=$2
 196     local minstep_x=$3
 197     local minstep_y=$4
 198     local ast_x=$5
 199     local ast_y=$6
 200
 201     if [ $minstep_x -lt 0 -a $cur_x -lt $ast_x ] ||
 202        [ $minstep_y -lt 0 -a $cur_y -lt $ast_y ] ||
 203        [ $minstep_x -gt 0 -a $cur_x -gt $ast_x ] ||
 204        [ $minstep_y -gt 0 -a $cur_y -gt $ast_y ]; then
 205         $debug_line "keepgoing finished"
 206         return 1
 207     fi
 208
 209     return 0
 210 }
 211
 212 # we check for if the first asteroid is blocked viewing the second asteroid
 213 # by the third asteroid, if not we add 1 to it's total
 214 asteroid_loop=("${!asteroids[@]}")
 215 index=0
 216 start_count=${#asteroids[@]}
 217 for asteroid in ${asteroid_loop[@]}; do
 218     ast1_x=${asteroid%,*}
 219     ast1_y=${asteroid#*,}
 220     cur_count=${#asteroid_loop[@]}
 221     percent=$((100-(100*$cur_count / $start_count)))
 222
 223     $debug_line "Doing fast checks"
 224     fast_checks $asteroid
 225     $debug_line "Running main loops"
 226
 227     printf '\r%02d%% complete' $percent
 228     for asteroid2 in ${asteroid_loop[@]}; do
 229         if [ $asteroid2 == $asteroid ]; then
 230             continue
 231         fi
 232         ast2_x=${asteroid2%,*}
 233         ast2_y=${asteroid2#*,}
 234
 235         vector1=$(get_vector $ast1_x $ast1_y $ast2_x $ast2_y)
 236
 237         # if we've got a cached can't see, use it to continue the loop
 238         if [ ${cantsee[$asteroid,$asteroid2]+a} ]; then
 239             continue
 240         fi
 241
 242         if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this
 243             for asteroid3 in "${!asteroids[@]}"; do
 244                 if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then
 245                     continue
 246                 fi
 247                 ast3_x=${asteroid3%,*}
 248                 ast3_y=${asteroid3#*,}
 249
 250                 # if this asteroid can't be in the way, continue the loop
 251                 if ! possibly_in_way $ast1_x $ast1_y $ast2_x $ast2_y $ast3_x $ast3_y; then
 252                     $debug_line "Apparently $ast1_x $ast1_y to $ast2_x $ast2_y cannot be blocked by $ast3_x $ast3_y"
 253                     continue
 254                 fi
 255
 256                 $debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3"
 257                 vector2=$(get_vector $ast1_x $ast1_y $ast3_x $ast3_y)
 258                 if ( check_collision $vector1 $vector2 ); then
 259                     # path is blocked go on to next in outer loop
 260                     $debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid"
 261                     cantsee[$asteroid2,$asteroid]=1
 262                     cantsee[$asteroid,$asteroid2]=1
 263                     continue 2
 264                 fi
 265             done
 266         fi
 267         # nothing blocked the view of asteroid2 from asteroid1
 268         $debug_line "Apparently $asteroid can see $asteroid2"
 269         asteroids[$asteroid]=$((${asteroids[$asteroid]}+1))
 270         asteroids[$asteroid2]=$((${asteroids[$asteroid2]}+1))
 271         cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path
 272     done
 273     unset asteroid_loop[$index]
 274     index=$((index+1))
 275 done
 276 echo -n $'\r'"                 "$'\r'
 277
 278 best_ast=
 279 best_count=0
 280 for asteroid in ${!asteroids[@]}; do
 281     count=${asteroids[$asteroid]}
 282     if [ $count -gt $best_count ]; then
 283         best_count=$count
 284         best_ast=$asteroid
 285     fi
 286     $debug_line "$asteroid: ${asteroids[$asteroid]}"
 287 done
 288
 289 echo "Best asteroid: $best_ast which can see $best_count asteroids"
 290
 291 #echo -n "+"
 292 #printf "%.0s-" $(seq 1 $width)
 293 #echo "+"
 294 ## redraw the board with numbers
 295 #for (( a=0; a<$ln; a++ )); do
 296 #    echo -n "|"
 297 #    for (( b=0; b<$width; b++ )); do
 298 #        if [ ${asteroids[$b,$a]+a} ]; then
 299 #            echo -n ${asteroids[$b,$a]}
 300 #        else
 301 #            echo -n "."
 302 #        fi
 303 #    done
 304 #    echo "|"
 305 #done
 306 #echo -n "+"
 307 #printf "%.0s-" $(seq 1 $width)
 308 #echo "+"