Make all the squares explode

Question

You are given a square matrix of width \$\ge2\$, containing square numbers \$\ge1\$.

Your task is to make all square numbers 'explode' until all of them have disappeared. You must print or return the final matrix.

More specifically:

Look for the highest square \$x^2\$ in the matrix.
Look for its smallest adjacent neighbor \$n\$ (either horizontally or vertically and without wrapping around).
Replace \$x^2\$ with \$x\$ and replace \$n\$ with \$n\times x\$.

Repeat the process from step 1 until there's no square anymore in the matrix.

Example

Input matrix:

$$\begin{pmatrix} 625 & 36\\ 196 & 324 \end{pmatrix}$$

The highest square \$625\$ explodes into two parts of \$\sqrt{625}=25\$ and merges with its smallest neighbor \$36\$, which becomes \$36\times 25=900\$:

$$\begin{pmatrix} 25 & 900\\ 196 & 324 \end{pmatrix}$$

The highest square \$900\$ explodes and merges with its smallest neighbor \$25\$:

$$\begin{pmatrix} 750 & 30\\ 196 & 324 \end{pmatrix}$$

The highest square \$324\$ explodes and merges with its smallest neighbor \$30\$:

$$\begin{pmatrix} 750 & 540\\ 196 & 18 \end{pmatrix}$$

The only remaining square \$196\$ explodes and merges with its smallest neighbor \$18\$:

$$\begin{pmatrix} 750 & 540\\ 14 & 252 \end{pmatrix}$$

There's no square anymore, so we're done.

Rules

The input matrix is guaranteed to have the following properties:
- at each step, the highest square will always be unique
- at each step, the smallest neighbor of the highest square will always be unique
- the sequence will not repeat forever
The initial matrix may contain \$1\$'s, but you do not have to worry about making \$1\$ explode, as it will never be the highest or the only remaining square.
I/O can be processed in any reasonable format
This is code-golf

Test cases

Input : [[16,9],[4,25]]
Output: [[24,6],[20,5]]

Input : [[9,4],[1,25]]
Output: [[3,12],[5,5]]

Input : [[625,36],[196,324]]
Output: [[750,540],[14,252]]

Input : [[1,9,49],[1,4,1],[36,25,1]]
Output: [[3,6,7],[6,2,7],[6,5,5]]

Input : [[81,4,64],[16,361,64],[169,289,400]]
Output: [[3,5472,8],[624,323,1280],[13,17,20]]

Input : [[36,100,1],[49,144,256],[25,49,81]]
Output: [[6,80,2],[42,120,192],[175,21,189]]

Input : [[256,169,9,225],[36,121,144,81],[9,121,9,36],[400,361,100,9]]
Output: [[384,13,135,15],[24,1573,108,54],[180,11,108,6],[380,209,10,90]]

Input : [[9,361,784,144,484],[121,441,625,49,25],[256,100,36,81,529],[49,4,64,324,16],[25,1,841,196,9]]
Output: [[171,19,700,4032,22],[11,210,525,7,550],[176,60,6,63,23],[140,112,1152,162,368],[5,29,29,14,126]]

You must print or return the final matrix. Can I modify the input matrix instead? — Gymhgy, May 10, 2019 at 17:14
Can the output be padded with (several rows and columns of) 0s? — Robin Ryder, May 10, 2019 at 17:49
@RobinRyder Because \$0\$ can't appear in the payload data, I'd say that's acceptable. — Arnauld, May 10, 2019 at 18:00

Xi'an ні війні · Accepted Answer · 2019-05-13 14:06:57Z

5

R, 301 287 277 274 222 217 195 186 178 174 bytes

Nothing particularly creative, including the zero buffering of the peripheral elements of the entry matrix, an earlier version later improved by Robin:

function(x){w=which.max
if(any(s<-!x^.5%%1)){
y=cbind(NA,rbind(NA,x,NA),NA)
z=y[i]=y[i<-w(y*y%in%x[s])]^.5
m=i+c(r<--c(1,nrow(y)),-r)
y[j]=y[j<-m[w(-y[m])]]*z
x=p(y[r,r])}
x}

Try it on-line

Using a sequence of numbers as its entry, and hence removing the call to a function, Nick Kennedy earlier managed a 186 bytes version of the algorithm as follows (with -10 bytes by Robin):

w=which.max;`~`=cbind;x=scan();while(any(s<-!x^.5%%1)){y=NA~t(NA~matrix(x,n<-length(x)^.5)~NA)~NA;i=w(y*y%in%x[s]);=i+c(r<--c(1,n+2),-r);y[j]=y[j<-m[w(-y[m])]]*(y[i]=y[i]^.5);x=y[r,r]};x

