25
\$\begingroup\$

sandbox (deleted)

Lets define a matrix of 9s as: $$ N = \begin{bmatrix} 9&9&9\\9&9&9\\9&9&9 \end{bmatrix} $$

Lets define an exploding number as a number at position \$(x,y)\$ that can be decomposed into equal integers between all its adjacent neighbors (including itself) and the absolute value of each portion is greater than 0.

From the previous matrix, lets explode the number at position \$(1,1)\$ (0 indexed) $$ N = \begin{bmatrix} 9&9&9\\9&\color{red}9&9\\9&9&9 \end{bmatrix} $$ $$ N = \begin{bmatrix} 9+\color{red}1&9+\color{red}1&9+\color{red}1\\9+\color{red}1&\color{blue}0+\color{red}1&9+\color{red}1\\9+\color{red}1&9+\color{red}1&9+\color{red}1 \end{bmatrix} $$

$$ N = \begin{bmatrix} 10&10&10\\10&\color{red}1&10\\10&10&10 \end{bmatrix} $$

Sometimes, decomposing result into a rational number greater than 1. This is something we need to avoid when exploding numbers. In this cases the remainder will be assigned to the exploded number.

To demonstrate it, lets continue working with our previous matrix. This time we will explode the number at position \$(0,0)\$

$$ N = \begin{bmatrix} \color{red}{10}&10&10\\10&1&10\\10&10&10 \end{bmatrix} $$

Here we have 3 neightbors and the number itself. Here the equation is something like \$10/4\$ which give us 2 for each and 2 as remainder.

$$ N = \begin{bmatrix} \color{blue}2+\color{red}{2}&\color{red}{10+2}&10\\\color{red}{10+2}&\color{red}{1+2}&10\\10&10&10 \end{bmatrix} $$

$$ N = \begin{bmatrix} \color{red}{4}&12&10\\12&3&10\\10&10&10 \end{bmatrix} $$

As well, sometimes a number wont be big enough to be decomposed in equal parts (where the abs is greater than 0) between his neighbors (|rational number| < 1). In this cases we need to "borrow" from the exploded number in order to maintain the "greater than 0" condition. Lets continue with our previous example and explode the number at position \$(1,1)\$.

$$ N = \begin{bmatrix} 4&12&10\\12&\color{red}3&10\\10&10&10 \end{bmatrix} $$

$$ N = \begin{bmatrix} 4+\color{red}1&12+\color{red}1&10+\color{red}1\\12+\color{red}1&\color{blue}0+\color{red}{1}-\color{green}6&10+\color{red}1\\10+\color{red}1&10+\color{red}1&10+\color{red}1 \end{bmatrix} $$ $$ N = \begin{bmatrix} 5&13&11\\13&\color{red}{-5}&11\\11&11&11 \end{bmatrix} $$


The challenge is, given a list of \$(x,y)\$ positions and an finite non-empty array of natural numbers, return the exploded form after each number from the positions list has been exploded.


Test cases

Input: initial matrix: [[3, 3, 3], [3, 3, 3], [3, 3, 3]], numbers: [[0,0],[0,1],[0,2]]

Output: [[1, 0, 1], [5, 6, 5], [3, 3, 3]]


Input: Initial matrix: [[9, 8, 7], [8, 9, 7], [8, 7, 9]], numbers: [[0,0],[1,1],[2,2]]

Output: [[4, 11, 8],[11, 5, 10],[9, 10, 4]]


Input: Initial matrix: [[0, 0], [0, 0]], numbers: [[0,0],[0,0],[0,0]]

Output: [[-9, 3],[3, 3]]


Input: Initial Matrix: [[10, 20, 30],[30, 20, 10],[40, 50, 60]], numbers: [[0,2],[2,0],[1,1],[1,0]]

Output: [[21, 38, 13], [9, 12, 21], [21, 71, 64]]


Input: Initial Matrix: [[1]], numbers: [[0,0]]

Output: [[1]]


Input: Initial Matrix: [[1, 2, 3]], numbers: [[0,0], [0, 1]]

