# Question
Title: These Primes of Mine Are Always Solid Lines
Let's create a N×N grid of spaces and underscores that can be used to visually determine if a number is prime. (N may be any positive integer.)

This grid has three simple rules:

1. The nth column contains the repeated pattern of n - 1 underscores followed by one space. This pattern starts at the first row and is stopped, possibly mid-pattern, at row N. (Rows and columns are 1-indexed.)
2. The first column is replaced with all underscores instead of all spaces.
3. If a space occurs somewhere the row index equals the column index it is replaced with an underscore.

# Example: N = 10

```
           1
  1234567890 <-- column indices
 1__________
 2__________
 3__________
 4_ ________
 5__________
 6_  _______
 7__________
 8_ _ ______
 9__ _______
10_ __ _____
 ^ row indices

```

The indices are just for clarity. The plain grid itself (what your program must output) is:

```
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____

```

Notice that:

* The first column is all underscores.
* The second column goes underscore space, underscore space, etc., except for the underscore on row 2.
* The third column goes underscore underscore space, underscore underscore space, etc., except for the underscore on row 3.
* etc.

**Also notice that besides 1, only prime numbered rows have underscores in every column.**

Since underscores span the entire font width, each prime numbered row forms a continuous solid line. So checking if a number is prime or not is quite easy visually; just check if its line is solid across all columns. (In fact looking up to the square root of the row index suffices but outputting that grid seems less elegant.)

# Program

Write a program that will draw these grids given N via stdin (or closest alternative). Output goes to stdout (or closest alternative) and should only contain spaces, underscores, and newlines, with an optional trailing newline.

The shortest code wins.

# Answer
> 7 votes
# CJam, ~~33~~ ~~28~~ 27 bytes

```
q~,:)_f{f{md\1=+'_S?}0'_tN}

```

Try it online.

### How it works

```
q~        " Read one line from STDIN and evaluate it.                                     ";
,:)       " For “N”, push [ 1 ... N ].                                                    ";
_         " Push a copy.                                                                  ";
f{        " For each “I in [ 1 ... N ], push “I   [ 1 ... N ]”; then:                     ";
  f{      " For each “J in [ 1 ... N ], push “J   I”; then:                               ";
    md\   " Push “J % I   J / I”.                                                         ";
    1=+   " Calculate “J % I + (J / I == 1)”.                                             ";
    '_S?  " Push an underscore if the result is truthy and a space otherwise.             ";
  }       "                                                                               ";
  0'_t    " Replace the first character of the resulting array by an underscore.          ";
  N       " Push a newline.                                                               ";
}         "                                                                               ";

```

### Example run

```
$ cjam solid-primes.cjam <<< 10
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam solid-primes.cjam <<< 100 | md5sum # trailing newline
e4396b316989813dada21141b569ccf9  -

```

# Answer
> 5 votes
# Ruby, ~~77~~ 73 characters

```
puts (1..n=gets.to_i).map{|a|?_+(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join}

```

Some tricks I used:

* The `..` operator has almost the lowest precedence of all operators in Ruby, so `(1..n=gets.to_i)` just works.
* Instead of adding an extra `a!=1` condition when checking to see if the character should be a space instead of an underscore (since the first row is all underscores), I just started the range from `2` and prepended an extra `?_`.
* Line A can become line B:

```
A | a%b==0&&a!=b ? ' ':?_
B | a!=b&&a%b==0? ' ':?_

```

because I have to have an extra space between `b` and `?` in line A, but that's not needed between `0` and `?` in line B. `b?` is a valid Ruby method, but `0?` is not.
* `puts` will automatically join arrays with newlines for you, removing the need for an extra `*"\n"`.

Output for `n=100`:

```
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________________________________________________________________________
____________________________________________________________________________________________________
_  _________________________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ________________________________________________________________________________________________
__ _________________________________________________________________________________________________
_ __ _______________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ ______________________________________________________________________________________________
____________________________________________________________________________________________________
_ ____ _____________________________________________________________________________________________
__ _ _______________________________________________________________________________________________
_ _ ___ ____________________________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ___________________________________________________________________________________________
____________________________________________________________________________________________________
_ _  ____ __________________________________________________________________________________________
__ ___ _____________________________________________________________________________________________
_ ________ _________________________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ________________________________________________________________________________________
____ _______________________________________________________________________________________________
_ __________ _______________________________________________________________________________________
__ _____ ___________________________________________________________________________________________
_ _ __ ______ ______________________________________________________________________________________
____________________________________________________________________________________________________
_  _  ___ ____ _____________________________________________________________________________________
____________________________________________________________________________________________________
_ _ ___ _______ ____________________________________________________________________________________
__ _______ _________________________________________________________________________________________
_ ______________ ___________________________________________________________________________________
____ _ _____________________________________________________________________________________________
_   _ __ __ _____ __________________________________________________________________________________
____________________________________________________________________________________________________
_ ________________ _________________________________________________________________________________
__ _________ _______________________________________________________________________________________
_ _  __ _ _________ ________________________________________________________________________________
____________________________________________________________________________________________________
_  __  ______ ______ _______________________________________________________________________________
____________________________________________________________________________________________________
_ _ ______ __________ ______________________________________________________________________________
__ _ ___ _____ _____________________________________________________________________________________
_ ____________________ _____________________________________________________________________________
____________________________________________________________________________________________________
_   _ _ ___ ___ _______ ____________________________________________________________________________
______ _____________________________________________________________________________________________
_ __ ____ ______________ ___________________________________________________________________________
__ _____________ ___________________________________________________________________________________
_ _ ________ ____________ __________________________________________________________________________
____________________________________________________________________________________________________
_  __ __ ________ ________ _________________________________________________________________________
____ _____ _________________________________________________________________________________________
_ _ __  _____ _____________ ________________________________________________________________________
__ _______________ _________________________________________________________________________________
_ __________________________ _______________________________________________________________________
____________________________________________________________________________________________________
_     ___ _ __ ____ _________ ______________________________________________________________________
____________________________________________________________________________________________________
_ ____________________________ _____________________________________________________________________
__ ___ _ ___________ _______________________________________________________________________________
_ _ ___ _______ _______________ ____________________________________________________________________
____ _______ _______________________________________________________________________________________
_  __ ____ __________ __________ ___________________________________________________________________
____________________________________________________________________________________________________
_ _ ____________ ________________ __________________________________________________________________
__ ___________________ _____________________________________________________________________________
_ __ _ __ ___ ____________________ _________________________________________________________________
____________________________________________________________________________________________________
_   _ _  __ _____ _____ ___________ ________________________________________________________________
____________________________________________________________________________________________________
_ __________________________________ _______________________________________________________________
__ _ _________ _________ ___________________________________________________________________________
_ _ ______________ __________________ ______________________________________________________________
______ ___ _________________________________________________________________________________________
_  __ ______ ____________ ____________ _____________________________________________________________
____________________________________________________________________________________________________
_ _  __ _ _____ ___ ___________________ ____________________________________________________________
__ _____ _________________ _________________________________________________________________________
_ ______________________________________ ___________________________________________________________
____________________________________________________________________________________________________
_   _  ____ _ ______ ______ _____________ __________________________________________________________
____ ___________ ___________________________________________________________________________________
_ ________________________________________ _________________________________________________________
__ _________________________ _______________________________________________________________________
_ _ ___ __ __________ _____________________ ________________________________________________________
____________________________________________________________________________________________________
_  _  __  ____ __ ___________ ______________ _______________________________________________________
______ _____ _______________________________________________________________________________________
_ _ __________________ ______________________ ______________________________________________________
__ ___________________________ _____________________________________________________________________
_ ____________________________________________ _____________________________________________________
____ _____________ _________________________________________________________________________________
_   _ _ ___ ___ _______ _______ _______________ ____________________________________________________
____________________________________________________________________________________________________
_ ____ ______ __________________________________ ___________________________________________________
__ _____ _ _____________________ ___________________________________________________________________
_ _  ____ _________ ____ ________________________ __________________________________________________

```

Now including Extra-Special™ Mega-Colorful Red© Highlight-Magic™® Extended Edition©: (click thumbnail to enlarge)