avoiding the definition of a (recursive) function, plus other nice gains.

Try it on-line

edited May 13, 2019 at 14:06

answered May 11, 2019 at 15:15

Xi'an ні війні

8287 silver badges21 bronze badges

1

\$\begingroup\$ Your byte count is off. In any case, here’s a heavily golfed version at 196 bytes: tio.run/… \$\endgroup\$
– Nick Kennedy
May 11, 2019 at 16:37
2

\$\begingroup\$ thanks for asking. In general, if someone posts a shorter version in a comment to your answer, you’re welcome to use it/adapt your answer on that basis. It would then be polite to add somewhere in the accompanying text 'Thanks to @<user> for saving <number> bytes!' or similar. If I’d ended up somewhere dramatically different to your answer but had taken inspiration from yours, I might instead have posted a separate answer acknowledging you. But here, most of what I’ve done are minor tweaks - the fundamental method remains yours. \$\endgroup\$
– Nick Kennedy
May 11, 2019 at 17:48

Add a comment |

Value Ink · Accepted Answer · 2019-05-10 19:32:44Z

Ruby, 140 135 bytes

Takes a flat list as input, outputs a flat list.

->m{i=1;(i=m.index m.reject{|e|e**0.5%1>0}.max
m[i+[1,-1,l=m.size**0.5,-l].min_by{|j|i+j>=0&&m[i+j]||m.max}]*=m[i]**=0.5if i)while i;m}

Try it online!

Explanation:

->m{                                # Anonymous lambda
    i=1;                            # Initialize i for the while loop
        (                           # Start while loop

i=m.index                           # Get index at...
    m.reject{|e|          }         # Get all elements of m, except the ones with...
                e**0.5%1>0          # a square root with a fractional component
                           .max     # Get the largest of these

m[i+                                # Get item at...
    [1,-1,l=m.size**0.5,-l]         # Get possible neighbors (up, down, left, right)
        .min_by{|j|i+j>=0&&m[i+j]|| # Find the one with the minimum value at neighbor
                            m.max}  # If out of range, return matrix max so
                                    #   neighbor isn't chosen
    ]
    *=m[i]**=0.5                    # Max square becomes its square root, then multiply
                                    #   min neighbor by it

)while i                            # End while loop. Terminate when index is nil.
m}                                  # Return matrix.

Erik the Outgolfer · Accepted Answer · 2019-05-11 12:04:22Z

2

Python 2, 188 bytes

M=input()
l=int(len(M)**.5)
try:
 while 1:m=M.index(max(i**.5%1or i for i in M));_,n=min((M[m+i],m+i)for i in m/l*[-l]+-~m%l*[1]+[l][:m/l<l-1]+m%l*[-1]);M[m]**=.5;M[n]*=M[m]
except:print M

Try it online!

Full program. Takes input and prints as a flat list.

answered May 11, 2019 at 12:04

Erik the Outgolfer

40.6k5 gold badges42 silver badges122 bronze badges

Add a comment |

bb94 · Accepted Answer · 2019-05-12 09:14:43Z

2

Perl 6, 236 bytes

{my@k=.flat;my \n=$_;loop {my (\i,\j)=@k>>.sqrt.grep({$_+|0==$_},:kv).rotor(2).max(*[1]);last if 0>i;$/=((0,1),(0,-1),(1,0),(-1,0)).map({$!=i+n*.[0]+.[1];+$!,n>.[0]+i/n&.[1]+i%n>=0??@k[$!]!!Inf}).min(*[1]);@k[i,$0]=j,j*$1};@k.rotor(+n)}

Try it online!

edited May 12, 2019 at 9:14

answered May 11, 2019 at 7:44

bb94

2,59113 silver badges17 bronze badges

1

\$\begingroup\$ 213 bytes. I have some doubts that the looping mechanism is as short as it could be though... I'm also annoyed that we're being beaten by Python, so maybe a different approach is in order \$\endgroup\$
– Jo King ♦
May 14, 2019 at 10:18

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

MATL, 49 48 bytes