Output: [[1, 1, 4]]


Notes

  • Input/Output rules apply

  • You can assume input matrix will never be empty

  • You can assume coordinates are always going to be valid

  • Input coord in test cases is given as (row, column). If you need it to be (x, y) you can swap the values. If so, please state that in your answer

\$\endgroup\$
5
  • \$\begingroup\$ new to code golf; what format is the sample allowed to take these matrices in? Any format that exists in the language? String form exactly as written? \$\endgroup\$
    – rtpax
    Feb 20, 2019 at 19:04
  • 1
    \$\begingroup\$ I suggest adding a test case for non-square matricies. \$\endgroup\$
    – Οurous
    Feb 20, 2019 at 21:15
  • \$\begingroup\$ @Ourous uh oh, I had been writing my program assuming they were guaranteed to be square, back to the drawing board I guess \$\endgroup\$
    – rtpax
    Feb 20, 2019 at 21:27
  • \$\begingroup\$ Can we assume the matrix-size is at least 2 by 2? Or can a 1 by 1 matrix be input as well? \$\endgroup\$ Feb 21, 2019 at 9:49
  • \$\begingroup\$ @rtpax Any format unless the question states otherwise, yes \$\endgroup\$
    – ASCII-only
    Feb 22, 2019 at 10:43

8 Answers 8

9
\$\begingroup\$

C(GCC) 220 216 214 212 bytes

credit to @ceilingcat for 2 bytes

#define L(v)for(int v=2;~v--;)
#define P l/C+r<0|l/C+r>=R|l%C+c<0|l%C+c>=C
f(int R,int C,int*m){for(int*i=m+R*C;~*i;) {int*M,l=*i+++C**i++,a=0,b;L(r)L(c)P?:++a;M=m+l;b=*M/a;b+=!b;*M- =b*a;L(r)L(c)M[r*C+c]+=P?0:b;}}

Run it here

a slightly less golfed version

#define L(v)for(int v=2;~v--;)
#define P l/C+r<0|l/C+r>=R|l%C+c<0|l%C+c>=C
f(int R, int C, int*m) {
    for(int*i=m+R*C;~*i;) {
        int*M,l=*i+++C**i++,a=0,b;
        L(r)
            L(c)
                P?:++a;
        M=m+l;
        b=*M/a;
        b+=!b;
        *M-=b*a;
        L(r)
            L(c)
                M[r*C+c]+=P?0:b;
    }
}

The calling code with an example

int main()
{
  int matrix[] = {3,3,3,3,3,3,3,3,3,0,0,0,1,0,2,-1};
  int rows = 3;
  int columns = 3;
  f(rows,columns,matrix);
  for(int r = 0; r < rows; ++r) {
    for(int c = 0; c < columns; ++c) {
      printf("%03d,",matrix[r*columns + c]);
    }
    printf("\n");
  }
}

and the output

001,005,003,
000,006,003,
001,005,003,
\$\endgroup\$
2
  • 11
    \$\begingroup\$ Welcome to PPCG :) \$\endgroup\$
    – Shaggy
    Feb 20, 2019 at 22:10
  • \$\begingroup\$ 198 bytes \$\endgroup\$
    – ceilingcat
    Apr 8, 2019 at 1:28
7
\$\begingroup\$

JavaScript (ES7),  126 125 123  121 bytes

Saved 2 bytes thanks to @Shaggy

Takes input as (matrix)(list). Outputs by modifying the matrix.

m=>a=>a.map(([Y,X])=>(g=n=>m[m.map((r,y)=>r.map((_,x)=>(x-X)**2+(y-Y)**2<3&&r[n++,x]++)),(m[Y][X]+=~n)<n||g``,Y][X]++)``)

Try it online!

How?

If we were to strictly follow the algorithm described in the challenge, we'd have to perform the following operations for each position pair \$(x,y)\$:

  1. walk through the matrix to compute the number of neighbors \$n\$
  2. compute \$\lfloor m(x,y) / n\rfloor\$ and deduce the quantity \$q\$ that needs to be added to each neighbor
  3. walk through the matrix again to update each neighbor
  4. update \$m(x,y)\$