# Ruby with color, 110 characters

```
puts (1..n=gets.to_i).map{|a|x=(2..n).map{|b|a!=b&&a%b==0? ' ':?_}.join;x.index(' ')??_+x :"\e[41m_#{x}\e[0m"}

```

# Answer
> 5 votes
# J - 28 char

```
1('_ '{~0==+&|:1&=+|/~)@:+i.

```

Explained by explosion:

```
1(                    )@:+i.  NB. on vector 1..n, do
                   |/~        NB. take the table "column modulo row"
               1&=+           NB. add 1 to column 1
          =                   NB. identity matrix of size 10
            &|:               NB. transpose both tables (now table is row mod col)
           +                  NB. add them
  '_ '{~0=                    NB. space if cell=0 else underscore

```

What it looks like:

```
   1('_ '{~0==+&|:1&=+|/~)@:+i.25
_________________________
_________________________
_________________________
_ _______________________
_________________________
_  ______________________
_________________________
_ _ _____________________
__ ______________________
_ __ ____________________
_________________________
_   _ ___________________
_________________________
_ ____ __________________
__ _ ____________________
_ _ ___ _________________
_________________________
_  __ __ ________________
_________________________
_ _  ____ _______________
__ ___ __________________
_ ________ ______________
_________________________
_   _ _ ___ _____________
____ ____________________

```

# Answer
> 4 votes
# Python 2, ~~76~~ 71

```
r=range(1,input()+1)
for i in r:print''.join("_ "[i%j<1<j<i]for j in r)

```

Not sure if it can get any shorter than this... These keywords: `range`, `input` and `print` cost quite a lot.

# Answer
> 3 votes
## APL (28)

```
'_ '[(1+(1≠⊢)∧≠∧0=|⍨)/¨⍳2⍴⎕]

```

Explanation:

* `⍳2⍴⎕`: read a number N and make an N-by-N coordinate matrix
* `(`...`)/¨`: for each pair of coordinates, apply the following function:
    + A cell must have a space if:
    + `0=|⍨`: y `mod` x = 0, and
    + : x isn't equal to y, and
    + `1≠⊢`: x isn't `1`.
    + `1+`: Add `1` to the resulting bit matrix because APL arrays start at 1.
* `'_ '[`...`]`: replace each `1` with an underscore and `2` with a space.

# Answer
> 2 votes
## Perl,  ~~69~~  61

Updated version (thanks, *Dennis*!)

```
$n=<>;for$i(1..$n){say"_".join"",map{$i%$_|$i==$_?_:$"}2..$n}

```

Original version:

```
$n=<>;for$i(1..$n){say"_".join("",map{$i%$_||$i==$_?"_":" "}(2..$n))}

```

# Answer
> 2 votes
# CJam, 27 bytes

```
q~:I,{__I?'_*S+I*I<'_t}%zN*

```

Try it online.

This approach achieves the same byte count as my other answer, but I thought it was worth posting anyway. Instead of marking proper multiples in every row, it does exactly what the specification says.

### How it works

```
q~:I                         " Read an integer I from STDIN.                              ";
    ,{                }%     " For each J ∊ {1,...,I}:                                    ";
          '_*S+              " Push J - 1 underscores followed by a space.                ";
               I*I<          " Repeat the pattern to complete I characters.               ";
       _I?                   " For the first row, replace all spaces with underscores.    ";
      _            '_t       " Replace the Jth character by an underscore.                ";
                        zN*  " Transpose rows and columns; separate with linefeeds.       ";

```

### Example run

```
$ cjam prime-lines.cjam <<< 10; echo
__________
__________
__________
_ ________
__________
_  _______
__________
_ _ ______
__ _______
_ __ _____
$ cjam prime-lines.cjam <<< 100 | md5sum # no trailing newline
83c7b974e1510f482322456a9dbb461f  -

```

# Answer
> 1 votes
## C, 143

C is obviously not the right choice of language for this. But for completeness, here's one possible way to do it in C. Works for values of *n* up to 1048575. Reads *n* from standard input.

```
#include <stdio.h>
main(){int n,i=0,j;scanf("%d",&n);char x[1<<20];x[n+1]=0;
for(;++i<=n;){for(j=0;++j<=n;)x[j]=i%j|i==j|j==1?95:32;puts(x+1);}}

```

It is very fast, however.

* Runtime for *n*=1,000,000 (which produces a 1,000,000,000,000-element grid) is approximately 55 minutes on my system.
* Runtime for *n*=1000 (which produes a 1,000,000-element grid) is less than 1/100 second.

---
Tags: code-golf, primes
---


# Question
Title: Redraw an image with just one closed curve
Inspired by vi.sualize.us

### Goal

The input is a grayscale image and the output is a black and white image. The output image consists of just one closed curve (loop) that is not allowed to intersect with itself or touch itself. The width of the line shall be constant throughout the whole image. The challenge here is finding an algorithm for doing so. The output just has to represent the input image, but with any artistic freedom. The resolution is not so important but the aspect ratio should stay about the same.

### Example

### More test images

# Answer
# Java : Dot matrix style

Since nobody has answered the question yet I'll give it a shot. First I wanted to fill a canvas with Hilbert curves, but in the end I've opted for a simpler approach:

Here is the code:

```
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;

public class LineArt extends JPanel {
    private BufferedImage ref;
    //Images are stored in integers:
    int[] images = new int[] {31, 475, 14683, 469339};
    int[] brightness = new int[] {200,170,120,0};

    public static void main(String[] args) throws Exception {
        new LineArt(args[0]);
    }

    public LineArt(String filename) throws Exception {
        ref = ImageIO.read(new File(filename));
        JFrame frame = new JFrame();
        frame.setVisible(true);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(ref.getWidth()*5, ref.getHeight()*5);
        this.setPreferredSize(new Dimension((ref.getWidth()*5)+20, (ref.getHeight()*5)+20));
        frame.add(new JScrollPane(this));
    }

    @Override
    public void paint(Graphics g) {
        Graphics2D g2d = (Graphics2D) g;
        g2d.setColor(Color.WHITE);
        g2d.fillRect(0, 0, getWidth(), getHeight());
        g2d.translate(10, 10);
        g2d.setColor(Color.BLACK);
        g2d.drawLine(0, 0, 4, 0);
        g2d.drawLine(0, 0, 0, ref.getHeight()*5);

        for(int y = 0; y<ref.getHeight();y++) {
            for(int x = 1; x<ref.getWidth()-1;x++) {
                int light = new Color(ref.getRGB(x, y)).getRed();
                int offset = 0;
                while(brightness[offset]>light) offset++;
                for(int i = 0; i<25;i++) {
                    if((images[offset]&1<<i)>0) {
                        g2d.drawRect((x*5)+i%5, (y*5)+(i/5), 0,0);
                    }
                }
            }
            g2d.drawLine(2, (y*5), 4, (y*5));
            g2d.drawLine((ref.getWidth()*5)-5, (y*5), (ref.getWidth()*5)-1, (y*5));
            if(y%2==0) {
                g2d.drawLine((ref.getWidth()*5)-1, (y*5), (ref.getWidth()*5)-1, (y*5)+4);
            } else {
                g2d.drawLine(2, (y*5), 2, (y*5)+4);
            }
        }
        if(ref.getHeight()%2==0) {
            g2d.drawLine(0, ref.getHeight()*5, 2, ref.getHeight()*5);
        } else {
            g2d.drawLine(0, ref.getHeight()*5, (ref.getWidth()*5)-1, ref.getHeight()*5);
        }
    }
}

```

**Update**: Now it creates a cycle, not just a single line
> 35 votes

# Answer
# Python: Hilbert curve (~~373~~ 361)

I decided to draw a Hilbert curve with variable granularity depending on the image intensity:

```
import pylab as pl
from scipy.misc import imresize, imfilter
import turtle

# load image
img = pl.flipud(pl.imread("face.png"))

# setup turtle
levels = 8
size = 2**levels
turtle.setup(img.shape[1] * 4.2, img.shape[0] * 4.2)
turtle.setworldcoordinates(0, 0, size, -size)
turtle.tracer(1000, 0)

# resize and blur image
img = imfilter(imresize(img, (size, size)), 'blur')

# define recursive hilbert curve
def hilbert(level, angle = 90):
    if level == 0:
        return
    if level == 1 and img[-turtle.pos()[1], turtle.pos()[0]] > 128:
        turtle.forward(2**level - 1)
    else:
        turtle.right(angle)
        hilbert(level - 1, -angle)
        turtle.forward(1)
        turtle.left(angle)
        hilbert(level - 1, angle)
        turtle.forward(1)
        hilbert(level - 1, angle)
        turtle.left(angle)
        turtle.forward(1)
        hilbert(level - 1, -angle)
        turtle.right(angle)

# draw hilbert curve
hilbert(levels)
turtle.update()

```

Actually I planned to make decisions on different levels of detail, like "This spot is so bright, I'll stop the recursion and move to the next block!". But evaluating image intensity locally leading to large movements is very inaccurate and looks ugly. So I ended up with only deciding whether to skip level 1 or to draw another Hilbert loop.

Here is the result on the first test image:

Thanks to @githubphagocyte the rendering is pretty fast (using `turtle.tracer`). Thus I don't have to wait all night for a result and can go to my well-deserved bed. :)

---

**Some code golf**

@flawr: "short program"? You haven't seen the golfed version! ;)

So just for fun:

```
from pylab import*;from scipy.misc import*;from turtle import*
i=imread("f.p")[::-1];s=256;h=i.shape;i=imfilter(imresize(i,(s,s)),'blur')
setup(h[1]*4.2,h[0]*4.2);setworldcoordinates(0,0,s,-s);f=forward;r=right
def h(l,a=90):
 x,y=pos()
 if l==1and i[-y,x]>128:f(2**l-1)
 else:
  if l:l-=1;r(a);h(l,-a);f(1);r(-a);h(l,a);f(1);h(l,a);r(-a);f(1);h(l,-a);r(a)
h(8)

```

(~~373~~ 361 characters. But it will take forever since I remove the `turte.tracer(...)` command!)

---

**Animation by flawr**

flawr: *My algorithm is slightly modified to what @DenDenDo told me: I had to delete some points in every iteration because the convergence would slow down drastically. That's why the curve will intersect itself.*
> 36 votes

# Answer
# Python 3.4 - Traveling Salesman Problem

The program creates a dithered image from the original:

For each black pixel a point is randomly generated near the pixel centre and these points are treated as a traveling salesman problem. The program saves an html file containing an SVG image at regular intervals as it attempts to reduce the path length. The path starts out self intersecting and gradually becomes less so over a number of hours. Eventually the path is no longer self intersecting:

