20
1
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]]
3
You must print or return the final matrix.
Can I modify the input matrix instead? – Embodiment of Ignorance – 2019-05-10T17:14:14.2972@EmbodimentofIgnorance Yes, that's perfectly fine. – Arnauld – 2019-05-10T17:18:10.940
Values on the corner (diagonal) are consider neighbors? – Luis felipe De jesus Munoz – 2019-05-10T17:36:24.887
@LuisfelipeDejesusMunoz No, only horizontal and vertical, as specified. – Arnauld – 2019-05-10T17:46:11.487
1Can the output be padded with (several rows and columns of) 0s? – Robin Ryder – 2019-05-10T17:49:32.143
Per the usual I/O rules, I’ve assumed a flat list of integers is fine for input and output (though processed as though it were a square matrix). Is that correct? – Nick Kennedy – 2019-05-10T18:00:47.783
1@RobinRyder Because $0$ can't appear in the payload data, I'd say that's acceptable. – Arnauld – 2019-05-10T18:00:52.033
@NickKennedy Yes, that's OK. – Arnauld – 2019-05-10T18:09:34.817