Instead of that, we use a recursive function which executes a simpler flow of operations, repeated as many times as needed:

  1. for each neighbor and for the reference cell itself: increment the cell and increment a counter \$n\$ (initialized to \$0\$)
  2. subtract \$n+1\$ from the reference cell
  3. if the above result is greater than or equal to \$n\$, do a recursive call
  4. increment the reference cell (all steps of this kind are executed in succession when the last recursive call has completed)

The main benefit is that we only need one loop over the matrix. The second benefit is that we don't have to compute any quotient at all.

Example

$$M=\begin{pmatrix} 0&0&0\\ 0&26&0\\ 0&0&0 \end{pmatrix}\text{ and }(x,y)=(1,1)$$

After step 1 of the first iteration, we have:

$$M=\begin{pmatrix} 1&1&1\\ 1&27&1\\ 1&1&1 \end{pmatrix}\text{ and }n=9$$

And after step 2 of the first iteration:

$$M=\begin{pmatrix} 1&1&1\\ 1&17&1\\ 1&1&1 \end{pmatrix}$$

The key point here is that the reference cell is updated by taking only the cost (\$-9\$) into account without the gain (\$+1\$), so that we know how much we can still draw from it.

Consequently, the sum of the cells is no longer equal to \$26\$ at this point. But this will be corrected at the end of the process, where all gains on the reference cell are accounted at once.

Step 3 of the first iteration: because \$17\$ is greater than \$9\$, we do a recursive call.

After step 1 of the second iteration, we have:

$$M=\begin{pmatrix} 2&2&2\\ 2&18&2\\ 2&2&2 \end{pmatrix}\text{ and }n=9$$

And after step 2 of the second iteration:

$$M=\begin{pmatrix} 2&2&2\\ 2&8&2\\ 2&2&2 \end{pmatrix}$$

Step 3 of the second iteration: this time, we have \$8<9\$, so we stop there.

We now increment the reference cell twice (step 4 of both iterations), leading to the final result:

$$M=\begin{pmatrix} 2&2&2\\ 2&10&2\\ 2&2&2 \end{pmatrix}$$

Commented

m => a =>                     // m[] = input matrix, a[] = list of positions
  a.map(([Y, X]) => (         // for each pair (X, Y) in a[]:
    g = n =>                  //   g = recursive function expecting n = 0
      m[                      //
        m.map((r, y) =>       //     for each row r[] at position y in m[]:
          r.map((_, x) =>     //       for each value at position x in r[]:
            (x - X) ** 2 +    //         if the quadrance between (x, y)
            (y - Y) ** 2 < 3  //         and (X, Y) is less than 3:
            && r[n++, x]++    //           increment n and increment r[x]
          )                   //       end
        ),                    //     end
        (m[Y][X] += ~n)       //     subtract n + 1 from m[Y][X]
        < n                   //     if the result is greater than or equal to n:
        || g``,               //       do a recursive call
        Y                     //     
      ][X]++                  //     increment m[Y][X]
    )``                       //   initial call to g
  )                           // end
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save a couple of bytes by replacing both occurrences of (0) with 2 backticks. \$\endgroup\$
    – Shaggy
    Feb 21, 2019 at 10:18
6
\$\begingroup\$

R, 163 162 161 159 155 146 bytes

function(m,l){for(e in l){v=m[i<-e[1],j<-e[2]];s=m[x<--1:(i<dim(m))+i,y<--1:(j<ncol(m))+j];z=sum(1|s);d=max(1,v%/%z);m[x,y]=s+d;m[i,j]=v+d-d*z};m}

Try it online!

Explanation

(Corresponds to a previous version of the code)