```
'''
Traveling Salesman image approximation.
'''

import os.path

from PIL import Image   # This uses Pillow, the PIL fork for Python 3.4
                        # https://pypi.python.org/pypi/Pillow

from random import random, sample, randrange, shuffle
from time import perf_counter

def make_line_picture(image_filename):
    '''Save SVG image of closed curve approximating input image.'''
    input_image_path = os.path.abspath(image_filename)
    image = Image.open(input_image_path)
    width, height = image.size
    scale = 1024 / width
    head, tail = os.path.split(input_image_path)
    output_tail = 'TSP_' + os.path.splitext(tail)[0] + '.html'
    output_filename = os.path.join(head, output_tail)
    points = generate_points(image)
    population = len(points)
    save_dither(points, image)
    grid_cells = [set() for i in range(width * height)]
    line_cells = [set() for i in range(population)]
    print('Initialising acceleration grid')
    for i in range(population):
        recalculate_cells(i, width, points, grid_cells, line_cells)
    while True:
        save_svg(output_filename, width, height, points, scale)
        improve_TSP_solution(points, width, grid_cells, line_cells)

def save_dither(points, image):
    '''Save a copy of the dithered image generated for approximation.'''
    image = image.copy()
    pixels = list(image.getdata())
    pixels = [255] * len(pixels)
    width, height = image.size
    for p in points:
        x = int(p[0])
        y = int(p[1])
        pixels[x+y*width] = 0
    image.putdata(pixels)
    image.save('dither_test.png', 'PNG')

def generate_points(image):
    '''Return a list of points approximating the image.

    All points are offset by small random amounts to prevent parallel lines.'''
    width, height = image.size
    image = image.convert('L')
    pixels = image.getdata()
    points = []
    gap = 1
    r = random
    for y in range(2*gap, height - 2*gap, gap):
        for x in range(2*gap, width - 2*gap, gap):
            if (r()+r()+r()+r()+r()+r())/6 < 1 - pixels[x + y*width]/255:
                        points.append((x + r()*0.5 - 0.25,
                                       y + r()*0.5 - 0.25))
    shuffle(points)
    print('Total number of points', len(points))
    print('Total length', current_total_length(points))
    return points

def current_total_length(points):
    '''Return the total length of the current closed curve approximation.'''
    population = len(points)
    return sum(distance(points[i], points[(i+1)%population])
               for i in range(population))

def recalculate_cells(i, width, points, grid_cells, line_cells):
    '''Recalculate the grid acceleration cells for the line from point i.'''
    for j in line_cells[i]:
        try:
            grid_cells[j].remove(i)
        except KeyError:
            print('grid_cells[j]',grid_cells[j])
            print('i',i)
    line_cells[i] = set()
    add_cells_along_line(i, width, points, grid_cells, line_cells)
    for j in line_cells[i]:
        grid_cells[j].add(i)

def add_cells_along_line(i, width, points, grid_cells, line_cells):
    '''Add each grid cell that lies on the line from point i.'''
    population = len(points)
    start_coords = points[i]
    start_x, start_y = start_coords
    end_coords = points[(i+1) % population]
    end_x, end_y = end_coords
    gradient = (end_y - start_y) / (end_x - start_x)
    y_intercept = start_y - gradient * start_x
    total_distance = distance(start_coords, end_coords)
    x_direction = end_x - start_x
    y_direction = end_y - start_y
    x, y = start_x, start_y
    grid_x, grid_y = int(x), int(y)
    grid_index = grid_x + grid_y * width
    line_cells[i].add(grid_index)
    while True:
        if x_direction > 0:
            x_line = int(x + 1)
        else:
            x_line = int(x)
            if x_line == x:
                x_line = x - 1
        if y_direction > 0:
            y_line = int(y + 1)
        else:
            y_line = int(y)
            if y_line == y:
                y_line = y - 1
        x_line_intersection = gradient * x_line + y_intercept
        y_line_intersection = (y_line - y_intercept) / gradient
        x_line_distance = distance(start_coords, (x_line, x_line_intersection))
        y_line_distance = distance(start_coords, (y_line_intersection, y_line))
        if (x_line_distance > total_distance and
            y_line_distance > total_distance):
            break
        if x_line_distance < y_line_distance:
            x = x_line
            y = gradient * x_line + y_intercept
        else:
            y = y_line
            x = (y_line - y_intercept) / gradient
        grid_x = int(x - (x_direction < 0) * (x == int(x)))
        grid_y = int(y - (y_direction < 0) * (y == int(y)))
        grid_index = grid_x + grid_y * width
        line_cells[i].add(grid_index)

def improve_TSP_solution(points, width, grid_cells, line_cells,
                         performance=[0,0,0], total_length=None):
    '''Apply 3 approaches, allocating time to each based on performance.'''
    population = len(points)
    if total_length is None:
        total_length = current_total_length(points)

    print('Swapping pairs of vertices')
    if performance[0] == max(performance):
        time_limit = 300
    else:
        time_limit = 10
    print('    Aiming for {} seconds'.format(time_limit))
    start_time = perf_counter()
    for n in range(1000000):
        swap_two_vertices(points, width, grid_cells, line_cells)
        if perf_counter() - start_time > time_limit:
            break
    time_taken = perf_counter() - start_time
    old_length = total_length
    total_length = current_total_length(points)
    performance[0] = (old_length - total_length) / time_taken
    print('    Time taken', time_taken)
    print('    Total length', total_length)
    print('    Performance', performance[0])

    print('Moving single vertices')
    if performance[1] == max(performance):
        time_limit = 300
    else:
        time_limit = 10
    print('    Aiming for {} seconds'.format(time_limit))
    start_time = perf_counter()
    for n in range(1000000):
        move_a_single_vertex(points, width, grid_cells, line_cells)
        if perf_counter() - start_time > time_limit:
            break
    time_taken = perf_counter() - start_time
    old_length = total_length
    total_length = current_total_length(points)
    performance[1] = (old_length - total_length) / time_taken
    print('    Time taken', time_taken)
    print('    Total length', total_length)
    print('    Performance', performance[1])

    print('Uncrossing lines')
    if performance[2] == max(performance):
        time_limit = 60
    else:
        time_limit = 10
    print('    Aiming for {} seconds'.format(time_limit))
    start_time = perf_counter()
    for n in range(1000000):
        uncross_lines(points, width, grid_cells, line_cells)
        if perf_counter() - start_time > time_limit:
            break
    time_taken = perf_counter() - start_time
    old_length = total_length
    total_length = current_total_length(points)
    performance[2] = (old_length - total_length) / time_taken
    print('    Time taken', time_taken)
    print('    Total length', total_length)
    print('    Performance', performance[2])

def swap_two_vertices(points, width, grid_cells, line_cells):
    '''Attempt to find a pair of vertices that reduce length when swapped.'''
    population = len(points)
    for n in range(100):
        candidates = sample(range(population), 2)
        befores = [(candidates[i] - 1) % population
                   for i in (0,1)]
        afters = [(candidates[i] + 1) % population for i in (0,1)]
        current_distance = sum((distance(points[befores[i]],
                                         points[candidates[i]]) +
                                distance(points[candidates[i]],
                                         points[afters[i]]))
                               for i in (0,1))
        (points[candidates[0]],
         points[candidates[1]]) = (points[candidates[1]],
                                   points[candidates[0]])
        befores = [(candidates[i] - 1) % population
                   for i in (0,1)]
        afters = [(candidates[i] + 1) % population for i in (0,1)]
        new_distance = sum((distance(points[befores[i]],
                                     points[candidates[i]]) +
                            distance(points[candidates[i]],
                                     points[afters[i]]))
                           for i in (0,1))
        if new_distance > current_distance:
            (points[candidates[0]],
             points[candidates[1]]) = (points[candidates[1]],
                                       points[candidates[0]])
        else:
            modified_points = tuple(set(befores + candidates))
            for k in modified_points:
                recalculate_cells(k, width, points, grid_cells, line_cells)
            return

def move_a_single_vertex(points, width, grid_cells, line_cells):
    '''Attempt to find a vertex that reduces length when moved elsewhere.'''
    for n in range(100):
        population = len(points)
        candidate = randrange(population)
        offset = randrange(2, population - 1)
        new_location = (candidate + offset) % population
        before_candidate = (candidate - 1) % population
        after_candidate = (candidate + 1) % population
        before_new_location = (new_location - 1) % population
        old_distance = (distance(points[before_candidate], points[candidate]) +
                        distance(points[candidate], points[after_candidate]) +
                        distance(points[before_new_location],
                                 points[new_location]))
        new_distance = (distance(points[before_candidate],
                                 points[after_candidate]) +
                        distance(points[before_new_location],
                                 points[candidate]) +
                        distance(points[candidate], points[new_location]))
        if new_distance <= old_distance:
            if new_location < candidate:
                points[:] = (points[:new_location] +
                             points[candidate:candidate + 1] +
                             points[new_location:candidate] +
                             points[candidate + 1:])
                for k in range(candidate - 1, new_location, -1):
                    for m in line_cells[k]:
                        grid_cells[m].remove(k)
                    line_cells[k] = line_cells[k - 1]
                    for m in line_cells[k]:
                        grid_cells[m].add(k)
                for k in ((new_location - 1) % population,
                          new_location, candidate):
                    recalculate_cells(k, width, points, grid_cells, line_cells)
            else:
                points[:] = (points[:candidate] +
                             points[candidate + 1:new_location] +
                             points[candidate:candidate + 1] +
                             points[new_location:])
                for k in range(candidate, new_location - 3):
                    for m in line_cells[k]:
                        grid_cells[m].remove(k)
                    line_cells[k] = line_cells[k + 1]
                    for m in line_cells[k]:
                        grid_cells[m].add(k)
                for k in ((candidate - 1) % population,
                          new_location - 2, new_location - 1):
                    recalculate_cells(k, width, points, grid_cells, line_cells)
            return

def uncross_lines(points, width, grid_cells, line_cells):
    '''Attempt to find lines that are crossed, and reverse path to uncross.'''
    population = len(points)
    for n in range(100):
        i = randrange(population)
        start_1 = points[i]
        end_1 = points[(i + 1) % population]
        if not line_cells[i]:
            recalculate_cells(i, width, points, grid_cells, line_cells)
        for cell in line_cells[i]:
            for j in grid_cells[cell]:
                if i != j and i != (j+1)%population and i != (j-1)%population:
                    start_2 = points[j]
                    end_2 = points[(j + 1) % population]
                    if are_crossed(start_1, end_1, start_2, end_2):
                        if i < j:
                            points[i + 1:j + 1] = reversed(points[i + 1:j + 1])
                            for k in range(i, j + 1):
                                recalculate_cells(k, width, points, grid_cells,
                                                  line_cells)
                        else:
                            points[j + 1:i + 1] = reversed(points[j + 1:i + 1])
                            for k in range(j, i + 1):
                                recalculate_cells(k, width, points, grid_cells,
                                                  line_cells)
                        return

def are_crossed(start_1, end_1, start_2, end_2):
    '''Return True if the two lines intersect.'''
    if end_1[0]-start_1[0] and end_2[0]-start_2[0]:
        gradient_1 = (end_1[1]-start_1[1])/(end_1[0]-start_1[0])
        gradient_2 = (end_2[1]-start_2[1])/(end_2[0]-start_2[0])
        if gradient_1-gradient_2:
            intercept_1 = start_1[1] - gradient_1 * start_1[0]
            intercept_2 = start_2[1] - gradient_2 * start_2[0]
            x = (intercept_2 - intercept_1) / (gradient_1 - gradient_2)
            if (x-start_1[0]) * (end_1[0]-x) > 0 and (x-start_2[0]) * (end_2[0]-x) > 0:
                return True

def distance(point_1, point_2):
    '''Return the Euclidean distance between the two points.'''
    return sum((point_1[i] - point_2[i]) ** 2 for i in (0, 1)) ** 0.5

def save_svg(filename, width, height, points, scale):
    '''Save a file containing an SVG path of the points.'''
    print('Saving partial solution\n')
    with open(filename, 'w') as file:
        file.write(content(width, height, points, scale))

def content(width, height, points, scale):
    '''Return the full content to be written to the SVG file.'''
    return (header(width, height, scale) +
            specifics(points, scale) +
            footer()
            )

def header(width, height,scale):
    '''Return the text of the SVG header.'''
    return ('<?xml version="1.0"?>\n'
            '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN"\n'
            '    "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">\n'
            '\n'
            '<svg width="{0}" height="{1}">\n'
            '<title>Traveling Salesman Problem</title>\n'
            '<desc>An approximate solution to the Traveling Salesman Problem</desc>\n'
            ).format(scale*width, scale*height)

def specifics(points, scale):
    '''Return text for the SVG path command.'''
    population = len(points)
    x1, y1 = points[-1]
    x2, y2 = points[0]
    x_mid, y_mid = (x1 + x2) / 2, (y1 + y2) / 2
    text = '<path d="M{},{} L{},{} '.format(x1, y1, x2, y2)
    for i in range(1, population):
        text += 'L{},{} '.format(*points[i])
    text += '" stroke="black" fill="none" stroke-linecap="round" transform="scale({0},{0})" vector-effect="non-scaling-stroke" stroke-width="3"/>'.format(scale)
    return text

def footer():
    '''Return the closing text of the SVG file.'''
    return '\n</svg>\n'

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if arguments:
        make_line_picture(arguments[0])
    else:
        print('Required argument: image file')

```

