16
\$\begingroup\$

This was inspired by Apply gravity to this matrix

Your challenge is to input a matrix with non-negative one-digit integers and drop down the 1's down 1 column, the 2's down 2 columns, the 3's down 3 columns, and so on. Once a number has been moved down and there is no number to take its original place, replace that slot with zero.

If the number can't be moved down enough, wrap it around the top. (e. g If there is a 3 in the second-to-last row, it should wrap around to the first row.)

If two numbers map to the same slot, the biggest number takes that slot.

Test cases:

0,1,2,1,0    0,0,0,0,0
0,0,2,0,1    0,1,0,1,0
1,0,2,1,0 => 0,0,2,0,1
0,0,0,1,0    1,0,2,1,0
0,0,0,0,0    0,0,2,1,0

0,0,2,0,1     0,0,2,0,0
0,2,1,1,0  => 3,0,0,0,1
3,0,2,1,0     0,0,2,1,0
0,0,0,0,0     0,2,0,1,0

Rules

Scoring

This is , so the answer with the least amount of bytes wins.

\$\endgroup\$
1
  • \$\begingroup\$ Suggested test cases: column 3100 -> 0013 (jumping over); column 800 -> 008 (wrapping around more than once) \$\endgroup\$
    – Stef
    Sep 27 at 8:50

15 Answers 15

7
\$\begingroup\$

APL(Dyalog Unicode), 17 16 14 bytes SBCS

-1 byte by looking at Jonah's J answer and another -2 bytes by implementing xash's suggestion on the same answer.

⌈/⊂(-⍤⊢⊖⊣×=)¨,

Try it on APLgolf!

I initially implemented a lot more "by hand", which ended up more than 3 times longer:

{{(⊃⍺)@(⊂1↓⍺)⊢⍵}/((↓⊂∘⍒⌷⊢){k,m|(k←≢⍵)0+⊃⍺}⌸⍸⍵),⊂0⍴⍨m←⍴⍵}

Try it on APLgolf!

\$\endgroup\$
7
\$\begingroup\$

J, 24 20 bytes