function(m,l) {          # Take input as matrix m and 1-indexed list of explosion points l
  for(e in l) {          # Loop over the list of explosion points
    i=e[1]; j=e[2]       # Assign current coordinates to (i,j) for brevity
    x=-1:1+i             # Assign the ranges of neighboring cells: (i-1) to (i+1),
    y=-1:1+j             # and (j-1) to (j+1)
    s=                   # Take the submatrix s=m[x,y]
      m[x<-x[x<=dim(m)]  # But first trim x and y from above to prevent out of bounds errors,
     ,y<-y[y<=ncol(m)]]  # trimming from below isn't necessary, as R tolerates index 0
    z=sum(1|s)           # Count the neighbors
    d=max(1,m[i,j]%/%z)  # Estimate, how much we'll distribute to each neighbor
    m[x,y]=s+d           # Add the distributed amount to each cell of the submatrix
    m[i,j]=m[i,j]-d*z    # Subtract the total amount from the exploded cell
  }
  m                      # Return the modified matrix
}
\$\endgroup\$
4
\$\begingroup\$

Clean, 181 167 bytes

import StdEnv;

foldl\m(x,y)={{if(d>2)0b+e-if(d>0)0b*n\\e<-:l&v<-[0..],let{b=max m.[y,x]n/n;$a b=2+sign a-(a+1)/size b;n= $x l* $y m;d=(v-x)^2+(u-y)^2}}\\l<-:m&u<-[0..]}

Try it online!

In the form of a partially-applied function literal.

Expanded (first version):

f // functinon f on {{Int}} and [(Int,Int)]
    = foldl \m (x, y) // fold :: (a -> b -> a) a [b] -> a with first argument \ {{Int}} (Int,Int) -> {{Int}} giving \ {{Int}} [(Int,Int)] -> {{Int}}
        = {                     // an array of
            {                   // arrays of
                if(d > 2) 0 b   // the amount we give to the neighbors
                + e             // plus the current entry
                - if(d > 0) 0 b // minus the amount taken from the target entry
                * n             // times the number of neighbors, if we're on the target
            \\                  // for each
                e <-: l         // element of row l
                & v <- [0..]    // and x-index v
                , let           // local definitions:
                    b           // the amount given to the neighbors
                        = max   // we need at least 1 each, so take the largest of
                            m.[y, x] // the target entry
                            n   // or the number of neighbors
                        / n     // divide it by the number of neighbors
                    n           // the number of neighbors
                        = (     // sum of
                            1   // one
                            + s x // if x is at the left edge = 0 else 1
                            + s ( // if x is at the right edge = 0 else 1
                                size l
                                - x 
                                - 1
                            )
                        ) * (   // times the sum of
                            1   // one
                            + s y // if y is at the top edge = 0 else 1
                            + s ( // if y is at the bottom edge = 0 else 1
                                size m
                                - y
                                - 1
                            )
                        )
                    d           // distance from the target point
                        = (v - x)^2
                        + (u - y)^2
            }
        \\                      // for each
            l <-: m             // row l in matrix m
            & u <- [0..]        // and y-index u
        }
\$\endgroup\$
4
\$\begingroup\$

Rust - 295 bytes

fn explode(p:(i8,i8),v:&mut Vec<Vec<i8>>){let x=v[p.0 as usize][p.1 as usize];let q=|x,y|x*x+y*y;loop{let mut t=0;for i in 0..v.len(){for j in 0..v[i].len(){if q(i as i8-p.0,j as i8-p.1)<3{v[i][j]+=1;v[p.0 as usize][p.1 as usize]-=1;t+=1;}}}if v[p.0 as usize][p.1 as usize]<=(x/t+x%t){break;}}}

This is pretty long due to Rust requiring unsigned integer indexing of vectors, but requiring signed integers to do subtraction resulting in negatives. However I believe my algorithm is the "shortest algorithm" so far. There is actually no need to deal with detecting edges, bottom, etc.

Notice three things: One, the sum of all cells is always constant. Two, this is a division / remainder situation, so we can apply Bresenham-algorithm style thinking. Three, the question always adds the same number to all cells within a certain distance of the special position cell, before dealing with the "extra" stuff in the special position.

Algorithm:

Store original value of cell at position P into M.

Begin Loop:

Iterate over each cell I in the matrix. If the position of cell I is within 3 Quadrance (squared distance) of the position P, then subtract 1 from cell P and add 1 to the cell I. Count how many times this is done in one iteration through the matrix.

If the value leftover in the cell at position P is less than or equal to M / Count + M modulo Count, then break the loop. Otherwise perform the loop again.

The resulting matrix will be the exploded version. Count is basically a way to count neighbors without dealing with edges. Looping is a way to break down the division/addition stuff into a repeated single addition/subtraction of one. The modulo check ensures we will have appropriate remainder left at position P to deal with 'explosions' that are not evenly divisible amongst neighbors. The do/while loop structure allows P<0 to work properly.

Ungolfed version on the Rust Playground

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Such a long function name isn't necessary, any 1-byter such as f would do. But you could probably save even more bytes, by using an anonymous function: |p:(i8,i8),v:&mut Vec<Vec<i8>>|{...} \$\endgroup\$
    – Kirill L.
    Feb 21, 2019 at 13:45
3
\$\begingroup\$

Java 10, 194 193 191 190 184 182 171 bytes

M->C->{for(var q:C){int n,X=q[0],Y=q[1],x,y,c=0;do{c++;x=n=0;for(var r:M){y=0;for(int $:r)r[y]+=Math.hypot(x-X,y++-Y)<2?++n/n:0;x++;}}while((M[X][Y]+=~n)>=n);M[X][Y]+=c;}}

Iterative port of @Arnauld's JavaScript answer.
-17 bytes thanks to @Arnauld.

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

Try it online.

Explanation:

M->C->{                      // Method with two integer-matrix parameters and no return-type
  for(var q:C){              //  Loop over the coordinates:
    int n,                   //   Count integer
        X=q[0],Y=q[1],       //   The current X,Y coordinate
        x,y,                 //   Temp x,y coordinates
        c=0;                 //   Counter, starting at 0
    do{                      //   Do-while:
      c++;                   //    Increase the counter `c` by 1
      x=n=0;                 //    (Re)set both `x` and the count `n` to 0
      for(var r:M)           //    Loop over the rows `r`:
        y=0;                 //     (Re)set `y` to 0
        for(int $:r)         //     Loop over the cells of the current row:
          r[y]+=             //      Increase the value at x,y by:
            Math.hypot(      //       If the hypot (builtin for `sqrt(a*a, b*b)`) of:
              x-X,           //        the difference between `x` and `X`,
                  y++-Y)     //        and difference between `y` and `Y`
                             //        (and increase `y` by 1 afterwards with `y++`)
              <2?            //       Is smaller than 2:
                 ++n/n       //        Increase count `n` and the value at x,y both by 1
                :            //       Else:
                 0;          //        Leave the value at x,y the same by increasing by 0
       x++;}}                //     Increase `x` by 1
    while((M[X][Y]+=~n)      //    Decrease the value at X,Y by n+1
          >=n);              //    Continue the do-while if this new value is still larger
                             //    than or equal to count `n`
    M[X][Y]+=c;}}            //   Increase the value at X,Y with counter `c`
\$\endgroup\$
4
  • 1
    \$\begingroup\$ m[y] with \$y\$ out of bounds is OK in JS (yielding undefined), but m[y][x] with \$y\$ out of bounds would crash as well. \$\endgroup\$
    – Arnauld
    Feb 21, 2019 at 12:14
  • \$\begingroup\$ @Arnauld Ah ok. I indeed remembered out of bounds usually isn't an issue in JS, but I can understand why undefined[x] would fail. Anyway, your (x-X)**2+(y-Y)**2<3 check is pretty smart. Need to remember that when I ever want to check values in a matrix in a 3x3 block (and within bounds) around it. I think I actually have a few answers like that, where I now use a try-catch, and in one case try-finally.. Will look at those when I have some time. \$\endgroup\$ Feb 21, 2019 at 12:22
  • 1
    \$\begingroup\$ 171 bytes with enhanced for loops. \$\endgroup\$
    – Arnauld
    Feb 22, 2019 at 10:22
  • \$\begingroup\$ @Arnauld Oh nice. Now that I see it I cannot believe I hadn't thought about that when I created a port from your answer, since you do the same.. >.> ;) \$\endgroup\$ Feb 22, 2019 at 11:39