The program uses 3 different approaches to improving the solution, and measures the performance per second for each. The time allocated to each approach is adjusted to give the majority of time to whatever approach is best performing at that time.

I initially tried guessing what proportion of time to allocate to each approach, but it turns out that which approach is most effective varies considerably during the course of the process, so it makes a big difference to keep adjusting automatically.

The three simple approaches are:

1. Pick two points at random and swap them if this does not increase the total length.
2. Pick one point at random and a random offset along the list of points and move it if the length does not increase.
3. Pick a line at random and check whether any other line crosses it, reversing any section of path that causes a cross.

For approach 3 a grid is used, listing all of the lines that pass through a given cell. Rather than have to check every line on the page for intersection, only those that have a grid cell in common are checked.

---

I got the idea for using the traveling salesman problem from a blog post that I saw before this challenge was posted, but I couldn't track it down when I posted this answer. I believe the image in the challenge was produced using a traveling salesman approach too, combined with some kind of path smoothing to remove the sharp turns.

I still can't find the specific blog post but I have now found reference to the original papers in which the Mona Lisa was used to demonstrate the traveling salesman problem.

The TSP implementation here is a hybrid approach which I experimented with for fun for this challenge. I hadn't read the linked papers when I posted this. My approach is painfully slow by comparison. Note that my image here uses less than 10,000 points, and takes many hours to converge enough to have no crossing lines. The example image in the link to the papers uses 100,000 points...

Unfortunately most of the links seem to be dead now, but the paper "TSP Art" by Craig S Kaplan & Robert Bosch 2005 still works and gives an interesting overview of different approaches.
> 33 votes

# Answer
## Java - Oscillations

The program draws a closed path and add oscillations whose amplitude and frequency are based on image brightness. The "corners" of path do not have oscillations to make sure the path does not intersects itself.

```
package trace;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

import snake.Image;

public class Main5 {

    private final static int MULT = 3;
    private final static int ROWS = 80; // must be an even number
    private final static int COLS = 40;

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

        int [] white = {255, 255, 255};
        for (int y = 0; y < dest.getHeight(); y++) {
            for (int x = 0; x < dest.getWidth(); x++) {
                dest.getRaster().setPixel(x, y, white);
            }
        }
        for (int j = 0; j < ROWS; j++) {
            if (j%2 == 0) {
                for (int i = j==0 ? 0 : 1; i < COLS-1; i++) {
                    drawLine(dest, src, (i+.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (i+1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS,
                            i > 1 && i < COLS-2);
                }

                drawLine(dest, src, (COLS-.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (COLS-.5)*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
            } else {
                for (int i = COLS-2; i >= (j == ROWS - 1 ? 0 : 1); i--) {
                    drawLine(dest, src, (i+.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (i+1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS,
                            i > 1 && i < COLS-2);
                }
                if (j < ROWS-1) {
                    drawLine(dest, src, (1.5)*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, (1.5)*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
                }
            }
            if (j < ROWS-1) {
                drawLine(dest, src, 0.5*dest.getWidth()/COLS, (j+.5)*dest.getHeight()/ROWS, 0.5*dest.getWidth()/COLS, (j+1.5)*dest.getHeight()/ROWS, false);
            }
        }
        ImageIO.write(dest, "png", new File("output.png"));
    }

    private static void drawLine(BufferedImage dest, BufferedImage src, double x1, double y1, double x2, double y2, boolean oscillate) {
        int [] black = {0, 0, 0};

        int col = smoothPixel((int)((x1*.5 + x2*.5) / MULT), (int)((y1*.5+y2*.5) / MULT), src);
        int fact = (255 - col) / 32;
        if (fact > 5) fact = 5;
        double dx = y1 - y2;
        double dy = - (x1 - x2);
        double dist = 2 * (Math.abs(x1 - x2) + Math.abs(y1 - y2)) * (fact + 1);
        for (int i = 0; i <= dist; i++) {
            double amp = oscillate ? (1 - Math.cos(fact * i*Math.PI*2/dist)) * 12 : 0;
            double x = (x1 * i + x2 * (dist - i)) / dist;
            double y = (y1 * i + y2 * (dist - i)) / dist;
            x += dx * amp / COLS;
            y += dy * amp / ROWS;
            dest.getRaster().setPixel((int)x, (int)y, black);
        }
    }

    public static int smoothPixel(int x, int y, BufferedImage src) {
        int sum = 0, count = 0;
        for (int j = -2; j <= 2; j++) {
            for (int i = -2; i <= 2; i++) {
                if (x + i >= 0 && x + i < src.getWidth()) {
                    if (y + j >= 0 && y + j < src.getHeight()) {
                        sum += src.getRGB(x + i, y + j) & 255;
                        count++;
                    }
                }
            }
        }
        return sum / count;
    }
}

```

Below a comparable algorithm that is based on a spiral. (**I know the path does not close and that it certainly intersects**, I just post it for the sake of art :-)
> 24 votes

# Answer
## Java - Recursive Path

I start from a 2x3 closed path. I scan each cell of the path and divide it into a new 3x3 sub-path. I try each time to choose the 3x3 sub-path that "looks like" the original picture. I repeat the above process 4 times.

Here is the code:

