Day 11

[advent-of-code-2021.git] / day11 / dumbo.sh

diff --git a/day11/dumbo.sh b/day11/dumbo.sh
new file mode 100755 (executable)
index 0000000..1bf6cbe
--- /dev/null
+++ b/day11/dumbo.sh
@@ -0,0 +1,163 @@
+#!/bin/bash
+
+set -u
+
+declare -a octopusses
+declare -A flashed=()
+declare -a to_flash=()
+
+filename="${1:-small.txt}"
+iterations="${2:-2}"
+step_display="${3:-1}"
+
+exec 3<"$filename"
+
+width=0
+height=0
+
+while read -u 3 line; do
+    width=${#line}
+    for (( a=0; a<$width; a++ )); do
+        octopusses+=(${line:$a:1})
+    done
+    ((height+=1))
+done
+
+get_offset() {
+    local x=$1
+    local y=$2
+
+    echo $((($y*$width)+$x))
+}
+
+flash_offset() {
+    local offset=$1
+    local x=$((offset%$width))
+    local y=$((offset/$width))
+
+    flash $x $y
+}
+
+flash() {
+    local x=$1
+    local y=$2
+
+    local offset=$(get_offset $x $y)
+
+    if [ "${flashed[$offset]+abc}" ]; then
+        return 0
+    fi
+    flashed[$offset]=1
+
+    for (( offsety=-1; offsety<=1; offsety++ )); do
+        for (( offsetx=-1; offsetx<=1; offsetx++ )); do
+            new_x=$(($x+$offsetx))
+            new_y=$(($y+$offsety))
+            if [ $new_x -eq $x ] && [ $new_y -eq $y ]; then
+                continue
+            fi
+            if [ $new_x -lt 0 ] || [ $new_x -ge $width ] || [ $new_y -lt 0 ] || [ $new_y -ge $height ]; then
+                continue
+            fi
+            # add one to the octopus
+            local __offset=$(get_offset $new_x $new_y)
+            ((octopusses[$__offset]+=1))
+            if [ ${octopusses[$__offset]} -gt 9 ]; then
+                to_flash+=($__offset)
+            fi
+        done
+    done
+}
+
+display_grid() {
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$height; x++ )); do
+            if [ "${flashed[$(get_offset $x $y)]+abc}" ]; then
+                tput bold
+                echo -n "${octopusses[$(get_offset $x $y)]}"
+                tput sgr0
+            else
+                echo -n "${octopusses[$(get_offset $x $y)]}"
+            fi
+        done
+        echo
+    done
+}
+
+total_flashes=0
+
+echo "Step 0"
+display_grid
+echo
+
+all_flashed=-1
+
+do_loop() {
+    local i=$1
+    to_flash=()
+    # first, add 1 to everything
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$width; x++ )); do
+            offset=$(get_offset $x $y)
+            ((octopusses[$offset]+=1))
+        done
+    done
+    # now go back through, but only play with the flashes
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$width; x++ )); do
+            offset=$(get_offset $x $y)
+            if [ ${octopusses[$offset]} -gt 9 ]; then
+                flash $x $y
+            fi
+        done
+    done
+    # and a quick second spin, just incase
+    for (( y=0; y<$height; y++ )); do
+        for (( x=0; x<$width; x++ )); do
+            offset=$(get_offset $x $y)
+            if [ ${octopusses[$offset]} -gt 9 ]; then
+                to_flash+=($offset)
+            fi
+        done
+    done
+
+    while [ "${#to_flash[@]}" -gt 0 ]; do
+        indexes=("${!to_flash[@]}")
+        index=${indexes[0]}
+        flash_offset ${to_flash[$index]}
+        unset to_flash[$index]
+    done
+
+    for offset in "${!flashed[@]}"; do
+        ((total_flashes+=1))
+        octopusses[$offset]=0
+    done
+
+    if [ $((i % $step_display)) -eq 0 ]; then
+        echo "Step $i"
+        display_grid
+        echo
+    fi
+
+    if [ $(($width*$height)) -eq ${#flashed[@]} ]; then
+        all_flashed=$i
+    fi
+
+    for offset in "${!flashed[@]}"; do
+        unset flashed[$offset]
+    done
+}
+
+for (( i=1; i<=$iterations; i++ )); do
+    do_loop $i
+done
+
+echo "total flashes for $iterations: $total_flashes"
+
+i=$(($iterations))
+while [ $all_flashed -eq -1 ]; do
+    ((i+=1))
+    do_loop $i
+done
+
+echo "All flashed on step $i"