19
\$\begingroup\$

This challenge is about creating these neat "green spray paint" patterns: (more pictures below)

example 1 example 2 example 3 example 7

Loosely explained, they are generated by starting with a black image and a point in the center. That point is successively moved by a randomly chosen offset or delta in x and y. Every pixel the point visits has 1 added to its green color channel. This process is then repeated with many many more points, all starting from the center, generating an entire green pattern.

Your task is to write the shortest program possible that takes in the necessary parameters and displays or outputs the resulting green spray paint image. This is code golf so the shortest code in bytes wins!

Specifics

The images require the following parameters, which must be inputs to your program in any order you choose:

  • Positive integer S is the width and height (Size) of the output image in pixels.

  • Non-negative integer N is the number of points to move over the image one by one, each adding a trail of green.

  • Non-negative integer M is the maximum number of moves that each point can take. (Without this they'd never stop.)

  • D is a list of pairs of integers [(dx1, dy1), (dx2, dy2), ...] that are deltas each point may be offset by each move.

    • You may also take this flattened [dx1, dy1, dx2, dy2, ...] or as two lists [dx1, dx2, ...] and [dy1, dy2, ...].

Generate the patterns by starting with a pure black S×S pixel image. Then repeat the following process N times, after which your image will be ready to be output:

  1. Start a point in the center of the image. (This means (floor(S/2), floor(S/2)) for most image coordinate systems.)
  2. Add 1 to the green color channel of the pixel currently below the point (up to a max of 255).
  3. Consider moving the point by each of the deltas in D so it becomes like (x + dx, y + dy). Keep track of the valid moves.
    • A valid move is one that keeps the point inside the bounds of the image, i.e. over a pixel.
  4. If there are no valid moves or the current point has taken M moves then stop and restart at step 1 with a new point.
  5. Otherwise, have the current point take a random valid move. Every valid move should have an equal chance.
  6. Go to step 2 to move the current point again.

Your implementation does not need to follow these precise steps as long as the results produced are the same. Of course they won't be exactly the same due to randomness, but it's easy to visually tell when things are working as expected.

Be sure to keep these corner cases in mind:

  • When N is 0 there are no points so the output should always be a totally black S×S image.

  • When M is 0 or D is empty it means no moves can be made, so only the starting pixel will have color. (See example 5.)

  • D may contain duplicate values that are valid moves, effectively meaning that move is more likely. (See example 7.)

Reference Program

Ungolfed reference code in Python 3. Not strictly a solution since it is hardcoded to output the first example from above.

S = 250
N = 800
M = 7000
D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)] # chess knight moves

import random
from PIL import Image
img = Image.new('RGB', (S, S), 'black')
pix = img.load()
for i in range(N):
    if (i + 1) % 10 == 0: print(f'{(i + 1)/N:.1%}') # progress tracker, not required output
    x, y, = S//2, S//2
    m = 0
    while True:
        pix[x, y] = 0, pix[x, y][1] + 1, 0
        valid = [(x + dx, y + dy) for dx, dy in D if 0 <= x + dx < S and 0 <= y + dy < S]
        if m >= M or not valid: break
        x, y = random.choice(valid)
        m += 1
#img.save('spraypaint.png') # uncomment to save image
img.show()

Examples

  1. S = 250
    N = 800
    M = 7000
    D = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]
    
    example 1 (from above)
  2. S = 250
    N = 1000
    M = 3000
    D = [(2, -1), (-2, -1), (-3, 0), (4, 0), (0, 2), (0, -1)]
    
    example 2 (from above)
  3. S = 250
    N = 400
    M = 10000
    D = [(60, 59), (60, -59), (-59, 60), (-59, -60)]
    

    example 3 (from above)

  4. S = 400
    N = 600
    M = 10000
    D = [(0, 1), (-1, 0), (0, -1), (1, 0)]
    

    example 4

  5. S = 51
    N = 1000
    M = 1000
    D = []
    
    example 5
  6. S = 51
    N = 1000
    M = 1
    D = [(-5, 5), (9, 9), (-15, 1), (20, -25)]
    
    example 6
  7. S = 300
    N = 1000
    M = 1000
    D = [(1, 0), (1, 0), (1, 0), (1, 0), (-3, 0), (0, 3), (0, -3)]
    
    example 7 (from above)
  8. S = 345
    N = 123
    M = 21212
    D = [(1, -4), (2, -3), (3, -2), (4, -1), (-9, 9)]
    
    example 8
  9. S = 200
    N = 1
    M = 1500000
    D = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
    
    example 9
  10. S = 300
    N = 4000
    M = 1000
    D = [(7, 1), (-4, 3), (-4, -3)]
    
    example 10
  11. S = 300
    N = 1500
    M = 1000
    D = [(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)]
    
    example 11
  12. S = 240
    N = 1000
    M = 10000
    D = [(80, 81), (80, -81), (-81, 80), (-81, -80)]
    
    example 12