```
package divide;

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

import javax.imageio.ImageIO;

import snake.Image;

public class Divide {

    private final static int MULT = 3;
    private final static int ITERATIONS = 4;

    public static void main(String[] args) throws IOException {
        BufferedImage src = ImageIO.read(Image.class.getClassLoader().getResourceAsStream("input.png"));
        BufferedImage dest = new BufferedImage(src.getWidth() * MULT, src.getHeight() * MULT, BufferedImage.TYPE_INT_RGB);
        for (int y = 0; y < src.getHeight() * MULT; y++) {
            for (int x = 0; x < src.getWidth() * MULT; x++) {
                dest.getRaster().setPixel(x, y, new int [] {255, 255, 255});
            }
        }
        List<String> tab = new ArrayList<String>();
        tab.add("rg");
        tab.add("||");
        tab.add("LJ");

        for (int k = 1; k <= ITERATIONS; k++) {
            boolean choose = k>=ITERATIONS-1;
            // multiply size by 3
            tab = iterate(src, tab, choose);
            // fill in the white space - if needed
            expand(src, tab, " r", " L", "r-", "L-", choose);
            expand(src, tab, "g ", "J ", "-g", "-J", choose);
            expand(src, tab, "LJ", "  ", "||", "LJ", choose);
            expand(src, tab, "  ", "rg", "rg", "||", choose);
            expand(src, tab, "L-J", "   ", "| |", "L-J", choose);
            expand(src, tab, "   ", "r-g", "r-g", "| |", choose);
            expand(src, tab, "| |", "| |", "Lg|", "rJ|", choose);
            expand(src, tab, "--", "  ", "gr", "LJ", choose);
            expand(src, tab, "  ", "--", "rg", "JL", choose);
            expand(src, tab, "| ", "| ", "Lg", "rJ", choose);
            expand(src, tab, " |", " |", "rJ", "Lg", choose);

            for (String s : tab) {
                System.out.println(s);
            }
            System.out.println();
        }

        for (int j = 0; j < tab.size(); j++) {
            String line = tab.get(j);
            for (int i = 0; i < line.length(); i++) {
                char c = line.charAt(i);
                int xleft = i * dest.getWidth() / line.length();
                int xright = (i+1) * dest.getWidth() / line.length();
                int ytop = j * dest.getHeight() / tab.size();
                int ybottom = (j+1) * dest.getHeight() / tab.size();
                int x = (xleft + xright) / 2;
                int y = (ytop + ybottom) / 2;
                if (c == '|') {
                    drawLine(dest, x, ytop, x, ybottom);
                }
                if (c == '-') {
                    drawLine(dest, xleft, y, xright, y);
                }
                if (c == 'L') {
                    drawLine(dest, x, y, xright, y);
                    drawLine(dest, x, y, x, ytop);
                }
                if (c == 'J') {
                    drawLine(dest, x, y, xleft, y);
                    drawLine(dest, x, y, x, ytop);
                }
                if (c == 'r') {
                    drawLine(dest, x, y, xright, y);
                    drawLine(dest, x, y, x, ybottom);
                }
                if (c == 'g') {
                    drawLine(dest, x, y, xleft, y);
                    drawLine(dest, x, y, x, ybottom);
                }
            }

        }

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

    }

    private static void drawLine(BufferedImage dest, int x1, int y1, int x2, int y2) {
        int dist = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
        for (int i = 0; i <= dist; i++) {
            int x = (x1*(dist - i) + x2 * i) / dist;
            int y = (y1*(dist - i) + y2 * i) / dist;
            dest.getRaster().setPixel(x, y, new int [] {0, 0, 0});
        }
    }

    private static void expand(BufferedImage src, List<String> tab, String p1, String p2, String r1, String r2, boolean choose) {
        for (int k = 0; k < (choose ? 2 : 1); k++) {
            while (true) {
                boolean again = false;
                for (int j = 0; j < tab.size() - 1; j++) {
                    String line1 = tab.get(j);
                    String line2 = tab.get(j+1);
                    int baseScore = evaluateLine(src, j, tab.size(), line1) + evaluateLine(src, j+1, tab.size(), line2);
                    for (int i = 0; i <= line1.length() - p1.length(); i++) {
                        if (line1.substring(i, i + p1.length()).equals(p1)
                                && line2.substring(i, i + p2.length()).equals(p2)) {
                            String nline1 = line1.substring(0,  i) + r1 + line1.substring(i + p1.length());
                            String nline2 = line2.substring(0,  i) + r2 + line2.substring(i + p2.length());
                            int nScore = evaluateLine(src, j, tab.size(), nline1) + evaluateLine(src, j+1, tab.size(), nline2);
                            if (!choose || nScore > baseScore) {
                                tab.set(j, nline1);
                                tab.set(j+1, nline2);
                                again = true;
                                break;
                            }
                        }
                    }
                    if (again) break;
                }
                if (!again) break;
            }
            String tmp1 = r1;
            String tmp2 = r2;
            r1 = p1;
            r2 = p2;
            p1 = tmp1;
            p2 = tmp2;
        }
    }

    private static int evaluateLine(BufferedImage src, int j, int tabSize, String line) {
        int [] color = {0, 0, 0};
        int score = 0;
        for (int i = 0; i < line.length(); i++) {
            char c = line.charAt(i);
            int x = i*src.getWidth() / line.length();
            int y = j*src.getHeight() / tabSize;
            src.getRaster().getPixel(x, y, color);
            if (c == ' ' && color[0] >= 128) score++;
            if (c != ' ' && color[0] < 128) score++;
        }
        return score;
    }

    private static List<String> iterate(BufferedImage src, List<String> tab, boolean choose) {
        int [] color = {0, 0, 0};
        List<String> tab2 = new ArrayList<String>();
        for (int j = 0; j < tab.size(); j++) {
            String line = tab.get(j);
            String l1 = "", l2 = "", l3 = "";
            for (int i = 0; i < line.length(); i++) {
                char c = line.charAt(i);
                List<String []> candidates = replace(c);
                String [] choice = null;
                if (choose) {

                    int best = 0;
                    for (String [] candidate : candidates) {
                        int bright1 = 0;
                        int bright2 = 0;
                        for (int j1 = 0; j1<3; j1++) {
                            int y = j*3+j1;
                            for (int i1 = 0; i1<3; i1++) {
                                int x = i*3+i1;
                                char c2 = candidate[j1].charAt(i1);
                                src.getRaster().getPixel(x*src.getWidth()/(line.length()*3), y*src.getHeight()/(tab.size()*3), color);
                                if (c2 != ' ') bright1++;
                                if (color[0] > 128) bright2++;
                            }
                        }
                        int score = Math.abs(bright1 - bright2);
                        if (choice == null || score > best) {
                            best = score;
                            choice = candidate;
                        }

                    }
                } else {
                    choice = candidates.get(0);
                }
                //String [] r = candidates.get(rand.nextInt(candidates.size()));
                String [] r = choice;
                l1 += r[0];
                l2 += r[1];
                l3 += r[2];
            }
            tab2.add(l1);
            tab2.add(l2);
            tab2.add(l3);
        }
        return tab2;
    }

    private static List<String []> replace(char c) {
        if (c == 'r') {
            return Arrays.asList(
                    new String[] {
                    "r-g",
                    "| L",
                    "Lg "},
                    new String[] {
                    "   ",
                    " r-",
                    " | "},
                    new String[] {
                    "   ",
                    "r--",
                    "Lg "},
                    new String[] {
                    " rg",
                    " |L",
                    " | "},
                    new String[] {
                    "   ",
                    "  r",
                    " rJ"});
        } else if (c == 'g') {
            return Arrays.asList(
                    new String[] {
                    "r-g",
                    "J |",
                    " rJ"},
                    new String[] {
                    "   ",
                    "-g ",
                    " | "},
                    new String[] {
                    "   ",
                    "--g",
                    " rJ"},
                    new String[] {
                    "rg ",
                    "J| ",
                    " | "},
                    new String[] {
                    "   ",
                    "g  ",
                    "Lg "});
        } else if (c == 'L') {
            return Arrays.asList(
                    new String[] {
                    "rJ ",
                    "| r",
                    "L-J"},
                    new String[] {
                    " | ",
                    " L-",
                    "   "},
                    new String[] {
                    "rJ ",
                    "L--",
                    "   "},
                    new String[] {
                    " | ",
                    " |r",
                    " LJ"},
                    new String[] {
                    " Lg",
                    "  L",
                    "   "});
        } else if (c == 'J') {
            return Arrays.asList(
                    new String[] {
                    " Lg",
                    "g |",
                    "L-J"},
                    new String[] {
                    " | ",
                    "-J ",
                    "   "},
                    new String[] {
                    " Lg",
                    "--J",
                    "   "},
                    new String[] {
                    " | ",
                    "g| ",
                    "LJ "},
                    new String[] {
                    "rJ ",
                    "J  ",
                    "   "});
        } else if (c == '-') {
            return Arrays.asList(
                    new String[] {
                    " rg",
                    "g|L",
                    "LJ "},
                    new String[] {
                    "rg ",
                    "J|r",
                    " LJ"},
                    new String[] {
                    "   ",
                    "---",
                    "   "},
                    new String[] {
                    "r-g",
                    "J L",
                    "   "},
                    new String[] {
                    "   ",
                    "g r",
                    "L-J"},
                    new String[] {
                    "rg ",
                    "JL-",
                    "   "},
                    new String[] {
                    " rg",
                    "-JL",
                    "   "},
                    new String[] {
                    "   ",
                    "gr-",
                    "LJ "},
                    new String[] {
                    "   ",
                    "-gr",
                    " LJ"}
                    );
        } else if (c == '|') {
            return Arrays.asList(
                    new String[] {
                    " Lg",
                    "r-J",
                    "Lg "},
                    new String[] {
                    "rJ ",
                    "L-g",
                    " rJ"},
                    new String[] {
                    " | ",
                    " | ",
                    " | "},
                    new String[] {
                    " Lg",
                    "  |",
                    " rJ"},
                    new String[] {
                    "rJ ",
                    "|  ",
                    "Lg "},
                    new String[] {
                    " Lg",
                    " rJ",
                    " | "},
                    new String[] {
                    " | ",
                    " Lg",
                    " rJ"},
                    new String[] {
                    "rJ ",
                    "Lg ",
                    " | "},
                    new String[] {
                    " | ",
                    "rJ ",
                    "Lg "}
                    );
        } else {
            List<String []> ret = new ArrayList<String []>();
            ret.add(
                    new String[] {
                    "   ",
                    "   ",
                    "   "});
            return ret;
        }

    }
}

```
> 22 votes

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


title: PNG Pixel Forces

text:
# Question
Title: PNG Pixel Forces
**Challenge**

A Pixel World is a PNG image where gravitational, electromagnetic, and nuclear forces no longer exist. Special forces known as "pixel forces" are all that remain. We define this force as

> Fp-\>q = a * (p * q) / (r * r) * r̂

