title: Reproduce an image using lines

text:
# Question
Title: Reproduce an image using lines
Write a program that takes in a true-color RGB image *I*, the maximum number of lines to draw *L*, and the minimum *m* and maximum *M* length of each line. Output an image *O* that looks as much as possible like *I* and is drawn using *L* or fewer straight lines, all of which have Euclidean length between *m* and *M*.

Each line must be one solid color, have both endpoints in the bounds of *O*, and be drawn using Bresenham's line algorithm (which most graphics libraries will already do for you). Individual lines can only be 1-pixel thick.

All lines, even those of length 0, should take up at least one pixel. Lines may be drawn on top of one another.

Before drawing any lines you may initialize the background of *O* to any solid color (that may depend on *I*).

## Details

* *O* should have the same dimensions as *I*.
* *L* will always be a nonnegative integer. It may be greater than the area of *I*.
* *m* and *M* are nonnegative floating point numbers with *M* \>= *m*. The distance between two pixels is the Euclidean distance between their centers. If this distance is less than *m* or greater than *M*, then a line between those pixels is not allowed.
* The lines should not be antialiased.
* Opacity and alpha should not be used.
* Your program should not take more than an hour to run on a decent modern computer on images with less than a million pixels and *L* less than 10,000.

## Test Images

You should of course show us your most accurate or interesting output images (which I expect will occur when *L* is between 5% and 25% of the number of pixels in *I*, and *m* and *M* are around one tenth of the diagonal size).

Here are some test images (click for originals). You may also post your own.

Simpler images:

This is a popularity contest. The highest voted submission wins.

## Notes

* It may be helpful to let *L* be derived from a percentage of total pixels in *I* as well as an absolute value. e.g. `>>> imageliner I=img.png L=50% m=10 M=20` would be the same thing as `>>> imageliner I=img.png L=32 m=10 M=20` if `img.png` were an 8 by 8 pixel image. Something similar could be done for *m* and *M*. This is not required.
* Since lines cannot go out of bounds, the longest lines possible will be the diagonal length of *I*. Having *M* higher than this should not break anything though.
* Naturally, if *m* is 0 and *L* is greater than or equal to the number of pixels in *I*, *O* could be identical to *I* by having length 0 "lines" at each pixel location. This behavior is not required.
* Arguably, reproducing the shape of *I* is more important than reproducing the color. You may want to look into edge detection.

# Answer
# C++ - somewhat random lines and then some

## First some random lines

The first step of the algorithm randomly generates lines, takes for the target image an average of the pixels along this, and then calculates if the summed up square of rgb space distances of all pixels would be lower if we would paint the new line (and only paint it, if it is). The new lines color for this is chosen as the channel wise average of the rgb values, with a -15/+15 random addition.

Things that I noticed and influenced the implementation:

* The initial color is the average of the complete image. This is to counter funny effects like when making it white, and the area is black, then already something as a bright green line is seen better, as it is nearer to black than the already white one.
* Taking the pure average color for the line is not so good as it turns out to be unable to generate highlights by being overwritten by later lines. Doing a little random deviation helps a bit, but if you look at starry night, it fails if the local contrast is high at many places.

I was experimenting with some numbers, and chose `L=0.3*pixel_count(I)` and left `m=10` and `M=50`. It will produce nice results starting at around `0.25` to `0.26` for the number of lines, but I chose 0.3 to have more room for accurate details.

For the full sized golden gate image, this resulted in 235929 lines to paint (for which it took a whopping 13 seconds here). Note that all images here are displayed in reduced size and you need to open them in a new tab/download them to view the full resolution.

## Erase the unworthy

The next step is rather expensive (for the 235k lines it took about an hour, but that should be well within the "an hour for 10k lines on 1 megapixel" time requirement), but it is also a bit surprising. I go through all the previously painted lines, and remove those that do not make the image better. This leaves me in this run with only 97347 lines that produce the following image:

You probably need to download and compare them in an appropriate image viewer to spot most differences.

## and start over again

Now I have a lot of lines that I can paint again to have a total of 235929 again. Not much to say, so here is the image:

## short analysis

The whole procedure seems to work like a blurring filter that is sensitive to local contrast and object sizes. But it is also interesting to see where the lines are painted, so the program records these too (For each line, the pixel color will be made one step whiter, at the end the contrast is maximized). Here are the corresponding ones to the three colored above.

## animations

And since we all love animations, here are some animated gifs of the whole process for the smaller golden gate image. Note that there is significant dithering due to gif format (and since creators of true color animation file formats and browser manufacturers are in war over their egos, there is no standard format for true color animations, otherwise I could have added an .mng or similar).

## Some more

As requested, here are some results of the other images (again you might need to open them in a new tab to not have them downscaled)

## Future thoughts

Playing around with the code can give some intresting variations.

* Chose the color of the lines by random instead of being based on the average. You might need more than two cycles.
* The code in the pastebin also contains some idea of a genetic algorithm, but the image is probably already so good that it would take too many generations, and this code is also too slow to fit into the "one hour" rule.
* Do another round of erase/repaint, or even two...
* Change the limit of where lines can be erased (e.g. "must make the image at lest N better")

## The code

These are just the two main useful functions, the whole code doesn't fit in here and can be found at http://ideone.com/Z2P6Ls

The `bmp` classes `raw` and `raw_line` function do access pixels and lines respectively in an object that can be written to bmp format (It was just some hack lying around and I thought that makes this somewhat independent from any library).

The input file format is PPM

```
std::pair<bmp,std::vector<line>>  paint_useful( const bmp& orig, bmp& clone, std::vector<line>& retlines, bmp& layer, const std::string& outprefix, size_t x, size_t y )
{
        const size_t pixels = (x*y);
        const size_t lines = 0.3*pixels;
//      const size_t lines = 10000;

//      const size_t start_accurate_color = lines/4;

        std::random_device rnd;

        std::uniform_int_distribution<size_t> distx(0,x-1);
        std::uniform_int_distribution<size_t> disty(0,y-1);
        std::uniform_int_distribution<size_t> col(-15,15);
        std::uniform_int_distribution<size_t> acol(0,255);

        const ssize_t m = 1*1;
        const ssize_t M = 50*50;

        retlines.reserve( lines );

        for (size_t i = retlines.size(); i < lines; ++i)
        {
                size_t x0;
                size_t x1;

                size_t y0;
                size_t y1;

                size_t dist = 0;
                do
                {
                        x0 = distx(rnd);
                        x1 = distx(rnd);

                        y0 = disty(rnd);
                        y1 = disty(rnd);

                        dist = distance(x0,x1,y0,y1);
                }
                while( dist > M || dist < m );

                std::vector<std::pair<int32_t,int32_t>> points = clone.raw_line_pixels(x0,y0,x1,y1);

                ssize_t r = 0;
                ssize_t g = 0;
                ssize_t b = 0;

                for (size_t i = 0; i < points.size(); ++i)
                {
                        r += orig.raw(points[i].first,points[i].second).r;
                        g += orig.raw(points[i].first,points[i].second).g;
                        b += orig.raw(points[i].first,points[i].second).b;
                }

                r += col(rnd);
                g += col(rnd);
                b += col(rnd);

                r /= points.size();
                g /= points.size();
                b /= points.size();

                r %= 255;
                g %= 255;
                b %= 255;

                r = std::max(ssize_t(0),r);
                g = std::max(ssize_t(0),g);
                b = std::max(ssize_t(0),b);

//              r = acol(rnd);
//              g = acol(rnd);
//              b = acol(rnd);

//              if( i > start_accurate_color )
                {
                        ssize_t dp = 0; // accumulated distance of new color to original
                        ssize_t dn = 0; // accumulated distance of current reproduced to original
                        for (size_t i = 0; i < points.size(); ++i)
                        {
                                dp += rgb_distance(
                                                                                orig.raw(points[i].first,points[i].second).r,r,
                                                                                orig.raw(points[i].first,points[i].second).g,g,
                                                                                orig.raw(points[i].first,points[i].second).b,b
                                                                        );

                                dn += rgb_distance(
                                                                                clone.raw(points[i].first,points[i].second).r,orig.raw(points[i].first,points[i].second).r,
                                                                                clone.raw(points[i].first,points[i].second).g,orig.raw(points[i].first,points[i].second).g,
                                                                                clone.raw(points[i].first,points[i].second).b,orig.raw(points[i].first,points[i].second).b
                                                                        );

                        }

                        if( dp > dn ) // the distance to original is bigger, use the new one
                        {
                                --i;
                                continue;
                        }
                        // also abandon if already too bad
//                      if( dp > 100000 )
//                      {
//                              --i;
//                              continue;
//                      }
                }

                layer.raw_line_add(x0,y0,x1,y1,{1u,1u,1u});
                clone.raw_line(x0,y0,x1,y1,{(uint32_t)r,(uint32_t)g,(uint32_t)b});
                retlines.push_back({ (int)x0,(int)y0,(int)x1,(int)y1,(int)r,(int)g,(int)b});

                static time_t last = 0;
                time_t now = time(0);
                if( i % (lines/100) == 0 )
                {
                        std::ostringstream fn;
                        fn << outprefix + "perc_" << std::setw(3) << std::setfill('0') << (i/(lines/100)) << ".bmp";
                        clone.write(fn.str());
                        bmp lc(layer);
                        lc.max_contrast_all();
                        lc.write(outprefix + "layer_" + fn.str());
                }

                if( (now-last) > 10 )
                {
                        last = now;
                        static int st = 0;
                        std::ostringstream fn;
                        fn << outprefix + "inter_" << std::setw(8) << std::setfill('0') << i << ".bmp";
                        clone.write(fn.str());

                        ++st;
                }
        }
        clone.write(outprefix + "clone.bmp");
        return { clone, retlines };
}

void erase_bad( std::vector<line>& lines, const bmp& orig )
{
        ssize_t current_score = evaluate(lines,orig);

        std::vector<line> newlines(lines);

        uint32_t deactivated = 0;
        std::cout << "current_score = " << current_score << "\n";
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                newlines[i].active = false;
                ssize_t score = evaluate(newlines,orig);
                if( score > current_score )
                {
                        newlines[i].active = true;
                }
                else
                {
                        current_score = score;
                        ++deactivated;
                }
                if( i % 1000 == 0 )
                {
                        std::ostringstream fn;
                        fn << "erase_" << std::setw(6) << std::setfill('0') << i << ".bmp";
                        bmp tmp(orig);
                        paint(newlines,tmp);
                        tmp.write(fn.str());
                        paint_layers(newlines,tmp);
                        tmp.max_contrast_all();
                        tmp.write("layers_" + fn.str());
                        std::cout << "\r i = " << i << std::flush;
                }
        }
        std::cout << "\n";
        std::cout << "current_score = " << current_score << "\n";
        std::cout << "deactivated = " << deactivated << "\n";

        bmp tmp(orig);

        paint(newlines,tmp);
        tmp.write("newlines.bmp");
        lines.clear();
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                if( newlines[i].is_active() )
                {
                        lines.push_back(newlines[i]);
                }
        }
}

```
> 21 votes

# Answer
## Java - random lines

A very basic solution that draws random lines and compute for them the source picture average color. The background color is set to the source average color.

**L = 5000, m = 10, M = 50**

**L = 10000, m = 10, M = 50**

**EDIT**

I've added a genetic algorithm that handles a population of lines. At each generation, we keep only the 50% best lines, drop the others and generate randomly new ones. The criteria for keeping the lines are:

* their distance to the source picture colors is small
* the number of intersections with other lines (the smaller the better)
* their length (the longer the better)
* their angle with the nearest neighbour (the smaller the better)

