Day 9

[advent-of-code-2021.git] / day09 / smoke_basin.sh

diff --git a/day09/smoke_basin.sh b/day09/smoke_basin.sh
new file mode 100755 (executable)
index 0000000..30af6fc
--- /dev/null
+++ b/day09/smoke_basin.sh
@@ -0,0 +1,176 @@
+#!/bin/bash
+
+set -u
+
+filename="${1:-example.txt}"
+
+exec 3<"$filename"
+
+width=0
+height=0
+declare -a map
+
+while read -u 3 row; do
+    for (( a=0; a<${#row}; a++ )); do
+        map+=("${row:$a:1}")
+    done
+    ((height+=1))
+    ((width=${#row}))
+done
+
+display_map() {
+    for (( a=0; a<$height; a++ )); do
+        for (( b=0; b<$width; b++ )); do
+            offset=$((($a*$width)+$b))
+            if [ ${low_spots[$offset]+abc} ]; then
+                tput bold
+            fi
+            echo -n "${map[$offset]}"
+            if [ ${low_spots[$offset]+abc} ]; then
+                tput sgr0
+            fi
+        done
+        echo
+    done
+}
+
+declare -A low_spots
+
+get_low_spots() {
+    # we entirely cheat, and just store the index positions
+    # in the array low_spots
+    low_spots=()
+
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$width; x++ )); do
+            offset=$((($y*width)+$x))
+            is_lowest=$(check_adjacents $offset)
+            if [ $is_lowest -eq 0 ]; then
+                low_spots[$offset]=$((${map[$offset]}+1))
+            fi
+        done
+    done
+}
+
+declare -a basins
+
+check_adjacents() {
+    local offset=$1
+    # we'll get y by dividing offset by width
+    local y=$((offset/$width))
+    # and x by taking the remainder of that
+    local x=$((offset%width))
+    local lower_count=0
+
+    if [ $y -gt 0 ]; then
+        # check spot above us
+        above_offset=$(((($y-1)*$width)+$x))
+        if [ ${map[$above_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $y -lt $((height - 1)) ]; then
+        # check spot below us
+        below_offset=$(((($y+1)*$width)+$x))
+        if [ ${map[$below_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $x -gt 0 ]; then
+        # check to our left
+        left_offset=$((offset-1))
+        if [ ${map[$left_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+    if [ $x -lt $((width - 1)) ]; then
+        # check to our right
+        right_offset=$((offset+1))
+        if [ ${map[$right_offset]} -le ${map[$offset]} ]; then
+            ((lower_count+=1))
+        fi
+    fi
+
+    echo "$lower_count"
+}
+
+get_surrounding() {
+    local offset=$1
+    local -n __been_checked="$2"
+    local -n __to_check="$3"
+    local x=$((offset % $width))
+    local y=$((offset / $width))
+
+    __offset=$((($y*$width)+$x))
+
+    if [ $x -gt 0 ]; then
+        check_offset=$((($y*$width)+($x-1)))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $y -gt 0 ]; then
+        check_offset=$(((($y-1)*$width)+$x))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $x -lt $(($width-1)) ]; then
+        check_offset=$((($y*$width)+$x+1))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    if [ $y -lt $(($height-1)) ]; then
+        check_offset=$(((($y+1)*$width)+$x))
+        if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
+            __to_check[$check_offset]=1
+        fi
+    fi
+    __been_checked[$__offset]=1
+    unset __to_check[$__offset]
+}
+
+find_basins() {
+    # we find the basin by using the low_spots.
+    for basin_mid in "${!low_spots[@]}"; do
+        basin_x=$(($basin_mid % $width))
+        basin_y=$(($basin_mid / $width))
+        declare -A checked
+        declare -A to_check
+
+        # add surrounding blocks to the to_check list
+        to_check[$basin_mid]=1
+        while [ ${#to_check[@]} -gt 0 ]; do
+            for offset in "${!to_check[@]}"; do
+                get_surrounding $offset checked to_check
+            done
+        done
+        # this *should* have avoided all 9s and got anything else in the area that we wanted, so the checked array
+        # at this point should contain the number of elements we care about
+        basins+=("${#checked[@]}")
+        checked=()
+    done
+}
+
+sum_risk() {
+    sum=0
+    for lowpoint in "${low_spots[@]}"; do
+        ((sum+=$lowpoint))
+    done
+    echo "$sum"
+}
+
+get_low_spots
+display_map
+
+echo
+echo "The risk is: $(sum_risk)"
+find_basins
+
+OLDIFS="$IFS"
+IFS=$'\n'
+sorted=($(sort -n <<<"${basins[*]}" | tail -n 3))
+
+echo "The largest 3 basin sizes are: ${sorted[@]}"
+echo "Multiplied together they are: $((${sorted[0]} * ${sorted[1]} * ${sorted[2]}))"