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     max_x=$width
 119     max_y=$ln
 120
 121     # directions:
 122     # -1, 0 - left
 123     #  1, 0 - right
 124     #  0, 1 - up
 125     #  0,-1 - down
 126     # -1, 1 - diagonal left down
 127     # -1,-1 - diagonal left up
 128     #  1, 1 - diagonal right down
 129     #  1,-1 - diagonal right up
 130     for direction in -1,0 1,0 0,1 0,-1 -1,1 -1,-1 1,1 1,-1; do
 131     #for direction in "-1,0" "1,0" "0,1" "0,-1"; do
 132         stepx=${direction%,*}
 133         stepy=${direction#*,}
 134         do_blocker_check $start_x $start_y $stepx $stepy
 135     done
 136 }
 137
 138 do_blocker_check() {
 139     startx=$1
 140     starty=$2
 141     stepx=$3
 142     stepy=$4
 143
 144     hitblocker=0
 145
 146     if [ $stepx -eq 0 -a $stepy -eq 0 ]; then
 147         echo "Somehow got 0 and 0 as steps"
 148         return
 149     fi
 150
 151     local x=$startx
 152     local y=$starty
 153
 154     # add the steps before we start the loop to not be
 155     # on ourselves
 156     x=$((x+$stepx))
 157     y=$((y+$stepy))
 158
 159     while [ $x -le $width -a $x -ge 0 -a $y -le $ln -a $y -ge 0 ]; do
 160         if [ ${asteroids[$x,$y]+a} ]; then
 161             if [ $hitblocker -eq 0 ]; then
 162                 cansee[$asteroid,$x,$y]=1
 163                 cansee[$x,$y,$startx,$starty]=1
 164                 hitblocker=1
 165             else
 166                 cantsee[$startx,$starty,$x,$y]=1
 167                 cantsee[$x,$y,$startx,$starty]=1
 168             fi
 169         fi
 170         x=$((x+$stepx))
 171         y=$((y+$stepy))
 172     done
 173 }
 174
 175 possibly_in_way() {
 176     source_x=$1
 177     source_y=$2
 178     sink_x=$3
 179     sink_y=$4
 180     blocker_x=$5
 181     blocker_y=$6
 182
 183     # first check the horizontal and vertical planes
 184     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 ) ]] ||
 185        [[ ( $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
 186        return 0
 187     fi
 188
 189     # if our source asteroid is further to the right thank our sink, then to stand half a chance
 190     # of being in the way, the blocker has to be x > $sink_x and x < source_x
 191     # apply the same rule for y
 192     # reverse the direction and do the same checks.
 193     # So if source_x < sink_x then blocker_x has to be < sink_x > source_x
 194     if [ $source_x -gt $sink_x -a $blocker_x -gt $sink_x -a $blocker_x -lt $source_x ] ||
 195        [ $source_y -gt $sink_y -a $blocker_y -gt $sink_y -a $blocker_y -lt $source_y ] ||
 196        [ $source_x -lt $sink_x -a $blocker_x -lt $sink_x -a $blocker_x -gt $source_x ] ||
 197        [ $source_y -lt $sink_y -a $blocker_y -lt $sink_y -a $blocker_y -gt $source_y ]; then
 198        return 0
 199     fi
 200
 201     return 1
 202 }
 203
 204 keep_going() {
 205     local cur_x=$1
 206     local cur_y=$2
 207     local minstep_x=$3
 208     local minstep_y=$4
 209     local ast_x=$5
 210     local ast_y=$6
 211
 212     if [ $minstep_x -lt 0 -a $cur_x -lt $ast_x ] ||
 213        [ $minstep_y -lt 0 -a $cur_y -lt $ast_y ] ||
 214        [ $minstep_x -gt 0 -a $cur_x -gt $ast_x ] ||
 215        [ $minstep_y -gt 0 -a $cur_y -gt $ast_y ]; then
 216         $debug_line "keepgoing finished"
 217         return 1
 218     fi
 219
 220     return 0
 221 }
 222
 223 # we check for if the first asteroid is blocked viewing the second asteroid
 224 # by the third asteroid, if not we add 1 to it's total
 225 asteroid_loop=("${!asteroids[@]}")
 226 index=0
 227 start_count=${#asteroids[@]}
 228 for asteroid in ${asteroid_loop[@]}; do
 229     ast1_x=${asteroid%,*}
 230     ast1_y=${asteroid#*,}
 231     cur_count=${#asteroid_loop[@]}
 232     percent=$((100-(100*$cur_count / $start_count)))
 233
 234     $debug_line "Doing fast checks"
 235     fast_checks $asteroid
 236     $debug_line "Running main loops"
 237
 238     printf '\r%02d%% complete' $percent
 239     for asteroid2 in ${asteroid_loop[@]}; do
 240         if [ $asteroid2 == $asteroid ]; then
 241             continue
 242         fi
 243         ast2_x=${asteroid2%,*}
 244         ast2_y=${asteroid2#*,}
 245
 246         vector1=$(get_vector $ast1_x $ast1_y $ast2_x $ast2_y)
 247
 248         # if we've got a cached can't see, use it to continue the loop
 249         if [ ${cantsee[$asteroid,$asteroid2]+a} ]; then
 250             continue
 251         fi
 252
 253         if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this
 254             for asteroid3 in "${!asteroids[@]}"; do
 255                 if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then
 256                     continue
 257                 fi
 258                 ast3_x=${asteroid3%,*}
 259                 ast3_y=${asteroid3#*,}
 260
 261                 # if this asteroid can't be in the way, continue the loop
 262                 if ! possibly_in_way $ast1_x $ast1_y $ast2_x $ast2_y $ast3_x $ast3_y; then
 263                     $debug_line "Apparently $ast1_x $ast1_y to $ast2_x $ast2_y cannot be blocked by $ast3_x $ast3_y"
 264                     continue
 265                 fi
 266
 267                 $debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3"
 268                 vector2=$(get_vector $ast1_x $ast1_y $ast3_x $ast3_y)
 269                 if ( check_collision $vector1 $vector2 ); then
 270                     # path is blocked go on to next in outer loop
 271                     $debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid"
 272                     cantsee[$asteroid2,$asteroid]=1
 273                     cantsee[$asteroid,$asteroid2]=1
 274                     continue 2
 275                 fi
 276             done
 277         fi
 278         # nothing blocked the view of asteroid2 from asteroid1
 279         $debug_line "Apparently $asteroid can see $asteroid2"
 280         asteroids[$asteroid]=$((${asteroids[$asteroid]}+1))
 281         asteroids[$asteroid2]=$((${asteroids[$asteroid2]}+1))
 282         cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path
 283     done
 284     unset asteroid_loop[$index]
 285     index=$((index+1))
 286 done
 287 echo -n $'\r'"                 "$'\r'
 288
 289 best_ast=
 290 best_count=0
 291 for asteroid in ${!asteroids[@]}; do
 292     count=${asteroids[$asteroid]}
 293     if [ $count -gt $best_count ]; then
 294         best_count=$count
 295         best_ast=$asteroid
 296     fi
 297     $debug_line "$asteroid: ${asteroids[$asteroid]}"
 298 done
 299
 300 echo "Best asteroid: $best_ast which can see $best_count asteroids"
 301
 302 #echo -n "+"
 303 #printf "%.0s-" $(seq 1 $width)
 304 #echo "+"
 305 ## redraw the board with numbers
 306 #for (( a=0; a<$ln; a++ )); do
 307 #    echo -n "|"
 308 #    for (( b=0; b<$width; b++ )); do
 309 #        if [ ${asteroids[$b,$a]+a} ]; then
 310 #            echo -n ${asteroids[$b,$a]}
 311 #        else
 312 #            echo -n "."
 313 #        fi
 314 #    done
 315 #    echo "|"
 316 #done
 317 #echo -n "+"
 318 #printf "%.0s-" $(seq 1 $width)
 319 #echo "+"