# Question
Title: Create icy avatar images for the winter season
It's winter, and the time of year has come for it to start getting cold (and for strange colorful headcloths to start appearing... soon). Let's write some code to make avatar pictures and other images frozen over, to fit the theme!

# Input

The input to submissions to this challenge should be an image (the image to make frozen) and a number (the threshold, which will be explained later).

You may input the image in any way your language supports them (a file path or URL as an argument, taking it from the clipboard, dragging and dropping an image, etc.) and in any format listed here that expresses colors in RGB (you can support / require RGBA instead if you want, but this is not a requirement).

You can input the number in any way you would like as well (command line argument, STDIN, input dialog, etc.), with the exception of hardcoding it into your program (ex. `n=10`). If you use a file path / URL for the image, it must be input in this manner as well.

# Output

The program must process the image according to the description below and then output it in any way you would like (to a file, showing it on screen, putting it on the clipboard, etc.).

# Description

Submissions should process the image with the following three steps. `n` refers to the number that your program received as input along with the image.

1. Apply a blur of radius `n` to the input image by replacing each pixel's R, G, and B values with the average R, G, and B values of all pixels within a Manhattan distance of `n` pixels, ignoring all out-of-bounds coordinates. (I.e. all pixels where the sum of the difference in X and the difference in Y is less than or equal to `n`.)

(note: I used a Gaussian blur for the images above because there was a convenient built-in function for it, so your images might look a little different.)
2. Set each pixel to a random pixel within a distance of `n/2` pixels ("distance" is defined the same way as in the previous step).

This should be done by looping through the image and setting each pixel to a random pixel in this range, so some pixels might disappear entirely and some might be duplicated.

All changes must apply at the same time. In other words, use the old values of the pixels (after step 1 but before this step), not the new values after setting them to a random pixel.
3. Multiply the "blue" RGB value of each pixel by 1.5, capping it at 255 (or whatever the maximum value for a band of pixels is) and rounding down.

# Rules

* You may use image libraries / image processing-related functions built into your language; however, you may not use any functions that perform one of the three major tasks mentioned in the description. For example, you can't use a `blur` function, but a `getPixel` function is fine.
* This is , so the shortest code in bytes wins!

# Answer
## Python 2 - 326 ~~339 358~~

Takes input from the user. File first, then `n`.

```
from PIL.Image import*;from random import*
a,N=input()
i=open(a)
d=list(i.getdata())
x,y=i.size
R=range(x*y)
m=lambda p,n,r:[p[i]for i in R if abs(n%x-i%x)+abs(n/y-i/y)<=r]
k=d[:]
for p in R:t=map(lambda x:sum(x)/len(x),zip(*m(k,p,N)));d[p]=t[0],t[1],min(255,t[2]*3/2)
i.putdata([choice(m(d,p,N/2))for p in R])
i.save('t.png')

```

This could probably be golfed much more :P Thanks to @SP3000 for golf ideas!

Sample input: (Windows)

```
"C:/Silly/Optimizer/Trix/Are/For/Kids.png",7

```

**Edit**: Bug fixed where blue was being propagated (Martin with n=20 is no longer a river ;\_; )

Martin with n=2:

Martin with n=10:

Martin with n=20:
> 14 votes

# Answer
## Python 2 - 617 Bytes

EDIT: golfed some, looks like FryAmTheEggMan has me beat though :)

```
from PIL import Image
import sys,random
j,i,n=sys.argv
n=int(n)
i=Image.open(i)
w,h=i.size
o=Image.new("RGB",(w,h))
D=list(i.getdata())
D=[D[i*w:i*w+w] for i in range(h)]
O=[]
d=n/2
z=range(-n,n+1)
M=lambda n:[[x,y] for x in z for y in z if abs(x)+abs(y)<=n]
m=M(n)
L=w*h
for i in range(L):
 y,x=i/w,i%w;c=r=g=b=0
 for q in m:
  try:C=D[y+q[1]][x+q[0]];r+=C[0];g+=C[1];b+=C[2];c+=1
  except:pass
 r/=c;g/=c;b/=c
 O.append((r,g,min(b*3/2,255)))
R=lambda:random.randint(-d,d)
for i in range(L):
 x,y=i%w,i/w;u=R();v=R()
 while not(0<x+u<w and 0<y+v<h):u=R();v=R()
 O[y*w+x]=O[(y+v)*w+(x+u)]
o.putdata(O)
o.save("b.png")

```
> 3 votes

# Answer
# Java - 1009 bytes

eh, I thought I could do better than this...

```
import java.awt.*;import java.io.*;import java.util.*;import javax.imageio.*;class r{public static void main(String[]v)throws Exception{java.awt.image.BufferedImage i=ImageIO.read(new File("y.png"));int n=Byte.valueOf(v[0]),w=i.getWidth(),h=i.getHeight();for(int z=0;z<w*h;z++){int x=z/h,y=z%h,r=0,g=0,b=0,c=0,x2,y2,k;for(x2=x-n;x2<=x+n;x2++){for(y2=y-n;y2<=y+n;y2++){if(Math.abs(x2-x)+Math.abs(y2-y)<=n&&x2>=0&&x2<w&&y2>=0&&y2<h){k=i.getRGB(x2,y2); r+=(k>>16)&0xFF;g+=(k>>8)&0xFF;b+=k&0xFF;c++;}}}i.setRGB(x,y,new Color(r/c,g/c,b/c).getRGB());}int[]t=new int[w*h];for(int z=0;z<h*w;z++){int x=z/h,y=z%h,x2,y2;ArrayList<Integer>e=new ArrayList<>();for(x2=x-n;x2<=x+n;x2++){for(y2=y-n;y2<=y+n;y2++){if(Math.abs(x2-x)+Math.abs(y2-y)<=n/2&&x2>=0&&y2>=0&&x2<w&&y2<h)e.add(i.getRGB(x2,y2));}}int p=e.get((int)(Math.random()*e.size())),b=(int)((p&0xFF)*1.5);t[x*h+y]=new Color((p>>16)&0xFF,(p>>8)&0xFF,b>255?255:b).getRGB();}for(int d=0;d<w*h;d++){i.setRGB(d/h,d%h,t[d]);}ImageIO.write(i,"PNG",new File("n.png"));}}

```

---

```
import java.awt.*;
import java.io.*;
import java.util.*;
import javax.imageio.*;
class IceBlur{
    public static void main(String[]v)throws Exception{
        java.awt.image.BufferedImage i=ImageIO.read(new File("blah.png"));
        int n=Byte.valueOf(v[0]),w=i.getWidth(),h=i.getHeight();
        for(int z=0;z<w*h;z++){
            int x=z/h,y=z%h,r=0,g=0,b=0,c=0,x2,y2,k;
            for(x2=x-n;x2<=x+n;x2++){
                for(y2=y-n;y2<=y+n;y2++){
                    if(Math.abs(x2-x)+Math.abs(y2-y)<=n&&x2>=0&&x2<w&&y2>=0&&y2<h){
                        k=i.getRGB(x2,y2);
                        r+=(k>>16)&0xFF;
                        g+=(k>>8)&0xFF;
                        b+=k&0xFF;
                        c++;}}}i.setRGB(x,y,new Color(r/c,g/c,b/c).getRGB());}
        int[]t=new int[w*h];
        for(int z=0;z<h*w;z++){
            int x=z/h,y=z%h,x2,y2;
            ArrayList<Integer>e=new ArrayList<>();
            for(x2=x-n;x2<=x+n;x2++){
                for(y2=y-n;y2<=y+n;y2++){
                    if(Math.abs(x2-x)+Math.abs(y2-y)<=n/2&&x2>=0&&y2>=0&&x2<w&&y2<h)e.add(i.getRGB(x2, y2));}}
            int p=e.get((int)(Math.random()*e.size())),b=(int)((p&0xFF)*1.5);
            t[x*h+y]=new Color((p>>16)&0xFF,(p>>8)&0xFF,b>255?255:b).getRGB();}
        for(int d=0;d<w*h;d++){i.setRGB(d/h, d%h, t[d]);}
        ImageIO.write(i,"PNG",new File("blah2.png"));}}

```

Martin with n=5:

n=20:

Me with 10:
> 3 votes

