title: Hungry Image Snake - Hole #3

text:
# Question
Title: Hungry Image Snake - Hole #3
Hole #1

Joe the snake is hungry.

He eats pictures, one pixel at a time.

He really likes bright pixels.

## The Challenge

Program Joe to eat the most bright pixels he can find, given that he can only move up, down, left or right.

## Specifications

* Joe must start at the upper left pixel of the image.
* Joe can only move horizontally or vertically by 1 each move
* Joe has only enough time to move 1/3 of the amount of pixels in the picture (1/3 as many moves as pixels). If the number of pixels is not a multiple of 3, round down to the nearest integer.
* Joe may cross his path, though that counts as 0 brightness
* Brightness is based on the sum of r,g and b, so rgb(0,0,0) has a brightness of 0 while rgb(255,255,255) has maximum brightness.

## Input

You may input the image however you like.

## Output

* an image showing the end result of your picture (with black being eaten pixels).
* The amount of brightness eaten (please specify what range in your answer)

## Scoring

Your program will be graded on:

* The average brightness of pixels Joe eats / The average brightness of the pixels in the picture\*

\*you may hardcode this in your program

Your total score will be the average of the scores for the following images:

Test images:

http://upload.wikimedia.org/wikipedia/en/thumb/f/f4/The\_Scream.jpg/800px-The\_Scream.jpg

# Answer
# C++, Score: ~~1.42042~~ 1.46766

This is essentially a slightly more sophisticated version of the two existing solutions: Of the four possible moves, it selects the one that maximizes brightness. However, instead of only looking at the brightness of the target pixel, it looks at the weighted sum of pixel-brightness in the neighborhood of the target pixel, where pixels closer to the target have a greater weight.

**EDIT:** Using nonlinear brightness in neighborhood calculation improves the score slightly.

Compile with `g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo`. Requires cairo.

Run with `joe <image-file> [<radius>]`. `<image-file>` is the input PNG image. `<radius>` (optional argument) is the radius of the summed-over neighborhood, in pixels (smaller is faster, larger is (roughly) better.) Outputs the score and an image named `out.<image-file>`.

```
#include <cairo/cairo.h>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

using namespace std;

int main(int argc, const char* argv[]) {
    auto* img = cairo_image_surface_create_from_png(argv[1]);
    int width = cairo_image_surface_get_width(img),
        height = cairo_image_surface_get_height(img),
        stride = cairo_image_surface_get_stride(img);
    unsigned char* data = cairo_image_surface_get_data(img);

    double* brightness = new double[width * height];
    double total_brightness = 0;
    for (int y = 0; y < height; ++y) {
        for (int x = 0; x < width; ++x) {
            const unsigned char* p = data + stride * y + 4 * x;
            total_brightness += brightness[y * width + x] = p[0] + p[1] + p[2];
        }
    }

    const int r = argc > 2 ? stoi(argv[2]) : 64, R = 2 * r + 1;
    double* weight = new double[R * R];
    for (int y = -r; y <= r; ++y) {
        for (int x = -r; x <= r; ++x)
            weight[R * (y + r) + (x + r)] = 1.0 / (x*x + y*y + 1);
    }

    auto neighborhood = [&] (int x, int y) {
        double b = 0;
        int x1 = max(x - r, 0), x2 = min(x + r, width - 1);
        int y1 = max(y - r, 0), y2 = min(y + r, height - 1);
        for (int v = y1; v <= y2; ++v) {
            const double *B = brightness + width * v + x1;
            const double *W = weight + R * (v - (y - r)) + (x1 - (x - r));
            for (int u = x1; u <= x2; ++u, ++B, ++W)
                b += (*W) * (*B) * (*B);
        }
        return b;
    };

    int n = (2 * width * height + 3) / 6;
    int x = 0, y = 0;
    double path_brightness = 0;
    int O[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int i = 0; i < n; ++i) {
        if (i % 1000 == 0) cerr << (200 * i + n) / (2 * n) << "%\r";

        path_brightness += brightness[width * y + x]; brightness[width * y + x] = 0;
        unsigned char* p = data + stride * y + 4 * x;
        p[0] = p[1] = 16 * i % 255; p[2] = 0;

        auto O_end = partition(begin(O), end(O), [&] (const int* o) {
            return x + o[0] >= 0 && x + o[0] < width &&
                   y + o[1] >= 0 && y + o[1] < height;
        });
        const int* o_max; double o_max_neighborhood = -1;
        for (auto o = O; o != O_end; ++o) {
            double o_neighborhood = neighborhood(x + (*o)[0], y + (*o)[1]);
            if (o_neighborhood > o_max_neighborhood)
                o_max = *o, o_max_neighborhood = o_neighborhood;
        }
        x += o_max[0]; y += o_max[1];
    }

    cout << (path_brightness * width * height) / (n * total_brightness) << endl;

    cairo_surface_write_to_png(img, (string("out.") + argv[1]).c_str());

    delete []brightness;
    delete []weight;
    cairo_surface_destroy(img);
}

```

## Results

```
Bridge    1.39945
Balls     1.77714
Scream    1.38349
Fractal   1.31727
Vortex    1.66493
Tornado   1.26366
-----------------
Average   1.46766

```

## More eye-candy
> 16 votes

# Answer
# Python 3, score = 1.57

First our snake travels the image creating vertical lines with equal distance from each other.

We can extend this snake by taking two points next to each other in a vertical line and creating a loop whose endpoints are them.

```
|      |
|  =>  +----+
|      +----+
|      |

```

We organize the points into pairs and for every pair we store the size and average brightness value of the loop which gives has the greatest average brightness.

At every step we choose the pair with highest value extend its loop to achieve maximum average brightness on the extension and calculate the new optimal loop size and brightness value for the pair.

We store the (value,size,point\_pair) triplets in a heap structure sorted by value so we can remove the biggest element (in O(1)) and add the new modified one (in O(log n)) efficiently.

We stop when we reachg the pixel count limit and that snake will be the final snake.

The distance between the vertical lines has very little effect in the results so a constant 40 pixel was choosen.

## Results

```
swirl    1.33084397946
chaos    1.76585674741
fractal  1.49085737611
bridge   1.42603926741
balls    1.92235115238
scream   1.48603818637
----------------------
average  1.57033111819

```

*Note: the original "The Scream" picture was not available so I used an other "The Scream" picture with similar resolution.*

Gif showing the snake extending process on the "swirl" image:

The code takes one (or more space separated) filename(s) from stdin and writes the resulting snake images to png files and prints the scores to stdout.

```
from PIL import Image
import numpy as np
import heapq as hq

def upd_sp(p,st):
    vs,c=0,0
    mv,mp=-1,0
    for i in range(st,gap):
        if p[1]+i<h:
            vs+=v[p[0],p[1]+i]+v[p[0]+1,p[1]+i]
            c+=2
            if vs/c>mv:
                mv=vs/c
                mp=i
    return (-mv,mp)

mrl=[]
bf=input().split()

for bfe in bf:
    mr,mg=0,0
    for gap in range(40,90,1500):

        im=Image.open(bfe)
        im_d=np.asarray(im).astype(int)

        v=im_d[:,:,0]+im_d[:,:,1]+im_d[:,:,2]

        w,h=v.shape

        fp=[]
        sp=[]
        x,y=0,0
        d=1

        go=True
        while go:
            if 0<=x+2*d<w:
                fp+=[(x,y)]
                fp+=[(x+d,y)]
                sp+=[(x-(d<0),y)]
                x+=2*d
                continue
            if y+gap<h:
                for k in range(gap):
                    fp+=[(x,y+k)]
                y+=gap
                d=-d
                continue
            go=False

        sh=[]
        px=im.load()

        pl=[]

        for p in fp:
            pl+=[v[p[0],p[1]]]
            px[p[1],p[0]]=(0,127,0)

        for p in sp:
            mv,mp=upd_sp(p,1)
            if mv<=0:
                hq.heappush(sh,(mv,1,mp+1,p))

        empty=False
        pleft=h*w//3
        pleft-=len(fp)
        while pleft>gap*2 and not empty:

            if len(sh)>0:
                es,eb,ee,p=hq.heappop(sh)
            else:
                empty=True
            pleft-=(ee-eb)*2

            mv,mp=upd_sp(p,ee)
            if mv<=0:
                hq.heappush(sh,(mv,ee,mp+1,p))

            for o in range(eb,ee):
                pl+=[v[p[0],p[1]+o]]
                pl+=[v[p[0]+1,p[1]+o]]
                px[p[1]+o,p[0]]=(0,127,0)
                px[p[1]+o,p[0]+1]=(0,127,0)

        pl+=[0]*pleft

        sb=sum(pl)/len(pl)
        ob=np.sum(v)/(h*w)

        im.save(bfe[:-4]+'snaked.png')

        if sb/ob>mr:
            mr=sb/ob
            mg=gap

    print(bfe,mr)
    mrl+=[mr]

print(sum(mrl)/len(mrl))

```
> 7 votes

# Answer
# Python 2 (score: 0.0797116)

Just a very simple and naïve greedy algorithm to get the ball rolling.

