title: Tracing the Hues of an Image

text:
# Question
Title: Tracing the Hues of an Image
Load an image into this stack snippet and move your mouse over it. A black curve that follows the hue angle, starting at your cursor point, will be drawn:

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><style>canvas{border:1px solid black;}</style>Load an image: <input type='file' onchange='load(this)'><br><br>Max length <input id='length' type='text' value='300'><br><br><div id='coords'></div><br><canvas id='c' width='100' height='100'>Your browser doesn't support the HTML5 canvas tag.</canvas><script>function load(t){if(t.files&&t.files[0]){var e=new FileReader;e.onload=setupImage,e.readAsDataURL(t.files[0])}}function setupImage(t){function e(t){t.attr("width",img.width),t.attr("height",img.height);var e=t[0].getContext("2d");return e.drawImage(img,0,0),e}img=$("<img>").attr("src",t.target.result)[0],ctx=e($("#c")),ctxRead=e($("<canvas>"))}function findPos(t){var e=0,a=0;if(t.offsetParent){do e+=t.offsetLeft,a+=t.offsetTop;while(t=t.offsetParent);return{x:e,y:a}}return void 0}$("#c").mousemove(function(t){function e(t,e){var a=ctxRead.getImageData(t,e,1,1).data,i=a[0]/255,r=a[1]/255,o=a[2]/255;return Math.atan2(Math.sqrt(3)*(r-o),2*i-r-o)}if("undefined"!=typeof img){var a=findPos(this),i=t.pageX-a.x,r=t.pageY-a.y;$("#coords").html("x = "+i.toString()+", y = "+r.toString());var o=parseInt($("#length").val());if(isNaN(o))return void alert("Bad max length!");for(var n=[i],f=[r],h=0;n[h]>=0&&n[h]<this.width&&f[h]>=0&&f[h]<this.height&&o>h;)n.push(n[h]+Math.cos(e(n[h],f[h]))),f.push(f[h]-Math.sin(e(n[h],f[h]))),h++;ctx.clearRect(0,0,this.width,this.height),ctx.drawImage(img,0,0);for(var h=0;h<n.length;h++)ctx.fillRect(Math.floor(n[h]),Math.floor(f[h]),1,1)}});</script>
```

I've only tested this snippet in Google Chrome.

For example, when the cursor is above red, the curve has a 0° slope, but when it's above yellow, it has a 60° slope. The curve continues on for the specified length, continuously changing its slope to match the hue.

Load up this image and when you pan the cursor across it, the line just around the cursor should do a complete counter-clockwise turn:

This and this are other neat images to try. (You'll need to save them and then load them with the snippet. They can't be directly linked due to cross-origin constraints.)

Here is a non-minified version of the snippet:

```
function load(i) { //thanks http://jsfiddle.net/vacidesign/ja0tyj0f/
    if (i.files && i.files[0]) {
        var r = new FileReader()
        r.onload = setupImage
        r.readAsDataURL(i.files[0])
    }
}

function setupImage(e) {
    img = $('<img>').attr('src', e.target.result)[0]
    function setup(c) {
        c.attr('width', img.width)
        c.attr('height', img.height)
        var ctx = c[0].getContext('2d')
        ctx.drawImage(img, 0, 0)
        return ctx
    }
    ctx = setup($('#c'))
    ctxRead = setup($('<canvas>'))
}

function findPos(obj) {
    var curleft = 0, curtop = 0;
    if (obj.offsetParent) {
        do {
            curleft += obj.offsetLeft;
            curtop += obj.offsetTop;
        } while (obj = obj.offsetParent);
        return { x: curleft, y: curtop };
    }
    return undefined;
}