* `F` is the pixel force that `p` exerts on `q`
* `a` is Adams' constant, defined as `a = 4.2 * 10 ^ 1`
* `p` and `q` are charges on two pixels
* `r` is the distance from `p` to `q`
* is the direction of r in radians, measured counterclockwise\* from the positive x-axis

\*There are infinitely many acceptable values for any given direction. For example, 6.28, 0, -6.28, and -12.57 radians are all equivalent, and would all be accepted.

Three types of pixels exist:

* A red pixel holds a charge of positive one
* A black pixel holds a charge of negative one
* A white pixel holds a charge of zero

The bottom left pixel of pixel world is located at `(0, 0)`. The positive y axis falls up the page, and the positive x axis falls to the right. The total force on a pixel is simply the vector sum of all forces exerted upon that pixel. Like charges repel, and opposite charges attract.

Given a file path to a Pixel World, as well as two integers `x` and `y`, output the total force exerted on the pixel at location `(x, y)` in the format `<magnitude>\n<direction>`. Output must be accurate to at least 2 decimal places, but you may output more if you want. Direction must be output in radians. The integers `x` and `y` are guaranteed to be within the world boundary.

**Deliverables**

You must include a program, and a command that can be used to run your program. Two examples:

> python AbsolutelyPositive.py "C:\Pixtona.png" 50 40
> java UltimateAttraction "C:\Jupix.png" 30 30

**Example Image**

In the image below, there is a black pixel at `(100, 104)`.

> Pixars.png

**Example Output**

This output does *not* correspond to the above input.

> 534.19721014
> 4.32605416

**Need help getting started?**

I wrote some example code here. I haven't tested it, so use it at your own risk.

# Answer
> 2 votes
## Python - 355

```
import sys,Image,math as m
i=Image.open(sys.argv[1])
w,h=i.size
a=i.load()
X,Y=map(int,sys.argv[2:])
t=m.atan2
c=lambda i,j:2*(a[i,j][0]>200)-(a[i,j][1]>200)-1
p=c(X,h-1-Y)
V=H=0
for j in range(h):
 for i in range(w):q=c(i,h-1-j);y=Y-j;x=X-i;r=x*x+y*y;f=r and 42.*p*q/r;V+=m.cos(t(x,y))*f;H+=m.sin(t(x,y))*f
d=t(V,H)
print(V**2+H**2)**.5,[d,m.pi*2+d][d<0]

```

**Ungolfed**

```
import sys
import Image
import math as m

X,Y=map(int,sys.argv[2:]) # The X and Y coordinates of the test pixel

i=Image.open(sys.argv[1]) # Open the image
w,h=i.size # Get the width and height of the image
a=i.load() # Get a pixel access object of the image
V=0 # V = vector sum of Vertical Forces
H=0 # H = vector sum of Horizontal Forces

# Function to calculate the charge of the a pixel at x=i, y=j
def c(i,j):
    global a
    if a[i,j][0]>200: # If Red > 200
        if a[i,j][2]>200: # If Green > 200
            return 0 # We assume that pixel is White
        else:
            return 1 # We assume that pixel is Red
    return -1 # Else, we asusme that pixel is Black

p=c(X,h-1-Y) # Assign the charge of the test pixel to p

for j in range(h): # For every y value...
    for i in range(w): # For every x value...
        q=c(i,h-1-j) # Assign the charge of the current pixel to q
        y=Y-j # The y distance of the test pixel from the current pixel
        x=X-i # The x distance of the test pixel from the current pixel
        rSquared=x*x+y*y # The r-squared distance between the 2 pixels
        f=rSquared and 42.*p*q/rSquared # If rSquared is > 0, calculate the force.
                                        # Otherwise, the force is zero
        V+=m.cos(m.atan2(x,y))*f # Add the Y component of the force to V
        H+=m.sin(m.atan2(x,y))*f # Add the X component of the force to H

d=m.atan2(V,H)
print(V**2+H**2)**.5,[d,m.pi*2+d][d<0]

```

**Some little program used to create tests:**

```
import Image
width  = 100 # Define your own image width
height = 100 # Define your own image height
image = Image.new("RGB", (width, height), "white")
pixels = image.load()
blacks = [(0,0), (1,1)] # Define your own black pixels
reds   = [(0,1), (1,0)] # Define your own red pixels
for x,y in blacks:
    pixels[x,height-1-y] = (0,0,0)
for x,y in reds:
    pixels[x,height-1-y] = (255,0,0)
image.save("y.png") # Save image

```

**Sample tests:**

```
Users-MacBook-Air:pngforces User$ python z3.py y.png 0 0
59.3969696197 0.785398163397

```

```
Users-MacBook-Air:pngforces User$ python z3.py y.png 50 50
0.0084 3.92699081699

```

```
Users-MacBook-Air:pngforces User$ python z3.py y.png 50 50
0.0084 0.785398163397

```

Just posting first... If there are any mistakes or issues, drop a comment down below, but will probably take quite some time to respond cuz I am really busy with other stuff.

---
Tags: code-golf
---


title: A Decent Decade

text:
# Question
Title: A Decent Decade
This is a short one:

> Only once in American history has there been a decade in which four of the years were prime numbers.

Your program has to output the decade after 1776 where four its years were primes. This is code golf so the shortest code wins.

The output must be like so:

```
1710s

```

or

```
1980s

```

***Note:*** The answer must be calculated and not explicitly hardcoded into your program.

# Answer
# CJam, 24 bytes

```
1770{A+_A,f+{mp},,4<}g's

```

At the cost of two extra bytes, this program can be modified to calculate the first decade containing four prime years after (not containing) a user-defined year:

```
liA/A*{A+_A,f+{mp},,4<}g's

```

### Example runs

```
$ cjam <(echo "1770{A+_A,f+{mp},,4<}g's"); echo
1870s
$ cjam <(echo "liA/A*{A+_A,f+{mp},,4<}g's") <<< 1776; echo
1870s
$ cjam <(echo "liA/A*{A+_A,f+{mp},,4<}g's") <<< 1870; echo
2080s
$ cjam <(echo "liA/A*{A+_A,f+{mp},,4<}g's") <<< 2080; echo
3250s
$ cjam <(echo "liA/A*{A+_A,f+{mp},,4<}g's") <<< 3250; echo
3460s

```

### How it works

```
li                          " Read an integer “Y” from STDIN.                 ";
  A/A*                      " Execute “Y = Y / 10 * 10”.                      ";
      {             4<}g    " While the result of the loop is less than four: ";
       A+                   " Execute  “Y += 10”.                             ";
         _A,f+              " Push [ Y Y+1 Y+2 Y+3 Y+4 Y+5 Y+6 Y+7 Y+8 Y+9 ]. ";
              {mp},,        " Compute the number of primes in that range.     ";
                        's  " Push 's'.                                       ";

```
> 4 votes

# Answer
# Python - ~~105 103~~ 87

Iterating over `i`th primes using `sympy`'s `prime` function:

```
import sympy
p=sympy.prime
for i in range(275,305):
 if p(i)>p(i+3)-9:print`p(i)-1`+'s'

```

**Alternative solution** iterating over years from 1780 to 2010 and counting primes per decade:

```
r=range
for d in r(1780,2010,10):
 if sum(all([y%i>0for i in r(2,y)])for y in r(d,d+10))>3:print`d`+'s'

```
> 1 votes

---
Tags: code-golf
---


title: Find the maximum operation

text:
# Question
Title: Find the maximum operation
The challenge is to find the maximum number you can get from a list of integer using basic arithmetic operators (addition, substraction, multiplication, unary negation)

**Input**

A list of integers

**Output**

The maximum result **using every integer** in the intput.

The input order doesn't matter, result should be the same.

You do not need to output the full operation, just the result.

**Examples**

```
Input : 3 0 1
Output : 4 (3 + 1 + 0)

Input : 3 1 1 2 2
Output : 27 ((2+1)*(2+1)*3))

Input : -1 5 0 6
Output : 36 (6 * (5 - (-1)) +0)

Input : -10 -10 -10
Output : 1000 -((-10) * (-10) * (-10))

Input : 1 1 1 1 1
Output : 6 ((1+1+1)*(1+1))

```

**Rules**