`ttX^tt1\~*X>X>XJt?wy=(tt5M1Y6Z+*tXzX<=*Jq*+w}**

Try it online! Or verify all test cases.

How it works

`           % Do...while
  tt        %   Duplicate twice. Takes a matrix as input (implicit) the first time
  X^        %   Square root of each matrix entry
  tt        %   Duplicate twice
  1\~       %   Modulo 1, negate. Gives true for integer numbers, false otherwise
  *         %   Multiply, element-wise. This changes non-integers into zero
  X>X>      %   Maximum of matrix. Gives maximum integer square root, or zero
  XJ        %   Copy into clipboard J
  t         %   Duplicate
  ?         %   If non-zero
    wy      %     Swap, duplicate from below. Moves the true-false matrix to top
    =       %     Equals, element-wise. This gives a matrix which is true at the
            %     position of the maximum that was previously identified, and
            %     false otherwise
    (       %     Write the largest integer square root into that position
    tt      %     Duplicate twice
    5M      %     Push again the matrix which is true for the position of maximum
    1Y6     %     Push matrix [0 1 0; 1 0 1; 0 1 0] (von Neumann neighbourhood)
    Z+      %     2D convolution, keeping size. Gives a matrix which is 1 for the
            %     neighbours of the value that was replaced by its square root
    *       %     Multiply. This replaces the value 1 by the actual values of
            %     the neighbours
    t       %     Duplicate
    XzX<    %     Minimum of non-zero entries
    =       %     Equals, element-wise. This gives a matrix which is true at the
            %     position of the maximum neighbour, and zero otherwise
    *       %     Multiply, element-wise. This gives a matrix which contains the
            %     maximum neighbour, and has all other entries equal to zero
    J       %     Push the maximum integer root, which was previously stored
    q       %     Subtract 1
    *       %     Multiply element-wise. This gives a matrix which contains the
            %     maximum neighbour times (maximum integer root minus 1)
    +       %     Add. This replaces the maximum neighbour by the desired value,
            %     that is, the previously found maximum integer square root
            %     times the neighbour value
    w       %     Swap
  }         %   Else. This means there was no integer square root, so no more
            %   iterations are neeeded
  **        %   Multiply element-wise twice. Right before this the top of the
            %   stack contains a zero. Below there are the latest matrix with
            %   square roots and two copies of the latest matrix of integers,
            %   one of which needs to be displayed as final result. The two
            %   multiplications leave the stack containing a matrix of zeros
            %   and the final result below
            % End (implicit). The top of the stack is consumed. It may be a
            % positive number, which is truthy, or a matrix of zeros, which is
            % falsy. If truthy a new iteration is run. If falsy the loop exits
            % Display (implicit)

ArkaneMoose · Accepted Answer · 2019-05-10 21:41:51Z

JavaScript (ES6), 271 259 250 245 bytes

m=>{for(l=m.length;I=J=Q=-1;){for(i=0;i<l;i++)for(j=0;j<l;j++)!((q=m[i][j]**.5)%1)&&q>Q&&(I=i,J=j,Q=q);if(I<0)break;d=[[I-1,J],[I+1,J],[I,J-1],[I,J+1]];D=d.map(([x,y])=>(m[x]||0)[y]||1/0);[x,y]=d[D.indexOf(Math.min(...D))];m[x][y]*=Q;m[I][J]=Q}}

Thanks to Luis felipe De jesus Munoz for −14 bytes!

Explanation:

m => { // m = input matrix
  // l = side length of square matrix
  // I, J = i, j of largest square in matrix (initialized to -1 every iteration)
  // Q = square root of largest square in matrix
  for (l = m.length; (I = J = Q = -1); ) {
    // for each row,
    for (i = 0; i < l; i++)
      // for each column,
      for (j = 0; j < l; j++)
        // if sqrt of m[i][j] (assigned to q) has no decimal part,
        // (i.e. if m[i][j] is a perfect square and q is its square root,)
        !((q = m[i][j] ** 0.5) % 1) &&
          // and if this q is greater than any previously seen q this iteration,
          q > Q &&
          // assign this element to be the largest square in matrix.
          ((I = i), (J = j), (Q = q));
    // if we did not find a largest square in matrix, break loop.
    if (I < 0) break;
    // d = [i, j] pairs for each neighbor of largest square in matrix
    d = [[I - 1, J], [I + 1, J], [I, J - 1], [I, J + 1]];
    // D = value for each neighbor in d, or Infinity if value does not exist
    D = d.map(([x, y]) => (m[x] || 0)[y] || 1 / 0);
    // x = i, y = j of smallest adjacent neighbor of largest square
    [x, y] = d[D.indexOf(Math.min(...D))];
    // multiply smallest adjacent neighbor by square root of largest square
    m[x][y] *= Q;
    // set largest square to its square root
    m[I][J] = Q;
  } // repeat until no remaining squares in matrix
  // no return necessary; input matrix is modified.
};

