CGAC2022 Day 14: Chimney cleaning

Question

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.

---

As we all know, Santa comes down the chimney to deliver presents to good kids. But chimneys are normally full of smoke, and the Elves are worried about Santa's health. So they decide to blow the smoke out using an electronic air blower.

A chimney is modeled as a rectangular grid. The number in each cell represents the amount of smoke in the region. The left and right sides are walls, the top is open, and the air blower is blowing wind from the bottom.

||========||
||  |99|  ||
||--+--+--||
||  |  |24||
||--+--+--||
||36|  |12||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |50|  ||
||^^^^^^^^||

Every second, the following happens in order. At any step, the smoke that goes outside of the chimney through the top is excluded from simulation.

1. The smoke is blown up one cell upwards.
2. The smoke diffuses to adjacent (4-way) cells (including outside).
   • Let's say a cell contains n amount of smoke. Then, for each available direction, exactly floor(n/5) amount of smoke moves in that direction.

Given the initial state above, smoke will move and diffuse as follows:

After step 1:
||========||
||  |  |24||
||--+--+--||
||36|  |12||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |50|  ||
||--+--+--||
||  |  |  ||
||^^^^^^^^||

After step 2: (1 second passed)
||========||
||7 |4 |14||
||--+--+--||
||15|9 |10||
||--+--+--||
||7 |10|2 ||
||--+--+--||
||10|10|10||
||--+--+--||
||  |10|  ||
||^^^^^^^^||

2 seconds passed:
||========||
||8 |12|5 ||
||--+--+--||
||11|6 |8 ||
||--+--+--||
||7 |10|6 ||
||--+--+--||
||4 |4 |4 ||
||--+--+--||
||  |2 |  ||
||^^^^^^^^||

5 seconds passed:
||========||
||5 |1 |5 ||
||--+--+--||
||1 |4 |1 ||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |  |  ||
||--+--+--||
||  |  |  ||
||^^^^^^^^||

This chimney is completely clear of smoke after 7 seconds.

Task