[:>./-@,|."0 2,*,=/]

Try it online!

-4 thanks to xash!

Solved independently, but seems very similar to ovs's APL solution. This one works for any number, because I didn't notice that the question only required handling 1-9.

The following explanation is slightly out of date, but the high-level concept, which is the interesting part, is still the same.

Consider input:

0 0 2 0 1
0 2 1 1 0
3 0 2 1 0
0 0 0 0 0
  • ~.@, ... ] - The ... part is a verb that takes the unique elements of the input ~.@, as the left arg and the unaltered input as the right arg:

                                    0 0 2 0 1
      0 2 1 3  >./@(-@[|."0 2[*=/)  0 2 1 1 0
                                    3 0 2 1 0
                                    0 0 0 0 0
    
  • =/ Checks if the entire input is equal to each of its unique elements, creating 4 masks, each the size of the original input:

      1 1 0 1 0
      1 0 0 0 1
      0 1 0 0 1  --> Locations of 0
      1 1 1 1 1
    
      0 0 1 0 0
      0 1 0 0 0
      0 0 1 0 0  --> Locations of 2
      0 0 0 0 0
    
      0 0 0 0 1
      0 0 1 1 0
      0 0 0 1 0  --> Locations of 1
      0 0 0 0 0
    
      0 0 0 0 0
      0 0 0 0 0
      1 0 0 0 0  --> Locations of 3
      0 0 0 0 0
    
  • [* Multiply each of those by the unique elements, giving us a "decomposed" version of the original input:

      0 0 0 0 0
      0 0 0 0 0
      0 0 0 0 0
      0 0 0 0 0
    
      0 0 2 0 0
      0 2 0 0 0
      0 0 2 0 0
      0 0 0 0 0
                     Decomposed input
      0 0 0 0 1
      0 0 1 1 0
      0 0 0 1 0
      0 0 0 0 0
    
      0 0 0 0 0
      0 0 0 0 0
      3 0 0 0 0
      0 0 0 0 0
    
  • -@[|."0 2 Rotate each of those matrices down by the required amount:

      0 0 0 0 0
      0 0 0 0 0
      0 0 0 0 0  --> Rotated 0
      0 0 0 0 0
    
      0 0 2 0 0
      0 0 0 0 0
      0 0 2 0 0  --> Rotated 2
      0 2 0 0 0
    
      0 0 0 0 0
      0 0 0 0 1
      0 0 1 1 0  --> Rotated 1
      0 0 0 1 0
    
      0 0 0 0 0
      3 0 0 0 0
      0 0 0 0 0  --> Rotated 3
      0 0 0 0 0
    
  • >./@ Reduce the "planes" by max:

    0 0 2 0 0
    3 0 0 0 1
    0 0 2 1 0
    0 2 0 1 0
    
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Using the unique numbers instead of 1 to 9 ended up being shorter in APL as well, so now it is really doing the same thing :) \$\endgroup\$
    – ovs
    Sep 25 at 22:15
  • 2
    \$\begingroup\$ 20b: Try it online! \$\endgroup\$
    – xash
    Sep 25 at 23:20
  • \$\begingroup\$ @xash I love that. Making it "bigger" made the solution smaller. \$\endgroup\$
    – Jonah
    Sep 26 at 0:23
6
\$\begingroup\$

Jelly,  16  12 bytes

I thought 16 seemed a bit much!

Zµ=Ɱ×ṙ"N»/)Z

A monadic Link that accepts a list of lists of integers and yields a list of lists of integers.

Try it online!

How?

Zµ=Ɱ×ṙ"N»/)Z - Link: matrix, M
Z            - transpose -> columns of M (top to bottom)
 µ        )  - for each (c in columns of M):
   Ɱ         -   map (across v in c) with:
  =          -     (c) equals (v)? (vectorises)
    ×        -   multiply by (c) (vectorises)
                 -> [c with zeroed out non-v's for each v in c] -  call this X
       N     -   negate (c)
      "      -   (X) zip (negated c) with:
     ṙ       -     rotate left by
         /   -   reduce by:
        »    -     maximum (vectorises)
           Z - transpose -> back to rows
\$\endgroup\$
3
5
\$\begingroup\$

JavaScript (ES6), 82 bytes

m=>m.map((r,y)=>r.map((_,x)=>m.map(q=(r,Y)=>q=(Y+(v=r[x]))%m.length-y|v<q?q:v)|q))

Try it online!

How?

For each position \$(x,y)\$ in the input matrix \$M\$ of height \$h\$, we look for all values \$M_{x,Y}\$ on the same column such that:

$$Y+M_{x,Y}\equiv y\pmod h$$

and keep the highest one.

\$\endgroup\$
5
\$\begingroup\$

Python 3 + numpy, 91 bytes

def f(a):r,c=a.nonzero();v=a[r,c];r+=v;i=v.argsort();a*=0;a[r[i]%len(a),c[i]]=v[i];return a

-23 due to @ovs

Try it online!

Much Different from the first solution. Takes a numpy array

(slightly outdated explanation) Assume the array

[[0 0 2 0 1]
 [0 2 1 1 0]
 [3 0 2 1 0]
 [0 0 0 0 0]]
  • r,c=nonzero(a) First save the x-indices (rows) to r and y-indices (cols) to c of nonzero elements
r: [0 0 1 1 1 2 2 2] 
c: [2 4 1 2 3 0 2 3]
  • v=a[r,c] Then get the nonzero elements into v
v: [2 1 2 1 1 3 2 1]
  • n=(r+v)%len(a) Then increment the each row (r) by respective nonzero elements (v) and modulo by matrix length (to wrap) and save to n
n: [2 1 3 2 2 1 0 3]
  • i=v.argsort() Grade up the nonzero elements (To fix the multiple slots problem)
i: [1 3 4 7 0 2 6 5]
  • j=a*0 Matrix of zeros of shape of a to j
j: [[0 0 0 0 0]
    [0 0 0 0 0]
    [0 0 0 0 0]
    [0 0 0 0 0]]
  • j[n[i],c[i]]=v[i] Assign graded up nonzero elements with new rows and old columns. Final result:
[[0 0 2 0 0]
 [3 0 0 0 1]
 [0 0 2 1 0]
 [0 2 0 1 0]]
\$\endgroup\$
9
  • \$\begingroup\$ You have a double space at the end, remove one of them for an easy bytesaving. \$\endgroup\$
    – ykcul
    Sep 26 at 12:12
  • 2
    \$\begingroup\$ zeros_like(a) can be shortened to a*0. And if you change nonzero(a) to a.nonzero() you can drop the import \$\endgroup\$
    – ovs
    Sep 26 at 15:53
  • \$\begingroup\$ And you don't need n and j: 91 bytes \$\endgroup\$
    – ovs
    Sep 26 at 16:05
  • \$\begingroup\$ @ovs thanks!! But why the import can be skipped? Is it general consensus \$\endgroup\$
    – wasif
    Sep 26 at 16:13
  • \$\begingroup\$ @ykcul where is the space? \$\endgroup\$
    – wasif
    Sep 26 at 16:14
4
\$\begingroup\$

R, 82 bytes

Or R>=4.1, 75 bytes by replacing the word function with \.

function(m,k=nrow(m),t=0*m){t[((row(m)+m-1)%%k+1+col(m)*k-k)[i]]=m[i<-order(m)];t}

Try it online!

Inspired by @wasif's answer.


Old solution (shorter for R>=4.1):

R, 94 92 89 88 bytes

Or R>=4.1, 74 bytes by replacing two function appearances with \s.

function(m,k=nrow(m))apply(m,2,function(x,t=0*x){t[((x-k:1)%%k+1)[i]]=x[i<-order(x)];t})

Try it online!

-2 bytes thanks to some arithmetic and moving \$nrows-x\$ up instead of \$x\$ down.

-3 bytes taking inspiration from @wasif's argsort in his answer (order in R).

\$\endgroup\$
4
\$\begingroup\$

Python 3+numpy, 73 bytes

import numpy
def f(A):t=numpy.c_[:len(A)];return(t*(A[t-t.T]==t)).max(1)

Try it online!

Note: this probably fails for double wrap around EDIT or, more generally, for matrix entries equal to or larger than the matrix height thanks @alephalpha for pointing this out end EDIT. I'm just not sure it is a requirement (this is my first post here).

How it works: We first clone the zeroth axis using an auxiliary indexer t. t is a column, t.T a row t-t.T is 2D, applied to the zeroth axis of A (the input) it creates a new axis. the index t-t.T populates this with rotated copies of A taking advantage of broadcasting, advanced indexing and standard python wrap around for negative indices. We then compare with t to find the places where the rotated value matches the rotation. This is a boolean array which we multiply with t to mark each match explicitly with its value. It remains to pick out the max value along the appropriate axis.

New contributor
loopy walt is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Welcome to Code Golf! Nice first post! \$\endgroup\$ Oct 19 at 4:15
  • \$\begingroup\$ Does it work when the largest integer in the matrix is larger than the matrix's size? \$\endgroup\$
    – alephalpha
    Oct 19 at 6:00
  • \$\begingroup\$ @alephalpha probably not. This is conceptually similar to but goes a bit farther than the double wrap around thing I already mentioned. I'm not 100% sure what OP's intention is, Falling past oneself may or may not be considered a pathological case. \$\endgroup\$
    – loopy walt
    Oct 19 at 6:14
3
\$\begingroup\$

Core Maude, 248 244 236 bytes

load linear
mod D is inc MATRIX{Nat0}*(sort Matrix{Nat0}to M). var A B C D : Nat . op d :
Nat M -> M . eq(A,B)|-> C ;(A,B)|-> D =(A,B)|-> max(C,D). eq d(A,(B,C)|-> D ;
X:M)=(B,(C + D)rem A)|-> D ; d(A,X:M). eq d(A,X:M)= X:M[owise]. endm

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Sun Sep 26 21:12:35 2021
Maude> red d(5, (1,0) |-> 1 ; (2,0) |-> 2 ; (3,0) |-> 1 ;
>          (2,1) |-> 2 ; (4,1) |-> 1 ;
>          (0,2) |-> 1 ; (2,2) |-> 2 ; (3,2) |-> 1 ;
>          (3,3) |-> 1 ) .
result M: 0,3 |-> 1 ; 1,1 |-> 1 ; 2,2 |-> 2 ; 2,3 |-> 2 ; 2,4 |-> 2 ; 3,1 |-> 1
    ; 3,3 |-> 1 ; 3,4 |-> 1 ; 4,2 |-> 1
Maude> red d(4, (2,0) |-> 2 ; (4,0) |-> 1 ;
>          (1,1) |-> 2 ; (2,1) |-> 1 ; (3,1) |-> 1 ;
>          (0,2) |-> 3 ; (2,2) |-> 2 ; (3,2) |-> 1 ) .
result M: 0,1 |-> 3 ; 1,3 |-> 2 ; 2,0 |-> 2 ; 2,2 |-> 2 ; 3,2 |-> 1 ; 3,3 |-> 1
    ; 4,1 |-> 1

Ungolfed

load linear

mod D is
    inc MATRIX{Nat0} * (sort Matrix{Nat0}to M).
    var A B C D : Nat .
    op d : Nat M -> M .
    eq (A, B) |-> C ; (A, B) |-> D = (A, B) |-> max(C, D) .
    eq d(A, (B, C) |-> D ; X:M) = (B, (C + D) rem A) |-> D ; d(A, X:M) .
    eq d(A, X:M) = X:M [owise] .
endm

The answer is obtained by reducing the function d with the height of the matrix and the matrix entries. In Maude, matrices are specified as a collection of their non-zero entries.

The height must be passed as a parameter because, in Maude's implementation of matrices, \$(M)\$ is indistinguishable from \$\big(\begin{smallmatrix} M & 0\\ 0 & 0 \end{smallmatrix}\big)\$ — i.e., all matrices can be infinitely extended with zeroes — but we must know the height to handle wrapping. We can't just assume it's the largest row number seen, because both example inputs have all zeroes for their last row.

One trick we use is to generate the output matrix initially without regard to collisions. It's not an error in Maude for a map to have duplicate keys, as long as you resolve them before you try to access that key from the map. We have a separate equation to resolve those duplicates. (Incidentally, that equation is why we must include MATRIX rather than protect it, which costs an extra byte (inc vs. pr) — because we're equating matrix terms to resolve collisions.)


Saved 4 bytes by dropping the var declaration for X and using an “on-the-fly” variable X:M.


Saved 8 bytes because I forgot to replace the module name DROP-DOWN with a shorter name before posting. 🤦

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

Python 3+numpy, 77 bytes

import numpy
b=0*a
for i in range(1,a.max()+1):b[numpy.roll(a==i,i,axis=0)]=i

Try it online!

the roll function does it all, and i stole the zeros_like trick from @ovs

New contributor
diggusbickus is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
2
\$\begingroup\$

Ruby, 155 bytes

->m{r,c,o=m.size,m[0].size,{}
o.default=0
e="r.times{|y|c.times{|x|"
eval e+"v=m[y][x]
v>o[[(y+v)%r,x]]&&o[[(y+v)%r,x]]=v}}"
eval e+"m[y][x]=o[[y,x]]}}"
m}

