day10/zap.sh

   1 #!/bin/bash
   2
   3 basedir=$(dirname $(readlink -f $BASH_SOURCE))
   4 . $basedir/common.sh
   5
   6 our_asteroid=26,29
   7
   8 declare -A asteroids
   9 declare -A asteroid_angles
  10
  11 exec 3<input.txt
  12 ln=0
  13 width=0
  14 while read -u 3 line; do
  15     width=${#line}
  16     for (( a=0; a<${#line}; a++ )); do
  17         char=${line:$a:1}
  18         if [ "${char}" == "#" ]; then
  19             asteroids[$a,$ln]=0
  20         fi
  21     done
  22     ln=$((ln+1))
  23 done
  24
  25 get_angle() {
  26     local a1=$1
  27     local a2=$2
  28
  29     local vector=$(get_asteroids_vector $a1 $a2)
  30     local move_x=${vector%,*}
  31     local move_y=${vector#*,}
  32
  33     val="$(calc -p 'round(((90 + ((180/pi()) * atan2('$move_y','$move_x'))) % 360) * 100000000) / 100000000')"
  34     echo "$val"
  35 }
  36
  37 get_closest_asteroid() {
  38     local asteroids=$1
  39
  40     local IFS="|"
  41     local min_dist=-1
  42     local nearest_asteroid=
  43     local x=0
  44     local y=0
  45
  46     for asteroid in $asteroids; do
  47         vector=$(get_asteroids_vector $our_asteroid $asteroid)
  48         x=${vector%,*}
  49         y=${vector#*,}
  50         # use absolute numbers for length calculation!
  51         x=${x#-}
  52         y=${y#-}
  53
  54         distance=$((x+y))
  55         if [ $distance -lt $min_dist -o $min_dist -eq -1 ]; then
  56             min_dist=$distance
  57             nearest_asteroid=$asteroid
  58         fi
  59     done
  60
  61     echo $nearest_asteroid
  62 }
  63
  64 remove_asteroid_from_string() {
  65     local asteroids=$1
  66     local asteroid=$2
  67     local new_asteroids=
  68     local a
  69
  70     local IFS="|"
  71     local seperator=""
  72
  73     for a in $asteroids; do
  74         if [ "$a" != "$asteroid" ]; then
  75             new_asteroids+="${seperator}$a"
  76         fi
  77         if [ "x$new_asteroids" != "x" ]; then
  78             seperator="|"
  79         fi
  80     done
  81
  82     echo "$new_asteroids"
  83 }
  84
  85 # calculate angles to each asteroid from us
  86 for asteroid in ${!asteroids[@]}; do
  87     if [ $asteroid == $our_asteroid ]; then
  88         continue
  89     fi
  90
  91     # otherwise, get the angle from us to there
  92     angle=$(get_angle $our_asteroid $asteroid)
  93
  94     # see if we've already got this angle as a key, if so append to it,
  95     # otherwise set it
  96     if [ ${asteroid_angles[$angle]+a} ]; then
  97         asteroid_angles[$angle]+="|$asteroid"
  98     else
  99         asteroid_angles[$angle]=$asteroid
 100     fi
 101 done
 102
 103 zapped_count=0
 104
 105 get_angles_list() {
 106     local OFS=$'\n'
 107
 108     printf "%s\n" "${!asteroid_angles[@]}" | sort -g
 109 }
 110
 111 sorted_angles=( "$(get_angles_list)" )
 112
 113 for (( round=0; round<3; round++ )); do
 114     for angle in $sorted_angles; do
 115         if [ ${asteroid_angles[$angle]+a} ]; then
 116             echo "$angle: ${asteroid_angles[$angle]}"
 117             closest=$(get_closest_asteroid "${asteroid_angles[$angle]}")
 118             #echo "      - closest $closest"
 119             # blow up the closest!
 120             newlist=$(remove_asteroid_from_string ${asteroid_angles[$angle]} $closest)
 121             if [ "x$newlist" == "x" ]; then
 122                 unset asteroid_angles[$angle]
 123             else
 124                 asteroid_angles[$angle]=$newlist
 125             fi
 126             zapped_count=$((zapped_count+1))
 127
 128             echo "$zapped_count: $closest"
 129
 130             if [ $zapped_count -eq 200 ]; then
 131                 echo "The 200th asteroid to be zapped was $closest"
 132                 break 2
 133             fi
 134         fi
 135     done
 136 done
 137
 138 echo "And we're done."