]> git.sommitrealweird.co.uk Git - advent-of-code-2021.git/blob - day11/dumbo.sh
Day 16 pt 1 - doesn't actually stack packets hierarchically - just parses the headers
[advent-of-code-2021.git] / 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"