title: MS Paint is underrated

text:
# Question
Title: MS Paint is underrated
MS Paint was always a great time waster, but it was shunned by most graphic designers. Perhaps people lost interest because of the jarring color palette, or because of limited undo levels. Regardless, it's still possible to generate beautiful images with just the standard brush and default color palette.

## Challenge

Using only the default brush (a 4x4 square with no corners) and the default color palette (the 28 colors below), attempt to replicate a source image using a technique based on stochastic hill climbing.

## Algorithm

Every answer must follow the same basic algorithm (stochastic hillclimb). Details can be tweaked within each step. A *movement* is considered to be a stroke of the brush (ie. clicking in paint).

1. **Guess next movement(s).** Make a guess (of coordinates and colors) for the next movement(s) however you'd like. However the guess must not reference the source image.
2. **Apply the guess.** Apply the brush to the painting to make the movement(s).
3. **Measure the benefit of movement(s).** By referencing the source image, determine whether the movement(s) benefited the painting (ie. the painting more closely resembles the source image). If it is beneficial, keep the movement(s), otherwise discard the movement(s).
4. **Repeat until convergence.** Go to Step 1 and try the next guess until the algorithm has converged sufficiently. The painting should heavily resemble the source image at this point.

**If your program does not match these four steps, it is probably not a stochastic hillclimb.** I have tagged this as a popularity contest because the goal is to produce interesting painting algorithms based on the limited color palette and brush.

## Contraints

* **The algorithm should be stochastic in some way.**
* **The next guess should not be influenced by the source image. You are guessing each new movement, and then checking to see if it helped or not.** For example, you are not allowed to determine where to place the brush based on the source image colors (that is similar to dithering the source image, which is not the goal).
* You are allowed to influence the placement by tweaking the steps of the algorithm however you'd like. For example, you could start your guesses at the edges and move inwards, drag the brush to create lines for each guess, or decide to paint dark colors first. You are allowed to reference previous iteration images (but not the source image) in order to calculate the next desired movement. These can be restrictive as you'd like (ie. only make guesses within the top-left quadrant for the current iteration).
* The measure of "difference" between the source image and the current iteration can be measured however you'd like, **as long as it does not calculate other potential movements to determine whether this movement is considered to be the "best".** It shouldn't know whether the current movement is the "best", only whether it fits within the tolerance of the acceptance criteria. For example, it can be as simple as `abs(src.R - current.R) + abs(src.G - current.G) + abs(src.B - current.B)` for each affected pixel, or any of the well-known color difference techniques.

## Palette

You can download the palette as a 28x1 image or create it directly in the code.

## Brush

The brush is a 4x4 square without corners. This is a scaled version of it:

(Your code must use the 4x4 version)

## Example

Input:

Output:

You can see how the basic algorithm progresses in a short video I made (each frame is 500 iterations): The Starry Night. The initial stages are interesting to watch:

# Answer
> 36 votes
# JavaScript

This solution uses the HTML5 canvas element to extract the image data, but without the need to use HTML, that means it can be run in your console. It access the color palette image as an array; I stored all the colors from the palette image in an array). It outputs to the console (after it finishes) and also stores the result in a variable.

**The most updated version of the code is in the fiddle**. The fiddle also uses a better algorithm to reduce noise in the pictures. The improvement in the algorithm is mostly fixing a function (max to min) which caused the inverse color to be chosen.

Code in the shape of the MS Paint Icon! (formatted code in fiddle or Stack Snippet)

```
eval(`                                                   function
                                                        Paint(t){fun
                                                         ction n(t){va
                                                         r n=t.toString(
                                                         16);return 1==n.
                                                         length?"0"+n:n}fu
                                                         nction e(t){return
                                                         "#"+n(t[0])+n(t[1]
                                                          )+n(t[2])}var a=ne
                                                          w Image,i=document.
                                                          createElement("canv
                                                          as"),h=null,o=docum
                                                          ent.createElement(
                                    "canvas"),r=          o.getContext("2d
                               ")     ,l=[],u=this,c      =[[0,0,0],[255
                            ,2       55,255],[ 192,192,   192],[128,12
                          8     ,128],[126,3,8],[252,13,27] ,[255,25
                       3,    56],[128,127,23],[15,127,18],[ 41,253
                      ,    46],[45,255,254],[17,128,127],[2 ,12,1
                    2    6],[ 11,36,2 51],[252,40,252],[12 7,15,1
                  2    6],[  128,127 ,68],[255,253,136],[4 2,253,
                 1   33],   [4,64,64],[23 ,131,251],[133,255,254],
               [    129   ,132,252],[6,6 6,126],[127,37,2 51],[127,
              6   4,1    3],[253,128,73],[252,22,129]];a.crossOrigin
             =   "",   a.src=t,this.done=this.done||function(){},a.o
            n   load=function(){function t(t){var n=0,e=0,a=0;return
           t  .forEach(function(t){n+=t[0],e+=t[1],a+=t[2]}),[n/t.leng
          t  h,e /t.length,a/t.length]}function n(t){for(var n=[],e=0;e
         <  t.l  ength;e+=1)n.push(t[e]);return n}function g(t,n){retur
        n  (Ma  th.abs(t[0]-n[0])/255+Math.abs(t[1]-n[1])/255+Math.abs(t
       [  2]- n[2])/255)/3}function f(t,n){for(var e=Math.floor(Math.ran
          do m()*n.length),a=n[e],i=(g(t,a),1-.8),h=56,o=[];o.length<=h&
         &g (t,a)>i;)if(o.push(a),a=n[Math.floor(Math.random()*n.length)]
     ,  o.length==h){var r=o.map(function(n){return g(t,n)});a=o[r.indexO
       f(Math.max.apply(Math,r))],o.push(a)}return a}function s(t,n){for(
    v  ar e=[];t.length>0;)e.push(t.splice(0,n).slice(0,-1));return e}i.w
   i  dth=a.width,i.height=2*a.height,h=i.getContext("2d"),h.drawImage(a,0
   ,0,a.width,a.height);for(var d=(function(t){reduce=t.map(function(t){re
  turn(t[ 0]+t[1]+t[2])/3})}(c),0),m=0,v=i.width*i.height/4,p=0;v>p;p+=1)d
  >2*Mat h.ceil(a.width/2)&&(d=0,m+=1),l.push(f(t(s(n(h.getImageData(2*d,2
  *m,4,4).data),4)),c)),d+=1;o.width=i.width,o.height=i.height;for(var d=0
 ,m=0,v=i.width*i.height/4,p=0;v>p;p+=1)d>2*Math.ceil(a.width/2)&&(d=0,m+=
 1),console.log("Filling point ("+d+", "+m+") : "+e(l[p])),r.fillStyle=e(l
 [p]),r.fillRect(2*d+1,2*m,2,1)  ,r.fillRect(2*d,2*m+1,4,2),r.fillRect(2*d
+1,2*m+3,2,1),d+=1;u.result=o      .toDataURL("image/png"),u.resultCanvas
=o,u.imageCanvas=i,u.image=a       ,u.done(),console.log(u.result)},a.one
rror=function(t){console.log       ("The image failed to load. "+t)}}/*..
............................       ......................................
. ..........................       .....................................
............................      ......................................
.............................    .......................................
.......................................................................
.......................................................................
..................  ..................................................
................     .................................................
..............       ................................................
.............       ................................................
...........        .................................................
 .........         ................................................
 .......          ................................................
  ....           ................................................
                ................................................
                ...............................................
               ...............................................
              ..............................................
              .............................................
             ............................................
             ..........................................
              .......................................
              .....................................
               .................................
                .............................
                  ......................
                                   .....
                                  .....
                                  .....
                                  ....
                                   */`
.replace(/\n/g,''))

```