# Answer
# C, 429 (391 + 38 for define flags)

```
i,R,G,B,q;char*c,t[99];main(r,a,b,k,z,p){scanf("%*[^ ]%d%*6s%d%[^N]%*[^R]R\n",&a,&b,t);int j=a*b,d[j],e[j];F(c=d;c<d+j;*c++=getchar());F(;i<j;e[i++]=X<<24|B/q<<16|G/q<<8|R/q,R=G=B=q=0)F(k=0;k<j;)p=d[k++],D<r&&(++q,R+=p&X,G+=p>>8&X,B+=p>>16&X);F(i=!printf("P7\nWIDTH %d\nHEIGHT %d%sNDHDR\n",a,b,t);i<j;d[i++]=e[k])F(;k=rand()%j,D>r/2;);F(c=d;q<j*4;i=(q%4-2?2:3)*c[q]/2,putchar(i>X?X:i),++q);}

```

Input format: `pam` file with no comments or extra whitespace in header, contents passed via STDIN.

`n` arguments are required (they can be anything).

Output format: `pam` file in STDOUT.

To compile:

```
gcc -DX=255 -DF=for "-DD=z=abs(k-i),z/b+z%a" -Wl,--stack,33554432 -funsigned-char icyavatars.c -o icyavatars

```

`-Wl,--stack,33554432` increases the stack size; this may be changed or removed, depending on the size of the picture being processed (the program requires a stack size greater than twice the number of pixels times 4).

`-funsigned-char` has gcc use `unsigned char` instead of `signed char` for `char`. The C standards allows for either of these options, and this option is only needed here because gcc uses `signed char` by default.

To run (n=5):

```
./icyavatars random argument here fourth fifth < image.pam > output.pam

```

**Note:** If compiling on Windows, `stdio.h`, `fcntl.h` and `io.h` must be included, and the following code added to the start of `main()` in order for the program to read/write to STDIN/STDOUT as binary, not text, streams (this is irrelevant on Linux, but Windows uses `\r\n` instead of `\n` for text streams).

```
setmode(fileno(stdin), _O_BINARY);
setmode(fileno(stdout), _O_BINARY);

```

### Commented version

```
int i,R,G,B,q;
char *c,t[99];
main(r,a,b,k,z,p){
    // read all of header
    // save a large chunk to t, save width to a, save height to b
    scanf("%*[^ ]%d%*6s%d%[^N]%*[^R]R\n", &a, &b, t);
    // create arrays for holding the pixels
    int j = a * b, d[j], e[j];
    // each pixel is 4 bytes, so we just read byte by byte to the int arrays
    for(c = d; c < d + j; ++c)
        *c=getchar();

    // calculating average rgb
    for(i = 0; i < j; ++i){
        // check every pixel; add r/g/b values to R/G/B if manhattan distance < r-1
        for(k = 0; k < j; ++k){
            // pixel being checked
            p = d[k];
            // manhattan distance
            z = abs(k - i)/b + abs(k - i)%a;
            if(z < r){
                // extract components and add
                ++q;
                R += p & 255;
                G += p >> 8 & 255;
                B += p >> 16 & 255;
            }
        }
        // set pixel in e (not d) to average RGB and 255 alpha
        e[i]= 255<<24 | B/q<<16 | G/q<<8 | R/q;
        // clear temporary variables
        R = G = B = q = 0;
    }

    // print header
    printf("P7\nWIDTH %d\nHEIGHT %d%sNDHDR\n",a,b,t);
    // choose random pixels
    for(i = 0; i < j; ++i){
        // loop until randomly generated integer represents a pixel that is close enough
        do{
            k = rand() % j;
            // manhattan distance
            z = abs(k - i)/b + abs(k - i)%a;
        }while(z > r/2);
        // set d to the new pixel value
        d[i] = e[k];
    }
    // apply blue scaling and output
    for(c = d, q = 0; q < j * 4; ++q){
        // 3/2 if blue component, 1 otherwise
        i = (q % 4 - 2 ? 2 : 3)*c[q]/2;
        // cap components at 255
        putchar(i > 255 ? 255 : i);
    }
}

```

Martin with n=10:

Martin with n=20:

Martin with n=100:
> 3 votes

# Answer
# R, 440 chars

```
f=function(n,p){a=png::readPNG(p);b=a;N=nrow(a);M=ncol(a);r=row(a[,,1]);c=col(a[,,1]);for(i in 1:N)for(j in 1:M)b[i,j,]=apply(a,3,function(x)mean(x[abs(r-i)+abs(c-j)<=n]));for(i in 1:N)for(j in 1:M){g=which(abs(r-i)+abs(c-j)<=n/2,arr.ind=T);o=sample(1:nrow(g),1);b[i,j,]=b[g[o,1],g[o,2],]};b[,,3]=b[,,3]*1.5;b[b>1]=1;png(w=M,h=N);par(mar=rep(0,4));plot(0,t="n",xli=c(1,M),yli=c(1,N),xaxs="i",yaxs="i",ax=F);rasterImage(b,1,1,M,N);dev.off()}

```

With line breaks for legibility:

```
f=function(n,p){
    a=png::readPNG(p) #use readPNG from package png
    b=a
    N=nrow(a)
    M=ncol(a)
    r=row(a[,,1])
    c=col(a[,,1])
    for(i in 1:N){ #braces can be deleted if all is contained in one line
        for(j in 1:M){
            b[i,j,]=apply(a,3,function(x)mean(x[abs(r-i)+abs(c-j)<=n]))
            }
        }
    for(i in 1:N){ #i'm sure this loop could be shortened
        for(j in 1:M){
            g=which(abs(r-i)+abs(c-j)<=n/2,arr.ind=T)
            o=sample(1:nrow(g),1)
            b[i,j,]=b[g[o,1],g[o,2],]
            }
        }
    b[,,3]=b[,,3]*1.5 #readPNG gives RGB values on a [0,1] range, so no need to round
    b[b>1]=1
    png(w=M,h=N)
    par(mar=rep(0,4))
    plot(0,t="n",xli=c(1,M),yli=c(1,N),xaxs="i",yaxs="i",ax=F)
    rasterImage(b,1,1,M,N)
    dev.off()
    }

```

Sample input: `f(2,"avatar.png")`

Results with n=2

... with n=10

... with n=20
> 1 votes

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


# Question
Title: Forming Polyominoes with a Chain of Rods
## Background

Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-intersecting polygons with axis-aligned sides can you form with a given chain?

Let's look at an example. Consider a particular chain consisting of 8 rods of length 1 and 2, which we can represent as `[1, 1, 2, 2, 1, 1, 2, 2]`. Up to rotations and translations, there are only 8 possible polyominoes (we do count different reflections):

This first rod is dark blue, and then we traverse the polygon in a *counter-clockwise* sense.

The sense of rotation doesn't affect the result in the above example. But let's consider another chain, `[3, 1, 1, 1, 2, 1, 1]`, which yields the following 3 polyominoes:

Notice that we do *not* include a reflection of the last polyomino, because it would require clockwise traversal.

If we had a more flexible chain of the same length, `[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]`, we would actually be able to form both reflections among some other polyoninoes, totalling 9:

## The Challenge

Given a description of a chain, as an array or similar, determine the number of distinct polyominoes you can form (up to rotations and translations) by using the rods *in order* while going around the perimeter in a counter-clockwise sense.

Please write a full program and include commands to compile (if applicable) and run your code from the command line. Please also include a link to a free compiler/interpreter for your language.

Your program should read the input from STDIN. The first line will contain an integer *M*. The next *M* lines will be test cases, each of which will be a space-separated list of rod lengths. Your program should print *M* lines to STDOUT, each of which consists of a single integer - the number of distinct polyominoes that can be formed.

You must only use a single thread.

