From: Brett Parker Date: Tue, 8 Dec 2020 21:12:21 +0000 (+0000) Subject: More optimisation for day10 X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2019.git/commitdiff_plain/208278a116710606095215db716ec2e1c99855cb?ds=inline;hp=667694b94a6758e3ce751c565309ae980e76a931 More optimisation for day10 --- diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh index 8faf834..bf54544 100755 --- a/day10/check_asteroids.sh +++ b/day10/check_asteroids.sh @@ -115,50 +115,61 @@ fast_checks() { 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 + # 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 - 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 +do_blocker_check() { + startx=$1 + starty=$2 + stepx=$3 + stepy=$4 - # 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 + hitblocker=0 - # head down - for (( y=$((start_y+1)); y<=$ln; y++ )); do - do_blocker_check $asteroid $start_x $y - done -} + if [ $stepx -eq 0 -a $stepy -eq 0 ]; then + echo "Somehow got 0 and 0 as steps" + return + fi -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 + 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 - fi + x=$((x+$stepx)) + y=$((y+$stepy)) + done } possibly_in_way() {