day10/check_asteroids.sh

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