Try it online!

We build an hash object with 2d-index as key.
Then we iterate input and we set the key corresponding to landing position to the value if greater.

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

05AB1E, 19 18 14 bytes

˜εQy*yFÁ]øεø€à

-5 bytes thanks to @ovs.

Try it online or verify all test cases.

Explanation:

Z          # Get the flattened maximum of the (implicit) input-matrix
 L         # Pop and push a list in the range [1,max]
˜          # (`ZL` is now `˜`: flatten the (implicit) input-matrix)
  ε        # Map over each:
   Q       #  Check for each integer in the (implicit) input-matrix whether it's equal
           #  to this integer
    y*     #  Multiply each by this integer
      yF   #  Loop `y` amount of times:
        Á  #   And rotate the rows that many times towards the right
  ]        # Close both the inner loop and map
   ø       # Zip/transpose to get a list of lists of rows
    ε      # Map each list of rows to:
     ø     #  Zip/transpose; so the values of each cell are grouped together now
      ۈ   #  Get the maximum of each list of cell-values
           # (after which the matrix is output implicitly as result)

Here a step-by-step of an input to output; with the old ZL (flattened maximum; [1,max] ranged list) instead of ˜ (flatten the input-matrix):

Z             #  i.e. [[0,0,2,0,1],
              #        [0,2,1,1,0],
              #        [3,0,2,1,0],
              #        [0,0,0,0,0]] → 3
 L            # → [1,2,3]
  εQ          # → [[[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0],[0,0,0,0,0]],
              #    [[0,0,1,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,0]]]
    y*        # → [[[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0],[0,0,0,0,0]],
              #    [[0,0,2,0,0],[0,2,0,0,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,0],[0,0,0,0,0],[3,0,0,0,0],[0,0,0,0,0]]]
      yFÁ]    # → [[[0,0,0,0,0],[0,0,0,0,1],[0,0,1,1,0],[0,0,0,1,0]],
              #    [[0,0,2,0,0],[0,0,0,0,0],[0,0,2,0,0],[0,2,0,0,0]],
              #    [[0,0,0,0,0],[3,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]]
   ø          # → [[[0,0,0,0,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,0,1],[0,0,0,0,0],[3,0,0,0,0]],
              #    [[0,0,1,1,0],[0,0,2,0,0],[0,0,0,0,0]],
              #    [[0,0,0,1,0],[0,2,0,0,0],[0,0,0,0,0]]]
    εø        # → [[[0,0,0],[0,0,0],[0,2,0],[0,0,0],[0,0,0]],
              #    [[0,0,3],[0,0,0],[0,0,0],[0,0,0],[1,0,0]],
              #    [[0,0,0],[0,0,0],[1,2,0],[1,0,0],[0,0,0]],
              #    [[0,0,0],[0,2,0],[0,0,0],[1,0,0],[0,0,0]]]
      €à      # → [[0,0,2,0,0],
              #    [3,0,0,0,1],
              #    [0,0,2,1,0],
              #    [0,2,0,1,0]]
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can sacrifice a bit of efficiency for a byte: ˜ instead of ZL. \$\endgroup\$
    – ovs
    Sep 27 at 12:32
  • \$\begingroup\$ @ovs Thanks. :) \$\endgroup\$ Sep 27 at 13:05
  • 1
    \$\begingroup\$ øyδFÁ}ø} can be simplified to yFÁ]. \$\endgroup\$
    – ovs
    Sep 28 at 12:56
  • \$\begingroup\$ @ovs That's indeed a lot simpler.. Now that I see it I can't believe I was doing something so complex instead, haha.. Thanks. \$\endgroup\$ Sep 28 at 14:38