$('#c').mousemove(function(e) { //thanks http://stackoverflow.com/a/6736135/3823976
    if (typeof img === 'undefined') return
    var pos = findPos(this)
    var x = e.pageX - pos.x
    var y = e.pageY - pos.y
    $('#coords').html('x = ' + x.toString() + ', y = ' + y.toString())
    var maxLength = parseInt($('#length').val())
    if (isNaN(maxLength)) {
        alert('Bad max length!')
        return
    }

    function hue(x, y) {
        var rgb = ctxRead.getImageData(x, y, 1, 1).data
        var r = rgb[0] / 255, g = rgb[1] / 255, b = rgb[2] / 255
        return Math.atan2(Math.sqrt(3) * (g - b), 2 * r - g - b)
    }

    //gather points
    var xs = [x], ys = [y]
    var i = 0
    while (xs[i] >= 0 && xs[i] < this.width && ys[i] >= 0 && ys[i] < this.height && i < maxLength) {
        xs.push(xs[i] + Math.cos(hue(xs[i], ys[i])))
        ys.push(ys[i] - Math.sin(hue(xs[i], ys[i])))
        i++
    }

    //draw stuff
    ctx.clearRect(0, 0, this.width, this.height)
    ctx.drawImage(img, 0, 0)
    for (var i = 0; i < xs.length; i++)
        ctx.fillRect(Math.floor(xs[i]), Math.floor(ys[i]), 1, 1) //not using strokes because they may be anti-aliased
})
```

```
canvas {
  border:1px solid black;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Load an image: <input type='file' onchange='load(this)'>
<br><br>
Max length <input id='length' type='text' value='300'>
<br><br>
<div id='coords'></div>
<br>
<canvas id='c' width='100' height='100'>Your browser doesn't support the HTML5 canvas tag.</canvas>
```

# Challenge

Write a program that does what the snippet is doing, just not interactively. Take an image and an (x, y) coordinate in the bounds of image, and a maximum curve length. Output the same image with the added black curve that follows the hue angles starting at (x, y) and ends when it reached the maximum length or hits an image boundary.

Specifically, start the curve at (x, y) and measure the hue angle there. Go one unit (one pixel's width) in that direction, **noting that your new position is most likely not an integer coordinate**. Mark another point on the curve and move again, using the hue from the closest pixel (using something like `floor` or `round`, I won't be checking this precisely). Continue on like this until the curve goes out of bounds or it exceeds the maximum length. To finish, plot all the curve points as single black pixels (again, use nearest pixels) overlayed on the image, and output this new image.

The "hue angle" is just the hue:

```
hue = atan2(sqrt(3) * (G - B), 2 * R - G - B)

```

Note that for grayscale values that don't technically have a hue, this returns 0, but that's fine.

(This formula uses `atan2` which most built-in math libraries have. R, G, B are from 0 to 1, not 0 to 255.)

* You can use any common lossless image file format as well as any image libraries.
* Take input from stdin or the command line, or write a function with arguments for the image file name, x and y, and the max length.
* The max length and x and y are always nonnegative integers. You can assume x and y are in range.
* Save the output image with a name of your choice or simply display it.
* Your implementation does not have to exactly match the snippet. A few pixels in slightly different places due to a slightly different rounding/calculation method is fine. (In chaotic cases this could lead to curves that end up majorly different, but as long as they look correct visually, it's fine.)

# Scoring

The smallest submission in bytes wins.

# Answer
> 2 votes
# MATLAB, 136

```
function t(g,x,y,l)
m=imread(g);imshow(m); h=2*pi*rgb2hsv(m);h=h(:,:,1);s=streamline(cos(h),-sin(h),x,y,[1,l]);set(s,'LineW',1,'Co','k');

```

Copied most of the setup and such from @sanchises, but I instead use `streamline` to compute and draw the path. It does antialias the line though, and uses bilinear interpolation, rather than nearest-neighbor as specified.

# Answer
> 5 votes
# C with SDL, ~~549~~ 516 bytes

I'll start this party! For some reason, I felt like trying my hand at golf tonight. What you guys do is hard... If there's one thing I don't see any of on this site, it's SDL. I may have just found out why. This particular snippet complies with both SDL2 and SDL1.2, but is atrocious. Called like `f("imagename.bmp", xcoord, ycoord, max_length);`. It saves a file with the same name as given in the arguments. Output seems to be very similar to the OP's code snippet, but "fuzzier." I may try to fix this up a bit later.

```
#include"SDL.h"
f(char*C,x,y,m){SDL_Surface*P=SDL_LoadBMP(C);int p=P->pitch,i=P->format->BytesPerPixel,q=0;double X=x,Y=y,f=255,R,G,B,h;Uint8*Q,d=1,r,g,b,k;while(d){Q=P->pixels+y*p+i*x;SDL_GetRGB(i==4?*(Uint32*)Q:i==3?SDL_BYTEORDER==4321?*Q<<16|Q[1]<<8|Q[2]:*Q|Q[1]<<8|Q[2]<<16:i==2?*(Uint16*)Q:*Q,P->format,&r,&g,&b);R=r/f;G=g/f;B=b/f;h=atan2(sqrt(3)*(G-B),2*R-G-B);for(k=0;k<i;k++)Q[k]=0;X+=cos(h);Y-=sin(h);if((int)X-x|(int)Y-y)q++;x=X;y=Y;d=x<0|x>=P->w|y<0|y>=P->h|q>=m?0:1;}SDL_SaveBMP(P,C);SDL_FreeSurface(P);}

```

Here it is all unraveled:

```
#include"SDL.h"
f(char*C,x,y,m){
    SDL_Surface*P=SDL_LoadBMP(C);
    int p=P->pitch,i=P->format->BytesPerPixel,q=0;
    double X=x,Y=y,f=255,R,G,B,h;
    Uint8*Q,d=1,r,g,b,k;
    while(d){
        Q=P->pixels+y*p+i*x;
        SDL_GetRGB(i==4?*(Uint32*)Q:i==3?SDL_BYTEORDER==4321?*Q<<16|Q[1]<<8|Q[2]:*Q|Q[1]<<8|Q[2]<<16:i==2?*(Uint16*)Q:*Q,P->format,&r,&g,&b);
        R=r/f;
        G=g/f;
        B=b/f;
        h=atan2(sqrt(3)*(G-B),2*R-G-B);
        for(k=0;k<i;k++)Q[k]=0;
        X+=cos(h);
        Y-=sin(h);
        if((int)X-x|(int)Y-y)q++;
        x=X;y=Y;
        d=x<0|x>=P->w|y<0|y>=P->h|q>=m?0:1;
    }
    SDL_SaveBMP(P,C);
    SDL_FreeSurface(P);
}

```

I should note that care was taken to make it cross platform--in the interest of honesty, it didn't feel good to hardcode it for my machine, even if it cut off a substantial number of bytes. Still, I feel like a couple things are superfluous here, and I'll look at it again later.

EDIT-------

This IS Graphical Output, after all... I'll update with images that I find interesting periodically.

`f("HueTest1.bmp", 270, 40, 200);`

`f("HueTest2.bmp", 50, 50, 200);`

`f("HueTest3.bmp", 400, 400, 300);`

# Answer
> 3 votes
# MATLAB, ~~186~~ 172

The game is **on**! Call as `t('YourImage.ext',123,456,100')`, for an image of any type MATLAB supports, starting at (x,y)=(123,456) and maximum length 100. Initial positions cannot be *exactly* at the right and bottom edges (that would cost me two bytes), so to start on the edge, use something like `x=799.99` to start at `x=800`. Indexing starts at 1, not 0.

Code:

```
function t(g,x,y,l)
m=imread(g);[Y,X,~]=size(m);h=2*pi*rgb2hsv(m);while(x>0&x<X&y>0&y<Y&l)
p=ceil(x);q=ceil(y);m(q,p,:)=0;a=h(q,p);x=x+cos(a);y=y-sin(a);l=l-1;end
imshow(m)

```

Revisions:

* Changed from line from previous to next pixel to just putting a dot at a pixel, since the line will never be longer than a pixel! ~~Still using `line` since that is the shortest code I know to produce a pixel.~~
* ~~Changed the color from black to blue, using `Co` to expand to `Color` (which MATLAB does automatically)~~
* Changed order of calculating next position and drawing a point, since I realized thanks to @grovesNL that I was actually drawing out of bounds since I was checking bounds *after* changing the position.
* Changed from drawing lines to setting rgb matrix to 0 and displaying after.

# Answer
> 3 votes
## Python, ~~203~~ 172

```
from scipy.misc import*
def f(i,x,y,l):
 a=imread(i);Y,X,_=a.shape;o=a.copy()
 while(X>x>0<y<Y<[]>l>0):r,g,b=a[y,x]/255.;o[y,x]=0;l-=1;x+=2*r-g-b;y-=3**.5*(g-b);imsave(i,o)

```

Sample output:

Call with `f("image.jpg", 400, 400, 300)`

I've wasted a lot of characters for the import, if anyone has suggestions to improve it. May not work in 3.0

# Answer
> 1 votes
## Processing, 323 characters

```
void h(String f,float x,float y,float m){PImage i=loadImage(f);PImage i2=loadImage(f);while(m>0){color c=i.get((int)x,(int)y);float r=red(c)/255;float g=green(c)/255;float b=blue(c)/255;float h=atan2(sqrt(3)*(g-b),2*r-g-b);float dx=cos(h);float dy=-sin(h);m-=1;x+=dx;y+=dy;i2.set((int)x,(int)y,color(0));}i2.save("o.png");}

```

With whitespace:

```
void h(String f, float x, float y, float m) {
  PImage i = loadImage(f);
  PImage i2 = loadImage(f);

  while (m > 0) {

    color c = i.get((int)x, (int)y);
    float r = red(c)/255;
    float g = green(c)/255;
    float b = blue(c)/255;
    float h = atan2(sqrt(3) * (g - b), 2 * r - g - b);

    float dx = cos(h);
    float dy = -sin(h);

    m-= 1;
    x += dx;
    y += dy;

    i2.set((int)x, (int)y, color(0));
  }

  i2.save("o.png");
}

```

I'm sure I could shorten this further, but it works for now.

# Answer
> 0 votes
# JavaScript 414

```
function P(G,x,y,l){
I=new Image()
I.onload=function(){d=document,M=Math,C=d.createElement('canvas')
d.body.appendChild(C)
w=C.width=I.width,h=C.height=I.height,X=C.getContext('2d')
X.drawImage(I,0,0)
D=X.getImageData(0,0,w,h),d=D.data,m=255,i=0
for(;l--;i=(w*~~y+~~x)*4,r=d[i]/m,g=d[i+1]/m,b=d[i+2]/m,H=M.atan2(M.sqrt(3)*(g-b),2*r-g-b),d[i]=d[i+1]=d[i+2]=0,x+=M.cos(H),y-=M.sin(H))
X.putImageData(D,0,0)}
I.src=G}

```

---
Tags: code-golf, graphical-output, image-processing
---


title: Infinite Labyrinths

text:
# Question
Title: Infinite Labyrinths
# Background

You are the apprentice of a powerful wizard, and your master is currently developing a spell for creating an inter-dimensional labyrinth to trap his enemies in. He wants you to program his steam-powered computer to analyze the possible layouts. Programming this diabolical machine is highly dangerous, so you'll want to keep the code as short as possible.

# Input

Your input is a two-dimensional grid of periods `.` and hashes `#`, signifying empty space and walls, given as a newline-delimited string. There will always be at least one `.` and one `#`, and you can decide whether there is a trailing newline or not.

This grid is the blueprint of an infinite labyrinth, which is made by aligning infinitely many copies of the grid next to each other. The labyrinth is divided into *cavities*, which are connected components of empty spaces (diagonally adjacent spaces are not connected). For example, the grid

```
##.####
...##..
#..#..#
####..#
##...##

```

results in the following labyrinth (continued infinitely in all directions):

```
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##

```

This particular labyrinth contains a cavity of infinite area. On the other hand, this blueprint results in a labyrinth with only finite cavities:

```
##.####
##..###
####...
..####.
#..####

```

# Output

Your output shall be a truthy value if the labyrinth contains an infinite cavity, and a falsy value if not. Note that the labyrinth may contain both finite and infinite cavities; in that case, the output shall be truthy.

# Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Additional Test Cases

Infinite cavities:

```
.#

#.#
...
#.#

#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#

##.###
#..###
..##..
###..#
##..##

..#..#..#..#..#..#
.#..#..#..#..#..#.
#..#..#..#..#..#..

#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####

```

Finite cavities:

```
###
#.#
###

.#
#.

####
.#..
####

#.#.#
..#..
#####
..#..
#.#.#

#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#

##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####

###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##

###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......

```

# Answer
> 2 votes
# JavaScript (ES6), 235 ~~253~~

Same method used by @mac. For each free cell, I try a recursive fill, marking used cells with the coordinate I am using (that can be outside the orginal template). If during the fill I arrive to a cell already marked having a different coordinate, I am in an infinite path.

The quirky way of handling the modulo in JS it's quite annoying.

```
L=g=>(
  g=g.split('\n').map(r=>[...r]),
  w=g[0].length,h=g.length,
  F=(x,y,t=((x%w)+w)%w,u=((y%h)+h)%h,v=g[u][t],k=0+[x,y])=>
    v<'.'?0:v>'.'?v!=k
    :[0,2,-3,5].some(n=>F(x+(n&3)-1,y+(n>>2)),g[u][t]=k),
  g.some((r,y)=>r.some((c,x)=>c=='.'&&F(x,y)))
)

```

**Test** In Firefox / FireBug console

*Infinite*

```
['##.###\n#..###\n..##..\n###..#\n##..##'
,'#.#\n...\n#.#'
,'#.###.#.###.#\n#.#...#...#.#\n#.#.#####.#.#\n..#.#...#.#..\n###.#.#.#.###\n#...#.#.#...#\n#.###.#.###.#'
,'##.###\n#..###\n..##..\n###..#\n##..##'
,'#.####.###.###.####\n#...#..#...###..###\n###.#..#.######..##\n....####.#######...\n###..###...########\n##########.##....##\n..###......##.##...\n#.........##..#####\n###########..###..#\n#...........####..#\n#.###########.##..#\n#.##....##.....####\n#.####.###.###.####'
].forEach(g=>console.log(g,L(g)))

```

*Output*

```
"##.###
#..###
..##..
###..#
##..##" true

"#.#
...
#.#" true

"#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#" true

"##.###
#..###
..##..
###..#
##..##" true

"#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####" true

```

*Finite*

```
['###\n#.#\n###', '.#\n#.', '####\n.#..\n####'
,'#.#.#\n..#..\n#####\n..#..\n#.#.#'
,'#.#.#.#.#.#\n..#...#.#..\n###.###.###\n..#.#......\n#.#.#######\n#.#.......#\n#.#######.#\n#.#.....#.#\n#.#.#.#.#.#'
,'##....#####\n.#..#...##.\n.##.#..#...\n..###.###..\n#..##.#####\n#...##....#\n#.#.#####.#\n###..####.#\n....####...\n###...#####'
,'###....##.#########\n####...##....#...##\n..####.#######.###.\n....##..........##.\n###..#####.#..##...\n####..#..#....#..##\n..###.####.#.#..##.\n..###...#....#.#...\n..####..##.###...##\n#.####.##..#####.##\n####...##.#####..##'
].forEach(g=>console.log(g,L(g)))

```

*Output*

```
"###
#.#
###" false

".#
#." false

"####
.#..
####" false

"#.#.#
..#..
#####
..#..
#.#.#" false

"#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#" false

"##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####" false

"###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##" false

```

# Answer
> 22 votes
# C# - ~~423~~ 375 bytes

Complete C# program, accepts input via STDIN, outputs "True" or "False" to STDOUT as appropriate.

I could not bare to leave that Linq in there... thankfully its removal paid off! It now keeps track of seen and visited cells in an array (given it only ever looks at a finite number of them anyway). I also re-wrote the directional code, removing the need for a Lambda, and generally making the code more impossible to understand (but with substantial byte savings).

```
using C=System.Console;struct P{int x,y;static void Main(){int w=0,W,k=0,o,i,j;P t;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;for(i=W=D.Length;i-->0&k<W;){k=1;P[]F=new P[W];for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W;D[i]>35&j<k;)for(t=F[j++],o=1;o<5&k<W;t.y+=(o++&2)-1){t.x+=o&2;if(D[--t.x%w+t.y%(W/w)*w]>35&System.Array.IndexOf(F,t)<0)F[k++]=t;}}C.WriteLine(k>=W);}}

```

It is a breadth-first (not that this matters) search which just carries on until it either gets stuck in a finite cavern, or it decides the cavern is big enough that it must be infinitely large (when it has as many cells as the original rectangle, this means there must be a path from one cell to itself somewhere else, which we can continue to follow forever).

Untrimmed code:

```
using C=System.Console;

struct P
{
    int x,y;

    static void Main()
    {
        int w=0, // w is the width
        W, // W is the length of the whole thing
        k=0, // k is visited count
        o, // o is offset, or something (gives -1,0 0,-1 +1,0 0,+1 t offset pattern)
        i, // i is the start cell we are checking currently
        j; // j is the F index of the cell we are looking at

        P t; // t is the cell at offset from the cell we are looking at

        string D="", // D is the map
        L;

        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        for(i=W=D.Length;i-->0&k<W;) // for each cell
        {
            k=1;

            P[]F=new P[W]; // F is the list of visited cells,

            for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W; // there are reasons (broken modulo)
                D[i]>35&j<k;) // for each cell we've visited, until we've run out
                for(t=F[j++], // get the current cell
                    o=1; // o is just a counter which we use to kick t about
                    o<5& // 4 counts
                    k<W; // make sure we havn't filled F
                    t.y+=(o++&2)-1) // kick and nudge y, inc o
                {
                    t.x+=o&2; // kick x
                    if(D[--t.x%w+t.y%(W/w)*w]>35 // nudge x, it's a dot
                       &System.Array.IndexOf(F,t)<0) // and we've not seen it before
                        F[k++]=t; // then add it
                }
        }

        C.WriteLine(k>=W); // result is whether we visited lots of cells
    }
}

```

# Answer
> 10 votes
# Python 2 - ~~258~~ ~~210~~ 244 bytes

Recursively check paths, if stack overflow return 1 (truthy) else return None (falsey).

```
import sys
def k(s):
 a=len(s);m=[[c=='.'for c in b]*999for b in s.split('\n')]*999;sys.setrecursionlimit(a)
 for x in range(a*a):
  try:p(m,x/a,x%a)
  except:return 1
def p(m,x,y):
 if m[x][y]:m[x][y]=0;map(p,[m]*4,[x,x,x+1,x-1],[y+1,y-1,y,y])

```

# Answer
> 5 votes
# Python 2 - 297 286 275 bytes

Picks an arbitrary "open" cell to begin a flood fill from. Labyrinth is infinite if during the fill we re-visit a cell we've already visited, but it has a different coordinate to the previous visit. If the flood fill fills the entire region without finding such a cell, try a different region. If such a region can't be found, the labyrinth is finite.

Takes file to process on command line, returns exit code `1` for infinite, and `0` for finite.

Returns correct results for all test cases.

```
import sys
e=enumerate
C=dict([((i,j),1)for i,l in e(open(sys.argv[1]))for j,k in e(l)if'.'==k])
while C:
 d={}
 def f(r,c):
  n=(r%(i+1),c%j)
  if n in d:return(r,c)!=d[n]
  if C.pop(n,0):d[n]=(r,c);return any(map(f,[r-1,r,r+1,r],[c,c+1,c,c-1]))
 if f(*C.keys()[0]):exit(1)

```

---
Tags: code-golf, grid, graph-theory, decision-problem, maze
---


# Question
Title: ASCII topology pt 1: Can I count on you?
I have a serious problem. I have some text files where I keep my very important numbers -- all of the important ones! And twos, and threes..

These numbers were so important that I couldn't entrust them to those newfangled decimal or binary number systems. I kept each number encoded in unary, as so:

```
            +--+
            |  |
+---+  +----+  |
|   |  |       |
+---+  +-------+
   ~/two.txt

```

Simple and reliable: two ASCII loops for the number 2. Unfortunately, these things tend to get tangled up over time and now I have a hard time figuring out how many loops are in each file. Here are some examples that I worked out by hand:

One:

```
   +---+
   |   |
+--+   |
|      |
+--+   |
   |   |
   |   |
   |   |
+--+   +--+
|         |
+---------+

```

Three:

```
+---------+
| +-----+ |
| | +-+ | |
| | | | | |
| | +-+ | |
| +-----+ |
+---------+

```

Four:

```
  +--------------+
  |  +--+  +--+  |
  |  |  |  |  |  |
+-|-----|-----|----+
| |  |  |  |  |  | |
| +--+  +--+  +--+ |
+------------------+

              +------------+
              |            |
        +-----+  +-----+   |
        |        |     |   |
  +-----|-----------+  |   |
  |     |  +--+  |  |  |   |
  +-+   +--|--|--+  +---------+
    |      |  +-+      |   |  |
    +------+    |      |   |  |
                +-------+  |  |
                       ||  |  |
                       |+-----+
                       |   |
                       +---+

```

Five:

```
+--------+  +--------+  +--------+
|        |  |        |  |        |
|     +--|-----+  +--|-----+     |
|     |  |  |  |  |  |  |  |     |
+-----|--+  +-----|--+  +--------+
      |        |  |        |
      +--------+  +--------+

```

Can you help me count my loops?

Here are the rules:

* Since I store everything in ASCII-encoded unary, space efficiency is very important to me. Therefore, this is code golf. The smallest program in bytes wins.
* Loops are drawn with the characters +, -, |. Every corner in the loop is drawn unambiguously: exactly one of the characters above and below the + will be |, and exactly one to the right or left will be -. Two + marks are never adjacent.
* Strands may pass over and under each other. When strands cross, you'll be able to see the "under" strand immediately on both sides of the "over" strand.
* Your program should take a string representation of the loop (either from stdin or as a function parameter) and produce a number (either to stdout or as a return value).
* Line lengths may not be uniform in the loop drawing and there may be trailing spaces on each line.
* You may assume that there is at least one loop in the input.

I'm counting on you!

# Answer
> 19 votes
# SnakeEx - 98 bytes with Javascript, 44 without

This looked like a good problem to try my language from the Fortnightly Challenge on:

```
m:({e<>PE}\-[|\-]*<T>\+|[|\-]*<T>)+`\+
e:\+

```

The best place to try this out is my online interpreter.

SnakeEx matches patterns in text by using "snakes" that move around the text matching regexes. The code reads kind of like a regex, except:

* The `<T>` instruction. That is a direction command that branches the snake left and right from its current direction.
* `{e<>PE}` is like a subroutine call. It that spawns a snake with definition `e` moving forward (`<>`) and with parameters `P` (piggyback - the spawning snake follows the new snake) and `E` (exclusive - don't match anything that's already been matched). This exclusive check is the only thing that stops the snake from looping infinitely.
* The prefix ``` at the end indicates that what follows should be matched only if it has already been matched, which we can use to force the loop to close.

Because SnakeEx is like regex and doesn't technically output the results as desired by itself, I guess we need to wrap it in some Javascript calling the interpreter:

```
function e(s){return snakeEx.run('m:({e<>PE}\\-[|\\-]*<T>\\+|[|\\-]*<T>)+`\\+\ne:\\+',s,1).length}

```

*Edit*: fixed it up to work with blutorange's additional test cases

# Answer
> 10 votes
# C# - 338 ~~388~~ ~~433~~ bytes

Saved a bunch of bytes by changing to a 1-dimensional array.

```
using C=System.Console;using System.Linq;class P{static void Main(){var D=C.In.ReadToEnd().Split('\n');int z,w=D.Max(m=>m.Length)+1,d,c=0;var E=D.SelectMany(l=>l.PadRight(w)).ToList();for(z=E.Count;z-->1;)if(E[z-1]==43)for(d=1,c++;E[z+=d%2<1?w*d-w:d-2]>32;)if(E[z]<44){E[z]=' ';d=d%2>0?z<w||E[z-w]<99?2:0:E[z+1]!=45?1:3;}C.WriteLine(c);}}

```

First it reads in the input, and makes it nice and rectangular, with a " " border so we don't have to do any bounds checking on the horizontal (cheaper to do the checking on the vertical than to put in the extra line). Then it looks back through the rectangle, so it always hits a right-bottom corner. When it hits one of these, it directs itself up, following any +s it meets, and clearing them as it goes (with a space). It stops following when it meets a space. Tested on the five given examples.

```
using C=System.Console;
using System.Linq;

class P
{
    static void Main()
    {
        // read in
        var D=C.In.ReadToEnd().Split('\n');

        int z, // z is position in E
        w=D.Max(m=>m.Length)+1, // w is width
        d, // d is direction of travel (1 == horizontal?, 2 == down/right?)
        c=0; // c is loop count

        // make all the lines the same length
        var E=D.SelectMany(l=>l.PadRight(w)).ToList(); // say no to horizontal bounds checking

        // consume +s
        for(z=E.Count;z-->1;)
            if(E[z-1]==43) // right-most lower-most +
                for(d=1,c++; // go left, increment counter
                    E[z+=d%2<1?w*d-w:d-2]>32 // move z, then check we havn't hit a space (when we do, z is basiclly z - 1)
                    ;)
                    if(E[z]<44) // +
                    {
                        E[z]=' '; // toodles

                        d=
                            d%2>0? // currently horizontal, must go vertical
                                z<w||E[z-w]<99?2 // can't go up, must go down
                                :0 // can go up, go up
                            : // currently vertical, must go horizontal
                                E[z+1]!=45?1 // can't go right, must go left
                                :3 // can go right, go right
                            ;
                    }

        // output result
        C.WriteLine(c);
    }
}

```

# Answer
> 6 votes
# Slip, ~~51~~ 41 + 2 = 43 bytes

```
$a(`+`-[^ +]*`+(<|>)`|[^ +]*`+#(<|>))+?$A

```

*(Now updated to work with @blutorange's test case at a major cost)*

Since @BMac used SnakeEx for this challenge, I thought I'd try and use my 2D pattern-matching language submission, Slip. But because Slip didn't have the features necessary to solve this problem, I've been adding them in over the past few days. In other words, this submission is **not eligible to win**.

Run with the `n` flag for number of matches, e.g.

```
py -3 slip.py regex.txt input.txt n

```

Try it online.

---

## Explanation

Due to the plethora of new features in this submission, this is a good opportunity to showcase them.

```
$a                Set custom anchor at current position
(
  `+`-            Match '+-'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  (<|>)           Either turn left or turn right
  `|              Match a '|'
  [^ +]*          Match any number of '|' or '-'
  `+              Match a '+'
  #               Prevent next match from moving the match pointer (doubling up on '+')
  (<|>)           Either turn left or turn right
)
+?                Do the above at least once, matching lazily
$A                Make sure we're back where we started

```

Slip tries to match starting from every position, and only returns unique matches. Note that we use `[^ +]` — while using `[-|]` would theoretically save two bytes, unescaped `-` at the beginning/end of character classes is not yet implemented in Slip.

# Answer
> 5 votes
# Ruby 295

```
F=->i{l=i.lines
g={}
l.size.times{|y|i.size.times{|x|l[y][x]==?+&&g[[y,x]]=[[y,x]]}}
c=->a,b{w=g[b]+g[a];w.map{|x|g[x]=w}}
k=g.keys
k.product(k).map{|n,o|
r,p=n
s,q=o
((r==s&&p<q&&l[r][p...q]=~/^\+-[|-]*$/)||(p==q&&r<s&&l[r...s].map{|l|l[p]||c}.join=~/^\+\|[|-]*$/))&&c[n,o]}
g.values.uniq.size}

```

Try it online: http://ideone.com/kIKELi (*I added a `#to_a` call on the first line, because ideone.com uses Ruby 1.9.3, which does not support `#size` for `Enumerable`s. In Ruby 2.1.5+ the code runs OK.*)

The approach is the following:

* make a list of all the `+` signs in the input and consider each of them a distinct shape
* find horizontal and vertical lines that link two `+` signs and combine their shapes into one
* in the end, the number of distinct shapes matches the result

Here's a more readable version:

```
def ascii_topology_count(input)
  lines = input.lines
  max_length = lines.map(&:size).max

  # hash in which the keys are corners ("+"s), represented by their [y, x] coords
  # and the values are arrays of corners, representing all corners in that group
  corner_groups = {}

  lines.size.times { |y|
    max_length.times { |x|
      if lines[y][x] == ?+
        corner_groups[[y, x]] = [[y, x]]
      end
    }
  }

  # function that combines the groups of two different corners
  # into only one group
  combine_groups =-> c1, c2 {
    g1 = corner_groups[c1]
    g2 = corner_groups[c2]

    g2 += g1
    corner_groups[c1] = g2
    g2.map{|x| corner_groups[x] = g2}
  }

  corner_groups.keys.product(corner_groups.keys).map{|c1, c2|
    y1,x1=c1
    y2,x2=c2
    if y1 == y2 && x1 < x2
      # test horizontal edge
      t = lines[y1][x1...x2]
      if t =~ /^\+-[|-]*$/
        # p "#{c1}, #{c2}, [H] #{t}"
        combine_groups[c1, c2]

      end
    end

    if x1 == x2 && y1 < y2
      # test vertical edge
      t=lines[y1...y2].map{|l|l[x1]||' '}.join

      if t =~ /^\+\|[|-]*$/
        # p "#{c1}, #{c2}, [V] #{t}"
        combine_groups[c1, c2]
      end
    end
  }

  corner_groups.values.uniq.count
end

```

# Answer
> 5 votes
# JavaScript (ES6) 190 ~~197 202 215 235 289 570~~

**Edit** Single dimension array instead of 2 dimension, max row size 999 chars (but can be more at no cost, e.g. 1e5 instead of 999)

**Edit** Added animated code snippet, see below

```
F=s=>[...s.replace(/.+/g,r=>r+Array(e-r.length),e=999)]
  .map((c,x,z,d=1,f='-',g='|')=>{
    if(c=='+')
      for(++n;z[x+=d]!='+'||([f,g,e,d]=[g,f,d,z[x-e]==g?-e:z[x+e]==g&&e],d);)
        z[x]=z[x]==g&&g
  },n=0)|n

```

**Ungolfed** first try

```
f=s=>
{
  cnt=0
  s = (1+s+1).split(/[1\n]/)

  for(;x=-1, y=s.findIndex(r=>~(x=r.indexOf('+-'))), x>=0;++cnt)
  {
    //console.log(y+' '+x+' '+s.join('\n'))
    dx = 1
    for(;dx;)
    {
      a=s[y-1],b=s[y+1],
      r=[...s[y]]
      for(r[x]=' ';(c=r[x+=dx])!='+';)
      {
        if (c=='-')
          if((a[x]||b[x])=='|')r[x]='|';
          else r[x]=' ';
      }

      if(a[x]=='|')dy=-1;
      else if(b[x]=='|')dy=1;
      else dy=0
      r[x]=' '
      s[y]=r.join('')
      if (dy) {
        for(;y+=dy,r=[...s[y]],(c=r[x])!='+'&c!=' ';)
        {
          if (c=='|')
            if((r[x-1]||r[x+1])=='-')r[x]='-';
            else r[x]=' ';
          s[y]=r.join('')
        }
        if(r[x-1]=='-')dx=-1;
        else if(r[x+1]=='-')dx=1;
        else dx=0;
      }
    }
  }
  return cnt
}

```

**Animated snippet**

```
F=s=>[...s.replace(/.+/g,r=>r+Array(e-r.length),e=999)].map((c,x,z,d=1,f='-',g='|')=>{if(c=='+')for(++n;z[x+=d]!='+'||([f,g,e,d]=[g,f,d,z[x-e]==g?-e:z[x+e]==g&&e],d);)z[x]=z[x]==g&&g,steps.push(z.map(c=>c?c!=','?c:'':0).join(''))},n=0)|n

function go(){var g=grid.value;steps=[];Num.value=F(g);a=_=>{g=steps.shift();if(g){grid.value=g;setTimeout(a, 100)}};a()}
```

```
textarea { width: 500px;  height: 500px; }
input {width: 80px}
```

```
Better viewed full page
Input (paste input text - enlarge if needed)<button onclick="go()">Process</button>Loop count:<input readonly id=Num />
<textarea id=grid></textarea>

```

**Test** In Firefox/FireBug console

```
F('\
  +--------------+\n\
  |  +--+  +--+  |\n\
  |  |  |  |  |  |\n\
+-|-----|-----|----+\n\
| |  |  |  |  |  | |\n\
| +--+  +--+  +--+ |\n\
+------------------+\n\
\n\
              +------------+\n\
              |            |\n\
        +-----+  +-----+   |\n\
        |        |     |   |\n\
  +-----|-----------+  |   |\n\
  |     |  +--+  |  |  |   |\n\
  +-+   +--|--|--+  +---------+\n\
    |      |  +-+      |   |  |\n\
    +------+    |      |   |  |\n\
                +-------+  |  |\n\
                       ||  |  |\n\
                       |+-----+\n\
                       |   |\n\
                       +---+')

```

> 4

```
F('\
+--------+  +--------+  +--------+\n\
|        |  |        |  |        |\n\
|     +--|-----+  +--|-----+     |\n\
|     |  |  |  |  |  |  |  |     |\n\
+-----|--+  +-----|--+  +--------+\n\
      |        |  |        |\n\
      +--------+  +--------+')

```

> 5

# Answer
> 4 votes
# Ruby, 178 187 199 212

Better ruby version, creates a function F. Now with more delicious interpreter warnings constantly.

```
b=->n{Q[I]=?~
d=Q[I+n]==(n>1??|:?-)?1:-1
loop{I+=d*n
b[n>1?1:N]if Q[I]==?+
Q[I]<?~?4:break}}
F=->s{N=s.size;Q=s+?\n
Q.gsub!(/^.*$/){$&.ljust N-1}
(0..N).find{!(I=Q=~/\+/)||b[1]}}

```

Test it online: ideone

Basically, function `b` starts at any `+`, recursively goes through the loop, setting all `+` to `u`. Thus one loop gets removed each time `b` is called. Function `F` just tries how often we need to call `b` until there aren't any loops remaining.

# Answer
> 2 votes
# Python 2 - 390

Takes a string with newlines from stdin. It's a pretty simple method golfed a fair bit, but I'm sure not as much as it could be considering how long it is.

```
s=raw_input().split('\n');L=len
def R(x,y):
 b=p,q=x,y;u=v=f=0
 while b!=(p,q)or not f:
    p+=u;q+=v;f=u+v;c=s[q][p]
    if'+'==c:u,v=[(i,j)for i,j in{(-1,0),(1,0),(0,-1),(0,1)}-{(-u,-v)}if 0<=q+j<L(s)and 0<=p+i<L(s[q+j])and s[q+j][p+i]in['-+','|+'][j]][0];s[q]=s[q][:p]+' '+s[q][p+1:]
    if c+s[q+v][p+u]in'-|-':p+=u;q+=v
print L([R(x,y)for y in range(L(s))for x in range(L(s[y]))if'+'==s[y][x]])

```

# Answer
> 1 votes
# Python 2 - 346 bytes

Implemented as a function `c` that takes the file data as input and returns the number of loops.

First, the function decomposes the data to a mapping of loop element locations to the element type at that location (e.g. `{(0,0): '+'}`). Then, it uses two mutually-recursive internal functions. The first removes a loop segment from the mapping and decides which locations to check for the subsequent segment. The second checks what kind of loop element is in the selected locations and, if it is compatible with what is expected, calls the first to remove the newly found section.

```
e=enumerate
def c(d):
 D={(i,j):k for i,l in e(d.split('\n'))for j,k in e(l)if k in'+-|'}
 def f(r,c,R,C,t):
  if D.get((r,c),t)!=t:g(r,c)
  elif D.get((R,C),t)!=t:g(R,C)
 def g(r,c):
  t=D.pop((r,c))
  if t!='|':f(r,c-1,r,c-2,'|');f(r,c+1,r,c+2,'|')
  if t!='-':f(r-1,c,r-2,c,'-');f(r+1,c,r+2,c,'-')
 n=0
 while D:g(*D.keys()[0]);n+=1
 return n

```

---
Tags: code-golf, ascii-art, topology
---


title: DoIt Java Style

text:
# Question
Title: DoIt Java Style
Given string X, convert it to Java Style string, as defined below:

* Strings may only contain numbers and letters(signs are not allowed)
* Strings must not start with numbers
* Strings must start with Capital letter
* Strings may not contain two capital letters in a raw.

As for conversion you may perform the next actions

* Replace capital letter with lower case letter and vise versa.
* Remove character

A good conversion is defined as follow:

Minimum actions been performed while achieving the next goals:

* all the sequences of capital letters only kept the first letter as capital.
* if a letter has a character in place before it, and the character is not a letter nor a number, then the letter becomes capital.
* in case that after a good conversion there is a contradiction with the style, good conversion will be applied again on the result of previous conversion.
* If there is more then one way to apply good conversion, than conversion `A` is considered to be better then conversion `B` if conversion `A` has more capital letters then `B`.

**Input:**

* String x

**Output:**

* Best conversion Java Style String

**I/O examples**

```
X                Output

'ab<>c'          'AbC'
'a<>b<>c'        'Abc' // conversion been applied twice. ABC -> Abc
'a<>bc'          'Abc' // conversion been applied twice. ABc -> Abc
'HI<>man'        'HiMan'
''               ''
'its**cOOL'      'ItsCool'
'28and*2fun'     'And2fun' // conversion been applied twice. and2fun -> And2fun

```

In this example strings been wrapped with '' sign.

**Criteria**

* The shortest program wins, as determined by the number of bytes of source code.

# Answer
> 0 votes
# Java ~~551~~ 490 bytes

```
public class A{public static void main(String...a){String b="";for(int i=0;i<2;i++){String[]c=a[0].split("[^a-zA-Z0-9]");if(c[0].length()>0&&Character.isDigit(c[0].charAt(0)))c[0]=c[0].replaceFirst("[0-9]+","");b="";for(String d:c){boolean e=false;String f="";byte[]g=d.getBytes();for(byte h:g){if(e){if(Character.isLowerCase(h))e=false;else h+='a'-'A';}else if(!Character.isLowerCase(h))e=true;f+=(char)h;}d=f;if(d.length()>0)b+=StringUtils.capitalize(d);}a[0]=b;}System.out.println(b);}}

```

Ungolfed Code:

```
public class A{
    public static void main(String...args){
        String input = args[0];

        String className = "";
        for (int i = 0; i < 2; i++) {
            String[] names = input.split("[^a-zA-Z0-9]");
            if(names[0].length() > 0 && Character.isDigit(names[0].charAt(0))){
                names[0] = names[0].replaceFirst("[0-9]+", "");
            }
            className = "";
            for (String value : names) {
                boolean toLowerCase = false;
                String newValue = "";
                byte[] bytes = value.getBytes();
                for (byte aByte : bytes) {
                    if(toLowerCase){
                        if (Character.isLowerCase(aByte)){
                            toLowerCase = false;
                        }
                        else{
                            aByte += 'a' - 'A';
                        }
                    }
                    else if (!Character.isLowerCase(aByte)){
                        toLowerCase = true;
                    }
                    newValue += (char)aByte;
                }

                value = newValue;
                if(value.length() > 0){
                    className += StringUtils.capitalize(value);
                }
            }
            input = className;
        }

        System.out.println(className);

    }
}

```

# Answer
> 0 votes
## Haskell 316 bytes

Not fully golfed, may spend time to golf a bit more if others come and join the game.

```
import Data.Char
data T = C | S | X
conv t [] = []
conv t (c:cs)
  |isLower c = case t of X -> toUpper c : conv C cs; _ -> c : conv S cs
  |isUpper c = case t of C -> toLower c : conv X cs; _ -> c : conv C cs
  |isDigit c = c : conv S cs
  |otherwise = conv X cs
main = interact $ conv X . dropWhile isDigit . conv X

```

The C, S, X, `data = T = C | S | X` stands for Capital, Small, Other.

---
Tags: code-golf, string
---


# Question
Title: Generate a Rectangle from a Specification
# Introduction

This challenge is inspired by Grime, my 2D pattern matching language. Basically, you are given a "grammar" that describes two-dimensional grids of characters, and your job is to generate a grid according to the grammar. In addition, the grid should be as small as possible in a certain weak sense.

# Input

Your input is a string containing lowercase ASCII characters and the symbols `|` and `-`. For simplicity, the input does not contain repeated lowercase characters. The string is a specification for a class of rectangular grids of characters, and it is parsed from left to right using a stack as follows.

* Given a lowercase character `c`, push to the stack an `m×n` grid of the character `c`, for any `m, n ≥ 1`.
* Given a pipe `|`, pop two grids `A` and `B` from the stack (`B` was on top), and push the grid `AB` obtained by concatenating `B` to the right of `A`. This requires that `A` and `B` have equal height.
* Given a hyphen `-`, pop two grids `A` and `B` from the stack (`B` was on top), and push the grid `A/B` obtained by concatenating `B` to the bottom of `A`. This requires that `A` and `B` have equal width.

It is guaranteed that for *some* choices of `m` and `n` made during the parsing process (which may be different for each letter), the input specification correctly describes some rectangle, which is left on the stack at the end.

# Output

Your output is a rectangular grid of characters specified by the input. The grid must be minimal in the sense that removing any row or column would make it invalid. You can return a newline-separated string (with or without a trailing newline), a 2D array of characters, or an array of strings, whichever is the most convenient format.

Note that you are not required to process the input exactly as described above; the only important thing is that your output is correct.

# Example

Consider the specification

```
par-s||e-

```

First, we choose to push a `1×2` rectangle of `p`, and `1×1` rectangles of `a` and `r` (the reason for this will be clear later). Then, we pop the `a` and `r` rectangles, and push their vertical concatenation

```
a
r

```

Next, we push a `1×2` rectangle of `s`, pop it and the above rectangle, and push their horizontal concatenation

```
as
rs

```

Then we pop that rectangle and the `p` rectangle, and push their concatenation

```
pas
prs

```

Finally, we push a `3×1` rectangle of `e`, pop it and the above rectangle, and push the vertical concatenation

```
pas
prs
eee

```

This is the output of the program, or at least one of the possibilities. Notice that even though

```
ppas
ppas
pprs
eeee

```

is also generated by the specification, it is not a valid output, since many of the rows and columns could be removed.

As a more subtle example, consider

```
co|m|p|il|e|r|-

```

This specification generates the rectangle

```
comp
iler

```

which is a valid output. However, it also generates

```
commp
iiler

```

which is valid too, since no single row or column can be removed without invalidating it.

# Rules

You can give a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Extra Test Cases

You can use these to test your program.

```
Input:
a
Output:
a

Input:
co|mp|l|-ex|i|f|-y|
Example output:
cccoy
mplly
exify

Input:
ja-r|g-o|ni-|ze|d-|
Example output:
jronze
arondd
ggoidd

Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Example output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

```

# Answer
# K, ~~123~~ 110 bytes

I used a similar approach to cardboard\_box's solution.

```
r:{y,x#,*|y};h:{t:(#x)|#y;r[t-#x;x],'r[t-#y]y};a:{(,x .|2#y),2_ y};*(){(a[{+h[+x;+y]}]x;a[h]x;(,,y),x)"-|"?y}/

```

This program is a series of helper definitions followed by a tacit function which takes a string as a right argument. Reformatting for readability and assigning the final function as `f`:

```
r: {y,x#,*|y};                           / repeat last row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x[y@1;y@0]),2_ y};                 / pop two values, concat

f: *(){:[y="-";a[v;x]; y="|";a[h;x]; (,,y),x]}/;

```

Use example:

```
  f "ja-r|g-o|ni-|ze|d-|"
("jronze"
 "aroidd"
 "ggoidd")

```

Tested using Kona, but it will also work in oK if you replace the `:` in the definition of `f` with a `$`\- k5 changed the syntax of "cond".

A key point is recognizing that doing a vertical append is the transpose of the horizontal append of the transpose of both matrices. (See definition `v`.) I think there's still room to squeeze out a few characters here and there. If anyone is interested in a more detailed explanation I can provide one.

## edit:

Updated the program at the top of this entry. Ungolfed version:

```
r: {y,x#,*|y};                           / repeat row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x .|2#y),2_ y};                    / apply a concat
f: *(){(a[v]x;a[h]x;(,,y),x)"-|"?y}/;

```

Notable length optimizations include the use of "dot apply" in `a`, replacing the "cond" with list indexing in `f` (less efficient, but shorter) and replacing terms of the form `a[b;c]` into `a[b]c` where permitted by grouping. Since I'm no longer using "cond" or any primitives which are different between k3 and k5 this version now works in oK without modification.
> 6 votes

# Answer
# Prolog, 539 bytes

```
:-lib(ic).
:-lib(util).
b(A,B,C):-between(A,B,C).
g(S):-string_list(S,L),p(L,[]).
w(h(L,R):_:_,I,J):-w(L,I,J);L=_:W:_,X is I-W,w(R,X,J).
w(v(U,D):_:_,I,J):-w(U,I,J);U=_:_:H,Y is J-H,w(D,I,Y).
w(f(C):W:H,I,J):-b(1,W,I),b(1,H,J),char_code(S,C),put_char(S).
p([],[S]):-term_variables(S,V),S=_:X:Y,labeling(V),!,b(1,Y,J),(b(1,X,I),w(S,I,J);nl),fail.
p([124|T],[Q,Z|R]):-!,Q=_:WA:H,Z=_:WB:H,W #= WA+WB,p(T,[h(Z,Q):W:H|R]).
p([45|T],[Q,Z|R]):-!,Q=_:W:HA,Z=_:W:HB,H #= HA+HB,p(T,[v(Z,Q):W:H|R]).
p([C|T],R):-!,[H,W] #:: 1..100,p(T,[f(C):W:H|R]).

```

# Explanation

We start with predicate `g`, which takes a string, convert it as a list of chars and call the `p` (parse) predicate with an empty stack as a second argument.

Predicate `p` calls itself recursively with an appropriately modified stack (look for `[H|T]` destructuring and constructor patterns). When called on the base case, where the input list is empty, `p` prints the unique element of the stack. If the stack has less or more than one element at this point, it means that we have an empty input string, a bad input string or a bug (with an emtpy string, the predicate fails (Prolog says `No`), but nothing is printed, which is ok, since we should not print anything for empty strings).

### Solving

The stack contains a description of the constructed rectangles, denoted `S:W:H`, where `S` is a symbolic representation of the rectangle, `W` its width and `H` its height (note, `A:B` is syntactic sugar for the `:(A,B)` tuple with a functor named `:`; it is just shorter to write than having a tuple with prefix notation).

With `A` and `B` sub-rectangle specifications, `S` can be either:

* `h(A,B)` : horizontal concat of A and B
* `v(A,B)` : vertical concat of A and B
* `f(C)` : fill with C, where C is a character code

Widths and heights of grids are constraint-programming variables: during vertical (resp. horizontal) concatenation, the width (resp. height) of the manipulated rectangles are unified, whereas the resulting height (resp. width) is constrained to be the sum of each subgrid's height (resp. width).

The labeling step at the end of the process instanciates variables while respecting constraints, using the minimal possible values (this is a property of the order by which solutions are tried).

I might have obtained a shorter answer using the same reasonning that is done in other answers, without constraints, but this is too late now.

Note also that because the default domain for variables is set to `1..100`, there is a limitation over the possible sizes of grids. The upper-bound could be changed if needed. The performance implications of this are that it *could* take a lot of time to determine that a particular solution admits no solution. I said "*could*" because constraints are likely to drastically prune the exponential search. If you find an input string that is hard/costly to reject, please share.

### Printing

The printing part is interesting because there is a kind of *ray-casting* algorithm over the structure: I iterate over each cell of the resulting grid, from point `(1,1)` to point `(W,H)` and call the `w` predicate to print the content of the grid in the main tree, at this location (of course, a newline is printed after processing each line).

In `w`, positions are relative to current grid (the root grid defines absolute coordinates).

When printing a `h(A,B)` structure at point `(X,Y)`, I unconditionnaly print in both branches:

* in grid `A` at point `(X,Y)`, and
* in grid `B` at point `(H,Y)`, where `H` is `X` minus the width of `A`.

The leaf branches of the grid-tree, `f(C)`, finally either print the character `C`, if the relative location is inside the grid, or do nothing. This is how I can print the content of grid to the output stream, from top to bottom, from left to right. No actual arrays are produced.

# Tests

```
t("ja-r|g-o|ni-|ze|d-|").
t("un|co|p-yr|i|gh-t-ab|-|le-||-").
t("co|mp|l|-ex|i|f|-y|").
t("a").

tt :- t(X),nl,g(X).
tt.

```

Running test:

```
[eclipse] tt.

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

cccoy
mmply
exify

a

Yes (0.00s cpu)

```
> 4 votes

# Answer
# Haskell, ~~388~~ ~~367~~ 352 bytes

```
data C=L{c::Char}|N{t::Int,w::Int,h::Int,l::C,r::C}
q=replicate
[]#[x]=x
(c:i)#(b:a:s)|c=='-'=i#(N 1(max(w a)$w b)(h a+h b)a b:s)|c=='|'=i#(N 2(w a+w b)(max(h a)$h b)a b:s)
(c:i)#s=i#(N 0 1 1(L c)(L c):s)
p i|t i==0=q(h i)$q(w i)$c$l i|t i==2=zipWith(++)(p(l i){h=h i})$p(r i){h=h i,w=w i-w(l i)}|1<2=p(l i){w=w i}++p(r i){w=w i,h=h i-h(l i)}
f=p.(#[])

```

Usage: `f "par-s||e-"` -\> `["pas","prs","eee"]`

Test run with pretty printing:

```
> putStr $ unlines $ f "par-s||e-"
pas
prs
eee

> putStr $ unlines $ f "co|m|p|il|e|r|-"
comp
iler

> putStr $ unlines $ f "a"
a

> putStr $ unlines $ f "co|mp|l|-ex|i|f|-y|"
coooy
mplly
exify

> putStr $ unlines $ f "ja-r|g-o|ni-|ze|d-|"
jronze
aroidd
ggoidd

> putStr $ unlines $ f "un|co|p-yr|i|gh-t-ab|-|le-||-"
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

```

How it works: the function `#` parses the input string into the tree structure `C` which is either a leaf `L` holding the character to print or a node `N`. `N` can be a) a side-by-side join (`t==2`), b) a top-bottom join (`t==1`) or c) a single letter square (`t==0`). All nodes have a width and height field and a left and right child. After parsing, `p` prints the remaining root node by recursively adjusting the size (width x height) of it's child nodes and joining them.

Edit: output as a list of lines instead of pretty printing
> 3 votes

# Answer
# Python 2.7, 259

```
z=zip
def p(a,b):
 s,l=sorted([a,b],key=len)
 s+=([s[-1]]*(len(l)-len(s)))
 return z(*(z(*a)+z(*b)))
g=lambda s,t=[]:s and(s[0]=='-'and g(s[1:],t[:-2]+[z(*p(z(*t[-2]),z(*t[-1])))])or(s[0]=='|'and g(s[1:],t[:-2]+[p(t[-2],t[-1])])or g(s[1:],t+[[s[0]]])))or t[0]

```

`g` is a function which takes a specification and gives a 2D array of characters. If you want a more user-friendly version, add this line to make it take a specification from stdin and print out the grid:

```
print'\n'.join(''.join(s)for s in g(raw_input()))

```

## Test Cases

```
Input:
a
Output:
a
==========
Input:
co|mp|l|-ex|i|f|-y|
Output:
coooy
mplly
exify
==========
Input:
ja-r|g-o|ni-|ze|d-|
Output:
jronze
aroidd
ggoidd
==========
Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

```

## Explanation

The strategy is simple: if a grid `G` is valid for a specification `S`, then repeating the rightmost column of `G` also gives a valid specification for `S`, and the same is true with repeating the bottom row (the proof of this is by structural induction on `S`). Therefore, when we want to concatenate two rectangles, we can simply append the last column/row of the smaller one until they match in size (this is what the function p does).
> 3 votes

# Answer
# JavaScript (ES6), 283 ~~295~~

**Edit** Now this (heavily golfed) JS solution is at least shorter than the reference (quite golfable) Python solution.

Similar to cardboard\_box, just repeating the leftmost column or the topmost row.

```
F=w=>(
s=[t=1,l='length'],
[for(c of w)(
  b=s[t],a=s[--t],
  c>'z'?
    s[t]=(G=(a,b,m=b[l]-a[l])=>m?m>0?G([a[0],...a],b):G(a,[b[0],...b]):a.map((r,i)=>r+b[i]))(a,b)
  :c<'a'?
    s[t]=a.map(r=>r[m=b[0][l]-r[l],0].repeat(m>0&&m)+r).concat(b.map(r=>r[0].repeat(m<0&&-m)+r))
  :s[t+=2]=[c]
)],
s[t].join('\n'))

```

**Ungolfed** This is my first, ungolfed solution.

```
F=sp=>{
  s=[]
  for(c of sp){
    a=s.pop(b=s.pop())
    if (c > 'z')
    {
      l = a.length
      m = b.length
      for(; l-m ;)
        l < m ? l = a.unshift(a[0]) : m = b.unshift(b[0])
      s.push(a.map((r,i) => r + b[i]))
    }
    else if (c < 'a')
    {
      l = a[0].length
      m = b[0].length
      s.push(
        a.map(r => r[0].repeat(l < m ? m-l : 0) + r)
        .concat(b.map( r => r[0].repeat( l > m ? l-m : 0) + r))
      )
    }
    else
    {
      s.push(a,b,[c])
    }
  }
  return s.pop().join('\n')
}

```

**Test** In Firefox/FireBug console

```
;['par-s||e-','co|m|p|il|e|r|-','co|mp|l|-ex|i|f|-y|',
 'ja-r|g-o|ni-|ze|d-|','un|co|p-yr|i|gh-t-ab|-|le-||-']
.forEach(w=>console.log(F(w)))

```

*Output*

```
pas
prs
eee

comp
iler

cccoy
mmply
exify

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

```
> 1 votes

# Answer
# Python 3, 251 bytes

Here's the reference answer I promised, golfed a bit further.

```
T=lambda m:list(map(list,zip(*m)))
E=lambda a,b:a[:1]*(len(b)-len(a))+a
H=lambda a,b:[d+c for c,d in zip(E(a,b),E(b,a))]
s=[]
for k in input():s=k>"z"and[H(*s[:2])]+s[2:]or k<"a"and[T(H(*map(T,s[:2])))]+s[2:]or[[[k]]]+s
for r in s[0]:print("".join(r))

```

This is a full program that takes the string from STDIN and prints to STDOUT. The approach is the same as that of cardboard\_box: push a 1x1 array for a character, and duplicate rows if needed for concatenation.

```
$ echo "par-s||e-" | python3 gr.py
pas
prs
eee

```

## Detailed explanation

* `T` transposes a given list of lists. The majority of the work is done by `zip(*m)` which swaps rows to columns, the rest is just converting the result into a list of lists, since `zip` returns a generator of tuples.
* `E(a,b)` returns `a` with its first element repeated enough times to match the length of `b`. Note that multiplying a list by a negative number gives the empty list, so if `b` is shorter than `a`, this returns `a`.
* `H(a,b)` returns the horizontal concatenation of `a` and `b`, the shorter one being lengthened by `E` if necessary.
* `s` is the stack.
* In the `for` loop, we iterate over the input string, and replace `s` by a new value: if it's `|` (greater than `z`), we pop two values and push their `H`, if it's `-` (lower than `a`), we pop two values, transpose, feed to `H`, transpose again and push the result, and otherwise push a 1x1 array with the letter.
* Finally, we print the first element of `s`.
> 0 votes

---
Tags: code-golf, ascii-art, generation, stack
---


# Question
Title: Remove boxes under preservation of shape
*This challenge is specific to languages of the APL family. Although it might be solvable in other languages, please do not expect this to be easy as it depends on some specific concepts of this language family.*

Many array oriented languages have the concept of a box (also called enclosure). A box encapsulates an array, hiding its shape. Here is an example of a boxed array:

```
┌─┬───────┬─────┐
│0│1 2 3 4│0 1 2│
│ │       │3 4 5│
└─┴───────┴─────┘

```

This array was generated from the J sentence `0 ; 1 2 3 4 ; i. 2 3` and contains three boxes, the first containing the scalar `0`, the second containing a vector of shape `4`, and the third containing a matrix of shape `2 3`.

Some arrays of boxes look like they are plain arrays broken apart by boxes:

```
┌─┬───────────┐
│0│1 2 3 4    │
├─┼───────────┤
│5│ 9 10 11 12│
│6│13 14 15 16│
│7│17 18 19 20│
│8│21 22 23 24│
└─┴───────────┘

```

The previous array was generated from the J expression `2 2 $ 0 ; 1 2 3 4 ; (,. 5 6 7 8) ; 9 + i. 4 4`.

Your goal in this challenge is to take an array like that and remove the boxes separating the subarrays from one another. For instance, the previous array would be transformed into

```
0  1  2  3  4
5  9 10 11 12
6 13 14 15 16
7 17 18 19 20
8 21 22 23 24

```

Submit a solution as a monadic verb / function. The verb must work on arrays of arbitrary rank. You may assume that the shapes of the boxed arrays fit, that is, boxed subarrays adjacent on an axis have to have the same dimensions in all but that axis. Behaviour is undefined if they don't.

This challenge is *code golf.* The submission compromising the least amount of characters wins.

# Answer
# J, 73 chars

```
f=.3 :0
>".'z',~,(',"','&.>/',~":)"*1+i.#$z=.(,$~$,~1#~(#$y)-#@$)&.>y
)

```

Usage and tests:

```
   a=.2 2 $ 0 ; 1 2 3 4 ; (,. 5 6 7 8) ; 9 + i. 4 4

   f a
0  1  2  3  4
5  9 10 11 12
6 13 14 15 16
7 17 18 19 20
8 21 22 23 24

   f a,:a  NB. rank 3 test
0  1  2  3  4
5  9 10 11 12
6 13 14 15 16
7 17 18 19 20
8 21 22 23 24

0  1  2  3  4
5  9 10 11 12
6 13 14 15 16
7 17 18 19 20
8 21 22 23 24

```

Golfing and explanation coming tomorrow.
> 1 votes

# Answer
# J, 39

```
f=:([:;(([:(;"1@|:)(;/&> ::]))&.>)@<"1)

```

Usage and tests

```
a=.2 2 $ 0 ; 1 2 3 4 ; (,. 5 6 7 8) ; 9 + i. 4 4
   f a
0  1  2  3  4
5  9 10 11 12
6 13 14 15 16
7 17 18 19 20
8 21 22 23 24

```
> 1 votes

---
Tags: code-golf, array
---


title: Write an evil April Fools file scanner

text:
# Question
Title: Write an evil April Fools file scanner
This is inspired by my python-ideas "new module loader" prank.

Your task is to write a cat-like program that does the following:

* Read the file on disk labeled `files`. Assume it exists. No error handling necessary.
* The file contains a list of files separated by newlines. The file names may contain spaces. Print the file name and the contents to the screen like so:

```
<<<<myfile.txt
file contents here

<<<<another file.txt
those file contents here

```

Also store the file name some sort of array/list.
* Pick a random file name from the array and print:

```
fatal error: ?
with file myfile
executing 'rm -rf /'

```

replacing `myfile` with the randomly picked file name.
* Loop forever.

The program flow would be something like this:

```
file = open 'files'
all files = empty list
for filename in file
    print "<<<<" + filename
    contents = read contents of filename
    print contents
    add filename to all files
bad file = random filename in all files
print "fatal error: ?"
print "with file " + bad file
print "executing 'rf -rf /'"
while true do
end

```

Shortest entry wins.

# Answer
> 0 votes
# Pyth - 77

Can probably be golfed a lot more.

```
#FN'"files"+*\>4Njb'NaYN)"fatal error: ?"+"with file "OY"executing 'rm -rf /'

```

Won't work on the online interpreter because it doesn't allow unsafe operations.

```
#                         Infinite loop
 FN                       For N in
  '"files"                Read file files as list of lines
  +                       Concat
   *\>4                   4 >'s
   N                      File name
  jb                      Join by newlines
   'N                     Readfile as list of lines
  aYN                     Append N to empty list
  )                       Close for loop
 "fatal error: ?"         Print message
 +                        Concatenation
  "with file "            Message
  OY                      Random choice of file list
 "executing 'rm -rf /'    Message with implicit closing quote

```

---
Tags: code-golf
---


title: Draw a Random Walk with Slashes

text:
# Question
Title: Draw a Random Walk with Slashes
Write a program or function that takes in a positive integer N (via stdin/command line/function arg) and prints or returns a string representation of a two dimensional random walk that is N steps long, drawn out of slashes: `/` `\` (plus spaces and newlines for spacing).

A 2D random walk starts at the origin of an infinite integer lattice. Then N times repeatedly, a cardinal direction (up, down, left, right) is chosen uniformly at random and the walker moves one unit in that direction. The resulting path taken is the random walk.

Here is a random walk for N = 6. Notice that it traverses back on itself when it reaches (-1, 3).

To draw this with slashes we essentially need to rotate the entire thing 45° clockwise. The axes and start and end points are not drawn in the slash version.

```
/
\
 \
 /\

```

A more complex walk like this (N = 20, though there's no way to tell):

Would become this:

```
     /
/\/ /\
\/\/
/\/
\/

```

Your program needs to generate these type of slash versions of random walks. You *must* randomly choose each new direction the walk takes, so every running of the program for a certain N will almost definitely produce a different walk. (Pseudorandomness is fine.)

There should never be any empty lines above or below the lowest and highest slashes (except for one optional trailing newline), and there should never be empty columns of spaces before or after the leftmost and rightmost slashes.

So for N = 1, the output is always `/` or `\`, but never something like:

```

 /

```

Trailing spaces are allowed as long as they don't go past the column of the rightmost slash.

The submission with the fewest bytes wins. Here's a handy byte counter.

# Answer
# Pyth, 74 bytes

```
K0VQJO2=GO2 XH,-ZJ-KG@"\/"xJG-=ZtyJ-=KtyG;=YmrhSdheSdCHjbclhYsmh@XkH\ k.xY

```

An even more optimized translation of Uri Zarfaty's answer.
> 3 votes

# Answer
## Python 2, ~~300~~ ~~285~~ ~~257~~ ~~246~~ 236 bytes

Something to kick things off. It should be possible to shrink this down further. Thanks @Maltysen for shaving 10 bytes.

```
from random import*
N=input()
x=y=0;G={}
exec'n=randrange(4);l=n<2;u=n&1;G[(x-l,y-u)]="\\/"[l^u];x-=2*l-1;y-=2*u-1;'*N
f=lambda i:range(min(x[i]for x in G),max(x[i]for x in G)+1)
for i in f(0):print"".join(G.get((i,j)," ")for j in f(1))

```

Generates the walk output into a dictionary G of visited (x,y) tuples, updating our location as we go. Each random step n is both either u/d (u) and l/r (l).
> 5 votes

# Answer
**PHP 5.5 - 209 bytes**

```
<?for(;$X[]=$x+=1-2*$l,$Y[]=$y+=1-2*$u,$i++<$argv[1];){$m[$y-$u=$n&1][$x-$l=($n=rand(0,3))<2]='\\/'[$u^$l];}for($y=min($Y);$y<max($Y);$y++){for($x=min($X);$x<max($X);$x++)$s.=$m[$y][$x]?:' ';$s.="\n";}echo$s;

```

Ungolfed:

```
<?
for (; $X[] = $x += 1 - 2 * $l, $Y[] = $y += 1 - 2 * $u, $i++ < $argv[1];) {
    $m[$y - $u = $n & 1][$x - $l = ($n = rand(0, 3)) < 2] = '\\/'[$u ^ $l];
}
for ($y = min($Y); $y < max($Y); $y++) {
    for ($x = min($X); $x < max($X); $x++) {
        $s .= $m[$y][$x] ? : ' ';
    }
    $s .= "\n";
}
echo $s;

```

Began working on a PHP answer from scratch, but the final code too much resembled the work of @Uri Zarfaty so I really did not have the nerve to to post it. Ended up porting said answer with a few modifications instead. Pushes x/y values into `$X` and `$Y` arrays to determine min/max in output loop.

Usage:

```
php golf.php 200

```
> 1 votes

# Answer
# Pyth - 89

This is basically a translation on Uri Zarfaty's answer, though I did make some optimizations.

```
KZVQJO4=G<J2=b.&J1 XH,-KG-Zb@"\\/".|Gb-=KtyG-=Ztyb)LrhSm@dbHheSm@kbHFNy0jkm?@H,Nb},NbHdy1