To my great disappointment, the algorithm does not really seems to improve the picture quality :-( just the lines are getting more parallel.

**First generation (5000 lines)**

**Tenth generation (5000 lines)**

**Playing with parameters**

```
package line;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.imageio.ImageIO;

import snake.Image;

public class Lines {

    private final static int NB_LINES = 5000;
    private final static int MIN_LENGTH = 10;
    private final static int MAX_LENGTH = 50;

    public static void main(String[] args) throws IOException {
        BufferedImage src = ImageIO.read(Image.class.getClassLoader().getResourceAsStream("joconde.png"));
        BufferedImage dest = new BufferedImage(src.getWidth(), src.getHeight(), BufferedImage.TYPE_INT_RGB);

        int [] bgColor = {0, 0, 0};
        int avgRed = 0, avgGreen = 0, avgBlue = 0, count = 0;
        for (int y = 0; y < src.getHeight(); y++) {
            for (int x = 0; x < src.getWidth(); x++) {
                int colsrc = src.getRGB(x, y);
                avgRed += colsrc & 255;
                avgGreen += (colsrc >> 8) & 255;
                avgBlue += (colsrc >> 16) & 255;
                count++;
            }
        }

        bgColor[0] = avgBlue/count; bgColor[1] = avgGreen/count; bgColor[2] = avgRed/count;
        for (int y = 0; y < src.getHeight(); y++) {
            for (int x = 0; x < src.getWidth(); x++) {
                dest.getRaster().setPixel(x, y, bgColor);
            }
        }
        List<List<Point>> lines = new ArrayList<List<Point>>();
        Random rand = new Random();
        for (int i = 0; i < NB_LINES; i++) {
            int length = rand.nextInt(MAX_LENGTH - MIN_LENGTH) + MIN_LENGTH;
            double ang = rand.nextDouble() * Math.PI;
            int lx = (int)(Math.cos(ang) * length); // can be negative or positive
            int ly = (int)(Math.sin(ang) * length); // positive only
            int sx = rand.nextInt(dest.getWidth() -1 - Math.abs(lx));
            int sy = rand.nextInt(dest.getHeight() - 1- Math.abs(ly));
            List<Point> line;
            if (lx > 0) {
                line = line(sx, sy, sx+lx, sy+ly);
            } else {
                line = line(sx+Math.abs(lx), sy, sx, sy+ly);
            }
            lines.add(line);
        }

        // render the picture
        int [] color = {0, 0, 0};
        for (List<Point> line : lines) {

            avgRed = 0; avgGreen = 0; avgBlue = 0;
            count = 0;
            for (Point p : line) {
                int colsrc = src.getRGB(p.x, p.y);
                avgRed += colsrc & 255;
                avgGreen += (colsrc >> 8) & 255;
                avgBlue += (colsrc >> 16) & 255;
                count++;
            }
            avgRed /= count; avgGreen /= count; avgBlue /= count;
            color[0] = avgBlue; color[1] = avgGreen; color[2] = avgRed;
            for (Point p : line) {
                dest.getRaster().setPixel(p.x, p.y, color);
            }

        }
        ImageIO.write(dest, "png", new File("a0.png"));

    }

    private static List<Point> line(int x0, int y0, int x1, int y1) {
        List<Point> points = new ArrayList<Point>();
        int deltax = x1 - x0;
        int deltay = y1 - y0;
        int tmp;
        double error = 0;
        double deltaerr = 0;
        if (Math.abs(deltax) >= Math.abs(deltay)) {
            if (x0 > x1) { // swap the 2 points
                tmp = x0; x0 = x1; x1 = tmp;
                tmp = y0; y0 = y1; y1 = tmp;
                deltax = - deltax; deltay = -deltay;
            }
            deltaerr = Math.abs (((double)deltay) / deltax);
            int y = y0;
            for (int x = x0; x <= x1; x++) {
                points.add(new Point(x, y));
                error += deltaerr;
                if (error >= 0.5) {
                    if (y0 < y1) y++; else y--;
                    error -= 1.0;
                }
            }
        } else {
            if (y0 > y1) { // swap the 2 points
                tmp = x0; x0 = x1; x1 = tmp;
                tmp = y0; y0 = y1; y1 = tmp;
                deltax = - deltax; deltay = -deltay;
            }
            deltaerr = Math.abs (((double)deltax) / deltay);   // Assume deltay != 0 (line is not horizontal),
            int x = x0;
            for (int y = y0; y <= y1; y++) {
                points.add(new Point(x, y));
                error += deltaerr;
                if (error >= 0.5) {
                    if (x0 < x1) x++; else x--;
                    error -= 1.0;
                }
            }
        }
        return points;
    }
}

```
> 17 votes

# Answer
# C - straight lines

A basic approach in C that operates on ppm files. The algorithm tries to place vertical lines with optimal line length to fill all pixels. The background color and the line colors are calculated as an average value of the original image (the median of each color channel):

```
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define SIGN(x) ((x > 0) ? 1 : (x < 0) ? -1 : 0)
#define MIN(x, y) ((x > y) ? y : x)
#define MAX(x, y) ((x > y) ? x : y)

typedef struct {
    size_t width;
    size_t height;

    unsigned char *r;
    unsigned char *g;
    unsigned char *b;
} image;

typedef struct {
    unsigned char r;
    unsigned char g;
    unsigned char b;
} color;

void init_image(image *data, size_t width, size_t height) {
    data->width = width;
    data->height = height;
    data->r = malloc(sizeof(data->r) * data->width * data->height);
    data->g = malloc(sizeof(data->g) * data->width * data->height);
    data->b = malloc(sizeof(data->b) * data->width * data->height);
}

#define BUFFER_LEN 1024
int load_image(const char *filename, image* data) {
    FILE *f = fopen(filename, "r");
    char buffer[BUFFER_LEN];          /* read buffer */
    size_t max_value;
    size_t i;
    fgets(buffer, BUFFER_LEN, f);
    if (strncmp(buffer, "P3", 2) != 0) {
        printf("File begins with %s instead of P3\n", buffer);
        return 0;
    }

    fscanf(f, "%u", &data->width);
    fscanf(f, "%u", &data->height);
    fscanf(f, "%u", &max_value);
    assert(max_value==255);

    init_image(data, data->width, data->height);

    for (i = 0; i < data->width * data->height; i++) {
        fscanf(f, "%hhu", &(data->r[i]));
        fscanf(f, "%hhu", &(data->g[i]));
        fscanf(f, "%hhu", &(data->b[i]));
    }
    fclose(f);

    printf("Read %zux%zu pixels from %s.\n", data->width, data->height, filename);
}

int write_image(const char *filename, image *data) {
    FILE *f = fopen(filename, "w");
    size_t i;
    fprintf(f, "P3\n%zu %zu\n255\n", data->width, data->height);
    for (i = 0; i < data->width * data->height; i++) {
        fprintf(f, "%hhu %hhu %hhu ", data->r[i], data->g[i], data->b[i]);
    }
    fclose(f);
}

unsigned char average(unsigned char *data, size_t data_len) {
    size_t i;
    size_t j;
    size_t hist[256];

    for (i = 0; i < 256; i++) hist[i] = 0;
    for (i = 0; i < data_len; i++) hist[data[i]]++;
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist[i];
        if (j >= data_len / 2) return i;
    }
    return 255;
}

void set_pixel(image *data, size_t x, size_t y, unsigned char r, unsigned char g, unsigned char b) {
    data->r[x + data->width * y] = r;
    data->g[x + data->width * y] = g;
    data->b[x + data->width * y] = b;
}

color get_pixel(image *data, size_t x, size_t y) {
    color ret;
    ret.r = data->r[x + data->width * y];
    ret.g = data->g[x + data->width * y];
    ret.b = data->b[x + data->width * y];
    return ret;
}

void fill(image *data, unsigned char r, unsigned char g, unsigned char b) {
    size_t i;
    for (i = 0; i < data->width * data->height; i++) {
        data->r[i] = r;
        data->g[i] = g;
        data->b[i] = b;
    }
}

void line(image *data, size_t x1, size_t y1, size_t x2, size_t y2, unsigned char r, unsigned char g, unsigned char b) {
    size_t x, y, t, pdx, pdy, ddx, ddy, es, el;
    int dx, dy, incx, incy, err;

    dx=x2-x1;
    dy=y2-y1;
    incx=SIGN(dx);
    incy=SIGN(dy);
    if(dx<0) dx=-dx;
    if(dy<0) dy=-dy;
    if (dx>dy) {
        pdx=incx;
        pdy=0;
        ddx=incx;
        ddy=incy;
        es=dy;
        el=dx;
    } else {
        pdx=0;
        pdy=incy;
        ddx=incx;
        ddy=incy;
        es=dx;
        el=dy;
    }
    x=x1;
    y=y1;
    err=el/2;
    set_pixel(data, x, y, r, g, b);

    for(t=0; t<el; t++) {
        err -= es;
        if(err<0) {
            err+=el;
            x+=ddx;
            y+=ddy;
        } else {
            x+=pdx;
            y+=pdy;
        }
        set_pixel(data, x, y, r, g, b);
    }
}

color average_line(image *data, size_t x1, size_t y1, size_t x2, size_t y2) {
    size_t x, y, t, pdx, pdy, ddx, ddy, es, el;
    int dx, dy, incx, incy, err;
    color ret;
    color px;
    size_t i;
    size_t j;
    size_t hist_r[256];
    size_t hist_g[256];
    size_t hist_b[256];
    size_t data_len = 0;

    for (i = 0; i < 256; i++) {
        hist_r[i] = 0;
        hist_g[i] = 0;
        hist_b[i] = 0;
    }

    dx=x2-x1;
    dy=y2-y1;
    incx=SIGN(dx);
    incy=SIGN(dy);
    if(dx<0) dx=-dx;
    if(dy<0) dy=-dy;
    if (dx>dy) {
        pdx=incx;
        pdy=0;
        ddx=incx;
        ddy=incy;
        es=dy;
        el=dx;
    } else {
        pdx=0;
        pdy=incy;
        ddx=incx;
        ddy=incy;
        es=dx;
        el=dy;
    }
    x=x1;
    y=y1;
    err=el/2;
    px = get_pixel(data, x, y);
    hist_r[px.r]++;
    hist_g[px.g]++;
    hist_b[px.b]++;
    data_len++;

    for(t=0; t<el; t++) {
        err -= es;
        if(err<0) {
            err+=el;
            x+=ddx;
            y+=ddy;
        } else {
            x+=pdx;
            y+=pdy;
        }
        px = get_pixel(data, x, y);
        hist_r[px.r]++;
        hist_g[px.g]++;
        hist_b[px.b]++;
        data_len++;
    }

    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist_r[i];
        if (j >= data_len / 2) {
            ret.r = i;
            break;
        }
    }
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist_g[i];
        if (j >= data_len / 2) {
            ret.g = i;
            break;
        }
    }
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist_b[i];
        if (j >= data_len / 2) {
            ret.b = i;
            break;
        }
    }
    return ret;
}

void lines(image *source, image *dest, size_t L, float m, float M) {
    size_t i, j;
    float dx;
    float mx, my;
    float mm = MAX(MIN(source->width * source->height / L, M), m);
    unsigned char av_r = average(source->r, source->width * source->height);
    unsigned char av_g = average(source->g, source->width * source->height);
    unsigned char av_b = average(source->b, source->width * source->height);
    fill(dest, av_r, av_g, av_b);
    dx = (float)source->width / L;
    mx = 0;
    my = mm / 2;
    for (i = 0; i < L; i++) {
        color avg;
        mx += dx;
        my += (source->height - mm) / 8;
        if (my + mm / 2 > source->height) {
            my = mm / 2 + ((size_t)(my + mm / 2) % (size_t)(source->height - mm));
        }
        avg = average_line(source, mx, my - mm / 2, mx, my + mm / 2);
        line(dest, mx, my - mm / 2, mx, my + mm / 2, avg.r, avg.g, avg.b);
    }
}

int main(int argc, char *argv[]) {
    image source;
    image dest;
    size_t L;
    float m;
    float M;

    load_image(argv[1], &source);
    L = atol(argv[2]);
    m = atof(argv[3]);
    M = atof(argv[4]);

    init_image(&dest, source.width, source.height);
    lines(&source, &dest, L, m, M);

    write_image(argv[5], &dest);
}

```

## L = 5000, m = 10, M = 50

## L = 5000, m = 10, M = 50

## L = 100000, m = 10, M = 50
> 9 votes

# Answer
## Python 3 -based off of "somewhat random lines and then some", plus sobel edge detection.

the code can theoretically run forever (so I can run it overnight for fun), but it records its progress, so all images are taken from the 1-10 min mark.

It first reads the image, and then uses sobel edge detection to find the angle of all the edges, to make sure that the lines do not trespass on another color. Once a line of the random length within (lengthmin,lengthmax) is set, it then tests to see if it contributes to the overall image. While smaller lines are better, I set the line length from 10-50.

```
from random import randint, uniform
import json
from PIL import Image, ImageDraw, ImageFilter
import math
k=(-1,0,1,-2,0,2,-1,0,1)
k1=(-1,-2,-1,0,0,0,1,2,1)
population=[]
lengthmin=10
lengthmax=50
number_lines=10**8
im=Image.open('0.png')
[x1,y1]=im.size
dx=0
class drawer():
    def __init__(self,genome,score,filename):
        self.genome=genome
        self.score=score
        self.filename=filename
    def initpoint(self,g1):
        g2=self.genome
        im=Image.open('0.png')
        im1=im.filter(ImageFilter.Kernel((3,3),k,1,128))
        im2=im.filter(ImageFilter.Kernel((3,3),k1,1,128))
        im1=im1.filter(ImageFilter.GaussianBlur(radius=4))
        im2=im2.filter(ImageFilter.GaussianBlur(radius=4))
        for x in range(0,number_lines):
            if(x%10**4==0):
                print(x*100/number_lines)
                self.save()
                g1.save('1.png')
            (x,y)=(randint(0,x1-1),randint(0,y1-1))
            w=im1.getpixel((x,y))[0]-128
            z=im2.getpixel((x,y))[0]-128
            w=int(w)
            z=int(z)
            W=(w**2+z**2)**0.5
            if(W!=0):
                w=(w/W)*randint(lengthmin,lengthmax)
                z=(z/W)*randint(lengthmin,lengthmax)
                (w,z)=(z,w)
                (a,b)=(x+w,y+z)
                a=int(a)
                b=int(b)
                x=int(x)
                y=int(y)
                if(a>=x1):
                    a=x1-1
                if(b>=y1):
                    b=y1-1
                if(a<0):
                    a=0
                if(b<0):
                    b=0
                if(x>=x1):
                    x=x1-1
                if(y>=y1):
                    y=y1-1
                if(x<0):
                    x=0
                if(y<0):
                    y=0
                C=[0,0,0]
                D=0
                E=0
                F=0
                G=0
                W=((x-a)**2+(y-b)**2)**0.5
                if(W!=0):
                    for Z in range(0,int(W)):
                        w=(Z/W)
                        (c,d)=((w*x+(1-w)*a),(w*y+(1-w)*b))
                        c=int(c)
                        d=int(d)
                        C[0]+=im.getpixel((c,d))[0]
                        C[1]+=im.getpixel((c,d))[1]
                        C[2]+=im.getpixel((c,d))[2]
                    C[0]/=W
                    C[1]/=W
                    C[2]/=W
                    C[0]=int(C[0])
                    C[1]=int(C[1])
                    C[2]=int(C[2])
                    for Z in range(0,int(W)):
                        w=(Z/W)
                        (c,d)=((w*x+(1-w)*a),(w*y+(1-w)*b))
                        c=int(c)
                        d=int(d)
                        E=0
                        D=0
                        D+=(g1.getpixel((c,d))[0]-im.getpixel((c,d))[0])**2
                        D+=(g1.getpixel((c,d))[1]-im.getpixel((c,d))[1])**2
                        D+=(g1.getpixel((c,d))[2]-im.getpixel((c,d))[2])**2
                        F+=D**0.5
                        E+=(im.getpixel((c,d))[0]-C[0])**2
                        E+=(im.getpixel((c,d))[1]-C[1])**2
                        E+=(im.getpixel((c,d))[2]-C[2])**2
                        G+=E**0.5
                    #print((G/W,F/W))
                    if(G<F):
                        for Z in range(0,int(W)):
                            w=(Z/W)
                            (c,d)=((w*x+(1-w)*a),(w*y+(1-w)*b))
                            c=int(c)
                            d=int(d)
                            g1.putpixel((c,d),(int(C[0]),int(C[1]),int(C[2])))
                        g2.append((x,y,a,b,int(C[0]%256),int(C[1]%256),int(C[2]%256)))
        return(g1)
    def import_file(self):
        with open(self.filename, 'r') as infile:
            self.genome=json.loads(infile.read())
        print(len(self.genome))
    def save(self):
        with open(self.filename, 'w') as outfile:
            data = json.dumps(self.genome)
            outfile.write(data)
population.append(drawer([],0,'0.txt'))
G=0
g1=Image.new('RGB',(x1,y1),'black')
g1=population[0].initpoint(g1)
g1.save('1.png')

```
> 6 votes

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


title: Look and say sequence

text:
# Question
Title: Look and say sequence
The look and say sequence is a basic form of run length encoding.

The sequence starts with the number 1 and each additional number encodes the number of digits that are repeated before each digit sequence. For example, "1" becomes "11", because there is one "1". Then "11" becomes "21", and so on.

The first few numbers are 1, 11, 21, 1211, 111221, 312211 and 13112221.

Write a program to output the first 20 numbers.

The catch is you **may not use any number** in your program, including other bases than base 10. You can only use letters and symbols. Also, the program can't directly contain the numbers (or fetch them from a web server, or from a file); it must actually compute them.

I will accept the answer which works and is the shortest; in case of a tie, vote counts will decide, and in case of a tie there, the winner will be chosen randomly.

# Answer
> 9 votes
### Golfscript, 44 43 40 41 38 37 36 chars

Since the criterion now requires golfing, here's the golfed version:

```
!:^;n).+{[^\{^$^$={;\)}^if\}*].n@}*;

```

The original, ungolfed, version actually dealt with strings rather than abusing Golfscript's formatting conventions for dumping the stack to stdout at program termination:

```
# Assumes nothing passed to stdin, so input length is zero
,):$''+
{
    .puts
    # Convert to an array of [count char count char ...]
    [$\{.@.@={;\)\}{\$\}if}*]
    # Convert to an array of [[count char] [count char] ...]
    $)/
    # Form the next string
    ''\{(@\+\+}/
}
# Nineteen times. There are a *lot* of ways of generating the number nineteen
# but I like this one
$).?.)*(*

```

# Answer
> 6 votes
# Perl (60 characters)

```
perl -e'print,s#(.)\g{$y}*#$&=~y///c.$^N#egfor(++$y.$/)x($^F.$|)'

```

Look ma, no numbers. The algorithm is rather similar to the "chinese perl goth's" solution above with a few golf tweaks:

* `$^F.$|` == "20" == 20 in numeric context
* $^N == last bracket matched
* for loop over `(1)x20` is much shorter than trying to use a range
* `++$y == 1` and use it both as a backreference `\g{$y}` & to seed the generator
* length is more cheaply spelt `y///c`

I spent a bunch of time trying alternative short ways to write `length()` before settling on the usual `y///c` \- numbers of the form x = nnnn...n (where there are k digits n) have a lovely property that k = x mod 9 / n. So you could write it as `$& % 9 / $^N`. But now you have to get rid of the 9.

(Fun to golf again - thanks to MtvViewMark for roping me back)

# Answer
> 6 votes
# Mathematica ~~88~~ 82

```
t=Flatten;x=b/b;
g@n_:=Grid@NestList[t@Map[Reverse,t[Tally/@Split@#,x],x]&,{x},n-x]

```

---

**Usage**

```
g[9]

```

# Answer
> 5 votes
## PHP 67 bytes

```
<?for(;~Î/$s=preg_filter(~Ð×ÑÖ£ÎÕÐš,~£ÏÚÆÐ£ÎßÑß£Î,$s)?:~Îõ;)echo$s;

```

The above may be copied directly, and saved in an ansi format.

Alternatively, it may generated with the following script, and then piped to a file:

```
<?="<?for(;~\xce/\$s=preg_filter(~\xd0\xd7\xd1\xd6\xa3\xce\xd5\xd0\x9a,~\xa3\xcf\xda\xc6\xd0\xa3\xce\xdf\xd1\xdf\xa3\xce,\$s)?:~\xce\xf5;)echo\$s;";

```

The script terminates when the current value of the series, `$s`, becomes larger than the largest representable floating point number, approximately `1e308`. This quite coincidentally occurs just after the 20th value.

Sample usage:

```
$ php look-and-say.php
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211

```

# Answer
> 3 votes
# Javascript, 105

```
z=c=+[];r=x="";s=i=-~c+r;for(e=-~s+r+c;e--;){alert(s);c=z;for(x=r;y=s[c++];++i)y!=s[c]&&(x+=i+y,i=z);s=x}

```

Output (change `alert` to `console.log`)

```
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211

```

# Answer
> 2 votes
## Perl, 94 bytes

```
$_=$w=cos"a";for$a($w..(ord('<')-ord('('))){print"$_ ";eval"s/(\\d)\\$w*/length(\$&).\$$w/ge"}

```

# Answer
> 2 votes
## Haskell, 116

```
import List
l=length
f=[l[f]]:map(((\x->[l x,head x])=<<).group)f
main=mapM putStrLn$map(show=<<)$take(l['a'..'t'])f

```

The trick of using `['a'..'t']` to extract the right number of elements was lifted from MtnViewMark's solution. Obviously superior to my original choice of `"a really long string"`.

# Answer
> 2 votes
## Perl (73)

Named capture buffers rock.

```
perl -le '$_++;$c=a;$r="(?<f>.)\\$_*";print,s/$r/length($&).$+{f}/eg while$c++ne u'

```

A bit of explanation:

`$_++;` incrementing `$_` which is undefined at the start, to make it contain `1`.

`$c=a;` \- abusing perl's barewords in a horrible way to make `$c` contain `'a'`.

`$r="(?<f>.)\\$_*"` \- constructing a regular expression matching repeated characters. normally i'd write it as `(.)\1*` but I can't use digits, so i've declared a capture buffer with the name of `f`. this also could be written as `(?<f>.)\k<f>*` but it'll make the regex one char longer, so I've used `\\$_` which evaluates to `\1`.

`print,s/$r/length($&).$+{f}/eg while$c++ne u`

Ungolfed:

`while($c++ne u) {` \- taking advantage of the fact that it's possible to increment strings in perl - incrementing a scalar containing `'a'` will make it contain `'b'`, and so on - so the loop will go from `'a'` to `'u'`

`print;` \- print `$_`

`s/$r/length($&).$+{f}/eg` \- operating on `$_`, replace whatever is matched by the previously constructed regular expression (repeated characters) by its length, followed by first char of it. `$&` means the whole match, `$+{f}` means "a named capture buffer with a name f".

`}`

# Answer
> 2 votes
**C: 213 characters**

```
main(){char*a,*b=calloc(' ',' '),*c=calloc(' ',' '),*d,*e,*f;*b='Q'-' ';for(a="                    ";*a;++a){printf("%s\n",b);e=f=b;d=c;while(*e){while(*f==*e){++f;}d+=sprintf(d,"%d%c",f-e,*e);e=f;}e=b;b=c;c=e;}}

```

# Answer
> 2 votes
**Mathematica 62**

```
x=a/a;Grid@NestList[Join@@({Length@#,#〚x〛}&/@Split@#)&,{x},#]&

```

# Answer
> 1 votes
## Ruby 1.9, 119 chars

```
num = "#{?b.ord-?a.ord}"
one = num.to_i
limit = ?U.ord-?A.ord
loop {
    puts num
    num = num.gsub(/(?<digit>.)\k<digit>*/) { $&.size.to_s + $+ }
    break if (limit -= one) == one - one
}

```

A golfed version:

```
k="#{?b.ord-?a.ord}"
j=k.to_i
i=?U.ord-?A.ord
loop{puts k
k=k.gsub(/(?<d>.)\k<d>*/){$&.size.to_s+$+}
(i-=j)==j-j&&exit}

```

# Answer
> 1 votes
# C++

### By *Chuck Morris*

```
/*  This implements the power of
**    C H U C K  M O R R I S .
*/

#include <iostream>
#include <vector>

/*
**  Deep within the murks
**  Of an assembly programmer's heart
**  Lies an ancient hatred
**  Of recursion
**
**  Yet a true C++ programmer
**  Can appreciate the beauty
**  And elegance
**  Which the following manifests
*/
std::string stringpp(std::string sz, size_t last_digit=(size_t)'\0')
{
    std::string bak = sz;

    if(last_digit < sz.length())
    {
        char nextnum = sz[sz.length() - (size_t)'\x01' - last_digit];
        ++nextnum;

        if(nextnum < ':')
        {
            sz = bak.substr((size_t)'\0', bak.length() - (size_t)'\x01' - last_digit);
            sz += nextnum;
            if(last_digit)
                sz += bak.substr(bak.length() - last_digit, last_digit);
        }
        else
        {
            nextnum = '0';

            sz = bak.substr((size_t)'\0', bak.length() - (size_t)'\x01' - last_digit);
            sz += nextnum;
            if(last_digit)
                sz += bak.substr(bak.length() - last_digit, last_digit);

            sz = stringpp(sz, last_digit + (size_t)'\x01');
        }
    }
    else
    {
        sz = "1";
        sz += bak;
    }

    return(sz);
}

class ChuckMorris
{
private:
    std::string sz;
public:
    ChuckMorris() { sz = "1"; }
    void next();
    std::string get();
};

void ChuckMorris::next()
{
    std::string num;

    std::string bak = sz;
    sz = "";

    for(size_t i = (size_t)'\0'; i < bak.length();)
    {
        num = "0";
        size_t i2 = i;
        for(; (i2 < bak.length()) && (bak.at(i) == bak.at(i2)); ++i2)
            num = stringpp(num);
        sz += num;
        sz += bak.substr(i, 1);
        i = i2;
    }
}

std::string ChuckMorris::get()
{
    return(sz);
}

int main(int argc, char* argv[])
{
    ChuckMorris chucky;

    // std::cout << stringpp("999").c_str() << std::endl;

    for(char chucks = '\0'; chucks < '\x14';)
    {
        std::cout << chucky.get().c_str();
        chucky.next();
        ++chucks;
        if(chucks != '\x14')
            std::cout << ", ";
    }

    std::cout << std::endl;

    return(0);
}

/*  And some elvish for elegance:
**  A Elbereth Gilthoniel
**  silivren penna míriel
**  o menel aglar elenath!
**  Na-chaered palan-díriel
**  o galadhremmin ennorath,
**  Fanuilos, le linnathon
**  nef aear, sí nef aearon!
*/

```

This is an elegance only *Chuck Morris* himself can achieve with C++ code. He coded it (for free) in less than zero seconds, while sleeping.

It may not be as "elegant" as Golfscript/others, but it does everything... in a ***statically typed language!***

# Answer
> 1 votes
## Python 2.x

```
from itertools import groupby
s=`len(' ')`
for x in'                    ':
    print s
    s=''.join(i+`len(list(j))` for i,j in groupby(s))

```

and a version without the hacky strings

```
from math import *
from itertools import groupby
s=`int(log(e))`
for x in s*int(e**pi-e):
    print s
    s=''.join(i+`len(list(j))` for i,j in groupby(s))

```

note that e\**pi-pi is very close to 20 (19.99909997918947) but slightly smaller, so it's no good to use int with

# Answer
> 1 votes
## Haskell, 109 characters

```
import List
q=show.length
l=q" ":map((>>=(\a->q a++[head a])).group)l
main=mapM_(putStrLn.snd)$zip['a'..'t']l

```

Not a digit in sight, not even as a character in a string! Prints the first 20 numbers, one per line.

---

* Edit (118 -\> 109) used suggestion of `length` to generate the initial `1`, then factored out `show.length`

# Answer
> 1 votes
## Lua, 138 bytes

```
p=#' 'm=p c=''..p f=#'    'for k=p,f*f+f do n=''o=#n while o<#c do q=o+p l=c:sub(q,q)i,o=c:find(l.."+",q)n=n..o-i+p..l end c=n print(n)end

```

# Answer
> 1 votes
## JavaScript (102 characters)

Requires support for arrow functions. This will work unmodified in JavaScript Shell or otherwise when `print` is changed to `alert`.

```
for(j=k=l=-~'',j=++j+j,j*=++j;j--;)print(k=(''+k).replace(RegExp('(.)\\'+l+'*','g'),(a,b)=>a.length+b))

```

# Answer
> 1 votes
# Clojure, 251 chars

```
(def z`~(count ""))(def t(read-string(str z "xa")))(println(take(+ t t)(iterate(fn[x](#(reduce(fn[a b](+ b(* a t)))%)(mapcat(juxt count first)(partition-by identity(#(loop[u %,d()](if(zero? u)(seq d)(recur(quot u t)(cons(mod u t)d))))x)))))(inc z))))

```

Heres the ungolfed version. This sure was fun to figure out.

```
(def z `~(count ""))
(def ten (read-string (str z "xa")))
(defn num->digits [n]
  " Takes a number and returns a sequence containing
    its digits in ascending order
    e.g., 123 -> (1 2 3)"
 (loop [num n, digits ()] (if (zero? num) (seq digits) (recur (quot num ten) (cons (mod num ten) digits)))))
(defn digits->num [seq]
  " Takes a sequence of digits and returns the number
    they represent
    e.g., (1 2 3) -> 123 "
  (reduce (fn [a b](+ b (* a ten))) seq))

(defn look-seq [n]
  " Returns a sequence containing the look-say representation for n"
    (digits->num (mapcat (juxt count first) (partition-by identity (num->digits n)))))

(defn look-n-say
  " Returns a lazy sequence representing
    Conway's look-and-say sequence starting at n"
  ([] (look-n-say (inc z)))
  ([n] (iterate look-seq n)))

(println (take (+ ten ten) (look-n-say)))

```

# Answer
> 1 votes
# Clojure, 172 characters

```
(let[o(*)t(+ o o)f(+ t t)p partial c comp](dorun(take(+(Math/pow t f)f)(map(c println(p apply str))(iterate(c(p mapcat(juxt count first))(p partition-by identity))[o])))))

```

This is using the trick that the multiplicative identity is 1; therefore, Clojure has `(*)` evaluate to 1. I let this be `o` (one), and then let `t` (two) be `(+ o o)`, and let `f` (four) be `(+ t t)`. I also alias `partial` and `comp` to one-letter names (hurrah for first class functions!).

I then use math to find the number 20, so I can use it for taking this number of elements from an infinite sequence of look-and-say strings: 2^4 + 4 = 20.

The actual algorithm for finding look-and-say numbers, unobfuscated, looks like this:

```
(iterate (comp (partial mapcat (juxt count first)) (partial partition-by identity)) [1])

```

The above produces the infinite sequence of sequences of digits corresponding to look-and-say numbers.

# Answer
> 1 votes
# K, 62

```
{,/,'[;?:'f]@$#:'f:(&~~':x)_x}\["J"$h,$"i"$"\t";,h:*$"i"$"\r"]

```

# Answer
> 1 votes
## Ruby 1.9+, 76 characters

Like @daniero, I shamelessly stole @Lowjacker's regex.

```
s=$-W.to_s
"\cT".ord.times{puts s;s.gsub!(/(?<d>.)\k<d>*/){$&.size.to_s+$+}}

```

# Answer
> 1 votes
## CJam, 11 bytes

```
X{NX$se`}J*

```

Test it here.

This answer does not compete as CJam is much younger than this challenge (and `e`` is a fairly recent feature). However, I thought the solution is really neat so I wanted to add it for completeness.

### Explanation

```
X     e# Push 1 as the start of the sequence.
{     e# Repeat this block 19 times...
  N   e#   Push a linefeed as a separator.
  X$  e#   Copy the last value (which will be either a number or a nested array of numbers.
  s   e#   Convert it to a string, which will flatten the value if it's an array.
  e`  e#   Run-length encode the string.
}J*

```

This works because `e`` happens to use the required order of run-length and value, and because the look-and-say sequence will never contain any "digits" greater than 3, so that we don't lose any information by simply flattening the RLE-result into a single string.

# Answer
> 0 votes
# Ruby 2.0, 82 characters.

I took Lowjacker's regex and put it into this one-liner.

```
(?(.ord>>p(n=??.size)).times{puts n=n.to_s.gsub(/(?<d>.)\k<d>*/){$&.size.to_s+$+}}

```

# Answer
> 0 votes
## C# - 209

```
using System.Linq;class P{static void Main(){int i='a',N='b'-i,O=i-i,
x=O;var C=N+"";while(i++<'u'){System.Console.WriteLine(C);var n="";(C+
" ").Aggregate((c,d)=>{x++;if(d!=c){n+=x+""+c;x=O;}return d;});C=n;}}}

```

Exploits the fact that char is implicitly convertible to int, and since a string is an IEnumerable collection of chars, I used the LINQ Aggregate() method to do the work.

```
using System.Linq;
class P
{
    static void Main()
    {
        int i = 'a',     // start loop counter at the int value for 'a'
            N = 'b' - i, // N is now literally 1 ('b' - 'a')
            O = i - i,   // O is now literally 0 (1 - 1)
            x = O;       // number counter
        var C = N + "";  // C is the current string. start with "1".

        while (i++ < 'u') // if 'a' is 1, 'u' is 20
        {
            // print the current string
            System.Console.WriteLine(C);

            var n = ""; // this will be our next string

            // aggregate the current string
            (C + " ").Aggregate((c, d) =>
            {
                // increment the number counter
                x++;
                if (d != c)
                {
                    // when a different number is found, update the next string
                    n += x + "" + c;
                    // reset the count
                    x = O;
                }
                // the current number is passed back in as the aggregate (c)
                return d;
            });

            // move next to current
            C = n;
        }
    }
}

```

# Answer
> 0 votes
# Haskell, 103/114 characters

this solution prints the numbers inside lists, like so:

```
[1]
[1,1]
[2,1]
...

```

code:

```
import Data.List
l=length
main=mapM print$take(l['a'..'t'])$iterate((>>= \v->[l v,head v]).group)[l[l]]

```

this version prints them outside lists, but has more characters:

```
import Data.List
l=length
main=mapM(print.(>>=show))$take(l['a'..'t'])$iterate((>>= \v->[l v,head v]).group)[l[l]]

```

output:

```
"1"
"11"
"21"
...

```

# Answer
> 0 votes
# K, 46 bytes

```
(-/_ic'"TA"){,/+(#:;*:)@'\:_[&o,~=':x]x}\,o:#`

```

A very old question, but I thought I could improve on the existing K solution.

The phrase `-/_ic'"ta"` generates the constant 19- the difference between the ASCII characters "t" and "a". I also need the constant 1, so I use the length of the empty symbol. Without these contortions, the program would look like the following:

```
19{,/+(#:;*:)@'\:_[&1,~=':x]x}\,1

```

Only 33 bytes, and pretty easy to follow by K standards. For each term of the sequence, find the starting index of each run of identical values (`&1,~=':x`), slice the sequence into runs (`_`), and apply count (`#:`) and first (`*:`) to each element of the resulting sequence. (`@'\:`) Take the transpose (`+`) of that result to reshape it into a list of (count,item) tuples and then finally raze (`,/`) into a flat list.

In action:

```
  (-/_ic'"TA"){,/+(#:;*:)@'\:_[&o,~=':x]x}\,o:#`
(,1
 1 1
 2 1
 1 2 1 1
 1 1 1 2 2 1
 3 1 2 2 1 1
 1 3 1 1 2 2 2 1
 1 1 1 3 2 1 3 2 1 1
 3 1 1 3 1 2 1 1 1 3 1 2 2 1
 1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
 1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
 ...

```

---
Tags: code-golf, restricted-source, sequence
---


title: Priming a Pristine World

text:
# Question
Title: Priming a Pristine World
*Heavily inspired by Programming a Pristine World. Also closely related to this challenge.*

---

Let's define a *pristine prime* as a number which is itself prime, but will no longer be prime if you remove any contiguous substring of N base 10 digits, where `0 < N < digits in number`.

For example, 409 is a pristine prime because 409 itself is prime, but all numbers resulting from removing a substring of 1 digit are not prime:

```
40
49
09 = 9

```

and all numbers resulting from removing substrings of length 2 are not prime:

```
4
9

```

On the other hand, the prime number 439 is not pristine. Removing the different substrings results in:

```
43
49
39
4
9

```

While 49, 39, 4, and 9 are all non-prime, 43 *is* prime; thus, 439 is not pristine.

2, 3, 5, and 7 are trivially pristine, since they cannot have any substrings removed.

## Challenge

Your challenge is to create a program or function that takes in a positive integer N and outputs the Nth pristine prime. The code should finish in under 1 minute on any modern PC for any input up to 50.

**The shortest code in bytes wins.**

As a reference, here are the first 20 pristine primes:

```
N    Pristine prime
1    2
2    3
3    5
4    7
5    11
6    19
7    41
8    61
9    89
10   409
11   449
12   499
13   821
14   881
15   991
16   6299
17   6469
18   6869
19   6899
20   6949

```

Here is a full list of pristine primes up to 1e7, or N = 376.

Finally, here are two related OEIS entries:

* A033274: very similar, but generated by keeping substrings instead of removing them.
* A071062: oddly similar, but generated in a much different manner.

# Answer
> 6 votes
# Pyth, 29 bytes

```
e.f>}ZPZsmq1lPs.D`Z}Fd.CU`Z2Q

```

Golfing, explanation, etc. to follow.

# Answer
> 4 votes
## CJam, 51 bytes

```
1ri{{)_mp1$s_,)2m*{:>},\f{\~2$<@@>+0e|imp}1b!&!}g}*

```

Just a first pass, this can probably be improved a lot.

Test it here.

# Answer
> 3 votes
# Japt, 61 bytes

```
$while(V<U)T$°,W=Ts ,Tj «Wl o d@1o1-X+Wl)dZ{WjYZ n j} } ©V°;T

