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
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 -a $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 -a $((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 -a $cur_y -eq $vector1_y ]; then
- $debug_line "Collision!"
- return 0
- fi
- done
-
- return 1
-}
-
-fast_checks() {
- asteroid=$1
- start_x=${asteroid%,*}
- start_y=${asteroid#*,}
-
- max_x=$width
- max_y=$ln
-
- # directions:
- # -1, 0 - left
- # 1, 0 - right
- # 0, 1 - up
- # 0,-1 - down
- # -1, 1 - diagonal left down
- # -1,-1 - diagonal left up
- # 1, 1 - diagonal right down
- # 1,-1 - diagonal right up
- for direction in -1,0 1,0 0,1 0,-1 -1,1 -1,-1 1,1 1,-1; do
- #for direction in "-1,0" "1,0" "0,1" "0,-1"; do
- stepx=${direction%,*}
- stepy=${direction#*,}
- do_blocker_check $start_x $start_y $stepx $stepy
- done
-}
-
-do_blocker_check() {
- startx=$1
- starty=$2
- stepx=$3
- stepy=$4
-
- hitblocker=0
-
- if [ $stepx -eq 0 -a $stepy -eq 0 ]; then
- echo "Somehow got 0 and 0 as steps"
- return
- fi
-
- local x=$startx
- local y=$starty
-
- # add the steps before we start the loop to not be
- # on ourselves
- x=$((x+$stepx))
- y=$((y+$stepy))
-
- while [ $x -le $width -a $x -ge 0 -a $y -le $ln -a $y -ge 0 ]; do
- if [ ${asteroids[$x,$y]+a} ]; then
- if [ $hitblocker -eq 0 ]; then
- cansee[$asteroid,$x,$y]=1
- cansee[$x,$y,$startx,$starty]=1
- hitblocker=1
- else
- cantsee[$startx,$starty,$x,$y]=1
- cantsee[$x,$y,$startx,$starty]=1
- fi
- fi
- x=$((x+$stepx))
- y=$((y+$stepy))
- done
-}
-
-possibly_in_way() {
- source_x=$1
- source_y=$2
- sink_x=$3
- sink_y=$4
- blocker_x=$5
- blocker_y=$6
-
- # first check the horizontal and vertical planes
- 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 ) ]] ||
- [[ ( $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
- return 0
- fi
-
- # if our source asteroid is further to the right thank our sink, then to stand half a chance
- # of being in the way, the blocker has to be x > $sink_x and x < source_x
- # apply the same rule for y
- # reverse the direction and do the same checks.
- # So if source_x < sink_x then blocker_x has to be < sink_x > source_x
- if [ $source_x -gt $sink_x -a $blocker_x -gt $sink_x -a $blocker_x -lt $source_x ] ||
- [ $source_y -gt $sink_y -a $blocker_y -gt $sink_y -a $blocker_y -lt $source_y ] ||
- [ $source_x -lt $sink_x -a $blocker_x -lt $sink_x -a $blocker_x -gt $source_x ] ||
- [ $source_y -lt $sink_y -a $blocker_y -lt $sink_y -a $blocker_y -gt $source_y ]; then
- return 0
- fi
-
- 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 -a $cur_x -lt $ast_x ] ||
- [ $minstep_y -lt 0 -a $cur_y -lt $ast_y ] ||
- [ $minstep_x -gt 0 -a $cur_x -gt $ast_x ] ||
- [ $minstep_y -gt 0 -a $cur_y -gt $ast_y ]; then
- $debug_line "keepgoing finished"
- return 1
- fi
-
- return 0
-}
-
-# 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
-asteroid_loop=("${!asteroids[@]}")
-index=0
-start_count=${#asteroids[@]}
-for asteroid in ${asteroid_loop[@]}; do
- ast1_x=${asteroid%,*}
- ast1_y=${asteroid#*,}
- cur_count=${#asteroid_loop[@]}
- percent=$((100-(100*$cur_count / $start_count)))
-
- $debug_line "Doing fast checks"
- fast_checks $asteroid
- $debug_line "Running main loops"
-
+# 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
+ percent=$((100*$cur_ast_num / $total_asts))
printf '\r%02d%% complete' $percent
- for asteroid2 in ${asteroid_loop[@]}; do
- if [ $asteroid2 == $asteroid ]; 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
+ # get a full list of angles for each other asteroid
+ declare -A asteroid_angles
+ for asteroid2 in ${!asteroids[@]}; do
+ if [ $asteroid == $asteroid2 ]; then
continue
fi
- if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this
- for asteroid3 in "${!asteroids[@]}"; do
- if [ $asteroid == $asteroid3 ] || [ $asteroid2 == $asteroid3 ]; then
- continue
- fi
- ast3_x=${asteroid3%,*}
- ast3_y=${asteroid3#*,}
-
- # if this asteroid can't be in the way, continue the loop
- if ! possibly_in_way $ast1_x $ast1_y $ast2_x $ast2_y $ast3_x $ast3_y; then
- $debug_line "Apparently $ast1_x $ast1_y to $ast2_x $ast2_y cannot be blocked by $ast3_x $ast3_y"
- continue
- fi
-
- $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 see $asteroid2"
- asteroids[$asteroid]=$((${asteroids[$asteroid]}+1))
- asteroids[$asteroid2]=$((${asteroids[$asteroid2]}+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
- unset asteroid_loop[$index]
- index=$((index+1))
-done
-echo -n $'\r'" "$'\r'
-
-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