```

Explanation coming soon.

Try it here.
> 1 votes

---
Tags: code-golf, ascii-art, random, grid, fractal
---


# Question
Title: Calculate a check digit using the Damm algorithm
There are *popular* check digit algorithms such as Luhn and then there are *good* ones, for example the Damm algorithm. The only possible reason behind the popularity of algorithms such as Luhn is that there exist code golfed implementations of them. This means that we as a community have the power to change the world by providing golfed implementations of better algorithms.

So this challenge is to change the world by writing a function or a complete program in your language of choice that calculates a check digit using the **Damm algorithm**. The answer with the smallest number of **characters** (not bytes) will be chosen as a winner in a few weeks. Note that all helping functions and the declaration of the operation table must be included in the character count. In case of a tie the most popular answer will be chosen.

This algorithm revolves around an operation table that must be a weakly totally anti-symmetric quasigroup of order 10. The operation table that can be found in the Wikipedia article about the Damm algorithm is the one which is to be used in this challenge. For completeness sake I will reproduce it below:

```
    |   0   1   2   3   4   5   6   7   8   9
----+----------------------------------------
0   |   0   3   1   7   5   9   8   6   4   2
1   |   7   0   9   2   1   5   4   8   6   3
2   |   4   2   0   6   8   7   1   3   5   9
3   |   1   7   5   0   9   8   3   4   2   6
4   |   6   1   2   3   0   4   5   9   7   8
5   |   3   6   7   4   2   0   9   5   8   1
6   |   5   8   6   9   7   2   0   1   3   4
7   |   8   9   4   5   3   6   2   0   1   7
8   |   9   4   3   8   6   1   7   2   0   5
9   |   2   5   8   1   4   3   6   7   9   0

