Using Algodoo and Paint I made these six 300×300 monochromatic images of four convenient shapes:

Image 1 Image 2 Image 3 Image 4 Image 5 Image 6

This class of images has the following properties:

  • They are always 300×300 pixels, monochromatic (black and white only), and have exactly four white regions that correspond to a square, a circle, a triangle, and a gear.
  • The shapes never overlap or touch each other, nor do they touch the image border or go out of bounds.
  • The shapes always have the same size, but they may be rotated and positioned in any way.

(The shapes also have equal areas, though when rastered like this their pixel counts are unlikely to be exactly equivalent.)


Write the shortest program or function possible that takes in the filename of such an image and turns all the white pixels...

  • red (255, 0, 0) if they are in the square.
  • blue (0, 0, 255) if they are in the circle.
  • green (0, 255, 0) if they are in the triangle.
  • yellow (255, 255, 0) if they are in the gear.


Image 1 colored in


Your program should work for effectively all possible input images. (Only valid 300×300 monochromatic images will be input.) The six images I have provided are merely examples, you may not hardcode their output into your program.

You may not use computer vision libraries or functions, built-in or external. The point is to do this using your own pixel-level operations. You may use image libraries that simply let you open and modify images (e.g. PIL for Python).

You may use any common lossless image file formats for input and output as long as you stick to the color scheme.

You can take in the image filename as a function argument, from stdin, or from the command line. The output image can be saved to a new file, the same file, or simply displayed.


The submission with the fewest bytes wins. I may test submissions with additional images to determine their validity.

  • May we assume the input is black & white with no anti-aliasing? If not, may we remove anti-aliasing from anti-aliased inputs? – John Dvorak Nov 1 '14 at 7:29
  • @JanDvorak Yes. By monochromatic I mean black and white only, so there can't be anti-aliasing. – Calvin's Hobbies Nov 1 '14 at 7:32
  • 1
    May we require a specific input format more precisely than just a file extension? Namely, I'd like me an ASCII PBM input without any comments inside. – John Dvorak Nov 1 '14 at 7:42
  • 12
    So... I was trying to solve this, and I ended up with this image. Not really sure how, but hey, it looks fancy. :P – Doorknob Nov 1 '14 at 14:11
  • 2
    I don't want to post my solution as it's the same idea as Ell's but worse. But I just want to say this was an enjoyable little challenge to do :) – Chris Burt-Brown Nov 1 '14 at 19:53
up vote 8 down vote accepted

J - 246,224 185 bytes