1
\$\begingroup\$

Python 2, 157 bytes

e=enumerate;l=input();j=[[0]*len(l[0])for _ in l]
for x,y,z in sorted([((n+x)%len(l),m,x)for n,y in e(l)for m,x in e(y)],key=lambda e:e[2]):j[x][y]=z
print j

Try it online!

-7 thanks to @ykcul

\$\endgroup\$
2
  • \$\begingroup\$ for _ in l in the first line saves a few bytes \$\endgroup\$
    – ykcul
    Sep 26 at 12:14
  • \$\begingroup\$ @ykcul nice thanks! \$\endgroup\$
    – wasif
    Sep 26 at 16:15
1
\$\begingroup\$

Charcoal, 23 bytes

IEθEι⌈Eθ∧¬﹪⁻⁺§νμξκLθ§νμ

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

  θ                     Input array
 E                      Map over rows
    ι                   Current row
   E                    Map over cells
       θ                Input array
      E                 Map over rows
             §νμ        Inner cell
            ⁺   ξ       Plus inner index
           ⁻     κ      Minus outer index
         ¬﹪             Is divisible by
                  Lθ    Height of array
        ∧               Logical And
                    §νμ Inner cell
     ⌈                  Maximum
I                       Cast to string
                        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 63 bytes

MapThread[Max,RotateRight[#/.x_/;x!=i:>0,i]~Table~{i,Max@#},2]&

Try it online!

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

Python 3, 103 bytes

r=range
f=lambda A:[*zip(*[[max(i*(c[j-i]==i)for i in r(len(c)))for j in r(len(c))]for c in zip(*A)])]

Try it online!

This is more or less a one-to-one translation of my numpy answer.

The same explanation and caveat apply.

New contributor
loopy walt is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\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.