35
\$\begingroup\$

Your task is to create a program that will, given an input image, create an output image of the same size, where all pixels are ordered by hex value.

Your program may:

  • Sort the pixels from left to right and then down or first sort down in columns and then right. In any case, the top left pixel is the smallest, and the bottom right is the largest.
  • Use transparency, but this is not required.
  • Sort by RGB, but you may use CMY, or any other format with at least 3 values. You can choose what values to sort on. (HSV may give some nice images)
  • Use any well-known image format that most computers can open.

Rules:

  • Output must be written to disk or be pipeable to a file.
  • Input is given as a commandline argument, in the form of a relative path to the image, or piped in from the commandline.
  • This is code golf, so shortest code in bytes wins!
\$\endgroup\$

13 Answers 13

20
\$\begingroup\$

Pyth - 10 bytes

Reads image, collapses bitmap, sorts, and then splits up bitmap again, then writes.

.wclK'zSsK

Doesn't work online for obvious reasons. Takes input as relative path to image file and outputs into o.png.

Output from American Gothic:

\$\endgroup\$
  • 3
    \$\begingroup\$ I hope I'm not the only one to have the impression that the picture is moving... \$\endgroup\$ – Quentin Nov 3 '15 at 0:33
  • \$\begingroup\$ It looks like wood. \$\endgroup\$ – Joe Z. May 3 '16 at 7:30
19
\$\begingroup\$

JavaScript (ES6), 383 377 354 bytes

f=s=>{d=document,i=new Image,i.src=s,i.onload=$=>{c=d.createElement`canvas`,x=c.getContext`2d`,c.width=w=i.width,c.height=h=i.height,x.drawImage(i,0,0),D=x.getImageData(0,0,w,h),t=D.data,t.set([].concat(...[...t].map((v,i,T)=>i%4?[,,,0]:T.slice(i,i+4)).sort((a,b)=>a.some((v,i)=>k=v-b[i])&&k)).slice(12*w*h)),x.putImageData(D,0,0),d.body.appendChild(c)}}

sample output

Runnable demo:

f=function(s) {l=[i=new Image].slice,i.crossOrigin="anonymous",i.src=s,i.onload=function($){d=document,c=d.createElement`canvas`,c.width=w=i.width,c.height=h=i.height,x=c.getContext`2d`,x.drawImage(i,0,0),D=x.getImageData(0,0,w,h),t=D.data,t.set([].concat.apply([],l.call(t).map((v,i)=>i%4?[0,0,0,0]:l.call(t,i,i+4)).sort((a,b)=>a.reduce((A,v,i)=>A||v-b[i],0))).slice(3*t.length)),x.putImageData(D,0,0),d.body.appendChild(c)}}
$("img").click(function() { f(this.src); })
canvas { padding-right: 4px; } img { cursor: pointer; }
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/The_Scream.jpg/114px-The_Scream.jpg"> <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Claude_Monet_La_Grenouill%C3%A9re.jpg/193px-Claude_Monet_La_Grenouill%C3%A9re.jpg"> <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg/120px-Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg"><br>

How this code works is to use getImageData to get an array of the form

[R,G,B,A,
 R,G,B,A,
 R,G,B,A,
 ...]

And map it to an array of the form

[[R,G,B,A],[0,0,0,0],[0,0,0,0],[0,0,0,0],
 [R,G,B,A],[0,0,0,0],[0,0,0,0],[0,0,0,0],
 [R,G,B,A],[0,0,0,0],[0,0,0,0],[0,0,0,0],
 ...]

So that the R values are mapped to arrays of the RGBA set, and the B, G, and A values turn into minimum-value zero arrays. When we sort this array, all the [0,0,0,0] arrays sort to the bottom and the real-value arrays sort normally at the top:

[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],
 [0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],
 [0,0,0,0],..., [R,G,B,A],[R,G,B,A],[R,G,B,A],...]
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
               extract & flatten these sorted pixels

We skim the top fourth of the array (to lose the empty values we created), flatten it with [].concat.apply, and end up with an array of the first form again, but this time, it's sorted.