```

Try it online!

It's a shame I haven't implemented loops in Japt yet, otherwise this would be a good bit shorter. Still golfing...

---
Tags: code-golf, sequence, number-theory, primes
---


title: Parse a two-dimensional syntax

text:
# Question
Title: Parse a two-dimensional syntax
## Background

Alice and Bob are creating a golfing language to win every single PPCG challenge. Alice wants to make a two-dimensional language, like \>\<\>, but Bob prefers a prefix-infix syntax like in J. As a compromise, they decide to create a two-dimensional prefix-infix language. The parser is a pain to write, and they need your help!

## Syntax specification

In Alice's and Bob's language, there are *variables*, which are represented by lowercase ASCII letters `a-z`, and *functions*, which are represented by uppercase ASCII letters `A-Z`. A function can be invoked with one or two arguments. A *program* is a rectangular grid of letters `a-zA-Z` and spaces, and the top left corner must not contain a space. This is an example of a valid program:

```
F Gy
H
R x

```

When the program is parsed, it's transformed into an expression of a C-style language (C, Java, Python...) containing single-letter variables and function calls in the format `<func>(<arg>)` or `<func>(<arg1>,<arg2>)`. For example, the above program results in this expression:

```
F(H(R(x)),G(x,y))

```

The details of the parsing process are as follows:

* The spaces are just filler, so they are not parsed.
* Every variable `a-z` is always parsed as itself.
* Every function `A-Z` is parsed as a function call. Its arguments are the closest expressions below it and to its right in the grid, in this order. If only one of these is present, it's given as the sole argument. You can assume that all functions have at least one argument in the grid.

In the above example, the variables `x` and `y` are parsed as themselves. The function `R` has nothing below it and `x` to its right, so it's parsed as the one-argument invocation `R(x)`. Similarly, `H` is parsed as `H(R(x))`, since it has `R` below it. The function `G` has `x` below it and `y` to its right, so it's parsed as `G(x,y)`, and similarly for `F`. The expression parsed at the top left corner is the result of the parsing process.

## Input and output

Your input is a non-empty rectangular array of characters. It will always be a valid program in Alice's and Bob's language, but it may contain expressions that are not used in the output. Your output shall be the parsed expression resulting from the above process.

## Rules and scoring

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

## Test cases

These are given in the format `grid <newline> expression`, with hyphens `---` between the cases. The SE format leaves some lines blank, but they should be filled with spaces.

```
x
x
---
x y
z
x
---
Fx
F(x)
---
Fx
y
F(y,x)
---
ABu
A(B(u))
---
G
H
k
G(H(k))
---
ABCA
x xs
 DFk