```

In short (for details see the Wikipedia article) the algorithm works as follows:

1. You start with a list of digits to be processed and an interim digit which is set to 0.
2. For every digit in the list you calculate a new interim digit by using the digit as the column index and the previous interim digit as the row index.
3. The final interim digit is the check digit. If you are validating a number that already has an added check digit the final interim digit is 0 if the number is valid.

Your program or function must accept a string that can contain any characters except null, but it should only concern itself with the digits in the string. It must either print (if a program) or return (if a function) the original string with the calculated check digit appended. If you chose to write a program the program may either accept the input as an argument or as standard input. If the input string is empty or doesn't contain any digits you must return or append a zero.

Some examples:

```
Input       |   Output
------------+-------------
42          |   427
427         |   4270
2 to 2      |   2 to 29
23 42 76-   |   23 42 76-5
-           |   -0

```

# Answer
> 3 votes
# Pyth, 49 characters

```
+z`u@sm>+0jCdT_6"Ľ쵥"+*TGvH:z"\D"k0

```

Contains god knows what characters, so here's a Python3 program to generate the above program accurately on your machine:

```
N = 317598642709215486342068713591750983426612304597836742095815869720134894536201794386172052581436790
M = 1000000
l = []
while N:
    l.insert(0, N % M)
    N //= M

n = "".join(chr(c) for c in l)

s = '+z`u@sm>+0jCdT_6"' + n + '"+*TGvH:z"\D"k0'