```
#!/usr/bin/python

from PIL import Image

OFFSETS = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def test_img(filename):
    img = Image.open(filename)

    joe, eaten = (0, 0), []
    img_w, img_h = img.size
    all_pixels = [
        sum(img.getpixel((x, y)))
        for x in xrange(img_w)
        for y in xrange(img_h)
    ]
    total_brightness = float(sum(all_pixels)) / len(all_pixels)

    for _ in xrange(0, (img_w*img_h)/3):
        max_offset, max_brightness = (0, 0), 0
        for o in OFFSETS:
            try:
                brightness = sum(img.getpixel((joe[0] + o[0], joe[1] + o[1])))
            except IndexError:
                brightness = -1
            if brightness >= max_brightness:
                max_offset = o
                max_brightness = brightness

        joe = (joe[0] + max_offset[0], joe[1] + max_offset[1])
        eaten.append(max_brightness)
        img.putpixel(joe, (0, 0, 0))

    eaten_brightness = float(sum(eaten)) / len(eaten)
    print('%d of %d (score %f)' % (eaten_brightness, total_brightness, eaten_brightness / total_brightness))
    img.show()

test_img('img0.jpg')
test_img('img1.png')
test_img('img2.jpg')
test_img('img3.jpg')
test_img('img4.jpg')

```

Output:

```
llama@llama:~/Code/python/ppcg40069hungrysnake$ ./hungrysnake.py
15 of 260 (score 0.060699)
9 of 132 (score 0.074200)
16 of 300 (score 0.055557)
4 of 369 (score 0.010836)
79 of 400 (score 0.197266)

```
> 5 votes

# Answer
## Java (score: 0.6949)

A simple algorithm which eats the brightest pixel out of the four pixels surrounding the current pixel. In the case of a tie, the pixel eaten is random, leading to differing scores and resulting images each execution. As such, the scores below are the averages over 50 executions on each image.

To run it, either edit the three arguments (existing as class constants) in the source, or pass them via command line in the form `java HungryImageSnake <source> <iterations> <printScores>` where `<source>` is the source file of the image to eat, `<iterations>` is the number of times to eat the image (taking the average score and saving the best score over all iterations), and `<printScores>` is true to print each iteration's score or false to not.

```
import javax.imageio.ImageIO;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

public class HungryImageSnake {

    private static final String SOURCE = "tornado.jpg";
    private static final int ITERATIONS = 50;
    private static final boolean PRINT_SCORES = true;

    public static void main(String[] args) {
        try {
            String source = args.length > 0 ? args[0] : SOURCE;
            int iterations = args.length > 1 ? Integer.parseInt(args[1]) : ITERATIONS;
            boolean printScores = args.length > 2 ? Boolean.parseBoolean(args[2]) : PRINT_SCORES;

            System.out.printf("Reading '%s'...%n", source);
            System.out.printf("Performing %d meals...%n", iterations);
            BufferedImage image = ImageIO.read(new File(source));
            double totalScore = 0;
            double bestScore = 0;
            BufferedImage bestImage = null;
            for (int i = 0; i < iterations; i++) {
                HungryImageSnake snake = new HungryImageSnake(image);
                while (snake.isHungry()) {
                    snake.eat();
                }
                double score = snake.getScore();
                if (printScores) {
                    System.out.printf("    %d: score of %.4f%n", i + 1, score);
                }
                totalScore += score;
                if (bestImage == null || score > bestScore) {
                    bestScore = score;
                    bestImage = snake.getImage();
                }
            }
            System.out.printf("Average score: %.4f%n", totalScore / iterations);
            String formattedScore = String.format("%.4f", bestScore);
            String output = source.replaceFirst("^(.*?)(\\.[^.]+)?$", "$1-b" + formattedScore + "$2");
            ImageIO.write(bestImage, source.substring(source.lastIndexOf('.') + 1), new File(output));
            System.out.printf("Wrote best image (score: %s) to '%s'.%n", bestScore, output);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private int x;
    private int y;
    private int movesLeft;
    private int maximumMoves;
    private double eatenAverageBrightness;
    private double originalAverageBrightness;
    private BufferedImage image;

    public HungryImageSnake(BufferedImage image) {
        this.image = copyImage(image);
        int size = image.getWidth() * image.getHeight();
        this.maximumMoves = size / 3;
        this.movesLeft = this.maximumMoves;
        int totalBrightness = 0;
        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                totalBrightness += getBrightnessAt(x, y);
            }
        }
        this.originalAverageBrightness = totalBrightness / (double) size;
    }

    public BufferedImage getImage() {
        return image;
    }

    public double getEatenAverageBrightness() {
        return eatenAverageBrightness;
    }

    public double getOriginalAverageBrightness() {
        return originalAverageBrightness;
    }

    public double getScore() {
        return eatenAverageBrightness / originalAverageBrightness;
    }

    public boolean isHungry() {
        return movesLeft > 0;
    }

    public void eat() {
        if (!isHungry()) {
            return;
        }
        int[][] options = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        shuffleArray(options); // prevent snake from getting stuck in corners
        int[] bestOption = null;
        int bestBrightness = 0;
        for (int[] option : options) {
            int optionX = this.x + option[0];
            int optionY = this.y + option[1];
            if (exists(optionX, optionY)) {
                int brightness = getBrightnessAt(optionX, optionY);
                if (bestOption == null || brightness > bestBrightness) {
                    bestOption = new int[]{ optionX, optionY };
                    bestBrightness = brightness;
                }
            }
        }

        image.setRGB(bestOption[0], bestOption[1], 0);
        this.movesLeft--;
        this.x = bestOption[0];
        this.y = bestOption[1];
        this.eatenAverageBrightness += bestBrightness / (double) maximumMoves;
    }

    private boolean exists(int x, int y) {
        return x >= 0 && x < image.getWidth() && y >= 0 && y < image.getHeight();
    }

    private int getBrightnessAt(int x, int y) {
        int rgb = image.getRGB(x, y);
        int r = (rgb >> 16) & 0xFF;
        int g = (rgb >> 8) & 0xFF;
        int b = rgb & 0xFF;
        return r + g + b;
    }

    private static <T> void shuffleArray(T[] array) {
        Random random = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            T temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    private static BufferedImage copyImage(BufferedImage source){
        BufferedImage b = new BufferedImage(source.getWidth(), source.getHeight(), source.getType());
        Graphics g = b.getGraphics();
        g.drawImage(source, 0, 0, null);
        g.dispose();
        return b;
    }
}

```

Average scores, by image, over fifty iterations:

```
Bridge - 0.7739
Spheres - 0.5580
Scream - 0.8197
Fractal - 0.3850
Vortex - 0.9158
Tornado - 0.7172

```

Best scores, by image, over the same fifty iterations:

```
Bridge - 0.8996
Spheres - 0.8741
Scream - 0.9183
Fractal - 0.5720
Vortex - 1.1520
Tornado - 0.9281

```

The highest scoring runs' images:

As is evident from the images, far less than a third of the pixels are actually eaten, as the snake occasionally gets stuck among pixels it has already eaten, at which it remains stuck within the dead area until the randomness of its movements bring it to an edible portion of the image.

Also as a result of the snake re-eating pixels, the scores are biased downward, as the zero-brightness of the dead pixels is again factored into the average. I would expect to see far higher scores if the scoring algorithm was modified to only divide by the number of moves that led to eating new pixels, rather than all moves (including those where the snake eats a now-dead pixel that it has eaten before).

Of course, a better approach would be to create some sort of brightness heuristic for each pixel and find the path of `width * height / 3` pixels with the highest average brightness, but I doubt this approach will be optimal in run time, especially on larger images, as the number of possible permutations would be very large. I may take a shot at some form of this approach later and post it in a separate answer if so.
> 5 votes

# Answer
# Python 2, Score: 1.205

I put together a quick Python solution some time ago but forgot to post it. Here it is. It finds the richest blocks in the image, then travels to each block, eating all the best blocks it comes to.

### Results

```
bridge.jpg: 591.97866/515.41501 =                               1.14855
BallsRender.png: 493.24711/387.80635 =                          1.27189
Mandel_zoom_04_seehorse_tail.jpg: 792.23990/624.60579 =         1.26838
Red_Vortex_Apophysis_Fractal_Flame.jpg: 368.26121/323.08463 =   1.13983
The_Scream.jpg: 687.18565/555.05221 =                           1.23806
swirl.jpg: 762.89469/655.73767 =                                1.16341

AVERAGE                                                         1.205

```

### Example Picture

### Python 2.7 Code

