From: Brett Parker <iDunno@sommitrealweird.co.uk>
Date: Tue, 8 Dec 2020 00:44:37 +0000 (+0000)
Subject: Unfinished day 10 2019, commiting because the code is mostly good
X-Git-Url: https://git.sommitrealweird.co.uk/advent-of-code-2019.git/commitdiff_plain/d6df687f21c08b115abd1eb34c43ab4a3c790b9e?ds=inline

Unfinished day 10 2019, commiting because the code is mostly good
---

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 @@
+.#..#
+.....
+#####
+....#
+...##