# Question
Title: Generate a 1920 x 1080 graphic with 2,073,600 unique colours
Challenge:

Write a program that outputs a graphic file 1920 pixels wide by 1080 pixels high. Every one of the 2,073,600 pixels within the graphic must be a unique colour and no colour values should be repeated. The colours should be specified in RGB and start at 0,0,0 and count upwards in sequence towards 255,255,255. You'll find a 1920 x 1080 pixel image will contain lots of blacks, blues and greens only.

For example, (a smaller cut down version). If the height was set to 5 and the width was set to 5 a 25 pixel square graphic would be output and each pixel would be a unique colour. The RGB colour array would look like this:

```
Array (
[0] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 0
    )

[1] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 1
    )

[2] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 2
    )

[3] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 3
    )

[4] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 4
    )

[5] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 5
    )

[6] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 6
    )

[7] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 7
    )

[8] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 8
    )

[9] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 9
    )

[10] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 10
    )

[11] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 11
    )

[12] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 12
    )

[13] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 13
    )

[14] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 14
    )

[15] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 15
    )

[16] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 16
    )

[17] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 17
    )

[18] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 18
    )

[19] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 19
    )

[20] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 20
    )

[21] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 21
    )

[22] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 22
    )

[23] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 23
    )

[24] => Array
    (
        [0] => 0
        [1] => 0
        [2] => 24
    )

)

```

Rules:

* Any programming language can be used to generate the image.
* The answer with the most upvotes wins.
* Colours must only be used once.
* Pixel in position 0,0 must start with colour 0,0,0
* Colours must fall within the true color 24 bit range.
* Image must be 1920 x 1080 pixels in size.
* Colours must be in RGB format.
* Using a library to output the image is ok.
* Output must be in the format of a graphic file e.g. output.png
* Output as text which represents the colour values doesn't count, the code must output a graphic file.
* File size of the output image doesn't matter.
* You must be able to view the output by opening it as a graphic in the chrome web browser.

I would be impressed if you mange to do this with really short code, your program also outputs the time in elapsed seconds taken to generate the image embedded within the image itself overlaid on the sequential pixels, your program outputs the image within 10 seconds. I would be really impressed if your program outputs the image within 1 second.

# Answer
> 40 votes
## Python - 660+ bytes

### Incremental Version

Full Size: http://www.pictureshack.net/images/57626\_all\_colors.png (4.52MB)

This is an image based on a Julia Set fractal. Each color is added to the image incrementally, although there is a substantial amount of pre-calculation.

---

### Luminosity Version

Full size: http://www.pictureshack.net/images/95389\_all\_colors4.png (5.24MB)

I've added an option to iterate each color by luminosity, rather than by index. This doesn't qualify as "counting up" from zero, but this seems to be a lax requirement. It's interesting that these two orderings expose completely different structures in the image. To use this, set the `use_luminosity` flag to `True`.

---

### Source

*Requires PIL.*

**Be warned**: this will take several minutes to execute. Using PyPy with Pillow runs in about one fifth the time of CPython with PIL, so I would recommend that, if possible.

```
from PIL import Image, ImageDraw

use_luminosity = True

dim = (1920,1080)

img = Image.new('RGB', dim)
draw = ImageDraw.Draw(img)

xstart = -.776707
ystart = -.134663

a = []

xd = 1.6 / 8192 / dim[0]
yd = 0.9 / 8192 / dim[1]

for x in range(dim[0]):
  print x
  for y in range(dim[1]):
    z = d = complex(xstart + x*xd, ystart + y*yd)
    c = 0
    while abs(z) < 2 and c < 5000:
      z = z*z + d
      c += 1
    a += [(c, -abs(z), x, y)]

a = a[1:]
a.sort(reverse = True)

t = [(i>>16, 255&i>>8, 255&i) for i in range(1, dim[0]*dim[1])]
if use_luminosity:
  t.sort(key = lambda c: c[0]*3 + c[1]*10 + c[2], reverse = True)

r = 0
for c,d,x,y in a:
  draw.point((x,y), t[r])
  r += 1

img.show()

```

***Edit**: updated so that `#000000` is at the upper-left, as specified.*
***Edit**: added a flag to iterate colors by luminosity.*
***Edit**: switched to native complex calculations, and integer luminosity weights, which are slightly faster.*

---

Solutions I worked on before the primary criterion became

## PHP - 161 bytes

```
<?header('Content-type: image/bmp');
ob_start();
echo'BM'.pack('I5S2',0,0,26,12,70780800,1,24);
for(;$i=($i-256)%2073601;)echo pack('CS',~$i,~$i>>8);
ob_end_flush();

```

This is going for fastest output possible. No library is used, just a pre-computed header, and direct byte output. Runs in less than 2s on my comp. By incrementing by *256* rather than *1*, it produces a pseudo-gradient effect, with no real computation needed. The only downfall is that (*0, 0*) is not black, but the result looks a lot nicer.

`ob_start();` and `ob_end_flush();` aren't strictly necessary, but buffering the output makes it run a lot faster.

Other interesting increments include:

17: https://i.stack.imgur.com/ieyyZ.png
103: https://i.stack.imgur.com/WD2wa.png
326: https://i.stack.imgur.com/c4DSF.png
557: https://i.stack.imgur.com/eTTWE.png
943: https://i.stack.imgur.com/7rrmR.png
2125: https://i.stack.imgur.com/Ct1kM.png

And many others. Although, most patterns that look like anything resemble stripes of some sort

---

## PHP - 105 bytes

```
<?=BM.pack(I5S2,header('Content-type:'),0,26,12,70780800,1,24);
for(;$i<2073600;)echo pack(CS,$i,$i++>>8);

```

Reckless disregard version.

* Given a broken `Content-type` header, Chrome will do its best to figure out what it was sent. In this case, it correctly identifies it as `image/bmp`. The lastest versions of FireFox and IE are also able to fix the broken header.
* The barewords `BM`, `I5S2`, and `CS` will generate a `NOTICE` error. To prevent corruption of the image, error reporting in `php.ini` will need to be set to prevent this (e.g. `error_reporting = E_ALL & ~E_NOTICE`).
* No output buffering. The image is constructed 3 bytes at a time, which is noticeably slower.
* The point (*0, 0*) is considered to be the lower left, rather than upper left.

---

## PHP-CLI - 83 bytes

```
<?=BM.pack(I5S2,0,0,26,12,70780800,1,24);
for(;$i<2073600;)echo pack(CS,$i,$i++>>8);

```

Run directly from the command line and piped to a file (e.g. `$ php all-colors.php > out.bmp`), no `Content-type` header is necessary. The resulting file is identical to the 105 byte version, and can be viewed in Chrome.

# Answer
> 24 votes
# C with the GD graphics library (err, about 2.5 KB?)

The rules didn't prohibit modifying an existing image. I made a program to replace all of an image's pixels with sequential RGB values from `#000000` to `#1fa3ff`, and I'm quite pleased with the results. Here's what it produced from from a photo posted to Flickr by Michael Carian (cc-by-sa 2.0):

(The raw output image is rather large (5.6 MB))

Here's a close-up of the top left corner (scaled up 400%):

The processing time is about 3 seconds for an image of this size:

```
$ time ./a.out foodface.png outfile.png
File accepted; 1920x1080 pixels
Saving...
Finished

real    0m3.251s
user    0m2.392s
sys 0m0.169s

```

and yes, all the pixels are different colours:

```
$ identify -format %k outfile.png
2073600

```

(`identify` is an ImageMagick utility; the `-format %k` option counts the number of unique colours in an image)

Here's the source code:

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

#define FIRST_PIXEL_MUST_BE_BLACK 1

#define luminance(rgb) (((rgb>>16)&0xff)*77+((rgb>>8)&0xff)*150+(rgb&0xff)*29)

typedef struct { int lum; int rgb; } pal;      /* Colour palette */
typedef struct { int lum; int x; int y; } pix; /* Pixel list */

/* Callback function for qsort */
int pcomp(const void *a, const void *b) {
  return ((pal *)(a))->lum-((pal *)(b))->lum;
}

int main(int argv, char *argc[]) {
  FILE        *infile,*outfile;
  gdImagePtr  img;
  int         img_width;
  int         img_height;
  int         npixels;
  int         x,y,i;
  int         rgb,colour_ref,c;
  pal         *palette;
  pix         *pixels;

  if (argv!=3) return printf("Usage: %s <source> <destination>\n",argc[0]);

  if (!(infile=fopen(argc[1],"r"))) {
    return printf("Can't open source file <%s>\n",argc[1]);
  }
  if (!(img=gdImageCreateFromPng(infile))) {
    return printf("Bad PNG file <%s>\n",argc[1]);
  }
  fclose(infile);

  img_width=img->sx;
  img_height=img->sy;
  npixels = img_width * img_height;
  printf("File accepted; %dx%d pixels\n",img_width,img_height);

  /* Allocate storage for palette and pixel data */
  palette = malloc(npixels * sizeof(pal));
  if (!palette) return printf("Out of memory\n");
  pixels = malloc(npixels * sizeof(pix));
  if (!pixels) return printf("Out of memory\n");

  /* Create palette and sort by luminance */
  for (i=0; i<npixels; i++) {
    palette[i].rgb=i;
    palette[i].lum=luminance(i);
  }
  qsort(palette,npixels,sizeof(pal),pcomp);

  /* Sort image pixels by luminance */
#if FIRST_PIXEL_MUST_BE_BLACK == 1
  colour_ref = gdImageColorAllocate(img,0,0,0);
  gdImageSetPixel(img,0,0,colour_ref);
#endif

  for (x=y=i=0;i<npixels;i++) {
    rgb = gdImageGetTrueColorPixel(img,x,y);
    pixels[i].x=x;
    pixels[i].y=y;
    pixels[i].lum=luminance(rgb);
    if (!(x=++x%img_width)) y++;
  }
#if FIRST_PIXEL_MUST_BE_BLACK == 1
  qsort(pixels+1,npixels-1,sizeof(pix),pcomp);
#else
  qsort(pixels,npixels,sizeof(pix),pcomp);
#endif

  /* Now use the palette to redraw all the pixels */
  for (i=0;i<npixels;i++) {
    c = palette[i].rgb;
    colour_ref = gdImageColorAllocate(img,c>>16,(c>>8)&0xff,c&0xff);
    gdImageSetPixel(img,pixels[i].x,pixels[i].y,colour_ref);
  }

  printf("Saving...\n");
  if (!(outfile=fopen(argc[2],"w"))) {
    return printf("Can't open <%s> for writing\n",argc[2]);
  }
  gdImagePng(img,outfile);
  fclose(outfile);
  gdImageDestroy(img);
  printf("Finished\n");
  return 0;
}

