day11/dumbo.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 declare -a octopusses
   6 declare -A flashed=()
   7 declare -a to_flash=()
   8
   9 filename="${1:-small.txt}"
  10 iterations="${2:-2}"
  11 step_display="${3:-1}"
  12
  13 exec 3<"$filename"
  14
  15 width=0
  16 height=0
  17
  18 while read -u 3 line; do
  19     width=${#line}
  20     for (( a=0; a<$width; a++ )); do
  21         octopusses+=(${line:$a:1})
  22     done
  23     ((height+=1))
  24 done
  25
  26 get_offset() {
  27     local x=$1
  28     local y=$2
  29
  30     echo $((($y*$width)+$x))
  31 }
  32
  33 flash_offset() {
  34     local offset=$1
  35     local x=$((offset%$width))
  36     local y=$((offset/$width))
  37
  38     flash $x $y
  39 }
  40
  41 flash() {
  42     local x=$1
  43     local y=$2
  44
  45     local offset=$(get_offset $x $y)
  46
  47     if [ "${flashed[$offset]+abc}" ]; then
  48         return 0
  49     fi
  50     flashed[$offset]=1
  51
  52     for (( offsety=-1; offsety<=1; offsety++ )); do
  53         for (( offsetx=-1; offsetx<=1; offsetx++ )); do
  54             new_x=$(($x+$offsetx))
  55             new_y=$(($y+$offsety))
  56             if [ $new_x -eq $x ] && [ $new_y -eq $y ]; then
  57                 continue
  58             fi
  59             if [ $new_x -lt 0 ] || [ $new_x -ge $width ] || [ $new_y -lt 0 ] || [ $new_y -ge $height ]; then
  60                 continue
  61             fi
  62             # add one to the octopus
  63             local __offset=$(get_offset $new_x $new_y)
  64             ((octopusses[$__offset]+=1))
  65             if [ ${octopusses[$__offset]} -gt 9 ]; then
  66                 to_flash+=($__offset)
  67             fi
  68         done
  69     done
  70 }
  71
  72 display_grid() {
  73     for (( y=0; y<$height; y++ )); do
  74         for (( x=0; x<$height; x++ )); do
  75             if [ "${flashed[$(get_offset $x $y)]+abc}" ]; then
  76                 tput bold
  77                 echo -n "${octopusses[$(get_offset $x $y)]}"
  78                 tput sgr0
  79             else
  80                 echo -n "${octopusses[$(get_offset $x $y)]}"
  81             fi
  82         done
  83         echo
  84     done
  85 }
  86
  87 total_flashes=0
  88
  89 echo "Step 0"
  90 display_grid
  91 echo
  92
  93 all_flashed=-1
  94
  95 do_loop() {
  96     local i=$1
  97     to_flash=()
  98     # first, add 1 to everything
  99     for (( y=0; y<$height; y++ )); do
 100         for (( x=0; x<$width; x++ )); do
 101             offset=$(get_offset $x $y)
 102             ((octopusses[$offset]+=1))
 103         done
 104     done
 105     # now go back through, but only play with the flashes
 106     for (( y=0; y<$height; y++ )); do
 107         for (( x=0; x<$width; x++ )); do
 108             offset=$(get_offset $x $y)
 109             if [ ${octopusses[$offset]} -gt 9 ]; then
 110                 flash $x $y
 111             fi
 112         done
 113     done
 114     # and a quick second spin, just incase
 115     for (( y=0; y<$height; y++ )); do
 116         for (( x=0; x<$width; x++ )); do
 117             offset=$(get_offset $x $y)
 118             if [ ${octopusses[$offset]} -gt 9 ]; then
 119                 to_flash+=($offset)
 120             fi
 121         done
 122     done
 123
 124     while [ "${#to_flash[@]}" -gt 0 ]; do
 125         indexes=("${!to_flash[@]}")
 126         index=${indexes[0]}
 127         flash_offset ${to_flash[$index]}
 128         unset to_flash[$index]
 129     done
 130
 131     for offset in "${!flashed[@]}"; do
 132         ((total_flashes+=1))
 133         octopusses[$offset]=0
 134     done
 135
 136     if [ $((i % $step_display)) -eq 0 ]; then
 137         echo "Step $i"
 138         display_grid
 139         echo
 140     fi
 141
 142     if [ $(($width*$height)) -eq ${#flashed[@]} ]; then
 143         all_flashed=$i
 144     fi
 145
 146     for offset in "${!flashed[@]}"; do
 147         unset flashed[$offset]
 148     done
 149 }
 150
 151 for (( i=1; i<=$iterations; i++ )); do
 152     do_loop $i
 153 done
 154
 155 echo "total flashes for $iterations: $total_flashes"
 156
 157 i=$(($iterations))
 158 while [ $all_flashed -eq -1 ]; do
 159     ((i+=1))
 160     do_loop $i
 161 done
 162
 163 echo "All flashed on step $i"