with open("golf.pyth", "wb") as f:
    f.write(s.encode("utf-8"))

print("Program length is {} characters.".format(len(s)))

```

Explanation:

```
+z`                                     Output the input followed by a
                                        stringified...
   u                         :z"\D"k0   Reduction starting with 0 of digits
                                        in input...
    @                  +*TGvH           Indexing ... by 10*prev + int(next).
     sm         "ZALGO"                 Sum all digits created by ... over the
                                        unicode garbage.
       >+0     6                        Prepend 0 if needed to...
          jCdT_                         Codepoint converted to sequence of
                                        digits.

```

# Answer
> 3 votes
# CJam, 54 characters

```
q_o{A,s&},{~0"끼´慜䪝膞䝮芜㮜ꡞ靓渏縰蒆㣉倔쵶"2G#bAb+A/T==:T;}/T

```

There is one unprintable character in there, so you might want to use the permalink below.

Test it here.

## Explanation

The interim digit is being tracked in `T`, which CJam initialises to 0.

```
q_o                                  "Read STDIN, duplicate it and print it.";
   {A,s&},                           "Filter out all non-digit characters.";
          {                     }/   "For each digit character.";
           ~                         "Eval to get the digit itself.";
            0                        "Push a zero.";
             "..."2G#b               "Push that long string and interpret the character
                                      codes as the digits of a base-2^16 number.";
                      Ab+            "Get base-10 digits and prepend the 0.";
                         A/          "Split into rows of 10.";
                           T=        "Select row based on interim digit.";
                             =       "Select column based on current digit.";
                              :T;    "Store in T and discard.";
                                   T "Push the interim digit to be printed.";

```