```
from pygame.locals import *
import pygame, sys, random

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
pic = pygame.image.load(fn)
pic.convert()
W,H = pic.get_size()
enough = W*H/3
screen.blit(pic, (0,0))

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

def look(p):
    x,y = p
    if 0 <= x < W and 0 <= y < H:
        return sum(pic.get_at(p))
    else:
        return -1

# index picture
locs = [(x,y) for x in range(W) for y in range(H)]
grid = dict( (p,sum(pic.get_at(p))) for p in locs )
rank = sorted( grid.values() )
median = rank[ len(rank)/2 ]
dark = dict( (k,v) for k,v in grid if v < median )
good = dict( (k,v) for k,v in grid if v > median )
pictotal = sum(rank)
picavg = 1.0 * pictotal/(W*H)
print('Indexed')

# compute zone values:
block = 16
xblocks, yblocks = (W-1)/block, (H-1)/block
zones = dict( ((zx,zy),0) for zx in range(xblocks) for zy in range(yblocks) )
for x,y in locs:
    div = (x/block, y/block)
    if div in zones:
        colsum = sum( pic.get_at((x,y)) )
        zones[div] += colsum

# choose best zones:
zonelist = sorted( (v,k) for k,v in zones.items() )
cut = int(xblocks * yblocks * 0.33)
bestzones = dict( (k,v) for v,k in zonelist[-cut:] )

# make segment paths:
segdrop = [(0,1)] * (block-1)
segpass = [(1,0)] * block
segloop = [(0,-1)] * (block-1) + [(1,0)] + [(0,1)] * (block-1)
segeat = ( segloop+[(1,0)] ) * (block/2)
segshort = [(1,0)] * 2 + ( segloop+[(1,0)] ) * (block/2 - 1)

def segtopath(path, seg, xdir):
    for dx,dy in seg:
        x,y = path[-1]
        newloc = (x+dx*xdir, y+dy)
        path.append(newloc)

# design good path:
xdir = 1
path = [(0,0)]
segtopath(path, segdrop, xdir)
shortzone = True
while True:
    x,y = path[-1]
    zone = (x/block, y/block)
    if zone in bestzones:
        if shortzone:
            seg = segshort
        else:
            seg = segeat
    else:
        seg = segpass
    segtopath(path, seg, xdir)
    shortzone = False
    # check end of x block run:
    x,y = path[-1]
    zone = (x/block, y/block)
    if not ( 0 <= x < xblocks*block ):
        del path[-1]
        segtopath(path, segdrop, xdir)
        shortzone = True
        xdir = xdir * -1
    if len(path) > enough:
        break
print('Path Found')

# show path on picture:
loc = path.pop(0)
eaten = 1
joetotal = grid[loc]
i = 0
while eaten <= enough:
    loc = path[i]
    i += 1
    pic.set_at(loc, (0,0,0))
    joetotal += grid[loc]
    eaten += 1
    if i % 1000 == 0:
        screen.blit(pic, (0,0))
        pygame.display.flip()
        for event in pygame.event.get():
            if event.type == QUIT: sys.exit(0)

# save picture and wait:
screen.blit(pic, (0,0))
pygame.display.flip()
pygame.image.save(pic, 'output/'+fn)
joeavg = 1.0 * joetotal/eaten
print '%s: %7.5f/%7.5f = %7.5f' % (fn, joeavg, picavg, joeavg/picavg)
while True:
    for event in pygame.event.get():
        if event.type == QUIT: sys.exit(0)

```
> 4 votes

---
Tags: code-challenge, image-processing
---


title: Finding the Deadlock

text:
# Question
Title: Finding the Deadlock
# Finding the Deadlock

When programming a multithreading application one must take good care to avoid deadlocking the various threads when accessing shared resources. A deadlock occurs when a thread attempts to access a resource that's locked in another thread at the same time that the other thread is trying to access a resource locked by the first. This is the simple case, but it can get more complex with longer resource chains.

## The challenge

You should write a program or function that can detect a possible deadlock situation in a list of the resources accessed by each thread. This is code-golf, so shortest answer in bytes wins.

Every thread is started at the same time, but after that they can run at any combination of interleaving. If there are 2 threads with 4 actions each, it could be run as (where each number is an action taken by the thread with that id) `1,1,1,1,2,2,2,2`, `2,2,2,2,1,1,1,1`, `1,2,1,2,1,2,1,2`, `1,1,2,2,2,2,1,1`, or any other possible combination.

## Input

You will receive, via STDIN, function parameter, or closest alternative, a list of strings. Each string will be in the format `+a` `-b`. Every one of this strings represents the locking(`+`)/unlocking(`-`) of a resource by the thread. Between every thread will be a `---` separator. It is guaranteed that a thread won't try to lock a resource it already has locked, and that all threads will explicitly unlock all the resources they have locked before exiting. Following is an example to demonstrate:

```
+a    # Lock resource a
+b    # Lock resource b
-a    # Unlock resource a
-b    # Unlock resource b
---   # Thread separator
+b    # Lock resource b
-b    # Unlock resource b

```

## Output

The output shall be falsy if the input doesn't contain any deadlock possibility, and truthy if it contains a possible deadlock situation. For example:

* `true`
* `false`
* `1`
* `0`

are all valid outputs, but anything clearly defined as truthy/falsy will be accepted.

## Examples

```
+a
-a
---
+a
-a

```

Output: `false`

---

```
+a
+b
-b
-a
---
+b
+a
-a
-b

```

Output `true`

Deadlock when trying to acquire `b,a` respectively for threads `1,2`

---

```
+a
+b
-a
-b
---
+a
+b
-b
-a

```

Output `false`

---

```
+a
+b
-b
-a
---
+b
+c
-c
-b
---
+c
+a
-a
-c

```

Output: `true`

Deadlock in threads 1,2,3 when trying to acquire `b,c,a` respectively.

---

http://pastebin.com/vMYRZxtW

Output `false`

---

http://pastebin.com/V5MVgNgS

Output `true`

Deadlock in threads 1,2,3 when trying to aquire `b,d,a` respectively.

---

Of course this could get a lot more complex, with more threads, more resources for each one, and so on, but I believe these tests cover the basics.

## Bonus

Since it's very very sad when you find deadlock situations when writing a program, there is a -8 byte bonus to answers outputting `:(` and `:)` as truthy/falsy respectively.

# Answer
> 4 votes
# Python 2 - 227

Basically makes sure there are no loops of 'precedence'. For example in the second test, the first thread has a `a(b)` precedence and the second thread has a `b(a)` precedence.

I was thinking about rewriting this in Pyth as I think it would work well with all the itertools operations, but converting the regex will take some work so for now I'll post this and maybe try to convert it and post another answer later.

```
from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))

```

# Answer
> 5 votes
# Python - ~~586~~ ~~539~~ ~~524~~ ~~501~~ 485 bytes - 8 = 477

Indentation levels:

```
1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

```

--

```
import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'

```

---
Tags: code-golf, combinatorics, graph-theory, decision-problem, concurrency
---


title: Sum in each dimension

text:
# Question
Title: Sum in each dimension
You are given a multi-dimensional array of integers. Each dimension has a fixed size (so that it would be always rectangular if it is 2D). Your program should calculate the sums in each dimension and append the sums as the new last items in that dimension.

Assume the input and output arrays are A and B, and the size of dimension *i* of A is ni. B would have the same number of dimensions as A and the size of dimension *i* would be ni+1. Bj1,j2,...,jm is the sum of Ak1,k2,...,km where:

* ki = ji if ji \<= ni
* 0 \< ki \<= ni if ji = ni+1

For the input:

```
[[1 2 3]
 [4 5 6]]

```

Your program (or function) should output:

```
[[1 2 3 6]
 [4 5 6 15]
 [5 7 9 21]]

```

The input contains only the array. The total number of dimensions and the size of each dimension are **not** given in the input. (But you can get them from the array by your own code.) You can use any convenient list formats in your language, as long as it doesn't specify the number of dimensions or dimension sizes directly.

The input has at least 1 dimension, and has at least 1 item in the array.

This is code-golf. Shortest code wins.

## Test cases

```
Input:
[5 2 3]
Output:
[5 2 3 10]

Input:
[[1 2 3] [4 5 6]]
Outputs:
[[1 2 3 6] [4 5 6 15] [5 7 9 21]]

Input:
[[[1] [1] [1] [0]]]
Output:
[[[1 1] [1 1] [1 1] [0 0] [3 3]] [[1 1] [1 1] [1 1] [0 0] [3 3]]]

Input:
[[[[-1]]]]
Output:
[[[[-1 -1] [-1 -1]] [[-1 -1] [-1 -1]]] [[[-1 -1] [-1 -1]] [[-1 -1] [-1 -1]]]]

```

# Answer
> 9 votes
# J, 14 bytes

```
#@$(0|:],+/^:)

```

Usage:

```
   ]a=.i.2 3
0 1 2
3 4 5

   (#@$(0|:],+/^:)) a    NB. parens are optional
0 1 2  3
3 4 5 12
3 5 7 15

```

The function is equivalent to the following `(0|:],+/)^:(#@$)` but uses a user-defined adverb to save parens.

Explanation for the latter code from right to left:

* `^:(#@$)`repeat `^:` for the number `#` of dimensions `$`:

+ `],+/` concatenate `,` to the argument `]` with the sum of it on the last dimension `+/`
    + `0|:` rotate dimensions `|:` by putting the first one `0` to the end of the dimension-list
* After doing the above procedure we get back the original input with sums on all dimensions.

*For my older solution check revision history.*

Try it online here.

# Answer
> 14 votes
# Mathematica, ~~32~~ 20 bytes

```
#/.List->({##,+##}&)&

```

### Example:

```
In[1]:= #/.List->({##,+##}&)&[{{1, 2, 3}, {4, 5, 6}}]

Out[1]= {{1, 2, 3, 6}, {4, 5, 6, 15}, {5, 7, 9, 21}}

```

### Explanation:

The full form of `{{1, 2, 3}, {4, 5, 6}}` is `List[List[1, 2, 3], List[4, 5, 6]]`. Then replace all the `List`s in the expression with the function `({##,+##}&)`.

