day10/check_asteroids.sh

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