```

# Answer
> 16 votes
# C++, 750 bytes

A Full resolution PNG (5.1MB)

The code creates a collection of all integers from 0-1080\*1920, then sorts them by overall brightness. It then creates a Mandelbrot set, and sorts the positions based on their escape iteration and value. Then it walks through both sets, assigning colors in order from dark to bright to the Mandelbrot values smallest to largest. Finally, it writes a 32 bit per pixel BMP image to the output filename specified as a command line parameter.

```
#include <windows.h>
#include <vector>
#include <algorithm>
#define X _complex
#define U int
#define S(j,g)std::sort(j.begin(),j.end(),g);
U w=1920,h=1080;
WORD q[27]={'MB',36918,126,0,0,54,0,40,0,w,0,h,0,1,32,0,0,36864,126};
#define V(a,b)((a>>b)&255)
#define L(z)V(z,16)*.3+V(z,8)*.6+V(z,0)*.1
#define F for(c=0;c<w*h;c++)
U C(U a,U b){return L(a)<L(b);}
U M(X a,X b){return a.x<b.x;}
U main(U c,char**v){
std::vector<U>l;
std::vector<X>D;
F l.push_back(c);
U*i=new U[c];
DWORD p;
F{float r=0,i=0,R;p=0;
for(;p<w&&r*r+i*i<4;p++){R=r*r-i*i;i=2*r*i+(c/w-h/2)/400.;r=R+(c%w-w/2)/400.;}
X d={-p-r*r-i*i,c};
D.push_back(d);}
S(l,C)
S(D,M)
F i[(U)D[c].y]=l[c];
void*f=CreateFileA(v[1],4<<28,0,0,2,0,0);
WriteFile(f,q,54,&p,0);
WriteFile(f,i,w*h*4,&p,0);}

```

The code isn't fully golfed, but it's not going to get too much smaller.

# Answer
> 11 votes
# C - 854 bytes (when squeezed)

I originally had something with cyan, magenta and yellow corners and smooth gradations of colors which looked really nice, but it didn't meet the specs.

The following fulfills the specs: uses the "first" 2,073,600 colors, no repetitions, and black in the top left corner.

How it works is kind of cool. It builds an array with the colors, then sorts vertically and horizontally by different criteria a couple of times. The end result are pleasing transitions between blue & green and between dark & light. It takes about 1.5 seconds to run. Compile using: `gcc -o many many.c -lm` and run using: `./many > many.ppm`

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

#define W 1920
#define H 1080

typedef struct {unsigned char r, g, b;} RGB;

int S1(const void *a, const void *b)
{
        const RGB *p = a, *q = b;
        int result = 0;

        if (!result)
                result = (p->b + p->g * 6 + p->r * 3) - (q->b + q->g * 6 + q->r * 3);

        return result;
}

int S2(const void *a, const void *b)
{
        const RGB *p = a, *q = b;
        int result = 0;

        if (!result)
                result = p->b - q->b;
        if (!result)
                result = p->g - q->g;
        if (!result)
                result = q->r - p->r;

        return result;
}

int main()
{
        int i, j, n;
        RGB *rgb = malloc(sizeof(RGB) * W * H);
        RGB c[H];

        for (i = 0; i < W * H; i++)
        {
                rgb[i].b = i & 0xff;
                rgb[i].g = (i >> 8) & 0xff;
                rgb[i].r = (i >> 16) & 0xff;
        }

        qsort(rgb, H * W, sizeof(RGB), S1);

        for (n = 0; n < 2; n++)
        {
                for (i = 0; i < W; i++)
                {
                        for (j = 0; j < H; j++)
                                c[j] = rgb[j * W + i];
                        qsort(c, H, sizeof(RGB), S2);
                        for (j = 0; j < H; j++)
                                rgb[j * W + i] = c[j];
                }

                for (i = 0; i < W * H; i += W)
                        qsort(rgb + i, W, sizeof(RGB), S1);
        }

        printf("P6 %d %d 255\n", W, H);
        fwrite(rgb, sizeof(RGB), W * H, stdout);

        free(rgb);

        return 0;
}

```

FYI, this was the original image...

And for those interested in the code used to generate this image:

```
#include <stdio.h>
#include <math.h>

int main(int argc, char **argv)
{
        int x, y;
        int w = (argc > 1)? atoi(argv[1]): 1920;
        int h = (argc > 2)? atoi(argv[2]): 1080;
        double l = hypot(w, h);

        fprintf(stdout, "P6 %d %d 255\n", w, h);

        for (y = 0; y < h; y++)
        {
                for (x = 0; x < w; x++)
                {
                        unsigned char v[3];
                        v[0] = floor(256 * hypot(0 - x, h - y) / l);
                        v[1] = floor(256 * hypot(w - x, h - y) / l);
                        v[2] = floor(256 * hypot(w - x, 0 - y) / l);
                        fwrite(v, sizeof(unsigned char), 3, stdout);
                }
        }

        return 0;
}

```

# Answer
> 8 votes
## Ruby, 109

```
require'chunky_png';i=ChunkyPNG::Image.new 1920,1080
i.area.times{|v|i[*(v.divmod(1080))]=v<<8|255};i.save ?i

```

EDIT: I should note that I submitted this when the question was still tagged , before it became a so I was going for short code. This is not very imaginative but I believe it to be a valid submission.

Color values range from `00 00 00` to `1f a3 ff`, incrementing by `1`, so the lack of `red` in the result is not surprising.

For the cost of adding 1 character to the source code length (replace `<<8` with `<<11`), the following output can be had. This covers more range of the spectrum at the cost of `blue` resolution. It increments through RGB space at eight times the rate. Color values range from `00 00 00` to `fd 1f f8`.

# Answer
> 7 votes
# Racket

Never used racket object oriented programming before (message passing) so I'm not sure this is optimal, but it seems to get the job done.

```
#lang racket
(require racket/draw)
(let* ((x 1920) (y 1080) (b 256) (bb (* b b)) (pic (make-object bitmap% x y)))
  (let loop ((c 0) (v 0))
    (when (> (* x y) c)
      (send pic set-argb-pixels (modulo c x)   ; x
                                (quotient c x) ; y
                                1              ; width
                                1              ; height
                                (list->bytes
                                 (list 0                            ; alpha
                                       (modulo v b)                 ; red
                                       (quotient v bb)              ; green
                                       (modulo (quotient v b) b)))) ; blue
      (loop (+ c 1) (+ v 8))))
  (send pic save-file "image.png" 'png))

```

By not using the 3 first bits in the red channel I get all three colors in my result image.

# Brainfuck

The code prints out a 24bit BMP image to STDOUT for 8 bit cell BF interpreters. It creates the same image as the Racket version. It's based on the pnm version.

```
>-------->>+>----->-------->+++++++>>---->------>++>--->>++++[-<+++
+>]<[-<+++++<++++<++<+<++++++++<<+++++++++++++<<<<++>>>>>>>>>>>]<<[
.[-]>]++[-<++++>]<[->.<]<<.[-]...<.[-]...<[.[-]<].<.[-].<+[>>>>+<.<
<.>.>++++++++[>-]>[<<+[>>-]>>[<<<+[>>>-]>>>[<<<<->>>>>>>]<]<]<<<<<]

```

Ubuntu ships with `bf` that has 8 bit cells:

```
bf img.bf > image.bmp

```

Old version that violates being able to open from Chrome. It makes a .pnm file that are compatible with most image viewers.

```
>------>+++++>+++++>++>------>>-------->>+>------>>++>------->+>--
---->++++++>>>++++[-<++++>]<[-<+++++<+++<+<+++<++++<+++<+++<+<+++<
+++<++++<+++<+<+++<+++<+++<+>>>>>>>>>>>>>>>>>]<[.[-]<]+[>>>>+<.<<.
>.>++++++++[>-]>[<<+[>>-]>>[<<<+[>>>-]>>>[<<<<->>>>>>>]<]<]<<<<<]

```

# Answer
> 6 votes
# Python - 104

```
from PIL import Image
a=list(range(2073600))
i=Image.new("RGB",(1920,1080))
i.putdata(a)
i.save("o.png")

```

This is the version, which would have been for the code-golf challenge. As it is just increasing the value from 0 up to 2073599, it contains only unique colors.

## Python - 110

As I didn't like the above version (the colorrange isn't fully used), I tried something like the following:

```
from PIL import Image
a=list(range(0,2073600*8,8))
i=Image.new("RGB",(1920,1080))
i.putdata(a)
i.save("o.png")

```

## Python - 122

Another extension to the above:

```
from PIL import Image
a=[(i<<3,i)[i%2]for i in range(2073600)]
i=Image.new("RGB",(1920,1080))
i.putdata(a)
i.save("o.png")

```

# Answer
> 6 votes
Updated, first version did not have all colors unique in 24-bit space:

**Mathematica: 110**

```
x = 1920; y = 1080; Image[
 ParallelTable[
  List @@ ColorConvert[Hue[h, 1, (b + h)/2], "RGB"], {h, 0, 1 - 1/y,
   1/y}, {b, 0, 1 - 1/x, 1/x}]]

```

Rules verification:

```
list = ParallelTable[
  List @@ ColorConvert[Hue[h, 1, (b + h)/2], "RGB"], {h, 0, 1 - 1/y,
   1/y}, {b, 0, 1 - 1/x, 1/x}]

```

First pixel is black:

```
list[[1, 1]]

```

> ```
> {0., 0., 0.}
>
> ```

All colors are unique:

```
id = ImageData[Image[list], "Bit16"]]
Length[DeleteDuplicates[Flatten[id, 1]]] == 1920*1080

```

> ```
> True
>
> ```

---

~~**Mathematica: 146**~~

~~```
x = 1920; Image[
 Partition[
  ParallelTable[
   List @@ ColorConvert[Hue[c, 1, c^.01], "RGB"], {c, 0, 1, 1/(
    x*1080)}], x]]

```
Takes 14.778 seconds.<br>Rules verification:<br>```
list = Partition[
  ParallelTable[
   List @@ ColorConvert[Hue[c, 1, c^.01], "RGB"], {c, 0, 1, 1/(
    x*1080)}], x];

```
First pixel is black:<br>```
list[[1, 1]]

```

```
{0., 0., 0.}

```
All colors are unique:<br>```
Length[DeleteDuplicates[Flatten[list, 1]]] == 1920*1080

```~~
> ~~```
> True
>
> ```~~

# Answer
> 5 votes
**Processing, 301**
This is not an attempt at the most terse solution, but it maintains all of the control to achieve the desired arrangement of colors. Yes, the colors are not consecutive, but that is no fun.

```
int w = 1920;
int h = 1080;
void setup(){
  size(w, h);
  int x = 0; int y = 0;
  for(int i=0; i<w*h; i++){
    stroke(
      (i >> 0) & 0xFF,
      (i >> 6) & 0xFF,
      (i >> 3) & 0xFF
    );
    if (y % h == 0){
      y = 0;
      x++;
    }
    point(x, y);
    y++;
  }
  save("unique.png");
}

```

# Answer
> 3 votes
## Visual Basic .NET, 273 bytes