# Answer
> 10 votes
## Python 2, 95 bytes

```
from numpy import*
a=copy(input())
for d in r_[:a.ndim]:a=r_[`d`,a,sum(a,d,keepdims=1)]
print a

```

This iterates over each dimension, concatenating its sums using NumPy.

I stumbled across NumPy's `r_`, which is pretty awesome for golfing. `r_[:n]` is shorter than `range(n)` and much more powerful (e.g. `r_[:4, 7, 8, 10:100:10]`). It can also do other things like concatenation along an arbitrary axis.

Example usage:

```
$ python sum.py
[[1, 2, 3], [4, 5, 6]]
[[ 1  2  3  6]
 [ 4  5  6 15]
 [ 5  7  9 21]]

```

# Answer
> 7 votes
# APL, ~~16~~ 15 bytes

```
{×≡⍵:∇¨⍵,+/⍵⋄⍵}

```

*Thanks to @user23013 for golfing off 3 bytes and figuring out the proper input format.*

Verify the test cases online with TryAPL.

### Idea

The general idea is the same as in my CJam submission, for which APL allows a much shorter implementation. It consists of only two steps:

1. Sum the array across its outmost dimension.
2. Repeat step 1 for each subarray.

### Code

```
{             } ⍝ Define a monadic function with argument ⍵ and reference ∇.
 ×≡⍵:           ⍝ If the depth of ⍵ is positive:
     ∇          ⍝   Apply this function...
      ¨         ⍝   to each element of...
       ⍵,       ⍝   the concatenation of ⍵...
         +/⍵    ⍝   and the sum across ⍵.
            ⋄⍵  ⍝  Else, return ⍵.

```

# Answer
> 6 votes
# Pip, ~~18~~ 15 bytes

```
{a-a?fMaAE$+aa}

```

This is an anonymous function, which takes the array as an argument and returns the result. Sample invocation, using the `-p` flag to obtain readable output:

```
C:\> pip.py -pe "( {a-a?fMaAE$+aa} [[1 2 3] [4 5 6]] )"
[[1;2;3;6];[4;5;6;15];[5;7;9;21]]

```

The idea is basically the same as Dennis's APL, though independently derived. More specifically:

```
{             }  Define a lambda function with parameter a
 a-a?            Shortest way I could find to test whether the argument is a list
                 or scalar: subtracting a number from itself gives 0 (falsy);
                 subtracting a list from itself gives a list of zeros (truthy!)
     fM          If truthy, it's a list, so map the same function (f) recursively to:
       aAE         Argument, with appended element...
          $+a      ...sum of argument (fold on +)
             a   If falsy, it's a scalar, so just return it

```

This method works because `+` (along with many other operators) functions item-wise on lists in Pip--a feature inspired by array-programming languages like APL. So when you `$+` a list like `[[1 2 3] [4 5 6]]`, the result is `[5 7 9]` as desired. Also used in the list-or-scalar test: `[1 2 3] - [1 2 3]` gives `[0 0 0]`, which is truthy (as are all lists except the empty list).

Previous 18-byte version:

```
{Ja=a?a(fMaAE$+a)}

```

Changes:

1. Saved a byte on the scalar-or-list test--previous method was to join the argument (on empty string) and test whether equal to its un-joined self (works because `[1 2 3] != 123`);
2. Eliminated the parentheses. They're necessary in the original because `M` is lower precedence than `?` (though I'm probably going to change that, especially now): without them, the code would parse as `(Ja=a?af)M(aAE$+a)`, leading to bizarre error messages. However, the middle argument of a ternary operator can be *any* expression of whatever precedence, no parentheses needed. So by making the list the truthy case, I can save those two bytes.

# Answer
> 5 votes
# APL (25)

```
{N⊣{N,[⍵]←+/[⍵]N}¨⍳⍴⍴N←⍵}

```

APL's arrays have dimensions built-in, so this is a function that takes an *n*-dimensional array and then sums along each dimension.

```
      {N⊣{N,[⍵]←+/[⍵]N}¨⍳⍴⍴N←⍵} ↑(1 2 3)(4 5 6)
1 2 3  6
4 5 6 15
5 7 9 21

```

Explanation:

* `N←⍵`: store the array in `N`.
* `⍴⍴N`: get the amount of dimensions `N` has. ( gives the dimensions, i.e. `⍴↑(1 2 3)(4 5 6)` gives `2 3`, so `⍴⍴` gives the dimensions of the dimensions.)
* `{`...`}¨⍳`: for each number from 1 to `⍴⍴N`:
    + `+/[⍵]N`: sum `N` along dimension
    + `N,[⍵]←`: join the result to `N` in that dimension
* `N`: finally, return `N`.

# Answer
> 3 votes
# CJam, 36 bytes

```
{_`{'[<}#:D{_":"D'.e]'++~a+{S}%}&}:S

```

This is a recursive named function that pops an array from the stack and leaves one in return.

Try the test cases in the CJam interpreter.

### Idea

Sadly, CJam does not have some automagical operator that allows to add arbitrarily nested arrays, so we have to implement it ourselves. Luckily, it does that two infix operators, `:` (reduce) and `.` (vectorize), that will prove helpful for this task.

Step one is calculating the number of dimensions. This is easy: Convert the array into its string representation and count the number of leading **\[**'s.

Now, to reduce an array of one dimension, you usually just execute `:+`:

```
[1 2] :+ e# Pushes 3.

```

For an array of two dimensions, `+` would perform concatenation instead of addition, so we have to vectorize it:

```
[[1 2][3 4]] :.+ Pushes [4 6].

```

Now, for an array of three dimensions, `.+` would operate on arrays of two dimensions and perform, once again, concatenation. This time, we have to vectorize `.+`:

```
[[[1 2][3 4]][[5 6][7 8]]] :..+ e# Pushes [[[6 8] [10 12]]].

```

For the general case, an array of dimension **D**, we have to chain one `:`, **D - 1** `.`'s and one `+`.

Of course, this only sums the array only across its outmost dimension. We can solve this by defining a function **S** that computes the dimension (and does nothing if it's zero), performs the sum as indicated above and, finally, applies itself to the array's elements.

### Code

```
{                                }:S e# Define S:
 _`                                  e#   Push a string representation of a the array.
   {'[<}#                            e#   Find the index of the first non-bracket.
         :D                          e#   Save it in D.
           {                   }&    e#   If D is positive:
            _                        e#     Push a copy of the array.
             ":"D'.e]                e#     Pad ":" with "."s to a string of length D.
                     '++~            e#     Add a "+" to the string and evaluate.
                         a+          e#     Wrap the result in a array and concatenate.
                           {S}%      e#     Apply S to the elements of the array.

```

# Answer
> 2 votes
## Ruby (~~181~~ ~~139~~ ~~119~~ 108 bytes)

```
def d a;a.push a[0].to_s['[']?a.map{|x|d x}.transpose.map{|x|x.reduce:+}:a.reduce(:+)end
p d eval ARGF.read

```

Assumes input is passed as JSON.

# Answer
> 2 votes
# Java, 669 bytes

not gonna lie, I'm quite proud of myself for this one :p

```
import java.lang.reflect.Array;enum S{D;<A>A s(A a){int l=Array.getLength(a),x=0;Class t=a.getClass();Class c=t.getComponentType();A r=(A)Array.newInstance(c,l+1);System.arraycopy(a,0,r,0,l);if(t==int[].class)for(;x<l;)((int[])r)[l]=((int[])r)[l]+((int[])r)[x++];else{for(;x<l;)Array.set(r,x,S.this.s(Array.get(r,x++)));Object o=Array.get(r,0);for(;--x>0;)o=s(o,Array.get(r,x));Array.set(r,l,o);}return r;}<A>A s(A a,A b){int l=Array.getLength(a),x=0;Class t=a.getClass();A r=(A)Array.newInstance(t.getComponentType(),l);if(int[].class==t)for(;x<l;)((int[])r)[x]=((int[])a)[x]+((int[])b)[x++];else for(;x<l;)Array.set(r,x,s(Array.get(a,x),Array.get(b,x++)));return r;}}

```

expanded with testing:

```
import java.lang.reflect.Array;
import java.util.Arrays;

public enum SumOf{
    Dimensions;

    <A>A sum(A array){ //call this method to solve the challenge
        int length=Array.getLength(array),x=0;
        Class arrayType=array.getClass();
        Class componentType=arrayType.getComponentType();
        //grow the array to include the sum element
        A result=(A)Array.newInstance(componentType,length+1);
        System.arraycopy(array,0,result,0,length);
        if(arrayType==int[].class) //one-dimensional array needs to be handled separately
            for(;x<length;) //find the sum
                ((int[])result)[length]=((int[])result)[length]+((int[])result)[x++];
        else{ //multi-dimensional array
            for(;x<length;) //find the sum for each element in this dimension's array
                Array.set(result,x,sum(Array.get(result,x++)));
            //find the total sum for this dimension's array
            Object s=Array.get(result,0);
            for(;--x>0;)
                s=_sum(s,Array.get(result,x)); //add the 2 elements together
            Array.set(result,length,s);
        }
        return result;
    }

    <A>A _sum(A arrayA,A arrayB){ //this method is used by the previous method
        int length=Array.getLength(arrayA),x=0;
        Class arrayType=arrayA.getClass();
        A result=(A)Array.newInstance(arrayType.getComponentType(),length);
        if(int[].class==arrayType) //one-dimensional array needs to be handled separately
            for(;x<length;) //find the sum of both arrays
                ((int[])result)[x]=((int[])arrayA)[x]+((int[])arrayB)[x++];
        else
            for(;x<length;) //find the sum of both arrays
                Array.set(result,x,sum(Array.get(arrayA,x),Array.get(arrayB,x++)));
            return result;
        }

    static int[] intArray( int firstElement, int...array ) {
        if( array == null ) array = new int[0];
        array = Arrays.copyOf( array, array.length + 1 );
        System.arraycopy( array, 0, array, 1, array.length - 1 );
        array[0] = firstElement;
        return array;
    }

    static <E> E[] arrayArray( E firstElement, E...array ) {
        if( array == null ) array = (E[]) Array.newInstance( firstElement.getClass(), 0 );
        array = Arrays.copyOf( array, array.length + 1 );
        System.arraycopy( array, 0, array, 1, array.length - 1 );
        array[0] = firstElement;
        return array;
    }

    static void printIntArray( int[]array ){
        System.out.print("[ ");
        for( int x = 0; x < array.length; x++ )
            System.out.print( array[x] + " " );
        System.out.print("] ");
    }

    static < A > void printArray( A array ) {
        if( array.getClass() == int[].class ){
            printIntArray( (int[]) array );
        }
        else {
            System.out.print("[ ");
            int length = Array.getLength( array );
            for( int x = 0; x < length; x++ )
                printArray( Array.get( array, x ) );
            System.out.print("] ");
        }
    }

    public static void main(String[]s){
        int[] test01 = intArray( 5, 2, 3 );
        System.out.print("Input: ");
        printArray( test01 );
        System.out.print("\nOutput: ");
        printArray( SumOf.Dimensions.sum( test01 ) );
        System.out.println();

        int[][] test02 = arrayArray( intArray( 1, 2, 3 ), intArray( 4, 5, 6 ) );
        System.out.print("\nInput: ");
        printArray( test02 );
        System.out.print("\nOutput: ");
        printArray( SumOf.Dimensions.sum( test02 ) );
        System.out.println();

        int[][][] test03 = arrayArray( arrayArray( intArray( 1 ), intArray( 1 ), intArray( 1 ), intArray( 0 ) ) );
        System.out.print("\nInput: ");
        printArray( test03 );
        System.out.print("\nOutput: ");
        printArray( SumOf.Dimensions.sum( test03 ) );
        System.out.println();

        int[][][][] test04 = arrayArray( arrayArray( arrayArray( intArray( -1 ) ) ) );
        System.out.print("\nInput: ");
        printArray( test04 );
        System.out.print("\nOutput: ");
        printArray( SumOf.Dimensions.sum( test04 ) );
        System.out.println();

        int[][][] test05 = arrayArray( arrayArray( intArray( 1, 2, 3 ), intArray( 4, 5, 6 ), intArray( 7, 8, 9 ) ), arrayArray( intArray( 11, 12, 13 ), intArray( 14, 15, 16 ), intArray( 17, 18, 19 ) ), arrayArray( intArray( 21, 22, 23 ), intArray( 24, 25, 26 ), intArray( 27, 28, 29 ) ) );
        System.out.print("\nInput: ");
        printArray( test05 );
        System.out.print("\nOutput: ");
        printArray( SumOf.Dimensions.sum( test05 ) );
        System.out.println();
    }

}

```

running the expanded testing version prints this:

```
Input: [ 5 2 3 ]
Output: [ 5 2 3 10 ]

Input: [ [ 1 2 3 ] [ 4 5 6 ] ]
Output: [ [ 1 2 3 6 ] [ 4 5 6 15 ] [ 5 7 9 21 ] ]

Input: [ [ [ 1 ] [ 1 ] [ 1 ] [ 0 ] ] ]
Output: [ [ [ 1 1 ] [ 1 1 ] [ 1 1 ] [ 0 0 ] [ 3 3 ] ] [ [ 1 1 ] [ 1 1 ] [ 1 1 ] [ 0 0 ] [ 3 3 ] ] ]

Input: [ [ [ [ -1 ] ] ] ]
Output: [ [ [ [ -1 -1 ] [ -1 -1 ] ] [ [ -1 -1 ] [ -1 -1 ] ] ] [ [ [ -1 -1 ] [ -1 -1 ] ] [ [ -1 -1 ] [ -1 -1 ] ] ] ]

Input: [ [ [ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ] ] [ [ 11 12 13 ] [ 14 15 16 ] [ 17 18 19 ] ] [ [ 21 22 23 ] [ 24 25 26 ] [ 27 28 29 ] ] ]
Output: [ [ [ 1 2 3 6 ] [ 4 5 6 15 ] [ 7 8 9 24 ] [ 12 15 18 45 ] ] [ [ 11 12 13 36 ] [ 14 15 16 45 ] [ 17 18 19 54 ] [ 42 45 48 135 ] ] [ [ 21 22 23 66 ] [ 24 25 26 75 ] [ 27 28 29 84 ] [ 72 75 78 225 ] ] [ [ 33 36 39 108 ] [ 42 45 48 135 ] [ 51 54 57 162 ] [ 126 135 144 405 ] ] ]

```

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


title: It's election time!

text:
# Question
Title: It's election time!
# It's time... to count the votes!

Today there are local elections in my entire country. Here, the number of seats for each party is decided using the D'Hondt method. Your goal is to implement a program or function that will decide how many seats each party gets, in the shortest amount of bytes.

For this method there are a fixed number of seats to distribute, and it's done like so:

1. Every party is assigned a variable number, which starts at the number of votes it got.
2. Then the first seat is given to the party who has the biggest value in their variable and then that value for that party becomes their total number of votes divided by `1+seats`, rounded down, where `seats` is the number of seats it already has (so after getting the first, their votes are divided by 2, and by 3 after getting the second seat).
3. After that the parties votes are compared again. The process continues until all the seats have been assigned.

If the highest number is a tie between two or more parties, it is resolved randomly (It has to be random, it can't just be the first of the two in the list).

## Input

You will receive a number `N`, which will indicate the number of seats available, and a list of the votes each party received, in whatever format you prefer. Example:

```
25
12984,7716,13009,4045,1741,1013

```

## Output

You should output a list of the seats each party got. In the example above it would be something like

```
8,5,9,2,1,0

```

They should be in the same order as the parties in the input.

## Examples

```
5
3,6,1

outputs: 2,3,0

```

---

```
135
1116259,498124,524707,471681,359705,275007,126435

outputs: 45,20,21,19,14,11,5

```

## Bonus

**-20% bonus** if take the parties name as input and give them in the output, like for example:

```
25
cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013

outputs

cio:8
pcc:5
irc:9
icb:2
cub:1
bb:0

```

# Answer
# CJam, ~~35.2~~ ~~28.8~~ ~~28.0~~ 26.4

```
q2*~,m*mr{~)f/1=~}$<:(f{1$e=1\tp}

```

This full program is 33 bytes long and qualifies for the bonus.

Try it online in the CJam interpreter.

### Example run

```
$ cjam seats <<< '[["cio"12984]["pcc"7716]["irc"13009]["icb"4045]["cub"1741]["bb"1013]]25'
["cio" 8]
["pcc" 5]
["irc" 9]
["icb" 2]
["cub" 1]
["bb" 0]

```

### How it works

```
q2*~   e# Repeat the input from STDIN twice. Evaluate.
       e# STACK: Array seats Array seats
,      e# Range: seats -> [0 ... seats-1]
m*     e# Take the cartesian product of the array from the input and the range.
mr     e# Shuffle the array. This makes sure tie breakers are randomized.
{      e# Sort by the following key:
  ~    e#     Dump: [["party" votes] number] -> ["party" votes] number
  f/   e#     Divide each: ["party" votes] number -> ["party"/number votes/number]
  1=   e#     Select: ["party"/number votes/number] -> votes/number
  ~    e#     Bitwise NOT.
}$     e#
<      e# Keep only the elements that correspond to seats.
:(     e# Shift each array.
       e# RESULT: S := [[number] ["party" votes] [number] ["party" votes] ...]
f{     e# For each A := ["party" votes]:
       e#     Push S.
  1$   e#     Push a copy of A.
  e=   e#     Count the occurrences of A in S.
  1\t  e#     Replace the vote count with the number of occurrences.
  p    e#     Print.
}      e#

```
> 6 votes

# Answer
# Pyth, 36 bytes - 20% = 28.8

```
J<_hCo/@eCQhNheN.S*UQUvzvz.e,b/JkhCQ

```

This qualifies for the bonus.

Try it online: Demonstration or Test harness

### Explanation:

```
                                       implicit: z = 1st input (as string)
                                                 Q = 2nd input (evaluated)

                      vz               evaluate z (#seats)
                     U                 generate the list [0,1,...,seats-1]
                   UQ                  generate the list [0,1,...,len(Q)-1]
                  *                    Cartesian product of these lists
                .S                     shuffle (necessary for break ties randomly)
     o                                 order these tuples N by:
        eCQ                               list of votes
       @   hN                             take the N[0]th vote count
      /      heN                          and divide by N[1]+1
   hC                                  extract the party index of the tuples
  _                                    reverse the list
 <                      vz             take the first #seats elements
J                                      and store them in J

                          .e     hCQ   enumerated map over the names of the parties
                                       (k = index, b = name):
                            ,             generate the pair:
                             b/Jk            name, J.count(k)
                                       print implicitely

```
> 6 votes

# Answer
# Javascript, 210 bytes

```
v=(a,b,c,d,e,f,g)=>{d=Object.assign({},b),c={};for(g in b)c[g]=0;for(;a--;)e=0,f=Object.keys(d),f.forEach(a=>e=d[a]>e?d[a]:e),f=f.filter(a=>d[a]===e),f=f[~~(Math.random()*f.length)],d[f]=b[f]/-~++c[f];return c}

```

Notes:

* Requires a modern browser/engine with support for ES6. Tested in Firefox.
* Uses the very important `/-~++` operator :)