Gymhgy · Accepted Answer · 2019-05-10 22:20:20Z

1

C# (Visual C# Interactive Compiler), 220 bytes

n=>l=>{for(int g;n.Any(x=>Math.Sqrt(x)%1==0);n[n.Select((a,b)=>(x:Math.Abs(b/l-g/l)+Math.Abs(b%l-g%l)==1?a:1<<30,y:b)).OrderBy(x=>x).First().y]*=n[g])n[g=n.IndexOf(n.Max(x=>Math.Sqrt(x)%1==0?x:0))]=(int)Math.Sqrt(n[g]);}

Try it online!

edited May 10, 2019 at 22:20

answered May 10, 2019 at 21:24

Gymhgy

7,99810 silver badges35 bronze badges

Add a comment |

ZaMoC · Accepted Answer · 2019-05-11 00:10:19Z

1

Wolfram Language (Mathematica), 224 bytes

(l=#;While[(c=Length)[m=Select[Join@@l,IntegerQ[Sqrt@#]&]]>0,t=##&@@#&@@SortBy[Select[(g=#&@@Position[l,f=Max@m])+#&/@{{1,0},{0,1},{-1,0},{0,-1}},Min@#>0&&Max@#<=c@l&],l[[##]]&@@#&];l[[##&@@g]]=(n=Sqrt@f);l[[t]]=l[[t]]n];l)&

Try it online!

edited May 11, 2019 at 0:10

answered May 10, 2019 at 23:55

ZaMoC

24.9k2 gold badges30 silver badges81 bronze badges

Add a comment |

dana · Accepted Answer · 2019-05-13 05:05:59Z

JavaScript (Node.js), 157 bytes

a=>g=(l,m=n=i=j=0)=>a.map((o,k)=>m>o||o**.5%1||[m=o,i=k])|m&&a.map((o,k)=>n*n<o*n|((i/l|0)-(k/l|0))**2+(i%l-k%l)**2-1||[n=o,j=k])|[a[i]=m**=.5,a[j]=m*n]|g(l)

Try it online!

-14 bytes thanks the @Arnauld who also wrote a nice test harness :)

Anonymous function that takes a 1-dimensional array as input and a length parameter specifying number if columns/rows.

Curried input is specified as f(array)(length).

// a: 1-dimensional array of values
// g: recursive function that explodes once per recursive call
// l: number of columns, user specified
// m: max square value
// n: min neighbor
// i: index of max square
// j: index of min neighbor
a=>g=(l,m=n=i=j=0)=>
  // use .map() to iterate and find largest square
  a.map((o,k)=>
    // check size of element
    m>o||
    // check if element is a square
    o**.5%1||
    // new max square found, update local variables
    [m=o,i=k])|
  // after first .map() is complete, continue iff a square is found
  // run .map() again to find smallest neighbor
  m&&a.map((o,k)=>
    // check size of element
    n*n<o*n|
    // check relative position of element
    ((i/l|0)-(k/l|0))**2+(i%l-k%l)**2-1||
    // a new smallest neighbor found, update local variables
    [n=o,j=k])|
  // update matrix in-place, largest square is reduced,
  // smallest neighbor is increased
  [a[i]=m**=.5,a[j]=m*n]|
  // make recursive call to explode again
  g(l)

Jo King · Accepted Answer · 2019-05-14 10:20:33Z

1

Jelly, 70 67 bytes

’dL½$}©+Ø.,U$;N$¤%®‘¤<®Ạ$Ƈæ.®‘ịÐṂḢ;ḷ;€ị½¥×÷ƭ⁹Ḣ¤¦Ṫ}¥ƒ
×Æ²$MḢçɗ⁸Ẹ?ƊÐL

Try it online!

I’m sure this can be done much more briefly, but I found this harder than it first appeared. Explanation to follow once I’ve tried to golf it better.

A full program that takes a list of integers corresponding to the square matrix and returns a list of integers representing the final exploded matrix.l

edited May 14, 2019 at 10:20

Jo King♦

47.2k5 gold badges124 silver badges184 bronze badges

answered May 10, 2019 at 18:01

Nick Kennedy

21.1k3 gold badges16 silver badges42 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2022-12-21 14:18:42Z

Java 8, 299 297 289 279 bytes

m->{for(int l=m.length,i,j,I,J,d,M,t,x,y;;m[x][y]*=d){for(i=l*l,I=J=d=0;i-->0;)d=Math.sqrt(t=m[i/l][i%l])%1==0&t>d*d?(int)Math.sqrt(m[I=i/l][J=i%l]):d;if(d<1)break;for(M=-1>>>1,m[x=I][y=J]=d,t=4;t-->0;)try{M=m[i=I+t/2-t/3*2][j=t<1?J-1:1/t+J]<M?m[x=i][y=j]:M;}finally{continue;}}}