Your program must not use more than 1 GB of memory at any time. (This is not a completely strict limit, but I will monitor your executable's memory usage, and kill any process that consistently uses more than 1 GB, or spikes significantly above it.)

To prevent excessive amounts of pre-computation, your code must not be longer than 20,000 bytes, and you must not read any files.

You must also not optimise towards the specific test cases chosen (e.g. by hardcoding their results). If I suspect that you do, I reserve the right to generate new benchmark sets. The test sets are random, so your program's performance on those should be representative for its performance on arbitrary input. The only assumption you're allowed to make is that the sum of the rod lengths is even.

## Scoring

I have provided benchmark sets for chains of *N* = 10, 11, ..., 20 rods. Each test set contains 50 random chains with lengths between 1 and 4 inclusive.

Your primary score is the largest *N* for which your program completes the entire test set within 5 minutes (on my machine, under Windows 8). The tie breaker will be the actual time taken by your program on that test set.

If anyone beats the largest test set, I will keep adding larger ones.

## Test Cases

You can use the following test cases to check the correctness of your implementation.

```
Input                            Output

1 1                              0
1 1 1 1                          1
1 1 1 1 1 1                      1
1 1 1 1 1 1 1 1                  3
1 1 1 1 1 1 1 1 1 1              9
1 1 1 1 1 1 1 1 1 1 1 1          36
1 1 1 1 1 1 1 1 1 1 1 1 1 1      157
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  758
1 1 2 2 1 1 2 2                  8
1 1 2 2 1 1 2 2 1 1              23
1 1 2 2 1 1 2 2 1 1 2 2          69
1 2 1 2 1 2 1 2                  3
1 2 1 2 1 2 1 2 1 2 1 2          37
1 2 3 2 1 2 3 2                  5
1 2 3 2 1 2 3 2 1 2 3 2          23
3 1 1 1 2 1 1                    3
1 2 3 4 5 6 7                    1
1 2 3 4 5 6 7 8                  3
1 2 3 4 5 6 7 8 9 10 11          5
2 1 5 3 3 2 3 3                  4
4 1 6 5 6 3 1 4                  2
3 5 3 5 1 4 1 1 3                5
1 4 3 2 2 5 5 4 6                4
4 1 3 2 1 2 3 3 1 4              18
1 1 1 1 1 2 3 3 2 1              24
3 1 4 1 2 2 1 1 2 4 1 2          107
2 4 2 4 2 2 3 4 2 4 2 3          114

```

You find an input file with these over here.

## Leaderboard

```
   User          Language       Max N      Time taken (MM:SS:mmm)

1. feersum       C++ 11         19         3:07:430

2. Sp3000        Python 3       18         2:30:181

```

# Answer
> 5 votes
# C++11

Updates: Added the first line of `c` which breaks out early if the distance is too far from the origin (which was the whole purpose of the variable `rlen`, but I forgot to write it in the first version). I changed it to use much less memory, but at the cost of time. It now solves N=20 in just under 5 minutes for me.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <ctime>

#define M std::map
#define MS 999
#define l (xM*2+1)

#define KITTENS(A,B)A##B
#define CATS(A,B)KITTENS(A,B)
#define LBL CATS(LBL,__LINE__)
#define unt unsigned
#define SU sizeof(unt)
#define SUB (SU*8)
#define newa (nb^SZ||fail("blob"),nb+++blob)

#define D

struct vec {int x, y;};

unt s[MS*2];
int xM, sl[MS];
vec X[MS];

struct a;
struct a  { M<unt,unt>v;};

#define SZ ((1<<29)/sizeof(a))
a*blob;
unt nb;

int fail(const char*msg)
{
    printf("failed:%s", msg);
    exit(1);
    return 1;
}

struct
{
    unt*m;
    bool operator()(int x, int y) { return m[(x+l*y)/SUB] >> (x+l*y)%SUB & 1; }
    void one(int x, int y) { m[(x+l*y)/SUB] |= 1U << (x+l*y)%SUB; }
    void zero(int x, int y) { m[(x+l*y)/SUB] &= ~(1U << (x+l*y)%SUB); }
} g;

unt c(a*A, vec x, unt rlen, unt sn) {
    if((unt)x.y+abs(x.x) > rlen) return 0;
    if(!rlen) {
        vec *cl=X, *cr=X, *ct=X;
        for(unt i=1; i<sn; i++) {
            #define BLAH(Z,A,B,o,O) \
                if(X[i].A o Z->A || (X[i].A == Z->A && X[i].B O Z->B)) \
                   Z = X+i

            BLAH(cl,x,y,<,>);
            BLAH(cr,x,y,>,<);
            BLAH(ct,y,x,>,>);
        }
        unt syms = 1;
        #define BLA(H,Z) {bool sy=1;for(unt o=0; o<sn; o++) sy &= (int)(1|-(H))*sl[o] == sl[(Z-X+o)%sn]; syms += sy;}
        BLA(~o&1,cl)
        BLA(1,ct)
        BLA(o&1,cr)

        #ifdef D
            //printf("D");for(int i=0;i<sn;i++)printf(" %u",sl[i]);printf("\n");
            if(syms==3) fail("symm");
        #endif

        return syms;
    }
    if(!(x.x|x.y|!sn)) return 0;
    X[sn] = x;

    unt k = 0;
    for(auto it: A->v) {
        int len = it.first;
        bool ve = sn&1;
        int dx = ve?0:len, dy = ve?len:0;

        #define PPCG(O)(x.x O (ve?0:z), x.y O (ve?z:0))
        #define MACR(O) { \
            vec v2 = {x.x O dx, x.y O dy}; \
            if(v2.y<0||(!v2.y&&v2.x<0)||abs(v2.x)>xM||v2.y>xM) \
                goto LBL; \
            for(int z=1; z<=len; z++) \
                if(g PPCG(O)) \
                    goto LBL; \
            for(int z=1; z<=len; z++) \
                g.one PPCG(O); \
            sl[sn] = O len; \
            k += c(blob+it.second, v2, rlen - len, sn+1); \
            for(int z=1; z<=len; z++) \
                g.zero PPCG(O); \
            } LBL: \

    MACR(+);
    MACR(-);
    }

    return k;
}

void stuff(a *n, unt j, unt r, unt len1)
{
    unt t=0;
    for(unt i=j; i<j+r; i++) {
        t += s[i];
        if((int)t > xM || (len1 && t>len1)) break;
        if(len1 && t < len1) continue;
        int r2 = r-(i-j)-1;
        if(r2) {
            unt x;
            if(n->v.count(t))
                x = n->v[t];
            else
                n->v[t] = x = newa - blob;
            stuff(blob+x, i+1, r2, 0);
        } else n->v[t] = -1;
    }
}

int main()
{
    time_t tim = time(0);
    blob = new a[SZ];
    int n;
    scanf("%u",&n);
    while(n--) {
        nb = 0;
        unt ns=0, tl=0;
        while(scanf("%u",s+ns)) {
            tl += s[ns];
            if(++ns==MS) return 1;
            if(getchar() < 11) break;
        }
        xM = ~-tl/2;
        g.m = (unt*)calloc((xM+1)*l/SU + 1,4);

        memcpy(s+ns, s, ns*SU);

        unt ans = 0;
        for(unt len1 = 1; (int)len1 <= xM; len1++) {
            a* a0 = newa;
            for(unt i=0; i<ns; i++)
                stuff(a0, i, ns, len1);
            ans += c(a0, {}, tl, 0);
            for(unt i=0; i<nb; i++)
                blob[i].v.clear();
        }
        printf("%d\n", ans/4);
        free(g.m);
    }

    tim = time(0) - tim;
    printf("time:%d",(int)tim);
    return 0;
}

```

Compile with

```
g++ --std=c++11 -O3 feersum.cpp -o feersum.exe

```

# Answer
> 3 votes
# Python 3 (with PyPy) — N = 18

```
ANGLE_COMPLEMENTS = {"A": "C", "F": "F", "C": "A"}
MOVE_ENUMS = {"U": 0, "R": 1, "D": 2, "L": 3}
OPPOSITE_DIR = {"U": "D", "D": "U", "L": "R", "R": "L", "": ""}

def canonical(angle_str):
    return min(angle_str[i:] + angle_str[:i] for i in range(len(angle_str)))

def to_angles(moves):
    """
    Convert a string of UDLR to a string of angles where
      A -> anticlockwise turn
      C -> clockwise turn
      F -> forward
    """

    angles = []

    for i in range(1, len(moves)):
        if moves[i] == moves[i-1]:
            angles.append("F")
        elif (MOVE_ENUMS[moves[i]] - MOVE_ENUMS[moves[i-1]]) % 4 == 1:
            angles.append("C")
        else:
            angles.append("A")

    if moves[0] == moves[len(moves)-1]:
        angles.append("F")
    elif (MOVE_ENUMS[moves[0]] - MOVE_ENUMS[moves[len(moves)-1]]) % 4 == 1:
        angles.append("C")
    else:
        angles.append("A")

    return "".join(angles)