All example inputs together.

Bonus

This isn't required but I would love to see what other neat patterns are possible. Put any cool images you make in your answer!

\$\endgroup\$
18
  • \$\begingroup\$ Well this is annoying. The top 3 example images fit on one line in the question submitter form but not in the published question... \$\endgroup\$ Apr 17, 2020 at 10:17
  • 2
    \$\begingroup\$ I have that problem with answers; I try to fit each part of an explanation in a certain width only to find that the actual width is less. \$\endgroup\$
    – Neil
    Apr 17, 2020 at 10:20
  • \$\begingroup\$ Well, fixed mostly. But yeah, now a bunch of my nicely formatted single lines take up two lines :( \$\endgroup\$ Apr 17, 2020 at 10:31
  • \$\begingroup\$ @Neil Yeah, I always have the same issue. I always end up editing the lines again after I posted my answer. After you've posted a first version and edit it later on, the preview is working fine though, which is weird imo.. It's only before you post the actual answer it's fwcked up.. :/ \$\endgroup\$ Apr 17, 2020 at 10:53
  • \$\begingroup\$ If a pixel is already 0x00FF00 (the maximum green color) and the point travels to it, what happens? Does it become 0x010000 (tiny bit of red) or 0x000000 (black)? \$\endgroup\$
    – PkmnQ
    Apr 17, 2020 at 11:36

5 Answers 5

6
\$\begingroup\$

Ruby, 263...150 147 bytes

->s,n,m,d{c=[0]*3*s*s;n.times{x=y=s/2;0.upto(m){c[3.*x+y*s]+=1;d.shuffle.find{|p,q|(g=x+p,y+q)-[*0...s]==[]&&(x,y=g)}||break}};puts:P3,s,s,255,0,c}

Try it online! (Times out on four of the test cases and truncates output for all but two of the others.)

Explanation

Takes d as an array of arrays and outputs in PPM format to STDOUT. Two features of PPM are exploited:

  1. No attempt is made to avoid G values greater than 255: PPM treats any such values as if they were equal to 255.
  2. Extraneous bytes at the end of the file (i.e. beyond the specified pixel count) are ignored. This allows a byte to be saved by working internally with the red channel rather than green, then shifting all the RGB values by one place on output.
->s,n,m,d{
  c=[0]*3*s*s;         # initialise all pixels to black
  n.times{
    x=y=s/2;           # set initial position
    0.upto(m){
      c[3.*x+y*s]+=1;  # add 1 to red channel at current position (x+y*s is single-digit pixel index, starting from 0 at top left)
      d.shuffle        # randomise moves
       .find{|p,q|     # if there is a move such that
         (g=x+p,y+q)   # the new co-ordinates
         -[*0...s]==[] # are both in [0, s) (i.e. within the image)
         &&(x,y=g)     # take that move
       }            
      ||break          # otherwise restart with a new point
    }
  };
  puts:P3,s,s,255,0,c  # print PPM file to STDOUT, inserting 0 to get green output
}

Sample outputs for test cases

Composite image including all test cases, ordered as follows:

1, 2, 3
4, 8
5, 6, 7, 9
10, 11, 12

enter image description here

Bonus

'Excalibur'
S = 400, N = 5000, M = 5000, D = [[1, -1], [1, -1], [-2, 10], [-10, 2]]

'Aurora'
S = 400, N = 2500, M = 2500, D = [[11, 13], [13, -11], [-29, 31], [31, 29], [41, 43], [43, -41], [-59, 61], [-59, -61]]

enter image description here

\$\endgroup\$
5
\$\begingroup\$

Java 10, 516 513 508 504 bytes

import java.awt.*;(S,N,M,D)->new Frame(){{add(new Panel(){public void paint(Graphics g){var G=(Graphics2D)g;G.setPaint(Color.BLACK);G.fillRect(0,0,S,S);int c[][]=new int[S][S],x,y,d[],r,n=N,m;for(;n-->0;)for(x=y=S/2,m=M;m-->0;){c[x][y]++;var L=new java.util.Stack<int[]>();for(var q:D)if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)L.add(q);r=L.size();if(r<1)break;d=L.get(r*=Math.random());x+=d[0];y+=d[1];}for(x=S*S;x-->0;G.drawLine(x,y,x,y))G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});show();}}

-4 bytes thanks to @ceilingcat.

Some example outputs:

Input: S=250; N=800; M=7000; D=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]
Output:
enter image description here