-18 bytes thanks to @ceilingcat.

Modifies the input-matrix instead of returning a new one to save bytes.

Try it online.

Explanation:

m->{                          // Method with integer-matrix input and no return-type
  for(int l=m.length,         //  Dimension-length `l` of the matrix
      i,j,I,J,d,M,t,x,y;      //  Temp integers
      ;                       //  Loop indefinitely:
       m[x][y]*=d){           //    After every iteration: multiply `x,y`'s value with `d`
    for(I=J=d=0,              //   (Re)set `I`, `J`, and `d` all to 0
        i=l*l;i-->0;)         //   Loop over all the cells:
      d=                      //    Set `d` to:
        Math.sqrt(t=m[i/l][i%l])%1==0?
                              //     If the current value is a perfect square
        *t>d*d?               //     And if it's larger than `d` squared:
          (int)Math.sqrt(m[I=i/l][J=i%l])
                              //      Set `I,J` to the current coordinate
                              //      And `d` to the square-root of the current value
        :d;                   //     Else: leave `d` the same
    if(d<1)                   //   If `d` is still 0 after the nested loop
                              //   (which means there are no more square-numbers)
      break;                  //    Stop the infinite loop
    for(M=-1>>>1,             //   (Re)set `M` to Integer.MAX_VALUE
        m[x=I][y=J]=d,        //   Replace the value at `I,J` with `d`
        t=4;t-->0;)           //   Loop `t` in the range (4, 0]:
      try{M=                  //    Set `M` to:
            m[i=I+t/2-t/3*2]  //     If `t` is 3:
                              //      Go to the row above
                              //     Else-if `t` is 2:
                              //      Go to the row below
                              //     Else (`t` is 0 or 1):
                              //      Stay in the current row
                              //     (and save this row in `i`)
             [j=t<1?J-1:1/t+J]//     If `t` is 0:
                              //      Go to the column left
                              //     Else-if `t` is 1:
                              //      Go to the column right
                              //     Else (`t` is 2 or 3):
                              //      Stay in the current column
                              //     (and save this column in `j`)
             <M?              //     And if the value in this cell is smaller than `M`:
                m[x=i][y=j]   //      Set `x,y` to `i,j`
                              //      And `M` to the current value in `i,j`
               :M;            //     Else: leave `M` the same
      }finally{continue;}}}   //    Catch and ignore IndexOutOfBoundsExceptions

l4m2 · Accepted Answer · 2022-12-21 16:21:45Z

1

JavaScript (Node.js), 141 bytes

f=(a,I,J,r)=>a.map((x,i)=>x.map((y,j)=>(1+J?(i-I)**2+(j-J)**2-1|r<y:y**.5%1||r>y)||(P=i,Q=j,r=y)))|1+J?f(a,a[P][Q]*=a[I][J]**=.5):r&&f(a,P,Q)

Try it online!

Take input 2D array

answered Dec 21, 2022 at 16:21

l4m2

23.9k2 gold badges23 silver badges91 bronze badges

Add a comment |

Stack Exchange Network

Make all the squares explode

Example

Rules

Test cases

12 Answers 12

R, 301 287 277 274 222 217 195 186 178 174 bytes

Ruby, 140 135 bytes

Python 2, 188 bytes

Perl 6, 236 bytes

MATL, 49 48 bytes

How it works

JavaScript (ES6), 271 259 250 245 bytes

C# (Visual C# Interactive Compiler), 220 bytes

Wolfram Language (Mathematica), 224 bytes

JavaScript (Node.js), 157 bytes

Jelly, 70 67 bytes

Java 8, 299 297 289 279 bytes

JavaScript (Node.js), 141 bytes

Your Answer

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

Hot Network Questions

Make all the squares explode

Example

Rules

Test cases

12 Answers 12

R, 301 287 277 274 222 217 195 186 178 174 bytes

Ruby, 140 135 bytes

Python 2, 188 bytes

Perl 6, 236 bytes

MATL, 49 48 bytes

How it works

JavaScript (ES6), 271 259 250 245 bytes

C# (Visual C# Interactive Compiler), 220 bytes

Wolfram Language (Mathematica), 224 bytes

JavaScript (Node.js), 157 bytes

Jelly, 70 67 bytes

Java 8, 299 297 289 279 bytes

JavaScript (Node.js), 141 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

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