def solve(rods):
    FOUND_ANGLE_STRS = set()

    def _solve(rods, rod_sum, point=(0, 0), moves2=None, visited=None, last_dir=""):
        # Stop when point is too far from origin
        if abs(point[0]) + abs(point[1]) > rod_sum:
            return

        # No more rods, check if we have a valid solution
        if not rods:
            if point == (0, 0):
               angle_str = to_angles("".join(moves2))

               if angle_str.count("A") - angle_str.count("C") == 4:
                   FOUND_ANGLE_STRS.add(canonical(angle_str))

            return

        r = rods.pop(0)

        if not visited:
            visited = set()
            move_dirs = [((r, 0), "R")]
            moves2 = []

        else:
            move_dirs = [((r,0), "R"), ((0,r), "U"), ((-r,0), "L"), ((0,-r), "D")]

        opp_dir = OPPOSITE_DIR[last_dir]

        for move, direction in move_dirs:
            if direction == opp_dir: continue

            new_point = (move[0] + point[0], move[1] + point[1])
            added_visited = set()
            search = True

            for i in range(min(point[0],new_point[0]), max(point[0],new_point[0])+1):
                for j in range(min(point[1],new_point[1]), max(point[1],new_point[1])+1):
                    if (i, j) != point:
                        if (i, j) in visited:
                            search = False

                            for a in added_visited:
                                visited.remove(a)

                            added_visited = set()
                            break

                        else:
                            visited.add((i, j))
                            added_visited.add((i, j))

                if not search:
                    break

            if search:
                moves2.append(direction*r)
                _solve(rods, rod_sum-r, new_point, moves2, visited, direction)
                moves2.pop()

            for a in added_visited:
                visited.remove(a)

        rods.insert(0, r)
        return

    _solve(rods, sum(rods))
    return len(FOUND_ANGLE_STRS)

num_rods = int(input())

for i in range(num_rods):
    rods = [int(x) for x in input().split(" ")]
    print(solve(rods))

```

Run with `./pypy <filename>`.

---

This is the reference implementation I wrote when discussing the question with Martin. It wasn't made with speed in mind and is quite hacky, but it should provide a good baseline to kick things off.

N = 18 takes about 2.5 minutes on my modest laptop.

## Algorithm

Rotations are checked by converting each shape into a series of `F` for forward, `A` for anticlockwise turn and `C` for clockwise turn at each lattice point on the boundary of the shape — I call this an *angle string*. Two shapes are rotationally identical if their angle strings are cyclic permutations. Rather than always checking this by comparing two angle strings directly, when we find a new shape we convert to a canonical form before storing. When we have a new candidate, we convert to the canonical form and check if we already have this (thus exploiting hashing, rather than iterating through the whole set).

The angle string is also used to check that the shape is formed anticlockwise, by making sure that the number of `A`s exceeds the number of `C`s by 4.

Self-intersection is naïvely checked by storing every lattice point on the boundary of the shape, and seeing if a point is visited twice.

The core algorithm is simple, placing the first rod to the right, then trying all possibilities for the remaining rods. If the rods reach a point which is too far from the origin (i.e. sum of remaining rod lengths is less than the Manhattan distance of the point from the origin), then we prematurely stop searching that subtree.

## Updates (latest first)

* 6/12: Introduced canonical form, added a few micro-optimisations
* 5/12: Fixed error in algorithm explanation. Made the quadratic cyclic-permutation-checking algorithm linear using the A,B cyclic permutations iff A substring of B+B method (I have no idea why I didn't do this earlier).

---
Tags: fastest-code, combinatorics
---


# Question
Title: Longest reverse palindromic DNA substring
As you may know, in **DNA** there are four bases — adenine (`A`), cytosine (`C`), guanine (`G`) and thymine (`T`). Typically `A` bonds with `T` and `C` bonds with `G`, forming the "rungs" of the DNA double helix structure.

We define the **complement** of a base to be the base it bonds to — i.e. the complement of `A` is `T`, the complement of `T` is `A`, the complement of `C` is `G` and the complement of `G` is `C`. We can also define the complement of a DNA string to be the string with each base complemented, e.g. the complement of `GATATC` is `CTATAG`.

Because of the double-stranded structure of DNA, the bases on one strand are complementary to the bases on the other strand. However DNA has a direction, and DNA transcription occurs in opposite directions on the two strands. Hence molecular biologists are often interested in the **reverse complement** of a DNA string — quite literally the reverse of the complement of the string.

To extend our previous example, the reverse complement of `GATATC` is `CTATAG` backwards, so `GATATC`. As you may have noticed, in this example the reverse complement is equal to the original string — we call such a string a **reverse palindrome**.\*

Given a string of DNA, can you find the longest substring which is a reverse palindrome?

<sup>\*I use the term "reverse palindrome", taken from Rosalind, to differentiate from the usual meaning of palindrome.</sup>

---

## Input

Input will be a single string consisting of only the characters `ACGT` in upper case. You may write either a function or a full program for this challenge.

## Output

You may choose to output via either printing or returning (the latter choice is only available in the case of a function).

Your program should output the longest reverse palindromic substring of the input string, if there is a unique solution. If multiple solutions exist, then you may either output any single one of them, or all of them (your choice). Duplicates are okay if you choose to output all of them.

The input is guaranteed to have a solution of at least length 2.

## Worked example

```
ATGGATCCG -> GGATCC

```

The reverse complement of `GGATCC` is itself (`GGATCC --complement--> CCTAGG --reverse--> GGATCC`), so `GGATCC` is a reverse palindrome. `GATC` is also a reverse palindome, but it is not the longest one.

## Test cases

```
AT -> AT
CGT -> CG
AGCA -> GC
GATTACA -> AT, TA
ATGGATCCG -> GGATCC
CCCCCGGGGG -> CCCCCGGGGG
ACATATATAGACT -> ATATAT, TATATA
ATTCGATCTATGTAAAGAGG -> TCGA, GATC
CGCACGTCTACGTACCTACGTAG -> CTACGTAG
TCAATGCATGCGGGTCTATATGCAT -> ATGCAT, GCATGC [, ATGCAT]
CGCTGAACTTTGCCCGTTGGTAGAACGGACTGATGTGAACGAGTGACCCG -> CG, GC, TA, AT [, GC, CG, CG, CG, CG]
CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG -> CCGTACGG

```

## Scoring

This is code golf, so the solution in the fewest bytes wins.

# Answer
# Pyth, ~~37 36 28~~ 24 bytes

```
ef&}TzqmaCd6T_mx4aCk6Tyz

```

Combining the tips from FryAmTheEggman and the reverse palindrome check trick from Peter, this is a super short version.

However, this only works with Pyth 3.0.1 which you can download from this link and run like

```
python3 pyth.py -c "ef&}TzqmaCd6T_mx4aCk6Tyz" <<< "ATTCGATCTATGTAAAGAGG"

```

(linux bash only. On windows, press Enter instead of the \<\<\< and then type the input)

---

This is my previous submission - 28 bytes solution

```
J"ACGT"ef&}TzqTjk_m@_JxJdTyz

```

Thanks to FryAmTheEggman for this version. This one creates all possible subsets of the input DNA string, filters the subsets on the condition that the subset is a substring of input and the reverse of transform is equal to the subset itself.

Due to all possible subset creation, this takes up even more memory than Peter's answer.

---

This is my first submission - 36 byte solution.

```
J"ACGT"eolNfqTjk_m@_JxJdTm:zhkek^Uz2

```

This is the exact translation of my CJam answer. I was hoping that this would be much smaller but turns out that lack of translation method made it almost similar size (still 2 bytes smaller though)

Try it online here
> 6 votes

# Answer
## GolfScript (35 34 bytes)

```
]{{..(;\);}%)}do{{6&}%.{4^}%-1%=}?

```

For testing purposes you may wish to use

```
]{{..(;\);}%.&)}do{{6&}%.{4^}%-1%=}?