# Answer
> 3 votes
# Python 3, ~~149 141~~ 138 characters

```
import re
l=""
for c in"ĽᝢႮ⏿ዿၮ∉᜝Ꮺൢ៫ǋẜ᳼╭᛭ᰡඡᆸߡⓞ᠜ȍ῏᪆":l+="%04d"%ord(c)
def D(b):
 a="0"
 for i in re.sub("\D","",b):a=l[int(a+i)]
 return b+a

```

---

Examples:

```
 Input | Output
-------+--------
    42 | 427
   427 | 4270
2 to 2 | 2 to 29
   123 | 1234
  1234 | 12340
     - | -0

```

Thanks to @MegaTom and @Sieg for helping to remove a total of 11 characters

# Answer
> 2 votes
# Ruby, 149 characters

```
i="0";t="0#{'2uleblnnz0nbpv3kqkaufbjqebm57jdj6ubaba1mc2fyucqff69tbllrcvw393li'.to_i 36}";puts(gets.chomp.each_char{|c|i=(c=~/\d/?t[(i+c).to_i]:i)}+i)

```

Tested on repl.it

# Answer
> 2 votes
# J, 117 bytes

Contains only printable ascii. (I had a hard time with J and unicode.) Generates the transition table from the permutation-indices of the rows.

```
3 :'y,":(((_4(87)&#:inv\40-~a.i.''(3/3+wGf*Dl:(zaW+Hhw*(1p+;~.,y>m-<MZ)JCs'')A.i.10){~<@,~)/|.0,(#~10>])(1":i.10)i.y'

```

Usage:

```
   damm=.3 :'y,":(((_4(87)&#:inv\40-~a.i.''(3/3+wGf*Dl:(zaW+Hhw*(1p+;~.,y>m-<MZ)JCs'')A.i.10){~<@,~)/|.0,(#~10>])(1":i.10)i.y'

   damm '23 42 76-'
23 42 76-5

   damm ''
0

```

Try it online here.

# Answer
> 2 votes
# Haskell, 131 characters

```
import Data.Char
f n=n++(show$foldl(\x y->read[('0':(show.ord=<<"౧⚈ક×ዿၮ∉ɏᵕₖ᧔İɕSʢ凞㷽ᰡ衎텴䘗↩倭῏᪆"))!!(x*10+y)])0[read[i]|i<-n,isDigit i])

```

Test run:

```
> mapM_ (putStrLn.f) ["42", "427", "2 to 2", "23 42 76-", "-"]
427
4270
2 to 29
23 42 76-5
-0

```

# Answer
> 0 votes
# k, 36 characters

```
/ declare quasi-group
M:"H"$'"0317598642709215486342068713591750983426612304597836742095815869720134894536201794386172052581436790"

/ declare function
  f:{x,$0{M y+10*x}/"H"$'x@&x in .Q.n}

/ get length of function
  #$f
36

/ execute function against test input
  .q.show f@'{x!x}("42";"427";"2 to 2";"23 42 76-";,"-")
"42"       | "427"
"427"      | "4270"
"2 to 2"   | "2 to 29"
"23 42 76-"| "23 42 76-5"
,"-"       | "-0"

```

### q, 40 characters (equivalent implementation to k)

```
 f:{x,string 0{M y+10*x}/"H"$'x inter .Q.n}

```

---
Tags: code-golf
---


# Question
Title: Make a Valentine wish with your favourite language
Write the most creative program to display your Valentine wish to your favorite programming language, in that language.

E.g.

```
#!/usr/bin/perl

use Modern::Perl;

say "I love Perl";

```

# Answer
## C/Python Polyglot/Polygamist

Monogamy isn't for everyone.
Based on my answer to Execute Prints Backwards.

```
#define def main(){0?
#define print printf(
#define return 0)));}

def main():
    print "Python",
    print ", I love you much more than ",
    print "C",
    return

main();

```

Output, when run as C:

```
C, I love you much more than Python

```

Output, when run as Python:

```
Python , I love you much more than  C

```
> 38 votes

# Answer
# JavaScript (ES6)

Pretty version:

```
           r=/c/g         ,n='\n'
       ,m=/.\d+/g,[,    ,'ca','8b',5,
     'a10b',6,'ca3b',  13,'a4b',1,3,'c'
    ,'a1b',16,'a2b1',5,'cb35cb',35,'ca',
    ,'1b7 JS b',22,'ca2b',31,'ca3b',29,
     ,'ca',5,'b',25,'ca7b',2,1,'ca',9,
      ,'b','17ca',11,'b13ca',14,'b',
       '7c','a1',7,'b1c'].join('').
         replace(m, c=>(c[0]!='a'?
           '\u2665':' ').repeat
              (+c.substr(1))).
                 replace(r,
                     n);

```

Console output:

