day10/check_asteroids.sh

   1 #!/bin/bash
   2
   3 set -u
   4 set -e
   5
   6 filename=${1:-small_grid.txt}
   7
   8 exec 3<$filename
   9
  10 declare -A asteroids
  11 declare -A cansee
  12 declare -A cantsee
  13
  14 ln=0
  15 width=0
  16 while read -u 3 line; do
  17     width=${#line}
  18     for (( a=0; a<${#line}; a++ )); do
  19         char=${line:$a:1}
  20         if [ "${char}" == "#" ]; then
  21             asteroids[$a,$ln]=0
  22         fi
  23     done
  24     ln=$((ln+1))
  25 done
  26
  27 debug_line() {
  28     line="$@"
  29     #echo "$line" >&2
  30 }
  31
  32 get_vector() {
  33     local x1=$1
  34     local y1=$2
  35     local x2=$3
  36     local y2=$4
  37
  38     x_diff=$(($x1 - $x2))
  39     y_diff=$(($y1 - $y2))
  40
  41     echo "$x_diff,$y_diff"
  42 }
  43
  44 check_collision() {
  45     # we want to know if vector2 is going to get in the way of vector1
  46     local vector1=$1
  47     local vector2=$2
  48
  49     debug_line Comparing: $vector1 $vector2
  50
  51     vector1_x=${vector1%,*}
  52     vector1_y=${vector1#*,}
  53     vector2_x=${vector2%,*}
  54     vector2_y=${vector2#*,}
  55
  56     # potentially blocking asteroid
  57     # first calculate the minimum x and y steps that are whole numbers
  58     # min number first, we'll then halve it and work through the steps
  59
  60     # work out which asteroid is furthest from use
  61     vector1_x_val=${vector1_x#-}
  62     vector1_y_val=${vector1_y#-}
  63     vector2_x_val=${vector2_x#-}
  64     vector2_y_val=${vector2_y#-}
  65
  66     minimum_number=$vector2_x_val
  67     if ( [ $vector2_x_val -gt $vector2_y_val ] && [ $vector2_y_val -gt 0 ] ) ||
  68         [ $minimum_number -eq 0 ]; then
  69         minimum_number=$vector2_y_val
  70     fi
  71
  72     debug_line "Min number: $minimum_number"
  73
  74     minstep_x=$vector2_x
  75     minstep_y=$vector2_y
  76     for (( a=$minimum_number; a>0; a-- )); do
  77         if [ $((vector2_x % $a)) -eq 0 ] && [ $((vector2_y % $a)) -eq 0 ]; then
  78             minstep_x=$((vector2_x / $a))
  79             minstep_y=$((vector2_y / $a))
  80             break
  81         fi
  82     done
  83     debug_line "Have minsteps: $minstep_x,$minstep_y"
  84
  85     # in all other cases, we're at least heading in the right direction
  86     cur_x=$vector2_x
  87     cur_y=$vector2_y
  88
  89     debug_line "Looking for: $vector1_x,$vector1_y"
  90     debug_line "Start: $cur_x,$cur_y"
  91
  92     # from the starting point, add the min steps until we're past the other asteroid
  93     while keep_going $cur_x $cur_y $minstep_x $minstep_y $vector1_x $vector1_y; do
  94         cur_x=$((cur_x+$minstep_x))
  95         cur_y=$((cur_y+$minstep_y))
  96         debug_line "Step: $cur_x,$cur_y"
  97         if [ $cur_x -eq $vector1_x ] && [ $cur_y -eq $vector1_y ]; then
  98             debug_line echo "Collision!"
  99             return 0
 100         fi
 101     done
 102
 103     return 1
 104 }
 105
 106 keep_going() {
 107     local cur_x=$1
 108     local cur_y=$2
 109     local minstep_x=$3
 110     local minstep_y=$4
 111     local ast_x=$5
 112     local ast_y=$6
 113
 114     if [ $minstep_x -lt 0 ] && [ $cur_x -lt $ast_x ]; then
 115         # past the asteroid, we missed
 116         debug_line "stop cond 1"
 117         return 1
 118     elif [ $minstep_y -lt 0 ] && [ $cur_y -lt $ast_y ]; then
 119         # past the asteroid, we missed
 120         debug_line "stop cond 2"
 121         return 1
 122     elif [ $minstep_x -gt 0 ] && [ $cur_x -gt $ast_x ]; then
 123         debug_line "stop cond 3"
 124         return 1
 125     elif [ $minstep_y -gt 0 ] && [ $cur_y -gt $ast_y ]; then
 126         debug_line "stop cond 4"
 127         return 1
 128     fi
 129
 130     return 0
 131 }
 132
 133 # we check for if the first asteroid is blocked viewing the second asteroid
 134 # by the third asteroid, if not we add 1 to it's total
 135 for asteroid in ${!asteroids[@]}; do
 136 #for asteroid in 9,0; do
 137     ast1_x=${asteroid%,*}
 138     ast1_y=${asteroid#*,}
 139
 140     for asteroid2 in ${!asteroids[@]}; do
 141     #for asteroid2 in 4,5; do
 142         if [ $asteroid2 == $asteroid ]; then
 143             continue
 144         fi
 145         ast2_x=${asteroid2%,*}
 146         ast2_y=${asteroid2#*,}
 147
 148         vector1=$(get_vector $ast1_x $ast1_y $ast2_x $ast2_y)
 149
 150         # if we've got a cached can't see, use it to continue the loop
 151         if [ ${cantsee[$asteroid,$asteroid2]+a} ]; then
 152             continue
 153         fi
 154
 155         if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards
 156             for asteroid3 in ${!asteroids[@]}; do
 157                 if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then
 158                     continue
 159                 fi
 160                 ast3_x=${asteroid3%,*}
 161                 ast3_y=${asteroid3#*,}
 162                 debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3"
 163                 vector2=$(get_vector $ast1_x $ast1_y $ast3_x $ast3_y)
 164                 if ( check_collision $vector1 $vector2 ); then
 165                     # path is blocked go on to next in outer loop
 166                     debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid"
 167                     cantsee[$asteroid2,$asteroid]=1
 168                     cantsee[$asteroid,$asteroid2]=1
 169                     continue 2
 170                 fi
 171             done
 172         fi
 173         # nothing blocked the view of asteroid2 from asteroid1
 174         debug_line "Apparently $asteroid can set $asteroid2"
 175         asteroids[$asteroid]=$((asteroids[$asteroid]+1))
 176         cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path
 177     done
 178 done
 179
 180 best_ast=
 181 best_count=0
 182 for asteroid in ${!asteroids[@]}; do
 183     count=${asteroids[$asteroid]}
 184     if [ $count -gt $best_count ]; then
 185         best_count=$count
 186         best_ast=$asteroid
 187     fi
 188     debug_line "$asteroid: ${asteroids[$asteroid]}"
 189 done
 190
 191 echo "Best asteroid: $best_ast which can see $best_count asteroids"
 192
 193 #echo -n "+"
 194 #printf "%.0s-" $(seq 1 $width)
 195 #echo "+"
 196 ## redraw the board with numbers
 197 #for (( a=0; a<$ln; a++ )); do
 198 #    echo -n "|"
 199 #    for (( b=0; b<$width; b++ )); do
 200 #        if [ ${asteroids[$b,$a]+a} ]; then
 201 #            echo -n ${asteroids[$b,$a]}
 202 #        else
 203 #            echo -n "."
 204 #        fi
 205 #    done
 206 #    echo "|"
 207 #done
 208 #echo -n "+"
 209 #printf "%.0s-" $(seq 1 $width)
 210 #echo "+"