```

which adds a `.&` to reduce the duplicated effort.

### Dissection

```
]{         # Gather string into an array and do-while...
  {        #   Map over each string in the array
    ..     #     Make a couple of copies of the string
    (;     #     Remove the first character from one of them
    \);    #     Remove the last character from the other
  }%
  )        #   Extract the last string from the array
}do        # Loop until that last string is ''
           # Because of the duplication we now have an array containing every substring
           # of the original string, and if we filter to the first occurrence of each
           # string then they're in descending order of length
{          # Find the first element in the string satisfying the condition...
  {6&}%    #   Map each character in the string to its bitwise & with 6
  .{4^}%   #   Duplicate, and map each to its bitwise ^ with 4
           #   This serves to test for A <-> T, C <-> G
  -1%=     #   Reverse and test for equality
}?

```
> 5 votes

# Answer
# CJam, ~~39~~ 38 bytes

I am sure this can be golfed further...

```
q:Q,,_m*{~Q<>}%{,~}${_"ACGT"_W%erW%=}=

```

Takes the DNA string from STDIN and outputs the longest reverse palindromic DNA to STDOUT

Try it online here

(Explanation soon) *(Saved 1 byte thanks to Peter)*
> 4 votes

# Answer
## Python 3, 125 chars

```
S=input()
l=[]
while S:
 s=_,*S=S
 while s:l+=[s]*all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]));*s,_=s
print(*max(l,key=len))

```

Look ma, no indexing! (Well, except to reverse the string, that doesn't count.)

Iterating over the substrings is done by taking off chars from the front and end using starred assignment. The outer loop removes characters for the start of `S`, and for each such suffix, `s` loops over all prefixes of it, testing them one by one.

Testing for reverse palindrome is done by the code

```
all(x+y in"ATA CGC"for x,y in zip(s,s[::-1]))

```

which checks that each symbol and its reversed-string counterpart are one of "AT", "TA", "CG", and "GC". I also found a set-based solution to be one character shorter, but loses two chars on requiring outer parens when used.

```
set(zip(s,s[::-1]))<=set(zip("ACTG","TGAC"))

```

This still feels like it can be shortened.

Finally, the longest palindrome is printed.

```
print(*max(l,key=len))

```

I hope space-separated outputs are OK. If a list also fine, the the star could be removed. I had tried tracking the running max in the loop instead, as well as cramming the inner loops into a list comprehension so I could take the max directly without constructing `l`, and both turned out slightly longer. But, it was close enough that it's hard to tell which approach is actually best.
> 4 votes

# Answer
## Perl - 59 bytes

```
#!perl -p
$_=$_[~!map$_[length]=$_,/((.)(?R)?(??{'$Q5'^$+.-$+}))/gi]

```

Counting the shebang as one, input is taken from `STDIN`.

**Sample usage:**

```
$ echo CTCGCGTTTGCATAACCGTACGGGCGGAACAGTCGGCGGTGCCTCCCAGG | perl dna.pl
CCGTACGG

```
> 3 votes

# Answer
## J (45)

```
{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.)

```

This is a function that takes a string:

```
   {.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.) 'ATGGATCCG'
┌──────┐
│GGATCC│
└──────┘