2
\$\begingroup\$

Common Lisp, 498 bytes

(defmacro s(l c x)`(incf(aref m,l,c),x))
(defmacro w(a &rest f)`(if(,a(or(= l 0)(= l(d 0)))(or(= c 0)(= c(d 1)))),@f))
(defmacro d(n)`(1-(array-dimension m,n)))
(defmacro p(i l m &rest f)`(loop for,i from(1-,l)to(1+,l)when(and(>=,i 0)(<=,i,m))do,@f))
(defmacro g()`(or(p i l(d 0)(p j c(d 1)(s i j 1)))(s l c(- v))))
(defun f(m l c)(let((v(w and 4(w or 6 9))))(if (<(/(s l c 0)v)1)(g)(loop for i to(1-(/(s l c 0)v))do(g)))))
(defun c(m n)(dotimes(i(length n))(f m(nth 0(nth i n))(nth 1(nth i n))))m)

Try it online!

Use this function as (print (c #2A((3 3 3) (3 3 3) (3 3 3)) '((0 0)(0 1)(0 2))))

Better readable version:

(defmacro s (l c x)
  `(incf (aref m ,l ,c) ,x))

(defmacro w (a &rest f)
  `(if (,a (or (= l 0)
           (= l (d 0)))
       (or (= c 0)
           (= c (d 1))))
       ,@f))

(defmacro d (n)
  `(1- (array-dimension m ,n)))

(defmacro p (i l m &rest f)
  `(loop for ,i from (1- ,l) to (1+ ,l)
     when (and (>= ,i 0) (<= ,i ,m))
     do ,@f))

(defmacro g ()
  `(or(p i l (d 0)
     (p j c (d 1)
        (s i j 1)))
      (s l c (- v))))

(defun f (m l c)
  (let ((v (w and 4 (w or 6 9))))
    (if (< (/ (s l c 0) v) 1)
    (g)
      (loop for i to (1- (/ (s l c 0) v))
        do (g)))))

(defun c (m n)
  (dotimes (i (length n))
    (f m (nth 0 (nth i n))
       (nth 1 (nth i n))))
  m)

Output example:

(print (c #2A((3 3 3) (3 3 3) (3 3 3) (3 3 3) (3 3 3) (3 3 3)) '((5 0)(4 1)(0 2))))
;; #2A((3 4 0) (3 4 4) (3 3 3) (4 4 4) (5 -4 4) (1 5 4))

(print (c #2A((3 3 3) (3 3 3) (3 3 3)) '((0 0)(0 1)(0 2))))
; #2A((1 0 1) (5 6 5) (3 3 3))  => #2A((1 0 1) (5 6 5) (3 3 3))

(print (c #2A((9 8 7) (8 9 7) (8 7 9)) '((0 0)(1 1)(2 2))))
;; #2A((4 11 8) (11 5 10) (9 10 4))  => #2A((4 11 8) (11 5 10) (9 10 4))

(print (c #2A((0 0) (0 0)) '((0 0)(0 0)(0 0))))
;; #2A((-9 3) (3 3))  => #2A((-9 3) (3 3))

(print (c #2A((10 20 30)(30 20 10)(40 50 60)) '((0 2)(2 0)(1 1)(1 0))))
;; #2A((21 38 13) (9 12 21) (21 71 64))  => #2A((21 38 13) (9 12 21) (21 71 64))
\$\endgroup\$
2
\$\begingroup\$

Python 2, 171 bytes

M,p=input()
l=len
for i,j in p:
 y=[(i+y,j+x)for x in-1,0,1for y in-1,0,1if l(M)>j+x>-1<i+y<l(M[0])];x=max(M[i][j]/l(y),1);M[i][j]-=x*l(y)
 for i,j in y:M[i][j]+=x
print M

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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