day09/smoke_basin.sh

   1 #!/bin/bash
   2
   3 set -u
   4
   5 filename="${1:-example.txt}"
   6
   7 exec 3<"$filename"
   8
   9 width=0
  10 height=0
  11 declare -a map
  12
  13 while read -u 3 row; do
  14     for (( a=0; a<${#row}; a++ )); do
  15         map+=("${row:$a:1}")
  16     done
  17     ((height+=1))
  18     ((width=${#row}))
  19 done
  20
  21 display_map() {
  22     for (( a=0; a<$height; a++ )); do
  23         for (( b=0; b<$width; b++ )); do
  24             offset=$((($a*$width)+$b))
  25             if [ ${low_spots[$offset]+abc} ]; then
  26                 tput bold
  27             fi
  28             echo -n "${map[$offset]}"
  29             if [ ${low_spots[$offset]+abc} ]; then
  30                 tput sgr0
  31             fi
  32         done
  33         echo
  34     done
  35 }
  36
  37 declare -A low_spots
  38
  39 get_low_spots() {
  40     # we entirely cheat, and just store the index positions
  41     # in the array low_spots
  42     low_spots=()
  43
  44     for (( y=0; y<$height; y++ )); do
  45         for (( x=0; x<$width; x++ )); do
  46             offset=$((($y*width)+$x))
  47             is_lowest=$(check_adjacents $offset)
  48             if [ $is_lowest -eq 0 ]; then
  49                 low_spots[$offset]=$((${map[$offset]}+1))
  50             fi
  51         done
  52     done
  53 }
  54
  55 declare -a basins
  56
  57 check_adjacents() {
  58     local offset=$1
  59     # we'll get y by dividing offset by width
  60     local y=$((offset/$width))
  61     # and x by taking the remainder of that
  62     local x=$((offset%width))
  63     local lower_count=0
  64
  65     if [ $y -gt 0 ]; then
  66         # check spot above us
  67         above_offset=$(((($y-1)*$width)+$x))
  68         if [ ${map[$above_offset]} -le ${map[$offset]} ]; then
  69             ((lower_count+=1))
  70         fi
  71     fi
  72     if [ $y -lt $((height - 1)) ]; then
  73         # check spot below us
  74         below_offset=$(((($y+1)*$width)+$x))
  75         if [ ${map[$below_offset]} -le ${map[$offset]} ]; then
  76             ((lower_count+=1))
  77         fi
  78     fi
  79     if [ $x -gt 0 ]; then
  80         # check to our left
  81         left_offset=$((offset-1))
  82         if [ ${map[$left_offset]} -le ${map[$offset]} ]; then
  83             ((lower_count+=1))
  84         fi
  85     fi
  86     if [ $x -lt $((width - 1)) ]; then
  87         # check to our right
  88         right_offset=$((offset+1))
  89         if [ ${map[$right_offset]} -le ${map[$offset]} ]; then
  90             ((lower_count+=1))
  91         fi
  92     fi
  93
  94     echo "$lower_count"
  95 }
  96
  97 get_surrounding() {
  98     local offset=$1
  99     local -n __been_checked="$2"
 100     local -n __to_check="$3"
 101     local x=$((offset % $width))
 102     local y=$((offset / $width))
 103
 104     __offset=$((($y*$width)+$x))
 105
 106     if [ $x -gt 0 ]; then
 107         check_offset=$((($y*$width)+($x-1)))
 108         if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
 109             __to_check[$check_offset]=1
 110         fi
 111     fi
 112     if [ $y -gt 0 ]; then
 113         check_offset=$(((($y-1)*$width)+$x))
 114         if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
 115             __to_check[$check_offset]=1
 116         fi
 117     fi
 118     if [ $x -lt $(($width-1)) ]; then
 119         check_offset=$((($y*$width)+$x+1))
 120         if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
 121             __to_check[$check_offset]=1
 122         fi
 123     fi
 124     if [ $y -lt $(($height-1)) ]; then
 125         check_offset=$(((($y+1)*$width)+$x))
 126         if [ ! ${__been_checked[$check_offset]+abc} ] && [ ${map[$check_offset]} -ne 9 ]; then
 127             __to_check[$check_offset]=1
 128         fi
 129     fi
 130     __been_checked[$__offset]=1
 131     unset __to_check[$__offset]
 132 }
 133
 134 find_basins() {
 135     # we find the basin by using the low_spots.
 136     for basin_mid in "${!low_spots[@]}"; do
 137         basin_x=$(($basin_mid % $width))
 138         basin_y=$(($basin_mid / $width))
 139         declare -A checked
 140         declare -A to_check
 141
 142         # add surrounding blocks to the to_check list
 143         to_check[$basin_mid]=1
 144         while [ ${#to_check[@]} -gt 0 ]; do
 145             for offset in "${!to_check[@]}"; do
 146                 get_surrounding $offset checked to_check
 147             done
 148         done
 149         # this *should* have avoided all 9s and got anything else in the area that we wanted, so the checked array
 150         # at this point should contain the number of elements we care about
 151         basins+=("${#checked[@]}")
 152         checked=()
 153     done
 154 }
 155
 156 sum_risk() {
 157     sum=0
 158     for lowpoint in "${low_spots[@]}"; do
 159         ((sum+=$lowpoint))
 160     done
 161     echo "$sum"
 162 }
 163
 164 get_low_spots
 165 display_map
 166
 167 echo
 168 echo "The risk is: $(sum_risk)"
 169 find_basins
 170
 171 OLDIFS="$IFS"
 172 IFS=$'\n'
 173 sorted=($(sort -n <<<"${basins[*]}" | tail -n 3))
 174
 175 echo "The largest 3 basin sizes are: ${sorted[@]}"
 176 echo "Multiplied together they are: $((${sorted[0]} * ${sorted[1]} * ${sorted[2]}))"