```

Explanation:

```
{.@(\:#&.>)@,@(('ACGT'&(|.@]-:[{~3-i.)#<)\\.)

              (                          \\.)  for each prefix of each suffix
               (                      #<)      include the argument if,
                        |.@]                      its reverse
                            -:                    is equal to
                'ACGT'&(      [{~3-i.)            the complement
            ,@                                 ravel
   (\:#&.>)@                                   sort by length of item
{.@                                            take the first one

```
> 3 votes

# Answer
# Python 2 - 177 bytes

```
s=raw_input()
r,l,o=range,len(s),[]
for a in[s[i:j+1]for i in r(l)for j in r(i,l)]:q=['TC GA'.index(c)-2for c in a];o+=[a if[-n for n in q][::-1]==q else'']
print max(o,key=len)

```

Simple brute force. The actual "reverse palindromic" check is the only interesting part. Here it is written more readably:

```
check = ['TC GA'.index(c)-2 for c in substring]
if [-n for n in check][::-1] == check:
    # substring is reverse palindromic

```

I do that on every possible substring and put them in a list if it's true. If it's false, I put in an empty string instead. When all the checks are done I output the longest element of the list. I used an empty string because it saves bytes over putting nothing in, but it also means the program won't choke if there's no solution. It outputs an empty line and exits gracefully.
> 3 votes

---
Tags: code-golf, chemistry, bioinformatics
---


title: Unique Array Combinations

text:
# Question
Title: Unique Array Combinations
The goal is to write a function or program which takes a set of integer arrays and returns a set of all possible arrays which meet the following criteria:

* A valid array must contain at least one number from each of the input arrays.
* A valid array cannot contain more than one number from a single input array.
* A valid array cannot contain duplicate values.

**Additional rules:**

* Order of the output does not matter.
* Input/Output can be in any format you wish.
* If no valid arrays exist, the result should be an empty array or blank string.

**Examples:**

```
input:
[[1,2],
 [2,1,0],
 [0,3,1]]

output:
[[2,3],
 [1]]

```

```
input:
[[1,3,4,7],
 [1,2,5,6],
 [3,4,8],
 [8,9]]

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

```

```
input:
[[1,2,3],
 [2,3,4],
 [1,4]]

output:
[]

```

# Answer
### GolfScript, 36 characters

```
:I[[]]\{{{|$}+1$/}%|}/{I{1$&,(},!*},

```

Input/output is standard GolfScript arrays, see in this example.

```
:I              # save input to variable I

# part 1: generate all possible sets with zero or one numbers from each array
# (zero or one is one char shorter than exactly one which would work also)
[[]]\           # push the set with an empty set
{               # iterate over all input sets
  {             #   iterate over the numbers in the current set
    {|$}+1$/    #     add this number to any set in the result
  }%
  |             #   join with the result set
}/

# part 2: filter for valid sets (i.e. exactly one number from each array)
{               # start of filter block
  I{            #   filter the input array of sets
    1$&         #     calculate overlap of the current set with the input set
    ,(          #     remove if length is equal to one
  },
  !             #   is the list empty? (i.e. all input matched the filter criterion)
  *             #   get rid of the second item on the stack
},              # end of filter block

```
> 6 votes

# Answer
# CJam, 35 bytes

```
q~:Q{m*{(+$_&}%}*_&{Q{1$&,(},,*!},p

```

Input is a list of list like:

```
[[1 3 4 7]
 [1 2 5 6]
 [3 4 8]
 [8 9]]

```

and output is the list of unique lists that match all conditions, like for above input,

```
[[1 8] [2 3 9] [3 5 9] [3 6 9] [2 4 9] [4 5 9] [4 6 9] [2 7 8] [5 7 8] [6 7 8]]

```

How it works:

```
q~:Q                                 "Evaluate the input and store it in Q";
    {          }*                    "Run this block for each adjacent pair in the array";
     m*                              "Calculate Cartesian product of the pair";
       {     }%                      "Map each cartesian product with the code block";
        (+$                          "Flatten the array and sort it";
           _&                        "Make the array unique";
                 _&                  "Only take unique cartesian products";
                   {            },   "Filter the cartesian products based on the code block";
                    Q{     },        "Put Q on stack and run it through this filter";
                      1$&            "Take ∩ of the input array with the cartesian product";
                         ,(          "Check that length of the ∩ should be greater than 1";
                             ,*!     "Now we have all the lists from the input list of list"
                                     "which matched more than 1 element from this cartesian"
                                     "product. So if this list is non empty, discard this"
                                     "cartesian product";
                                  p  "Print the filtered out valid unique arrays";

```

Try it online here
> 5 votes

# Answer
## Mathematica, ~~135~~ ~~84~~ 72 bytes

```
f=Cases[Union/@Tuples@#,l_/;!MemberQ[#,k_/;Length@Intersection[k,l]>1]]&

```

Less golf:

```
f = Cases[
   Union /@ Tuples@#,
   l_ /; ! MemberQ[#, k_ /; Length@Intersection[k, l] > 1]
] &

```

This defines a function `f` that expects the input as a plain Mathematica list of lists, e.g.

```
f[{{1, 2}, {2, 1, 0}, {0, 3, 1}}]

```

Basically, I'm creating a list of all lists that fulfil conditions 1 and 3, and then I'm filtering out those that violate conditions 2. ~~There might be a shortcut for one of the two, which I'll have to think about in more depth tomorrow.~~ Found that shortcut!
> 3 votes

# Answer
# ruby, ~~143~~ 114

Now shorter thanks to @Ventero.

```
h={};i=eval$*[0];v=i.flatten.uniq
loop{h[a=v.sample(1+rand(v.size)).sort]||=h[a]||i.any?{|o|(o&a).size!=1}?1:p(a)}

```

Usage:

```
ruby uniq_arr.rb '[[1,3,4,7],[1,2,5,6],[3,4,8],[8,9]]'
[2, 3, 9]
[6, 7, 8]
[3, 5, 9]
[1, 8]
[2, 7, 8]
[4, 6, 9]
[5, 7, 8]
[2, 4, 9]
[3, 6, 9]
[4, 5, 9]

```

Making it stop (eventually) is easy, but requires some code. It stops one h contains 2\**l-1 elements, l being the number of unique elements in i, i.flatten.uniq.size

http://ideone.com/zTlXZw
> 2 votes

# Answer
### Ruby — ~~80~~ 73 characters

@Howard knocks off 7 characters:

```
f=->a{a[0].product(*a).map(&:uniq).uniq.select{|l|a.all?{|x|(l&x).one?}}}

```

Some sample input:

```
a = [[1, 2], [2, 1, 0], [0, 3, 1]]
b = [[1,3,4,7], [1,2,5,6], [3,4,8], [8,9]]
c = [[1,2,3], [2,3,4], [1,4]]
d = [[]]
e = [[1,2]]

```

Output:

```
f[a] # => [[1], [2, 3]]
f[b] # => [[1, 8], [3, 2, 9], [3, 5, 9], [3, 6, 9], [4, 2, 9], [4, 5, 9], [4, 6, 9], [7, 2, 8], [7, 5, 8], [7, 6, 8]]
f[c] # => []
f[d] # => []
f[e] # => [[1], [2]]

```

### Haskell — 90 characters

I'm just learning Haskell, so I imagine this can be vastly improved. Same basic strategy as my Ruby solution.

```
import Data.List
f a=[l|l<-nub.map nub$sequence a,all(\x->length x==1)(map(intersect l)a)]

```
> 2 votes

# Answer
# Python, 157 characters

This is a straightforward brute-force implementation.

```
from itertools import*
a=input()
v=set(chain(*a))
print[x for x in chain(*[combinations(v,r)for r in range(len(v))])if all(1==len(set(x)&set(y))for y in a)]

```
> 1 votes

---
Tags: code-golf, combinatorics
---


title: Organize Halloween Candy - Hole #4

text:
# Question
Title: Organize Halloween Candy - Hole #4
See Hole #1 if you are confused.

What does every kid do after he/she collects buckets of candy over Halloween?

Sort it by type and size, of course1!

## The Challenge

Given a dumped-out bag of candy of varying shapes and sizes, sort the candy from left to right based on:

* First: The amount of candy (so 5 of one will be more left than 4 of another)
* Second (if there are any ties after the first): If the amount is the same, the candy with more **internal area** (based on number of characters) will rank higher.

If after the second sort there is still a tie, then you may choose either to be first.

## Input

You will be given the candy through stdin; strewn about. See examples below.

## Output

Output the candy ordered in the correct order. Note, candy should *always* be placed in *very* neat columns to appease your OCD fish2. The candy of the same type should be placed directly under one another. See examples below.

## What do you mean by "interior area"?

* The interior area of a piece of candy is measured by the total characters making up the candy as a whole.
* Any whitespace within a "border" is considered part of the area of the candy.
* A border is any connected loop of characters, each character diagonal or next to it's neighbor.

For example,

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

```

has more area than

```
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX

```

even though is has less characters overall.

## Examples

input:

```
                       _           \|            |/                                     _
    _               lllllll        -*------------*-            -\       /-           lllllll
 lllllll           lllllllll        |  /\  /\  / |             +|\ooooo/|+          lllllllll
lllllllll          llll+llll        | /  \/  \/  |             ||o     o||          llll+llll
llll+llll          lllllllll       -*------------*-            ||o     o||          lllllllll
lllllllll           lllllll        /|            |\            +|/ooooo\|+           lllllll
 lllllll               |                                       -/       \-              |
    |                  |                _                                               |
    |   -\       /-    |             lllllll                                            |
    |   +|\ooooo/|+    |            lllllllll                                           |
    |   ||o     o||    |            llll+llll                                           |
    |   ||o     o||    +            lllllllll                              rrr--rrr     +
    +   +|/ooooo\|+                  lllllll                                rr||rr
        -/       \-                     |                                   | || |
                                        |                                   | || |
                                        |                                   | || |
                                        |                                   | || |
                                        |            \|            |/       | || |
                                        +            -*------------*-       | || |
                                                      |  /\  /\  / |        | || |
                        -\       /-                   | /  \/  \/  |        | || |
                        +|\ooooo/|+                  -*------------*-       rr||rr
                        ||o     o||                  /|            |\      rrr--rrr
                        ||o     o||
                        +|/ooooo\|+
                        -/       \-

```

Would become

```
    _     \|            |/ -\       /- rrr--rrr
 lllllll  -*------------*- +|\ooooo/|+  rr||rr
lllllllll  |  /\  /\  / |  ||o     o||  | || |
llll+llll  | /  \/  \/  |  ||o     o||  | || |
lllllllll -*------------*- +|/ooooo\|+  | || |
 lllllll  /|            |\ -/       \-  | || |
    |                                   | || |
    |     \|            |/ -\       /-  | || |
    |     -*------------*- +|\ooooo/|+  | || |
    |      |  /\  /\  / |  ||o     o||  | || |
    |      | /  \/  \/  |  ||o     o||  rr||rr
    +     -*------------*- +|/ooooo\|+ rrr--rrr
          /|            |\ -/       \-
    _
 lllllll  \|            |/ -\       /-
lllllllll -*------------*- +|\ooooo/|+
llll+llll  |  /\  /\  / |  ||o     o||
lllllllll  | /  \/  \/  |  ||o     o||
 lllllll  -*------------*- +|/ooooo\|+
    |     /|            |\ -/       \-
    |
    |
    |
    |
    +

    _
 lllllll
lllllllll
llll+llll
lllllllll
 lllllll
    |
    |
    |
    |
    |
    +

    _
 lllllll
lllllllll
llll+llll
lllllllll
 lllllll
    |
    |
    |
    |
    |
    +

```

A second example:

```
                   qq                                                                 \/
                   qq                 qq      qq                                    +-----+
                                      qq      qq         qq                       +       |
 jjjjjjjj                                                qq         qq            |       |
  jjjjjj             \/                                             qq      qq    |       |
   jjjj            +-----+ <---notice that the left side is not connected   qq    +-------+
  jj  jj         +       |       <-->       <-->
 j      j        |       |
jj  <>  jj       |       |       <-->                                 qq            jjjjjjjj
 jj    jj        +-------+                                            qq             jjjjjj
   jjjj                                 qq           qq                               jjjj
                                        qq           qq                              jj  jj
                                                                                j      j
                      +---------------------------------------------------------+  jj  <>  jj
      ooooo           +---------------------------------------------------------+   jj    jj
     o     yyyyyy                                                                     jjjj
     o           ww - notice diagonal border, allowed
     o           ww                                                 jjjjjjjj
     o     yyyyyy          ooooo                ooooo                jjjjjj
      ooooo               o     yyyyyy         o     yyyyyy           jjjj
                          o           ww       o           ww        jj  jj
                          o           ww       o           ww       j      j
                          o     yyyyyy         o     yyyyyy        jj  <>  jj
                           ooooo                ooooo               jj    jj
                                                                      jjjj

```

Solution:

```
qq  ooooo          jjjjjjjj  <-->     \/    +---------------------------------------------------------+
qq o     yyyyyy     jjjjjj          +-----+ +---------------------------------------------------------+
   o           ww    jjjj    <--> +       |
qq o           ww   jj  jj        |       |
qq o     yyyyyy    j      j  <--> |       |
    ooooo         jj  <>  jj      +-------+
qq                 jj    jj
qq  ooooo            jjjj             \/
   o     yyyyyy                     +-----+
qq o           ww  jjjjjjjj       +       |
qq o           ww   jjjjjj        |       |
   o     yyyyyy      jjjj         |       |
qq  ooooo           jj  jj        +-------+
qq                 j      j
    ooooo         jj  <>  jj
qq o     yyyyyy    jj    jj
qq o           ww    jjjj
   o           ww
qq o     yyyyyy    jjjjjjjj
qq  ooooo           jjjjjj
                     jjjj
qq                  jj  jj
qq                 j      j
                  jj  <>  jj
qq                 jj    jj
qq                   jjjj

```

Note that columns have 1 character of spacing between them, and are aligned horizontally at the top. Also note that each candy is in an exact columns, each candy with 1 character of spacing in between.

## Scoring

This is code-golf, so shortest program (in bytes) wins.

1 What else would you do? Obviously you want to display your awesome might and power in the amount of candy you collected, right?

2 I know what you're thinking! A fish has to look through a *curved* bowl at your candy, so therefore it would be distorted anyway! Well, my fish lived (before it died) in a *rectangular* aquarium.

# Answer
> 7 votes
# Ruby, 928 characters

Whew, this one was fun!

```
w=[];b=' ';u=$<.read.split'
';k=->l,z,t,p{loop{y=!!1;z.each{|c|t.each{|o|v=[c[0]+o[0],c[1]+o[1]]
y=!(z+=[v])if v[0]>=0&&v[1]>=0&&v[0]<l.size&&v[1]<l[0].size&&p[l[v[0]][v[1]]]&&!z.index(v)}}
break if y};z};(y=y;z=k[u,[[u.index{|p|y=p.index /\S/},y]],([-1,0,1].product([-1,0,1])-[0,0]),->x{x!=b}]
n=z.min_by{|c|c[0]}[0];m=z.min_by{|c|c[1]}[1];q=Array.new(z.max_by{|c|c[0]}[0]-n+1){b*(z.max_by{|c|c[1]}[1]-m+1)}
z.each{|c|q[c[0]-n][c[1]-m]=u[c[0]][c[1]];u[c[0]][c[1]]=b};w+=[q])while u*''=~/\S/;o=Hash.new 0;w.each{|c|o[c]+=1}
p=->q{e=k[q,((0...q.size).flat_map{|x|[[x,0],[x,q[0].size-1]]}+(1...q[0].size-1).flat_map{|y|[[0,y],[q.size-1,y]]}).select{|c|q[c[0]][c[1]]==b},[[0,1],[0,-1],[1,0],[-1,0]],->x{x==b}]
(q.size*q[0].size)-e.size};r=o.sort_by{|k,v|v+(p[k]/1e3)}.reverse.map{|k,v|(k+[b*k[0].size])*v}
r.map!{|k|k+([b*k[0].size]*(r.max_by(&:size).size-k.size))};puts ([b]*r.max_by(&:size).size).zip(*r).map{|r|r.join(b)[2..-1]}

```

You can give the input on STDIN, or you can pass an input file as an argument (like `ruby organize.rb candy.txt`) and it will treat the file as STDIN automatically.

All semicolons can be replaced with newlines; I just glued some lines together to reduce vertical space.

Ungolfed (2367 chars):

```
#!/usr/bin/ruby
input = $<.read.split("\n")
candies = []

# utility method
flood = -> arr, coords, offsets, cond {
    loop {
        changed = false
        coords.each{|c|
            offsets.each{|o|
                nc = [c[0]+o[0], c[1]+o[1]]
                if nc[0] >= 0 && nc[1] >= 0 && nc[0] < arr.length && nc[1] < arr[0].length &&
                    cond[arr[nc[0]][nc[1]]] && !coords.index(nc)
                    coords.push nc
                    changed = true
                end
            }
        }
        break if !changed
    }
    coords
}

# while there are non-whitespace characters in the pile
while input.join =~ /\S/
    # get coordinates of the first character to flood-fill on
    y = nil
    x = input.index{|row| y = row.index /\S/ }

    # flood-fill on that character
    coords = flood[input, [[x, y]], ([-1,0,1].product([-1,0,1]) - [0, 0]), ->x{x != ' '}]

    # x = max, n = min
    xx = coords.max_by{|c| c[0] }[0]
    nx = coords.min_by{|c| c[0] }[0]
    xy = coords.max_by{|c| c[1] }[1]
    ny = coords.min_by{|c| c[1] }[1]

    # create a properly sized thingy for this one candy
    candy = Array.new(xx - nx + 1) {
        ' ' * (xy - ny + 1)
    }

    # fill the thingy, while also removing it from the pile
    coords.each{|c|
        candy[c[0] - nx][c[1] - ny] = input[c[0]][c[1]]
        input[c[0]][c[1]] = ' '
    }

    candies.push candy
end

# group by same candies
candytypes = Hash.new 0
candies.each{|c| candytypes[c] += 1 }

area = -> candy {
    # we want to eliminate surrounding spaces
    # so flood-fill all spaces that touch the edges
    surround = (0...candy.length).flat_map{|x| [[x, 0], [x, candy[0].length-1]] } +
        (1...candy[0].length-1).flat_map{|y| [[0, y], [candy.length-1, y]] }
    surround.select! {|c| candy[c[0]][c[1]] == ' ' }
    surround = flood[candy, surround, [[0,1],[0,-1],[1,0],[-1,0]], ->x{x == ' '}]

    # now just subtract amount of surrounding spaces from total amount of chars
    (candy.length * candy[0].length) - surround.length
}
columns = candytypes.sort_by {|k, v|
    # this is a pretty ugly hack
    v + (area[k] / 1000.0)
}.reverse.map{|k, v| (k + [' ' * k[0].length]) * v }
columns.map!{|k| k + ([' ' * k[0].length] * (columns.max_by(&:length).length - k.length)) }

puts ([' '] * columns.max_by(&:length).length).zip(*columns).map{|r| r.join(' ')[2..-1] }

```

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


title: Divide food to the poor equally!

text:
# Question
Title: Divide food to the poor equally!
# The problem

Through a terrible procastination accident you are reborn as Scrooge McDuck for a day. To make the most out of the situation you decide to give away food to the poor. Since you also are a mathematician you store the food in a vector `v(1,2,3)`.

You want to give each family approximately the same food. To make things simple each family has `n` members. The task is to write a code to split the vector `v` into rows of length `n` where each row has the same amount of ''food''.

Equality is measured by the standard deviation; how different the sum of each row (the food each family receives) is from the mean.

## Input

Input should be an integer `n` and a vector `v` The length of `v` does not have to be divisible by `n`; zero pad it if that is the case.

## Example

```
v = (4, 9, 3, 6, 19, 6, 9, 20, 9, 12, 19, 13, 7, 15)
n = 3

```

Should return

```
 4     6    19
 9     9    13
 3    20     7
 6     9    15
19    12     0

```

The sum of each row is 29,31,30,30,31, so the standard deviation is 0.748331 for `n` = 2. Note the presence of a 0 that we added.

## The output

The code should output the standard deviation. You can also print the matrix but this is not a requirement.

## The score

The winner is judged **not** by the shortest code, but by the **sum of the standard deviations**, given the test vector and `n` = 2, 3, and 23. e.g.

```
Score = your_func(2, foodvec) + your_func(3, foodvec) + your_func(23, foodvec)

```

Use the following vector to test http://pastebin.com/ybAYGHns and test for `n=2,3,23`. The final score is the *sum* of those three tests. The vector is somewhat big since Scrooge has a lot of food saved up.

# Answer
> 2 votes
## Python 3 using PyPy: 6.368014 + 0.701679 + 0.486916 = 7.556608

### Optimal for n = 2

There are 1000 numbers, so we want to distribute the food to 500 families. If the food vector is sorted (`food[1] >= food[2] >= ... >= food[500]`), then the minimal std is reached by giving the first family the food items `food[1]` and `food[500]`, the second family `food[2]` and `food[499]`, the third family `food[3]` and `food[498]`, ...

I thought of a quite easy proof. Basically I expanded the product of the std, removed the terms that appear in each food partition, and proofed that the result is minimal. If someone wants a more detailed explanation, just ask me nice.

### Approximation for n \> 2

I don't think, that there's a fast way of finding the optimal solution for n \> 2.

I start with an heuristic solution. I distribute the food items in sorted (descending) order to the family with the lowest food so far (only to such families, which have received less than n food items).

Afterwards I improve the solution, by swapping 1 food item between a pair of families. I use the `N` families with to lowest food and the `N` families with the most food so far. After all possible swaps, I choose the best swap, and call the local search recursively.

The bigger the value of `N` is, the lower will be the std (but also the running time will be longer). I used `N = 20` and when I can't find swap, I try again with `N = 100`. PyPy finishes all 3 test cases in less than 8 minutes.

### Code

```
def findSmallestStd(food, n):
    food.sort(reverse=True)
    while len(food) % n:
        food.append(0)
    family_count = len(food) // n

    if n == 2: # optimal
        return list(zip(food[:len(food)//2], reversed(food[len(food)//2:])))
    else: # heuristic approach
        partition = [[] for _ in range(family_count)]
        for food_item in sorted(food, reverse=True):
            partition.sort(key=lambda f: sum(f) if len(f) < n else float('inf'))
            partition[0].append(food_item)
        return local_search(partition, calc_std(partition))

def local_search(partition, best_std, N = 20):
    # find indices with smallest and largest sum
    families1 = nsmallest(N, partition, key=sum)
    families2 = nlargest(N, partition, key=sum)
    best_improved_swap = None

    for family1, family2 in product(families1, families2):
        for index1, index2 in product(range(len(family1)), range(len(family2))):
            family1[index1], family2[index2] = family2[index2], family1[index1]
            std = calc_std(partition)
            if std < best_std:
                best_std = std
                best_improved_swap = (family1, family2, index1, index2)
            family1[index1], family2[index2] = family2[index2], family1[index1]

    if best_improved_swap:
        family1, family2, index1, index2 = best_improved_swap
        family1[index1], family2[index2] = family2[index2], family1[index1]
        partition = local_search(partition, best_std)
    elif N < 100:
        return local_search(partition, best_std, 100)
    return partition

```

The complete code and the output is available on Github: Code, Output

### edit

I was confused about the std-calculation, that N3buchadnezzar proposed in the original question. I updated it to the correct mathematical definition, so we can compare different solutions.

### edit 2

In my last submission I varied the family count. E.g. the best solution for n = 2 used 507 families. N3buchadnezzar told me, that there have to be exactly `ceil(len(food) / n)` families. So I changed my code a little bit. Basically removed the loop over the family counts and improved the local search.

# Answer
> 2 votes
## Python 2: 6.368013505 + 96.84345115 + 5.572725419 = 108.784190072

This is probably not a very optimized or smart approach but it gave me decent results so i decided to post it. I sorted the list and chopped the list in groups of n long. The odd groups get reversed and then I zipped them together (just look at the code really). It's small and quick and it works fairly well on a big amount of numbers (not so much on a small amount, it scored around 3.5 on the example).

So this is my function:

```
def myFunction(v, n):
  v = sorted(v)
  while len(v) % n != 0:
     v = [0] + v
  lists = list(grouper(v, len(v)/n))
  for i in range(len(lists)):
     if i%2 == 0:
         lists[i] = lists[i][::-1]
  zippedList = list(zip(*lists))
  for i in range(len(zippedList)):
     zippedList[i] = sum(zippedList[i])
  print(zippedList)
  return numpy.std(zippedList)

def grouper(l, n):
   for i in range(0, len(l), n):
      yield l[i:i+n]

```

Because it's such an easy (read lazy) solution, it's very fast. The entire program took about 0.1s to run. With pypy it would be even faster but Numpy is apparently still not ported to pypy and i don't feel like manually calculating the standard deviation so yeah. If I made any huge mistakes (both on programming and english grammer) or have recommendations, tell me. It's the first time I gave a code challenge a try.

---
Tags: code-challenge, arithmetic, optimized-output
---


# Question
Title: Find a point's position on the integral Hilbert curve
The Hilbert curves are a class of space-filling fractal curves where every bend in the path is at a right angle and the curve as a whole fills up a square, with the property that sequences of consecutive segments are always displayed as contiguous blocks.

Traditionally, the curve is drawn as a series of very squiggly lines inside a square such that each segment becomes smaller and smaller until they fill up the whole square. However, like the Walsh matrix, it is also possible to represent the limit curve as a sequence of line segments connecting lattice points that grows infinitely until it fills up an entire quadrant of lattice points on the Cartesian plane.

Suppose we define such a curve as the *integral Hilbert curve*, as follows:

* Start at the origin.
* Move one unit right (`R`), one unit up (`U`), and one unit left (`L`). Down will be notated as `D`.
* Let `RUL` be `H_1`. Then define `H_2` as `H_1 U I_1 R I_1 D J_1` where:

+ `I_1` is `H_1` rotated 90 degrees counterclockwise and flipped horizontally.
    + `J_1` is `H_1` rotated 180 degrees.

Perform the steps of `H_2` after `H_1` to complete `H_2`.
* Define `H_3` as `H_2 R I_2 U I_2 L J_2`, where:

+ `I_2` is `H_2` rotated 90 degrees clockwise and flipped vertically.
    + `J_2` is `H_2` rotated 180 degrees.

Perform the steps of `H_3` after `H_2` to complete `H_3`.
* Define `H_4` and other `H_n` for even `n` the same way as `H_2`, but relative to `H_{n-1}`.
* Define `H_5` and other `H_n` for odd `n` the same way as `H_3`, but relative to `H_{n-1}`.
* The integral Hilbert curve is `H_infinity`.

We get a function `f(n) = (a, b)` in this way, where `(a, b)` is the position of a point moving `n` units along the integral Hilbert curve starting from the origin. You may notice that if we draw this curve `2^{2n}-1` units long we get the `n`th iteration of the unit-square Hilbert curve magnified `2^n` times.

Your task is to implement `f(n)`. The shortest code to do so in any language wins.

---

Example inputs and outputs:

```
> 0
(0, 0)
> 1
(1, 0)
> 9
(2, 3)
> 17
(4, 1)
> 27
(6, 3)
> 41
(7, 6)
> 228
(9, 3)
> 325
(24, 3)

```

Note that your solution's *algorithm* must work in general; if you choose to implement your algorithm in a language where integers are of bounded size, that bound must not be a factor in your program's code.

# Answer
> 3 votes
## GolfScript (62 bytes)

```
{1:a:b(.@4base{:?3%!:|b^?2<3?=.b^:b^^|!.a^:a^{\}*{@2*@+}2*}/\}

```

This is an anonymous function which takes `n` on the stack and leaves `x y` on the stack. Online demo

It's essentially the iterative code from the Wikipedia article reversed so that it processes the base-4 representation of `n` from most-significant to least-significant digit instead of least-significant to most-significant. This simplifies the bookkeeping required to output `x` and `y` in the right order.

Pseudocode translation (not tested, may contain errors):

```
a = b = true;
x = y = 0;
foreach (digit in n base 4) {
    p = (digit % 3 == 0) ^ b;
    q = (digit < 2) ^ b;
    b ^= (digit == 3);
    if (a) swap(p, q);
    a ^= (digit % 3 != 0);
    y = 2*y + (p ? 1 : 0);
    x = 2*x + (q ? 1 : 0);
    swap(x, y);
}
swap(x, y)

```

# Answer
> 3 votes
## R: ~~178~~ 169

Room for improvement in this, but it's a start

```
f=function(d){x=y=0;s=1;while(s<Inf){a=bitwAnd(1,d/2);b=bitwAnd(1,bitwXor(d,a));if(b==0){if(a==1){x=s-1-x;y=s-1-y};t=x;x=y;y=t};x=x+(s*a);y=y+(s*b);d=d/4;s=s*2};c(x,y)}

```

Test Run

```
> f(0)
[1] 0 0
> f(1)
[1] 1 0
> f(9)
[1] 2 3
> f(41)
[1] 7 6
> f(325)
[1] 24  3

```

---
Tags: code-golf
---