Example usage:

```
v(25, {cio:12984,pcc:7716,irc:13009,icb:4045,cub:1741,bb:1013})

```
> 5 votes

# Answer
# Pyth - 54 bytes

```
AGZQ=kZK*]0lZVGJhOfqeTh.MZZ.e(kb)Z XJK1 XZJ/@kJ+@KJ1;K

```

Input format (stdin):

```
[25,[12984,7716,13009,4045,1741,1013]]

```

Output format (stdout):

```
[8, 5, 9, 2, 1, 0]

```

Variables used:

```
G = total number of seats
K = array of seats currently assigned to each party
k = number of votes for each party
Z = k/(K+1)
J = which party should have the next seat

```
> 4 votes

# Answer
# Perl, 110

```
#!perl -pa
$n=pop@F;@x=map
0,@F;/a/,$x[$'/$n]++for(sort{$b-$a}map{map{($'/$_|0).rand.a.$i++}//..$n}@F)[0..$n-1];$_="@x"

```

Input space separated with the seat count last.

Try me.
> 2 votes

---
Tags: code-golf
---


# Question
Title: Write a self replicating program that stops replicating after "printing" "Hello world!" with the filenames
Write a self replicating program, in the source code filename `H.*`, contianed in an empty folder then manually compile and run or just run the program if your chosen language is dynamic, and it should then just create a new source file, `e.*`, with the same exact source code, and automatically compile/run that new program, which makes the new source file `l.*`, etc. until the source file `!.*` is made, and that program should do essentially nothing once it is compiled/run. "Hello world!" has some repeated characters, so the second character should be created by a similar filename, just with a new `<space>` at the end. Programs that just make/compile source files from the single instance of the program are invalid, and yes, " " is a valid filename. It should appear to say "Hello World!" when viewed in the file explorer sorted by time created.

---

For example, if you were to attempt this challenge in python, than you would create the source file `H.py`, which complies and runs `e.py`, which then itself creates `l.py`, that file `l .py`, `o.py`, `.py`, `w.py`, `o .py`, `r.py`, `l .py` and `d.py` which finally creates and runs `!.py`, which does not do anything once run.

# Answer
> 2 votes
# Python 2, 194

```
import os,sys
h,A='H|e|l|l |o| |w|o |r|l  |d|!'.split('|'),sys.argv[0]
d,a,F=dict(zip(h,h[1:])),A.split('.')[0],file
if a in d:o=d[a]+'.py';F(o,'w').write(F(A).read());os.popen('python "'+o+'"')

```

# Answer
> 0 votes
# Bash, ~~99~~ ~~88~~ 84

```
X=`grep -Po "(?<=#$0#)[^#]*" "$0"` #H#e#l#l #o# #W#o #r#l  #d#!
cp "$0" "$X"
sh "$X"

```

## Explanation:

1. First we create a regex from the name of the file (the argument `$0`). For example, here is the regex constructed when the first file executes (`$0` is `H`):

```
 (?<=#H#)[^#]*

```