Slightly de-golfed with whitespace and comments:

f=s=>{ 
  // first, load image, then do everything else onload
  i=new Image,
  i.src = s,
  i.onload=$=>{
    // set up the canvas
    d=document,
    c=d.createElement`canvas`,
    w=c.width=i.width,
    h=c.height=i.height,
    x=c.getContext`2d`,

    // draw image to canvas and capture pixel data
    x.drawImage(i,0,0),
    D=x.getImageData(0,0,w,h),
    t=D.data,

    // set pixel data to...
    t.set(
      // the flattened array...
      [].concat(...
        // that is a mapping of the pixel data...
        [...t].map(
          // that clumps RGBA families into subarrays
          // by replacing every fourth value with [R,G,B,A]
          // and all other values to [0,0,0,0]...
          (v,i,T)=>i%4?[,,,0]:T.slice(i,i+4)
        )
        // and is then sorted...
        .sort(
          // by reducing each array to a positive, negative, or zero
          // by comparing R,G,B,& A until the first nonzero difference
          (a,b)=>a.some((v,i)=>k=v-b[i])&&k
        )
      )
      // then eliminate the low-sorted empty [0,0,0,0] values we created,
      // leaving only the top fourth, with real values
      // (note that 3*4*w*h is the same as 3*t.length)
      .slice(3*4*w*h)
    ),

    // now that `t` is set, store `D` in canvas
    x.putImageData(D,0,0),

    // show canvas
    d.body.appendChild(c)
  }
}

Note that most browsers may fail to run this code for large images, because it passes a huge number of arguments into [].concat. When the browser environment does not allow sufficient memory for all the arguments, an alternative approach is to re-map the RGBA values out of the top fourth arrays back onto the array, for a total score of 361 bytes:

f=s=>{d=document,i=new Image,i.src=s,i.onload=$=>{c=d.createElement`canvas`,x=c.getContext`2d`,c.width=w=i.width,c.height=h=i.height,x.drawImage(i,0,0),D=x.getImageData(0,0,w,h),t=D.data,t.set([...t].map((v,i,T)=>i%4?[,,,0]:T.slice(i,i+4)).sort((a,b)=>a.some((v,i)=>k=v-b[i])&&k).map((v,i,A)=>A[3*w*h+(i>>2)][i%4])),x.putImageData(D,0,0),d.body.appendChild(c)}}

We simply replace the [].concat(...{stuff}).slice(12*w*h) with {stuff}.map((v,i,A)=>A[3*w*h+(i>>2)][i%4]).)

\$\endgroup\$
  • \$\begingroup\$ Could you include an example output? \$\endgroup\$ – Paŭlo Ebermann Nov 3 '15 at 18:46
  • \$\begingroup\$ @PaŭloEbermann Done. \$\endgroup\$ – apsillers Nov 3 '15 at 18:54
  • \$\begingroup\$ @insertusernamehere Oh, dang, I only tested on small images. My concat.apply call is supplying too many arguments to concat and the JS engine is rejecting it. D: Thanks! I'll fix that and note the two scores. (And I'm glad I could help!) \$\endgroup\$ – apsillers Nov 3 '15 at 18:56
  • \$\begingroup\$ @insertusernamehere Thanks for the head-up about the size limitation; I've now also published a slightly longer version that works on larger images. \$\endgroup\$ – apsillers Nov 5 '15 at 14:13
  • \$\begingroup\$ @apsillers Nice work. Can't upvote again unfortunately. :) \$\endgroup\$ – insertusernamehere Nov 5 '15 at 14:17
14
\$\begingroup\$