* Shortest code wins
* Standard "loopholes" apply
* You may only use + * - operators (addition, multiplication, substraction, unary negation)
* The code should work as long as the result can be stored on a 32 bit Integer.
* Any overflow behaviour is up to you.

I hope this is clear enough, this is my first Code Golf challenge suggestion.

# Answer
# C - 224 bytes - Running time O(n)

```
o=0,w=0,n[55],t,*m=n,*p=n;main(r){for(;scanf("%d",++p);t<3?--p,w+=t/2,o+=t&1:t<*m|m==n?m=p:9)t=*p=abs(*p);t=o<w?o:w;o-=t;w-=t;t+=o/3;for(o%3?o%3-2?t?t--,w+=2:++*m:w++:9;t--;)r*=3;for(r<<=w;--p>n;)r*=*p;printf("%d",r>1?r:o);}

```

It was amusing to see only exponential-time solutions for a linear-time problem, but I suppose it was the logical way to proceed since there were no bonus points for actually having an algorithm, which is an anagram of logarithm.

After converting negative numbers to positive and discarding zeroes, clearly we are mostly interested in multiplication. We want to maximize the logarithm of the final number.

log(a + b) \< log(a) + log(b) except when a = 1 or b = 1, so ones are the only case in which we are interested in adding anything together. In general it is better to add a 1 to a smaller number, because that causes a bigger increase in logarithm, i.e. a larger percentage increase, than adding 1 to a big number. There are four possible scenarios, ordered most to least preferable, for utilizing ones:

1. Adding one to a 2 gives +log .405 \[log(3) - log(2)\]
2. Combining ones into threes gives +log .366 per one \[log(3) / 3\]
3. Making a 2 out of ones gives +log .347 per one \[log(2) / 2\]
4. Adding one to a number 3 or higher gives +log .288 or less \[log(4) - log(3)\]

The program keeps track of the number of ones, the number of twos, and the minimum number greater than 2, and goes down the list of the most to least preferable ways of using the ones. Finally, it multiplies all the remaining numbers.
> 9 votes

# Answer
# Haskell, 126 characters

this is just brute-forcing, with the exception of ignoring the sign of the input and ignoring subtraction and unary negation.

```
import Data.List
f[x]=abs x::Int
f l=maximum$subsequences l\\[[],l]>>= \p->[f p+f(l\\p),f p*f(l\\p)]
main=interact$show.f.read

```

this code is extremely slow. the code recursively calculates f on each subsequence of the input **four times** <sub>(except for \[\] and the input itself)</sub>. but hey, it's code golf.
> 6 votes

# Answer
# SWI-Prolog - 250

Oh boy, I spent way too long on this.

```
o(A,B,A+B).
o(A,B,A-B).
o(A,B,A*B).
t([],0).
t([A,B|T],D):-t(T,Q),o(A,B,C),o(C,Q,D).
t([A|T],C):-t(T,Q),o(A,Q,C).
a(A):-t(A,B),n(C),B>C,retract(n(C)),assert(n(B)).
m(A):-assert(n(0)),\+p(A),n(R),R2 is R,write(R2).
p(A):-permutation([0|A],B),a(B),0=1.

```

Called from command line (e.g.):

```
> swipl -s filename.pl -g "m([1, 1, 1, 1, 1])" -t halt
6

```

*(For no particlar reason, I found it awesome that my golfed function names spell "tomato pot.")*

**Ungolfed version:**

```
% Possible operations
operation(Left, Right, Left + Right).
operation(Left, Right, Left - Right).
operation(Left, Right, Left * Right).

% Possible ways to transform
transform([], 0).
transform([A, B|T], D) :- transform(T, Q), operation(A, B, C), operation(C, Q, D).
transform([A|T], C) :- transform(T, Q), operation(A, Q, C).

% Throw the given array through every possible transformation and update the max
all_transforms(A) :- transform(A, B), n(C), B>C, retract(n(C)), assert(n(B)).

% Find all the permutations and transformations, then fail and continue execution.
prog(A) :- assert(n(0)), !, permutation([0|A], B), all_transforms(B), fail.

% End the program
finished :- n(R), write(R), nl, R2 is R, write(R2), nl.

% Run the program
main(A) :- ignore(prog(A)), finished.

```

**Explanation:**

1. Take in an array as an argument.
2. Get all permutations of the array.
3. Find some arrangement of operators to add to the array. (This is done via dynamic programming, seeing whether it's better if we combine the first two elements or not.)
4. Check this against our current max value. If it's better, replace it.
5. Tell the program we failed so that it keeps checking, but then negate that (using `ignore` or `\+`) to let the predicate overall return `true` and continue.
6. We're given a string of predicates, instead of a number, so assign it using `is` and then write it.
> 5 votes

# Answer
# Scala, 134

```
print(args.map(Math abs _.toInt)./:(Seq(Array(0)))((l,a)=>l.map(a+:_)++l.flatMap(_.permutations.map{r=>r(0)+=a;r}))map(_.product)max)

```

Ungolfed & commented:

```
print(
  args
    .map(Math abs _.toInt)                     // to int, ignoring -
    .foldLeft(Seq(Array(0))){ (list,num) =>    // build up a list of sums of numbers
      list.map(num+:_) ++                      // either add the new number to the list
      list.flatMap(_.permutations.map{ copy =>
        copy(0)+=num                           // or add it to one of the elements
        copy
      })
    }
    .map(_.product) // take the maximum of the the products-of-sums
    .max
)

```

A slightly different approach, from realizing that the biggest answer can always be expressed as a product of sums.

So close, but a bunch of library stupidity (permutations returns an Iterator instead of a Seq, horrible type inference on empty sequences, Array.update returning Unit) did me in.
> 4 votes

# Answer
# Haskell - 295 290 265 246 203 189 182 bytes

---

Finally works! Also now it is a brute force rather than a dynamic solution.

---

Thanks to proudhaskeller for some of the golfing tips.

This is probably **not** a fully golfed solution because I actually suck at golfing, but it is the best I can come up with (and it looks complicated, so I got that going for me):

```
import Data.List
main=interact$show.g.read
g x=maximum[product$a#b|a<-sequence$replicate(length x-1)[0,1],b<-permutations x]
(a:b)#(c:d:e)|a>0=b#(c+d:e)|0<1=c:b#(d:e)
_#x=x

```

New test cases:

```
[1,1,1,2,2]
12

[1,1,3,3,3]
54

[1,1,1,1,1,1,1,1,5,3]
270

```

Solution explanation:

The `main` function just gets an input and runs `g` with it.

`g` takes the input and returns the maximum of all possible combinations of sums and list orders.

`#` is the function which calculates the sums in a list like this:

```
a = [1,0,0,1]
b = [1,1,1,2,2]
a#b = [2,1,4]

```
> 3 votes

# Answer
## Python 278 (O(n!))

```
from itertools import*
def f(n):
 f,n,m=lambda n:[(n,)]+[(x,)+y for x in range(1,n)for y in f(n-x)],map(abs,map(int,n.split())),0
 for p,j in product(permutations(n),f(len(n))):
  i=iter(p)
  m=max(m,reduce(lambda e,p:e*p,(sum(zip(*zip([0]*e,i))[1])for e in j)))
 return m

```

## Explanation

1. Unary Negate should be judiciously used to convert all negative numbers to positive
2. Find all possible permutations of the numbers
3. Using Integer partition to find all power-sets of a given permutation
4. Find the product of the sums
5. Return the maximum of the product of the sums
> 3 votes

# Answer
## GolfScript (52 chars)

```
~]0-{abs}%.1-.1,or@,@,-,-1%{!\$.0=3<@+{()}1if+}/{*}*

```

Online demo

feersum's analysis is pretty good but it can be taken further if the goal is golfing rather than efficiency. In pseudo-code:

```
filter zeros from input and replace negatives with their absolute value
filter ones to get A[]
count the ones removed to get C
while (C > 0) {
    sort A
    if (A[0] < 3 || C == 1) A[0]++
    else A.append(1)
    C--
}
fold a multiply over A

```
> 1 votes

---
Tags: code-golf, math, arithmetic
---