```
Imports System.Drawing : Module Module1
    Sub Main()
        Dim b As New Bitmap(1920, 1080) : For i As Integer = 0 To 2073599 : Dim x = 0 : b.SetPixel(Math.DivRem(i, 1080, x), x, Color.FromArgb(i + &HFF000000)) : Next : b.Save("output.png")
    End Sub
End Module

```

This outputs a 5.61 MB file:

The code above is a compressed version of this more readable code. Spaces were removed to save bytes.

```
Imports System.Drawing
Module Module1
    Sub Main()
        Dim b As New Bitmap(1920, 1080)
        For i As Integer = 0 To 2073599
            Dim x = 0
            b.SetPixel(Math.DivRem(i, 1080, x), x, Color.FromArgb(i + &HFF000000))
        Next
        b.Save("output.png")
    End Sub
End Module

```

Link to the image: http://µ.pw/k

# Answer
> 2 votes
**ImageMagick - Convert** 119

Lets use the `convert` from the ImageMagick toolbox to create images. It runs in 0 seconds. It is golfed to 119 characters. I overlay two gradients (red-blue and black-white) convert them to HSL and back to RGB.

```
G=gradient;convert -size 900x900 $G:red-blue \( $G: -rotate 90 \) -compose CopyRed -resize 1920x1080\! -composite o.png

```

Examples of gradient overlay can be found in the ImageMagick manual pages.

# Answer
> 1 votes
**PHP, 507**

You will probably need to increase the amount of memory allocated to PHP in order to run. Uses GD. Takes around 9 seconds to generate the image.

```
$a=microtime(true);$c=1920;$d=1080;$e=$c*$d;$f=@imagecreatetruecolor($c,$d);$h=255;$j=2200000;$k=array();$l=1;for($m=0;$m<=$h;$m++){for($n=0;$n<=$h;$n++){for($o=0;$o<=$h;$o++){if($l<=$j){$k[]=array($m,$n,$o);$l++;}else{break;}}}}while($p<=$e){for($q=0;$q<=$c;$q++){for($s=0;$s<=$d;$s++){$t=imagecolorallocate($f,$k[$p][0],$k[$p][1],$k[$p][2]);imagesetpixel($f,$q,$s,$t);$p++;}}}$u=number_format((microtime(true)-$a),4).' seconds';imagestring($f,6,10,10,$u,$v);header('Content-Type: image/png');imagepng($f);

```

Link to the output image: https://i.stack.imgur.com/AAKqW.png

See it running on the web: http://ben-paton.co.uk/portfolio/pixel.php?w=1920&h=1080

# Answer
> 1 votes
# DELPHI/PASCAL (Version #1), 361 bytes

```
program P;
{$APPTYPE CONSOLE}
uses
  System.SysUtils, Vcl.Imaging.pngimage,System.UITypes;
var a : TPNGObject; h,w: Integer; c : TColor;
begin
   a :=TPNGObject.CreateBlank(COLOR_RGB, 16, 1920, 1080);
   for h := 0 to 1020 do
     for w := 0 to 1920 do
         begin
         a.Pixels[h,w]:= c ;
         inc(c);
         end;
   a.SaveToFile('e:\t.png');
end.

```

# Answer
> 0 votes
# Tcl/Tk, 149

# ~~150~~

```
set p [image c photo -w 1920 -h 1080]
set y 0
time {set x 0
time {$p p [format #%06x [expr $y*1920+$x]] -t $x $y
incr x} 1920
incr y} 1080
$p w c.png

```

# Answer
> 0 votes
## Java 411 386+24 bytes

## Golfed

```
import java.awt.image.*;()->new BufferedImage(1920,1080,1){{long t=System.currentTimeMillis();int q=-1;for(int i=0;i<getWidth();i++)for(int j=0;j<getHeight();j++)setRGB(i,j,q++);java.io.File f=new java.io.File(System.getProperty("user.home"),"Desktop"+System.getProperty("file.separator")+(System.currentTimeMillis()-t)+".png");javax.imageio.ImageIO.write(this,"png",f);java.awt.Desktop.getDesktop().open(f);}}

```

## Ungolfed

```
import java.awt.image.*;
() -> new BufferedImage(1920, 1080, 1) {
        {
            long t = System.currentTimeMillis();
            int q = -1;
            for (int i = 0; i < getWidth(); i++)
                for (int j = 0; j < getHeight(); j++)
                    setRGB(i, j, q++);
            java.io.File f = new java.io.File(System.getProperty("user.home"),
                    "Desktop" + System.getProperty("file.separator")
                            + (System.currentTimeMillis() - t) + ".png");
            javax.imageio.ImageIO.write(this, "png", f);
            java.awt.Desktop.getDesktop().open(f);
        }
    }

```

## Result

## Explanation

This is not my attempt at the shortest solution, but rather the most portable. Only left import for BufferedImage because the other's didn't save bytes. Rather than loading the Image into a JPanel and writing on it, I saved the time it takes from beginning until writing to disk as the filename. For me, this took this resulted in filenames of about ~110 ms, whereas the time from beginning until end usually took ~500ms. Lastly, it should be platform independent as I tested in both Windows and an Ubuntu VM and it worked (It writes the file to your Desktop). Had to have the return statement due to the Callable syntax garbage. Although I'm working on the work around, I doubt I'll find a better implementation on my own due to the saves from using l and w for my for loops. I'd say half a second for java isn't too bad. My original implementation opened directly to chrome using

```
 (System.getProperty("os.name").toLowerCase().contains("win")) { try { Process
 * p = Runtime.getRuntime() .exec(new String[] { "cmd", "/c", "start chrome " +
 * f }); p.waitFor(); } catch (Exception e) { } } else if
 * (System.getProperty("os.name").toLowerCase().contains("ix")) { try { Process
 * p = Runtime.getRuntime().exec(new String[] { "google-chrome" + f }); } catch

```

But I believe it's still validated as it can still be opened by chrome, it just automatically opens to your default png viewer (version not tested on Unix based machines).

I'm aware of the byte saves possible but mainly have omitted them to qualify for bonuses. If requested I can upload shorter, platform specific examples. Thank you.

## Edit

Removed Unnecessary Try Catch block and ill formatted return statement to reduce ~30 bytes.
Removed `BufferedImage.TYPE_INT_RGB` because it's literally just 1.

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


title: Gif - Jif, Jif - Gif

text:
# Question
Title: Gif - Jif, Jif - Gif
Stolen from @Downgoat with permission

The point of this challenge is to (not) settle the debate on the pronunciation of "gif".

"

---

The pronunciation of *gif* is debated and while it's supposed to be (and should be) pronounced *jif*, it's still commonly disputed.

In this challenge you will be given a set of words that have a *g* or *j*, representing the sound that the word is pronounced with. You'll also get some text in which you have to fix the incorrect spellings of *gif*.

Because this is the internet and everyone always wrong. It's (not) common courtesy to correct them.

An example of a wrong pronunciation would be:

```
There was a **gif** of a mouse eating a burrito
```

The wrong spelling of *gif*? Unacceptable! This must be corrected immediately:

```
There was a **jif (as in jar)** of a mouse eating a burrito
```

---

Are we done? Nope, you're *still* wrong.

You're *always* wrong

This must work the other way:

```
In the **jif** the cat wore a hat of a cat
```

This obvious misspelling must be fixed, we shall correct this to:

```
In the **gif (as in graphic)** the cat wore a hat of a cat
```

---

### Rules

* Input is a string (the sentence) and an array of strings (or any reasonable alternative, such as a comma separated string) in any order
* You may take the `g` and `j` words in any order. They may be taken separately.
* Every instance of `gif` (any case) in the sentence must be replaced with `jif (as in ___)` where `___` is a uniformly random selected word beginning with `j` from the array of strings, and vice versa for `jif` with words beginning with `g`.
* ONLY the words `gif` and `jif` should be replaced (i.e "jiffy" should not be changed). Those words have done no wrong.
* You are guaranteed that at least one word in the array begins with `g` and at least one begins with `j`.
* Case must be preserved (e.g. `GiF` -\> `JiF`).
* You may write a program or a function
* Standard loopholes apply
* We need to (not) settle the debate quickly; shortest code in bytes wins

---

### Examples

Input and output separated by a single line:

```
graphic, jar, jam, gram
I saw a jif of how to pronounce gif that showed gif is pronounced jif

I saw a gif (as in graphic) of how to pronounce jif (as in jar) that showed jif (as in jam) is pronounced gif (as in gram)

gravy, jeff
G is for gIf, h is for JiF, i is for gIF, j is for JIf

G is for jIf (as in jeff), h is for GiF (as in gravy), i is for jIF (as in jeff), j is for JIf (as in gravy)

joke, june, gorilla, great
Jiffy should not be treated as a GIF or JIF, like gifted.

Jiffy should not be treated as a JIF (as in june) or GIF (as in great), like gifted.

```

# Answer
## Mathematica, 164 165 bytes

This is an abomination, but I want someone to share my pain.

```
StringReplace[f[f@"g"="j"]="g";f[f@"G"="J"]="G";z=IgnoreCase->1>0;#,x:"g"|"j"~~y:"if ":>{f@x,y,"(as in ",RandomChoice@StringCases[#2,f@x~~Except[","]..,z]}<>") ",z]&

```

`Function` which expects the first argument `#` to be the sentence to be (in)corrected and the second argument `#2` to a be comma separated string of words.

`f[f@"g"="j"]="g";f[f@"G"="J"]="G"` defines a function `f` which takes the letters `g`, `G`, `j`, and `J` to their appropriate replacements. This is ever so slightly shorter than `f@"g"="j";f@"j"="g";f@"G"="J";f@"J"="G"`.

I also set `z` equal to `IgnoreCase->True` since I'll be using it twice.

`x:"g"|"j"~~y:"if "` is a `StringExpression` which matches `"gif "` or `"jif "`, naming the first letter `x` and the last three characters `y`. Since the option `z` (also known as `IgnoreCase->True`) is passed to `StringReplace`, these letters can be in any combination of upper and lower case.

I then replace every such match with

```
{f@x,y,"(as in ",RandomChoice@StringCases[#2,f@x~~Except[","]..,z]}<>") "

```

`RandomChoice@StringCases[#2,f@x~~Except[","]..,z]` randomly selects a word out of the second argument `#2` which begins with `f[x]`, again ignoring case because the option `z` is given.
> 6 votes

# Answer
# Ruby, ~~88~~ ~~87~~ 91 bytes

-1 byte from ETHproductions. +4 bytes because words containing "gif" or "jif" shouldn't be replaced. -2 bytes because replacement word lists can be taken separately now.

```
->s,g,j{s.gsub(/\b(g|j)if\b/i){$&.tr("GgJj","JjGg")+" (as in #{($1[/g/i]?j:g).sample})"}}

```

Try it online!
> 5 votes

# Answer
# CJam, 78 bytes

```
l',%:A;lS%{_ela"gifjif"3/&{_V=_el:B'g=1W?Z*+V\t" (as in "A{V=elB=!},mR')}O?S}%

```

Try it online!