This searches for a sequence of non-`#` characters preceded by `#H#`. That is, it finds the next filename in a sequence of `#`-separated filenames. (I used `#` so that the separator before `H` would function as the string delimiter itself, with the bonus of not needing a closing delimiter.)
2. Then we search (`grep`) the currently-executing file `"$0"` with this regex. We need the `-P` flag (or similar) to use the lookbehind construct, and `-o` to only return the new filename, not the whole line.
3. We store the result (using backticks ```) of this whole evaluation in the variable `X`.
4. We copy (`cp`) the current file to the new file.
5. Finally we execute the new file with `sh`.

## Example usage:

```
robert@unity:~/hwbash$ ls -lrt
total 4
-rw-r--r-- 1 robert robert 97 May 25 23:52 H
robert@unity:~/hwbash$ sh H
cp: cannot create regular file `': No such file or directory
sh: 0: Can't open
robert@unity:~/hwbash$ ls -lrt
total 48
-rw-r--r-- 1 robert robert 97 May 25 23:52 H
-rw-r--r-- 1 robert robert 97 May 25 23:52 e
-rw-r--r-- 1 robert robert 97 May 25 23:52 l
-rw-r--r-- 1 robert robert 97 May 25 23:52 l
-rw-r--r-- 1 robert robert 97 May 25 23:52 o
-rw-r--r-- 1 robert robert 97 May 25 23:52
-rw-r--r-- 1 robert robert 97 May 25 23:52 W
-rw-r--r-- 1 robert robert 97 May 25 23:52 o
-rw-r--r-- 1 robert robert 97 May 25 23:52 r
-rw-r--r-- 1 robert robert 97 May 25 23:52 l
-rw-r--r-- 1 robert robert 97 May 25 23:52 d
-rw-r--r-- 1 robert robert 97 May 25 23:52 !
robert@unity:~/hwbash$

```

## Updates

1. I saved some bytes by using `bash H` instead of `#!/bin/bash`. This also means that I don't have to copy the executable permission, so sorting by timestamps works now (but you need to add a `sleep 1` or something to make it reliable).
2. Saved some more bytes by moving the string to a comment and changing the command from `bash` to `sh`.

---
Tags: code-golf, hello-world
---


title: Minimum of a Polynomial in Python

text:
# Question
Title: Minimum of a Polynomial in Python
What is the shortest amount of code that can find the minimum of an inputted polynomial? I realize that you can import packages like Numpy and others, but using only user defined functions, what is the shortest way to do this? For example, if 6x6 \+ 4x3-12 is entered (ignore parsing issues), what would be the shortest amount of code to find the minimum value?

# Answer
## Python - 202 Bytes

```
D=lambda p:[i*p[i]for i in range(1,len(p))]
A=lambda p,x:p>[]and p[0]+x*A(p[1:],x)
def N(p):f=D(p);s=D(f);x=1.;y=-x;exec'x-=A(f,x)/A(s,x);y-=A(f,y)/A(s,y);'*99;return A(p,x),A(p,y)
print min(N(input()))

```

*11 bytes saved due to @xnor.*

Input is taken from stdin, and is expected to be in the following format: \[*x0*, *x1*, *x2*, ...\]. For example, the sample in the problem description would be entered as `[-12, 0, 0, 4, 0, 0, 6]`.

---

**Functions**

*D* \- Calculates the derivative of a polynomial *p*.
*A* \- Applies a polynomial *p* to the value *x*.
*N* \- Uses Newton's Method to calculate local minima/maxima of a polynomial *p*.

*Note:* For higher order polynomials, there may be several local minima. In these cases, this function is not guaranteed to find the global minimum.

---

**Sample Usage**

```
$ echo [-12, 0, 0, 4, 0, 0, 6] | python poly-min.py
-12.6666666667

```
> 6 votes

---
Tags: code-golf, tips, python, optimization, polynomials
---


title: 9 Holes of Code Golf - Kickoff

text:
# Question
Title: 9 Holes of Code Golf - Kickoff
There has already been a 9 Hole Challenge (and another one here), but that was soooo last year. And besides,  have only been around for 2 months (although it seems like forever). And it is considerably different.

Leader Board: (note that weighting for holes are not established yet)

```
+---------------+------------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
|Competitor     | Language   | Hole 1 | Hole 2 | Hole 3 | Hole 4 | Hole 5 | Hole 6 | Hole 7 | Hole 8 | Hole 9 | Total  |
+----------------------------------------------------------------------------------------------------------------------+
|Dennis         |CJam        |        | 31     |        |        |        |        |        |        |        | 31     |
+----------------------------------------------------------------------------------------------------------------------+
|Optimizer      |CJam        |        | 35     |        |        |        |        |        |        |        | 35     |
+----------------------------------------------------------------------------------------------------------------------+
|Martin Büttner |Mathematica |        | 222    |        |        |        |        |        |        |        | 222    |
+----------------------------------------------------------------------------------------------------------------------+
|Cameron        |Python      | 878    |        |        |        |        |        |        |        |        | 878    |
+----------------------------------------------------------------------------------------------------------------------+
|bubalou        |Processing 2| 717    |        |        |        |        |        |        |        |        | 717    |
+----------------------------------------------------------------------------------------------------------------------+
|Doorknob       |Python 2    |        |        |0.079711|        |        |        |        |        |        |0.079711|
+----------------------------------------------------------------------------------------------------------------------+
|Vulcan         |Java        |        |        |0.6949  |        |        |        |        |        |        |0.6949  |
+----------------------------------------------------------------------------------------------------------------------+
|Eli            |C++         |        |        |1.42042 |        |        |        |        |        |        |1.42042 |
+---------------+------------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

```

**Other Holes:**

It's been slow around here lately, so I am here to kick off the next 9 hole golf course, involving a smattering of all that I have seen here in my (albeit limited) experience. This will entail:

* Ascii Art
* Graphical Output
* Conway's Game of Life
* King of the Hill
* Kolmogorov complexity
* Quines
* Image processing
* Math
* Classic code golf.

I am really looking forward to seeing what you can do!

## Competition Rules

* You will choose **1 language** for **all** of the holes (that you participate in...see point 4 for more info).
* For all holes - standard loopholes are (still) not funny.
* The next challenge will appear when I see that there are enough submissions given a reasonable amount of time. King of the hill, for example, will take longer.
* You **do not** have to participate in all of the holes. If you find a hole particularly challenging, don't have the time to do it, etc, you will receive 2 times as many points as the lowest score. Please do not take advantage of this rule by leaving 1 golfscript answer with 12 characters and taking 24 as a score.

## Scoring

* Your score is based on the culmination of the scores from all of the holes
* Lowest score wins (as per real golf)
* The leaderboard will be placed at the top of this page

I will try my very best to make sure that no questions are duplicates, all questions have objective criteria, are well written, and that they all have (relatively) equal weight in the context of the whole contest.

*However, Please be patient when I fail.*

And, without further ado, the first challenge!

## The Plasma Globe

A plasma globe is everyone's favorite toy:

Your job it to draw one.

You must draw a base:

a globe:

A tesla thingy (?)

And, of course, cool plasma shoots:

However, when you put your hand near a plasma globe (or a conductive object as Wikipedia tells me), it attracts the plasma.

Your globe should reflect that.

To put it quantitatively, your globe has a maximum of 16 shoots (see above picture). An "object" on the surface of the globe (given by an angle in radians) will contain "conductive power", that is, the amount of beams it attracts. So an object with a power of 5 will attract 5 beams (a single line with thickness 5) leaving 11 to **spread evenly among the rest of the globe**:

Note that
1. the black circle in the middle remains above the plasma
2. that in this example, the angle would be pi/2.

You may have more than one conductive object, and in that event, it is not required that the shoots are equally spaced apart. However, they be relatively spaced out. For example, this is ok for 2 objects, 1 at angle pi/4 power 5 and another at angle 5pi/3 power 3:

You should be able to see each of the end points of the shoots (of plasma).

However, given an object (or sum of objects) with power greater than 16, the globe will "break":

## Notes

* The globe's diameter is 1.5 times bigger than the length of the base, which is a square
* When the globe breaks, the globe is on the right side. It is tangent to the right side of the base as well as the ground. There should be no plasma when the plasma globe is broken (why? safety features of course! No word on how it broke in the first place.)
* The color of everything except the shoots must be black, and 1 pixel thick. The color of the plasma has hue 245 - 280, and saturation/value 100. Use this under "HSV" if you have no idea what I am talking about.

## Input

Input can be through STDIN/command line args/whatever or through function arguments.

There should be 2 inputs - length of the base of the plasma globe (include an axis if using vector graphics), and an array of objects like this:

```
[[angle,power],[angle,power],[angle,power]]

```

So for no objects (see first picture with 16 lines) the input would be

```
100,[]

```

For the next (one object, power 5) it would be:

```
100,[[1.570796,5]]

```

For the last example:

```
100,[[0.785398,5],[5.23598,3]]

```

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

# Answer
> 4 votes
# Processing 2 - 717 characters

As processing is a language made for artists, and I am a very novice programmer, I do not expect to do very well on many of these challenges. That being said, I really like how simple it is to draw things in processing, and I have been meaning to play around with it some more, so these challenges should be interesting.

```
int j,m,b,k,d,l;float w,c,h,x,y,z;float v[],p[],g[];void setup(){j=m=d=0;c=z=0;String i[]= loadStrings("f.txt");i[0]=i[0].replace("[","").replace("]","");String o[]=split(i[0],',');v=new float[o.length];p=new float[o.length-1];for(String s:o){if(!s.equals("")){v[j]=Float.parseFloat(s);}j++;}w=v[0];size((int)w*3,(int)w*3);h=w*.75;l=v.length;noLoop();}void draw(){translate(w/2,height);scale(1,-1);rect(0,0,w,w);if(l>2){while(m<j-1){m+=2;c+=v[m];}}if(c>16){ellipse(w+h,h,2*h,2*h);rect(w/2,w,1,h);}else{ellipse(w/2,w+h,2*h,2*h);rect(w/2,w,1,h);b=16;m=1;stroke(#1500ff);if(l>2){while(m<j){p[m-1]=cos(v[m])*h;p[m]=sin(v[m])*h;strokeWeight(v[m+1]);line(w/2,w+h,p[m-1]+w/2,p[m]+w+h);b-=v[m+1];m+=2;}}strokeWeight(1);c=(PI*2)/b;k=b;g=new float[b+b];while(b>0){g[d]=cos(z+c*b)*h;g[d+1]=sin(z+c*b)*h;m=0;if(l>2){while(m<j-1){if(abs(g[d]-p[m])<.1 && abs(g[d+1]-p[m+1])<.1){b=k+1;z=z+.1;d=-2;break;}m+=2;}}b--;d+=2;}d--;while(d>0){line(w/2,w+h,g[d]+w/2,g[d-1]+w+h);d-=2;}}stroke(#000000);fill(#000000);ellipse(w/2,w+h,w/9,w/9);}

```

I'm sure this can be golfed down considerably and I may try to do that when I have more time, but for now I am happy with it.

reads in a file (f.txt) located in the data folder of the sketch to get its input. I used Camerons idea of shifting the free beams until they don't overlap.

```
int j,m,b,k,d,l;
float w,c,h,x,y,z;
float v[],p[],g[];
void setup(){
j=m=d=0;
c=z=0;
String i[]= loadStrings("f.txt");
i[0]=i[0].replace("[","").replace("]","");
String o[]=split(i[0],',');
v=new float[o.length];
p=new float[o.length-1];
for(String s:o){if(!s.equals("")){v[j]=Float.parseFloat(s);}j++;}
w=v[0];
size((int)w*3,(int)w*3);
h=w*.75;
l=v.length;
noLoop();
}

void draw()
{
  translate(w/2,height);
  scale(1,-1);
  rect(0,0,w,w);
  if(l>2)
  {
    while(m<j-1)
    {
      m+=2;
      c+=v[m];
    }
  }
  if(c>16)
  {
    ellipse(w+h,h,2*h,2*h);
    rect(w/2,w,1,h);
  }
  else
  {
    ellipse(w/2,w+h,2*h,2*h);
    rect(w/2,w,1,h);
    b=16;m=1;
    stroke(#1500ff);
    if(l>2)
    {
      while(m<j)
      {
        p[m-1] = cos(v[m]) * h;
        p[m] = sin(v[m]) * h;
        strokeWeight(v[m+1]);
        line(w/2,w+h,p[m-1]+w/2,p[m]+w+h);
        b-=v[m+1];
        m+=2;
      }
    }
    strokeWeight(1);
    c=(PI*2)/b;
    k=b;
    g=new float[b+b];
    while(b>0)
    {
      g[d] = cos(z+c*b) * h;
      g[d+1] = sin(z+c*b) * h;
      m=0;
      if(l>2)
      {
        while(m<j-1)
        {
          if(abs(g[d]-p[m])<.1 && abs(g[d+1]-p[m+1])<.1)
          {
            b=k+1;
            z=z+.1;
            d=-2;
            break;
          }
          m+=2;
        }
      }
      b--;
      d+=2;
    }
    d--;
    while(d>0)
    {
      line(w/2,w+h,g[d]+w/2,g[d-1]+w+h);
      d-=2;
    }
  }
    stroke(#000000);
    fill(#000000);
    ellipse(w/2,w+h,w/9,w/9);
}

```

Examples:

100,\[\[0.785398,3\],\[5.23598,5\]\]

100,\[\]

100,\[\[1.72398,12\],\[5.23598,5\]\]

get processing here

# Answer
> 3 votes
## Python, 878 chars

By no means is this golfed well, but I wanted to see an answer for this hole.

```
import matplotlib.pyplot as P
from math import *
L=len
M=min
Y=P.plot
K=P.Circle
Z=P.gcf().gca().add_artist
f=sin
g=cos
k={'color':(0,0,0)}
j={'color':(.16,0,1)}
def Q(S,C):
    P.axis([-S,S*2.5,0,S*3.5],**k)
    Y([0,S,S,0,0],[0,0,S,S,0],**k)
    Y([S/2,S/2],[S,7*S/4],**k)
    Z(K([S/2,7*S/4],S/20,**k))

    k['fill']=False

    A,B=zip(*C)

    N=16-sum(B)
    if N<0:
        Z(K([7*S/4,3*S/4],3*S/4,**k))

    else:
        Z(K([S/2,7*S/4],3*S/4,**k))
        if L(C)==0:
            D(16,0,S)
        elif L(C)==1:
            D(N,A[0],S)
            Y([S/2,S/2+3*S*g(A[0])/4],[7*S/4,7*S/4+3*S*f(A[0])/4],linewidth=B[0],**j)
        else:
            for c in C:
                Y([S/2,S/2+3*S*g(c[0])/4],[7*S/4,7*S/4+3*S*f(c[0])/4],linewidth=c[1],**j)
            D(N,J(N,A),S)
    P.show()

def J(N,A):
    T=d=0
    t=2*pi/N
    while d<0.1:
        T+=0.1
        d=M(M(a-T-floor((a-T)/t)*t for a in A),\
            M(T+ceil((a-T)/t)*t-a for a in A))
    return T

def D(N,I,S):
    a=I
    for i in range(N):
        Y([S/2,S/2+3*S*g(a)/4],[7*S/4,7*S/4+3*S*f(a)/4],**j)
        a+=2*pi/N

```

And some sample outputs

```
Q(100,[[pi/4,6],[-4.2*pi/8,1]])

```

```
Q(100,[[0.785398,10],[5.23598,7]])

```

```
Q(100,[[pi/4,3],[pi/2,3],[3*pi/2,2],[5*pi/4,2]])

```

# Answer
> 1 votes
# Python 2.7, ~~378~~ 375

```
from turtle import *;import sys
(s,P),A,B=eval(sys.argv[1]),90,180
n,S=sum([b for(a,b) in P]),.75*s;l=16-n
for i in 'abcd':fd(s);lt(A)
pu()
if l<0:goto(s+S,0)
else:goto(s/2,s)
pd();circle(S);pu();goto(s/2,s);lt(A);pd();fd(S)
def C():fd(S);fd(-S)
if n<16:
 color('blue')
 for i in range(l):rt(360/l);C()
 for a,p in P:pensize(p);rt(a*57.3);C()
color('black')
shape('circle')

```

It reads its parameters from commandline argument.

Sample images :

(parameters=`100,[[0.785398,5],[5.23598,3]]`)

(parameters=`100,[]`)

(parameters=`100,[[1.72398,12],[5.23598,5]]`)

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


title: Hole 2 - Prime Quine

text:
# Question
Title: Hole 2 - Prime Quine
Find Hole 1 here.

Make a quine that, when run, outputs its own source code block multiple times. In fact, it must output it n times, where n in the next prime number.

I think an example shows it best.

```
[MY QUINE][MY QUINE]
[MY QUINE][MY QUINE][MY QUINE]
[MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE]
[MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE]
[MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE][MY QUINE]

```

Each Program will output its base "block" (so \[MY QUINE\]) *the next prime number* times.

Built in functions to calculate whether a number is prime, (like an isPrime function), or to determine the next prime (like a nextPrime() function) are not allowed.

* This means that functions to list the number of divisors is not allowed
* Functions that return the prime factorization are likewise disallowed

This should be a true quine (except for some leeway, see next point), so you should not read your own source code.

Because languages like Java and C# are already at a disadvantage, You need not output totally working code. If it could be put in a function (that is called) and output the next quine, you are good.

This is code-golf, so shortest code wins!

# Answer
# CJam, 31 bytes

```
{'_'~]-3>U):U{)__,1>:*)\%}g*}_~

```

Try it online in the CJam interpreter.

### Idea

To check for primality, we'll use Wilson's theorem, which states that an integer **n \> 1** is prime if and only if **(n - 1)! ≡ -1 (mod n)**, which is true if and only if **(n - 1)! + 1 % n == 0**.

### Code

```
{                           }_~ e# Define a block and execute a copy.
                                e# The original block will be on top of the stack.
 '_'~]                          e# Push those characters and wrap the stack in an array.
      -3>                       e# Keep only the last three elements (QUINE).
         U):U                   e# Increment U (initially 0).
             {           }g     e# Do-while loop:
              )__               e# Increment the integer I on the stack (initially U).
                 ,1>            e#   Push [1 ... I-1].
                    :*          e#   Multiply all to push factorial(I-1).
                      )\%       e#   Push factorial(I-1) + 1 % I.
                                e# While the result is non-zero, repeat.
                                e# This pushes the next prime after U.
                           *    e# Repeat QUINE that many times.

```
> 5 votes

# Answer
## Mathematica, ~~248~~ 222 bytes

**Edit:** Fixed the usage of a prime-related function, but also improved the quining a bit.

**Edit:** Thanks to Dennis for introducing me to Wilson's theorem.

```
1;n=If[ValueQ@n,n+1,1];StringJoin@Array[#<>ToString[1##,InputForm]<>#2&@@\("1;n=If[ValueQ@n,n+1,1];StringJoin@Array[#<>ToString[1##,InputForm]<>#\2&@@("*"&,For[i=n,Mod[++i!/i+1,i]>0,0];i]")&,For[i=n,Mod[++i!/i+1,i]>0,0];i]

```

This assumes that the kernel is quit between subsequent runs of the quine (or at least `n` is reset), because it relies on `n` being undefined before the first instance of `[MyQuine]` is run.

This can probably be shortened a lot, but I don't have a lot of experience with quines, especially in Mathematica.

Here is an explanation:

```
1;

```

This doesn't do anything, but if concatenated onto the end of the previous quine, it multiplies the result of the last expression by `1` (which is a no-op) and the semicolon suppresses output. This ensures that only the last copy of `[MyQuine]` prints anything.

```
n=If[ValueQ@n,n+1,1];

```

This initialises `n` to `1` in the first copy of `[MyQuine]` and then increments it by `1` in each further copy - i.e. this just counts how many copies there are in `n`.

Skip ahead to the end now:

```
For[i=n,Mod[++i!/i+1,i]>0,0];i

```

This finds the next prime using Wilson's theorem.

```
StringJoin@Array[#<>ToString[1##,InputForm]<>#2&@@\("QUINE_PREFIX"*"QUINE_SUFFIX")&,NEXTPRIME[n]]

```

This is the actual quine. It creates `NextPrime@n` copies of the code itself. It's also a bit weird. Yes, I'm multiplying two strings there, and no that doesn't have a meaningful result. `QUINE_PREFIX` contains all the code before the two strings and `QUINE_SUFFIX` contains all the code after the two strings. Now usually you use `Apply` (or `@@`) to turn a list into a series of arguments. But you can replace any `Head` with `Apply` \- e.g. multiplication. So despite this being a product I can still turn it into into two arguments to my function. That function does:

```
#<>ToString[1##,InputForm]<>#2

```

Where `#` is the first argument (the prefix string), `#2` is the second argument (the suffix string), `##` is a sequence of both arguments. I need to prepend `1` to preserve the multiplication - otherwise `##` would splat into the argument list to `ToString`. Anyway, `ToString[1##,InputForm]&@@("abc"*"def")` returns `"abc"*"def"`... just what I need!

I think with all the stuff I need around the quine, an `eval`-based quine would be more appropriate here. I'll look into that later or tomorrow.
> 1 votes

# Answer
## CJam, ~~36~~ 35 bytes

```
{]W="_~"]U):U{)_,{)1$\%!},,2>}g*}_~

```

This can ~~definitely~~ be golfed further.

**How it works:**

```
{                               }_~   "Copy this code block and execute the copy";
 ]W=                                  "Take just the last element from the stack";
                                      "The other thing on stack is the block from above";
    "_~"]                             "Put "_~" on stack and wrap the 2 things in an array";
                                      "At this point, the string representation of stack"
                                      "elements is identical to the source code";
         U):U                         "Increment U and update U's value. This  variable"
                                      "actually counts the number of [Quine] blocks";
             {)_,{)1$\%!},,2>}g       "Find the next prime number"
                               *      "Repeat the array that many times, thus repeat the"
                                      "[Quine] block, the next prime times";

```

Thanks to Martin for reminding me the `]W=` trick :)

