set -e
basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
+
+. $basedir/common.sh
+
filename=${1:-$basedir/3_4_8.txt}
-exec 3<$filename
+read_file $filename
-declare -A asteroids
declare -A cansee
declare -A cantsee
-ln=0
-width=0
-while read -u 3 line; do
- width=${#line}
- for (( a=0; a<${#line}; a++ )); do
- char=${line:$a:1}
- if [ "${char}" == "#" ]; then
- asteroids[$a,$ln]=0
- fi
- done
- ln=$((ln+1))
-done
+debug_line=true # default to not actually outputting any debug info
+
+if [ ${DEBUG:-0} -gt 0 ]; then
+ debug_line=debug_line
+fi
debug_line() {
line="$@"
- #echo "$line" >&2
-}
-
-get_vector() {
- local x1=$1
- local y1=$2
- local x2=$3
- local y2=$4
-
- x_diff=$(($x1 - $x2))
- y_diff=$(($y1 - $y2))
-
- echo "$x_diff,$y_diff"
-}
-
-check_collision() {
- # we want to know if vector2 is going to get in the way of vector1
- local vector1=$1
- local vector2=$2
-
- debug_line Comparing: $vector1 $vector2
-
- vector1_x=${vector1%,*}
- vector1_y=${vector1#*,}
- vector2_x=${vector2%,*}
- vector2_y=${vector2#*,}
-
- # potentially blocking asteroid
- # first calculate the minimum x and y steps that are whole numbers
- # min number first, we'll then halve it and work through the steps
-
- # work out which asteroid is furthest from use
- vector1_x_val=${vector1_x#-}
- vector1_y_val=${vector1_y#-}
- vector2_x_val=${vector2_x#-}
- vector2_y_val=${vector2_y#-}
-
- minimum_number=$vector2_x_val
- if ( [ $vector2_x_val -gt $vector2_y_val ] && [ $vector2_y_val -gt 0 ] ) ||
- [ $minimum_number -eq 0 ]; then
- minimum_number=$vector2_y_val
- fi
-
- debug_line "Min number: $minimum_number"
-
- minstep_x=$vector2_x
- minstep_y=$vector2_y
- for (( a=$minimum_number; a>0; a-- )); do
- if [ $((vector2_x % $a)) -eq 0 ] && [ $((vector2_y % $a)) -eq 0 ]; then
- minstep_x=$((vector2_x / $a))
- minstep_y=$((vector2_y / $a))
- break
- fi
- done
- debug_line "Have minsteps: $minstep_x,$minstep_y"
-
- # in all other cases, we're at least heading in the right direction
- cur_x=$vector2_x
- cur_y=$vector2_y
-
- debug_line "Looking for: $vector1_x,$vector1_y"
- debug_line "Start: $cur_x,$cur_y"
-
- # from the starting point, add the min steps until we're past the other asteroid
- while keep_going $cur_x $cur_y $minstep_x $minstep_y $vector1_x $vector1_y; do
- cur_x=$((cur_x+$minstep_x))
- cur_y=$((cur_y+$minstep_y))
- debug_line "Step: $cur_x,$cur_y"
- if [ $cur_x -eq $vector1_x ] && [ $cur_y -eq $vector1_y ]; then
- debug_line echo "Collision!"
- return 0
- fi
- done
-
- return 1
-}
-
-keep_going() {
- local cur_x=$1
- local cur_y=$2
- local minstep_x=$3
- local minstep_y=$4
- local ast_x=$5
- local ast_y=$6
-
- if [ $minstep_x -lt 0 ] && [ $cur_x -lt $ast_x ]; then
- # past the asteroid, we missed
- debug_line "stop cond 1"
- return 1
- elif [ $minstep_y -lt 0 ] && [ $cur_y -lt $ast_y ]; then
- # past the asteroid, we missed
- debug_line "stop cond 2"
- return 1
- elif [ $minstep_x -gt 0 ] && [ $cur_x -gt $ast_x ]; then
- debug_line "stop cond 3"
- return 1
- elif [ $minstep_y -gt 0 ] && [ $cur_y -gt $ast_y ]; then
- debug_line "stop cond 4"
- return 1
- fi
-
- return 0
+ echo "$line" >&2
}
-# we check for if the first asteroid is blocked viewing the second asteroid
-# by the third asteroid, if not we add 1 to it's total
+# lets be silly and use the stuff from zap to build the lists instead
+best_count=0
+best_ast=
+cur_ast_num=0
+total_asts=${#asteroids[@]}
for asteroid in ${!asteroids[@]}; do
-#for asteroid in 9,0; do
- ast1_x=${asteroid%,*}
- ast1_y=${asteroid#*,}
+ percent=$((100*$cur_ast_num / $total_asts))
+ printf '\r%02d%% complete' $percent
+ # get a full list of angles for each other asteroid
+ declare -A asteroid_angles
for asteroid2 in ${!asteroids[@]}; do
- #for asteroid2 in 4,5; do
- if [ $asteroid2 == $asteroid ]; then
+ if [ $asteroid == $asteroid2 ]; then
continue
fi
- ast2_x=${asteroid2%,*}
- ast2_y=${asteroid2#*,}
- vector1=$(get_vector $ast1_x $ast1_y $ast2_x $ast2_y)
-
- # if we've got a cached can't see, use it to continue the loop
- if [ ${cantsee[$asteroid,$asteroid2]+a} ]; then
- continue
- fi
-
- if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards
- for asteroid3 in ${!asteroids[@]}; do
- if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then
- continue
- fi
- ast3_x=${asteroid3%,*}
- ast3_y=${asteroid3#*,}
- debug_line "Checking for collision between $asteroid and $asteroid2 by $asteroid3"
- vector2=$(get_vector $ast1_x $ast1_y $ast3_x $ast3_y)
- if ( check_collision $vector1 $vector2 ); then
- # path is blocked go on to next in outer loop
- debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid"
- cantsee[$asteroid2,$asteroid]=1
- cantsee[$asteroid,$asteroid2]=1
- continue 2
- fi
- done
- fi
- # nothing blocked the view of asteroid2 from asteroid1
- debug_line "Apparently $asteroid can set $asteroid2"
- asteroids[$asteroid]=$((asteroids[$asteroid]+1))
- cansee[$asteroid2,$asteroid]=1 # don't bother doing the expensive calculations on the return path
+ angle=$(get_angle $asteroid $asteroid2)
+ asteroid_angles[$angle]=1
done
-done
-
-best_ast=
-best_count=0
-for asteroid in ${!asteroids[@]}; do
- count=${asteroids[$asteroid]}
+ count=${#asteroid_angles[@]}
if [ $count -gt $best_count ]; then
best_count=$count
best_ast=$asteroid
fi
- debug_line "$asteroid: ${asteroids[$asteroid]}"
+ asteroid[$asteroid]=${#asteroid_angles[@]}
+ unset asteroid_angles
+ cur_ast_num=$((cur_ast_num+1))
done
+printf '\r \r'
-echo "Best asteroid: $best_ast which can see $best_count asteroids"
-
-#echo -n "+"
-#printf "%.0s-" $(seq 1 $width)
-#echo "+"
-## redraw the board with numbers
-#for (( a=0; a<$ln; a++ )); do
-# echo -n "|"
-# for (( b=0; b<$width; b++ )); do
-# if [ ${asteroids[$b,$a]+a} ]; then
-# echo -n ${asteroids[$b,$a]}
-# else
-# echo -n "."
-# fi
-# done
-# echo "|"
-#done
-#echo -n "+"
-#printf "%.0s-" $(seq 1 $width)
-#echo "+"
+echo "Found $best_ast with $best_count asteroids"
+exit 0
projects / advent-of-code-2019.git / blobdiff