Buat semua kotak meledak

20

Anda diberi matriks kuadrat lebar , yang berisi angka kuadrat .21

Tugas Anda adalah membuat semua angka kuadrat 'meledak' sampai semuanya hilang. Anda harus mencetak atau mengembalikan matriks terakhir.

Lebih spesifik:

  1. Cari kuadrat tertinggi dalam matriks.x2
  2. Cari tetangga terdekat terkecil (baik secara horizontal atau vertikal dan tanpa melilit).n
  3. Ganti dengan dan ganti dengan .x2xnn×x

Ulangi proses ini dari langkah 1 hingga tidak ada kotak lagi dalam matriks.

Contoh

Matriks input:

(62536196324)

Kotak tertinggi meledak menjadi dua bagian dan bergabung dengan tetangga terkecilnya , yang menjadi :625625=253636×25=900

(25900196324)

Kotak tertinggi meledak dan bergabung dengan tetangganya yang terkecil :90025

(75030196324)

Kotak tertinggi meledak dan bergabung dengan tetangganya yang terkecil :32430

(75054019618)

Satu-satunya persegi tersisa meledak dan bergabung dengan tetangganya yang terkecil :19618

(75054014252)

Tidak ada kotak lagi, jadi kita sudah selesai.

Aturan

  • Matriks input dijamin memiliki properti berikut:
    • di setiap langkah, alun-alun tertinggi akan selalu unik
    • pada setiap langkah, tetangga terkecil dari alun-alun tertinggi akan selalu unik
    • urutan tidak akan terulang selamanya
  • Matriks awal mungkin berisi , tetapi Anda tidak perlu khawatir membuat meledak, karena tidak akan pernah menjadi yang tertinggi atau satu-satunya persegi yang tersisa.11
  • I / O dapat diproses dalam format apa pun yang wajar
  • Ini adalah

Uji kasus

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
sumber
3
You must print or return the final matrix.Bisakah saya memodifikasi matriks input?
Perwujudan Ketidaktahuan
2
@EmbodimentofIgnorance Ya, tidak apa-apa.
Arnauld
Nilai di sudut (diagonal) dianggap tetangga?
Luis felipe De jesus Munoz
1
Bisakah output diisi dengan (beberapa baris dan kolom) 0s?
Robin Ryder
1
0

Jawaban:

5

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

Tidak ada yang kreatif, termasuk nol buffering dari elemen periferal dari matriks entri, versi sebelumnya yang kemudian ditingkatkan oleh 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}

Cobalah secara online

Menggunakan urutan angka sebagai entri, dan karenanya menghapus panggilan ke suatu fungsi, Nick Kennedy sebelumnya mengelola versi algoritma 186 byte sebagai berikut (dengan -10 byte oleh 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

menghindari definisi fungsi (rekursif), ditambah keuntungan bagus lainnya.

Cobalah secara online

Xi'an
sumber
1
Hitungan byte Anda tidak aktif. Dalam kasus apa pun, berikut ini adalah versi golf dengan
Nick Kennedy
2
Terima kasih untuk bertanya. Secara umum, jika seseorang memposting versi yang lebih pendek dalam komentar atas jawaban Anda, Anda dapat menggunakannya / menyesuaikan jawaban Anda atas dasar itu. Maka akan sopan untuk menambahkan suatu tempat di teks yang menyertai 'Terima kasih kepada @ <user> untuk menyimpan <number> byte!' atau serupa. Jika saya berakhir di suatu tempat yang secara dramatis berbeda dengan jawaban Anda tetapi telah mengambil inspirasi dari jawaban Anda, saya mungkin malah memposting jawaban terpisah yang mengakui Anda. Tapi di sini, sebagian besar dari apa yang saya lakukan adalah perubahan kecil - metode dasar tetap milik Anda.
Nick Kennedy
2

Ruby , 140 135 byte

Mengambil daftar datar sebagai input, menampilkan daftar datar.

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

Cobalah online!

Penjelasan:

->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.
Nilai Tinta
sumber
2

Python 2 , 188 byte

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

Cobalah online!

Program lengkap. Mengambil input dan mencetak sebagai daftar datar.

Erik the Outgolfer
sumber
2

Perl 6 , 236 byte

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

Cobalah online!

bb94
sumber
1
213 byte . Saya memiliki beberapa keraguan bahwa mekanisme putarannya sesingkat mungkin ... Saya juga kesal karena kita dikalahkan oleh Python, jadi mungkin pendekatan yang berbeda sedang dilakukan
Jo King
2

MATL , 49 48 byte

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

Cobalah online! Atau verifikasi semua kasus uji .

Bagaimana itu bekerja

`           % 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
sumber
1

JavaScript (ES6), 271 259 250 245 byte

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

Terima kasih kepada Luis felipe De jesus Munoz untuk −14 byte!

Penjelasan:

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
sumber
1

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

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]);}

Cobalah online!

Perwujudan Ketidaktahuan
sumber
1

Bahasa Wolfram (Mathematica) , 224 byte

(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)&

Cobalah online!

J42161217
sumber
1

JavaScript (Node.js) , 157 byte

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)

Cobalah online!

-14 byte terima kasih pada @Arnauld yang juga menulis test harness yang bagus :)

Fungsi anonim yang mengambil array 1 dimensi sebagai input dan parameter panjang yang menentukan angka jika kolom / baris.

Input kari ditentukan sebagai 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
sumber
1

Java 8, 299 297 byte

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

Memodifikasi input-matriks alih-alih mengembalikan yang baru untuk menghemat byte.

Cobalah online.

Penjelasan:

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
sumber
1

Jelly , 70 67 byte

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

Cobalah online!

Saya yakin ini bisa dilakukan lebih singkat, tetapi saya menemukan ini lebih sulit daripada yang pertama kali muncul. Penjelasan untuk diikuti setelah saya mencoba bermain golf dengan lebih baik.

Program lengkap yang mengambil daftar bilangan bulat yang sesuai dengan matriks kuadrat dan mengembalikan daftar bilangan bulat yang mewakili matriks meledak terakhir.

Nick Kennedy
sumber