Haz explotar todos los cuadrados

20

Se le da una matriz cuadrada de ancho 2 , que contiene números cuadrados 1 .

Su tarea es hacer que todos los números cuadrados "exploten" hasta que todos hayan desaparecido. Debe imprimir o devolver la matriz final.

Más específicamente:

  1. Busque el cuadrado más alto en la matriz.x2
  2. Busque su vecino adyacente más pequeño (ya sea horizontal o verticalmente y sin envolver).n
  3. Reemplace con y reemplace con n × x .x2xnortenorte×X

Repita el proceso desde el paso 1 hasta que ya no haya cuadrado en la matriz.

Ejemplo

Matriz de entrada:

(62536196324)

El cuadrado más alto 625 explota en dos partes de y se fusiona con su vecino más pequeño , que se convierte en 36 × 25 = 900 :625=253636×25=900

(25900196324)

El cuadrado más alto 900 explota y se fusiona con su vecino más pequeño 25 :

(75030196324)

El cuadrado más alto 324 explota y se fusiona con su vecino más pequeño 30 :

(75054019618 años)

El único cuadrado restante 196 explota y se fusiona con su vecino más pequeño 18 años :

(75054014252)

Ya no hay cuadrado, así que hemos terminado.

Reglas

  • Se garantiza que la matriz de entrada tiene las siguientes propiedades:
    • en cada paso, el cuadrado más alto siempre será único
    • en cada paso, el vecino más pequeño del cuadrado más alto siempre será único
    • la secuencia no se repetirá para siempre
  • La matriz inicial puede contener 1 's, pero no tiene que preocuparse por hacer que 1 explote, ya que nunca será el cuadrado más alto o único.
  • Las E / S se pueden procesar en cualquier formato razonable
  • Esto es

Casos de prueba

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]]
Arnauld
fuente
3
You must print or return the final matrix.¿Puedo modificar la matriz de entrada en su lugar?
Encarnación de la ignorancia
2
@EmbodimentofIgnorance Sí, eso está perfectamente bien.
Arnauld
Los valores en la esquina (diagonal) se consideran vecinos?
Luis felipe De jesus Munoz
1
¿Se puede rellenar la salida con (varias filas y columnas de) 0s?
Robin Ryder
1
@RobinRyder Debido a que no puede aparecer en los datos de carga útil, diría que es aceptable. 0 0
Arnauld

Respuestas:

5

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

Nada particularmente creativo, incluido el almacenamiento en búfer cero de los elementos periféricos de la matriz de entrada, una versión anterior más tarde mejorada por 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}

Pruébalo en línea

Utilizando una secuencia de números como su entrada y, por lo tanto, eliminando la llamada a una función, Nick Kennedy administró anteriormente una versión de 186 bytes del algoritmo de la siguiente manera (con -10 bytes por 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

evitando la definición de una función (recursiva), más otras buenas ganancias.

Pruébalo en línea

Xi'an
fuente
1
Tu recuento de bytes está apagado. En cualquier caso, aquí hay una versión muy golfizada en 196 bytes: tio.run/…
Nick Kennedy
2
gracias por preguntar. En general, si alguien publica una versión más corta en un comentario a su respuesta, puede usarla / adaptar su respuesta sobre esa base. Sería cortés agregar en algún lugar del texto adjunto '¡Gracias a @ <usuario> por guardar <número> bytes!' o similar. Si hubiera terminado en un lugar dramáticamente diferente a su respuesta, pero me hubiera inspirado en la suya, podría haber publicado una respuesta por separado que lo reconociera. Pero aquí, la mayoría de lo que he hecho son ajustes menores: el método fundamental sigue siendo suyo.
Nick Kennedy
2

Ruby , 140 135 bytes

Toma una lista plana como entrada, emite una lista plana.

->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}

Pruébalo en línea!

Explicación:

->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.
Tinta de valor
fuente
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

Pruébalo en línea!

Programa completo Toma entrada e imprime como una lista plana.

Erik el Outgolfer
fuente
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)}

Pruébalo en línea!

bb94
fuente
1
213 bytes . Tengo algunas dudas de que el mecanismo de bucle sea tan corto como podría ser ... También estoy molesto de que Python nos esté golpeando, así que tal vez sea necesario un enfoque diferente
Jo King
2

MATL , 49 48 bytes

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

Pruébalo en línea! O verificar todos los casos de prueba .

Cómo funciona

`           % 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)
Luis Mendo
fuente
1

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}}

¡Gracias a Luis felipe De jesus Munoz por −14 bytes!

Explicación:

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.
};
ArkaneMoose
fuente
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)&

Pruébalo en línea!

J42161217
fuente
1

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)

Pruébalo en línea!

-14 bytes gracias a @Arnauld que también escribió un buen arnés de prueba :)

Función anónima que toma una matriz unidimensional como entrada y un parámetro de longitud que especifica el número de columnas / filas.

La entrada al curry se especifica como 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)
dana
fuente
1

Java 8, 299 297 bytes

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

Modifica la matriz de entrada en lugar de devolver una nueva para guardar bytes.

Pruébalo en línea.

Explicación:

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;i-->0;)           //   Loop `i` in the range (`l`, 0]:
      for(j=l;j-->0;          //    Inner loop `j` in the range (`l`, 0]:
          d=                  //      After every iteration: set `d` to:
            t>d*d             //       If `t` is larger than `d` squared
            &Math.sqrt(t)%1==0?
                              //       And `t` is a perfect square:
             (int)Math.sqrt(m[I=i][J=j])
                              //        Set `I,J` to the current `i,j`
                              //        And `d` to the square-root of `t`
            :d)               //       Else: leave `d` the same
        t=m[i][j];            //     Set `t` to the value of `i,j`
    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=t>2?          //     If `t` is 3:
                 I-1          //      Go to the row above
                :t>1?         //     Else-if `t` is 2:
                 I+1          //      Go to the row below
                :             //     Else (`t` is 0 or 1):
                 I]           //      Stay in the current row
                              //     (and save this row in `i`)
             [j=t<1?          //     If `t` is 0:
                 J-1          //      Go to the column left
                :t<2?         //     Else-if `t` is 1:
                 J+1          //      Go to the column right
                :             //     Else (`t` is 2 or 3):
                 J]           //      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
      }catch(Exception e){}}} //    Catch and ignore IndexOutOfBoundsExceptions
Kevin Cruijssen
fuente
1

Jalea , 70 67 bytes

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

Pruébalo en línea!

Estoy seguro de que esto se puede hacer mucho más brevemente, pero me pareció más difícil de lo que parecía. Explicación a seguir una vez que he intentado jugar mejor al golf.

Un programa completo que toma una lista de enteros correspondientes a la matriz cuadrada y devuelve una lista de enteros que representan la matriz explotada final.

Nick Kennedy
fuente