Input: S=200; N=10000; M=5000; D=[[1,1],[2,2],[30,30],[1,-1],[2,-2],[30,-30],[-1,1],[-2,2],[-30,30]]
Output:
enter image description here

Input: S=200, N=5000, M=5000, D=[[10,11],[11,10],[25,26],[26,25],[50,51],[51,50],[-75,-75]]
Output:
enter image description here

Explanation:

import java.awt.*;            // Required import for almost everything
(S,N,M,D)->                   // Method with the 4 parameters and Frame return-type
  new Frame(){                //  Create the Frame
   {                          //   In an inner code-block:
     add(new Panel(){         //    Add a Panel we can draw on:
       public void paint(Graphics g){
                              //     Overwrite its paint method:
         var G=(Graphics2D)g; //      Cast interface to object so we can use it to draw
         G.setPaint(Color.BLACK);
                              //      Set the color to black
         G.fillRect(0,0,S,S); //      Create the square of size `S` by `S`
         int c[][]=new int[S][S],
                              //      Create an integer-matrix of the same size,
                              //      filled with 0s by default
             x,y,             //      Temp integers for the current coordinates
             d[],             //      Temp integer-array for the randomly selected delta
             r,               //      Temp integer for the random index
             n=N,             //      Copy of the input `N` (since we are in a
                              //      code-block, it has to be effectively final..)
             m;               //      Temp integer
         for(;n-->0;)         //      Loop `n` amount of times:
           for(x=y=S/2,       //       Start `x,y` at the center
               m=M;m-->0;){   //       Inner loop `M` amount of times:
             c[x][y]++;       //        Increase the value at the current `x,y` by 1
             var L=new java.util.Stack<int[]>(); 
                              //        Create an empty list
             for(var q:D)     //        Loop over the deltas:
               if(q[0]>~x&x+q[0]<S&q[1]>~y&y+q[1]<S)
                              //         If `x,y` + this delta is within bounds:
                 L.add(q);    //          Add the current delta to the list
             r=L.size();      //        Set `r` to the amount of valid deltas left
             if(r<1)          //        If there are no valid deltas:
               break;         //         Stop the inner loop
             d=L.get(r*=Math.random());
                              //        Pick a random delta from the list
             x+=d[0];y+=d[1];}//        And update the `x,y` coordinate with it
         for(x=S*S;x-->0      //      Then loop over all coordinates:
             ;                //        After every iteration:
              G.drawLine(r,y,r,y))
                              //         Draw the current pixel
           G.setPaint(new Color(0,Math.min(c[r=x/S][y=x%S],255),0));}});
                              //       Set the green color based on the value in `c`,
                              //       or 255 if it's exceeding that
     show();}}                //    And finally show the Frame
\$\endgroup\$
0
2
\$\begingroup\$

Wolfram Language (Mathematica), 216 bytes