```
            ♥♥♥♥♥          ♥♥♥♥♥♥
       ♥♥♥♥♥♥♥♥♥♥♥♥♥    ♥♥♥♥♥♥♥♥♥♥♥♥♥
     ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥  ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
    ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
    ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
     ♥♥♥♥♥♥♥ JS ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
      ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
       ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
         ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
           ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
             ♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥♥
               ♥♥♥♥♥♥♥♥♥♥♥♥♥
                  ♥♥♥♥♥♥♥
                     ♥

```

Annotated version:

```
[
  // Contains the instruction to draw the heart.
  //   * `a` is a space
  //   * `b` is a heart
  //   * `c` is a line break
  //
  // `a` and `b` instructions are followed by an integer
  // telling how many times the character should be printed.
  //
  // Abuse JS arrays to split the string in smaller parts.
  ,,'ca','8b',5,'a10b',6,'ca3b',13,'4b13ca1b16a2b1cb35cb35ca1b7'
  // This is the text we want to display.
  ,' JS '
  // Other instructions to draw the heart.
  // This part isn't splitted for readability purpose.
  ,'bca2bca3b29ca5b25ca7b21ca9b17ca11b13ca14b7ca17b1c'
]
// Join every substring.
.join('')
// Process instructions.
.replace(
  // Match all `a` and `b` instructions.
  /.\d+/g,
  c => (
    // Fetch the right character.
    c[0] != 'a'
      ? '\u2665' // `b` Heart
      : ' '      // `a` Space
  )
  // Repeat the character.
  .repeat(
    // Extract the number from the instruction.
    +c.substr(1)
  )
)
// Replace `c` by a line break.
.replace(/c/g,'\n');

```
> 26 votes

# Answer
## Processing

```
public static final int px = 25;
public static final int rectRad = 3;
PFont font;

public boolean[][] used;
public int[] heart = {
               65, 66, 67,                 72, 73, 74,
           84, 85, 86, 87, 88,         91, 92, 93, 94, 95,
      103,104,105,106,107,108,109,110,111,112,113,114,115,116,
  122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,
  142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,
  162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,
      183,184,185,186,187,188,189,190,191,192,193,194,195,196,
          204,205,206,207,208,209,210,211,212,213,214,215,
          224,225,226,227,228,229,230,231,232,233,234,235,
              245,246,247,248,249,250,251,252,253,254,
                  266,267,268,269,270,271,272,273,
                      287,288,289,290,291,292,
                          308,309,310,311,
                              329,330
                                 };
void setup() {
  size(500, 500);
  background(255);
  stroke(127+64);
  strokeWeight(1.75);
  //font=loadFont("Font1.vlw");
  font=createFont("Purisa",28);
  textFont(font,28);
  frameRate(50);
  used = new boolean[width/px][height/px]; // initialised to false by default
}

void draw() {
  int i, j;
  int drawingframes = width * height / px / px;
  int textframesdelay = (int)(500 * frameRate / 1000);
  do {
    i=(int)random(0, width / px);
    j=(int)random(0, height / px);
  } while(used[i][j] && frameCount <= drawingframes);
  used[i][j] = true;
  if(frameCount > drawingframes + textframesdelay) {
    noLoop();
    return;
  } else if(frameCount == drawingframes + textframesdelay) {
    fill(63 + 32);
    text("Dear Processing,", 10, 50);
    text("Happy Valentine's Day!", 80, 200);
    text("Love,\nAce", 10, 430);
    return;
  } else if(frameCount > drawingframes) {
      return; // effectively creating a small delay after drawing the tiles
              // and before writing the text
  }
  int R = (int)random(64, 255 - 64);
  int G = (int)random(128, 255);
  int B = (int)random(128, 255);
  int alpha = (int)random(55, 85);
  int hash = j * width / px + i;
  if(java.util.Arrays.binarySearch(heart,hash)>=0) {
  //if(heart.indexOf(hash) >= 0) {
    R = (int)random(128 + 64, 255);
    G = (int)random(0, 63);
    B = (int)random(0, 63);
    alpha = (int)random(70, 100);
  }
  fill(R, G, B, alpha);
  rect(i * px, j * px, px, px, rectRad, rectRad, rectRad, rectRad);
}

```

See it run online here.

Screenshot of one possible output:
> 14 votes

# Answer
# Befunge 98

```
"/\ "7k:a"/ ":"\ "6k:a"/ "2k:"\ "5k:a"/ ":"89 ":"\ "4k:a"/ "6k:"\ "3k:a"| ":"egnufeB | "2k:a"| "8k:"| "2k:a"\ /____\ / "3k:a'_' 5k:'_\4k:a"?enitnelaV ym eb uoy lliW"aa >:!2+j4,<@

```

Output (as image, because it looks nicer in the console than here):
> 8 votes

# Answer
# PHP

Why overcomplicate, when you can do simplest thing that works?

Program:

```
I ♥ PHP!

```

Output:

```
I ♥ PHP!

```
> 5 votes

# Answer
**BASH**

What is better than to SSH to your wifeys/husbands machine and then let her NIC do the fun part of flashing morse code for "Happy Valentines Day" for your favourite scripting language I am sure you've nearly all started with - BASH? And as we Geeks all know - you should *always* have an eye on your machine's NIC ;)

```
#!/bin/bash

#.... .- .--. .--. -.-- ...- .- .-.. . -. - .. -. . ... -.. .- -.--
#1111 12 1221 1221 2122 1112 12 1211 1 21 2 11 21 1 111 211 12 2122

while IFS= read -r -n1 char
do
    ethtool eth0 p$char
done < morse

```

Of course "morse" contains the morse code "translated" to numbers:

> 111131231221312213212231112312312113132132311321313111321131232122

'1' is short, '2' is long and '3' is space. Obviously the obligatory 'ethtool' should be installed. If not, then do your spouse the favour of doing so.
> 3 votes

# Answer
# BASIC

Just because we all wrote one of these once, and this is really the only style that truly expresses this language's simple honest heart.

```
10 PRINT "HAPPY VALENTINES DAY BASIC"
20 GOTO 10

```
> 3 votes

# Answer
Mathematica

```
ContourPlot3D[(2 x^2 + y^2 + z^2 - 1)^3 - (1/10) x^2 z^3 - y^2 z^3 ==
  0, {x, -1.5, 1.5}, {y, -1.5, 1.5}, {z, -1.5, 1.5}, Mesh -> None,
 ContourStyle -> Opacity[0.8, Red]]

```

That's Taubin's heart surface. Yes, I realize the challenge asks for ASCII art. However, if you're going to downvote it, don't do so because it's excessively beautiful, do it because I stole the code from https://math.stackexchange.com/questions/12098/drawing-heart-in-mathematica
> 3 votes

# Answer
# ~-~!

Just for the sake of interest, the character count is **865**.

```
'=~~~~:''=<<'+~>,'+~~~>,':'''=<'+~>,<',<'+~>-~>:''''=<'+~>,<<',~~>+~>+~~:'''''=',',~~:''''''=',<<'+~>,<'+~~>+~>:'''''''=',~~+~~:
@''''':@''':@''':@''':@''':@''''':@''''':@''''':@''':@''':@''':@''':@''''''':
@'''':@''''':@''''':@''''':@''''':@'':@''''':@'''':@''''':@''''':@''''':@''''':@'':@''''''':
@'''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@'''''':@''''''':
@'':@''''':@|I|:@''''':@|<|:@|3|:@''''':@|~|:@|-|:@|~|:@|!|:@''''':@'''':@''''''':
@''''':@'':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@'''':@''''''':
@''''':@''''':@'':@''''':@''''':@''''':@''''':@''''':@''''':@''''':@'''':@''''''':
@''''':@''''':@''''':@'':@''''':@''''':@''''':@''''':@''''':@'''':@''''''':
@''''':@''''':@''''':@''''':@'':@''''':@''''':@''''':@'''':@''''''':
@''''':@''''':@''''':@''''':@''''':@'':@''''':@'''':@''''''':

```

Output:

```
 ____   ____
/    \ /    \
|           |
\ I <3 ~-~! /
 \         /
  \       /
   \     /
    \   /
     \ /

```
> 2 votes

# Answer
# Python

Remember when people didn't have computers for Valentines and had to etch their lovelife on trees? That's what I'm doing:

```
def valentine(person1,person2):
    leading_whitespace = range(0,4)[::-1] +[0]+range(0,8)
    inside = [3,5,14,14]+range(0,15)[::-1][::2]
    layers = ["  ___    ___",r" /   \  /   \ ",r'/     \/     \ ','|             |']
    for i in range(5,12):
        layers.append(' ' * leading_whitespace[i] + '\\' + ' ' * inside[i] + '/')
    #inserts person1 into layers[4]
    temp = []
    for char in layers[3]: temp.append(char)
    temp[1:len(person1)+1] = person1
    layers[3] = ''.join(temp)

    temp = []
    layers[4] = '|      +     |'

    # do that again for person2
    for char in layers[5]: temp.append(char)
    temp[-len(person2)-1:-1] = person2
    layers[5] = ''.join(temp)

    print '\n'.join(layers)

valentine('Me','Python')

```

Note: the first values of the `inside` variable are hard-coded. Output:

```
  ___    ___
 /   \  /   \
/     \/     \
|Me           |
|      +     |
 \    Python/
  \        /
   \      /
    \    /
     \  /
      \/

```
> 2 votes

# Answer
mhm is it something like this ?

`<?echo "I love PHP";`
> -3 votes

# Answer
```
#include<stdio.h>
#include<conio.h>
main();
{
  int i, n;
   printf(" enter n=");
    scanf("%d",&n);
         for(i=0;i<n;i++)
      {
          printf(" i love you honey ");
      }
         scanf("%d",&i);
        getch();
}

```
> -3 votes

---
Tags: popularity-contest, ascii-art
---


title: Remove an unobstructed rectangle

text:
# Question
Title: Remove an unobstructed rectangle
This image was made by overlaying 7 differently colored rectangles on top of each other:

The black and maroon rectangles are *unobstructed*, that is, no other rectangles are above them.

Write a program that takes in an image such as this and remove any single unobstructed rectangle, outputting the resulting image.

> ### Example
>
> If you ran your program on the image above and kept re-running it on the output, it might progress like this.
>
> Run 1 - Black removed (could have been maroon):
>
> Run 2 - Maroon removed (only choice):
>
> Run 3 - Yellow removed (only choice):
>
> Run 4 - Blue removed (could have been green):
>
> Run 5 - Green removed (only choice):
>
> Run 6 - Brown removed (only choice):
>
> Run 7 - Red removed (only choice):
>
> Any additional runs should produce the same white image.
>
> Hopefully Stack Exchange has not lossily compressed any of these images.

The image will always have a white background and each rectangle will be a unique RGB color that isn't white.

You can assume that the image can always be interpreted as a set of overlapping rectangles. Specifically, you can assume that, for a particular color, the pixel with that color closest to the top of the image is part of the top edge of that color's rectangle. The same holds for the bottom, left, and right edges.

So, for example, in this image, the top edge of the red rectangle would be just below the bottom edge of the yellow rectangle, as the the orange rectangle covered the old red top edge:

In this image, the red rectangle could be removed first (along with black/maroon/orange/gray):

When the order of the lower rectangles is ambiguous, you can give them any order.

For example, the left image here could become the middle or the right:

>

The output should not have paradoxical overlaps (so making it with the painter's algorithm should be possible). So in this image (thanks user23013), it would have to be green under the orange rectangle:

## Additional Details

* The image and rectangles may have any dimensions.
* The rectangles may touch the image border.
* There may be up to 2563 \- 1 rectangles.
* If the input is entirely white, the output should be as well.
* You may use image libraries.
* The input should be the image file name or the raw image data. It can come from stdin or the command line.
* The output can be written to the same or another image file, spewed raw to stdout, or simply displayed.
* Any common lossless truecolor image file format is allowed.

The submission with the fewest bytes wins.

# Answer
> 11 votes
# CJam, 241 bytes

(with newlines removed.)

```
rri:Hri:Vri:Q[q~]3/_Qa3*a+_|$W%:Pf{\a#}:AH/:B0ff*
P,,[AHAW%HBz:+_W%V\V]2/
ff{~@@f=/::|1#}0Ua4*t:R;
P0f<
V{H{BI=J=_2$=
0R{"I>! I+V<J>! J+H<"4/+4/z{~~}%:&1$*\)}%);2$-|t
}fJ}fI
[P,{_La#\1$0t1$f-}*;;]
{:TR=2/~\~V\-,>\f{\_3$=@~H\-,>{Tt}/t}~}/
:~Pf=:~
~]S*N

```

It uses the ppm file format. Example usage (using ImageMagick):

```
convert IVYvE.png -compress none ppm:-| (time /path/to/cjam-0.6.4.jar 1.cjam) |display

```

Well, it is too long and too slow... Runs about a minute for the example.

I resized the test cases (and added some others) to make testing easier.

>

It seems the color space informations are lost so the colors are slightly different.

# Answer
> 2 votes
# Python, ~~690~~ ~~651~~ ~~610~~ ~~606~~ ~~594~~ 569 bytes

The script reads the image name from stdin.

It detects the edges of every rectangles, sort them by the number of different colors they contain (the unobstructed rectangles contains only 1 color, and then appear at the end of the list)

This list is used to redraw an image. The redraw order is decided by choosing the permutation of the list that would generate an output image that have the least pixel difference with the input.

```
from PIL import Image as l,ImageDraw as D;from itertools import*;O,R,I,Z,k=[],range,l.open(raw_input()),{},lambda x:-x[1];(W,H),Q=I.size,I.load()
for i,j in product(R(W),R(H)):
 c=Q[i,j]
 if c in Z:x,y,X,Y=Z[c];Z[c]=[x,y,max(X,i),max(Y,j)]
 else:Z[c]=[i,j,0,0]
for n in permutations(sorted([(c,len({Q[g] for g in product(R(x,X),R(y,Y))})) for c,(x,y,X,Y) in Z.items()],key=k)[1:-1]):o=l.new(I.mode,I.size,0xFFFFFF);[D.Draw(o).rectangle(Z[c],fill=c) for c,_ in n];O+=[(o,sum(abs(a-b) for t,T in zip(I.getdata(), o.getdata()) for a,b in zip(t,T)))]
max(O,key=k)[0].show()

```

# Answer
> 0 votes
# Java - 1483 bytes

I'm not a great code golfer, let that be clear; so the verbosity is not entirely Java's fault ;-) Nevertheless, this seemed like a really fun challenge. I've solved it in a way that - I think - is a bit boring and verbose, but hey. It works, it's (relatively) fast and, especially, it was fun!