A(x,B(D(F(k)),C(x,A(s))))
---
A  B

C  D x
A(C(D(x)),B(D(x)))
---
RT Hq
I xR k
R(I(x),T(H(R(k),q)))
---
A A  A a
 S A  b
B  C   Dx
d X  u f
A(B(d,C(D(f,x))),A(X(u),A(u,a)))

```

# Answer
## CJam, ~~67~~ ~~62~~ ~~60~~ ~~58~~ ~~57~~ 54 bytes

*Thanks to Dennis for saving 4 bytes.*

```
{:Gsc_32&{"()"[GGz2{1m<_{S#}#>W<\}*z]{},{J}%',**+}|}:J

```

This defines a named block (function) `J` and leaves it on the stack. The function itself expects an array of strings on the stack, which represents the input grid, and leaves the desired string in its stead.

Test it here.

I've been meaning to tackle this one since it was posted, but apparently I needed a bounty and an overly long Pyth solution to motivate myself sufficiently.

### Explanation

The solution is of course recursive and gradually builds up the string.

```
{
  :G       e#  Store the current grid in G.
  sc       e#  Convert the grid to a string, flattening it, then to a character, which
           e#  discards everything but the first character. This is a golfed 0=0=.
           e#  This character will either be an upper-case letter (function) or a lower-
           e#  case letter (variable).
  _32&     e#  Make a copy of the character and take bitwise AND with 32. This gives a
           e#  NULL character for functions and a space for variables.
  {        e#  If the result is falsy... (i.e. NULL, i.e. we have a function)
    "()"   e#   Push parentheses for later use.
    [      e#   Remember the current stack depth.
    GGz    e#   Push an array which contains the grid and its transpose.
    2{     e#   Run this block twice... (it will be applied once to each grid)
      1m<  e#    Rotate the rows. This has two effects: a) It removes the first row
           e#    from the front such that we can go looking for the next non-space
           e#    character down the first column from the start. b) It places a row
           e#    at the end which we know doesn't start with a space, which acts as
           e#    a guard in case there are no further letters below the current one.
      _    e#    Duplicate this grid.
      {    e#    Find the first index where this block yields something truthy...
        S# e#     Find the index of the first space in the current row. If the row
           e#     starts with a space, this is 0, i.e. falsy and the search continues.
           e#     If there is a space in any later position, that will be positive and
           e#     truthy, so this index gets returned. If there is no space at all,
           e#     the result is -1 which is also truthy and ends the search.
      }#
      >    e#     Discard all lines up to (but not including) the found index.
      W<   e#     Discard the guard row at the end.
      \    e#     Swap the grids so that the next pass processes the other grid.
    }*
    z      e#    Transpose the second grid back to its original orientation.
    ]      e#    Wrap both processed grids in an array.
    {},    e#    Remove a grid if it's empty.
    {J}/   e#    For each remaining grid, call J recursively.
    ',*    e#    Join the grids with commas if there are still two of them.
    *      e#    Wrap this string in the parentheses below on the stack.
    +      e#    Prepend the function name.
  }|
}:J

```
> 8 votes

# Answer
# Python 2, ~~227~~ ~~223~~ ~~192~~ ~~182~~ ~~179~~ 177 bytes

```
def r(i,y=0,x=0):
 c=i[y][x];z=[]
 for t in"pq":
    p=q=0
    try:
     while" "==i[y+p][x+q]or 1>p+q:exec t+"+=1"
     z+=[r(i,y+p,x+q)]
    except:1
 return c+"(%s)"%",".join(z)*c.isupper()

```

(The four spaces are in fact tabs)

Takes a 2d list of characters as the first argument to r.
> 5 votes

# Answer
## Haskell, ~~124~~ ~~122~~ ~~120~~ 119 bytes

```
r@((c:_):_)#g|c>'_'=[c]|c<'!'=g%r|1<2=c:'(':(tail%r)!(map tail%r)++")"
_#_=""
g%r=g r#g
a!b=a++[','|a>"",b>""]++b
(#id)

```

Usage example: `(#id) ["RT Hq ","I xR k"]` -\> `"R(I(x),T(H(R(k),q)))"`.

How it works: besides the input grid `r`, the function `#` takes another function `g` as an argument that is applied on `r` whenever the top left character is a space. If it's a lowercase char instead, return it. Otherwise it must be an uppercase character and `#` is called recursively, once with `tail` to go down and once with `map tail` to go right. `!` joins the results from the recursive calls with a `,`, if needed. All starts with the input grid and the identity function.
> 5 votes

# Answer
# Pyth, 97 bytes

```
D:TkdI}p@@QTkGR)=Z0p\(V2JK0W|q\ @@Q=b+TJ=H+kK!+JK=J+NJ=K+!NK)I!|gblQgHl@Q0p*Z\,:bH+=Z1d))p\);:000

```

My god that took a long time to make (about 5/6 hours?). Pyth really wasn't designed for this...

Try it here.

Attempt at explanation as well as python equivalent

```
Q = literal_eval(input())

def at_slice(T,k,d):
  if Pprint(Q[T][k]) in "abcdefghijklmnopqrstuvwxyz": return
  Z = 0
  Pprint("(")
  for N in range(2):
    J=K=0
    while " "==Q[assign('b',T+J)][assign('H',k+K)] or not J+K:
      J+=N
      K+=not N
    if not (b>=len(Q) or H>=len(Q[0])):
      Pprint(Z*",")
      at_slice(b,H,assign('Z',1)+d)
   Pprint(")")
at_slice(0,0,0)

```

Where the functions `Pprint` and `assign` return what they're given.
> 5 votes

# Answer
# Python 3, 187 bytes

Still looking for ways to golf this down, but I'm just pleased I managed to turn it into a one-liner.

```
lambda g,r=0,c=0:g[r][c]+'(%s)'%','.join([p(g,R,c)for R in range(r+1,len(g))if c<len(g[R])and' '!=g[R][c]][:1]+[p(g,r,C)for C in range(c+1,len(g[r]))if' '!=g[r][C]][:1])*g[r][c].isupper()

```
> 0 votes

---
Tags: code-golf, grid, parsing
---


title: Thanksgiving Turkey

text:
# Question
Title: Thanksgiving Turkey
(Hopefully it's still Thanksgiving for you)

You got a turkey for your thanksgiving dinner but you don't know how to evenly distribute it. The problem is, some people eat more than others, so you need to find a solution

## Input

There will be two inputs. The first will be an ascii art of various people.

```
     o
 o  \|/
\|/  |
 |   |
/ \ / \

```

### ascii-art specifications

Each person takes up a width of 3 columns. Each person is separated by a single column of spaces. The very top of each person is an `o`. Below the `o`, offset by `1` and `-1` in the x, are `\` and `/`, respectively. From the `o` to the second to last row in the input are `|`, the amount of these per person is their "height". The only data you will need to extract from each person is their "height".

---

There will always be at least one person. Each person always has at *least* 2-height. The max height your program should handle is at *least* a height of 64.

If you would like the input padded with spaces to form a rectangle, please specify this in your answer.

---

The second input is the turkey. The turkey is not really a turkey, more of `NxM` dimensions of a turkey. If the second input is `3x2`, then the turkey has dimensions of 3\*2, with a total area of 6.

## Output

The output may be a list or your language's closest alternative (e.g. Array). You may also output a string, with the values separated by spaces.

The values for each person should be output in the order in which they were input.

## Challenge

Your goal is to divide the area of the turkey among the people.

An example scenario:

Assume they are two people, with heights of `3` and `6`, respectively. If there is a turkey of `5x3`. The total area of the turkey that will need to be distributed is `15`.

Now how would you distribute it among everyone? Here's how:

```
                    the_persons_height
TurkeyForAPerson = -------------------- * turkey_area
                    sum_of_all_heights

```

This means, for the first person with a height of `3`, they will get `3/9*15` turkey, or `5`, the second person with a height of `6` they will get `6/9*15` or `10` turkey.

## Output

Output must solely consist of digits, and `.`, unless you choose to go for the bonus. In that case, it may only consist of digits, spaces (), and a slash (`/`).

## Full example

Input:

```
6x5
     o
     |
 o  \|/
\|/  |
 |   |
 |   |
/ \ / \

```

Output:

```
11.25 18.75

```

## Bonuses

**-20% Bonus:** You output a fraction (must be simplified), it does **not** matter whether it is a mixed or improper fraction.

## Scoring

This is so shortest code in bytes wins!

# Answer
> 3 votes
# Pyth, 23 bytes

```
mc*vXzG\*dsN=N-/R\|C.z0

```

This doesn't work in the online version, because it uses `eval` to determine the size of the turkey.

### Explanation:

```
mc*vXzG\*dsN=N-/R\|C.z0   implicit: z = first input line
                    .z    read all other lines
                   C      transpose them
               /R\|       count the "|"s in each column
              -       0   remove 0s in this list (columns with no "|"s)
            =N            assign the resulting list to N
m                         map each value d in N to:
    XzG\*                    replace every letter in z with a "*"
   v                         evaluate the result (does the multiplication)
  *      d                   multiply with d
 c        sN                 divide by sum(N)

```

# Answer
> 4 votes
# LabVIEW, 67 Bytes

Im counting after what i proposed in the meta post so its not fixed but yeah here goes.

input padded with spaces is expected.

Im counting heads and get the size of people from the line where the heads are at.

# Answer
> 3 votes
# Japt, ~~49~~ 46 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
W=UqR y f@Y%4¥1 £Xq'| l -1)£Vq'x r@X*Y,1 *X/Wx

```

Outputs as an array. (Note that you will need to wrap each of the two inputs in quotation marks.)

### How it works

```
            // Implicit: U = stick-figures, V = turkey size
W=UqR y     // Assign variable W to: split U at newlines, transpose rows with columns,
f@Y%4==1    // take each stick-figure body,
m@Xq'| l -1 // and count the number of "|"s.
)m@Vq'x     // Now map each item X in W to: V split at "x",
r@X*Y,1     // reduced by multiplication, starting at 1,
*X/Wx       // multiplied by X and divided by the total of W.
            // Implicit: output last expression

```

# Answer
> 3 votes
# MATLAB 109\*80% = 87.2 bytes

```
function o=f(t,p);p=char(strsplit(p,'\n'));a=sum(p(:,2:4:end)=='|');o=rats(prod(sscanf(t,'%dx%d'))*a/sum(a));

```

So this is a MATLAB function which takes two inputs, the first is a string for the turkey size (e.g. `'8x4'`, and the second is the string containing the people. It returns a string containing improper fractions for each person.

This could have been a lot smaller, but the new lines got tricky. MATLAB could easily convert a string with `;` as a separator for each line, but trying to use a newline proved difficult, costing 25 characters:

```
p=char(strsplit(p,'\n')); % Converts the input person string to a 2D array

```

Getting the size of the people is actually quite easy:

```
a=sum(p(:,2:4:end)=='|');

```

This takes every fourth column starting from the second (which will be all the columns where bodies of people will be), then converts that to an array containing 1's where there are body bits and 0's where there aren't. Finally it sums column-wise which results in the array `a` which is a 1D array containing the size of each person.

```
prod(sscanf(t,'%dx%d'))*a/sum(a)

```

Next we extract the size of the turkey from the input string which is in the form `%dx%d`, i.e. one number then 'x' then another number. The resulting array of two numbers are multiplied together to get turkey area.

This is multiplied by each of the peoples height, and also divided by the total height of all people to get the portion of turkey for each person as a decimal number.

```
rats(...)

```

The final step to qualify the bonus - this bit makes the code 6 characters longer, but the bonus knocks off ~22 so its worth it. `rats()` is a nice function which converts a decimal number to a simplified improper fraction (accurate to 13 d.p.). Feeding it an array of decimal numbers (i.e. the amount for each person) will return a single string containing fractions for each person in turn separated by spaces.

Granted the output of `rats()` adds more than one space, but the question doesn't say it can't - just says the string must contain only digits, ' ' and '/'.

This is the output from the example (quote marks added by me to prevent spaces being removed, not in actual output):

```
'     45/4          75/4     '

```

---

Example usage:

```
f('6x5',['     o ' 10 '     | ' 10 ' o  \|/' 10 '\|/  | ' 10 ' |   | ' 10 ' |   | ' 10 '/ \ / \'])

```

output:

```
'     45/4          75/4     '

```

---

It also works (albeit with warnings) on the online **Octave** interpreter. You can try it here. The link is to a workspace with the `f` function defined in a file already. So you should be able to just enter the example usage above at the prompt.

# Answer
> 2 votes
# Pyth - 25 bytes

Can definitely golf a couple bytes off of it. Pretty straightforward approach.

```
KfT/R\|C.z*R*FsMcz\xcRsKK

```

Try it online here.

# Answer
> 2 votes
## Haskell 119 bytes

```
import Data.List
g x=sum[1|y<-x,y>'{']
s#p|(h,_:t)<-span(<'x')s=[g x*read h*read t/g p|x<-transpose$lines p,any(>'{')x]

```

Usage example: `"6x5" # " o \n | \n o \\|/\n\\|/ | \n | | \n | | \n/ \\ / \\\n"` -\> `[11.25,18.75]`.

# Answer
> 2 votes
# JavaScript (ES6), 131 bytes

```
(t,p)=>eval(`h=[];for(s=0;m=r.exec(p);s++)h[i=m.index%l/4|0]=~~h[i]+1;h.map(v=>v/s*${t.replace("x","*")})`,l=p.search`
`+1,r=/\|/g)

```

Returns an array of portions.

## Explanation

```
(t,p)=>                      // t = turkey equation, p = ASCII art of people
  eval(`                     // use eval to enable for loop without {} or return
    h=[];                    // h = array of each person's height
    for(s=0;m=r.exec(p);s++) // for each match of "|", s = sum of all heights
      h[i=m.index%l/4|0]=    // i = person index of this match
        ~~h[i]+1;            // increment person's height (~~ casts undefined to 0)
    h.map(v=>v/s*            // divide each height by the sum and multiply by turkey area
      ${t.replace("x","*")}  // since this is inside an eval just convert t to an equation
    )`,                      // implicit: return array of each person's portion

    // These are executed BEFORE the eval (escaping characters would mean more bytes)
    l=p.search`
`+1,                         // l = line length
    r=/\|/g                  // r = regex to match height markers
  )

```

## Test

```
var solution = (t,p)=>eval(`h=[];for(s=0;m=r.exec(p);s++)h[i=m.index%l/4|0]=~~h[i]+1;h.map(v=>v/s*${t.replace("x","*")})`,l=p.search`
`+1,r=/\|/g)
```

```
Turkey = <input type="text" id="turkey" value="6x5" /><br />
<textarea id="people" rows="8" cols="40">     o
     |
 o  \|/
\|/  |
 |   |
 |   |
/ \ / \</textarea><br />
<button onclick="result.textContent=solution(turkey.value,people.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 1 votes
## Python 99 bytes

```
lambda a,b: [`(''.join(i)).count('|')*1.0/a.count('|')*eval(b)` for i in zip(*a.split('\n'))[1::4]]

```

Input:`' o \n | \n o \\|/\n\\|/ | \n | | \n | | \n/ \\ / \\','6*5'`

Output: `['11.25', '18.75']`

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


title: Point in convex hull (2D)

text:
# Question
Title: Point in convex hull (2D)
### Background

The convex hull of a finite number of points is the smallest convex polygon that contains all of the points, either as vertices or on the interior. For more information, see this question on PGM which defines it very well.

### Input

`N+1` 2-D coordinates (`N >= 3`) passed through `STDIN` (with other usual golf inputs allowed too) in the following format (the number of decimals can vary but you can assume it remains "reasonable" and each number can be represented as a float):

```
0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

```

### Output

A truthy value printed to `STDOUT` (or equivalent) if the first point in the list (`(0.00;0.00000)` in the example above) is in the convex hull of the other N points, and a falsy value otherwise.

This is , so the shortest solution in bytes wins.

* *Border cases*: you can return any value (but don't crash) if the point lies on the border of the convex hull (i.e. on a side or on a vertex on the outer frontier of the hull), since it is a zero probability event (under any reasonable probability).
* *Forbidden*: anything (language, operator, data structure, built-in or package) that exists **only** to solve geometric problems (e.g. Mathematica's ConvexHull). General purpose mathematical tools (vectors, matrices, complex numbers etc.) are allowed.

### Tests

# Answer
# J, ~~40~~ ~~39~~ 34 bytes

```
3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

```

An anonymous dyadic function, taking a point, *p*, as one of its arguments, and a list of points, *P*, as the other argument (it doesn't matter which argument is which), and returning `0` or `1`, if *p* is outside or inside the convex hull of *P*, respectively. The point *p*, and the points in *P*, are taken as complex numbers.

## Example

```
  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

```

---

or...

# Python 2, function, ~~121~~ ~~103~~, full program, ~~162~~

# Python 3, 149 bytes

```
import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

```

Takes input, in the same format as the original post, through STDIN, and prints a boolean value indicating whether p is in the convex hull of P

---

## Explanation

The program tests whether the difference between the maximum and minimum (signed) angles between any point *r* in *P*, *p*, and a fixed arbitrary point *q* in *P* (we just use the first point in *P*), is less than 180°. In other words, it tests whether all the points in *P* are contained in an angle of 180° or less, around *p*. *p* is in the convex hull of *P* if and only if this condition is false.

---

At the cost of a few more bytes, we can use a similar method that doesn't require us to explicitly calculate angles: Note that the above condition is equivalent to saying that *p* is outside the convex hull of *P* if and only if there exists a line *l* through *p*, such that all the points in *P* are on the same side of *l*. If such a line exists, then there's also such a line that is incident to one (or more) of the points in *P* (we can rotate *l* until it touches one of the points in *P*.)

To (tentatively) find this line, we start by letting *l* be the line through *p* and the first point in *P*. We then iterate over the rest of the points in *P*; if one of the points is to the left of *l* (we assume some directionality throughout, left or right doesn't really matter,) we replace *l* with the line passing through *p* and that point, and continue. After we iterated over all of *P*, if (and only if) *p* is outside the convex hull, then all the points in *P* should be to the right of (or on) *l*. We check that using a second pass over the points in *P*.

**Python 2, 172 bytes**

```
import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)

```

Alternatively, to do the same thing in a single pass, let *to-the-left-of* be a realtion between any two points, *q* and *r*, in *P*, such that *q* is to the left of *r* if *q* is to the left of the line passing through *p* and *r*. Note that to-the-left-of is an order relation on *P* if and only if all the points in *P* are on the same side of some line passing through *p*, that is, if *p* is outside the convex hull of *P*. The procedure described above finds the minimum point in *P* w.r.t. this order, i.e., the "leftmost" point in *P*. Instead of performing two passes, we can find the maximum (i.e., the "rightmost" point), as well as the minimum, points in *P* w.r.t. the same order in a single pass, and verify that the minimum is to the left of the maximum, i.e., effectively, that to-the-left-of is transitive.

This would work well if *p* is outside the convex hull of *P*, in which case to-the-left-of is actually an order relation, but may break when *p* is inside the convex hull (for example, try to figure out what will happen if we ran this algorithm where the points in *P* are the vertices of a regular pentagon, running counter-clockwise, and *p* is its center.) To accommodate, we slightly alter the algorithm: We select a point *q* in *P*, and bisect *P* along the line passing through *p* and *q* (i.e., we partition *P* around *q* w.r.t. to-the-left-of.) We now have a "left part" and a "right part" of *P*, each contained in a halfplane, so that to-the-left-of is an order relation on each; we find the minimum of the left part, and the maximum of the right part, and compare them as described above. Of course, we don't have to physically bisect *P*, we can simply classify each point in *P* as we look for the minimum and maximum, in a single pass.

**Python 2, 194 bytes**

```
import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)

```
> 9 votes

# Answer
# Octave, 82 72 bytes

```
d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

```

The idea is to check whether the linear program min { c'x : Ax=b, e'x=1, x \>= 0 } has a solution, where e is a vector of all ones, columns of A are the coordinates of the point cloud, and b is the test point, and c is arbitrary. In other words, we try to represent b as a convex combination of columns of A.

To run the script, use `octave -f script.m <input.dat`
> 4 votes

# Answer
## R, 207 bytes

```
d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

```

The script takes its inputs from STDIN, e.g. `Rscript script.R < inputFile`.

It generates all triangles from the `N` last points (the last line, `apply(combn(...` ) and checks whether the first point is in the triangle using the `t` function.

`t` uses the area method to decide if `U` is in `ABC`: (writing `(ABC)` for the area of `ABC`) `U` is in `ABC` iff `(ABC) == (ABU) + (ACU) + (BCU)`. Also, areas are calculated using the determinant formula (see here for a nice demo from Wolfram).

I suspect this solution is more prone to numerical errors than my other one, but it works on my test cases.
> 2 votes

# Answer
## R, 282 bytes

```
d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

```

The script takes its inputs from STDIN, e.g. `Rscript script.R < inputFile`.

It generates all triangles from the `N` last points (the last line, `apply(combn(...` ) and checks whether the first point is in the triangle using the `t` function.

`t` uses the barycentric method to decide if `U` is in `ABC`: (writing `XY` for the `X` to `Y` vector) since `(AB,AC)` is a basis for the plane (except for the degenerate cases where A,B,C are aligned), `AU` can be written as `AU = u.AB + v.AC` and `U` is in the triangle iff `u > 0 && v > 0 && u+v < 1`. See for instance here for a more detailed explanation and a nice interactive chart. *NB: to save a few chars and avoid DIV0 errors, we only compute a shortcut to `u` and `v` and a modified test (`min(u*k,v*k,k-u-v)>0`).*

The only mathematical operators used are `+`, `-`, `*`, `min()>0`.
> 0 votes

---
Tags: code-golf, math, geometry
---


# Question
Title: Most logical rectangle formula from numbers
### Introduction

The task is simple. When given a number, output the most logical rectangle. To explain what a logical rectangle is, I provided some examples:

Input: `24`.

All possible rectangles have the form `A x B`, (`A` and `B` are both positive integers). So, all possible rectangles for `24` are:

* `1 x 24`
* `2 x 12`
* `4 x 6`

From this list, the most logical rectangle has the lowest `A + B`:

* `1 + 24 = 25`
* `2 + 12 = 14`
* `4 + 6 = 10`

You can see that `4 x 6` is the most logical rectangle, so we will output `4 x 6` (or `6 x 4`).

### The rules

* Given an integer from `1` to `99999`, output the most logical rectangle.
* You may write a function or a program.
* The spaces in the output are not required.
* This is , so the submission with the least amount of bytes wins!

### Test cases

```
Input >   Output

1     >   1 x 1
4     >   2 x 2
8     >   4 x 2 (or 2 x 4)
15    >   5 x 3 (or 3 x 5)
47    >   1 x 47 (or 47 x 1)
5040  >   72 x 70 (or 70 x 72)
40320 >   210 x 192 (or 192 x 210)

```

# Answer
## CJam, 26 bytes

```
ri_mQ),W%{1$\%!}=:X/" x "X

```

or

```
ri_mQ{)1$\%!},W=):X/" x "X

```

Test it here.

Finds the largest divisor less than or equal to the square root of the input as one of the two side lengths.
> 1 votes

# Answer
# Pyth, 18 bytes

```
jd[Kf!%QTs@Q2\x/QK

```

Try it online: Demonstration or Test Suite

Same idea as Martin's. Finds the first number \>= floor(sqrt(n)), that divides n.

### Explanation:

```
jd[Kf!%QTs@Q2\x/QK   implicit: Q = input number
          @Q2        sqrt(Q)
         s           floor, converts ^ to an integer
    f                find the first number T >= floor(sqrt(Q)), that satisfies:
     !%QT               Q mod T == 0
   K                 store this number in K
  [K         \x/QK   create the list [K, "x", Q/K]
jd                   join by spaces

```
> 1 votes

# Answer
## Java 8, 86 bytes

```
n->{for(int i=(int)Math.sqrt(n);;i--)if(n%i==0){System.out.print(i+"x"+n/i);return;}};

```

Lambda function, test with:

```
public class Rectangle {
    interface Test {
        void run(int v);
    }
    public static void main (String[] args){
        Test test = n->{for(int i=(int)Math.sqrt(n);;i--)if(n%i==0){System.out.print(i+"x"+n/i);return;}};

        int[] testCases = {1, 4, 8, 15, 47, 5040, 40320};
        for (int i : testCases) {
            test.run(i);
            System.out.println();
        }
    }
}

```

Finds the largest divisor less than or equal to the square root of the input. Same concept as the CJam and Pyth answers.
> 1 votes

---
Tags: code-golf, math, number, geometry
---


title: Rolling the Dice

text:
# Question
Title: Rolling the Dice
# Rolling the Dice

So, I was rolling dice a while ago and thought of a challenge.

Given the cube with a net taken from input and a list of moves, find the square on the bottom at the end.

I will use this image for the examples here.

### Input

You take in a string with a list of moves. The string contains only the capital ASCII letters N, S, W, and E. These correspond to rolling the cube one step into that direction.

In the picture, one N would make the bottom face a 6. In this image, North is away from the camera, South is towards, East is right, and West is left.

You also take in a string in the following format: 1P 2P 3P 4P 5P 6P, where each P is a position from N, S, W, E, T, and B. T & B are bottom and top.

The numbers are the face with that number, and the letter represents the position the face is in. In case it isn't clear, the net will always be ordered by the number, so 1P 2P 3P 4P 5P 6P, never 2B 1T 3N 4S 5W 6E.

The position in the image is 1S 2B 3E 4W 5T 6N.

### Output

Your program should output a number representing the bottom side.

### Test Cases

```
(nothing), 1S 2B 3E 4W 5T 6N -> 2
N, 1S 2B 3E 4W 5T 6N -> 6
NS, 1S 2B 3E 4W 5T 6N -> 2
NWS, 1S 2B 3E 4W 5T 6N -> 2
NWSNWS, 1S 2B 3E 4W 5T 6N -> 2
NWSS, 1S 2B 3E 4W 5T 6N -> 3
NNNNNN, 1S 2B 3E 4W 5T 6N -> 5
SNWEEWS, 1N 2T 3E 4W 5B 6S, 6
SNEEWS, 1N 2T 3W 4S 5B 6E, 4

```

### Other Rules

You may also assume the cube is on a infinite flat plane, probably with some sort of friction.

Standard loopholes disallowed, even though I can't find any.

For invalid input, your code may do anything except start the apocalypse.

Because this program should fit on my dice, it should be as small as possible. I count in bytes, with some exceptions for languages like Folders.

# Answer
> 8 votes
## CJam, ~~43~~ ~~40~~ ~~37~~ 34 bytes

*Thanks to Dennis for helping me save 6 bytes.*

```
lW%3/$1f=q{i8%"ÉĔɠƂ!"=i\m!=}/c

```

Test it here.

### Explanation

```
lW%    e# Read the first line and reverse it.
S/     e# Split it around spaces.
$      e# Sort it. This puts the faces in order [B E N S T W].
1f=    e# Select the second character from each face, which is the number.
q      e# Read the remainder of the input (the instructions).
{      e# For each instruction...
  i8%  e#   Convert the character (NWSE) to an integer and take modulo 8.
  "ÉĔɠƂ!"=i
       e#   Use that to (cyclically) index this string and convert *that* character
       e#   to an integer.
  \    e#   Swap with the list of faces.
  m!   e#   Generate all permutations of the faces.
  =    e#   Select the permutation corresponding to the above integer.
}/     e# At the end of the loop, the bottom face will be the first character.
c      e# Convert the string to a character, which discards everything but the bottom face.

```

As for how the mapping of instruction characters to permutations works, here is a handy table:

```
   i   8%  5%  ""=   i   [0 1 2 3 4 5]m!=

N  78   6   1   Ĕ   276  [2 1 4 0 3 5]
W  87   7   2   ɠ   608  [5 0 2 3 1 4]
S  83   3   3   Ƃ   386  [3 1 0 4 2 5]
E  69   5   0   É   201  [1 4 2 3 5 0]

```

I've included the `5%` column because that is what the cyclic indexing into the string does implicitly. For the four permutations we can see that each of them leaves two (opposite) sides untouched and cyclically permutes the other four.

# Answer
> 5 votes
## Perl, ~~166~~ ~~158~~ ~~154~~ ~~144~~ ~~139~~ ~~135~~ ~~134~~ ~~132~~ 116 bytes

*includes +1 for `-p`*

```
s/(\d)(.)/$h{$2}=$1/eg;$N='NTSB',$S='STNB',$E='ETWB',$W='WTEB';map{@h{@l}=@h{(@l=$$_=~/./g)[1..3,0]}}/\w/g;$_=$h{B}

```

## With comments:

```
                                    # example input: "NS, 1S 2B 3E 4W 5T 6N"
s/(\d)(.)/$h{$2}=$1/eg;             # construct %h ( S=>1, B=>2, E=>3, W=>4, B=>2, N=>6 )

                                    # = Transformations =
$N='NTSB',                          # N becomes T, T becomes S, S becomes B, B becomes N
$S='STNB',
$E='ETWB',
$W='WTEB';

map {                               # iterate the moves "NS"
    @h{ @l } =                      # LHS: bulk-assign new values; @l defined in RHS
      @h{                           # RHS: init @l, transform
          (@l=$$_=~/./g)            # get transform, put ('N','T','S','B') in @l for LHS
          [1..3,0]                  # construct a rotated slice for RHS
    }
} /\w/g;                            # match the movements in list context

$_=$h{B}                            # assign the bottom face to output.

```

---

Input file:
```
, 1S 2B 3E 4W 5T 6N
N, 1S 2B 3E 4W 5T 6N
NS, 1S 2B 3E 4W 5T 6N
NWS, 1S 2B 3E 4W 5T 6N
NWSNWS, 1S 2B 3E 4W 5T 6N
NWSS, 1S 2B 3E 4W 5T 6N
NNNNNN, 1S 2B 3E 4W 5T 6N
SNWEEWS, 1N 2T 3E 4W 5B 6S
SNEEWS, 1N 2T 3W 4S 5B 6E

```

Run with

```
perl -p dice.pl < input.txt

```

Output: `262223564`

---

* *update 158* Using `$N, $S, $E, $W` global variables instead of `%t = {N=>, S=>, E=>, $W=>}` saves 8 bytes.
* *update 154* Since the requirement is that the program output a number, not printing the newline `print "$h{B}\n"` saves 4 bytes: `print $h{B}`.
* *update 144* Save 10 bytes by doing

```
($s)=/^(\w+),/;            s/(\d)(.)/$h{$2}=$1/eg;

```

instead of

```
($s,@i)=split /,? |\n/;    %h=reverse map{split//}@i;

```
* *update 139* Move the regex for the command to the end to eliminate a variable, saving 6 bytes.
* *update 135* Save 4 bytes on `@l[0..3,0]` instead of `@l[1..3],$l[0]`.
* *update 134* Save 1 byte by using assignment `@l=split//,$$_` as value.
* *update 132* Save 2 bytes by doing `/^\w+/ && $&` instead of `/^(\w+)/ && $1`.
* *update 129* Save 3 bytes by using `-p` instead of `-n` and assigning $\_ for print.
* *update 116* Save 13 bytes by rewriting `split//, /^\w+/ && $&` into `/^\w+/g`.

# Answer
> 4 votes
# Python 2, 204 bytes

Thought it was time to respond to my own question.

```
def x(p,m):
    d={p[3*i-2]:i for i in range(1,7)}
    for j in m:n=2if j in'NE'else-2;x='BSTN'if j in'NS'else'BETW';d[x[0]],d[x[1]],d[x[2]],d[x[3]]=d[x[1+n]],d[x[(2+n)%4]],d[x[(3+n)%4]],d[x[0+n]]
    print d['B']

```

Not very short, but works.

Run as:

```
x('1B 2T 3N 4S 5W 6E','SNEEWS')
#Output: 4

```

**Edit**: Counted bytes wrong. Now longer. :(

---
Tags: code-golf, geometry, abstract-algebra
---


title: Can the Array be Unshuffled?

text:
# Question
Title: Can the Array be Unshuffled?
### Background

Very skilled card handlers are capable of a technique whereby they cut a deck perfectly in half, then perfectly interleave the cards. If they start with a sorted deck and perform this technique flawlessly 52 times in a row, the deck will be restored to sorted order. Your challenge is to take ~~a deck of cards~~ an integer array and determine whether it can be sorted using only Faro shuffles.

### Definition

Mathematically, a Faro shuffle is a permutation on 2 *n* elements (for any positive integer *n*) which takes the element in position *i* (1-indexed) to position 2 *i* (mod 2 *n*+1). We would also like to be able to handle odd-length lists, so in that case, just add one element to the end of the list (a Joker, if you have one handy) and Faro shuffle the new list as above, but ignore the added dummy element when checking the list's order.

### Goal

Write a program or function that takes a list of integers and returns or outputs a truthy if some number of Faro shuffles would cause that list to be sorted in nondescending order (even if that number is zero--small lists should give a truthy). Otherwise, return or output a falsy.

### Examples

```
[1,1,2,3,5,8,13,21]  => True
[5,1,8,1,13,2,21,3] => True
[9,36,5,34,2,10,1] => True
[1,0] => True
[0] => True
[] => True
[3,2,1] => True
[3,1,2] => False
[9,8,7,6,5,4,3,2,1,0] => True
[9,8,7,6,5,4,3,2,0,1] => False
[3,1,4,1,5,9,2,6,9] => False
[-1,-1,-1,-2] => True

```

## Scoring

This is so shortest source in bytes wins.

# Answer
> 3 votes
# MATL, 41 bytes

```
itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx

```

The output is `1` or `0`.

### Explanation

```
i              % get input array
tn2\           % is size odd?
?              % if that's the case
  YNh          % concat NaN at the end
]              % end if
tn             % get size of input array
t1+:           % vector 1:n+1, where n is input size, so loop will be entered even with []
"              % for loop
  x[]2e!PY)    % delete result from previous iteration and do the shuffling
  ttZN~)       % remove NaN, if there's any
  tS=A         % check if array is sorted
  t.           % copy the result. If true, break loop
]              % end for
wx             % remove unwanted intermediate result

```

### Example

```
>> matl itn2\?YNh]tnt1+:"x[]2e!PY)ttZN~)tS=At.]wx
> [1,1,2,3,5,8,13,21]
1

```

# Answer
> 3 votes
# Pyth - ~~26~~ ~~25~~ 24 bytes

Uses cumulative reduce to apply Faro shuffle multiple times and keep all the results. Then, it maps through it and checks if they are invariant under sorting, then uses sum to check is any are true. Returns a positive or zero.

```
smSI-db.usC_c2NQsC.tc2Qb

```

Test Suite.

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


title: The alphanumeric spiral

text:
# Question
Title: The alphanumeric spiral
The task is very simple, when given an input, output one of the following spirals:

`Input = 1` gives a spiral with the letter `A` beginning in the top left corner:

```
A B C D E F
T U V W X G
S 5 6 7 Y H
R 4 9 8 Z I
Q 3 2 1 0 J
P O N M L K

```

`Input = 2` gives a spiral with the letter `A` beginning in the top right corner:

```
P Q R S T A
O 3 4 5 U B
N 2 9 6 V C
M 1 8 7 W D
L 0 Z Y X E
K J I H G F

```

`Input = 3` gives a spiral with the letter `A` beginning in the bottom right corner:

```
K L M N O P
J 0 1 2 3 Q
I Z 8 9 4 R
H Y 7 6 5 S
G X W V U T
F E D C B A

```

`Input = 4` gives a spiral with the letter `A` beginning in the bottom left corner:

```
F G H I J K
E X Y Z 0 L
D W 7 8 1 M
C V 6 9 2 N
B U 5 4 3 O
A T S R Q P

```

As you can see, the spiral always goes *clockwise* and moves from the *outside* to the *inside*.

The rules are simple:

* You need to provide a full program using STDIN and STDOUT, or the nearest equivalent if not possible.
* Given an input (`1, 2, 3, 4`), output the related spiral.
* Trailing whitespaces are allowed
* Leading whitespaces are allowed when used *consistently*
* You need to use uppercase letter for the output, lowercase letters are not allowed.
* This is , so the program with the least amount of bytes wins!

# Answer
> 5 votes
## CJam, ~~45~~ ~~43~~ 42 bytes

```
'[,65>A,+W%(s{W%z_,@s/(@.+}A*ri{W%z}*Sf*N*

```

Test it here.

### Explanation

```
'[,65>  e# Push the upper-case alphabet.
A,+     e# Append the digits.
W%      e# Reverse everything.
(s      e# Pull off the 9 and turn it into a string.
{       e# Repeat this 10 times to roll the string up in a spiral...
  W%z   e#   Rotate the existing grid clockwise.
  _,    e#   Duplicate grid so far and get the number of rows.
  @s    e#   Pull up the list of characters and flatten it into one string.
  /     e#   Split the string into chunks of the size of the number of rows.
  (     e#   Pull off the first chunk.
  @.+   e#   Pull up the grid so far and prepend the chunk as a new column.
}A*     e# We now have the spiral as desired, with the A in the bottom left corner.
ri      e# Read input and convert to integer.
{       e# Repeat this code that often..
  W%z   e#   Rotate the spiral clockwise.
}*
Sf*     e# Join each line with spaces.
N*      e# Join the lines with linefeeds.

```

# Answer
> 10 votes
# Japt, 53 bytes ~~58 59 60~~

*Saved 5 bytes thanks to @ETHproductions*

```
"FGHIJK EXYZ0L DW781M CV692N BU543O ATSRQP"¸zU ®¬¸} ·

```

This uses the rotate command which I never thought would be so useful

## Explanation && Ungolfed

```
"FGHIJK EXYZ0L DW781M CV692N BU543O ATSRQP"qS zU m_q qS} qR

             // Implicit: U = input
"FGH...SRQP" // String, " " represent newlines
qS           // Split   " "
zU           // Rotate
m_           // Loop the lines
  q qS}      // Insert spaces
qR           // Join by newlines

```

Try it online

# Answer
> 3 votes
# Mathematica 156 bytes

Converts initial string of letters, `"ABCDEFTUVWXGS567YHR498ZIQ3210JPONMLK"`, into an array. `Nest` applies `f` to that array `n-1`times, where n is the input number. `f` works by `Transpose`-ing the array followed by `Reverse`applied to each row. `g` converts the final array into a string.

```
s=StringJoin;r=Riffle;f=Nest[Reverse/@Transpose@#&,Partition[Characters@"ABCDEFTUVWXGS567YHR498ZIQ3210JPONMLK",6],#-1]&;
g@n_:=s@r[s/@(r[#," "]&/@f[n]),"\n"]

```

---

**Example**

```
g[4]

```

---

If the output could be given as an array, the function `g` would be unnecessary.

```
f[4]

```

> {{"F", "G", "H", "I", "J", "K"}, {"E", "X", "Y", "Z", "0", "L"}, {"D", "W", "7", "8", "1", "M"}, {"C", "V", "6", "9", "2", "N"}, {"B", "U", "5", "4", "3", "O"}, {"A", "T", "S", "R", "Q", "P"}}

# Answer
> 3 votes
# MATLAB, ~~61~~ 89 bytes

```
b=[65:90 48:57];n=zeros(12,6);n(2:2:end)=rot90(b(37-spiral(6)),input('')-2);disp([n' ''])

```

I'll see if I can get it down a bit. Not sure though.

This creates an array of all letters from A to Z followed by 0 to 9, then takes a spiral and uses that to arrange the data in the correct order. The array is then rotated by the amount the user specifies and then printed out.

The output consistently uses leading spaces as allowed by the question (in fact at no extra byte cost, it could do trailing spaces instead). Here is an example:

```
 F G H I J K
 E X Y Z 0 L
 D W 7 8 1 M
 C V 6 9 2 N
 B U 5 4 3 O
 A T S R Q P

```

---

As I saw that spaces are required, this original code (for 61) is not valid because it doesn't add a space between each character. But I will add it here for reference.

```
b=['A':'Z' '0':'9'];disp(rot90(b(37-spiral(6)'),6-input('')))

```

and produces:

```
ABCDEF
TUVWXG
S567YH
R498ZI
Q3210J
PONMLK

```

# Answer
> 2 votes
# JavaScript ES6, 165 ~~172~~

Simple rotation, starting from a hardcoded string

**Note** 1 byte saved thx @user81655

```
p=prompt();alert("ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK".split` `.map((r,y,a)=>[...r].map((c,x)=>p<2?c:a[p<3?5-x:p<4?5-y:x][p<3?y:p<4?5-x:5-y]).join` `).join`
`)

```

Test snippet:

```
// Test: redefine alert to write inside the snippet
alert=x=>P.innerHTML=x

p=prompt();
alert(
  "ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK"
  .split` `
  .map(
    (r,y,a)=>
    [...r].map(
      (c,x)=>p<2?c:
      a
       [p<3?5-x:p<4?5-y:x]
       [p<3?y:p<4?5-x:5-y]
    ).join` `
  ).join`\n`
)
```

```
<pre id=P></pre>
```

# Answer
> 1 votes
# Pyth - 60 bytes

Hardcodes the string and uses matrix operations to get all the options.

```
jjL\ @[_CKc6"ABCDEFTUVWXGS567YHR498ZIQ3210JPONMLK"KC_K__MK)Q

```

Test Suite.

# Answer
> 1 votes
# Ruby, 173 bytes

```
->i{_,r,o=->s{s.map{|i|i*' '}},->s{s.transpose.map{|i|i.reverse}},%W(ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK).map(&:chars);puts i<2?_[o]:i<3?_[t=r[o]]:i<4?_[r[t]]:_[r[r[t]]]}

```

**Ungolfed:**

```
-> i {
  _ = -> s { s.map{|i| i*' ' } }
  r = -> s { s.transpose.map{|i| i.reverse } }
  o = %W(ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK).map(&:chars)
  puts i<2?_[o]:i<3?_[t=r[o]]:i<4?_[r[t]]:_[r[r[t]]]
}

```

**Usage:**

```
->i{_,r,o=->s{s.map{|i|i*' '}},->s{s.transpose.map{|i|i.reverse}},%W(ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK).map(&:chars);puts i<2?_[o]:i<3?_[t=r[o]]:i<4?_[r[t]]:_[r[r[t]]]}[4]
F G H I J K
E X Y Z 0 L
D W 7 8 1 M
C V 6 9 2 N
B U 5 4 3 O
A T S R Q P

```

# Answer
> 1 votes
## Python, 152 bytes

```
s=[r for r in "ABCDEF TUVWXG S567YH R498ZI Q3210J PONMLK".split(" ")]
for i in range(1,int(input())):s=zip(*list(s)[::-1])
for x in s:print(" ".join(x))

```

---
Tags: code-golf, string, kolmogorov-complexity, grid
---