Usage:

```
Paint('DATA URI');

```

# Fiddle.

The fiddle uses crossorigin.me so you don't need to worry about cross-origin-resource-sharing.

I've also updated the fiddle so you can adjust some values to produce the best-looking painting. Some pictures' colors might be off, to avoid this, adjust the accept\_rate to adjust the algorithm. A lower number means better gradients, a higher number will result in sharper colors.

---

Here's the fiddle as a Stack-Snippet (NOT updated, in case the fiddle doesn't work):

```
/* Options */

var accept_rate = 82,  // 0 (low) - 100 (high)
    attempts    = 16, // Attemps before giving up
    edge_multi  = 2;   // Contrast, 2-4

function Paint(image_url) {
    var image = new Image(), canvas = document.createElement('canvas'), context = null, result = document.createElement('canvas'), resultContext = result.getContext('2d'), final_colors = [], self = this, color_choices = [
        [0,0,0],
        [255,255,255],
        [192,192,192],
        [128,128,128],
        [126,3,8],
        [252,13,27],
        [255,253,56],
        [128,127,23],
        [15,127,18],
        [41,253,46],
        [45,255,254],
        [17,128,127],
        [2,12,126],
        [11,36,251],
        [252,40,252],
        [127,15,126],
        [128,127,68],
        [255,253,136],
        [42,253,133],
        [4,64,64],
        [23,131,251],
        [133,255,254],
        [129,132,252],
        [6,66,126],
        [127,37,251],
        [127,64,13],
        [253,128,73],
        [252,22,129]
      ];
  image.crossOrigin = "";
  image.src = image_url;

  this.done = this.done || function () {};

  function hex(c) {
    var res = c.toString(16);
    return res.length == 1 ? "0" + res : res;
  }

  function colorHex(r) {
    return '#' + hex(r[0]) + hex(r[1]) + hex(r[2]);
  }

  image.onload = function () {
    canvas.width = image.width; canvas.height = image.height * 2;
    context = canvas.getContext('2d');
    context.drawImage(image, 0, 0, image.width, image.height);

    function averageColors(colors_ar) {
      var av_r = 0,
          av_g = 0,
          av_b = 0;

      colors_ar.forEach(function (color) {
        av_r += color[0];
        av_g += color[1];
        av_b += color[2];
      });

      return [av_r / colors_ar.length,
              av_g / colors_ar.length,
              av_b / colors_ar.length];
    }

    function arrayFrom(ar) {
      var newar = [];
      for (var i = 0; i < ar.length; i += 1) {
        newar.push(ar[i]);
      }
      return newar;
    }

    function colorDif(c1,c2) {
      // Get's distance between two colors 0.0 - 1.0
      return (Math.abs(c1[0] - c2[0]) / 255 +
              Math.abs(c1[1] - c2[1]) / 255 +
              Math.abs(c1[2] - c2[2]) / 255) / 3;
    }

    var furthest = (function (cc) {
      // Determines furthest color

      // Reduces RGB into a "single value"
      reduce = cc.map(function(color) {
        return ( color[0] + color [1] + color [2] ) / 3;
      });

    }(color_choices));

    function intDif(i1,i2,t) {
        return Math.abs(i1 - i2) / t
    }

    function arrayIs(ar, int,d) {
        return intDif(ar[0],int,255) <= d &&
               intDif(ar[1],int,255) <= d &&
               intDif(ar[2],int,255) <= d
    }

    function colorLoop(c1,c2) {
        var edgeCap =  edge_multi * ((accept_rate / 100) / 50), values = c2.map(function (i) {
            return colorDif(c1,i);
        });

      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             c2[values.indexOf(Math.min.apply(Math, values))];
    }

    function colorFilter(c1, c2) {
      // Does the color stuff
      var rand  = Math.floor( Math.random() * c2.length ), // Random number
          color = c2[rand], // Random color
          randdif = colorDif(c1, color),
          threshhold = 1 - accept_rate / 100, // If the color passes a threshhold
          maxTries   = attempts, // To avoid infinite looping, 56 is the maximum tries to reach the threshold
          tries      = [];

      // Repeat until max iterations have been reached or color is close enough

      while ( tries.length <= maxTries && colorDif( c1, color ) > threshhold ) {
        tries.push(color);
        color = c2[Math.floor(Math.random() * c2.length)]; // Tries again

        if (tries.length == maxTries) {
          // Used to hold color and location
          var refLayer = tries.map(function(guess) {
            return colorDif(c1, guess);
          });

          color = tries[refLayer.indexOf(Math.min.apply(Math, refLayer))];
            tries.push(color);
        }

      }

      var edgeCap =  edge_multi * ((accept_rate / 100) / 50), loop = colorLoop(c1, c2);

      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             colorDif(c1,color)<accept_rate?color:
             loop;
    }

    function chunk(ar, len) {
      var arrays = [];

      while (ar.length > 0)
        arrays.push(ar.splice(0, len).slice(0, -1));

      return arrays;
    }

    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;

    for (var i = 0; i < total; i += 1) {
      if (x > (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }

      final_colors.push( colorFilter( averageColors( chunk( arrayFrom(context.getImageData(x * 2, y * 2, 4, 4).data), 4 ) ), color_choices) );

      x += 1;
    }

    // Paint Image
    result.width = canvas.width;
    result.height = canvas.height;
    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
    for (var i = 0; i < total; i += 1) {
      if (x > (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }

        console.log("Filling point (" + x + ", " + y + ") : " + colorHex(final_colors[i]));

      resultContext.fillStyle = colorHex(final_colors[i]);
      resultContext.fillRect(x*2 + 1, y * 2, 2 , 1); // Top
      resultContext.fillRect(x * 2, y * 2 + 1, 4, 2); // Middle
      resultContext.fillRect(x * 2 + 1, y * 2 + 3, 2, 1); // Bottom

      x += 1;
    }

    self.result = result.toDataURL("image/png");
    self.resultCanvas = result;
    self.imageCanvas = canvas;
    self.image = image;
    self.done();

    console.log(self.result);

  };

  image.onerror = function(error) {
    console.log("The image failed to load. " + error);
  }

}

// Demo

document.getElementById('go').onclick = function () {
    var url = document.getElementById('image').value;
    if (!url.indexOf('data:') == 0) {
        url = 'http://crossorigin.me/' + url;
    }
    var example = new Paint(url);

    example.done = function () {
        document.getElementById('result').src = example.result;
        document.getElementById('result').width = example.resultCanvas.width;
        document.getElementById('result').height = example.resultCanvas.height;
        window.paint = example;
    };
};
```

```
<!--This might take a while-->
Enter the image data URI or a URL, I've used crossorigin.me so it can  perform CORS requests to the image. If you're inputting a URL, be sure to include the http(s)
<input id="image" placeholder="Image URI or URL"><button id="go">Go</button>
    <hr/>
    You can get the image URI from a website like <a href="http://jpillora.com/base64-encoder/">this one</a>
    <hr/>

    Result:
    <img id="result">
        <span id="error"></span><hr/>
        Check your console for any errors. After a second, you should see the colors that are being generated / printed getting outputted to the console.
```

---

To commemorate New Horizon's flyby of Pluto, I've inputted an image of Pluto:

For the following I've set it to make them resemble the original as close as possible:

I ran this with OS X Yosemite's default wallpaper. After leaving it run for a bit, the results are absolutely stunning. The original file was huge (26 MB) so I resized and compressed it:

The starry night (I've used a higher resolution image for better results)

A picture I found on google:

# Answer
> 12 votes
# **JavaScript + HTML**

### Random:

Random Point

### Random Aligned:

Subdivides the canvas into 4x4 squares, and chooses a point randomly inside one of the squares. Offsets will move the grid, so you can fill in the little gaps.

### Loop:

Creates a grid and Loops through all the points. Offsets moves the grid. Spacing determine the size of each cell. (They will start to overlap)

### Color difference:

* RGB
* HSL
* HSV

```
var draw = document.getElementById("canvas").getContext("2d");
var data = document.getElementById("data").getContext("2d");
colors = [
    [0, 0, 0],
    [255, 255, 255],
    [192, 192, 192],
    [128, 128, 128],
    [126, 3, 8],
    [252, 13, 27],
    [255, 253, 56],
    [128, 127, 23],
    [15, 127, 18],
    [41, 253, 46],
    [45, 255, 254],
    [17, 128, 127],
    [2, 12, 126],
    [11, 36, 251],
    [252, 40, 252],
    [127, 15, 126],
    [128, 127, 68],
    [255, 253, 136],
    [42, 253, 133],
    [4, 64, 64],
    [23, 131, 251],
    [133, 255, 254],
    [129, 132, 252],
    [6, 66, 126],
    [127, 37, 251],
    [127, 64, 13],
    [253, 128, 73],
    [252, 22, 129]
];
iteration = 0;
fails = 0;
success = 0;
x = 0;
y = 0;
//Init when the Go! button is pressed
document.getElementById("file").onchange = function (event) {
    document.getElementById("img").src = URL.createObjectURL(event.target.files[0]);
    filename = document.getElementById("file").value;
    /*if (getCookie("orginal") == filename) {
        console.log("Loading from Cookie");
        reload = true;
        document.getElementById("reload").src = getCookie("picture");
    }*/
};

/*function getCookie(cname) {
    var name = cname + "=";
    var ca = document.cookie.split(';');
    for (var i = 0; i < ca.length; i++) {
        var c = ca[i];
        while (c.charAt(0) == ' ') c = c.substring(1);
        if (c.indexOf(name) == 0) return c.substring(name.length, c.length);
    }
    return "";
}*/

//Run when the image has been loaded into memory
document.getElementById("img").onload = function () {
    document.getElementById("file").disable = "true";
    document.getElementById("canvas").hidden = "";
    document.getElementById("canvas").height = document.getElementById("img").height;
    document.getElementById("data").height = document.getElementById("img").height;
    document.getElementById("canvas").width = document.getElementById("img").width;
    document.getElementById("data").width = document.getElementById("img").width;

    var imgData = draw.createImageData(document.getElementById("img").width, document.getElementById("img").height);
    for (var i = 0; i < imgData.data.length; i += 4) {
        imgData.data[i + 0] = 0;
        imgData.data[i + 1] = 0;
        imgData.data[i + 2] = 0;
        imgData.data[i + 3] = 255;
    }
    draw.putImageData(imgData, 0, 0);
    data.putImageData(imgData, 0, 0);
    if (reload == true) {
        draw.drawImage(document.getElementById("reload"), 0, 0);
    }
    data.drawImage(document.getElementById("img"), 0, 0);
    setInterval(function () {
        for (var u = 0; u < document.getElementById("selectColor").value; u++) {
            doThing();
        }
    }, 0);
};

//The core function. Every time this function is called, is checks/adds a dot.
function doThing() {
    getCoords();
    paintBucket();
    console.count("Iteration");
    if (compare(x, y)) {
        draw.putImageData(imgData, x, y);
    }
}

function getCoords() {
    switch (document.getElementById("selectCord").value) {
        case "1":
            x = Math.floor(Math.random() * (document.getElementById("img").width + 4));
            y = Math.floor(Math.random() * (document.getElementById("img").height + 4));
            break;
        case "2":
            x = Math.floor(Math.random() * ((document.getElementById("img").width + 4) / 4)) * 4;
            console.log(x);
            x += parseInt(document.getElementById("allignX").value);
            console.log(x);
            y = Math.floor(Math.random() * ((document.getElementById("img").height + 4) / 4)) * 4;
            y += parseInt(document.getElementById("allignY").value);
            break;
        case "3":
            x += parseInt(document.getElementById("loopX").value);
            if (x > document.getElementById("img").width + 5) {
                x = parseInt(document.getElementById("allignX").value);
                y += parseInt(document.getElementById("loopY").value);
            }
            if (y > document.getElementById("img").height + 5) {
                y = parseInt(document.getElementById("allignY").value);
            }
    }
}

function compare(arg1, arg2) {
    var arg3 = arg1 + 4;
    var arg4 = arg2 + 4;
    imgData2 = data.getImageData(arg1, arg2, 4, 4);
    imgData3 = draw.getImageData(arg1, arg2, 4, 4);
    N = 0;
    O = 0;
    i = 4;
    addCompare();
    addCompare();
    i += 4;
    for (l = 0; l < 8; l++) {
        addCompare();
    }
    i += 4;
    addCompare();
    addCompare();
    i += 4;
    //console.log("New Score: " + N + " Old Score: " + O);
    iteration++;
    /*if(iteration>=1000){
        document.cookie="orginal="+filename;
        document.cookie="picture length="+document.getElementById("canvas").toDataURL().length;
        document.cookie="picture="+document.getElementById("canvas").toDataURL();

    }*/
    if (N < O) {
        return true;
    } else {
        return false;
    }
}

function addCompare() {
    if (document.getElementById("colorDif").value == "HSL") {
        HSLCompare();
        i += 4;
        return;
    }
    if (document.getElementById("colorDif").value == "HSV") {
        HSVCompare();
        i += 4;
        return;
    }
    N += Math.abs(imgData.data[i] - imgData2.data[i]);
    N += Math.abs(imgData.data[i + 1] - imgData2.data[i + 1]);
    N += Math.abs(imgData.data[i + 2] - imgData2.data[i + 2]);
    O += Math.abs(imgData3.data[i] - imgData2.data[i]);
    O += Math.abs(imgData3.data[i + 1] - imgData2.data[i + 1]);
    O += Math.abs(imgData3.data[i + 2] - imgData2.data[i + 2]);
    i += 4;
}

function HSVCompare() {
    var NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[0];
    var PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[0];
    var OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[0];

    var NScore = [Math.abs(NewHue - PicHue), ((NewHue < PicHue) ? NewHue + (1 - PicHue) : PicHue + (1 - NewHue))];
    var OScore = [Math.abs(OldHue - PicHue), ((OldHue < PicHue) ? OldHue + (1 - PicHue) : PicHue + (1 - OldHue))];

    NScore = Math.min(NScore[0], NScore[1]);
    OScore = Math.min(OScore[0], OScore[1]);

    NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[1];
    PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[1];
    OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[1];

    NScore += Math.abs(NewHue-PicHue);
    OScore += Math.abs(OldHue-PicHue);

    NewHue = rgbToHsv(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[2];
    PicHue = rgbToHsv(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[2];
    OldHue = rgbToHsv(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[2];

    N += Math.abs(NewHue-PicHue) + NScore;
    O += Math.abs(OldHue-PicHue) + OScore;
}

function rgbToHsv(r, g, b){
    r = r/255, g = g/255, b = b/255;
    var max = Math.max(r, g, b), min = Math.min(r, g, b);
    var h, s, v = max;

    var d = max - min;
    s = max == 0 ? 0 : d / max;

    if(max == min){
        h = 0; // achromatic
    }else{
        switch(max){
            case r: h = (g - b) / d + (g < b ? 6 : 0); break;
            case g: h = (b - r) / d + 2; break;
            case b: h = (r - g) / d + 4; break;
        }
        h /= 6;
    }

    return [h, s, v];
}

function HSLCompare() {
    var result = 0;
    rgb = false;

    var NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[0];
    var PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[0];
    var OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[0];
    if (rgb == true) {
        N += Math.abs(imgData.data[i] - imgData2.data[i]);
        N += Math.abs(imgData.data[i + 1] - imgData2.data[i + 1]);
        N += Math.abs(imgData.data[i + 2] - imgData2.data[i + 2]);
        O += Math.abs(imgData3.data[i] - imgData2.data[i]);
        O += Math.abs(imgData3.data[i + 1] - imgData2.data[i + 1]);
        O += Math.abs(imgData3.data[i + 2] - imgData2.data[i + 2]);
        return;
    }
    var NScore = [Math.abs(NewHue - PicHue), ((NewHue < PicHue) ? NewHue + (1 - PicHue) : PicHue + (1 - NewHue))];
    var OScore = [Math.abs(OldHue - PicHue), ((OldHue < PicHue) ? OldHue + (1 - PicHue) : PicHue + (1 - OldHue))];

    NScore = Math.min(NScore[0], NScore[1]);
    OScore = Math.min(OScore[0], OScore[1]);

    NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[1];
    PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[1];
    OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[1];

    NScore += Math.abs(NewHue-PicHue);
    OScore += Math.abs(OldHue-PicHue);

    NewHue = rgbToHue(imgData.data[i], imgData.data[i + 1], imgData.data[i + 2])[2];
    PicHue = rgbToHue(imgData2.data[i], imgData2.data[i + 1], imgData2.data[i + 2])[2];
    OldHue = rgbToHue(imgData3.data[i], imgData3.data[i + 1], imgData3.data[i + 2])[2];

    N += Math.abs(NewHue-PicHue) + NScore;
    O += Math.abs(OldHue-PicHue) + OScore;
}

function rgbToHue(r, g, b) {
    if (Math.max(r, g, b) - Math.min(r, g, b) < 50) {
        rgb = true
    }
    r /= 255, g /= 255, b /= 255;
    var max = Math.max(r, g, b),
        min = Math.min(r, g, b);
    var h, s, l = (max + min) / 2;

    if (max == min) {
        h = s = 0; // achromatic
    } else {
        var d = max - min;
        s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
        switch (max) {
            case r:
                h = (g - b) / d + (g < b ? 6 : 0);
                break;
            case g:
                h = (b - r) / d + 2;
                break;
            case b:
                h = (r - g) / d + 4;
                break;
        }
        h /= 6;
    }
    return [h,s,l];
}

//Create a 4x4 ImageData object, random color selected from the colors var, transparent corners.
function paintBucket() {
    color = Math.floor(Math.random() * 28);
    imgData = draw.createImageData(4, 4);
    imgData2 = draw.getImageData(x, y, 4, 4);
    i = 0;
    createCorn();
    createColor();
    createColor();
    createCorn();
    for (l = 0; l < 8; l++) {
        createColor();
    }
    createCorn();
    createColor();
    createColor();
    createCorn();
}

function createCorn() {
    imgData.data[i] = imgData2.data[i];
    imgData.data[i + 1] = imgData2.data[i + 1];
    imgData.data[i + 2] = imgData2.data[i + 2];
    imgData.data[i + 3] = 255;
    i += 4;
}

function createColor() {
    imgData.data[i] = colors[color][0];
    imgData.data[i + 1] = colors[color][1];
    imgData.data[i + 2] = colors[color][2];
    imgData.data[i + 3] = 255;
    i += 4;
}
```

```
<canvas id="canvas" hidden></canvas>
<br>
<canvas id="data" hidden></canvas>
<br>
<input type="file" id="file"></input>
<br>
<img id="img">
<img id="reload" hidden>
<p>Algorithms:</p>
<select id="selectCord">
    <option value="1">Random</option>
    <option value="2">Random Alligned</option>
    <option value="3" selected>Loop</option>
</select>
<select id="selectColor">
    <option value="2000">Super Speedy</option>
    <option value="1000">Very Speedy</option>
    <option value="500" selected>Speedy</option>
    <option value="1">Visual</option>
</select>
<select id="colorDif">
    <option value="RGB" selected>RGB</option>
    <option value="HSL">HSL</option>
    <option value="HSV">HSV</option>
</select>
<p>Algorithm Options:
    <br>
</p>
<p>X Offset:
    <input id="allignX" type="range" min="0" max="3" value="0"></input>
</p>
<p>Y Offset:
    <input id="allignY" type="range" min="0" max="3" value="0"></input>
</p>
<p>Spacing X:
    <input id="loopX" type="range" min="1" max="4" value="2"></input>
</p>
<p>Spacing Y:
    <input id="loopY" type="range" min="1" max="4" value="2"></input>
</p>
```

RGB:
HSL:
HSV:

# Answer
> 8 votes
## C# (reference implementation)

This is the code used to generate the images in the question. I thought it would be useful to give some people a reference for organizing their algorithm. A completely random coordinate and color are selected each movement. It performs surprisingly well considering the limitations imposed by the brush size/acceptance criteria.

I use the CIEDE2000 algorithm for measuring color differences, from the open source library ColorMine. This should give closer color matches (from a human perspective) but it doesn't seem to be a noticeable difference when used with this palette.

```
using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
using ColorMine.ColorSpaces;
using ColorMine.ColorSpaces.Comparisons;

namespace Painter
{
    public class Painter
    {
        private readonly Bitmap _source;
        private readonly Bitmap _painting;
        private readonly int _width;
        private readonly int _height;
        private readonly CieDe2000Comparison _comparison = new CieDe2000Comparison();
        private const int BRUSHSIZE = 4;
        private readonly Random _random = new Random();
        private readonly ColorPalette _palette;

        private static readonly int[][] BRUSH = {
            new[] {1, 0}, new[] {2, 0},
            new[] {0, 1}, new[] {1, 1}, new[] {2, 1}, new[] {3, 1},
            new[] {0, 2}, new[] {1, 2}, new[] {2, 2}, new[] {3, 2},
            new[] {1, 3}, new[] {2, 3}
        };

        public Painter(string sourceFilename, string paletteFilename)
        {
            _source = (Bitmap)Image.FromFile(sourceFilename);
            _width = _source.Width;
            _height = _source.Height;

            _palette = Image.FromFile(paletteFilename).Palette;
            _painting = new Bitmap(_width, _height, PixelFormat.Format8bppIndexed) {Palette = _palette};

            // search for black in the color palette
            for (int i = 0; i < _painting.Palette.Entries.Length; i++)
            {
                Color color = _painting.Palette.Entries[i];
                if (color.R != 0 || color.G != 0 || color.B != 0) continue;
                SetBackground((byte)i);
            }
        }

        public void Paint()
        {
            // pick a color from the palette
            int brushIndex = _random.Next(0, _palette.Entries.Length);
            Color brushColor = _palette.Entries[brushIndex];

            // choose coordinate
            int x = _random.Next(0, _width - BRUSHSIZE + 1);
            int y = _random.Next(0, _height - BRUSHSIZE + 1);

            // determine whether to accept/reject brush
            if (GetBrushAcceptance(brushColor, x, y))
            {
                BitmapData data = _painting.LockBits(new Rectangle(0, y, _width, BRUSHSIZE), ImageLockMode.ReadWrite, PixelFormat.Format8bppIndexed);
                byte[] bytes = new byte[data.Height * data.Stride];
                Marshal.Copy(data.Scan0, bytes, 0, bytes.Length);

                // apply 4x4 brush without corners
                foreach (int[] offset in BRUSH)
                {
                    bytes[offset[1] * data.Stride + offset[0] + x] = (byte)brushIndex;
                }
                Marshal.Copy(bytes, 0, data.Scan0, bytes.Length);
                _painting.UnlockBits(data);
            }
        }

        public void Save(string filename)
        {
            _painting.Save(filename, ImageFormat.Png);
        }

        private void SetBackground(byte index)
        {
            BitmapData data = _painting.LockBits(new Rectangle(0, 0, _width, _height), ImageLockMode.WriteOnly, PixelFormat.Format8bppIndexed);
            byte[] bytes = new byte[data.Height * data.Stride];
            for (int i = 0; i < data.Height; i++)
            {
                for (int j = 0; j < data.Stride; j++)
                {
                    bytes[i*data.Stride + j] = index;
                }
            }
            Marshal.Copy(bytes, 0, data.Scan0, bytes.Length);
            _painting.UnlockBits(data);
        }

        private bool GetBrushAcceptance(Color brushColor, int x, int y)
        {
            double currentDifference = 0.0;
            double brushDifference = 0.0;
            foreach (int[] offset in BRUSH)
            {
                Color sourceColor = _source.GetPixel(x + offset[0], y + offset[1]);
                Rgb sourceRgb = new Rgb {R = sourceColor.R, G = sourceColor.G, B = sourceColor.B};
                Color currentColor = _painting.GetPixel(x + offset[0], y + offset[1]);

                currentDifference += sourceRgb.Compare(new Rgb {R = currentColor.R, G = currentColor.G, B = currentColor.B}, _comparison);
                brushDifference += sourceRgb.Compare(new Rgb {R = brushColor.R, G = brushColor.G, B = brushColor.B}, _comparison);
            }
            return brushDifference < currentDifference;
        }
    }
}

```

Then you can generate series of images (like my video) by calling an instance in a way similar to the code below (tweak based on number of iterations/frames/name desired). The first argument is the file path to the source image, the second argument is the file path to the palette (linked in the question), and the third argument is the file path for output images.

```
namespace Painter
{
    class Program
    {
        private static void Main(string[] args)
        {
            int i = 0;
            int counter = 1;
            Painter painter = new Painter(args[0], args[1]);
            while (true)
            {
                painter.Paint();
                if (i%500000 == 0)
                {
                    counter++;
                    painter.Save(string.Format("{0}{1:D7}.png", args[2], counter));
                }
                i++;
            }
        }
    }
}

```

I searched for some colorful canvas paintings online and came across the images below, which seem to be great (complicated) test images. All copyrights belong to their respective owners.

Source

Source

Source

# Answer
> 7 votes
# JavaScript Canvas

**Update**

Excellent suggestions in the comments. It's now faster and doesn't slow down the ui!

```
function previewFile() {
  var srcImage = document.getElementById('srcImage');
  var file = document.querySelector('input[type=file]').files[0];
  var reader = new FileReader();

  reader.onloadend = function() {
    srcImage.src = reader.result;
  }

  if (file) {
    reader.readAsDataURL(file);
  } else {
    srcImage.src = "";
  }
}

var buckets = []; // buckets / iterations
var iter_per_focus = 5000;

var pal = "00FFFF,0000FF,00FF00,FFFF00,\
C0C0C0,FF0000,FF00FF,FFFF78,\
FF0078,FF7848,7878FF,78FFFF,\
00FF78,784800,007800,\
007878,787800,780000,787878,\
000078,780078,004878,7800FF,\
0078FF,004848,787848,000000,FFFFFF".split(",");
var pLen = pal.length;
var p = 0;
var _R = 0;
var _G = 1;
var _B = 2;
var _CAN = 3;

// Create fast access palette with r,g,b values and
// brush image for color.
function initPal() {

  for (var i = 0; i < pal.length; i++) {
    var r = parseInt(pal[i].substr(0, 2), 16);
    var g = parseInt(pal[i].substr(2, 2), 16);
    var b = parseInt(pal[i].substr(4, 2), 16);
    var pcan = document.createElement('canvas');
    pcan.width = 4;
    pcan.height = 4;
    var pctx = pcan.getContext('2d');
    pctx.fillStyle = '#' + pal[i];
    pctx.beginPath();
    pctx.rect(1, 0, 2, 4);
    pctx.rect(0, 1, 4, 2);
    pctx.fill();

    pal[i] = [r,g,b,pcan];

  }
}
initPal();

var score = [];
var can = document.getElementById("canB");
var ctx = can.getContext('2d');
var mainDiv = document.getElementById("main");
var bCan = document.createElement('canvas');
bCan.width = can.width;
bCan.height = can.height;
var bCtx = bCan.getContext('2d');

var canA = document.getElementById("canA");
can.width = can.height = canA.width = canA.height = 200;
var ctxA = canA.getContext('2d');
var imageData;
var data;

function getSrcImage() {
  var img = document.getElementById('srcImage');
  can.width = canA.width = img.width;
  can.height = canA.height = img.height;
  ctxA.drawImage(img, 0, 0);
  imageData = ctxA.getImageData(0, 0, img.width, img.height);
  data = imageData.data;

  // adjust for brush offset
  var w = can.width - 2;
  var h = can.height - 2;

  var n = Math.floor((w * h) / iter_per_focus);
  buckets = [];
  for (var i = 0; i < n; i++) {
    var bucket = [];
    bucket.r = Math.floor(Math.random() * pLen);
    buckets.push(bucket);
  }
  var b = 0;
  var pt = 0;
  for (var y = 0; y < h; y++) {
    for (var x = 0; x < w; x++, pt+=4) {
      var r = Math.floor((Math.random() * n));
      buckets[r].push([x,y,pt,256 * 12,Math.floor(Math.random()*pLen)]);
      b %= n;
    }
    pt += 8; // move past brush offset.
  }

}

var loopTimeout = null;

function loopInit() {
  var r, y, x, pt, c, s;
  var row = can.width * 4;

  var b = 0;

  function loop() {
    clearTimeout(loopTimeout);
    var bucket = buckets[b++];
    var len = bucket.length;
    // Stepping color
    //c = pal[p];
    // Pulsing color;
    //c = pal[Math.floor(Math.random()*pLen)]
    // Pulsting step
    c = pal[bucket.r++];
    bucket.r%=pLen;
    b %= buckets.length;
    if (b === 0) {
      p++;
      p%=pLen;
    }

    for (var i = 0; i < len; i++) {

      var x = bucket[i][0]
      var y = bucket[i][1];
      var pt = bucket[i][2];
      // Random color
      //c = pal[bucket[i][4]++];
      //bucket[i][4]%=pLen;

      s = Math.abs(data[pt] - c[_R]) +
        Math.abs(data[pt + 1] - c[_G]) +
        Math.abs(data[pt + 2] - c[_B]) +
        Math.abs(data[pt + 4] - c[_R]) +
        Math.abs(data[pt + 5] - c[_G]) +
        Math.abs(data[pt + 6] - c[_B]) +
        Math.abs(data[pt + row] - c[_R]) +
        Math.abs(data[pt + row + 1] - c[_G]) +
        Math.abs(data[pt + row + 2] - c[_B]) +
        Math.abs(data[pt + row + 4] - c[_R]) +
        Math.abs(data[pt + row + 5] - c[_G]) +
        Math.abs(data[pt + row + 6] - c[_B]);
      if (bucket[i][3] > s) {
        bucket[i][3] = s;
        bCtx.drawImage(c[_CAN], x - 1, y - 1);
      }

    }
    loopTimeout = setTimeout(loop, 0);
  }

  loop();
}

// Draw function is separate from rendering. We render
// to a backing canvas first.
function draw() {
  ctx.drawImage(bCan, 0, 0);
  setTimeout(draw, 100);
}

function start() {

  getSrcImage();
  imageData = ctxA.getImageData(0, 0, can.width, can.height);
  data = imageData.data;
  bCan.width = can.width;
  bCan.height = can.height;
  bCtx.fillStyle = "black";
  bCtx.fillRect(0, 0, can.width, can.height);
  loopInit();

  draw();
}
```

```
body {
  background-color: #444444;
  color: #DDDDEE;
}
#srcImage {
  display: none;
}
#testBtn {
  display: none;
}
#canA {
  display:none;
}
```

```
<input type="file" onchange="previewFile()">
<br>
<img src="" height="200" alt="Upload Image for MS Painting">

<button onclick="genImage()" id="testBtn">Generate Image</button>

<div id="main">
  <img id="srcImage" src="" onload="start()">
  <canvas id="canA"></canvas>
  <canvas id="canB"></canvas>
</div>
```

# Answer
> 3 votes
## Mathematica

It's not really all that fast though, but at least it makes vaguely recognisable images, so I'm happy.

```
img = Import["https://i.stack.imgur.com/P7X6g.jpg"]
squigglesize = 20;
squiggleterb = 35;
colors = Import["https://i.stack.imgur.com/u9JAD.png"];
colist = Table[RGBColor[PixelValue[colors, {x, 1}]], {x, 28}];
imgdim0 = ImageDimensions[img];
curimg = Image[ConstantArray[0, Reverse[imgdim0]]];

rp := RandomInteger[squigglesize, 2] - squigglesize/2;
i = 0; j = 0;
Module[{imgdim = imgdim0, randimg, points, randcol, squigmid, st,
  randist, curdist = curdist0, i = 0, j = 0},

 While[j < 10,
  squigmid = {RandomInteger[imgdim[[1]]], RandomInteger[imgdim[[1]]]};
  While[i < 20,
   randcol = RandomChoice[colist];
   st = RandomInteger[squiggleterb, 2] - squiggleterb/2;
   points = {rp + squigmid + st, rp + squigmid + st, rp + squigmid + st, rp + squigmid + st};

   randimg =
    Rasterize[
     Style[Graphics[{Inset[curimg, Center, Center, imgdim],
        {randcol, BezierCurve[Table[{-1, 0}, {4}] + points]},
        {randcol, BezierCurve[Table[{-1, 1}, {4}] + points]},
        {randcol, BezierCurve[Table[{0, -1}, {4}] + points]},
        {randcol, BezierCurve[points]},
        {randcol, BezierCurve[Table[{0, 1}, {4}] + points]},
        {randcol, BezierCurve[Table[{0, 2}, {4}] + points]},
        {randcol, BezierCurve[Table[{1, -1}, {4}] + points]},
        {randcol, BezierCurve[Table[{1, 0}, {4}] + points]},
        {randcol, BezierCurve[Table[{1, 1}, {4}] + points]},
        {randcol, BezierCurve[Table[{1, 2}, {4}] + points]},
        {randcol, BezierCurve[Table[{2, 0}, {4}] + points]},
        {randcol, BezierCurve[Table[{2, 1}, {4}] + points]}
       }, ImageSize -> imgdim, PlotRange -> {{0, imgdim[[1]]}, {0, imgdim[[2]]}}],
      Antialiasing -> False], RasterSize -> imgdim];
   randist = ImageDistance[img, randimg];
   If[randist < curdist, curimg = randimg; curdist = randist; i = 0;
    j = 0;];
   i += 1;
   ]; j += 1; i = 0;];
 Print[curimg]]

```

Output:

Output could probably be a bit better with more iterations, and there's still a lot that I can try to speed it up/improve convergence, but for now this seems good enough.

# Answer
> 2 votes
# SmileBASIC

```
OPTION STRICT
OPTION DEFINT

DEF MSPAINT(IMAGE,WIDTH,HEIGHT,STEPS)
 'read color data
 DIM COLORS[28]
 COPY COLORS%,@COLORS
 @COLORS
 DATA &H000000,&H808080,&H800000
 DATA &H808000,&H008000,&H008080
 DATA &H000080,&H800080,&H808040
 DATA &H004040,&H0080FF,&H004080
 DATA &H8000FF,&H804000,&HFFFFFF
 DATA &HC0C0C0,&HFF0000,&HFFFF00
 DATA &H00FF00,&H00FFFF,&H0000FF
 DATA &HFF00FF,&HFFFF80,&H00FF80
 DATA &H80FFFF,&H8080FF,&HFF0080
 DATA &HFF8040

 'create output array and fill with white
 DIM OUTPUT[WIDTH,HEIGHT]
 FILL OUTPUT,&HFFFFFFFF

 VAR K
 FOR K=1 TO STEPS
  'Pick random position/color
  VAR X=RND(WIDTH -3)
  VAR Y=RND(HEIGHT-3)
  VAR COLOR=COLORS[RND(28)]

  'Extract average (really the sum) color in a 4x4 area.
  'this is less detailed than checking the difference of every pixel
  'but it's better in some ways...
  'corners are included so it will do SOME dithering
  'R1/G1/B1 = average color in original image
  'R2/G2/B2 = average color in current drawing
  'R3/G3/B3 = average color if brush is used
  VAR R1=0,G1=0,B1=0,R2=0,G2=0,B2=0,R3=0,G3=0,B3=0
  VAR R,G,B
  VAR I,J
  FOR J=0 TO 3
   FOR I=0 TO 3
    'original image average
    RGBREAD IMAGE[Y+J,X+I] OUT R,G,B
    INC R1,R
    INC G1,G
    INC B1,B
    'current drawing average
    RGBREAD OUTPUT[Y+J,X+I] OUT R,G,B
    INC R2,R
    INC G2,G
    INC B2,B
    'add the old color to the brush average if we're in a corner
    IF (J==0||J==3)&&(I==0||I==3) THEN
     INC R3,R
     INC G3,G
     INC B3,B
    ENDIF
   NEXT
  NEXT
  'brush covers 12 pixels
  RGBREAD COLOR OUT R,G,B
  INC R3,R*12
  INC G3,G*12
  INC B3,B*12

  'Compare
  BEFORE=ABS(R1-R2)+ABS(G1-G2)+ABS(B1-B2)
  AFTER =ABS(R1-R3)+ABS(G1-G3)+ABS(B1-B3)

  'Draw if better
  IF AFTER<BEFORE THEN
   FILL OUTPUT,COLOR, Y   *WIDTH+X+1,2 ' ##
   FILL OUTPUT,COLOR,(Y+1)*WIDTH+X  ,4 '####
   FILL OUTPUT,COLOR,(Y+2)*WIDTH+X  ,4 '####
   FILL OUTPUT,COLOR,(Y+3)*WIDTH+X+1,2 ' ##
  ENDIF
 NEXT

 RETURN OUTPUT
END

```

**MSPAINT** *image%\[\]* **,** *width%* **,** *height%* **,** *steps%* **OUT** *output%\[\]*

* image% - 2D \[y,x\] integer array with the image data (32 bit ARGB format (alpha is ignored))
* width% - image width
* height% - image height
* steps% - number of iterations
* output% - output array, same as image%.

# Answer
> 2 votes
# Java + Processing

I saw this challenge and immediately had to try it.

My algorithm isn't too well optimized, so the output is a bit choppy.

```
color[] palette={#000000,#FFFFFF,#C0C0C0,#808080,#7E0308,#FC0D1B,#FFFD38,#807F17,#0F7F12,#29FD2E,#2DFFFE,#11807F,#020C7E,#0B24FB,#FC28FC,#7F0F7E,#807F44,#FFFD88,#2AFD85,#044040,#1783FB,#85FFFE,#8184FC,#06427E,#7F25FB,#7F400D,#FD8049,#FC1681};
PImage p;
int currTime;
int sTime=0;
int yPix;
void settings() {
  p=loadImage("arun-clarke-V-bkeYsTflY-unsplash.jpg");
  yPix = 0;

  size(p.width,p.height);
}
void setup() {
  frameRate(p.width);
    noStroke();
  rectMode(CENTER);
  //image(p,0,0);
  //for(int i=0; i<palette.length;i++) {
  //  fill(palette[i]);
  //  square(i*20,0, 20);
  //}
}

void draw() {

    int x =  int(random(p.width));
    int y = int(random(p.height));
    color randPix = p.get(x,y);
    float[] d = new float[palette.length];
    for(int k=0;k<palette.length;k++) {
    d[k]=abs(red(randPix)-red(palette[k]))+abs(blue(randPix)-blue(palette[k]))+abs(green(randPix)-green(palette[k]));
    }int b=0;
    for(int l=0;l<palette.length;l++){
      if(d[l]<=d[b]){
        b=l;
      }
    }
    fill(palette[b]);
    rect(x,y,2,4);
    rect(x,y,4,2);

}
void mouseClicked() {
  noLoop();
  save("c.png");
}

```

# Examples

---
Tags: popularity-contest, graphical-output
---


title: Saddle points in a matrix

text:
# Question
Title: Saddle points in a matrix
A matrix can be thought of as the altitudes of a surface in 3D space. Consider the 8 neighbours (orthogonal and diagonal) of a cell as a cyclic sequence in clockwise (or anticlockwise) order. Some neighbours may be higher than the original cell, some lower, and some levelled at the same height as the original cell. We split the cycle of neighbours into segments according to that property and discard the levelled segments. If we end up with exactly 4 segments alternating between higher and lower, we call the original cell an *order-2 saddle point*. Boundary cells (edges and corners) are never considered to be saddle points. Your task is to output the number of order-2 saddle points in a given matrix.

For instance, in the matrix

```
3 3 1
4 2 3
2 1 2

```

the central cell's neighbours in clockwise order are

```
3 3 1 3 2 1 2 4
+ + - +   -   +  // + for higher, - for lower
a a b c   d   a  // segments

```

Note that the list is cyclic, so we consider the final `4` part of the initial segment `a`. The signs of segments `abcd` are alternating - this is indeed a saddle point.

Another example:

```
1 7 6
5 5 5
2 5 6

```

Neighbours:

```
1 7 6 5 6 5 2 5
- + +   +   -
a b b   c   d

```

We have 4 +/- segments but their signs are not alternating, so this is *not* a saddle point. Note how segment `b` is separated from segment `c` by a levelled segment. We discard the levelled segment, but `b` and `c` remain separated. Same goes for `d` and `a`.

Third example:

```
3 9 1
8 7 0
3 7 8

```

Neighbours:

```
3 9 1 0 8 7 3 8
- + - - +   - +
a b c c d   e f

```

The signs are alternating but the number of +/- segments is 6. This is known as a *monkey saddle* or an *order-3 saddle point*. For the purposes of this challenge we should *not* count it.

Write a function or a complete program. Input is an integer matrix as typically represented in your language. It will consist of integers between 0 and 9 inclusive. Output is a single integer. Standard loopholes are forbidden. The shortest solution per language wins, as (obviously?) indicates.

```
in                                   out

[[3,3,1],[4,2,3],[2,1,2]]             1

[[1,7,6],[5,5,5],[2,5,6]]             0

[[3,9,1],[8,7,0],[3,7,8]]             0

[[3,2,3,9,0,4,2,1,9,9,1,4,8,7,9,3],
 [1,1,5,7,9,9,0,9,8,9,9,8,8,9,0,5],
 [5,8,1,5,1,6,3,5,9,2,5,6,9,0,7,5],
 [3,0,2,4,7,2,9,1,0,0,7,2,4,6,7,2],
 [6,7,1,0,2,7,3,2,4,4,7,4,5,7,3,2],
 [6,5,1,1,6,2,1,2,8,9,4,6,9,7,1,0],
 [1,6,1,8,2,2,7,9,2,0,2,4,8,8,7,5],
 [0,6,5,4,1,3,9,3,2,3,7,2,2,8,5,4]]  19

[[2,3,2,0,8,5,5,1,2,3,7,5,6,0,0,5],
 [4,1,4,9,4,7,3,8,6,8,4,2,8,7,1,7],
 [4,1,4,6,9,3,0,1,0,7,8,5,3,0,5,3],
 [5,6,0,8,0,4,9,3,2,9,9,8,4,0,0,3],
 [7,4,1,6,7,8,7,3,6,1,4,9,4,6,2,0],
 [3,1,6,7,9,7,7,6,8,6,8,1,4,9,7,0],
 [8,9,1,1,2,4,8,2,3,9,8,7,5,3,1,9],
 [0,9,5,3,8,7,7,7,8,9,0,0,2,7,3,4]]  31

[[6,6,2,3,4,6,5,4,9,5,5,1,4,7,7,6],
 [1,5,0,5,6,7,9,8,5,0,5,6,1,5,2,9],
 [0,0,0,6,1,8,1,1,9,0,7,4,5,4,5,5],
 [4,5,3,6,3,8,0,0,7,3,9,1,3,9,2,2],
 [8,8,5,3,7,1,0,7,1,1,8,1,3,0,7,7],
 [4,5,8,0,7,2,0,4,6,7,3,3,2,8,1,2],
 [1,1,6,2,5,8,4,2,6,1,6,9,8,4,8,1],
 [3,9,1,7,0,8,1,1,7,8,5,4,8,2,0,3]]   7

```

# Answer
# JavaScript (ES6), 179 bytes

```
a=>a.map((r,y)=>r.map((v,x)=>t+=x*y/r[x+1]&&a[y+1]?[...(S='12221000')+S].map((n,i)=>p-(p=d=Math.sign(v-a[y+~-n][x+~-S[i+2&7]]))&&d?s&s!=-(s=d)?T=a:T++:0,T=s=p=0)|T>>1==4:0),t=0)|t

```

Try it online!

### How?

We iterate on each cell \\$v\_{y,x}\\$ of each row \\$r\_y\\$ of the input matrix.

We first make sure that we're not located over an edge of the matrix with:

```
x * y / r[x + 1] && a[y + 1]

```

(neither \\$x\\$ or \\$y\\$ is \\$0\\$ and both \\$v\_{y,x+1}\\$ and \\$r\_{y+1}\\$ are defined)

We iterate twice on each neighbor cell and keep track of the number of valid segments in \\$T\\$. By doing this, each segment is guaranteed to be counted twice, except the first one which may be counted either twice or three times, depending on its starting point in relation to the starting point of the cycle. Either way, we have \\$\lfloor{T/2}\rfloor=4\\$ for order-2 saddle points, in which case we increment the counter \\$t\\$.

Example:

If the first segment is aligned with the starting point:

```
neighbor cells: AAAABCCD --> AAAABCCDAAAABCCD
                             ^   ^^ ^^   ^^ ^  --> T = 8

```

If it is not aligned:

```
neighbor cells: AABCCDAA --> AABCCDAAAABCCDAA
                             ^ ^^ ^^   ^^ ^^   --> T = 9

```

We iterate on neighbor cells by starting with the rightmost one and moving clockwise with:

```
[...(S = '12221000') + S].map((n, i) => a[x + ~-n][y + ~-S[i + 2 & 7]])

```

Try it online!

We store the sign of the difference between the current cell and its current neighbor in \\$d\\$. We keep track of the previous value of \\$d\\$ in \\$p\\$ and the previous sign (for non-zero values) in \\$s\\$.

The logic to update \\$p\\$, \\$s\\$ and \\$T\\$ reads as follows:

```
p - (p = d) && d ? s & s != -(s = d) ? T = a : T++ : 0

```

In plain English:

* Ignore identical consecutive values.
* Ignore segments with \\$d=0\\$.
* Increment \\$T\\$ on valid sign transitions.
* Whenever an invalid sign transition is detected, do `T = a` to force all upcoming operations on \\$T\\$ to either ***NaN*** or \\$0\\$, thus invalidating the final test.
> 4 votes

# Answer
# APL (Dyalog Unicode), ~~70~~ 66 bytes

```
D←⊢-1∘⌽
+/,{16=×/|D⍵/⍨×⍵×D⍵}¨(⍉1↓⌽)⍣4×(⊢-{⊂(,⍵)[8(-,⊢)3,⍳3]}⌺3 3)⎕

```

Try it online!

*-4 bytes thanks to @Bubbler and @ngn*

Full program that requires `⎕IO←0`

```
⍝ Helper function D: cyclic differences of a list
D←⊢-1∘⌽
  ⊢     ⍝ Each element
   -    ⍝ Subtract
    1∘⌽ ⍝ The one after
⍝ Main code
+/,{16=×/|D⍵/⍨×⍵×D⍵}¨¯2 ¯2↓1⊖1⌽×(⊢-{⊂(,⍵)[6 9 8 7 4,⍳3]}⌺3 3)⎕
⎕           ⍝ The input grid
{...}⌺3 3   ⍝ For the 3×3 window centered on each cell:
 (,⍵)[8(-,⊢)3,⍳3] ⍝ Obtain the cycle elements clockwise from the right
 ⊂                ⍝ Ensure that the output is the same shape as G
×⊢-         ⍝ The sign of the difference between each cycle and its center in G
(⍉1↓⌽)⍣4    ⍝ Trim off the entries with centers on an edge/corner
{...}¨      ⍝ For each sign-difference cycle:
 ×⍵×D⍵      ⍝ The indices where a +/- segment ends
              ⍝ (nonzero and different from the following element)
 ⍵/⍨        ⍝ The signs of each segment in order
              ⍝ (must be ¯1 1 ¯1 1 or reverse to be truthy --- can only have entries +/- 1)
 D          ⍝ Cyclic differences (must be 2 ¯2 2 ¯2 or reverse to be truthy --- can only have entries ¯2, 0, or 2)
 16=×/      ⍝ Test if product is 16: ensures right length and right values.
            ⍝ Note that the sum of the cyclic differences are always 0, so 2 2 2 2 is impossible)
+/,         ⍝ Count the total number that meet the condition

```

A creative idea I had was taking 2×2 stencils of 2×2 stencils with `({⊂⍵}⌺2 2)⍣2⊢G` then extracting cycles with `{1⌷⊃,/0 1 2 3{⍉∘⌽⍣⍺⊢⍵}¨,⍵}¨`. This might have been shorter (if golfed a bit more) because it didn't initially require `¯2 ¯2↓1⊖1`, but unfortunately we still had to subtract corresponding elements of G.
> 3 votes

# Answer
# 05AB1E, 66 bytes

```
gÍF3£D¬gÍFε3£}`R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ€¦}\\¦D}¯O

