set -e
basedir=$(dirname $(readlink -f ${BASH_SOURCE}))
+
filename=${1:-$basedir/3_4_8.txt}
exec 3<$filename
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
+ echo "$line" >&2
}
get_vector() {
local vector1=$1
local vector2=$2
- debug_line Comparing: $vector1 $vector2
+ $debug_line Comparing: $vector1 $vector2
vector1_x=${vector1%,*}
vector1_y=${vector1#*,}
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
+ 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"
+ $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
+ 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"
+ $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"
+ $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 "Collision!"
+ $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#*,}
+
+ hitblocker=0
+
+ max_x=$width
+ max_y=$ln
+
+ # first, head left of the asteroid
+ for (( x=$((start_x-1)); x>=0; x-- )); do
+ do_blocker_check $asteroid $x $start_y
+ done
+ hitblocker=0 # this gets updated in do_blocker_check, reset it
+
+ # now head right of the asteroid
+ for (( x=$(($start_x+1)); x<= $width; x++ )); do
+ do_blocker_check $asteroid $x $start_y
+ done
+ hitblocker=0 # this gets updated in do_blocker_check, reset it
+
+ # head upwards
+ for (( y=$((start_y-1)); y>=0; y-- )); do
+ do_blocker_check $asteroid $start_x $y
+ done
+ hitblocker=0 # this gets updated in do_blocker_check, reset it
+
+ # head down
+ for (( y=$((start_y+1)); y<=$ln; y++ )); do
+ do_blocker_check $asteroid $start_x $y
+ done
+}
+
+do_blocker_check() {
+ asteroid=$1
+ x=$2
+ y=$3
+
+ if [ ${asteroids[$x,$y]+a} ]; then
+ if [ $hitblocker -eq 0 ]; then
+ cansee[$asteroid,$x,$y]=1
+ cansee[$x,$y,$asteroid]=1
+ hitblocker=1
+ else
+ cantsee[$asteroid,$x,$y]=1
+ cantsee[$x,$y,$asteroid]=1
+ fi
+ fi
+}
+
+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 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"
+ 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
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"
+
printf '\r%02d%% complete' $percent
for asteroid2 in ${asteroid_loop[@]}; do
if [ $asteroid2 == $asteroid ]; then
continue
fi
- if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards
+ 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#*,}
- debug_line "Checking for collision between $asteroid and $asteroid2 by $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"
+ $debug_line "We hit $asteroid3 when looking for $asteroid2 from $asteroid"
cantsee[$asteroid2,$asteroid]=1
cantsee[$asteroid,$asteroid2]=1
continue 2
done
fi
# nothing blocked the view of asteroid2 from asteroid1
- debug_line "Apparently $asteroid can set $asteroid2"
+ $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
best_count=$count
best_ast=$asteroid
fi
- debug_line "$asteroid: ${asteroids[$asteroid]}"
+ $debug_line "$asteroid: ${asteroids[$asteroid]}"
done
echo "Best asteroid: $best_ast which can see $best_count asteroids"
projects / advent-of-code-2019.git / commitdiff