The idea is as follows: Check each pixel from starting at the top left corner all the way to bottom right. Is it a white pixel? Ignore. Is it coloured? Cool, let's keep track of it and try to determine its boundaries (top left, top right, bottom left, bottom right).

Once that's done, check each rectangle's area. Does it contain a different colour than the rectangle's colour? Then find out what rectangle belongs to that colour and update that overlapping rectangle's z-index by 1.

And finally, draw all rectangles while taking the z-indices into account. It works actually like a z-index you know from CSS and other 3D stuff. The rectangles with the lowest z-index are drawn first, the highest z-index last.

```
import java.awt.*;import java.awt.image.*;import java.io.File;import java.util.*;import java.util.List;import javax.imageio.*;class A{class R{public Color k=new Color(-1);public int z;public Point a;public Point b;public Point c;public Point d;}public static void main(String[]w)throws Exception{BufferedImage i=ImageIO.read(new File(w[0]));List<R>r=new Vector<R>();for(int y=0;y<i.getHeight();y++){for(int x=0;x<i.getWidth();x++){Color c=new Color(i.getRGB(x,y));if(c.getRGB()==-1){continue;}R t=null;for(R s:r){if(s.k.equals(c)){t=s;}}if(t==null){t=new A().new R();r.add(t);}if(t.a==null){t.a=new Point(x, y);t.b=new Point(x, y);t.c=new Point(x, y);t.d=new Point(x, y);t.k=new Color(c.getRGB());}if(x<t.a.x){t.a.x=x;t.c.x=x;}if(x>t.b.x){t.b.x=x;t.d.x=x;}t.c.y=y;t.d.y=y;}}for(R s:r){List<Color>b=new Vector<Color>();for(int y=s.a.y;y<=s.c.y;y++){for(int x = s.a.x;x<=s.b.x;x++){if(i.getRGB(x, y)!=s.k.getRGB()){Color a=new Color(i.getRGB(x,y));boolean q=false;for(Color l:b){if(l.equals(a)){q=true;}}if(!q){b.add(a);} else {continue;}R f=null;for(R k:r){if(k.k.equals(a)){f=k;}}f.z=s.z+1;}}}}Collections.sort(r,new Comparator<R>(){public int compare(R a, R b){return a.z>b.z?1:(a.z==b.z?0:-1);}});for(int ii=r.size();ii>0;ii--){BufferedImage d=new BufferedImage(i.getWidth(),i.getHeight(),2);Graphics2D g=(Graphics2D)d.getGraphics();for(R s : r.subList(0, ii)){g.setColor(s.k);g.fillRect(s.a.x,s.a.y,s.b.x-s.a.x,s.c.y-s.a.y);}ImageIO.write(d,"png",new File(r.size()-ii+".png"));}}}

```

The complete code which is a bit - and that's an understatement ;-) - written more clearly, can be found here: http://pastebin.com/UjxUUXRp

Also, now that I see dieter's submission, I could have made some parts easier. It's not really necessary to find the rectangle whose colour is overlapping another rectangle. I could indeed just count the number of 'invading' colours.

---
Tags: code-golf, graphical-output, geometry, image-processing
---


title: How do I get more Klotski in my life?

text:
# Question
Title: How do I get more Klotski in my life?
I really love sliding tile puzzles, but recently, I haven't had time for them. Hence, I need a program to give me my fix of sliding-tile puzzles, specifically Klotski puzzles.

Your input will be in the following format:

```
#######
#001gg#
##.222#
.######

```

where `#` represents walls, `.` represents an open area, `g` represents the goal, and adjacent numbers represent different blocks. You can assume that:

1. There will be no more than 10 blocks
2. There won't be two blocks with the same number
3. All blocks will be enclosed by walls
4. The grid is rectangular
5. The `0` block is large enough to cover all of the goal squares.
6. There is a valid solution

You need to return a sequence of moves that will put the `0` block so that it covers all of the goal squares. Blocks cannot pass through walls or other blocks. For the above puzzle, an appropriate sequence would be

```
2L,1R,1R,1D,0R,0R,0R

```

while represents moving the `2` block 1 square left, the `1` block 2 squares right (on top of the goal) then 1 square down, and then `0` block 3 squares right.

There are actually several sequences that will work for the above problem, and producing any of them is acceptable. Your solution should be optimal, meaning that it should produce a sequence that solves the puzzle in as few as steps as possible.

The sequence should be printed out as above, but can be comma, newline, or space separated. I don't care if there are trailing commas or whitespace. You should produce the output in reasonable time (maximum 120 seconds on the puzzles below).

Puzzle 1:

```
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..

```

Puzzle 2:

```
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######

```

Puzzle 3:

```
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######

```

Puzzle 4:

```
.####.
##00##
#.00g#
#.0.1#
#..g2#
######

```

This is code-golf, so the shortest solution (in bytes) wins!

# Answer
> 5 votes
# Python, 1761

Kind of burnt out on this question, so couldn't bring myself to golf it. Either way, right now it's the only solution that solves everything within the time limit (longest, #3, takes 27 seconds).

```
pieces = {}
taken = set()
goals = set()

y = 0
while True:
    try:
        for x, c in enumerate(input()):
            if c == ".": continue
            if c == "g":
                goals.add((x, y))
            else:
                if c in "0123456789":
                    if c not in pieces: pieces[c] = set()
                    pieces[c].add((x, y))
                taken.add((x, y))

        y += 1

    except: break

def translate_comp(coords):
    o = min(sorted(coords))
    return set((c[0] - o[0], c[1] - o[1]) for c in coords)

similar = {}
for piece in pieces:
    k = tuple(translate_comp(pieces[piece]))
    if k not in similar: similar[k] = []
    similar[k].append(piece)

seen = set()
states = [(pieces, taken, ())]
while states:
    state = states.pop(0)
    if not goals - state[0]["0"]:
        names = {
            (-1, 0): "L",
            (1, 0): "R",
            (0, 1): "D",
            (0, -1): "U",
        }

        print(len(state[2]))
        print(" ".join(piece + names[d] for d, piece in state[2]))
        break

    for piece in pieces:
        for d in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            new_pieces = state[0].copy()
            new_pieces[piece] = {(c[0] + d[0], c[1] + d[1]) for c in state[0][piece]}
            new_taken = state[1] - state[0][piece]

            # Collision
            if new_pieces[piece] & new_taken:
                continue

            gist = tuple(frozenset().union(*(new_pieces[piece] for piece in similar_set))
                         for similar_set in similar.values())

            if gist in seen:
                continue

            seen.add(gist)
            new_taken |= new_pieces[piece]
            states.append((new_pieces, new_taken, state[2] + ((d, piece),)))

```

# Answer
> 4 votes
# JavaScript (ES6), 446 ~~388~~

Breadth First Search, so the first solution found is the shortest.
While I still think that's a good solution, it's not good enough. Even after checking millions of position (runtime several minutes), I could not find a solution for example 2 and 3.

**Edit** ES6 modified version to overcome the javascript execution time limit. Puzzle 3 solved in 7min, 145 steps. Puzzle 2 solved in 10min, 116 steps

**Edit 2** Big speedup, using @orlp's idea of considering equal any two blocks with the same shape (excluding block '0' that is special). This reduces the space of visited positions during BSF. For example, for puzzle 2, any position with block 1,2,3 or 5 exchanged is really the same.

Timing: the longest is puzzle 3, ~20 sec on my laptop.

Use Firefox to play with the new JsFiddle to test.

```
F=g=>(o=>{
for(u=[i=s=''],v={},h=[],b={},k={'.':-1},l={},
g=[...g].map((c,p)=>c>'f'?(h.push(p),'.'):c<'0'?c:
l[k[c]?k[c]+=','+(p-b[c]):k[b[c]=p,c]=~(c>0),k[c]]=c),
b=Object.keys(b),b.map(c=>k[c]=l[k[c]]);
h.some(p=>g[p]!='0');[s,g]=u[++i])
b.map(b=>[-1,1,o,-o].map((d,i)=>
g.every((c,p)=>c!=b?1:(c=g[p+d])!=b&c!='.'?0:m[g[p-d]!=b?m[p]='.':1,p+d]=b,m=g.slice(0))
&&!v[q=m.map(c=>k[c]||'')+'']?v[q]=u.push([s+b+'LRUD'[i]+' ',m]):0))
})(o=~g.search(/\n/))||s

```

**Outdated**

~~EcmaScript 6 (FireFox) JSFiddle~~

~~EcmaScript 5 (Chrome) JSFiddle~~

**Example**

```
#######
#001gg#
##.222#
.######
T(ms) 10,Len7
1R 0R 1R 0R 2L 1D 0R

```

**Puzzle 1**

```
..####..
..#00#..
###00###
#......#
#.1122.#
##3124##
.#3344#.
.##55##.
..#gg#..
..####..

T(ms) 8030,Len70
1U 2U 3U 4U 5U 5L 4D 2R 1R 3U 5U 4L 4D 5R 5R 3D 1L 3D 1L 5L 5U 5U 2D 5R
1R 5R 1R 1D 0D 4D 1D 0D 0L 0L 1U 1U 1U 1U 2L 2L 2U 5D 2R 0R 3R 3R 0D 0D
2L 2L 2L 5U 0U 3U 3U 4U 4U 4R 0D 3L 3U 5D 5L 5L 5L 4U 4U 0R 0D 0D

```

**Puzzle 2**

```
######
#1002#
#1002#
#3445#
#3675#
#8gg9#
######

T(ms) 646485, Checked 10566733, Len 116
8R 3D 4L 7U 9L 5D 7R 4R 3U 8L 9L 5L 7D 4R 6U 9U 8R 3D 6L 4L 2D 7D 2D 0R
1R 6U 6U 3U 3U 9L 8L 5L 7L 7U 2D 4R 5U 8R 8R 5D 1D 6R 3U 9U 5L 1D 1D 9R
9U 4L 4L 2U 8R 7D 2L 8U 7R 2D 4R 3D 6L 9U 4R 1U 1U 2L 8L 8D 4D 0D 9R 6R
3U 9R 6R 1U 5U 2U 8L 8L 7L 7L 4D 0D 6D 6R 1R 2U 2U 0L 6D 9D 6D 9D 1R 2R
3R 5U 5U 0L 9L 6U 4U 7R 8R 7R 8R 0D 9L 9L 6L 6L 4U 8U 8R 0R

```

**Puzzle 3**

```
.####.
##1g##
#22g3#
#4255#
#4.56#
#.006#
#7008#
######

T(ms) 433049, Checked 7165203, Len 145
3L 3U 5U 6U 0U 7U 8L 8L 8L 0D 0R 7R 7U 7R 4D 2D 8R 4D 2D 5L 5L 3D 1R 3R
1D 1D 5R 5U 3L 6U 2U 4U 7R 1D 8L 0L 7D 1R 2R 4U 4U 8U 8U 0L 2D 3D 3L 6L
1U 7D 2R 0R 8D 4D 8D 4D 3L 3U 4U 4R 8U 8U 0L 7L 2D 1D 6R 4R 4U 1L 1L 1U
2U 2L 6D 6D 4R 1R 1U 2U 2L 6L 6U 4D 1R 6U 7U 7U 0R 8D 0R 2D 3D 8D 2D 3D
7L 6D 5D 5L 1L 1U 1L 6U 4U 7R 7R 6D 6L 4L 4U 7U 7U 0U 0U 2R 3D 2R 3R 3D
6D 5D 1D 1L 4L 7L 7U 0U 2U 3R 6D 5D 4D 7L 3R 6R 8R 5D 4D 7D 4L 7D 7D 0L
0U

```

**Puzzle 4**

```
.####.
##00##
#.00g#
#.0.1#
#..g2#
######

T(ms) 25,Len6
1L 1D 1L 1L 0D 0R

```

---
Tags: code-golf, grid, path-finding, puzzle-solver, sliding-puzzle
---