40
\$\begingroup\$

Minecraft has a fairly unique lighting system. Each block's light value is either one less than the brightest one surrounding it, or it is a light source itself. Your task is to write a method that takes in a 2D array of light source values, and then returns a 2D array with spread out lighting, where 0 is the minimum value.

Examples

Input1 = [
         [0, 0, 4, 0], 
         [0, 0, 0, 0], 
         [0, 2, 0, 0], 
         [0, 0, 0, 0]
        ]

Output1 = [
         [2, 3, 4, 3], 
         [1, 2, 3, 2], 
         [1, 2, 2, 1], 
         [0, 1, 1, 0]
        ]

Input2 = [
         [2, 0, 0, 3], 
         [0, 0, 0, 0], 
         [0, 0, 0, 0], 
         [0, 0, 0, 0]
        ]

Output2 = [
         [2, 1, 2, 3], 
         [1, 0, 1, 2], 
         [0, 0, 0, 1], 
         [0, 0, 0, 0]
        ]

Notes

You can assume:

  1. Input will not be empty
  2. The y axis will be the same length
  3. All numbers will be integers; no nulls, doubles, or floats
  4. All numbers will be between 0 and 15 (inclusive).

Rules:

  1. Return a 2D array following the above mechanics
  2. No value can be less than 0
  3. If there are two highest neighbors, just subtract one from them
  4. Light sources do not change, unless a surrounding block is brighter than it.
  5. No standard loopholes
  6. This is code golf, so shortest code wins!
\$\endgroup\$
20
  • 1
    \$\begingroup\$ It would be good to have some more test cases \$\endgroup\$
    – Luis Mendo
    Mar 22 at 23:54
  • 1
    \$\begingroup\$ Actually, it looks like maybe "surrounding" does not include diagonals at all? \$\endgroup\$ Mar 22 at 23:55
  • 1
    \$\begingroup\$ My bad, it was in the text \$\endgroup\$
    – Luis Mendo
    Mar 23 at 0:09
  • 2
    \$\begingroup\$ What does 'The y axis will be the same length' mean? \$\endgroup\$
    – Dingus
    Mar 23 at 1:46
  • 1
    \$\begingroup\$ The diagonals of a light source will yes be less. Light source of 2 is very weak, so it only lights directly around it. Diagonals do not count to this. Take a look at this image - bit.ly/37Uui3Y . \$\endgroup\$
    – Chspsa
    Mar 23 at 14:34

13 Answers 13

6
\$\begingroup\$

BQN, 21 bytesSBCS

(⊢⌈¯1+«⌈»⌈«˘⌈»˘)⍟(≠⥊)

Run online!

«⌈»⌈«˘⌈»˘ computes the element-wise maximum of:

  • « Push in 0's from the bottom
  • » Push in 0's from the top
  • «˘ Push in 0's from right
  • »˘ Push in 0's from the left

Then substract 1 from this / add ¯1 (¯1+) and take the maximum with the input matrix ().

≠⥊ gives the number of element in the flattened matrix and (...)⍟ iterates the function on the left that many times.

\$\endgroup\$
4
  • \$\begingroup\$ Can you add an explanation? \$\endgroup\$
    – Jonah
    Mar 23 at 15:41
  • 1
    \$\begingroup\$ @Jonah added something \$\endgroup\$
    – ovs
    Mar 23 at 18:50
  • \$\begingroup\$ so bqn has a builtin for non-cycling rotation (ie, «)... does it also have the normal one with cycling? \$\endgroup\$
    – Jonah
    Mar 23 at 20:32
  • 1
    \$\begingroup\$ @Jonah Yes rotation is the dyadic , just as APL. BQN doesn't have infixes/windowed reduce, so stuff like 2+/\\] <-> 1↓»⊸+ is the main use for the shifts « and ». \$\endgroup\$
    – ovs
    Mar 23 at 21:49
6
\$\begingroup\$

R >=4.1, 377 215 182 150 bytes

f=\(m,w=T,n=1:ncol(m),z=Reduce(pmax,Map(\(j){o=outer(m[p][j]-abs(n-i[j,1]),abs(n-i[j,2]),`-`);o*(o>0)},1:nrow(i<-which(p<-m>1,a=T)))))`if`(w,f(z,F),z)

I sure learned a lot.

Thanks to June Choe for the outer() tip which enabled a significant optimisation, and then some cleanup.

Also thanks to @pajonk for some additional savings, use of Map, and for introducing me to 'attempt this online'

\$\endgroup\$
3
  • \$\begingroup\$ 154 by reducing whitespace, inlining variable assignments, using Map instead of lapply and renaming the main function. \$\endgroup\$
    – pajonk
    Mar 29 at 8:38
  • 1
    \$\begingroup\$ 150 actually \$\endgroup\$
    – pajonk
    Mar 29 at 9:00
  • \$\begingroup\$ Still 150 if I use an alternative outer formulation from here. I wasn't aware of ATO - thanks! \$\endgroup\$ Mar 30 at 11:38