```

I'm 100% sure that I can reduce some bytes here, working on it :) Meanwhile, I'll post this basic idea.

Explenation:

```
gÍF3£D¬gÍFε3£}`R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ€¦D}\\¦}¯O
              `R«ćªćU«X.Sγ€Ù˜ÐнsθQsʒ0Ê}©gs-4Q®ü‚€OÄO0Q&ˆ                 Expects a 3x3 matrix. We will run this part for each relevant cell in the overall matrix.
                                                                         Pushes 1 to the global array when this cell is order-2 saddle point, pushes 0 otherwise.
                                                                         ----------
gÍ                                                                       number of rows in the matrix minus 2.
  F                                                            }         Loop Rows-2 times
   3£                                                                    Take 3 first rows.
     D¬                                                                  Push itself and the first element (first line)
       gÍ                                                                Size. (number of columns)
         F                                                 }             Loop Cols-2
          ε3£}                                                           Trim first 3 elements from each of the selected 3 rows.
                                                        €¦D              Remove the first element of each row and duplicate it for the next iteration.
                                                            \\¦          Clear remaining elements on stack, remove current first row of the 3 rows, prepare for next iteration.
                                                                         ----------
              `                                                          Push the 3x3 matrix we got from the nested loop in 3 separate values to the stack. Last row on top.
               R                                                         Reverse last row.
                «                                                        Merge with the second row.
                 ćª                                                      Extract head and append
                   ćU                                                    Extract head and save in X
                     «                                                   Merge with the first row. Now all values of the cell are in order clockwise.
                      X.S                                                For each element in the list, put -1 if lower than X (middle of cell), 0 if equal, 1 if greater.
                         γ                                               Split a into chunks of equal adjacent elements. (segment)
                          €Ù˜                                            Uniquify each element and flat the list.
                             Ð                                           Triplicate
                              нsθQ                                       Extract head, extract tail, are they equal?
                                  sʒ0Ê}©                                 Filter (remove zeros from the list), save the filtered list in register C
                                        g                                Size of the filtered list.
                                         s-                              Size of the filtered list - [1 if head was equal to the tail]
                                           4Q                            Is it equal to 4 (segments)? {{Condition I}}
                                             ®ü‚                         Overlapping pairs
                                                €O                       Sum each pair (desired: [-1,1] or [1,-1] will give 0)
                                                  Ä                      Abs(a)
                                                   O0Q                   Is the sum of all sums of pairs equals 0? (which means there was alternating 1/-1) {{Condition II}}
                                                      &                  Does both of the conditions were okay?
                                                       ˆ                 Push the result to the global array.
                                                                         ----------
                                                                ¯O       Push the global array and sum its values to get the number of order-2 saddle points.

```

Try it online!
> 2 votes

# Answer
# Python 2, 254 bytes

```
lambda m:sum(s(m[i][j:j+3],m[i+1][j:j+3],m[i+2][j+2::-1][:3])for j in range(len(m[0])-2)for i in range(len(m)-2))
t=['-','+']*2
def s(q,(x,m,y),w):a=''.join(' -+'[cmp(m,v)]for v in q+[y]+w+[x]);return[v for v,_ in zip(a,a[-1:]+a)if' '!=v!=_]in(t,t[::-1])

```

Try it online!
> 1 votes

# Answer
# Ruby, ~~237 218~~ 207 bytes

```
->a,z=0,i=j=1{l=z+=1if[[*a[i-1][h=j-1,3],(x=a[i])[j+1],*a[i+1][h,3].reverse,x[h]].map{|n|l=n<=>x[j]}.drop_while{|i|i==l}.map{|b|b==l||(l=b)==0?5:l}-[5]]-[[1,-1]*2,[-1,1]*2]==[];x[1+j+=1]||a[1+i+=j=1]?redo:z}

```

Try it online!
> 1 votes

---
Tags: code-golf, matrix, counting
---