Requires the list of replacement characters to be separated by nothing but commas.

---

Explanation:

```
l',%                        e# read line of input and split at commas
    :A;                     e# store in var A and pop off the stack
       lS%{...}%            e# for each word in the next line of input so:

_ela"gifjif"3/&             e#   intersection of ["gif" "jif"] and [lowercase(word)]
               {...}O?      e#   if set it non-empty, run block below, otherwise do nothing (push empty string)
                      S     e#   push space

_V=                         e#     extract first char
   _el:B                    e#     duplicate to lowercase and store in var B
        'g=1W?Z*+           e#     convert g/G <=> j/J
                 V\t        e#     store back to word
" (as in "                  e#     push string
           A{V=elB=!},      e#     filter replacements by words starting with the same char (case insensitive)
                      mR    e#     select random element
                        ')  e#     push ')' char

```
> 3 votes

# Answer
# Python 3, 237 bytes

```
lambda s,g,j:' '.join([(w if False in(w[0]in q,w[1:2]in['i','I'],w[2:3]in['f','F'],w[3:]in",;!?.")else q[w[0]]+w[1:3]+" (as in "+choice(g if w[0]in 'jJ'else j)+')'+w[3:])for w in s.split()])
from random import*
q=dict(zip("gGjJ","jJgG"))

```

Try it online!

This is the best I can do -- might be some way to do it quicker (probably with regexes) but my brain hurts now.

Explanation: `q` is a simple dictionary mapping, I hope that's clear. `s,g,j` are the input string, the list of g-words, and the list of j-words. `' '.join` joins together the list comprehension done across `for w in s.split()` is therefore for the list of words in s.

The middle bit is black magic, which I'll break down piecewise. First, the condition: `False in(w[0]in q,w[1:2]in['i','I'],w[2:3]in['f','F'],w[3:]in",;!.")`.

`w[0]in q` checks the first character is in the keys of `q` which are `'g','G','j','J'`. The reason for separating out `q` as a variable is we also use it as a dict/map later.

`w[1:2]in ['i','I']` checks that the second character is either i or I. The :2 is necessary because just putting `w[1]` would result in a crash on 1-letter words, but slices don't do that for some reason (I thought they did, whatever!)

`w[2:3]in ['f','F']` is analogous. I briefly had this as just 2: before I realized I needed to account for gif, or jif, followed by punctuation!

`w[3:]in",;!?."` checks that the subsequent character(s) are punctuation. I admit my code doesn't work if someone puts 'gif?!' but I can't be perfect. Someone else can take up the challenge of opening quotes before gif or jif, too.

`False in(,,,)` is basically a big NAND. It's actually the same bytecount as separating four items with `and` and swapping the arguments, but this looks cooler and works better if you have to extend it to a fifth `and`ed thing.

`w if` means that if False is in the conditional-list, we just return the word unchanged -- it doesn't meet our criteria. `else`, we change it to:

`q[w[0]]+w[1:3]+" (as in "+choice(g if w[0]in 'jJ'else j)+')'+w[3:]`

OK. `q[w[0]]` substitutes the first letter correctly. `w[1:3]` tacks on the i or I and f or F, `w[3:]` tacks on any trailing punctuation. That leaves the as in clause.

`" (as in "+choice(g if w[0]in 'jJ'else j)+')'` puts in the obvious string literal at the start and the trailing parenthesis, the interesting bit here is `choice(g if w[0]in 'jJ'else j)` which randomly chooses from `g` or `j`, depending on if `w[0]` is in `'jJ'`. and I just realized I had this bit backwards so fixing that throughout, done.

It's been a long day. `choice` is in the `random` module hence the import. I think that's everything.
> 1 votes

# Answer
## JavaScript (ES6), 142 bytes

```
(s,g,j,r=l=>l[Math.random()*l.length|0])=>s.replace(/\b[gj]if\b/gi,w=>`GJgj`[l=`JGjg`.search(w[0])]+w.slice(1)+` (as in ${r([g,j,g,j][l])})`)

```

Takes separate `g` and `j` word lists.
> 0 votes

# Answer
# Javascript(ES6), 151 bytes

```
f=(s,g,j)=>s.replace(/\b(g|j)(if)\b/ig,(m,p,c)=>`${a=g,p=="j"?"g":p=="J"?"G":(a=j,p=="g"?"j":"J")}${c}(as in ${a[Math.floor(Math.random()*a.length)]})`)

```

I probably can golf down the ternary part more, but I can't think of how right now. Also, it takes the g and j words separately.
> 0 votes

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


# Question
Title: Enumerate all possible grids of integers with constraints
**Problem**

Consider a square 3 by 3 grid of non-negative integers. For each row `i` the sum of the integers is set to be `r_i`. Similarly for each column `j` the sum of integers in that column is set to be `c_j`.

The task is to write code to enumerate all possible different assignments of integers to the grid given the row and column sum constraints. Your code should output one assignment at a time.

**Input**

Your code should take 3 non-negative integers specifying the row constraints and 3 non-negative integers specifying the column constraints. You can assume that these are valid, i.e. that the sum or row constraints equals the sum of column constraints. Your code can do this in any way that is convenient.

**Output**

Your code should output the different 2d grids it computes in any human readable format of your choice. The prettier the better of course. The output must not contain duplicate grids.

**Example**

If all the row and column constraints are exactly `1` then there are only `6` different possibilities. For the first row you can put a `1` in any of the first three columns, for the second row there are now `2` alternatives and the last row is now completely determined by the previous two. Everything else in the grid should be set to `0`.

Say the input is `2 1 0` for the rows and `1 1 1` for the columns. Using APL's lovely output format, the possible integers grids are:

```
┌─────┬─────┬─────┐
│0 1 1│1 0 1│1 1 0│
│1 0 0│0 1 0│0 0 1│
│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┘

```

Now say the input is `1 2 3` for the rows and `3 2 1` for the columns. The possible integer grids are:

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

```

# Answer
# APL (Dyalog), 42 bytes

```
{o/⍨(⍵≡+/,+⌿)¨o←3 3∘⍴¨(,o∘.,⊢)⍣8⊢o←⍳1+⌈/⍵}

```

Try it online!

Uses `⎕IO←0` which is default on many systems. The other stuff in the header is just pretty printing for the matrices (boxed display).

Input is list of six values, rows sums first, then column sums.

**How?**

`o←⍳1+⌈/⍵` \- `o` gets the range `0` to the maximum (`⌈/`) of input

`,o∘.,⊢` \- cartesian product with `o` and flatten (`,`)

`⍣8` \- repeated for eight times

`3 3∘⍴¨` \- shape every 9-items list into a 3×3 matrix

`¨o←` \- save these matrices to `o`, and for each

`+/,+⌿` \- check if the rows sums (`+/`) concatenated to the column sums (`+⌿`)

`⍵≡` \- correspond with the input

`o/⍨` \- filter `o` (the matrices array) by truthy values
> 9 votes

# Answer
# Husk, ~~20~~ 17 bytes

```
fȯ=⁰mΣS+Tπ3π3Θḣ▲⁰

```

-3 bytes thanks to @H.PWiz

Takes input as a list `xs` encoding the constraints `[r_1,r_2,r_3,c_1,c_2,c_3]`, try it online!

### Explanation

Brute force approach :P Generate all 3x3 grids with entries `[0..max xs]`:

```
f(=⁰mΣS+T)π3π3Θḣ▲⁰  -- input ⁰, for example: [1,1,1,1,1,1]
                ▲⁰  -- max of all constraints: 1
               ḣ    -- range [1..max]: [1]
              Θ     -- prepend 0: [0,1]
            π3      -- 3d cartesian power: [[0,0,0],...,[1,1,1]]
          π3        -- 3d cartesian power: list of all 3x3 matrices with entries [0..max] (too many)
f(       )          -- filter by the following predicate (eg. on [[0,0,1],[1,0,0],[0,1,0]]):
      S+            --   append to itself, itself..: [[0,0,1],[1,0,0],[0,1,0],..
        T           --   .. transposed:             ..[0,1,0],[0,0,1],[1,0,0]]
      mΣ            --   map sum: [1,1,1,1,1,1]
    =⁰              --   is it equal to the input: 1

```
> 7 votes

# Answer
# Brachylog, 17 bytes

```
{~⟨ṁ₃{ℕᵐ+}ᵐ²\⟩≜}ᶠ

```

Try it online!

**WARNING: UGLY OUTPUT!** Don't frick out, it's still human-readable, I'm not required to account for how much. ;)

For some reason it has to be much longer than what I'd expect to make sense (13 bytes):

```
⟨ṁ₃{ℕᵐ+}ᵐ²\⟩ᶠ

```

This latter version, if it worked, would have taken input from the output (i.e. command-line argument) instead.
> 6 votes

# Answer
# Python 2, ~~149~~ ~~145~~ ~~142~~ ~~141~~ ~~138~~ 136 bytes

```
lambda s:[i for i in product(range(max(sum(s,[]))+1),repeat=9)if[map(sum,(i[j:j+3],i[j/3::3]))for j in 0,3,6]==s]
from itertools import*

```

Try it online!

Takes input as a list of lists: `[[r1, c1], [r2, c2], [r3, c3]]`
> 4 votes

# Answer
## Haskell, ~~94~~ ~~88~~ ~~84~~ 79 bytes

```
q=mapM id.(<$"abc")
f r=[k|k<-q$q$[0..sum r],(sum<$>k)++foldr1(zipWith(+))k==r]

```

Takes the sums of the rows and columns as a single flat 6-element list `[r1,r2,r3,c1,c2,c3]`.

Try it online!

```
q=mapM id.(<$"abc")         -- helper function

f r =                       --
  [k | k <-   ,    ]        -- keep all k
    q$q$[0..sum r]          --   from the list of all possible matrices with
                            --   elements from 0 to the sum of r
                            -- where
    (sum<$>k) ++            --   the list of sums of the rows followed by
    foldr1(zipWith(+))k     --   the list of sums of the columns
    == r                    -- equals the input r