(s=Table[{0,0,0}~Table~S,S=#];t=1;Do[s[[##&@@(d=Floor[{S/2,S/2}])]]={0,t++,0};Do[s[[##&@@(c=RandomChoice[If[(z=Select[d+#&/@If[#4=={},{0,0},#4],Max@#<S-1&&Min@#>1&])=={},d,z]])]]+={0,1,0};d=c,#3],#2];s~Image~"Byte")&

[400, 600, 10000, {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}]

enter image description here

[1000, 2000, 2000, {{5, 5}, {2, 3}, {1, -1}, {-3, -4}, {4, 5}, {-5, -5}}]

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ I think it will be shorter to use an array first and then turn it into an image later. \$\endgroup\$ Apr 17, 2020 at 16:01
  • \$\begingroup\$ @mypronounismonicareinstate might try that later \$\endgroup\$
    – ZaMoC
    Apr 17, 2020 at 16:26
2
\$\begingroup\$

JavaScript (ES6), 279 269 bytes

f=
(c,s,n,m,d)=>{c.width=c.height=s
c=c.getContext('2d',{alpha:0})
i=c.getImageData(0,0,s,s)
for(;x=y=s/2|0,n--;)for(o=m;i.data[(x+y*s)*4+1]++,l=o--&&(e=d.map(([a,b])=>[x+a,y+b]).filter(([a,b])=>a>=0&b>=0&a<s&b<s)).length;)[x,y]=e[l*Math.random()|0]
c.putImageData(i,0,0)}
Size: <input id=s type=number min=1 value=250><br>Pixels: <input id=n type=number min=0 value=800><br>Moves: <input id=m type=number min=0 value=7000><br>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]><br><input type=button value=Go! onclick=f(c,+s.value,+n.value,+m.value,JSON.parse(d.value))><br><canvas id=c>

Takes a fifth parameter which is the canvas element on which to draw the resulting image. Byte count does not include the test driver, which comprises the f= line of JavaScript and all of the HTML. Edit: Saved 10 bytes thanks to @Kaiido. Ungolfed version with incremental rendering:

b.onclick = async function() {
  b.disabled = true;
  try {
    await f(c, +s.value, +n.value, +m.value, JSON.parse(d.value));
  } catch (ex) {
    console.error(ex);
  }
  b.disabled = false;
}
async function f(canvas, size, number, moves, deltas) {
  canvas.width = canvas.height = size;
  let context = canvas.getContext('2d', { alpha: false });
  context.fillRect(0, 0, size, size);
  let image = context.getImageData(0, 0, size, size);
  for (let i = 0; i < number; i++) {
    let x = size / 2 | 0, y = x, j = moves;
    for (;;) {
      image.data[(x + y * size) * 4 + 1]++;
      if (!j--) break;
      let valid = deltas.map(([dx, dy]) => [x + dx, y + dy]).filter(([x, y]) => x >= 0 && y >= 0 && x < size && y < size);
      if (!valid.length) break;
      [x, y] = valid[valid.length * Math.random() | 0];
    }
    context.putImageData(image, 0, 0);
    await new Promise(requestAnimationFrame);
  }
}
<div>Size: <input id=s type=number min=1 value=250></div>
<div>Pixels: <input id=n type=number min=0 value=800></div>
<div>Moves: <input id=m type=number min=0 value=7000></div>
<div>Deltas: <input id=d value=[[1,2],[-1,2],[1,-2],[-1,-2],[2,1],[-2,1],[2,-1],[-2,-1]]></div>
<div><input id=b type=button value=Go!></div>
<canvas id=c>

\$\endgroup\$
5
  • \$\begingroup\$ You can get rid of c.fillRect(0,0,s,s) if you pass ,{alpha:0} to the c.getContext('2d') call. \$\endgroup\$
    – Kaiido
    Apr 18, 2020 at 1:53
  • \$\begingroup\$ @Kaiido Thanks, I don't know the Canvas API at all well, so I had not heard of that parameter. \$\endgroup\$
    – Neil
    Apr 18, 2020 at 9:59
  • \$\begingroup\$ Ooh, the incremental rendering is a great idea! \$\endgroup\$ Apr 18, 2020 at 19:15
  • \$\begingroup\$ what does this part do? for (;;)? \$\endgroup\$
    – Ryan Stone
    Nov 5, 2020 at 20:40
  • \$\begingroup\$ @RyanStone That's just an infinite loop, excepting of course the break statements that terminate it. I thought it was clearer to use that in the ungolfed version. \$\endgroup\$
    – Neil
    Nov 5, 2020 at 22:17
1
\$\begingroup\$

Python 2 + PIL, 217 214 211 bytes

A golf of the reference implementation, but a lot less efficient. Instead of using loops, this generates many many lines of code (N*(M+2)) that will run once.

import random,PIL.Image as I
S,N,M,D=input()
i=I.new('RGB',(S,S))
p=i.load()
exec('v=[[S//2]*2]\n'+'if v:x,y=random.choice(v);p[x,y]=0,p[x,y][1]+1,0;v=[(x+a,y+b)for a,b in D if-1<x+a<S>y+b>=0]\n'*-~M)*N
i.show()

Output for S=51, N=1000, M=1, D=[(-5, 5), (9, 9), (-15, 1), (20, -25)]:

enter image description here

Output of an older version for S=300, N=1500, M=1000, D=[(10, -10), (-10, 10), (5, 5), (-5, -5), (1, 0), (-1, 0)], don't try such a large example with the current version:

enter image description here

\$\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.