Given a 2D grid of non-negative integers which represents the current state of smoke in the chimney, simulate the chimney as specified above and output the state 1 second later. You may assume that the chimney is at least 2 units wide and 2 units tall.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[[0, 99, 0], [0, 0, 24], [36, 0, 12], [0, 0, 0], [0, 50, 0]]
-> [[7, 4, 14], [15, 9, 10], [7, 10, 2], [10, 10, 10], [0, 10, 0]]
-> [[8, 12, 5], [11, 6, 8], [7, 10, 6], [4, 4, 4], [0, 2, 0]]
-> [[7, 7, 7], [8, 5, 6], [5, 6, 5], [0, 2, 0], [0, 0, 0]]
-> [[7, 4, 5], [4, 5, 4], [1, 3, 1], [0, 0, 0], [0, 0, 0]]
-> [[5, 1, 5], [1, 4, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
-> [[1, 4, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
-> [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]

Answer 1

J, ^{71 61} 58 bytes

0(1}.$$,+[:(+/-1&#.)5<.@%~,*1=[:|@-/~$j./@#:i.@#@,)@,0,~}.

Try it online!

Answer 2

Python3, 301 bytes:

E=enumerate
def f(b):
 while any(map(any,b)):
  T=[]
  for x,r in E(b):
   for y,c in E(r):
    b[x][y]=0;p=x-1
    if x:
     b[p][y]=c
     for X,Y in(0,1),(-1,0),(1,0),(0,-1):
      K=0<=y+Y<len(b[0]);b[p][y]-=c//5*K
      if-1<p+X<len(b):T+=K*[(p+X,y+Y,c//5)]
  for x,y,v in T:b[x][y]+=v
  yield b

Try it online!

Answer 3

JavaScript (Node.js), 108 bytes

a=>a.map((r,y)=>r.map((c,x)=>(g=c=>p+2&&c/5*(p-y<3)+c%5*!p--+g((R=a[y-~(p>1)])?R[x+p%2]??R[x]:0)|0)(c,p=3)))

Attempt This Online!

For cell (x, y), the value after function is:

sum(
  floor(a[x,y]/5) only if (y is not 0),
  floor(a[x,y+1]/5),
  floor(a[x-1,y+1]/5),
  floor(a[x+1,y+1]/5),
  floor(a[x,y+2]/5),
  a[x,y+1] mod 5,
  floor(a[x,y+1]/5) only if (x is one of edge),
)

Answer 4

Pip, 125 129 bytes

@<($+(({(FL1ZGc*l)RA_bMS[a-1;a+1;a+c<c*l&a+c|a;a-c>=0&a-c|a]}MU{[a;b//5;h:#\a+1]}ME(k:WV(@>aAL2ZG(l:#@a))))AE(_-4*(_//5)Mk))UWh)

Try It Online!

I feel like there should be a much neater and golfier way of doing this in pip, but I couldn't figure it out

Edit: forgot to delete the temporary last row

Answer 5

JavaScript (ES2020), 129 bytes

m=>[...m,m[0].fill(0)].map((r,y,m)=>r.map((v,x)=>[-1,s=0,1,2].map(d=>s-=1/(V=m[y+d%2]?.[x+~-d%2])?~(V/5)-~(v/5):0)|v+s)).slice(1)

Attempt This Online!

Answer 6

Charcoal, 46 42 bytes

ＩΦＥ⊞ＯθＥ⌊θ⁰Ｅι⁺λΣＥθΣＥν∧⁼¹⁺↔⁻κξ↔⁻μρ⁻÷∧ξπ⁵÷λ⁵κ

Try it online! Link is to verbose version of code. Explanation:

        θ                                   Input array
       ⌊                                    Minimum (any) row
      Ｅ                                     Map over cells
         ⁰                                  Zero
   ⊞Ｏ                                       Push to
     θ                                      Input array
  Ｅ                                         Map over rows
           ι                                Current row
          Ｅ                                 Map over cells
             λ                              Current value
            ⁺                               Plus
                θ                           Input array
               Ｅ                            Map over rows
                   ν                        Inner row
                  Ｅ                         Map over cells
                      ¹                     Literal integer `1`
                     ⁼                      Equals
                          κ                 Outer row index
                         ⁻                  Minus
                           ξ                Inner row index
                        ↔                   Absolute value
                       ⁺                    Plus
                              μ             Outer cell index
                             ⁻              Minus
                               ρ            Inner cell index
                            ↔               Absolute value
                    ∧                       Logical And
                                   ξ        Inner row index
                                  ∧         Logical And
                                    π       Inner cell value
                                 ÷          Integer divided by
                                     ⁵      Literal integer `5`
                                ⁻           Minus
                                       λ    Outer cell value
                                      ÷     Integer divided by
                                        ⁵   Literal integer `5`
                 Σ                          Take the sum
              Σ                             Take the sum
 Φ                                          Filtered where
                                         κ  Row index is not zero
Ｉ                                           Cast to string
                                            Implicitly print

For instance, in the example of [[[0, 99, 0], [0, 0, 24], [36, 0, 12], [0, 0, 0], [0, 50, 0]]], when the outer loop is processing the 24 and the inner loop is processing the 12, the cells are found to be adjacent, so 12/5=2 is diffused into the outer cell but 24/5=4 is diffused out, while when the inner loop is processing the two zero cells also adjacent to the 24 there is nothing to diffuse in while 4 still diffuses out each time. This results in a net total of 24+2-4+0-4+0-4=14 in that cell.

Answer 7

Python3 + scipy, 173 bytes (broken)

To be clearest, this solution doesn't exactly work, but its so close to working and uses a different method than the other answers now for potentially a big byte savings, so I decided to post it to see if someone can get inspired to get it over the line.

from scipy.signal import convolve2d as c
import numpy as n
g=lambda i:c(n.vstack([[0,0,0],i[1:],[0,0,0]]),[[0,1/5,0],[1/5,1/5,1/5],[0,1/5,0]],'same','symm')[1:].astype(int)

Run online at onecompiler.com

Output

Given the first test case:

[[ 0 99  0]
 [ 0  0 24]
 [36  0 12]
 [ 0  0  0]
 [ 0 50  0]]

This outputs:

[[ 7  4 12]
 [14  9  9]
 [ 7 10  2]
 [10 10 10]
[ 0 10  0]]

Instead of the expected:

[[ 7  4 14]
 [15  9 10]
 [ 7 10  2]
 [10 10 10]
 [ 0 10  0]]

Explained

import scipy
import scipy.signal
import numpy as np
# We can solve this with matrix convolutions and row shifts in fewer operations (and hopefully less bytes)
# than iteration.
def g_ungolfed(i):
    # 1. pad arrays with 0-rows on both y-sides
    ## Slicing the first row off lets smoke 'escape' out of the top during the initial shift
    ## Padding the first row with a temp row lets smoke 'escape' out the top during dispersion.
    ## Padding the last row lets us shift the smoke up 1 row later on
    i_padded = np.vstack([[0,0,0],i[1:], [0,0,0]])
    print("padded", i_padded)
    # 2. Run the convolution to do the smoke pattern
    ## define a convolution kernel to follow the 20% smoke dispersal pattern --
    k = [
        [0,1/5,0],
        [1/5,1/5,1/5],
        [0,1/5,0],
    ]
    ## mode="same" keeps the output matrix in the same dimensions as the i_padded input
    ## boundary="symm" handles the correct behavior for the smoke-fill pattern on the left-right boundaries of the chimney
    # The floor(n/5) integer division isn't respected here which is why the results are wrong.
    dispersed = scipy.signal.convolve2d(i_padded, k, mode="same", boundary="symm")
    # 3. Slice off the temp top row
    print("intermediate", dispersed)
    dispersed_shifted = dispersed[1:]
    # 4. cast the results to int
    return dispersed_shifted.astype(int)

Answer 8

Python 3, 149 bytes

lambda m:[o:=[[0]*len(m.pop(0))],[[n[1]%5+sum(i//5for i in n)for n in zip(x,y,y[1:]+[y[-1]],[y[0]]+y[:-1],z)]for x,y,z in zip(o+m,m+o,m[1:]+o+o)]][1]

Try it online!