```

As the elements of the matrices to test go up to the sum of `r`, the code does not finish in reasonable time for large row/column sums. Here's a version that goes up to the maximum of `r` which is faster, but 4 bytes longer: Try it online!
> 4 votes

# Answer
# Mathematica, 81 bytes

```
Select[0~Range~Max[s=#,t=#2]~g~3~(g=Tuples)~3,(T=Total)@#==s&&T@Transpose@#==t&]&

```

finds all 3x3 matrices with elements 0..Max and selects the right ones
this means that `(Max+1)^9` matrices have to be checked

Try it online!
> 3 votes

# Answer
# , ~~115~~ 110 bytes

```
function(S)for(m in unique(combn(rep(0:max(S),9),9,matrix,F,3,3)))if(all(c(rowSums(m),colSums(m))==S))print(m)

```

Try it online!

Takes input as `c(r1,r2,r3,c1,c2,c3)`, a single `vector`, and prints the matrices to stdout.

It's quite similar to Uriel's APL answer, but it generates the 3x3 grids somewhat differently.

Letting `M=max(S)`, it generates the vector `0:M`, then `rep`eats it 9 times, i.e., `[0..M, 0...M, ..., 0...M]` nine times. Then it selects all combinations of that new vector taken 9 at a time, using `matrix, 3, 3` to convert each 9-combination into a `3x3` matrix, and forcing `simplify=F` to return a list rather than an array. It then uniquifies this list and saves it as `m`.

Then it filters `m` for those where row/column sums are identical to the input, printing those that are and doing nothing for those that aren't.

Since it computes `choose(9*(M+1),9)` different possible grids (more than the `(M+1)^9` possibilities), it'll run out of memory/time faster than the more efficient (but less golfy) answer below:

# , 159 bytes

```
function(S,K=t(t(expand.grid(rep(list(0:max(S)),9)))))(m=lapply(1:nrow(K),function(x)matrix(K[x,],3,3)))[sapply(m,function(x)all(c(rowSums(x),colSums(x))==S))]

```

Try it online!
> 3 votes

# Answer
# MATL, ~~35~~ 22 bytes

*-13 bytes thanks to Luis Mendo*

```
X>Q:q9Z^!"@3et!hsG=?4M

```

Try it online!

Link is to a version of the code that prints a little more nicely; this version will just print all the matrices with a single newline between them.

Takes input as `[c1 c2 c3 r1 r2 r3]`.

Obviously, this computes the cartesian power `X^` of `0...max(input)` with exponent `9`, and transposing `!`. It then loops `"` over the columns, reshaping each `@` as a 3x3 matrix `3e`, duplicating `t`, transposing `!`, and horizontally concatenating them `h`. Then it computes the column sums `s`, which will result in the vector `[c1 c2 c3 r1 r2 r3]`. We do elementwise equality to the input `G=`, and if `?` all are nonzero, we recover the correct matrix by selecting the input to the function `!` by using `4M`.
> 3 votes

# Answer
## Batch, 367 bytes

```
@echo off
for /l %%i in (0,1,%1)do for /l %%j in (%%i,1,%1)do for /l %%k in (%%i,1,%4)do call:c %* %%i %%j %%k
exit/b
:c
set/a"a=%1-%8,c=%4-%9,f=%8-%7,g=%9-%7,l=%5-f,m=%2-g,l^=m-l>>31&(m^l),m=%5+c-%3-f,m&=~m>>31
for /l %%l in (%m%,1,%l%)do set/a"b=%2-g-%%l,d=%5-f-%%l,e=%6-a-b"&call:l %7 %%l
exit/b
:l
echo %1 %f% %a%
echo %g% %2 %b%
echo %c% %d% %e%
echo(

```

The top left 2×2 square forces the result, so the best approach is to generate all values for the top left integer, all valid values for the sum of the top left and top middle integer, all valid values for the sum of the top left and middle left integer, and calculate the range of valid values for the middle integer, then, having looped through all the appropriate ranges, calculate the remaining values from the constraints.
> 2 votes

# Answer
# Python 2, 118 bytes

```
def f(v,l=[],i=0):n=len(l);V=v*1;V[~n/3]-=i;V[n%3]-=i;return[l][any(V):]if n>8else V*-~min(V)and f(V,l+[i])+f(v,l,i+1)

```

Try it online!

---

# Python 2, 123 bytes

```
V=input()
n=max(V)+1
for k in range(n**9):
 m=[];exec"m+=[k%n,k/n%n,k/n/n%n],;k/=n**3;"*3
 if map(sum,m+zip(*m))==V:print m

```

Try it online!
> 1 votes

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


title: Build an Electrical Grid

text:
# Question
Title: Build an Electrical Grid
# The Challenge

There are N cities aligned in a straight line. The i-th city is located `A[i]` kilometers to the right of the origin. No two cities will be in the same place.

You are going to build an electrical grid with some power plants. Power plants must be built inside a city. However, you are only allowed to build `K` (\< N) power plants, so there will be some cities with no power plants in them. For each city with no power plants, you must build a cable between it and **the nearest city that has a power plant**.

For example, if there are three cities located at `0, 1, 2`, and only the city at `0` has a power plant, you need to build two cables, one from `2` to `0`(2km) and the other from `1` to `0`(1km), which have a total length of 3km.

Given `K` and positions of cities (`A`), you should compute the minimum kilometers of cable you need to build the grid.

# Example Testcases

```
K = 1, A = [0, 2, 4, 6, 8] : 12
# build power plant in the city at position 4, total length = 4 + 2 + 0 + 2 + 4 = 12

K = 3, A = [0, 1, 10, 11, 20, 21, 22, 30, 32] : 23
# build power plants in cities at positions 0, 10 and 22

K = 5, A = [0, 1, 3, 6, 8, 11, 14] : 3
# build power plants in all cities except those at positions 0, 3

K = 6, A = [0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84] : 49

```

# Specifications

* You should implement a function or a program, which takes a positive integer `K` and a list of integers `A` in any form, and output/return an integer representing the answer.
* `A` is sorted in ascending order, and all elements are non-negative integers.
* `A[0] = 0`, and `A[N-1]` will be no more than 1000N.
* Note that the output will be in magnitude of 1000N2, so in larger cases, you may need 64-bit integers in some languages.
* Multithreading is **not** allowed (I will set the affinity of your program to only 1 core when judging). Compiler optimizations (such as `-O2` in C) are allowed.

# Scoring

* I will time your code on my computer (Ubuntu 16.04 with Intel i7-3770S processor) with different size of testcases. Specifically, I will generate some testcases with N = floor(2x/5) where x is a positive integer.
Your score will be the x value of the smallest testcase that your program uses more than 10 seconds or 1 GiB of memory, or doesn't give a correct answer.

+ The answer with highest score wins. If two answers get the same score, the earlier answer wins.
* All programs will be judged by the same set of testcases.
* Feel free to post your own scorings. Explanations of your algorithm are encouraged.

# Bonus

This is my C++ program, it scores **108**. You can verify the SHA-256 digest `9a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935d` by the whole code segment (without footer) in the link.

The algorithm combines binary search and Knuth's optimization to find the correct penalty of each plant to get the desired number. The complexity is O(N log N log A\[N-1\]). I was surprised that the program got a higher score than the O(N log A\[N−1\]) solution by Anders Kaseorg. It's probably due to the fact that the log case in Knuth's optimization won't usually occur.

Note that this challenge is the same as IOI 2000 Post Office. The original constraints are N \<= 300 and K \<= 30, though.

# Answer
# Rust, score = 104

This is an implementation of the algorithm noted by Grønlund et al. (2017) at the end of §3.3.1, though I had to follow a long citation chain and fill in some missing details. It runs in *O*(*N* log *A*\[*N* − 1\]) time.

Compile with `rustc -O`. Input format is `K` on the first line, followed by the entries of `A`, one entry per line, all on stdin.

(Note: I’m submitting this an hour after the bounty deadline, but I expect the last version I submitted before the bounty deadline, which ran in *O*(*N* log *N* log *A*\[*N* − 1\]) time, to score about 94.)

```
use std::cmp::min;
use std::io::{self, BufRead};
use std::iter::{once, Cloned};
use std::num::Wrapping;
use std::ops::Range;
use std::slice;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

trait ColsTrait<Col>: Clone {
    type Iter: Iterator<Item = Col>;
    fn len(&self) -> usize;
    fn iter(&self) -> Self::Iter;
    fn slice(&self, range: Range<usize>) -> Self;
}

impl<'a, Col: Clone> ColsTrait<Col> for &'a [Col] {
    type Iter = Cloned<slice::Iter<'a, Col>>;
    fn len(&self) -> usize {
        (*self).len()
    }
    fn iter(&self) -> Self::Iter {
        (*self).iter().cloned()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        unsafe { self.get_unchecked(range) }
    }
}

impl ColsTrait<usize> for Range<usize> {
    type Iter = Range<usize>;
    fn len(&self) -> usize {
        self.end - self.start
    }
    fn iter(&self) -> Range<usize> {
        self.clone()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        Range {
            start: self.start + range.start,
            end: self.start + range.end,
        }
    }
}

fn smawk<Col: Copy, Cols: ColsTrait<Col>, Key: Ord, F: Copy + Fn(usize, Col) -> Key>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(&l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j);
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f,
            smawk(n / 2, shift + 1, &s[..], f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols.clone(),
            f,
            smawk(n / 2, shift + 1, cols, f).into_iter(),
        )
    }
}

fn smawk1<
    Col: Copy,
    Cols: ColsTrait<Col>,
    Key: Ord,
    F: Fn(usize, Col) -> Key,
    Iter: Iterator<Item = usize>,
>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    if k >= a.len() {
        return 0;
    }
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    let c = |i: usize, j: usize| {
        let h = (i - j) / 2;
        unsafe {
            (sa.get_unchecked(i) - sa.get_unchecked(i - h) - sa.get_unchecked(j + h)
                + sa.get_unchecked(j))
                .0
        }
    };
    let cost1 = c(a.len(), 0);
    if k == 1 {
        return cost1;
    }
    let cost2 = (1..a.len()).map(|j| c(j, 0) + c(a.len(), j)).min().unwrap();
    let mut low = 0;
    let mut high = cost1 - cost2;
    let mut ret = INF;
    while low <= high {
        let penalty = low + (high - low) / 2;
        let mut out = vec![(INF, 0); a.len() + 1];
        out[0] = (0, 0);
        let mut begin = 0;
        let mut chunk = 1;
        loop {
            let r = min(a.len() + 1 - begin, 2 * chunk);
            let edge = begin + chunk;
            let (out0, out1) = out.split_at_mut(edge);
            let f = |i: usize, j: usize| {
                let h = (edge + i - j) / 2;
                let &(cost, count) = unsafe { out0.get_unchecked(j) };
                (
                    cost.saturating_add(
                        unsafe {
                            sa.get_unchecked(edge + i) - sa.get_unchecked(edge + i - h)
                                - sa.get_unchecked(j + h)
                                + sa.get_unchecked(j)
                        }.0 + penalty,
                    ),
                    count + 1,
                )
            };
            for ((i, j), o) in smawk(r - chunk, 0, begin..edge, &f)
                .into_iter()
                .enumerate()
                .zip(out1.iter_mut())
            {
                *o = min(f(i, begin + j), *o);
            }
            let x = unsafe { out1.get_unchecked(r - 1 - chunk) };
            if let Some(j) = (edge..begin + r - 1).find(|&j| &f(r - 1 - chunk, j) <= x) {
                begin = j;
                chunk = 1;
            } else if r == a.len() + 1 - begin {
                break;
            } else {
                chunk *= 2;
            }
        }
        let &(cost, count) = unsafe { out.get_unchecked(a.len()) };
        if count > k {
            low = penalty + 1;
        } else {
            ret = cost.wrapping_sub(k as Cost * penalty);
            if count == k {
                return ret;
            }
            high = penalty - 1;
        }
    }
    ret
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

```

Try it online!

# Rust, pretest score = 73

Compile with `rustc -O`. Input format is `K` on the first line, followed by the entries of `A`, one entry per line, all on stdin.

```
use std::io::{self, BufRead};
use std::iter::once;
use std::num::Wrapping;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

fn smawk<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j.clone());
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &s, f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &cols, f).into_iter(),
        )
    }
}

fn smawk1<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key, Iter: Iterator<Item = usize>>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    let mut cost = vec![INF; a.len() + 1 - k];
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    cost[0] = 0;
    let cols = (0..a.len() + 1 - k).collect::<Vec<_>>();
    for m in 0..k {
        cost = {
            let f = |i: usize, &j: &usize| {
                if i + 1 >= j {
                    let h = (i + 1 - j) / 2;
                    unsafe {
                        cost.get_unchecked(j).saturating_add(
                            (sa.get_unchecked(i + m + 1) - sa.get_unchecked(i + m + 1 - h)
                                - sa.get_unchecked(j + m + h)
                                + sa.get_unchecked(j + m))
                                .0,
                        )
                    }
                } else {
                    INF
                }
            };
            smawk(a.len() + 1 - k, 0, &cols, &f)
                .into_iter()
                .enumerate()
                .map(|(i, j)| f(i, &j))
                .collect()
        };
    }
    cost[a.len() - k]
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

```

Try it online!
> 9 votes

# Answer
# C, score = 56

content of `a.c`:

```
typedef void V;typedef char C;typedef long L;typedef unsigned long U;
#define R return
#define W while
#define S static
#include<sys/syscall.h>
#define h1(f,x    )({L r;asm volatile("syscall":"=a"(r):"0"(SYS_##f),"D"(x)              :"cc","rcx","r11","memory");r;})
#define h3(f,x,y,z)({L r;asm volatile("syscall":"=a"(r):"0"(SYS_##f),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
#define read(a...) h3(read ,a)
#define write(a...)h3(write,a)
#define exit(a...) h1(exit ,a)
S V P(U x){C s[32],*p=s+32;*--p='\n';do{*--p='0'+x%10;x/=10;}W(x);write(1,p,s+32-p);}
S V mc(V*x,V*y,L n){C*p=x,*q=y;for(L i=0;i<n;i++)p[i]=q[i];}
#define min(x,y)({typeof(x)_x=(x),_y=(y);_x+(_y-_x)*(_y<_x);})
#define t(x,i,j)x[(i)*(n+n-(i)+1)/2+(j)] //triangle indexing
#define x(i,j)t(x,i,j)
#define y(i,j)t(y,i,j)
#define z(i,j)t(z,i,j)
#define N 4096 //max
L n;U ka[N+1],c[N],x[N*(N+1)/2],y[N*(N+1)/2],z[N*(N+1)/2];
V _start(){
 C s[1<<20];L r=0;U v=0;
 W(0<(r=read(0,s,sizeof(s))))for(L i=0;i<r;i++)if('0'<=s[i]&&s[i]<='9'){v=s[i]-'0'+10*v;}else{ka[n++]=v;v=0;}
 n--;U k=*ka,*a=ka+1;
 for(L i=n-1;i>=0;i--)for(L j=i-1;j>=0;j--)x(j,i)=x(j+1,i)-a[j]+a[i];
 for(L i=0;i<n;i++)for(L j=i+1;j<n;j++)y(i,j)=y(i,j-1)+a[j]-a[i];
 for(L i=n-1;i>=0;i--)for(L j=i+1;j<n;j++){
  U v=~0ul,*p=&x(i,i),*q=&y(i,j);for(L l=i;l<j;l++){v=min(v,*p+++*q);q+=n-l;} //min(v,x(i,l)+y(l,j));
  z(i,j)=v;}
 mc(c,z,8*n);
 for(L m=1;m<k;m++)for(L j=n-1;j>=m;j--){
  U v=~0ul,*p=&z(j,j);for(L i=j-1;i>=m-1;i--){v=min(v,c[i]+*p);p-=n-i;} //min(v,c[i]+z(i+1,j))
  c[j]=v;}
 P(c[n-1]);exit(0);}

```

shell script to compile and test the above:

```
#!/bin/bash -e
clang -O3 -nostdlib -ffreestanding -fno-unwind-tables -fno-unroll-loops -fomit-frame-pointer -oa a.c
strip -R.comment -R'.note*' a;stat -c'size:%s' a
t(){ r="$(echo "$1"|./a)";if [ "$r" != "$2" ];then echo "in:$1, expected:$2, actual:$r";fi;} #func tests
t '1 0 2 4 6 8' 12
t '3 0 1 10 11 20 21 22 30 32' 23
t '5 0 1 3 6 8 11 14' 3
t '6 0 1 3 6 8 14 15 18 29 30 38 41 45 46 49 58 66 72 83 84' 49
t '2 0 7 9' 2
for n in 1176 1351 1552 1782 2048;do #perf test
 echo "n:$n";a=0 inp="$((2*n/3))" RANDOM=1;for i in `seq $n`;do inp="$inp $a";a=$((a+=RANDOM%1000));done
 ulimit -t10 -v1048576;time ./a<<<"$inp"
done

```

~~n=776 takes 6.2s, n=891 takes 12s~~

~~n=1176 takes 5.9s, n=1351 takes a little over 10s~~

n=1351 takes 8.7s, n=1552 takes more than 10s (with k=2\*n/3) on my `Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz`
> 6 votes

# Answer
# C++, score = 53

The solution I had said in the comment. `O(n²×k)`. (now I deleted it because it is no longer necessary) Probably can be reduced to `O(n×k)`.

The input is pretty flexible, on the first line, the first number is `k`, the other numbers are items of array `a`, but if it encounters any close-parentheses it stops reading input. So input like `K = 1, A = [0, 2, 4, 6, 8] : 12` is accepted.

```
// https://codegolf.stackexchange.com/questions/149029/build-an-electrical-grid

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <climits>

bool read(std::istream& str, int& x) {

    char ch;

    do {
        if (str >> x) return true;
        if (str.eof()) return false;
        str.clear(); // otherwise it's probably int parse error
    } while (str >> ch && ch != ']' && ch != ')' && ch != '}');
    // ignore 1 character, but treat any close parentheses as end of input

    // cannot read anything now
    return false;
}

int main() {
    int k; std::vector<int> a;

    //{ Read input
    std::string st; std::getline(std::cin, st);
    std::stringstream sst (st);

    read(sst, k);

    int x;
    while (read(sst, x)) a.push_back(x);
    //}

    std::vector<std::vector<int>> dp (a.size(), std::vector<int>(k));
    // dp[n][k] = min distance you can get for cities [n..a.size()-1]
    // and [k+1] power plants, and city [n] has a power plant.

    // sum_array[x] = sum of coordinates of cities [x..a.size()-1]
    std::vector<int> sum_array (a.size()+1);
    sum_array.back() = 0;
    for (int n = a.size(); n --> 0;)
        sum_array[n] = sum_array[n+1] + a[n];

    for (int n = a.size(); n --> 0;) {
        for (int k1 = k; k1 --> 0;) {
            if (k1 == 0) {
                int nWire = a.size() - 1 - n;
                dp[n][k1] = sum_array[n+1] - nWire * a[n];
            } else {
            // unindent because my screen width is limited

dp[n][k1] = INT_MAX / 2; // avoid stupid overflow error (in case of -ftrapv)

// let [n1] be the next position for a power plant
int first_connect_right = n; // < lengthy variable name kills screen width
// ^ lengthy comment kills screen width

for (int n1 = n + 1; n1 < (int)a.size(); ++n1) {

    while (a[first_connect_right]-a[n] < a[n1]-a[first_connect_right]) ++first_connect_right;

    int nRightWire = n1 - first_connect_right, nLeftWire = first_connect_right - 1 - n;
    dp[n][k1] = std::min(dp[n][k1],
        a[n1]*nRightWire-(sum_array[first_connect_right]-sum_array[n1]) +
        (sum_array[n+1]-sum_array[first_connect_right])-a[n]*nLeftWire +
        dp[n1][k1-1]
    );

}

            }

        }
    }

    int ans = INT_MAX;
    for (int n = a.size()+1-k; n --> 0;) {
        ans = std::min(ans, dp[n].back() + a[n]*n-sum_array[0]+sum_array[n]);
    }

    std::cout << ans << '\n';

    return 0;
}

```

Try it online!

Generate random test cases. (input `N` and optionally city range, `1000×N` by default)
> 3 votes

# Answer
# C#, score = 23

I am sure this is not going to win this challenge, I just wanted to post a first (and very basic) answer to encourage other people to post their algorithms and improve mine. This code must be compiled as a console project that uses the Combinatorics package from NuGet. The main method contains some calls to the `Build` method to test the proposed cases.

```
using Combinatorics.Collections;
using System;

namespace ElectricalGrid
{
    class Program
    {
        static void Main(string[] args)
        {
            if (Build(1, new long[] { 0, 2, 4, 6, 8 }) == 12)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(3, new long[] { 0, 1, 10, 11, 20, 21, 22, 30, 32 }) == 23)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(5, new long[] { 0, 1, 3, 6, 8, 11, 14 }) == 3)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(6, new long[] { 0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84 }) == 49)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");

            Console.ReadKey();
        }

        static long Build(int k, long[] a)
        {
            var combs = new Combinations<long>(a, k);
            var totalDist = long.MaxValue;
            foreach (var c in combs)
            {
                long tempDist = 0;
                foreach (var i in a)
                {
                    var dist = long.MaxValue;
                    foreach (var e in c)
                    {
                        var t = Math.Abs(i - e);
                        if (t < dist) dist = t;
                    }
                    tempDist += dist;
                }
                if (tempDist < totalDist) totalDist = tempDist;
            }
            return totalDist;
        }
    }
}

```

Really simple explanation: for each combination `c` of `k` elements from `a`, calculate the sum of the distances from each element of `a` to the nearest element in `c`, and return the combination with the least total distance.

One-liner version of the `Build` method (probably slower than the original, expanded version; this needs to add a reference to `System.Linq`):

```
static long Build(int k, long[] a)
{
    return new Combinations<long>(a, k).Min(c => a.Sum(i => c.Min(e => Math.Abs(i - e))));
}

```
> 2 votes

# Answer
# C++, score = 48

```
#include <stdio.h>
#include <queue>
#include <algorithm>
typedef long long ull;
typedef unsigned int uint;
uint A[1<<20];
ull S[1<<20];

double ky = 1;
struct point {
    ull dist;
    int n;
    inline point() {}
    inline point(ull dist, int n): dist(dist), n(n) {}
    inline double res() const{
        return dist + n * ky;
    }
    inline int operator<(const point& other) const {
        return res() < other.res();
    }
} V[1<<20];
inline ull f(int L, int R) {
    int m = L+R+1 >> 1;
    return (S[R]-S[m]) - A[m]*(R-m) +
           A[m]*(m-L) - (S[m]-S[L]);
}
int main() {
    int N, K, i, j, p;
    scanf ("%d%d", &N, &K);
    ull s = 0;
    for (i=1; i<=N; i++) {
        scanf ("%u", A+i);
        S[i] = s += A[i];
    }
    double kyL = 0, kyH = 1e99;
    point cL, cR;
    for (int step=0; step++<50; ky = std::min(ky*2, (kyL+kyH)*.5)) {
        for (i=1; i<=N; i++) {
            point tmp(f(0,i), 1);
            for (j=1; j<i; j++) {
            //printf("ky=%f [%d]=%d %I64d %f\n", ky, i, tmp.n, tmp.dist, tmp.res());
                point cmp = V[j];
                cmp.dist += f(j, i);
                cmp.n ++;
                if (cmp<tmp) tmp=cmp;
            }
            //printf("ky=%f [%d]=%d %I64d %f\n", ky, i, tmp.n, tmp.dist, tmp.res());
            V[i] = tmp;
        }
        if (V[N].n == K) {
_:          return! printf("%I64d", V[N].dist);
        }
        if (V[N].n > K) {
            kyL = ky;
            cL = V[N];
        } else {
            kyH = ky;
            cR = V[N];
        }
        //printf("ky=%f %d %I64d %f\n", ky, V[N].n, V[N].dist, V[N].res());
        //getch();
    }
    V[N].dist = (double)cL.dist / (cR.n-cL.n) * (K-cL.n) +
                (double)cR.dist / (cL.n-cR.n) * (K-cR.n) + .5;
    printf("%I64d", V[N].dist);
}

```

Usage input: N K A\[1\] A\[2\] ... A\[N\]
> 2 votes

# Answer
# Ruby, score = 23

```
->a,l{d=l.map{|x|l.map{|y|(x-y).abs}};[*0...l.size].combination(a).map{|r|r.map{|w|d[w]}.transpose.sum{|r|r.min}}.min}

```

Try it online!

I don't think it's going to win, but I wanted to give it a try.
> 2 votes

# Answer
# JavaScript (ES6) (Node.js), score = 10

New Algorithm, will explain if it actually works this time.

```
const {performance} = require('perf_hooks');

class Connection{
    constructor(left,index,length,right){
        if(typeof right === 'undefined'){
            this._distance = 0;
        } else {
            this._distance = typeof left === 'undefined' ? 0 :
                    Math.abs(right - left);
        }
        var half = Math.floor(length/2);
        if(length % 2 < 1){
            this._magnitude = half - Math.abs(index - half + 1);
        } else {
            var temp = index - half;
            this._magnitude = half - Math.abs(temp >= 0 ?temp:temp + 1);
        }
        this._value = this.distance * this.magnitude;
    }

    get distance(){return this._distance;};
    get magnitude(){return this._magnitude;};
    set magnitude(value){
        this._magnitude = value;
        this._value = this.distance * this.magnitude;
    };
    valueOf(){return this._value};
}

class Group{
	constructor(...connections){
        this._connections = connections;

		this._max = Math.max(...connections); //uses the ValueOf to get the highest Distance to the Left
	}
	get connections(){return this._connections;};
	get max(){return this._max;};
    cutLeft(index){

            for(let i=1,j=index-1;;i++){

                if(typeof this.connections[j] === 'undefined' || this.connections[j].magnitude <= i){
                    break;
                }
                this.connections[j].magnitude = i;
                j--;
            }

    }

    cutRight(index){

            for(let i=0,j=index;;i++){

                if(typeof this.connections[j] === 'undefined' || this.connections[j].magnitude <= i){
                    break;
                }
                this.connections[j].magnitude = i;
                j++;
            }

    }

    static of(...connections){
        return new Group(...connections.map((c,i)=>new Connection(c.distance,i,connections.length)));
    }

	split(){
        var index = this.connections.findIndex(c=>c.valueOf() == this.max);
        if(index < 0){
            return;
        }
        var length = this.connections.length;
        var magnitude = this.connections[index].magnitude;

        this.cutLeft(index);
        this.cutRight(index);
        this._max = Math.max(...this.connections);
	}

    center(){
        if(typeof this._center === 'undefined'){
            this._center = this.connections.reduce((a,b)=>a==0?b.valueOf():a.valueOf()+b.valueOf(),0);
        }
        return this._center;
    }

    valueOf(){return this._max;};
    toString(){
        var index = this.connections.findIndex(c=>c.valueOf() == this.max);
        var value = this.connections[index].magnitude;
        var ret = '';
        for(let i = 0;i<value;i++){
            ret += this.connections.map(c=>{return (i<c.magnitude)?c.distance:' ';}).reduce((a,b)=>a==''?b:a+'-'+b,'') + '\n';
        }
        return ret;
    };
}

function crunch(plants, cities){
	var found = [];
    var size = cities.length;
    cities = cities.map((city,i,arr)=> new Connection(city,i,size,arr[i+1])).slice(0,cities.length-1);
    var group = new Group(...cities);
    for(;plants>1;plants--){
    group.split();
    }
    console.log(`Wire Length Needed: ${group.center()}`);
}

function biggestGroup(groups){
	return groups.find(g => g[g.length-1].orig - g[0].orig);
}

function* range (start, end, limit) {
    while (start < end || typeof limit !== 'undefined' && limit-- > 0) {
        yield start
        start += 1 + Math.floor(Math.random()*100);
    }
}

function* cities (score){
	let n = Math.floor(Math.pow(2,score/5));
	var start = 0;
	while (n-- > 0 && start <= (1000 * n)) {
		yield start;
        start += 1 + Math.floor(Math.random()*100);
    }
}

if(typeof process.argv[3] === 'undefined'){
    crunch(1,[0, 2, 4, 6, 8]);
    console.log("Correct Answer: 12");
    crunch(3,[0, 1, 10, 11, 20, 21, 22, 30, 32]);
    console.log("Correct Answer: 23");
    crunch(5,[0, 1, 3, 6, 8, 11, 14]);
    console.log("Correct Answer: 3");
    crunch(6,[0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84]);
    console.log("Correct Answer: 49");
    crunch(2, [0, 21, 31, 45, 49, 54]);
    console.log("Correct Answer: 40");
    crunch(2, [0, 4, 7, 9, 10]);
    console.log("Correct Answer: 7");
    crunch(2, [0, 1, 3, 4, 9]);
    console.log("Correct Answer: 6");

    var max = 0;
    var min = Number.POSITIVE_INFINITY;
    var avg = [];

    var score = typeof process.argv[2] === 'undefined' ? 60 : process.argv[2];

    for(j = 0; j<10; j++){
        var arr = []; for(let i of cities(score)) arr.push(i);
        var plants = Math.floor(1 + Math.random() * arr.length);
        console.log(`Running: Test:${j} Plants: ${plants}, Cities ${arr.length}, Score: ${score}`);
        // console.log(`City Array: [${arr}]`);
        var t0 = performance.now();
        crunch(plants,arr);
        var t1 = performance.now();
        time = (t1-t0)/1000;
        console.log(`Time Taken = ${time} seconds`);
        avg.push(time);
        max = Math.max(time,max);
        min = Math.min(time,min);
    }
    console.log(`Bench: ${avg.reduce((a,b)=>a+b,0)/avg.length} Max: ${max} Min: ${min} Total: ${avg.reduce((a,b)=>a+b,0)}`);
} else {
    var plants = process.argv[2];
    var arr = process.argv.slice(3);
    console.log(`Running: Plants: ${plants}, Cities ${arr.length}`);
    var t0 = performance.now();
    crunch(plants,arr);
    var t1 = performance.now();
    time = (t1-t0)/1000;
    console.log(`Time Taken = ${time} seconds`);
}

```

Try it online!

Run the same way as the other one.

# JavaScript (ES6) (Node.js), pretest score = 12

Outline of the algorithm:

The program first maps the Data into the City Class, which maps a few data points:

* city - the absolute distance of the city
* left - the distance of the closest city to the left
* right - distance of the closest city to the right
* index - (deprecated) index in original city array

the array is then thrown into the Group class, which has the following:

* cities - the city array
* dist - the distance spanning the group
* max - the largest left connection in the group
* split()
    + returns an array containing sub groups split along the largest connection connected to the center city in the group
    + if there are 2 center nodes (an even length group) it chooses from those 3 connections
    + (\*note\*: this will drop any groups with less than two cities)
* center()
    + returns the best wire value for the group
    + working on a solution to skip iterating over each city left for this step
    + now with 50% less mapping

Now the algorithm proceeds to split the groups as long as it has 2 or more power plants to place.

Finally it maps the groups to the it's centers, and sums them all up.

## How to run:

### Run using Node.js (v9.2.0 is what was used for creation)

running the program using generated test cases for score 70:

```
node program.js 70

```

running the program using 1 power plant and cities \[0,3,5\]:

```
node program.js 1 0 3 5

```

## Code:

```
const {performance} = require('perf_hooks');

class City{
	constructor(city, left, right, i){
		this._city = city;
		this._index = i;
		this._left = typeof left === 'undefined' ? 0 : city - left;
		this._right = typeof right === 'undefined' ? 0 : right - city;
	}

	get city(){return this._city;};
	get index(){return this._index;};
	get left(){return this._left;};
    get right(){return this._right;};
    set left(left){this._left = left};
    set right(right){this._right = right};

	valueOf(){return this._left;};
}

class Group{
	constructor(...cities){
        this._cities = cities;
        // console.log(cities.map(a=>a.city).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log(cities.map(a=>a.left).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log(cities.map(a=>a.right).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log("+==+==+==+==+==+==+==+==+==+==+==+==")
		this._dist = cities[cities.length-1].city - cities[0].city;
		this._max = Math.max(...cities); //uses the ValueOf to get the highest Distance to the Left
	}

	get dist(){return this._dist;};
	get cities(){return this._cities;};
	get max(){return this._max;};

	split(){
        //var index = this.cities.findIndex(city=>city.left == this.max);
        //this.cities[index].left = 0;
        // console.log(`Slicing-${this.max}-${index}------`)
        var centerIndex = this.cities.length / 2;
        var splitIndex = Math.floor(centerIndex);
        if(centerIndex%1 > 0){
            var center = this.cities[splitIndex];
            if(center.right > center.left){

                splitIndex++;
            }
        } else {
            var right = this.cities[splitIndex];
            var left = this.cities[splitIndex-1];
            if(left.left > Math.max(right.right,right.left)){

                splitIndex--;
            } else if(right.right > Math.max(left.left,left.right)){

                splitIndex++;
            }
        }
        // console.log(splitIndex);
        this.cities[splitIndex].left = 0;
        this.cities[splitIndex-1].right = 0;
        var leftCities = [...this.cities.slice(0,splitIndex)];
        var rightCities = [...this.cities.slice(splitIndex)];

        // var center = this.cities[]

        if(leftCities.length <= 1){
            if(rightCities.length <= 1){
                return [];
            }
            return [new Group(...rightCities)]
        }
        if(rightCities.length <= 1){
            return [new Group(...leftCities)];
        }
        return [new Group(...leftCities), new Group(...rightCities)];
	}

    center(){
        if(typeof this._center === 'undefined'){
            if(this.cities.length == 1){
                return [0];
            }
            if(this.cities.length == 2){
                return this.cities[1].left;
            }
            var index = Math.floor(this.cities.length/2);
            this._center = this.cities.reduce((a,b)=> {
                // console.log(`${a} + (${b.city} - ${city.city})`);
                return a + Math.abs(b.city - this.cities[index].city);
            },0);
            // console.log(this._center);
        }

        return this._center;
    }

	valueOf(){return this._max;};
}

function crunch(plants, cities){
	var found = [];
    var size = cities.length;
    cities = cities.map((city,i,arr)=> new City(city,arr[i-1],arr[i+1],i));
	var groups = [new Group(...cities)];

	// console.log(groups);
    for(;plants>1;plants--){
        var mapped = groups.map(g=>g.center()-g.max);
        var largest = Math.max(...groups);
        // console.log('Largest:',largest)
        // console.log(...mapped);
		var index = groups.findIndex((g,i)=> mapped[i] == g.center() - g.max && g.max == largest);
		// console.log(index);
        groups = index == 0 ?
            [...groups[index].split(),...groups.slice(index+1)]:
            [...groups.slice(0,index),...groups[index].split(),...groups.slice(index+1)];
    }
    // console.log(`=Cities=${size}================`);
    // console.log(groups);
    size = groups.map(g=>g.cities.length).reduce((a,b)=>a+b,0);

    // console.log(`=Cities=${size}================`);
    var wires = groups.map(g=>g.center());

    // console.log(...wires);
    // console.log(`=Cities=${size}================`);
    console.log(`Wire Length Needed: ${wires.reduce((a,b)=>a + b,0)}`);
}

function biggestGroup(groups){
	return groups.find(g => g[g.length-1].orig - g[0].orig);
}

function* range (start, end, limit) {
    while (start < end || typeof limit !== 'undefined' && limit-- > 0) {
        yield start
        start += 1 + Math.floor(Math.random()*100);
    }
}

function* cities (score){
	let n = Math.floor(Math.pow(2,score/5));
	var start = 0;
	while (n-- > 0 && start <= (1000 * n)) {
		yield start;
        start += 1 + Math.floor(Math.random()*100);
    }
}

if(typeof process.argv[3] === 'undefined'){
    crunch(1,[0, 2, 4, 6, 8]);
    console.log("Correct Answer: 12");
    crunch(3,[0, 1, 10, 11, 20, 21, 22, 30, 32]);
    console.log("Correct Answer: 23");
    crunch(5,[0, 1, 3, 6, 8, 11, 14]);
    console.log("Correct Answer: 3");
    crunch(6,[0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84]);
    console.log("Correct Answer: 49");
    crunch(2, [0, 21, 31, 45, 49, 54]);
    console.log("Correct Answer: 40");
    crunch(2, [0, 4, 7, 9, 10]);
    console.log("Correct Answer: 7");

    var max = 0;
    var min = Number.POSITIVE_INFINITY;
    var avg = [];

    var score = typeof process.argv[2] === 'undefined' ? 60 : process.argv[2];

    for(j = 0; j<10; j++){
        var arr = []; for(let i of cities(score)) arr.push(i);
        var plants = Math.floor(1 + Math.random() * arr.length);
        console.log(`Running: Test:${j} Plants: ${plants}, Cities ${arr.length}, Score: ${score}`);
        var t0 = performance.now();
        crunch(plants,arr);
        var t1 = performance.now();
        time = (t1-t0)/1000;
        console.log(`Time Taken = ${time} seconds`);
        avg.push(time);
        max = Math.max(time,max);
        min = Math.min(time,min);
    }
    console.log(`Bench: ${avg.reduce((a,b)=>a+b,0)/avg.length} Max: ${max} Min: ${min} Total: ${avg.reduce((a,b)=>a+b,0)}`);
} else {
    var plants = process.argv[2];
    var arr = process.argv.slice(3);
    console.log(`Running: Plants: ${plants}, Cities ${arr.length}`);
    var t0 = performance.now();
    crunch(plants,arr);
    var t1 = performance.now();
    time = (t1-t0)/1000;
    console.log(`Time Taken = ${time} seconds`);
}

```

Try it online!

I will clean up the commented out code over the next couple of days as I am still working on this, just wanted to see if this was passing more than just the small cases.
> 2 votes

# Answer
# C (non-competing, pretest score = 76)

This is an attempt to translate @AndersKaseorg's second Rust solution to C.

```
typedef void V;typedef char C;typedef long L;
#define R return
#define W while
#define S static
#include<sys/syscall.h>
#define exit(x)     ({L r;asm volatile("syscall":"=a"(r):"0"(SYS_exit ),"D"(x)              :"cc","rcx","r11","memory");r;})
#define read(x,y,z) ({L r;asm volatile("syscall":"=a"(r):"0"(SYS_read ),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
#define write(x,y,z)({L r;asm volatile("syscall":"=a"(r):"0"(SYS_write),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
S V P(L x){C s[32],*p=s+32;*--p='\n';do{*--p='0'+x%10;x/=10;}W(x);write(1,p,s+32-p);}
#define N 0x100000 //max
#define INF (-1ul>>1)
S L cost[N],nk1,*am; //nk1:n-k+1, am:input's partial sums offset with the current "m" in _start()
S L f(L i,L j){if(i+1>=j&&cost[j]!=INF){L h=(i-j+1)>>1;R cost[j]+am[i+1]-am[j+h]-am[i-h+1]+am[j];}else{R INF;}}
S V smawk(L sh,L*c,L nc,L*r){ //sh:shift,c:cols,r:result
 L n=nk1>>sh;if(!n)R;
 L m=n>>1,u[m];
 if(n<nc){
  L ns=0,s[nc],sk[nc],*skp=sk;
  for(L jk=0;jk<nc;jk++){
   L j=c[jk];W(ns>0&&f(~(~(ns-1)<<sh),j)<=f(~(~(ns-1)<<sh),s[ns-1])){--ns;--skp;}
   if(ns<n){s[ns++]=j;*skp++=jk;}
  }
  smawk(sh+1,s,ns,u);for(L i=0;i<m;i++)u[i]=sk[u[i]];
 }else{
  smawk(sh+1,c,nc,u);
 }
 L l=0,ish=(1<<sh)-1,dsh=1<<(sh+1);
 for(L i=0;i<m;i++){
  L k=u[i],bj=l,bc=f(ish,c[l]);
  for(L j=l+1;j<=k;j++){L h=f(ish,c[j]);if(h<bc){bc=h;bj=j;}}
  *r++=bj;*r++=k;l=k;ish+=dsh;
 }
 if(n&1){
  L nsh=~(~(n-1)<<sh),bj=l,bc=f(nsh,c[l]);
  for(L j=l+1;j<nc;j++){L h=f(nsh,c[j]);if(h<bc){bc=h;bj=j;}}
  *r=bj;
 }
}
S L inp(L*a){
 L n=-1,l,v=0;C b[1<<20];
 W(0<(l=read(0,b,sizeof(b))))for(L i=0;i<l;i++)if('0'<=b[i]&&b[i]<='9'){v=b[i]-'0'+10*v;}else{a[++n]=v;v=0;}
 R n;
}
V _start(){
 S L a[N];L n=inp(a),k=*a,s=0;for(L i=0;i<n;i++){a[i]=s;s+=a[i+1];}a[n]=s;
 *cost=0;for(L i=1,l=n+1-k;i<l;i++)cost[i]=INF;
 S L c[N];L nc=n+1-k;for(L i=0;i<nc;i++)c[i]=i;
 S L r[N];nk1=n-k+1;for(L m=0;m<k;m++){am=a+m;smawk(0,c,nc,r);for(L i=n-k;i>=0;i--)cost[i]=f(i,r[i]);}
 P(cost[n-k]);exit(0);
}

```

Compile with:

```
#!/bin/bash -e
clang -O3 -nostdlib -ffreestanding -fno-unwind-tables -fno-unroll-loops -fomit-frame-pointer -oa a.c
strip -R.comment -R'.note*' a

```
> 1 votes

# Answer
# Clean, score = 65

```
module main
import StdEnv, System.IO

parseArgs :: *World -> ((Int, {#Int}), *World)
parseArgs world
    # (args, world)
        = nextArgs [] world
    # args
        = reverse args
    # (k, a)
        = (hd args, tl args)
    = ((toInt k, {toInt n \\ n <- a}), world)
where
    nextArgs :: [String] *World -> ([String], *World)
    nextArgs args world
        # (arg, world)
            = evalIO getLine world
        | arg == ""
            = (args, world)
        = nextArgs [arg:args] world

minimalWeight :: Int !{#Int} -> Int
minimalWeight k a
    # count
        = size a
    # touches
        = createArray ((count - k + 3) / 2 * k) 0
    = treeWalk k count a [(0, 0, 0, 0)] touches
where
    treeWalk :: Int !Int {#Int} ![(!Int, !Int, Int, Int)] *{Int} -> Int
    treeWalk k verticies a [(weight, vertex, degree, requires) : nodes] touches
        | vertex >= verticies
            = weight
        | requires >= k
            = treeWalk k verticies a nodes touches
        # index
            = degree * k + requires
        | (select touches index) > vertex
            = treeWalk k verticies a nodes touches
        # (next, pivot)
            = (vertex + 1 + degree, verticies + requires)
        # (nodes, touches)
            = (orderedPrepend (weight, next, 0, requires + 1) nodes, update touches index (vertex + 1))
        | pivot >= k + next
            # (weight, vertex)
                = (weight + (select a next) - (select a vertex), vertex + 1)
            # nodes
                = orderedPrepend (weight, next + 1, 0, requires + 1) nodes
            | pivot == k + next
                = treeWalk k verticies a nodes touches
            # weight
                = weight + (select a (next + 1)) - (select a vertex)
            # nodes
                = orderedPrepend (weight, vertex, degree + 1, requires) nodes
            = treeWalk k verticies a nodes touches
        = treeWalk k verticies a nodes touches
    where
        orderedPrepend :: (!Int, Int, Int, Int) ![(!Int, Int, Int, Int)] -> [(Int, Int, Int, Int)]
        orderedPrepend a []
            = [a]
        orderedPrepend a [b : b_]
            # (x, _, _, _)
                = a
            # (y, _, _, _)
                = b
            | y > x
                = [a, b : b_]
            = [b : orderedPrepend a b_]

Start world
    # ((k, a), world)
        = parseArgs world
    = minimalWeight k a

```

Compile with:
`clm -h 1024M -gci 32M -gcf 32 -s 32M -t -nci -ou -fusion -dynamics -IL Platform main`

Takes `K`, and then each element of `A`, as command-line arguments.
> 1 votes

---
Tags: fastest-code
---