Mathematica 86 83 72 bytes

 f=Flatten;Image[f[Sort[f[s=ImageData@#1,1]]]~ArrayReshape~Dimensions@s]&

With 14 bytes saved thanks to @Martin Buttner.


Example

The image itself is input. Alternatively, a variable containing the image could be used.

gothic

\$\endgroup\$
  • \$\begingroup\$ The challenge specifies that pixels be sorted by hex value, but if I read this correctly, you use Mathematica's default sort for {R,G,B} or {R,G,B,alpha} lists. It's not clear to me that these are equivalent. \$\endgroup\$ – Michael Stern Nov 3 '15 at 0:55
  • \$\begingroup\$ @MichaelStern I don't know Mathematica, but if it sorts tuples elementwise like most languages, they are equivalent: Numbers like hex are sorted by each digit, two of which are represented by each element in the tuple. \$\endgroup\$ – Maltysen Nov 3 '15 at 1:01
  • \$\begingroup\$ @MichaelStern, Maltysen is correct. The RGB sort and the Hex sort are equivalent: sorting by the R, then the G, then the B value works just like the place value sort in Hex. \$\endgroup\$ – DavidC Nov 3 '15 at 1:05
  • \$\begingroup\$ OK, +1 from me. \$\endgroup\$ – Michael Stern Nov 3 '15 at 1:06
  • \$\begingroup\$ ImageData and ArrayReshape could use infix notation. Flatten is long enough to save a couple of bytes by assigning it to f. And do you actually need "Byte"? Wouldn't the default just scale the channel values to [0,1] such that the sorting and image reconstruction would still work just fine? \$\endgroup\$ – Martin Ender Nov 3 '15 at 9:29
5
\$\begingroup\$

Javascript ES6, 334 bytes

f=s=>{with((d=document).body.appendChild(c=d.createElement`canvas`).getContext`2d`)(i=new Image).src=s,drawImage(i,0,0,w=c.width=i.width,h=c.height=i.height),t=(g=getImageData(0,0,w,h)).data,t.set([...t].map(i=>(0+i.toString(16)).slice(-2)).join``.match(/.{8}/g).sort().join``.match(/../g).map(i=>parseInt(i,16))),putImageData(g,0,0)}

Ungolfed:

f=s=>{                                   // create function that accepts image name
 with((d=document).body.appendChild(     // use "with" to exclude having to prepend "<context2d>." to drawImage, getImageData and putImageData
   c=d.createElement`canvas`).getContext`2d`) // create canvas to get pixels from and draw output to
  (i=new Image).src=s,                   // create image, define source filename
  drawImage(i,0,0,w=c.width=i.width,     // draw image to canvas
                  h=c.height=i.height),
  t=(g=getImageData(0,0,w,h)).data,      // get image data from canvas in form of Uint8Array
  t.set([...t]                           // convert image data from Uint8Array to standard array
   .map(i=>(0+i.toString(16)).slice(-2)) // convert R,G,B,A bytes to base16 strings with leading zeros
   .join``.match(/.{8}/g)                // convert array of [R,G,B,A,R,G,B,A,...] to [RGBA,RGBA,...]
   .sort()                               // sort pixel values
   .join``.match(/../g)                  // convert array of [RGBA,RGBA,...] to [R,G,B,A,R,G,B,A,...]
   .map(i=>parseInt(i,16))),             // convert hex strings back to integers, reassign to image data
  putImageData(g,0,0)                    // dump image data onto canvas
}
\$\endgroup\$
  • \$\begingroup\$ @insertusernamehere It works on the latest Firefox. Like your answer, it assumes there is a body to append the canvas to and that the source image is from the same domain. \$\endgroup\$ – Dendrobium Nov 4 '15 at 0:16
  • \$\begingroup\$ +1 Very sleek solution. It also processes images up to 1600 x 1900px. \$\endgroup\$ – insertusernamehere Nov 4 '15 at 8:33
  • 2
    \$\begingroup\$ Today I learned that appendChild returns its argument. Very useful! You inspired me to whittle down my entry from 377 to 354, but I can't quite beat yours :). (When I use your appendChild-chaining and with technique I can get it down to 347, but still 13 away!) Excellent work! \$\endgroup\$ – apsillers Nov 4 '15 at 15:17
5
\$\begingroup\$

C (using SDL1.2), 333 322 315 bytes

C is most probably not the 'sharpest knife in the shelf' for this kind of work, I wanted to give it a try anyway. Tips for improving my answer are welcome. The program gets the name of the input image file as a cli argument.

#include <SDL.h>
#include <SDL_image.h>
#define X SDL_Surface*
#define Y const void*
C(Y a,Y b){return*(Uint32*)a-*(Uint32*)b;}main(int o,char**a){X i=IMG_Load(a[1]);X s=SDL_SetVideoMode(i->w,i->h,32,0);i=SDL_ConvertSurface(i,s->format,0);qsort(i->pixels,i->w*i->h,4,C);SDL_BlitSurface(i,0,s,0);for(;;SDL_Flip(s));}

compile and run : gcc -I/usr/include/SDL snippet.c -lSDL -lSDL_image && ./a.out

enter image description here

I don't usually golf in C, but I've just answered this challenge yesterday and I just wanted to continue playing with that new toy :)

thanks to @pseudonym117 for helping me saving 5 bytes

\$\endgroup\$
  • \$\begingroup\$ Can save 1 byte by changing your while at the end to for(;;SDL_Flip(s));, and I believe you can omit int on the method C and save 4 more. \$\endgroup\$ – pseudonym117 Nov 5 '15 at 17:37
4
\$\begingroup\$

JavaScript (ES6), 452 480 484 487 511 bytes

Wow, this got longer than expected:

f=u=>{i=new Image;i.src=u;i.onload=_=>{c=(d=document).createElement`canvas`;c.width=w=i.width;c.height=h=i.height;x=c.getContext`2d`;x.drawImage(i,0,0,w,h);p=x.getImageData(0,0,w,h).data;t=[];f=[];for(j=0;j<p.length;++j)t.push([p[j],p[++j],p[++j],p[++j]]);t.sort((a,b)=>a[0]>b[0]||a[0]==b[0]&&a[1]>b[1]||a[0]==b[0]&&a[1]==b[1]&&a[2]>b[2]).map(u=>f.push.apply(f,u));x.putImageData(new ImageData(new Uint8ClampedArray(f),w,h),0,0);d.body.appendChild(c)}}

The function takes an URL as its input f('test.jpg'); and draws the result into a canvas-element which is appended to the body.

Note that the source must be on the same domain or the script will halt with a security issue.


Limitations

I've tested it in Firefox 42 on OS X (10.10) on a machine with 2.5 GHz i7 and 16 GB RAM. The maximum image size I could process without Firefox asking to continue the script execution was 1600 x 1932 px.


Ungolfed

f = u => {
    i = new Image;
    i.src = u;
    i.onload = _ => {
        c = (d = document).createElement`canvas`;
        c.width = w = i.width;
        c.height = h = i.height;

        x = c.getContext`2d`;
        x.drawImage(i, 0, 0, w, h);

        p = x.getImageData(0, 0, w, h).data;

        t = [];
        f = [];

        for (j = 0; j < p.length;++j)
            t.push([p[j], p[++j], p[++j], p[++j]]);

        t.sort( (a,b) => a[0] > b[0] || a[0] == b[0] && a[1] > b[1] || a[0] == b[0] && a[1] == b[1] && a[2] > b[2] )
         .map(u => f.push.apply(f,u));

        x.putImageData( new ImageData( new Uint8ClampedArray(f), w, h), 0, 0);
        d.body.appendChild(c)
    }
}

Output

For a better comparison I also took the "American Gothic" as the example source:

enter image description here


Edits

  • Saved 24 bytes by using for (a in b) instead of for(;;). Thanks to ar34z
  • Saved 3 bytes by storing document in a variable.
  • Saved 4 bytes by dropping some of these ().
  • Saved 10 bytes by using tagged template strings, omitting the () on object creation and removing another pair of redundant (). Thanks to apsillers.
  • Saved 14 bytes by massive refactoring of the code that flattens the color array after sorting. Thanks a lot to apsillers and Ypnypn for undercutting each other.
  • Saved 1 byte by refactoring the for-loop that gets the colors of each pixel.
\$\endgroup\$
  • 1
    \$\begingroup\$ You can minimise the for-loops using for(k in t) which will save a few more bytes :) \$\endgroup\$ – ar34z Nov 3 '15 at 11:23
  • 1
    \$\begingroup\$ Nice work! Some improvements: lose the () in new Image(); use tagged template strings for your string arguments (createElement`canvas`, getContext`2d`), don't use parentheses for single arrow functions parameters (just do f=u=>{...}; parens are only for multi-parameter or zero-parameter arrow funcs). Also you might have one or two single-statement for loops that have brackets, which aren't necessary. \$\endgroup\$ – apsillers Nov 3 '15 at 14:05
  • \$\begingroup\$ Oh, actually, for zero-argument arrow funcs, use a single-character dummy argument instead of two-char empty parens. (i.onload=$=>... instead of i.onload=()=>...) \$\endgroup\$ – apsillers Nov 3 '15 at 14:11
  • \$\begingroup\$ I think for(l in u)f.push(u[l]); can become for(z of u)f.push(z); \$\endgroup\$ – Ypnypn Nov 3 '15 at 14:12
  • \$\begingroup\$ @Ypnypn It can be even shorter than that :). -- for(u of t)for(z of u)f.push(z) is pretty dang short, but it can be shortened further to t.map(u=>u.map(z=>f.push(z))). In a lot of cases, using .map or .some with an arrow function is going to be shorter than using a for loop. If you want to go really crazy, you can save even more here with t.map(u=>f.push.apply(f,u)); which says "For every array u in t, supply u as a list of arguments to f.push via apply (since push can accept an unbounded number of arguments and it pushes all of them in order). \$\endgroup\$ – apsillers Nov 3 '15 at 17:45
4
\$\begingroup\$

Bash + GNU utils, 80

s()(sed 1d $1|cut -d\  -f$2)
sed 1q $1
s $1 2-|sort -t_ -k1.16|paste <(s $1 1) -

This assumes input/output format is in ImageMagick pixel enumeration .txt format. The input is passed as a filename and the output goes to STDOUT.


If the above is not considered a well-known image format, then we can add in the necessary conversions:

Bash + GNU utils + ImageMagick, 108

s()(sed 1d t|cut -d\  -f$1)
convert $1 txt:t
(sed 1q t
s 2-|sort -t_ -k1.16|paste <(s 1) -)|convert txt:- $2

Input and output are specified as filenames. ImageMagick determines what file formats to use by the passed file extensions, so we can use any common ones:

$ ./sortpixels.sh 398px-Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg o.png
$ 

The resulting o.png looks like:

enter image description here

\$\endgroup\$
3
\$\begingroup\$

Python 2, 128 bytes

from PIL import*
a=Image.open('a')
b=a.load()
c,d=a.size
a.putdata(sorted(b[e,f]for f in range(d)for e in range(c)))
a.save('b')

Provided the image is a file named a with no extension, the output will be a file named b with no extension.

American Gothic American Gothic (sorted)

\$\endgroup\$
  • \$\begingroup\$ I haven't checked, but you should be able to do something along the lines of a.putdata(sorted(b[f/c,f%d]for f in range(d*c))) instead (I just woke up, so I may have mixed up the variables). \$\endgroup\$ – Kade Nov 5 '15 at 14:19
  • \$\begingroup\$ As you wrote it, it didn't work (index out of range), but I haven't tried switching around any variables (I don't have much time at the moment). @Shebang \$\endgroup\$ – Zach Gates Nov 5 '15 at 14:40
3
\$\begingroup\$

Java, 316 bytes

import javax.imageio.*;class C{public static void main(String[]a)throws Exception{java.awt.image.BufferedImage i=ImageIO.read(new java.io.File(a[0]));int w=i.getWidth(),h=i.getHeight(),v[]=i.getRGB(0,0,w,h,null,0,w);java.util.Arrays.sort(v);i.setRGB(0,0,w,h,v,0,w);ImageIO.write(i,"png",new java.io.File("a.png"));}}

Places the hexadecimal values of the pixel colors in an array. The array is sorted, and the colors are remapped to the pixels in the image. The name of the resulting image is a.png.

yellow tulips input yellow tulips output
American Gothic input enter image description here

\$\endgroup\$
3
\$\begingroup\$

SmileBASIC, 39 35 bytes

Assuming the image is loaded onto the 512*512 graphics page:

DIM A[0]GSAVE A,0SORT A
GLOAD A,0,1

Explained:

DIM IMG[0] 'create array
GSAVE IMG,0 'save graphics to array
SORT IMG 'sort
GLOAD IMG,0,1 'load graphics from array

It's that simple! Unfortunately we have to use integers, which adds 4 bytes to the program size due to the type suffixes.

\$\endgroup\$
  • \$\begingroup\$ I'm not really sure why ints are required. It seems like using floats actually gets the results correct. Running this code using ints on SYS/DEFSP.GRP puts a FF000000 in the top left and a 00101010 in the bottom right, which is the apparent opposite of the question. Using floats puts 00000000 in the top left and FFF8F8F8 in the bottom right, which is correct. (Of course, this treats the hex colors as unsigned/higher channel greater, which is probably correct.) \$\endgroup\$ – snail_ Apr 13 at 8:19
  • \$\begingroup\$ I think that's valid, since the question doesn't specify a specific order to sort by (and since the values are signed, 0xFF000000 is smaller than 0x00101010) but anyway, I'm not actually sure why I used integers here... I think at the time I didn't understand how GLOAD used unsigned values when you used a float array, and just assumed it didn't work. \$\endgroup\$ – 12Me21 Apr 13 at 11:48
2
\$\begingroup\$

Java, 424 417 404 bytes

Well, this is not a language you want to golf in...

import java.awt.image.*;import java.io.*;import javax.imageio.*;class F{public static void main(String[]x)throws Exception{BufferedImage i,o;i=ImageIO.read(new File(x[0]));o=new BufferedImage(i.getWidth(),i.getHeight(),BufferedImage.TYPE_INT_RGB);o.setData(i.getRaster());int[]p=((DataBufferInt)o.getRaster().getDataBuffer()).getData();java.util.Arrays.sort(p);ImageIO.write(o,"png",new File("o.png"));}}
\$\endgroup\$
2
\$\begingroup\$

C#, 497 bytes

First time post, first golf. Clearly not the best for golfing

Not really respecting the piping. Takes an image path as an input and outputs it with letter "o" prepend to the name.

Works better with bitmaps, odds results with others

using System.Linq;using System.Drawing;using System.Runtime.InteropServices;class Program{static void Main(string[]args){using(var im=(Bitmap)Image.FromFile(args[0])){int h=im.Height;int w=im.Width;var b=im.LockBits(new Rectangle(0,0,w,h),System.Drawing.Imaging.ImageLockMode.ReadWrite,System.Drawing.Imaging.PixelFormat.Format32bppRgb);var p=new int[h*w];Marshal.Copy(b.Scan0,p,0,h*w);var q=p.ToList();q.Sort();p=q.ToArray();Marshal.Copy(p,0,b.Scan0,h*w);im.UnlockBits(b);im.Save("o"+args[0]);}}}
\$\endgroup\$
1
\$\begingroup\$

Haskell, 195 bytes

import Data.List
import Graphics.GD
f p=do 
 a<-loadPngFile p;(x,y)<-imageSize a;let l=[(i,j)|j<-[0..y],i<-[0..x]]
 mapM(flip getPixel a)l>>=mapM(\(d,c)->setPixel d c a).zip l.sort;savePngFile"o"a

This uses the GD library. Usage f <filename>. The input file must be in png format. The output file is named o.

How it works: straightforward, i.e. read the picture, walk over all coordinates and get the pixels, sort the pixels, walk over the coordinates again, but this time set the pixels in the order they appear in the sorted list, write the file to disk.

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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