Try it online here
> 1 votes

# Answer
# J - 60 char

Uses the next-prime method like the other answers. (That's the `4 p:` bit.)

```
((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''

```

A cute little J trick is that `f :g` acts like `f` when given one argument and `g` when given two. So, if you write out, say `f :;'a'f :;'a'f :;'a'` then that acts like `f'a';'a';'a'`, which is great because that's a boxed list whose items are `'a'` and whose length is the number of occurrences.

So we can lift that into a quiney sort of thing. The `f` we use looks like `(foo $~ bar)`, where `foo` constructs the string part that we repeat over and over, `bar` finds the next prime number and multiplies it by 60, the length of the string in `foo`.

```
   ((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
   # ((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
180
   ((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
   # ((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''((58&$,2#{:)@;$~60*4 p:#) :;'((58&$,2#{:)@;$~60*4 p:#) :;'''
300

```
> 0 votes

# Answer
# Python 2.7, 214

```
from sys import*;R,s=range,chr(35)
def N(n):
 if n<3:return n+1
 for p in R(n+1,n+n):
    for i in R(2, p):
     if p%i==0:break
     else:return p
P=file(argv[0]).read();print(P.split(s)[0]+s)*N(P.count(chr(37)));exit(0)
#

```
> 0 votes

---
Tags: code-golf, quine
---