(viewmat~0,(255*4 3$_2|.#:3720)/:/:@(<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,))@(~.@,i.])@(>./**@{.)@((0,(,-)#:>:i.3)&|.)^:_@(*i.@:$)@(0<readimg_jqtide_)

This was a fun one!

I reused the connected-components part I used for the "Am I in the biggest room" challenge, and used the ratio between average and maximum distance of all points to each component's center. I settled for this, as it's both scale and rotation invariant, and apparently good enough to distinguish between the shapes as given. Ranking this value from low to high gives me the order circle, gear, square and triangle, used to permute the colormap.

Displays the result using the viewmap addon. No toolboxes used except for file reading and output.

Robustness does not seem to be a requirement, this takes off 18 bytes. 2 more unnecessary spaces, replaced &.> by &> in ratio and &.: by &: in dcent for another 2 bytes.

Huge gain in both shortness and performance of comp using shifting instead of cut (;.). This way the image is replicated and shifted in all 8 directions instead of scanning it with a 3x3 window.

The id function was ridiculously complex for what it needed to do. Now it assigns id's to pixels in objects by multiplying the image with an array of unique numbers, hence setting the BG to zero.

Code a bit more explained:

load'viewmat'                                 NB. display only
imnames =: < ;. _2 (0 : 0)

images =: (0<readimg_jqtide_) each imnames    NB. read all images in boxed array

id =: *i.@:$                                  NB. NB. assign one number to each non-background (non-zero) pixel
comp =: (>./ * *@{.)@shift^:_@id              NB. 8 connected neighbor using shift
  shift =: (>,{,~<0 _1 1)&|.                  NB. generate the original, and 8 shifted versions (automatically padding and cropping).
result =: comp each images                    NB. Execute comp verb for each image
col =: (~.@, i. ])                            NB. Color: give each component and BG a separate color.

NB. BG in 0, 0 Get all max distance to center % mean distance to center ratios
ratio  =: (< ([:}.rat@:dcent@getInd &>)  <"0@~.@,)
  getInd =: 4 $. $.@:=                        NB. get indices for component y in array x
  dcent  =: +/&.:*:@(-"1) +/%#                NB. distence from center each point
  rat    =: >./ % +/%#                        NB. ratio from distances

cm=: (255*4 3$_2|.#:3720)                     NB. colormap (except black).
(viewmat~ 0,cm /: /:@ratio )@col each result  NB. for each image, show the result, permuting the colormap according to ratio's

NB. almostgolf this
P1 =: (>./**@{.)@((0,(,-)#:>:i.3)&|.)^:_@(*i.@:$)@(0<readimg_jqtide_) NB. reading till components
P2 =: (<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,) NB. recognition: get fraction mean vs max distance to center per component, toss BG.     
P3 =: (viewmat~0,(255*4 3$_2|.#:3720)/:/:@P2)@(~.@,i.])@P1    NB. piece together : permute colormap, display components

NB. seriousgolf
f =:(viewmat~0,(255*4 3$_2|.#:3720)/:/:@(<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,))@(~.@,i.])@((>./**@{.)@shift^:_)@(*i.@:$)@(0<readimg_jqtide_)
NB. example usage:
f&> imnames NB. do for all images

This one is a bit long to explain in detail, but will do if there is interest.

  • The upper right pixel is guaranteed to be bg. As per the OP "The shapes never overlap or touch each other, nor do they touch the image border or go out of bounds." – Dr. belisarius Nov 6 '14 at 4:25
  • Thanks, that's helpful. (actually I meant left upper pixel, the first in the ravel). This shaves off the background detection (22 bytes). – jpjacobs Nov 6 '14 at 8:30
  • Dramatically reduced length, and increased performance :) – jpjacobs Nov 6 '14 at 14:21

Mathematica, 459 392 bytes



f = (
 d = ImageData@Import@# /. {a_, _, _} :> a;
    For[a = {}; b = {# & @@ d~Position~1},
     b != {},
     c = # & @@ b;
     b = Rest@b;
     d[[## & @@ c]] = 0;
     If[Extract[d, c + #] == 1, 
        b = b ⋃ {c + #}] & /@ {e = {1, 0}, -e, e = {0, 1}, -e}
    m = 1. Mean@a; m = # - m & /@ a;
    n = 
     Count[Partition[Norm /@ SortBy[m, ArcTan @@ # &], 300, 1, 1], 
      l_ /; l[[150]] == Max@l];
    (d[[## & @@ #]] = Round[n^.68]) & /@ a
    ) & /@ Range@4;
 Image[d /. 
   n_Integer :> {{0, 0, 0}, , {0, 1, 0}, {1, 0, 0}, , , , {1, 1, 
       0}, {0, 0, 1}}[[n + 1]]]
) &

I could save 6 more bytes by turning m=1.Mean@a;m=#-m&/@a; into m=#-Mean@a&/@a;, but that significantly blows up execution time, which is annoying for testing. (Note, that this is two optimisations: pulling out the computation of Mean@a out of loop and using exact symbolic types instead of floating point numbers. Interestingly, the use of exact types is a lot more significant than computing the mean in every iteration.)

So this is approach number three:

  • Detect areas by flood-fill.
  • Find approximate centre of each area by averaging all pixel coordinates.
  • Now for all pixels in the shape let's plot distance from vs angle to that centre:

    enter image description here

    The triangle has 3 clear maxima, the square 4, the gear 16, and the circle has tons, due to aliasing fluctuations about the constant radius.

  • We find the number of maxima by looking at slices of 300 pixels (ordered by angle), and count the slices where the pixel at position 150 is the maximum.
  • Then we just colour all pixels depending on the number of peaks (the circle is anything over 16, and usually yields around 20 peaks, due to the size of the slices).

Just for the record, if I use Ell's idea, and simply sort the regions by largest distance between any pixel and centre, I can do this in 342 bytes:


But I do not intend to compete with that, as long as everyone else is using their own original algorithms, instead of golfing down those of others.

  • The most interesting solution! – CSharpie Nov 5 '14 at 21:55

Java, 1204 1132 1087 1076

Just to prove to myself that I can do this.

I included imports right next to the function declarations; these would have to be outside the class for this to work:

import java.awt.*;import java.awt.image.*;import*;import java.util.*;import javax.imageio.*;

BufferedImage i;Set<Point>Q;void p(String a)throws Exception{i=new BufferedImage(302,302,1);i.getGraphics().drawImage( File(a)),1,1,null);Set<Set<Point>>S=new HashSet<>();for(int y=0;y<300;y++){for(int x=0;x<300;x++){if(!G(x,y)){Point p=new Point(x,y);Q=new HashSet<>();if(!>s.contains(p)))S.add(f(x,y));}}}Object[],P)->c(p)-c(P)).toArray();s(o[0],255);s(o[1],255<<16);s(o[2],0xFF00);s(o[3],0xFFFF00);ImageIO.write(i.getSubimage(1,1,300,300),"png",new File(a));}boolean G(int x,int y){return i.getRGB(x,y)!=-1;}Set<Point>f(int x,int y){Point p=new Point(x,y);if(!Q.contains(p)&&!G(x,y)){Q.add(p);f(x-1,y);f(x+1,y);f(x,y-1);f(x,y+1);}return Q;}int c(Set<Point>s){return(int)>G(p.x-2,p.y-1)||G(p.x-2,p.y+1)||G(p.x+1,p.y-2)||G(p.x-1,p.y-2)||G(p.x+2,p.y-1)||G(p.x+2,p.y+1)||G(p.x+1,p.y+2)||G(p.x-1,p.y+2)).count();}void s(Object o,int c){((Set<Point>)o).stream().forEach(p->{i.setRGB(p.x,p.y,c);});}

Ungolfed (and runnable; ie boilerplate added):

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.util.HashSet;
import java.util.Set;
import javax.imageio.ImageIO;

public class SquareCircleTriangleGear {
    public static void main(String[]args){
        try {
            new SquareCircleTriangleGear().p("filepath");
        } catch (Exception ex) {
    BufferedImage i;
    void p(String a)throws Exception{
        i = new BufferedImage(302,302,BufferedImage.TYPE_INT_RGB);
        i.getGraphics().drawImage( File(a)),1,1,null);
        Set<Set<Point>>set=new HashSet<>();
        for(int y=0;y<300;y++){
            for(int x = 0;x<300;x++){
                    Point p = new Point(x,y);
                    Q=new HashSet<>();
        ImageIO.write(i.getSubImage(1,1,300,300), "png", new File(a));
    Set<Point>fill(int x, int y){
        Point p=new Point(x,y);
        if(!Q.contains(p)&&!i.getRGB(x,y)!=-1) {
        return Q;
    int c(Set<Point>s){return (int)>isBoundary(p.x,p.y)).count();}
    boolean isBoundary(int x, int y){
        return i.getRGB(x-2,y-1)!=-1||i.getRGB(x-2,y+1)!=-1||i.getRGB(x+1,y-2)!=-1||
    void s(Object o,int c){

This works by iterating over every pixel of the image and flood-filling each time we reach a "hole". We add each flood-fill result as a Set<Point> to a Set. Then we determine which shape is which. This is done by looking at the number of boundary pixels of the shape. I defined boundary as a knight's move away from a black tile, since that would stay more constant between rotations and such. When we do this, it becomes clear that the shapes can be sorted by that value: Circle, Square, Triangle, Gear. So I sort and set all pixels of that shape to the correct color.

Note that the image I'm writing to is not directly taken from the file, because if I were to do that, Java would treat the image as black and white and filling with colors wouldn't work. So I have to create my own image with TYPE_INT_RGB (which is 1). Also note that the image I'm doing work on is 302 by 302; this is so that the Knight's distance algorithm doesn't need to worry about attempting to read out-of-bounds on the image. I fix this discrepancy in size by calling i.getSubImage(1,1,300,300). Note: I may have forgotten to fix this when I uploaded the images, in which cases the images are 2 pixels too wide, but except for this fact, they should be correct

The function will overwrite the file whose path is passed in. Outputs:

enter image description here enter image description here enter image description here enter image description here

  • Can save a few characters by shortening the class name as well as args in the main method to "a" or similar. – Ryan Nov 1 '14 at 19:05
  • @Ryan Those aren't counted in the count. I only count the imports + the functions, as allowed by the question. – Justin Nov 1 '14 at 19:09
  • I think I may be able to get this under 1000 bytes. Must work on this later when there is time to try. – Justin Nov 2 '14 at 0:25

Python, 571 567 528 bytes

Similarly to Quincunx's solution, it starts by flood-filling each shape with an index from 1 to 4. It then determines the identity of the shapes by the radius of their bounding circle. A color-palette is constructed accordingly and the image is saved as an indexed-color image.

EDIT: Missed the fact the shapes are guaranteed not to touch the image border. Shorter it is, then!

from PIL.Image import*;from numpy import*
O=[[0,i,array([0,0])]for i in N];n=0
for i in R:
 if D[i]>4:
    while S:
     if D[j]>4:D[j]=n;O[n][0]+=1;O[n][2]+=j%W,j/W;S+=[j+1,j-1,j+W,j-W]
for o in O[1:]:o[2]/=o[0];o[0]=0
for i in R:
 if D[i]:o=O[D[i]];v=(i%W,i/W)-o[2];o[0]=max(o[0],dot(v,v))
for i in N:j=3*O[i][1];P[j:j+3]=C[3*i:3*i+3]

Takes an input filename on the command line and writes the output to o.png.

  • 2
    Argh, that's so much simpler than what I'm trying to do. +1 – Martin Ender Nov 1 '14 at 13:29

Mathematica 225


The OP decided that this approach uses computer vision functions, so it's no longer in the running. I'll leave it posted however. Perhaps someone may find it of interest.

f@i_ := (m = MorphologicalComponents[ImageData@i];
Image@Partition[Flatten[(m)] /. 
   Append[ ReplacePart[SortBy[ComponentMeasurements[m, "Circularity"], Last], 
   {{1, 2} -> Yellow, {2, 2} -> Green, {3, 2} -> Red, {4, 2} -> Blue}], 0 -> Black], 

ImageData returns the image as a matrix of 0's and 1's.

Flatten converts that matrix to a list.

Morphological Components finds the 4 clusters of pixels and assigns a distinct integer, 1, 2, 3, 4 to each pixel according to the cluster. 0 is reserved for the (black) background.

ComponentMeasurements tests the circularity of the clusters.

From most to least circular will always be: the circle, the square, the triangle, and the gear.

ReplacePart replaces each component integer with the respective RGB color, using the circularity sort.

Partition...Dimensions[m][[2]] takes the list of pixel colors, and returns a matrix the same dimensions as the input image.

Image converts the matrix of pixel colors to a colored image.




  • 147 chars: f@i_:=Image[#/.Append[Thread[Ordering[Last/@ComponentMeasurements[#,"Circularity"]]->{Yellow,Green,Red,Blue}],0->Black]]&@MorphologicalComponents@i – alephalpha Nov 4 '14 at 3:45
  • Minor point: your colors don't have the correct rgb values. Major point: I'm not sure I'd count this as not using computer vision libraries or functions. – Calvin's Hobbies Nov 4 '14 at 3:58
  • "Circularity" is arguably visual; I'll see what else I can do. The colors are, however, dead on: {RGBColor[1, 0, 0], RGBColor[0, 1, 0], RGBColor[0, 0, 1], RGBColor[1, 1, 0]}, where 1 corresponds to 255. No libraries were used. – DavidC Nov 4 '14 at 4:19
  • @Calvin'sHobbies The issue seems to come down to whether MorphologicalComponents satisfies or violates your rules. Once one knows which cluster each pixel belongs to, there are many ways, including a raw count of pixels, to determine which figure is which. – DavidC Nov 4 '14 at 4:53
  • I'm going to say that it does violate the rules, as it is very arguably a computer vision function, and it gives Mathematica an unfair advantage. I agree that the colors should be correct but they plainly look off in your image (red is (255,0,22) when I check in Paint). I don't have Mathematica so I can't run to make sure. – Calvin's Hobbies Nov 4 '14 at 8:03

Mathematica, 354 345 314 291 288

Still golfing, could be shortened by a few more chars, but performance becomes unbearable. Uses the Variance to identify shapes:

f=(w=Position[z=ImageData@Import@#,1];r=Nearest;v@x_:=Variance@N[Norm[Mean@x-#]&/@x];Image[Plus@@(ReplacePart[0z/. 0->{0,0,0},#->r[{108,124,196,115}->List@@@{Blue,Red,Green,Yellow},v@#][[1]]]&/@Rest@NestList[(m=r[w=w~Complement~#];FixedPoint[Union@@(m[#,{8,2}]&/@#)&,{#&@@w}])&,{},4])])&

With spacing:

f = (w = Position[z = ImageData@Import@#, 1];
     r = Nearest; 
     v@x_ := Variance@N[Norm[Mean@x - #] & /@ x];
     Image[Plus @@ (ReplacePart[ 0 z /. 0 -> {0, 0, 0}, # -> r[{108, 124, 196, 115} -> 
                                              List @@@ {Blue, Red, Green, Yellow}, v@#][[1]]] & /@
     Rest@NestList[(m = r[w = w~ Complement~#];
                   FixedPoint[Union @@ (m[#, {8, 2}] & /@ #) &, {# & @@ w}]) &
                   , {}, 4])]) &


s = {"", "", 
     "", "", 
     "", ""};
Partition[f /@ s, 3] // Grid

Mathematica graphics

Here it is completely ungolfed. Will add explanations later:

findOneZone[{universe_List, lastZone_List}] :=
 Module[{newUniverse, proximityFindFunc, seedElement},
  newUniverse = Complement[universe, lastZone];
  proximityFindFunc = Nearest@newUniverse;
  seedElement = {First@newUniverse};
  {newUniverse, FixedPoint[Union @@ (proximityFindFunc[#, {8, 2}] & /@ #) &, seedElement]}]

colorAssign[zone_List] :=
   vlist = {108, 124, 196, 115},
   cols = List @@@ {Blue, Red, Green, Yellow},
  centerVariance[x_List] := Variance@N[Norm[Mean@x - #] & /@ x];
  First@Nearest[vlist -> cols, centerVariance@zone]]

colorRules[zones_List] := (# -> colorAssign[#] & /@ zones)

main[urlName_String] := 
 Module[{pixels, FgPixelPositions, rawZones, zones},
  pixels = ImageData@Import@urlName;
  FgPixelPositions = Position[pixels, 1];
  (*fill and separate the regions*)
  rawZones = NestList[findOneZone[#] &, {FgPixelPositions, {}}, 4];
  zones = Rest[rawZones][[All, 2]];
  (*Identify,colorize and render*)
  Image@ReplacePart[ConstantArray[{0, 0, 0}, Dimensions@pixels], 

s = {""};
main /@ s

Python, 579 577 554 514 502 501 bytes

For each shape, flood-fills it, then compute the distance between the centroid and the farthest point.

then the real surface of the shape is compared to the surface of a triangle, square, disc or wheel that would have the same size.

import math;from PIL.Image import*;A,R,_,I=abs,range(300),255,open(sys.argv[1]).convert('P');Q=I.load()
for j in R:
 for i in R:
  if Q[i,j]==_:
   while p:
    if not(Q[n]!=_ or n in z):
   r=max([math.hypot(X/s-x,Y/s-y) for x,y in z]);C={1:A(s-(1.4*r)**2),2:A(s-r*r/3),3:A(s-math.pi*r*r),4:A(s-2.5*r*r)}
   for p in z:

C# 1086 bytes

Yet another floodfill-solution, just for the record since there is no C# version here. Like Quincunx i wanted to prove myself that I can do it and there is not much differnce to his approach in Java.

  • This solution does not use any recursion (but a stack) because i kept running into StackOverflows.
  • The detection of borderpixels is simplified by looking at the 4 next pixels, if any of those is black, the current is a border pixel.

It accepts every imageformat.

  • Parameter 1 = InputPath
  • Parameter 2 = OutputPath

It probably can be stripped down a few charachters by removing all the static stuff and creating an instance of Program.

Readable Version:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

class Program
    static Bitmap img;
    static int w, h;
    static ISet<Point> pointsDone = new HashSet<Point>();
    static void Main(string[] a)
        img = new Bitmap(a[0]);
        w = img.Width;
        h = img.Height;
        Bitmap clone = new Bitmap(w,h, PixelFormat.Format32bppArgb);
        Graphics.FromImage(clone).DrawImage(img, 0, 0, w, h);
        img = clone;

        Color[] colors = new[] { Color.Blue, Color.Red, Color.Green, Color.Yellow };

        var shapes = new List<ISet<Tuple<bool, Point>>>();
        for(int x=0;x<w;x++)
            for (int y = 0; y < h; y++)
                Point p = new Point(x, y);
                if (pointsDone.Add(p) && _isWhitePixel(p))
        int index = 0;
        foreach (var shp in shapes.OrderBy(shp => shp.Count(item => item.Item1)))
            foreach (var pixel in shp)
                img.SetPixel(pixel.Item2.X, pixel.Item2.Y, colors[index]);


    private static ISet<Tuple<bool, Point>> _detectShape(Point p)
        var todo = new Stack<Point>(new[] { p });
        var shape = new HashSet<Tuple<bool, Point>>();
            p = todo.Pop();
            var isBorderPixel = false;
            foreach (var n in new[] { new Point(p.X + 1, p.Y), new Point(p.X - 1, p.Y), new Point(p.X, p.Y + 1), new Point(p.X, p.Y - 1) })
                if (_isWhitePixel(n))
                    if (pointsDone.Add(n))
                else isBorderPixel = true; // We know we are at the border of the shape
            shape.Add(Tuple.Create(isBorderPixel, p));

        } while (todo.Count > 0);
        return shape;

    static bool _isWhitePixel(Point p)
        return img.GetPixel(p.X, p.Y).ToArgb() == Color.White.ToArgb();


using System;using System.Collections.Generic;using System.Drawing;using System.Drawing.Imaging;using System.Linq;class P{static Bitmap a;static int w,h;static ISet<Point> d=new HashSet<Point>();static void Main(string[] q){a=new Bitmap(q[0]);w=a.Width;h=a.Height;var c=new Bitmap(w,h,PixelFormat.Format32bppArgb);Graphics.FromImage(c).DrawImage(a,0,0,w,h);a=c;var e=new[]{Color.Blue,Color.Red,Color.Green,Color.Yellow};var f=new List<ISet<dynamic>>();for(int x=0;x<w;x++)for(int y=0;y<h;y++){Point p=new Point(x,y);if (d.Add(p)&&v(p))f.Add(u(p));}int i=0;foreach(var s in f.OrderBy(s=>s.Count(item=>item.b))){foreach(var x in s)a.SetPixel(x.p.X,x.p.Y,e[i]);i++;}a.Save(q[1]);}private static ISet<dynamic> u(Point p){var t=new Stack<Point>(new[]{p});var s=new HashSet<dynamic>();do{p=t.Pop();var b=false;foreach(var n in new[]{new Point(p.X+1,p.Y),new Point(p.X-1,p.Y),new Point(p.X,p.Y+1),new Point(p.X,p.Y-1)})if(v(n)){if (d.Add(n))t.Push(n);}else b=true;s.Add(new{b,p});}while (t.Count>0);return s;}static bool v(Point p){return a.GetPixel(p.X,p.Y).ToArgb()==Color.White.ToArgb();}}

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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