From d6df687f21c08b115abd1eb34c43ab4a3c790b9e Mon Sep 17 00:00:00 2001 From: Brett Parker Date: Tue, 8 Dec 2020 00:44:37 +0000 Subject: [PATCH] Unfinished day 10 2019, commiting because the code is mostly good --- day10/11_13_210.txt | 20 ++++ day10/1_2_35.txt | 10 ++ day10/5_8_33.txt | 10 ++ day10/6_3_41.txt | 10 ++ day10/check_asteroids.sh | 210 +++++++++++++++++++++++++++++++++++++++ day10/input.txt | 36 +++++++ day10/small_grid.txt | 5 + 7 files changed, 301 insertions(+) create mode 100644 day10/11_13_210.txt create mode 100644 day10/1_2_35.txt create mode 100644 day10/5_8_33.txt create mode 100644 day10/6_3_41.txt create mode 100644 day10/check_asteroids.sh create mode 100644 day10/input.txt create mode 100644 day10/small_grid.txt diff --git a/day10/11_13_210.txt b/day10/11_13_210.txt new file mode 100644 index 0000000..33437ba --- /dev/null +++ b/day10/11_13_210.txt @@ -0,0 +1,20 @@ +.#..##.###...####### +##.############..##. +.#.######.########.# +.###.#######.####.#. +#####.##.#.##.###.## +..#####..#.######### +#################### +#.####....###.#.#.## +##.################# +#####.##.###..####.. +..######..##.####### +####.##.####...##..# +.#####..#.######.### +##...#.##########... +#.##########.####### +.####.#.###.###.#.## +....##.##.###..##### +.#.#.###########.### +#.#.#.#####.####.### +###.##.####.##.#..## diff --git a/day10/1_2_35.txt b/day10/1_2_35.txt new file mode 100644 index 0000000..e28e424 --- /dev/null +++ b/day10/1_2_35.txt @@ -0,0 +1,10 @@ +#.#...#.#. +.###....#. +.#....#... +##.#.#.#.# +....#.#.#. +.##..###.# +..#...##.. +..##....## +......#... +.####.###. diff --git a/day10/5_8_33.txt b/day10/5_8_33.txt new file mode 100644 index 0000000..987698f --- /dev/null +++ b/day10/5_8_33.txt @@ -0,0 +1,10 @@ +......#.#. +#..#.#.... +..#######. +.#.#.###.. +.#..#..... +..#....#.# +#..#....#. +.##.#..### +##...#..#. +.#....#### diff --git a/day10/6_3_41.txt b/day10/6_3_41.txt new file mode 100644 index 0000000..af5b6e9 --- /dev/null +++ b/day10/6_3_41.txt @@ -0,0 +1,10 @@ +.#..#..### +####.###.# +....###.#. +..###.##.# +##.##.#.#. +....###..# +..#.#..#.# +#..#.#.### +.##...##.# +.....#.#.. diff --git a/day10/check_asteroids.sh b/day10/check_asteroids.sh new file mode 100644 index 0000000..d333a33 --- /dev/null +++ b/day10/check_asteroids.sh @@ -0,0 +1,210 @@ +#!/bin/bash + +set -u +set -e + +filename=${1:-small_grid.txt} + +exec 3<$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() { + 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 +} + +# 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 + ast1_x=${asteroid%,*} + ast1_y=${asteroid#*,} + + for asteroid2 in ${!asteroids[@]}; do + #for asteroid2 in 4,5; 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 + 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 + done +done + +best_ast= +best_count=0 +for asteroid in ${!asteroids[@]}; do + count=${asteroids[$asteroid]} + if [ $count -gt $best_count ]; then + best_count=$count + best_ast=$asteroid + fi + debug_line "$asteroid: ${asteroids[$asteroid]}" +done + +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 "+" diff --git a/day10/input.txt b/day10/input.txt new file mode 100644 index 0000000..2f558ea --- /dev/null +++ b/day10/input.txt @@ -0,0 +1,36 @@ +#.....#...#.........###.#........#.. +....#......###..#.#.###....#......## +......#..###.......#.#.#.#..#....... +......#......#.#....#.##....##.#.#.# +...###.#.#.......#..#............... +....##...#..#....##....#...#.#...... +..##...#.###.....##....#.#..##.##... +..##....#.#......#.#...#.#...#.#.... +.#.##..##......##..#...#.....##...## +.......##.....#.....##..#..#..#..... +..#..#...#......#..##...#.#...#...## +......##.##.#.#.###....#.#..#......# +#..#.#...#.....#...#...####.#..#...# +...##...##.#..#.....####.#....##.... +.#....###.#...#....#..#......#...... +.##.#.#...#....##......#.....##...## +.....#....###...#.....#....#........ +...#...#....##..#.#......#.#.#...... +.#..###............#.#..#...####.##. +.#.###..#.....#......#..###....##..# +#......#.#.#.#.#.#...#.#.#....##.... +.#.....#.....#...##.#......#.#...#.. +...##..###.........##.........#..... +..#.#..#.#...#.....#.....#...###.#.. +.#..........#.......#....#.......... +...##..#..#...#..#...#......####.... +.#..#...##.##..##..###......#....... +.##.....#.......#..#...#..#.......#. +#.#.#..#..##..#..............#....## +..#....##......##.....#...#...##.... +.##..##..#.#..#.................#### +##.......#..#.#..##..#...#.......... +#..##...#.##.#.#.........#..#..#.... +.....#...#...#.#......#....#........ +....#......###.#..#......##.....#..# +#..#...##.........#.....##.....#.... diff --git a/day10/small_grid.txt b/day10/small_grid.txt new file mode 100644 index 0000000..737ae7f --- /dev/null +++ b/day10/small_grid.txt @@ -0,0 +1,5 @@ +.#..# +..... +##### +....# +...## -- 2.39.5