2015/advent18.sh

   1 iters=${1-100}
   2 declare -A grid next # use namerefs and function to toggle between them
   3 i=0
   4 while read line; do
   5     j=0
   6     while read cell; do
   7         if [[ $cell == '#' ]]; then
   8             grid[$i.$j]=1
   9         else
  10             grid[$i.$j]=0
  11         fi
  12         : $((j++))
  13     done < <(printf $line | sed 's/\(.\)/\1\n/g')
  14     : $((i++))
  15 done
  16 w=$j h=$i
  17 # count [name] # set $count to the number of cells turned on in ${grid[*]}
  18 count() {
  19     declare -n g=${1-grid}
  20     local i=0 j
  21     count=0
  22     while [[ $i -lt $h ]]; do
  23         j=0
  24         while [[ $j -lt $w ]]; do
  25             count=$((count + g[$i.$j]))
  26             : $((j++))
  27         done
  28         : $((i++))
  29     done
  30 }
  31 if [[ ! $part1 ]]; then
  32     grid[0.0]=1
  33     grid[0.$((w-1))]=1
  34     grid[$((h-1)).0]=1
  35     grid[$((h-1)).$((w-1))]=1
  36 fi
  37 count
  38 echo "initial $w*$h grid contains ${#grid[*]} cells, $count on"
  39 # generate old new # compute the next generation in new reading from old
  40 generate() {
  41     declare -n old=$1 new=$2
  42     local i=0 j neighbors
  43     while [[ $i -lt $h ]]; do
  44         j=0
  45         while [[ $j -lt $w ]]; do
  46             neighbors=$((old[$((i-1)).$((j-1))] +
  47                          old[$((i-1)).$((j  ))] +
  48                          old[$((i-1)).$((j+1))] +
  49                          old[$((i  )).$((j-1))] +
  50                          old[$((i  )).$((j+1))] +
  51                          old[$((i+1)).$((j-1))] +
  52                          old[$((i+1)).$((j  ))] +
  53                          old[$((i+1)).$((j+1))]))
  54             new[$i.$j]=$((neighbors == 3 || (neighbors == 2 && old[$i.$j])))
  55             # echo "cell $i.$j has $neighbors on, new state ${new[$i.$j]}"
  56             : $((j++))
  57         done
  58         : $((i++))
  59     done
  60     if [[ ! $part1 ]]; then
  61         new[0.0]=1
  62         new[0.$((w-1))]=1
  63         new[$((h-1)).0]=1
  64         new[$((h-1)).$((w-1))]=1
  65     fi
  66 }
  67 iter=0
  68 while [[ $iter -lt $iters ]]; do
  69     echo "computing generation $iter"
  70     if ((iter%2)); then # odd iteration
  71         generate next grid
  72     else # even iteration
  73         generate grid next
  74     fi
  75     : $((iter++))
  76 done
  77 if ((iter%2)); then
  78     count next
  79 else
  80     count grid
  81 fi
  82 echo "final grid has $count cells on"