5
\$\begingroup\$

JavaScript (ES6),  99 94  93 bytes

Modifies the input matrix in-place.

m=>{for(d=64;d--;m.map((r,y)=>r.map((v,x)=>r[x]=(q=~-(m[y+D%2]||0)[x+~-D%2])>v?q:v)))D=d%4-1}

Try it online!

Commented

m => {                   // m[] = input matrix
  for(                   // repeat 64 times,
    d = 64;              // using d as a counter:
    d--;                 //
    m.map((r, y) =>      //   for each row r[] at position y in m[]:
      r.map((v, x) =>    //     for each value v at position x in r[]:
        r[x] = (         //       update r[x]:
          q =            //         q is the value of the neighbor cell
          ~-(            //         located at m[y + dy][x + dx],
            m[y + D % 2] //         using D as the current direction
            || 0         //         (-1 = North, 0 = West, 1 = South,
          )[x + ~-D % 2] //         2 = East), minus 1
        ) > v ? q        //         keep the maximum of q and the
              : v        //         current value v
      )                  //     end of inner map()
    )                    //   end of outer map()
  ) D = d % 4 - 1        //   set D to (d mod 4) - 1
}                        // implicit end of for()
\$\endgroup\$
5
\$\begingroup\$

MATL, 24 bytes

Xz,G@+&fh]&1ZP-TYaX>GZye

Try it online! Or verify all test cases.

Explanation

Xz       % Implicit input. Get nonzeros as a column vector (*)
,        % Do twice
  G      %   Push input
  @      %   Push iteration index: 0 or 1
  +      %   Add, element-wise
  &f     %   Two-output find: gives row and column indices of nonzeros
  h      %   Concatenate horizontally. Gives a 2-row matrix where each
         %   row contains the coordinates of nonzeros (first iteration)
         %   or of all entries (second iteration)
]        % End
&1ZP     % Cityblock distance between rows
-        % Subtract from (*), element-wise with broadcast
TYa      % Extend with two rows of zeros. This serves two purposes:
         % making sure that the maximum of each row is at least 0; and
         % making sure that each column has more than 1 entry, so that
         % the following function (maximum) operates along the first
         % dimension (compute maximum of each column)
X>       % Maximum along the first (non-singleton) dimension (**)
GZy      % Push input. Size
e        % Reshape (**) with the specified size. Implicit display
\$\endgroup\$
5
\$\begingroup\$

C(gcc) 230 227 220 172 171 128 97 bytes

smaller thanks to @Muskovets an @engineergaming, and now @ceilingcat

i,j;f(n,x,y)int*n;{for(i=x*y;i--;)for(j=x*y;j--;n[j]=fmax(n[j],n[i]-abs(i%x-j%x)-abs(i/x-j/x)));}

Try it Online!

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! I think you can save a few bytes by removing some spaces in the argument list. \$\endgroup\$ Mar 23 at 17:33
  • \$\begingroup\$ 199 bytes by abusing parameter declarations \$\endgroup\$ Mar 23 at 22:20
  • \$\begingroup\$ 172 bytes by editing @engineergaming's \$\endgroup\$
    – Muskovets
    Mar 24 at 9:43
  • \$\begingroup\$ 104 bytes if you modify the array in place (not sure if that's allowed but a couple answers do that) \$\endgroup\$ Mar 24 at 22:12
  • \$\begingroup\$ 89 bytes if you assume the array is 4x4 (which OP allowed in comments) \$\endgroup\$ Mar 25 at 15:46
4
\$\begingroup\$

JavaScript (Node.js), 100 98 94 bytes

A=Math.abs
f=(a,i,j)=>a.map((r,y)=>r.map((c,x)=>1/i?t=t>(u=c-A(i-y)-A(j-x))?t:u:f(t=a,y,x)|t))

Try it online!

-4 byte from ophact

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I was posting an answer the exact instant you posted this :| \$\endgroup\$ Mar 22 at 23:45
  • 1
    \$\begingroup\$ Use Math.abs for absolute value (assign A directly to the function) to save bytes \$\endgroup\$
    – ophact
    Mar 23 at 6:24
4
\$\begingroup\$

Python 3 with numpy, 93 bytes

f=lambda a,n=0:f(rot90(fmax(a,r_[a[1:],a[-1:]]-1)),n+1)if n<len(a)*4else a
from numpy import*

Try it online!

Each iteration spreads light upwards, then rotates the array by 90 degrees.

\$\endgroup\$
3
\$\begingroup\$

J, 28 27 bytes

(>./@,((,-)=1 2)|.!.0<:)^:_

Try it online!

Consider input:

0 0 4 0
0 0 0 0
0 2 0 0
0 0 0 0
  • (,-)=1 2) 4 directions of movement:

     1  0
     0  1
    _1  0
     0 _1
    
  • |.!.0<: Rotate the input minus 1 in those directions:

    _1 _1 _1 _1
    _1  1 _1 _1
    _1 _1 _1 _1
     0  0  0  0
    
    _1  3 _1  0
    _1 _1 _1  0
     1 _1 _1  0
    _1 _1 _1  0
    
     0  0  0  0
    _1 _1  3 _1
    _1 _1 _1 _1
    _1  1 _1 _1
    
     0 _1 _1  3
     0 _1 _1 _1
     0 _1  1 _1
     0 _1 _1 _1
    
  • >./@, Prepend input and max reduce the 5 "planes":

    0 3 4 3
    0 1 3 0
    1 2 1 0
    0 1 0 0
    
  • (...)^:_ Repeat that process until a fixed point:

    2 3 4 3
    1 2 3 2
    1 2 2 1
    0 1 1 0
    
