set -u
set -e
-filename=${1:-small_grid.txt}
+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 echo "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#*,}
+
+ 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 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
# 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
-for asteroid in ${!asteroids[@]}; do
-#for asteroid in 9,0; do
+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)))
- for asteroid2 in ${!asteroids[@]}; do
- #for asteroid2 in 4,5; do
+ $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
continue
fi
- if ! [ ${cansee[$asteroid,$asteroid2]+a} ]; then # we already calculated this backwards
- for asteroid3 in ${!asteroids[@]}; do
+ 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"
- asteroids[$asteroid]=$((asteroids[$asteroid]+1))
+ $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
done
+ unset asteroid_loop[$index]
+ index=$((index+1))
done
+echo -n $'\r'" "$'\r'
best_ast=
best_count=0
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 / blobdiff