\$\endgroup\$
3
\$\begingroup\$

Python 3, 207 205 bytes

Once I first saw this challenge posted, I started having some ideas for python solutions bouncing around in my head. This solution turned out to be way longer than I would have hoped, but I did find away to do this without numpy, which the other python solution uses:

f=lambda x:[[eval(f"max(max({i*'x[i-1][j],'}{j*'x[i][j-1],'}{~i%len(x)*'x[i+1][j],'}{~j%len(x)*'x[i][j+1],'})-1,x[i][j])")for j in range(len(x))]for i in range(len(x))]
g=lambda x:x if f(x)==x else g(f(x))

Try it online!

I wanted to be able to fit this into one lambda, but I simply couldn't seem to get the conditional to work, so g(x) is the function that is actually called to get the result. The main bulk of the code is in the giant eval() statement, which basically calculates the highest adjacent block, subtracts 1 from that, and takes the the max of that and the blocks current value. The rest of the code just iterates that over each block, and then recursively does that until all light levels have been calculated.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ you can save 2 bytes by changing f(x)if f(x)==x to x if f(x)==x \$\endgroup\$ Mar 28 at 3:37
  • \$\begingroup\$ Oh good one @patcharalimtrairat, I cant believe i missed that \$\endgroup\$
    – des54321
    Mar 28 at 4:19
2
\$\begingroup\$

Haskell, 107 bytes

r x=[0..length x-1]
f a=let(w,h)=(r$head a,r a)in[[maximum[a!!y!!x-abs(x-j)-abs(y-i)|x<-w,y<-h]|j<-w]|i<-h]

Attempt This Online!

\$\endgroup\$
1
2
\$\begingroup\$

Charcoal, 22 bytes

IEθEι⌈Eθ⌈Eν⁻π⁺↔⁻ξκ↔⁻ρμ

Try it online! Link is to verbose version of code. Explanation: Same algorithm as @alephalpha's PARI/GP answer.

 EθEι                   Map over input array
      Eθ Eν             Map over input array
            π           Innermost value
           ⁻            Subtract
              ↔⁻ξκ      Absolute row difference
             ⁺          Plus
                  ↔⁻ρμ  Absolute column difference
     ⌈  ⌈               Take the maximum
I                       Cast to string
                        Implicitly print

Note that Charcoal's default I/O format is rather ugly so I've also written a 26-byte prettier version which unfortunately only works up to 9:

WS⊞υιEυ⭆ι⌈Eυ⌈Eν⁻π⁺↔⁻ξκ↔⁻ρμ

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

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 73 bytes

m->matrix(#m~,#m,i,j,vecmax(matrix(#m~,#m,k,l,m[k,l]-abs(k-i)-abs(l-j))))

Attempt This Online!

\$output[i,j]=\underset{k,l}\max(input[k,l]-|k-i|-|l-j|)\$

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 22 21 bytes

Δ<U4FøíXøíDUćaª‚øεø€à

Port of @Jonah's J answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Δ           # Loop until the result no longer changes:
 <          #  Decrease each value in the matrix by 1
            #  (which will be the implicit input-matrix in the first iteration)
  U         #  Pop and store it in variable `X`
 4F         #  Loop 4 times:
   øí       #   Rotate the matrix once clockwise:
   ø        #    Zip/transpose; swapping rows/columns
    í       #    Reverse each inner row
            #   (which will be the implicit input-matrix in the first iteration)
   X        #   Push matrix `X`
    øí      #   Rotate it once clockwise as well
      DU    #   Store a copy as new value for `X`
        ć   #   Extract head; pop remainder-matrix and first row separated
         a  #   Convert all values in this row to 0 (with an is_letter check)
          ª #   Append this list of 0s as trailing row
   ‚øεø€à   #   Reduce the two matrices by maximum:
   ‚        #    Pair the two matrices together
    ø       #    Zip/transpose; creating pair of rows
     εø     #    Zip/transpose each inner pair of rows to pair of cell-values
       ۈ   #    Leave the maximum of each inner-most pair of cell-values
            # (after which the resulting matrix is output implicitly) 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.