title: The Colors in Our Stars

text:
# Question
Title: The Colors in Our Stars
Write a program that takes in a string or text file whose first line has the form

```
width height

```

and each subsequent line has the form

```
x y intensity red green blue

```

where:

* `width` and `height` may be any positive integers.
* `x` and `y` may be any integers.
* `intensity` may be any non-negative integer.
* `red`, `green`, and `blue` may be any integers from 0 to 255 inclusive.

Your program must output a truecolor image in any common lossless image file format whose dimensions are `width` by `height`. Each `x y intensity red green blue` line represents a colorful star or orb that must be drawn on the image. There may be any number of stars to draw, including 0. You may assume the string or file has a trailing newline.

The algorithm for drawing the image is as follows, though you may implement it in any way you like as long as the result is identical:

> For every pixel (*X*,*Y*) in the image (where *X* is 0 at the leftmost edge and *width-1* at the rightmost edge, and *Y* is 0 at the top edge and *height-1* at the bottom edge), the color channel *C* ϵ {*red*, *green*, *blue*} (a value pinned between 0 to 255) is given by the equation:
>
> Where the *dist* function is either Euclidean distance:
>
> Or Manhattan distance:
>
> Choose whichever distance function you prefer, based on golfability or aesthetics.
>
> Each of the lines in the input besides the first is an element of the *Stars* set. So, for example, Sx represents the `x` value on one of the input lines, and SC represents either `red`, `green`, or `blue`, depending on which color channel is currently being calculated.

# Examples

### Example A

If the input is

```
400 150
-10 30 100 255 128 0

```

the output should be

if you're using Euclidean distance, and

if you're using Manhattan distance.

### Example B

If the input is

```
200 200
100 100 10 255 255 255
20 20 40 255 0 0
180 20 40 255 255 0
180 180 40 0 255 0
20 180 40 0 0 255

```

the respective outputs for Euclidean and Manhattan distance should be

and .

### Example C

If the input is

```
400 400
123 231 10 206 119 85
358 316 27 170 47 99
95 317 3 202 42 78
251 269 17 142 150 153
43 120 3 145 75 61
109 376 6 230 231 52
331 78 21 31 81 126
150 330 21 8 142 23
69 155 11 142 251 199
218 335 7 183 248 241
204 237 13 112 253 34
342 89 18 140 11 123

```

the output should be

if you're using Euclidean distance, and

if you're using Manhattan distance.

### Example D

If the input is

```
400 400
123 231 5 206 119 85
358 316 5 170 47 99
95 317 5 202 42 78
251 269 5 142 150 153
43 120 5 145 75 61
109 376 5 230 231 52
331 78 5 31 81 126
150 330 5 8 142 23
69 155 5 142 251 199
218 335 5 183 248 241
204 237 5 112 253 34
342 89 5 140 11 123

```

the output should be

if you're using Euclidean distance, and

if you're using Manhattan distance.

### Example E

If the input is

```
100 1

```

then the output should be a 100 pixel wide by 1 pixel tall image that is completely black.

# Notes

* Take the input string or the name of a text file that contains it from stdin or the command line, or you may write a function that takes in a string.
* "Outputting" the image means either:
    + Saving it to a file with the name of your choice.
    + Printing the raw image file data to stdout.
    + Displaying the image, such as with PIL's `image.show()`.
* I won't be checking that your images are pixel perfect (Stack Exchange lossily compresses images anyway) but I will be very suspicious if I can visually tell any difference.
* You may use graphics/image libraries.

# Winning

The shortest submission in bytes wins. In case of ties, the earliest submission wins.

*Fun Bonus:* Give the input for a truly spectacular output image.

# Answer
# Pyth - 46 bytes

This was fun! I finally got to use Pyth's image I/O features. Does euclidean distance because of golfiness, though manhattan is just a short change.

```
Krz7.wcmmsm/*@b+3k@b2h.a,<b2_.DdhKrR7.zU3*FKhK

```

This just loops through all the pixels with the formula's though it condenses the pixel loop into one loop and uses `divmod` since Pyth only supports 3 nested maps and the calculations take two (one for RGB and one for the stars).

Saves image as `o.png`. Pretty slow, does the first 2 tests in \<2 min, but the other 2 take on the order of half an hour.

There is a bug in `.w` that no one noticed because no one uses it ;) but I put in a pull request so use my fork to test if isn't merged soon. Merged!

## Examples Outputs

### Example A

### Example B

## Example C

### Example D
> 26 votes

# Answer
# JavaScript ~~394~~ 344

```
function X(a){for(l=a.match(/\d+/g),h=document,v=h.body.appendChild(h.createElement("canvas")),v.width=W=l[0],v.height=H=l[1],w=v.getContext("2d"),e=w.createImageData(W,H),d=e.data,N=W*H;N--;)for(i=2,c=N*4,d[c+3]=255;i<l.length;)for(x=N%W-l[i++],y=~~(N/W)-l[i++],k=l[i++],q=0;q<3;)d[c+q++]+=k*l[i++]/-~Math.sqrt(x*x+y*y);w.putImageData(e,0,0);}

```

**Edit:** shortened the code a lot by applying wolfhammer's awesome suggestions.

### Test

*Note: Wait a few seconds for the snippet below to render (takes ~4 seconds on my machine).*

```
function X(a){for(l=a.match(/\d+/g),h=document,v=h.body.appendChild(h.createElement("canvas")),v.width=W=l[0],v.height=H=l[1],w=v.getContext("2d"),e=w.createImageData(W,H),d=e.data,N=W*H;N--;)for(i=2,c=N*4,d[c+3]=255;i<l.length;)for(x=N%W-l[i++],y=~~(N/W)-l[i++],k=l[i++],q=0;q<3;)d[c+q++]+=k*l[i++]/-~Math.sqrt(x*x+y*y);w.putImageData(e,0,0);}

var start = Date.now();

X("400 150\n" +
  "-10 30 100 255 128 0");

X("200 200\n" +
  "100 100 10 255 255 255\n" +
  "20 20 40 255 0 0\n" +
  "180 20 40 255 255 0\n" +
  "180 180 40 0 255 0\n" +
  "20 180 40 0 0 255");

X("400 400\n" +
  "123 231 10 206 119 85\n" +
  "358 316 27 170 47 99\n" +
  "95 317 3 202 42 78\n" +
  "251 269 17 142 150 153\n" +
  "43 120 3 145 75 61\n" +
  "109 376 6 230 231 52\n" +
  "331 78 21 31 81 126\n" +
  "150 330 21 8 142 23\n" +
  "69 155 11 142 251 199\n" +
  "218 335 7 183 248 241\n" +
  "204 237 13 112 253 34\n" +
  "342 89 18 140 11 123");

X("400 400\n" +
  "123 231 5 206 119 85\n" +
  "358 316 5 170 47 99\n" +
  "95 317 5 202 42 78\n" +
  "251 269 5 142 150 153\n" +
  "43 120 5 145 75 61\n" +
  "109 376 5 230 231 52\n" +
  "331 78 5 31 81 126\n" +
  "150 330 5 8 142 23\n" +
  "69 155 5 142 251 199\n" +
  "218 335 5 183 248 241\n" +
  "204 237 5 112 253 34\n" +
  "342 89 5 140 11 123");

var end = Date.now();

console.log('Done in ' + (end - start)/1000 + 's.');
```

```
canvas {
  display: block;
  padding: 10px;
}
```

You can also run it in JSFiddle.

### Bonus: Blue Eclipse

```
function X(a){for(l=a.match(/\d+/g),h=document,v=h.body.appendChild(h.createElement("canvas")),v.width=W=l[0],v.height=H=l[1],w=v.getContext("2d"),e=w.createImageData(W,H),d=e.data,N=W*H;N--;)for(i=2,c=N*4,d[c+3]=255;i<l.length;)for(x=N%W-l[i++],y=~~(N/W)-l[i++],k=l[i++],q=0;q<3;)d[c+q++]+=k*l[i++]/-~Math.sqrt(x*x+y*y);w.putImageData(e,0,0);}

var j = 0;
var renderFrame = function () {
  if(window.h && window.v){h.body.removeChild(v);} // clear prev frame
  X("225 150\n" +
    (70 + j) + " " + (120 - j) + " 170 135 56 0\n" +
    j * 5 + " " + j * 3 + " 64 0 50 205");
  if(++j < 50) { setTimeout(renderFrame, 1); } else { console.log('done!'); }
};
setTimeout(renderFrame, 10);
```

You can also run it in JSFiddle.

### Description

This is a straightforward JavaScript + HTML5 canvas implementation: a function that takes a string argument (without trailing spaces/newlines) and displays the output in the DOM. It uses Euclidean distance.

Here is the readable code:

```
X = function (str) {
  var lines = str.split("\n");
  var canvas = document.createElement('canvas');
  var z = lines[0].split(u=' ');
  var width = z[0], height = z[1];

  canvas.width = width;
  canvas.height = height;
  document.body.appendChild(canvas);

  var ctx = canvas.getContext("2d");
  var imageData = ctx.createImageData(width, height);

  for(var y = 0; y < height; y++){
    for(var x=0; x < width; x++){
      var coord = (y * width + x) * 4;

      for(i=1; i < lines.length;i++){
        var t = lines[i].split(u);

        var
          dx = x - t[0],
          dy = y - t[1];

        var distance = Math.sqrt(dx * dx + dy * dy);

        for(var channel = 0; channel < 3; channel++) {
          var channelIndex = coord + channel;
          imageData.data[channelIndex] += t[2] * t[3 + channel] / (distance + 1);
        }
      }

      var alphaIndex = coord + 3;
      imageData.data[alphaIndex] = 255;
    }
  }

  ctx.putImageData(imageData, 0, 0);
};

```
> 43 votes

# Answer
# Java - 627 bytes

Java is indeed one of the best golfing languages :)

```
import java.awt.image.*;class M{void f(String n)throws Exception{String[]p=n.split("\n");int[]b=s(p[0]);BufferedImage o=new BufferedImage(b[0],b[1],2);for(int i=0;i<b[0];i++)for(int j=0;j<b[1];j++){int[]c=new int[3];for(int l=1;l<p.length;l++){int[]r=s(p[l]);for(int k=0;k<3;k++){c[k]+=r[2]*r[3+k]/(Math.sqrt(Math.pow(i-r[0],2)+Math.pow(j-r[1],2))+1);if(c[k]>255)c[k]=255;}}o.setRGB(i,j,new java.awt.Color(c[0],c[1],c[2]).getRGB());}javax.imageio.ImageIO.write(o,"png",new java.io.File("o.png"));}int[]s(String s){String[]a=s.split(" ");int[]r=new int[a.length];for(int i=0;i<a.length;i++)r[i]=Integer.valueOf(a[i]);return r;}}

```

Using the input below, you can create a somewhat realistic model of our solar system (the size of some planets is wrong, but the distance between them should be accurate). I tried to give rings to saturn, but it didn't work... Source

```
1950 50
-15 25 25 255 255 0
39 25 1 255 0 0
55 25 3 255 140 0
68 25 4 0 191 255
92 25 2 255 0 0
269 25 10 245 222 179
475 25 7 245 245 220
942 25 6 0 250 150
1464 25 6 0 0 255
1920 25 1 255 245 238

```

Full HD picture, which doesn't look thaaat great... Would be happy if someone could improve it!
> 27 votes

# Answer
# Bash, ~~147~~ 145 bytes

ImageMagick is used to manipulate images. Euclidean distance is used.

```
read w h
o=o.png
convert -size $w\x$h canvas:black $o
while read x y i r g b
do
convert $o -fx "u+$i*rgb($r,$g,$b)/(hypot(i-$x,j-$y)+1)" $o
done

```
> 20 votes

# Answer
## Python 3, 189 bytes

I'm nobody's idea of an expert golfer, but here goes.

* Input comes from `stdin` and goes to `stdout` in PPM format.
* Run it like so: `python3 codegolf_stars_golfed.py < starfield.txt > starfield.pnm`

First, Manhattan distance:

```
import sys
(w,h),*S=[list(map(int,l.split()))for l in sys.stdin]
print('P3',w,h,255,*(min(int(sum((I*C[z%3]/(abs(X-z//3%h)+abs(Y-z//3//h)+1))for
X,Y,I,*C in S)),255)for z in range(h*w*3)))

```

And secondly, Euclidean distance:

```
import sys
(w,h),*S=[list(map(int,l.split()))for l in sys.stdin]
print('P3',w,h,255,*(min(int(sum((I*C[z%3]/(abs(X-z//3%h+(Y-z//3//h)*1j)+1))for
X,Y,I,*C in S)),255)for z in range(h*w*3)))

```

I could save four bytes by using integer division instead of `int()`, and in fact that seems to be what the original images do--you can just barely make out some striations in the dark fringes of the star glow that aren't present in strictly correct code. As it stands, though, this code follows the description, not the images.

The ungolfed version, and my original golfing before the many optimisations that others pointed out or that I stumbled upon myself, are in this gist.

**EDIT:** I saved 7 bytes by moving `for x` and `for y` into a single `print` (or `o`) function, but this produces a PNM file with a very long line, which may or may not cause some problems.

**EDIT 2:** Maltysen saved me another 20 bytes. Thanks!

**EDIT again:** Now that there's only one `print`, the `o` alias is a liability, not a saving. 4 more bytes off.

**EDIT some more:** Sp3000 saved me 2 more bytes. Meanwhile, aliasing `map` to `m` wasn't saving anything, so in the interests of readability(!) I've expanded it again. It's now a nice round 28 bytes.

**EDIT the last(?):** Now with Euclidean distance support--and by abusing complex numbers, I did it in exactly the same number of bytes!

**EDIT, the Hollywood reboot:** Sp3000's next suggestion knocked off 5 bytes.

**EDIT, the stupidly named sequel:** 6 bytes trimmed off, thanks to a suggestion Maltysen made that I didn't grasp until Sp3000 repeated it... then *another* 8 bytes from `%` abuse. And talking it out in chat knocked off a phenomenal ~~21~~ 26 bytes. I'm humbled.
> 16 votes

# Answer
# C++, 272 bytes

```
#include<png.hpp>
#define G(a)i>>C;for(x=0;x<w*h;++x){auto&p=img[x%h][x/h];c=p.a+I*C/(abs(x/h-X)+abs(x%h-Y)+1);p.a=c>255?255:c;}
auto&i=std::cin;main(){int w,h,x,X,Y,I,c,C;i>>w>>h;png::image<png::rgb_pixel>img(w,h);while(i>>X>>Y>>I){G(red)G(green)G(blue)}img.write("a");}

```

Needs a lenient C++11 compiler (GCC 4.9.2 is only slightly displeased), and the png++ library, which itself requires `libpng`. Manhattan distance used. Takes input on `stdin`, outputs to a file named "a" in the current directory in PNG format.

Example D:

---

---
> 11 votes

# Answer
# Python 2, ~~240~~ ~~232~~ 228 bytes

```
from PIL.Image import*
def f(S):
 L=map(int,S.split());t=a,b=L[:2];I=new("RGB",t)
 for k in range(a*b):I.load()[k/a,k%a]=tuple(sum(x[2]*x[c]/(abs(x[0]-k/a)-~abs(x[1]-k%a))for x in zip(*[iter(L[2:])]*6))for c in(3,4,5))
 I.show()

```

Uses Manhattan distance. This would probably be even shorter in Python 3, but I messed up my Python packages recently and I'm having trouble reinstalling Pillow. PPM would probably be even shorter, but I like PIL.

For fun, I tried to apply the algorithm as is in the L\*a\*b\* color space instead, thinking it would give better colour blending (especially in example B). Unfortunately, Calvin's algorithm lets channels go over their max values, which makes the images look a little less awesome than I hoped...
> 8 votes

# Answer
# Python 2, ~~287~~ 251 bytes

A golfed version of the original code I used to generate the images. Could probably be golfed a bit more (by a better golfer than me). It's a function that takes in the full input string. Image processing done with PIL's Image Module. Uses Manhattan distance.

```
from PIL import Image
def S(I,r=range):
 I=map(int,I.split());w,h=I[:2];M=Image.new('RGB',(w,h));P=M.load()
 for z in r(w*h):
  P[z%w,z/w]=tuple(int(sum(I[i+2]*I[i+j+3]/(1.+abs(I[i]-z%w)+abs(I[i+1]-z/w))for i in r(2,len(I),6)))for j in r(3))
 M.show()

```

Using Euclidean distance is 5 bytes longer (256 bytes):

```
from PIL import Image
def O(I,r=range):
 I=map(int,I.split());w,h=I[:2];M=Image.new('RGB',(w,h));P=M.load()
 for z in r(w*h):
  P[z%w,z/w]=tuple(int(sum(I[i+2]*I[i+j+3]/(1+((I[i]-z%w)**2+(I[i+1]-z/w)**2)**.5)for i in r(2,len(I),6)))for j in r(3))
 M.show()

```

Here's a complete test suite that runs examples A through E from the question, for both distance metrics:

```
from PIL import Image
def S(I,r=range):
 I=map(int,I.split());w,h=I[:2];M=Image.new('RGB',(w,h));P=M.load()
 for z in r(w*h):
  P[z%w,z/w]=tuple(int(sum(I[i+2]*I[i+j+3]/(1.+abs(I[i]-z%w)+abs(I[i+1]-z/w))for i in r(2,len(I),6)))for j in r(3))
 M.show()

def O(I,r=range):
 I=map(int,I.split());w,h=I[:2];M=Image.new('RGB',(w,h));P=M.load()
 for z in r(w*h):
  P[z%w,z/w]=tuple(int(sum(I[i+2]*I[i+j+3]/(1+((I[i]-z%w)**2+(I[i+1]-z/w)**2)**.5)for i in r(2,len(I),6)))for j in r(3))
 M.show()

A = """400 150
-10 30 100 255 128 0"""
B = """200 200
100 100 10 255 255 255
20 20 40 255 0 0
180 20 40 255 255 0
180 180 40 0 255 0
20 180 40 0 0 255"""
C = """400 400
123 231 10 206 119 85
358 316 27 170 47 99
95 317 3 202 42 78
251 269 17 142 150 153
43 120 3 145 75 61
109 376 6 230 231 52
331 78 21 31 81 126
150 330 21 8 142 23
69 155 11 142 251 199
218 335 7 183 248 241
204 237 13 112 253 34
342 89 18 140 11 123"""
D = """400 400
123 231 5 206 119 85
358 316 5 170 47 99
95 317 5 202 42 78
251 269 5 142 150 153
43 120 5 145 75 61
109 376 5 230 231 52
331 78 5 31 81 126
150 330 5 8 142 23
69 155 5 142 251 199
218 335 5 183 248 241
204 237 5 112 253 34
342 89 5 140 11 123"""
E = """100 1"""
for i in (A, B, C, D, E):
    S(i) #S for Star
    O(i) #O for Orb

```

They all look indistinguishable. The larger ones may take a few seconds to run.
> 6 votes

# Answer
# Mathematica, 146 bytes

```
Image@Table[Total[#3{##4}/255&@@@{##2}/(1+#~ManhattanDistance~{x,y}&/@({#1,#2}&@@@{##2}))],{y,0,Last@#-1},{x,0,#&@@#-1}]&@@#~ImportString~"Table"&

```

A pure function taking a string. To run it in a reasonable amount of time, replace the `1` in `1+#~ManhattanDistance...` with a `1.`; this forces numeric computation instead of symbolic.

Ungolfed:

```
Image[
    Table[
        Total[
        (#3 * {##4} / 255 & @@@ {##2})
            / (1 + ManhattanDistance[#, {x, y}]& /@ ({#1, #2}& @@@ {##2}) )
        ], {y, 0, Last[#]-1}, {x, 0, First[#]-1}
    ] (* Header is #, data is {##2} *)
]& @@ ImportString[#, "Table"]&

```
> 6 votes

# Answer
# C, 247 bytes

Not going to win, but I like to golf in C. No external image library used, outputs to stdout in PPM format. Takes input on stdin. Uses Manhattan distance for golfiness.

```
j,w,h,k,*b,t[6];main(){scanf("%d %d",&w,&h);b=calloc(w*h,24);for(;~scanf("%d",t+j++%6);)for(k=0;j%6?0:k<3*w*h;k++)b[k]=fmin(b[k]+t[2]*t[3+k%3]/(abs(k/3%w-*t)+abs(k/3/w-t[1])+1),255);printf("P6\n%d %d\n255\n",w,h);for(k=0;k<3*w*h;putchar(b[k++]));}

```

Here's the Euclidean distance variant (257 bytes):

```
j,w,h,k,*b,t[6];main(){scanf("%d %d",&w,&h);b=calloc(w*h,24);for(;~scanf("%d",t+j++%6);)for(k=0;j%6?0:k<3*w*h;k++)b[k]=fmin(b[k]+t[2]*t[3+k%3]/(sqrt(pow(k/3%w-*t,2)+pow(k/3/w-t[1],2))+1),255);printf("P6\n%d %d\n255\n",w,h);for(k=0;k<3*w*h;putchar(b[k++]));}

```
> 6 votes

# Answer
# CJam, 86 bytes

```
q~]"P3 "\_2>:T;2<_S*" 255 "@:,~\m*{(+0a3*T6/{_2<3$.-:z~+)d\2>(f*\f/.+}/:i255fe<\;S*S}/

```

While this may look kind of lengthy for a golfing language, I believe that of the solutions posted so far, it's the shortest that does not use image output functionality. This produces a PPM file in ASCII form. The image below was converted from PPM to PNG using GIMP.

I do not recommend to run the code in the online CJam interpreter. At least not for the full size images. My browser locked up, most likely because of the memory usage. It completes the 400x400 images in the second range with the offline version.

Explanation:

```
q~      Read and parse input.
]       Wrap it in an array.
"P3 "   Output start of PPM header.
\       Swap input to top.
_2>     Slice off first two values, leaving the star descriptors.
:T;     Store star descriptors in variable T.
2<      Get first two values in input, which is the image size.
_S*     Leave a copy of the size in the output for the PPM header.
" 255 " Rest of PPM header, range of color values.
@       Pop sizes to top.
:,      Expand sizes to ranges.
~       Unwrap size ranges into separate stack elements.
\       Swap ranges, since we need x-range second for Cartesian product.
m*      Generate all coordinate pairs with Cartesian product.
{       Loop over pixel coordinate pairs.
  (+      Swap values in coordinate pair to get x-coordinate first again.
  0a3*    Generate [0 0 0] array. Will be used to sum up colors from stars.
  T       Get list of stars.
  6/      Split into sub-lists with 6 values for each star.
  {       Loop over the stars.
    _2<     Get the first two values (position) of the star.
    3$      Pull current pixel coordinates to top of stack.
    .-      Subtract pixel coordinates from star position.
    :z      Absolute value of difference.
    ~+      Unpack differences and add them to get Manhattan distance.
    )d      Add 1 and convert to double to get denominator of formula.
    \       Swap star values to top.
    2>      Slice off first two values, leaving intensity and color.
    (       Pop off intensity.
    f*      Multiply it with color values.
    \       Swap denominator to top.
    f/      Perform division of color components by denominator.
    .+      Add it to sum of colors.
  }/      End loop over stars.
  :i      Convert double values for colors to integer.
  255fe<  Cap color components at 255.
  \;      Swap pixel coordinate to top and pop it.
  S*S     Join color components with space, and add another space.
}/      End loop over coordinate pairs.

```
> 6 votes

# Answer
# C# 718 bytes

I realize that c# is terrible for golfing, but here's my attempt at 718 bytes

```
namespace System{using Collections.Generic;using Drawing;using Linq;using O=Convert;class P{int j,i;List<S> s=new List<S>();Image G(string t){var l=t.Replace("\r","").Split('\n');var w=O.ToInt32(l[0].Split(' ')[0]);var h=O.ToInt32(l[0].Split(' ')[1]);for(i=1;i < l.Length;i++){var p=l[i].Split(' ');s.Add(new S{X=O.ToInt32(p[0]),Y=O.ToInt32(p[1]),I=O.ToSingle(p[2]),R=O.ToByte(p[3]),G=O.ToByte(p[4]),B=O.ToByte(p[5])});}var b=new Bitmap(w,h);for(j=0;j<h;j++)for(i=0;i<w;i++)b.SetPixel(i,j,C());return b;}Color C(){return Color.FromArgb(X(x=>x.R),X(x=>x.G),X(x=>x.B));}int X(Func<S,float>f){return(int)Math.Min(s.Sum(x=>x.I*f(x)/(Math.Sqrt((x.X-i)*(x.X-i)+(x.Y-j)*(x.Y-j))+1)),255);}class S{public float X,Y,R,G,B,I;}}}

```

If anyone has any suggestions to shorten it, feel free to let me know.
> 5 votes

# Answer
# Python, 259 bytes

Finally done! First code golf I've tried, decided to use Python and went with the Manhattan distance. Shoutout to Maltysen for helping me with the iterators, reduced the total size to almost half!

```
from PIL.Image import new
N,*s=[list(map(int,i.split()))for i in iter(input,'')]
q,m=new("RGB",(N[0],N[1])),[]
[m.append(tuple(sum(k[2]*k[i]//(abs(k[1]-x)+abs(k[0]-y)+1)for k in s)for i in(3,4,5)))for x in range(N[1])for y in range(N[0])]
q.show(q.putdata(m))

```
> 4 votes

# Answer
# CJam, 70 bytes

```
"P3"l_~\:W*255\,[q~]6Te]6/f{\[Wmd\]f{.-Z/~\)\~mh)/f*}:.+{i255e<}/}~]S*

```

Euclidean distance, ASCII PPM output. Try it online

It should be possible to squeeze a few more bytes, but I don't want to spend too much time.
> 2 votes

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


title: Interpreted Interpreter

text:
# Question
Title: Interpreted Interpreter
Duplicate? I knew somebody must've done this before.

---

Programming a programming language in itself is something that has interested me since I knew what a programming language was. So I thought I'd create a Code Golf challenge for you.

## Challenge

Create an interpreter for a given programming language, programmed entirely in itself. The interpreter should be able to run any valid program in that language, including itself.

### Inputs:

The program can take it's input as a file passed as a parameter (e.g. `python myfile.py`) or as lines from stdin (`cat myfile.py | python`).

### Outputs:

Whatever an interpreter would normally output, on the correct streams (stdout, stderr etc.)

## Specifications

* The code needs to be written in an interpretable language, and serve as an interpreter for its own language.
* It can't use an `eval()` function to interpret code.
* It must run any valid program in that language. If the language allows external modules (or includes), it must be able to read those modules.
* This task is code golf. The submission with the least characters that is correct wins. In case of a tie, the solution that was submitted first wins.

### Loophole remover:

* Yes, if you can interpret Java, Bytecode or HQ9++ in themselves, go ahead!
* In JavaScript / ES, using HTML tags such as `<script>` is not allowed.

# Answer
# Nothing, 0 chars

The source code is an empty file. It does nothing, like any Nothing program, therefore it is the correct execution of every such program.
> 10 votes

# Answer
# JavaScript ES6, 44 bytes/chars

```
s=>document.write(`<${t='script>'}${s}</`+t)

```

Defines a function, taking the code string as a parameter.

**How it works:**

This function simply takes the code, wraps it in `<script>` tags, and writes it into the page. It doesn't use the `eval` function at all - the browser simply runs the code when the new `<script>` element is inserted into the page.

**Tested in the FireFox console on the `about:blank` page as follows:**

```
(s=>document.write(`<${t='script>'}${s}</`+t))("alert('hi')")

```

*Yes, this is probably a loophole and as such I don't really expect to win. (It's impossible to beat the Nothing answer, anyway...)*

*If anything, hopefully it shows how it is possible to evaluate code in javascript without the use of the `eval` function.*
> 3 votes

---
Tags: code-golf, interpreter
---


# Question
Title: Determine the move in which a LOGO turtle crosses a point that it has already visited
**Situation**:

1. A turtle starts at (0, 0) on a cartesian graph.
2. We have a non-empty zero-indexed "moves" list that contains numbers.
3. Each number represents the distance moved.
4. The first number is the distance north, the second is the distance east, the third is the distance south, the fourth is the distance west, and repeats like this forever. Therefore the directions cycle every four moves.

**Goal:**

Find an algorithm that gives the move number that makes the turtle cross a point that it has already visited before.

The move number is the *index of the "moves" list*.

This algorithm should preferably be O(n).

**Example:**

If given this move list: `[1, 3, 2, 5, 4, 4, 6, 3, 2]`

The move number answer is then 6. (It's the 7th move).

Draw it on a graph, the turtle will go:

(0,0) -\> (0,1) -\> (3,1) -\> (3,-1) -\> (-2,-1) -\> (-2,3) -\> (2,3) -\> (2,-3)

At this 6 move number (7th move) it will meet (2,1) which is a point that the turtle has already crossed.

**Example Implementation**

Here was my try in PHP (I think it's kind of like O(n\*(m+m)) where m is the average size of the distance):

```
/**
 * Logo Turtle Challenge
 * This solution is somewhat space inefficient, and could become time inefficient if the distance range for a particular move is huge!
 * There is probably a solution that allows you to persist only the corner coordinates and then using line equations to figure out if they intersect.
 * The space inefficiency could be partially solved with a lazy range generator.
 * Could be further micro-optimised by only checking the coordinates on the fourth[3] movement.
 */

function logo_turtle($movements) {

    $coordinates = [0 => [0 => true]];
    $current_coordinate = [
        'x' => 0,
        'y' => 0
    ];
    $directions = ['n', 'e', 's', 'w'];

    foreach($movements as $move => $distance){

        // cycle through the directions
        $current_direction = array_shift($directions);
        array_push($directions, $current_direction);

        // if the distance is less than 1, then skip it, but we still cycle the direction!
        if ($distance < 1) {
            continue;
        }

        // clean slate
        $coordinates_to_check = [];

        // for each direction, acquire a list of coordinates derived from its traverse
        // these coordinates will be used to check if turtle crosses its own previous path
        switch($current_direction){
            case 'n':

                $x_end = $current_coordinate['x'];
                $y_end = $current_coordinate['y'] + $distance;

                $start = $current_coordinate['y'] + 1;
                foreach(range($start, $y_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $current_coordinate['x'], 'y' => $value];
                }

            break;
            case 'e':

                $x_end = $current_coordinate['x'] + $distance;
                $y_end = $current_coordinate['y'];

                $start = $current_coordinate['x'] + 1;
                foreach(range($start, $x_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $value, 'y' => $current_coordinate['y']];
                }

            break;
            case 's':

                $x_end = $current_coordinate['x'];
                $y_end = $current_coordinate['y'] - $distance;

                $start = $current_coordinate['y'] - 1;
                foreach(range($start, $y_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $current_coordinate['x'], 'y' => $value];
                }

            break;
            case 'w':

                $x_end = $current_coordinate['x'] - $distance;
                $y_end = $current_coordinate['y'];

                $start = $current_coordinate['x'] - 1;
                foreach(range($start, $x_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $value, 'y' => $current_coordinate['y']];
                }

            break;
        }

        // if the traversal meets one of the existing coordinates, then the current move is an interception
        foreach($coordinates_to_check as $xy){

            if(
                isset(
                    $coordinates[
                        $xy['x']
                    ][
                        $xy['y']
                    ]
                )
            ){
                return $move;
            }

            // add the point to the list of coordinates that has been traversed
            $coordinates[$xy['x']][$xy['y']] = true;

        }

        // update the current coordinate for the next iteration
        $current_coordinate = [
            'x' => $x_end,
            'y' => $y_end
        ];

    }

    return -1;

}

$moves = [1, 3, 2, 5, 4, 4, 6, 3, 2];
$turtle_move = logo_turtle($moves); // returns 6

```

**Criteria:**

1. Feel free to write it in any language you want.
2. Winning algorithm is the first one that is published with an O(n) implementation.
3. With regards to algorithms with the same time complexity class, whichever code has the least amount of characters win.
4. Time limit is the best answer by 30th November 2014.

# Answer
> 5 votes
# C, O(n), 65 95 102 bytes

After I made at least one additional test case, some more code naturally needed to be added.

Thanks to Serge Mosin for finding another bug.

```
k(int*m){int*i=m;for(;2[i]>*i++;);for(*i-=i[~1]*(1[i]+(i-m>2)*i[~2]>=i[-1]);2[i]<*i++;);return 1+i-m;}

```

**Test cases**:

```
int a[] = {1, 3, 2, 5, 4, 4, 6, 3, 2}; // -> 6
int b[] = {4, 4, 5, 7, 8, 6, 5}; // -> 6
int c[] = {1, 1, 2, 1, 1}; // -> 4

```

Behavior is unspecified if there is a 0 in the array, since OP didn't specify whether that counts as the path crossing itself. Also, it is assumed that the path does cross at some point.

It might be undefined behavior to have `2[i] > *i++` but in code golf, that's like (negative) bonus points.

The first loop processes the part of the path that forms an outward spiral, which continues as long as each segment is longer than the previous parallel segment. The second loop traverses an inward spiral, in which each segment is shorter than the previous segment. At the beginning of the second spiral, there needs to be an adjustment to detect a possible collision with the previous stuff.

# Answer
> 3 votes
Here is a solution in JavaScript

```
function turtle(A) {
    for (i=3;i<A.length;i++) {
        if (A[i-1] <= A[i-3] && (A[i] >= A[i-2] || A[i-1] >= A[i-3]-(A[i-5] || 0) && A[i] >= A[i-2]-A[i-4] && A[i-2] >= A[i-4]))
            return i
    }
    return -1
}

```

Test Cases

```
var a = [1, 3, 2, 5, 4, 4, 6, 3, 2] // -> 6
var b = [4, 4, 5, 7, 8, 6, 5] // -> 6
var c = [1, 1, 2, 1, 1] // -> 4
var d = [1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10] // -> 8
var e = [1, 1, 1, 1] // -> 3
var f = [1, 1, 5, 3, 3, 2, 2, 1, 1, 3] // -> 9
var g = [1, 2, 2, 1, 1] // -> -1

```

Basically the turtle can only cross if the line from one time ago is less than or equal to the line from three times ago. Then check two cases, one where the current line is greater than or equal to the line from two times ago, and one where the current line crosses the line from five times ago.

The question doesn't specify what happens if the turtle moves 0. If that would be considered crossing his own path it would be easy to check for. If not, it would complicate things a bit.

# Answer
> 1 votes
I've made this teste just yesterday. This is my Objective-C version. It not meant to be the perfect, the latest and blah blah blah that Cordiality cries for, but a enough and readable version:

Its check the segment on vertical or horizontal to check if any previous drawn will be crossed.

https://gist.github.com/dbonates/818d6cea288a81cf888f

Hope it helps, if anyone wanna improve it feel free :)

Here goes the code as asked:

```
#import <Foundation/Foundation.h>

// Determine the move in which a LOGO turtle crosses a point that it has already visited

BOOL isBetween(int valueToTest, int limitOne, int limitTwo) {

    if (limitOne > limitTwo) {
        return (limitTwo <= valueToTest && valueToTest <= limitOne);
    } else {
        return (limitOne <= valueToTest && valueToTest <= limitTwo);
    }
}
int stepColistionCheck(NSMutableArray *stepsArray) {

    // NSLog(@"stepsArr: [%@]", [stepsArray componentsJoinedByString:@","] );

    int cx = 0;
    int cy = 0;

    int len = (int)[stepsArray count];

    // array with x and y position on grid
    NSMutableArray *deltaArray = [NSMutableArray array];

    for (int i=0; i<len; i++) {

        int direction = i%4;

        switch (direction) {
            case 0: // going NORTH
                cy -= [stepsArray[i] integerValue];
                [deltaArray addObject:@(cy)];
                break;

            case 1: // going EAST
                cx += [stepsArray[i] integerValue];
                [deltaArray addObject:@(cx)];
                break;

            case 2: //going SOUTH
                cy += [stepsArray[i] integerValue];
                [deltaArray addObject:@(cy)];
                break;

            case 3: //going WEST
                cx -= [stepsArray[i] integerValue];
                [deltaArray addObject:@(cx)];
                break;

            default:
                break;
        }
    }

    // array de deltas produzidos
    // NSLog(@"deltaArray: [%@]\n\n", [deltaArray componentsJoinedByString:@","] );

    // testing starting from third (the first that could colide, with the first vertical     in this case)
    for (int i=3; i< len; i++) {

        //check if will test horizontal colliding or vertical
        // 0, stands for vertical, 1 for horizontal
        int orientation = i%2;

        if (orientation == 0) { //vertical

            // the x value for this vertical segment is equal do the x from previous one
            int segmentX = [deltaArray[i-1] intValue];

            // NSLog(@"- testing vertical segment at index: %d, myX = %d:", i, segmentX);

            //loop from first horizontal to here
            // j is the horizontal segment
            int previousValue;

            for (int j=1; j < i; j+=2) {

                // first test, cant be adjacents
                if (j != (i-1) && j != (i+1)) {

                    if (j < 2) {
                        previousValue = 0;
                    } else {
                        previousValue = [deltaArray[j-2] intValue];
                    }

                    // trying to find if my x (segmentX) is between the values:     previousValue e [deltaArray[j] intValue]

                    if (isBetween(segmentX, [deltaArray[j] intValue], previousValue)) {

                        // NSLog(@"\tok, found candidate horizontal contains myX at     index %d", j);

                        // that horizontal segment contains my x,
                        // now I should check for y interpolation

                        // the y for current horizontal candidate for colision,
                        // is the y value before this index on delta array

                        int canditateY;
                        canditateY = [deltaArray[j-1] intValue];

                        // the Y of this horizontal segment found (canditateY), must me     in my y range, between [deltaArray[i] intValue] and [deltaArray[    i-2] intValue]

                        if (isBetween(canditateY, [deltaArray[i] intValue], [deltaArray[    i-2] intValue])) {
                            // the candidate Y has been found on current range of y for     this segment
                            // NSLog(@"\t\t***** FOUND SEGMENT THAT CROSS at index step     %d", (i+1));
                            return (i+1);
                        }
                    }
                }
            }

        }
        else if (orientation == 1) { //horizontal

            int segmentY = [deltaArray[i-1] intValue];

            // NSLog(@"- testing horizontal in index: %d, myY = %d:", i, segmentY);

            //loop from first vertical to here
            // j is the vertical segment
            int previousValue;

            // test which includes my x
            for (int j=0; j < i; j+=2) {

                if (j<1) {
                    previousValue = 0;
                } else {
                    previousValue = [deltaArray[j-2] intValue];
                }

                // first test, cant be adjacents
                if (j != (i-1) && j != (i+1)) {
                    if (isBetween(segmentY, [deltaArray[j] intValue], previousValue)) {

                        // NSLog(@"\tcandidate vertical contains myY at index %d", j);

                        // that vertical segment contains my y,
                        // now I should check for x interpolation

                        // the x for current vertical candidate for colision,
                        // is the x value before this index on delta array

                        int canditateX;
                        if (j<1) {
                            canditateX = 0;
                        } else {
                            canditateX = [deltaArray[j-1] intValue];
                        }

                        if (isBetween(canditateX, [deltaArray[i] intValue], [deltaArray[    i-2] intValue])) {
                            // the candidate X has been found on current range of x for     this segment
                            // NSLog(@"\t\t***** FOUND SEGMENT THAT CROSS at index step     %d", (i+1));
                            return (i+1);
                        }
                    }
                }
            }
        }

        // NSLog(@"- no colision with this segment");
    }

    return -1;
}

int main(int argc, char *argv[]) {
    @autoreleasepool {

        NSMutableArray *arr = [NSMutableArray arrayWithObjects: @7, @6, @9, @5, @8, @4,     @7, @3, @5, @2, @4, @1, @6, nil]; //return 13 // collide going to north

        printf("will collide on step %d", stepColistionCheck(arr));
    }
}

```

# Answer
> 1 votes
# EDIT:

The bugs were found in this solution so don't use it. Refer to this one instead. Here is rich list of different test cases (including the one showing bugs in my solution).

```
int a[] = {1, 1, 1, 2}; // 3
int b[] = {1, 1, 2, 1, 1}; //4
int c[] = {1, 3, 2, 5, 4, 4, 6, 3, 2}; // 6
int d[] = {4, 4, 5, 7, 8, 6, 5}; // 6
int e[] = {1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10}; // 8
int f[] = {1, 1, 5, 3, 3, 2, 2, 1, 1, 3}; // 9 <-- this is the one I failed on

```

---

# C, O(n), 82 bytes.

This is a fix for feersum's solution. I cannot write comments so I post it here as an answer:

```
k(int*m){int*i=m;for(;2[i]>*i++;);for(*i-=(i-m>2)*i[~1];2[i]<*i++;);return 1+i-m;}

```

Here is the case where his solution fails:

```
int a[] = {1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10};

```

His function returns `6`, though the correct answer is `8`.

All other notes about his solution are held here as well.

# Answer
> 1 votes
Here is my approach done in Ruby, it uses Cramer's Rule to deduce if 2 segments cross each other. Since we are dealing only with horizontal and vertical lines maybe its an overkill but it passed all the test cases.

https://gist.github.com/Janther/089b2a4338760c057cbf

```
def intersects?(p0, p1, p2, p3)
  s1_x = p1[0] - p0[0]
  s1_y = p1[1] - p0[1]
  s2_x = p3[0] - p2[0]
  s2_y = p3[1] - p2[1]

  denom = s1_x * s2_y - s2_x * s1_y
  # if denom == 0 lines are parallel
  # TODO: aditional check if they overlap
  return false if (denom == 0)

  denomPositive = denom > 0

  s3_x = p0[0] - p2[0]
  s3_y = p0[1] - p2[1]

  s_numer = s1_x * s3_y - s1_y * s3_x
  # s must be positive for posible colition
  # s = s_numer / demom
  return false if (s_numer < 0) == denomPositive

  t_numer = s2_x * s3_y - s2_y * s3_x
  # t must be positive for posible colition
  # t = t_numer / demom
  return false if (t_numer < 0) == denomPositive

  # both t and s must be <= 1 so |s_numer| <= |denom| AND |t_numer| <= |denom|
  (s_numer <= denom) == denomPositive && (t_numer <= denom) == denomPositive
end

def solution(a)
  path = [[0, 0]]
  directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

  a.each.with_index do |steps, solution_index|
    position = path.last
    direction = directions[solution_index % 4]

    path << [position[0] + steps * direction[0], position[1] + steps * direction[1]]

    next if path.size < 4

    end_segment_1   = path[path.size - 1]
    # Border case when the path ends at the beginning
    return solution_index + 1 if end_segment_1 == [0, 0]
    start_segment_1 = path[path.size - 2]

    # First check is 4 moves ago
    start_segment_0 = path[path.size - 5]
    end_segment_0   = path[path.size - 4]

    if intersects?(start_segment_0, end_segment_0, start_segment_1, end_segment_1)
      return solution_index + 1
    end

    next if path.size <= 6
    # Second check is 6 moves ago
    start_segment_0 = path[path.size - 7]
    end_segment_0   = path[path.size - 6]

    if intersects?(start_segment_0, end_segment_0, start_segment_1, end_segment_1)
      return solution_index + 1
    end

  end
  0
end

solution [1, 3, 2, 5, 4, 4, 6, 3, 2] #=> 7
solution [1, 1, 1, 2] #=> 4
solution [1, 1, 2, 1, 1]  #=> 5
solution [4, 4, 5, 7, 8, 6, 5] #=> 7
solution [1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10] #=> 9
solution [1, 1, 5, 3, 3, 2, 2, 1, 1, 3] #=> 10

```

## Explanation of intersects?

We have 2 segments represented by p0, p1 and p2, p3.

Let's call the vector that joins p0 and p1 "s1" and the vector that joins p2 and p3 "s2".

```
s1 = p1 - p0
s2 = p3 - p2

```

Then we can represent the 2 lines by using the starting point and the vector like this:

```
L1 = p0 + t * s1
L2 = p2 + s * s2

```

If the two lines were to cross each other we should find a single value for t and s that fulfils the following equation

```
p0 + t * s1 = p2 + s * s2

```

If we cross multiply each side with s1 we get

```
(p0 + t * s1) x s1 = (p2 + s * s2) x s1

```

Since s1 x s1 = 0

```
(p0 - p2) x s1 = s * (s2 x s1)

```

And finally

```
s = (p0 - p2) x s1 / (s2 x s1)

```

Let's follow the same steps to solve for t

```
(p0 + t * s1) x s2 = (p2 + s * s2) x s2
t * (s1 x s2) = (p2 - p0) x s2
t = (p2 - p0) x s2 / (s1 x s2)

```

Having s1 x s2 = - (s2 x s1)

```
t = (p0 - p2) x s2 / (s2 x s1)

```

We have 2 equations

```
s = (p0 - p2) x s1 / (s2 x s1)
t = (p0 - p2) x s2 / (s2 x s1)

```

Since we don't want extra calculations let's have 2 more variables

```
denom = s2 x s1
s3 = p0 - p2

```

If denom is 0 segments are parallel and extra analysis should be made if they overlap.

If 0 ≤ t ≤ 1 AND 0 ≤ s ≤ 1 the lines cross inside the given segments, otherwise they cross in some other point.

Since floating point division is more CPU demanding than comparing 2 integers the code was modified to avoid dividing but still having the logic of 0 ≤ t ≤ 1 AND 0 ≤ s ≤ 1 and I added comments on the code to explain the logic.

Here you can find the original analysis which I used. https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

# Answer
> 1 votes
Just adding my php solution, runs in **O(n)**:

```
$arr = [1, 3, 2, 5, 4, 4, 6, 3, 2];

$sol = solution($arr);
var_dump($sol);

function solution($arr) {
    $state = 0;
    $dmax  = 0;
    $arrCount = count($arr);

    for($i = 2; $i < $arrCount; $i++) {
        switch ($state) {
            case 0:
                if($arr[$i] <= $arr[$i-2]) {
                    $dmax = ($i >= 4 && $arr[$i-4] >= $arr[$i-2]) ? $arr[$i-1] - $arr[$i-3] : $arr[$i-1];
                    $state = 1;
                }
                break;

            case 1:
                if ($arr[$i] >= $dmax) {
                    return $i+1;
                } else {
                    $dmax = $arr[$i-1];
                }
                break;

        }
    }
    return -1;
}

```

---
Tags: fastest-algorithm
---


title: Find the Semordnilaps

text:
# Question
Title: Find the Semordnilaps
Semordnilaps (also known as heteropalindromes, semi-palindromes, half-palindromes, reversgrams, mynoretehs, reversible anagrams, word reversals, or anadromes) are words which are also words when spelled backwards. A few examples are:

* Ward \<=\> Draw
* Mined \<=\> Denim
* Parts \<=\> Strap

Given a positive integer N (via function argument or STDIN), return / output a list of semordnilaps from this list of English words, that have exactly N letters. The list of words can be saved locally on your computer as a text file called: `w.txt`. You can also get the list from the url, but it will be included in the byte count.

Rules:

1. Palindromes are not semordnilaps! Therefore, the words "noon", "rotor" and "radar" should not be included in the list.
2. Only one of the words (in a semordnilap pair) should be included in the list. Therefore, if "dog" is in the list, "god" should not be (it doesn't matter which one is included.)
3. If there are no semordnilaps, the output should be an empty string, 0, FALSE or something else indicating that there were no results. The function must work even if there are no results.

This is code golf so the shortest code in bytes wins!

---

## Leaderboard

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
var QUESTION_ID=42090,OVERRIDE_USER=44713;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 10 votes
# Pyth, 23 (18 code, 5 necessary STDIN)

```
J'f&qlTQ&}_TJ>_TTJ

```

This is a fairly straightforward solution.

`J` stores the list of words. Then we filter over the list of words (`f J`) on the length of the word being the input (`qlTQ`), the reversed word being in the list (`}_TJ`), and the reversal of the word being greater than the word (`>_TT`). The last condition ensures `T` is not palindromic, and that only one of the pair is printed. The resultant list is printed.

The way Pyth works, the only way to open a file is to receive its name on STDIN. This is why I have counted 5 of the STDIN bytes, `w.txt`, in my score.

Example run:

```
$ pyth -c "J'f&qlTQ&}_TJ>_TTJ" <<< '6
w.txt'
['animal', 'denier', 'diaper', 'drawer', 'pupils', 'recaps', 'redraw', 'sleets', 'snoops', 'sports']

```

# Answer
> 10 votes
# Ruby, 74 bytes

```
f=->n{i=IO.read('w.txt').split
p *i&[f.reverse]if f.size==n while f=i.pop}

```

Iterates over the list by removing elements, which avoids both palindromes and outputting both "stressed" and "desserts". Using the same variable name for the function and the iterator gets around a Ruby syntax quirk: even though `f=i.pop` is evaluated before `f.reverse`, the line won't parse unless `f` already means something. I could also use `p`.

# Answer
> 4 votes
# Python, ~~126~~ ~~125~~ 120 bytes

```
N=input()
J=open("w.txt").read().split()
for c in set(J):
 if N==len(c)and c!=c[::-1]and c[::-1]in J:print c;J.remove(c)

```

Pretty straightforward solution.

# Answer
> 4 votes
# bash ~~134~~ ~~157~~ 118 bytes

`f () { comm -12 <(sort w.txt) <(rev w.txt|sort)|while read w; do ((${#w}==$1))&&[[ $w<$(rev<<<$w) ]]&&echo $w; done; }`

This is not a serious entry, but rather in response to Brian's Bash answer. This is how I tend to think about programming this sort of thing in Bash--by using Bash itself for as little as possible, and letting the built-in tools do all the work.

# Answer
> 3 votes
# CJam, ~~48~~ ~~47~~ ~~45~~ ~~42~~ 38 bytes

Since the URL has to be counted, I'm using the same URL shortener as Optimizer.

```
"ri.ms/§"gDcN+/{,ea~i=},_Wf%&{_W%>},N*

```

The `§` is part of extended ASCII, so each character in the code can be encoded in a single byte.

As in Optimizer's case, you'll have to use the Java interpreter and run this locally from a file, say `semordnilap.cjam`, and then

```
java -jar cjam-0.6.2.jar semordnilap.cjam <N>

```

so the input is given as a command-line argument.

How it works (slightly outdated):

```
"Prepare word list:";
"ri.ms/§"gDcN+/
"ri.ms/§"g      "Fetch list from shortened URL.";
          DcN+  "Create \r\n string.";
              / "Split input into lines.";

"Process input:";
{,ea~i=},
{      }, "Filter the list.";
 ,        "Get word length.";
  ea      "Push command-line arguments.";
    ~     "Unwrap array.";
     i    "Convert to integer.";
      =   "Check equality.";

"Find all palindromes and semordnilaps:";
_Wf%&
_     "Duplicate list.";
 Wf%  "Reverse each line.";
    & "Set intersection.";

"Remove duplicates and palindromes:";
{_W%>},N*
{    },   "Filter list.";
 _W%      "Duplicate word, reverse.";
    >     "Check lexicographic order.";
       N* "Join with newlines.";

```

The resulting string is automatically printed at the end of the program.

# Answer
> 3 votes
# Java, ~~280~~ 218 bytes

Compared to the rest of the competition, I have absolutely no idea if this is a good score.

```
void a(int n)throws Exception{List<String>l=Files.readAllLines(Paths.get("w.txt"));for(String s:l){String c=new StringBuilder(s).reverse()+"";if(s.length()==n&&c.compareTo(s)>0&&l.contains(c)){System.out.println(s);}}}

```

Expanded:

```
void a(int n)throws Exception{
    List<String>l=Files.readAllLines(Paths.get("w.txt"));
    for(String s:l){
        String c=new StringBuilder(s).reverse()+"";
        if(s.length()==n&&c.compareTo(s)>0&&l.contains(c)){
            System.out.println(s);
        }
    }
}

```

Uses compareTo() to simultaneously ignore palindromes and duplicates.

# Answer
> 2 votes
# Ruby, 95 bytes

```
f=->n{l=[]
(a=IO.read"w.txt").split.map{|w|a[w]=?.
w.size==n&&a[/^#{r=w.reverse}\s$/]&&l<<w}
l}

```

## Explanation

* Input is taken as the argument to a lambda. It expects an `Integer`.
* Read the file into memory as a `String` (`a`).
* Loop trough an `Array` of all words (without newlines).
    + Remove the word from `a`.
    + Add qualifying words to the `Array` `l`.
* Return `l`.

An empty `Array` is returned when no qualifying words were found.

# Answer
> 2 votes
# CJam, 68 bytes

```
"www.ri.ms/§"gDc-N/{_,ea~~=\_W%=!*},:Q{_W%aQ\/,({Q\a-:Q;1}{;0}?},N*

```

You will have to download the Java version of the compiler from here and save the above code in a file called words.cjam (can be any name). Then run the code like

```
java -jar cjam-0.6.2.jar <file_name> <input_number> [> <output_file_name>]

```

For example, for `N = 8`,

```
java -jar cjam-0.6.2.jar words.cjam 8 > out.txt

```

# Answer
> 2 votes
# K, 59 bytes

```
{*+?{x@<x}'+(w;r)@\:&(x=#:'w)&(~w~'r)&w in r:|:'w:0:`w.txt}

```

Pretty straightforward. Read the list, construct the reverse list, take their intersection, filter out the palindromes, filter in the required count, sort and dedupe the pairs.

# Answer
> 2 votes
# Node.js, 172 bytes

Function:

```
function d(n){return(require('fs').readFileSync("w.txt")+"").match(RegExp(("b"+Array(n+1).join("(.)")+"b(?=(.|s)*b"+"87654321".substr(-n)+"b)").replace(/\w/g,"\\$&"),"g"))}

```

Testing:

```
console.log(d(+process.argv[2]));
// run from command line like this:
// node main 4
// where
//   main is js file name
//   4    is length

```

# Answer
> 1 votes
# Mathematica, 105 bytes

```
F[f_,n_]:=(W=StringSplit@Import@f;Select[W,StringLength@#==n&&MemberQ[W,r@#]&&Order[r@#,#]==1&&r@#!=# &])

```

Sometimes Import will automatically split the text into list of list of lines, or treat it as CSV or TSV. At other times, Import will read the contents of the file into a string. Import did the latter for the test data.

# Answer
> 1 votes
# Node.js, CoffeeScript, 132 Bytes

```
f=(n)->(require('fs').readFileSync('w.txt')+'').split('\n').filter((s,i,f)->s.length==n&&f.indexOf(s.split('').reverse().join(''))>i)

```

# Node.js, 162 Bytes

```
function a(n){return(require('fs').readFileSync('w.txt')+'').split('\n').filter(function(s,i,f){return s.length==n&&f.indexOf(s.split('').reverse().join(''))>i})}

```

**Chrome Dev Tools Console, 111 Bytes** (On the download page)

```
f=(n=>$('pre').innerText.split('\n').filter((x,i,a)=>x.length==n&&a.indexOf(x.split('').reverse().join(''))>i))

```

All versions return an array of all Semordnilaps of length `n`.

# Node.js, 162 Bytes

Prints all semordnilaps:

```
function a(n){(require('fs').readFileSync('w.txt')+'').split('\n').map(function(s,i,f){s.length==n&&f.indexOf(s.split('').reverse().join(''))>i&&console.log(s)})}

```

# Answer
> 1 votes
# Julia, 101 bytes

```
k=split(readall("w.txt"))
for(i=k)
([]!=(l=find(x->x==reverse(i)&&x!=i,k)))&&(println(i);k[l]="")
end

```

This should actually work...

# Answer
> 0 votes
**BASH**

```
f() {
  w=($(cat "${1}"))
  for ((i=0;i<=${#w[@]};i++)); do
    if ((${#w[$i]} == $2)); then
      r=
      for((x=${#w[$i]}-1;x>=0;x--)); do
        r="$r${w[$i]:$x:1}";
      done
      if [[ ${w[$i]} != ${r} ]] && grep -qw $r "${1}"; then
        echo "${w[$i]}, ${r}"
      fi
      unset w[$i]
    fi
  done
}

```

tests...

```
f /usr/share/dict/words 5

debut, tubed
decaf, faced
decal, laced
deeps, speed
denim, mined
devil, lived
draws, sward
faced, decaf
keels, sleek
knits, stink
laced, decal
lager, regal
leper, repel
lever, revel
lived, devil
loops, spool
loots, stool
mined, denim
parts, strap
peels, sleep
pools, sloop
ports, strop
rebut, tuber
regal, lager
remit, timer
repel, leper
revel, lever
sleek, keels
sleep, peels
sloop, pools
smart, trams
snaps, spans
snips, spins
spans, snaps
speed, deeps
spins, snips
spool, loops
spots, stops
sprat, tarps
stink, knits
stool, loots
stops, spots
strap, parts
straw, warts
strop, ports
sward, draws
tarps, sprat
timer, remit
trams, smart

```

---
Tags: code-golf
---


# Question
Title: Can you reach this number by doubling and rearranging?
*Inspired by this question on Math.SE.*

Starting with `1` you can repeatedly perform one of the following two operations:

* Double the number.

**or**
* Rearrange its digits in any way you want, except that there must not be any leading zeroes.

Taking an example from the linked Math.SE post, we can reach `1000` via the following steps:

```
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 125, 250, 500, 1000

```

Which numbers can you reach with this process and what is the shortest solution?

## The Challenge

Given a positive integer `N`, determine the shortest possible sequence of integers to reach `N` with the above process, if possible. If there are several optimal solutions, output any one of them. If no such sequence exists, you should output an empty list.

The sequence may be in any convenient, unambiguous string or list format.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Here is a list of all reachable numbers up to and including 256. The first column is the number (your input), the second column is the optimal number of steps (which you can use to check the validity of your solution) and the third column is one optimal sequence to get there:

```
1       1       {1}
2       2       {1,2}
4       3       {1,2,4}
8       4       {1,2,4,8}
16      5       {1,2,4,8,16}
23      7       {1,2,4,8,16,32,23}
29      10      {1,2,4,8,16,32,23,46,92,29}
32      6       {1,2,4,8,16,32}
46      8       {1,2,4,8,16,32,23,46}
58      11      {1,2,4,8,16,32,23,46,92,29,58}
61      6       {1,2,4,8,16,61}
64      7       {1,2,4,8,16,32,64}
85      12      {1,2,4,8,16,32,23,46,92,29,58,85}
92      9       {1,2,4,8,16,32,23,46,92}
104     15      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104}
106     14      {1,2,4,8,16,32,64,128,256,265,530,305,610,106}
107     14      {1,2,4,8,16,32,23,46,92,29,58,85,170,107}
109     18      {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,109}
116     12      {1,2,4,8,16,32,23,46,92,29,58,116}
122     7       {1,2,4,8,16,61,122}
124     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124}
125     11      {1,2,4,8,16,32,64,128,256,512,125}
128     8       {1,2,4,8,16,32,64,128}
136     18      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,136}
140     15      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,140}
142     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,142}
145     17      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145}
146     18      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,146}
148     11      {1,2,4,8,16,32,23,46,92,184,148}
149     16      {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,149}
152     11      {1,2,4,8,16,32,64,128,256,512,152}
154     17      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154}
158     16      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158}
160     14      {1,2,4,8,16,32,64,128,256,265,530,305,610,160}
161     13      {1,2,4,8,16,32,23,46,92,29,58,116,161}
163     18      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,163}
164     18      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,164}
166     20      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166}
167     17      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,167}
169     23      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,169}
170     13      {1,2,4,8,16,32,23,46,92,29,58,85,170}
176     17      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176}
182     9       {1,2,4,8,16,32,64,128,182}
184     10      {1,2,4,8,16,32,23,46,92,184}
185     16      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185}
188     23      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185,370,740,470,940,409,818,188}
190     18      {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,190}
194     16      {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,194}
196     23      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,196}
203     16      {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,203}
205     13      {1,2,4,8,16,32,64,128,256,512,125,250,205}
208     16      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208}
209     19      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145,290,209}
212     8       {1,2,4,8,16,61,122,212}
214     15      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214}
215     11      {1,2,4,8,16,32,64,128,256,512,215}
218     9       {1,2,4,8,16,32,64,128,218}
221     8       {1,2,4,8,16,61,122,221}
223     14      {1,2,4,8,16,32,23,46,92,29,58,116,232,223}
227     20      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,361,722,227}
229     20      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229}
230     16      {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,230}
232     13      {1,2,4,8,16,32,23,46,92,29,58,116,232}
233     22      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233}
235     19      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,235}
236     19      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,236}
238     19      {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,832,238}
239     25      {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233,466,932,239}
241     16      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,241}
244     8       {1,2,4,8,16,61,122,244}
247     21      {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,362,724,247}
248     17      {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124,248}
250     12      {1,2,4,8,16,32,64,128,256,512,125,250}
251     11      {1,2,4,8,16,32,64,128,256,512,251}
253     19      {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,253}
256     9       {1,2,4,8,16,32,64,128,256}

```

If you want even more test data, here is the same table up to and including 1,000.

Any number not appearing on these tables should yield an empty list (provided the number is in the range of the table).

# Answer
> 18 votes
# Pyth, 43 bytes

```
?}QKhu?Jf}QTGJsm+Ld+yedsMfnhT\0.p`edGQ]]1KY

```

Demonstration.

This is starts by generating all possible double or rearrange sequences. However, since I actually wanted to see it finish, I added a short circuit.

It either runs until it finds a solution, or for a number of iterations equal to the input, at which point it gives up and returns `[]`.

---

This is guaranteed to be enough iterations. First, we know that this many iterations is enough for all n \<= 1000, thanks to the example results. For larger numbers, the following argument holds:

First, each step of the process must either maintain or increase the number of digits.

Second, three numbers that are all rearrangements of one another can never all appear in a shortest sequence, because it would have been quicker to just do a single rearrangement from the first to the last.

Third, all multiples of 3 are unreachable, because neither doubling nor rearrangement can produce a multiple of 3 from a non-multiple of 3.

Thus, the longest possible sequence ending at a given number is equal to the sum of twice the number of sets of digits with less than or equal to as many digits as the input, and where the digits do not sum to a multiple of 3.

The number of such digit sets for each number of digits:

```
4 - 474
5 - 1332
6 - 3330

```

In addition, we know from the examples that no shortest sequence ending with a 3 digit number is of length greater than 26. Thus, an upper bound of the sequence lengths is:

```
4: 474 * 2 + 26 = 974
5: 974 * 2 + 1332 = 3638
6: 3330 * 2 + 3638 = 10298

```

In each case, the upper bound is lower than any number with the number of digits

The number of digit sets cannot grow by more than a factor of 10 when the number of digits is increased by one, because the new numbers can be separated into groups by last digit, each of which cannot have more sets than there were with one fewer digit.

Thus, the upper bound will be lower than any number with that many digits for all possible numbers of digits greater than or equal to 4, which completes the proof that a number of iterations equal to the input is always enough.

# Answer
> 7 votes
# SWI-Prolog, 252 bytes

```
a(N,Z):-findall(X,b(N,[1],X),R),sort(R,[Z|_]);Z=[].
b(N,[A|T],Z):-n(A,C),n(N,M),length(C,L),length(M,O),L=<O,((A=N,reverse([A|T],Z));(A\=N,(B is A*2;permutation(C,D),\+ nth0(0,D,48),n(B,D),\+member(B,[A|T])),b(N,[B,A|T],Z))).
n(A,B):-number_codes(A,B).

```

Example: `a(92,Z).` outputs `Z = [1, 2, 4, 8, 16, 32, 64, 46, 92]`

I haven't checked yet that this works for N \> 99 because of the time it takes, but I see no reason why it wouldn't work.

# Answer
> 2 votes
# Julia, ~~306~~ ~~245~~ 218 bytes

Still working on golfing this. Will provide an ungolfed version once I'm done.

```
s->(M=s=[s];while 1∉s C=0;for i=1:size(s,1) p=2;for j=permutations(dec(s[i])) j[1]>48&&j[end]%2<1&&(l=int(j);l=l÷p;l∉M&&(M=[M,l];S=[l s[i,:]];C==0?C=S:C=[C;S]));p=1end;end;C==0&&return [];s=C;end;sortrows(s)[1,:])

```

# Answer
> 1 votes
# Haskell, 246 bytes

I am not entirely sure if this works, it does iff the sequence that first diverges lower (as to be sorted lower) is always shorter, as for example

`[1,2,4,8,16,32,64,128,256,512,125,250,500,1000]`

is shorter than

`[1,2,4,8,16,32,64,128,256,512,251,502,250,500,1000]`

which i tested to be true up to 1000.

```
import Data.List
h l|mod(e l)2==0=l:h(div(e l)2:l)|0<1=[l]
s l=map((:l).read)(filter((/='0').e)(permutations$show$e l))
e=head
m=map e
n f=m.groupBy(\a b->e a==e b).sort.concatMap f
w l|e(e l)==1=[nub$e l]|m x/=m l=w x|0<1=[[]] where x=n h(n s l)

```

# Answer
> 1 votes
# C# 655 bytes

```
List<int> C(int i,List<int> x,int a){x.Add(a);if(a==i)return x;List<int> o=null;string s=a.ToString(),m=i.ToString();var res=G(s,s.Length);foreach (var r in res)if (r.First()!='0'){var l=int.Parse(new String(r.ToArray()));if(!x.Contains(l)&&l.ToString().Length<=m.Length){var n=C(i,x.ToList(),l);if(n!=null&&(o==null||o.Count()>n.Count()))o=n;}}if ((a*2).ToString().Length>m.Length)return o;var p = C(i, x.ToList(), a * 2);if (p!=null&&(o==null||o.Count()>p.Count()))o=p;return o;}IEnumerable<IEnumerable<T>> G<T>(IEnumerable<T> l,int i){return i==1?l.Select(t =>new T[]{t}):G(l,i-1).SelectMany(t=>l.Where(e=>!t.Contains(e)),(a,b)=>a.Concat(new T[]{b}));}

```

Call with (LinqPad):

```
var i = 64;
C(i,new List<int>(),1).Dump();

```

Haven't tested numbers above 99. If you have time -\> good luck ;-)

edit: ungolfed version:

```
List<int> C(int i, List<int> x, int toAdd, bool removeLast)
{
    x.Add(toAdd);

    if ( toAdd == i )
    {
        return x;
    }
    else
    {
        List<int> shortest = null;
        if ( toAdd > 9 )
        {
            var res = G(toAdd.ToString(), toAdd.ToString().Length);

            foreach ( var r in res )
            {
                if ( r.First () != '0' )
                {
                    var resi = int.Parse(new String(r.ToArray()));

                    if ( !x.Contains(resi) && resi.ToString().Length <= i.ToString().Length )
                    {
                        var resPerm = C(i, x.ToList(), resi, false);
                        if ( resPerm != null )
                        {
                            if ( shortest == null || shortest.Count() > resPerm.Count() )
                            {
                                shortest = resPerm;
                            }
                        }
                    }
                }
            }
        }
        if ( (toAdd * 2).ToString().Length > i.ToString().Length )
        {
            return shortest;
        }
        var resDouble = C(i, x.ToList(), toAdd * 2, false);
        if ( resDouble != null )
        {
            if ( shortest == null || shortest.Count() > resDouble.Count() )
            {
                shortest = resDouble;
            }
            return shortest;
        }

        return shortest;
    }
}
IEnumerable<IEnumerable<T>> G<T>(IEnumerable<T> l,int i)
{
    return i==1?l.Select(t => new T[]{t}):G(l,i-1).SelectMany(t=>l.Where(e=>!t.Contains(e)),(a,b)=>a.Concat(new T[]{b}));
}

```

# Answer
> 0 votes
# CJam, 83

```
ri:N_1a:Xa:Y;{X,{XI=__se!{c~},:i^\2*|NA*,&X-_YI=f+Y\+:Y;X\+:X;}fI}*X#_){Y=W%}{;L}?p

```

Try it online

I've been sitting on this for a long time, it's not very short nor fast, and I'm not sure I have the energy/motivation to improve it, so I'm just posting it.

---
Tags: code-golf, sequence, number-theory, path-finding, permutations
---


title: Is the pizza fair?

text:
# Question
Title: Is the pizza fair?
This question is inspired by, and is the inverse of this one.

Dennis (`E`), Doorknob (`D`), Martin (`M`) and Chris (`C`) have ordered a pizza. The rectangular pizza is divided into square pieces, each marked with their intended eater.

Write a program or function that given a **rectangular** pizza consisting of 0 or more of each letter determines whether:

1. Each slice for each person is path-connected. This means that all letters that are the same should be directly adjacent to eachother (no diagonal connections).
2. The number of slices per person is the same for all.

You must output a truthy/falsy value with an optional trailing newline that indicates whether or not the given pizza is fair.

### Valid testcases:

```
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
```

```
DEMC
```

```
DD
EE
MC
MC
```

```
EEDDMMMCCC
EEEDDDMMCC
```

### Invalid testcases:

```
EDM
```

```
EDMCCMDE
```

```
DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC
```

```
DDMMEECC
DMMEECCC
```

---

Shortest code in bytes wins.

# Answer
> 5 votes
# Pyth, 53 bytes

```
!f-lJs.z*4lu&G{smfqT@JY@UJ+Ld[Z1_1Klh.z_K)G]xJT)"CDEM

```

Demonstration

This is essentially a flood fill for each letter, followed by a check that all of the resulting sets are of the appropriate size.

To flood-fill, it starts with the upper-left-most occurence of each letter, then generates all neighbors of locations found so far, filters for locations with the right letter, and repeats until the set stops changing.

# Answer
> 6 votes
# Snails, 129

Prints 1 for a fair pizza and 0 for an unfair pizza.

```
&
={(t\Dt\Et\Ct\M),!(t.}{(o\D)+l^D,=~u{^D=(r^D,~},~|o\E`+l^E,=~u{^E=(r^E,~},~|o\C`+l^C,=~u{^C=(r^C,~},~|o\M`+l^M,=~u{^M=(r^M,~},~

```

Expanded version:

```
&
={ (t\Dt\Et\Ct\M), !(t.)}   {
(o\D)+ l^D,=~ u{^D=(r^D,~)}, ~ |
(o\E)+ l^E,=~ u{^E=(r^E,~)}, ~ |
(o\C)+ l^C,=~ u{^C=(r^C,~)}, ~ |
(o\M)+ l^M,=~ u{^M=(r^M,~)}, ~

```

`&` means that the pattern must match at all locations on the grid. The first line checks for an equal number of each of E, D, M, C. it uses the teleport instruction `t`, which is a great way to make programs with factorial complexity. If an input has unequally sized slices with several units for each of the 4 mods, the program will more or less hang forever. After that, there is a check for a contiguous path to the top-left instance of whichever letter the pattern started on.

# Answer
> 6 votes
# CJam, 93

```
qN/_z,:W;s:A,,:B_{{{_B=_@-}g}%$}:F;{a+_Af=)#{F~B\@t:B}|;}:U;W>{_W-U}/{W%},{_(U}/BFe`0f=_1<4*=

```

Try it online

This is ridiculously long because CJam doesn't (yet) have built-in flood-fill or union-find. I implemented union-find in the program.

**Explanation:**

```
qN/_         read input, split into lines and duplicate
z,:W;        transpose, get length (original width) and store in W
s:A          convert to string (without newlines) and store in A
,,           make an array [0..n-1] (n = pizza size)
:B_          store in B (initial structure) and duplicate (will be used in 2 loops)
{…}:F;       define function F ("Find" for multiple indices and sort)
  {…}%       for each value (x)
    {…}g     do…while
      _B=    duplicate x and get B[x]
      _@-    leave a B[x] on the stack and calculate B[x] - x
              if non-zero, repeat the loop with B[x]
  $          sort the results
{…}:U;       define function U ("Union" for 2 indices)
  a+         make an array of the 2 indices
  _Af=       get the corresponding letters from A
  )#         check if the letters are different
  {…}|       if not, execute…
    F~       call F on the array and dump the 2 results on the stack
    B\@t     join the sets - B[bigger index] = smaller index
    :B       store back in B
  ;          pop the last value (either array if indices or B)
W>           remove the first row of indices
{…}/         for each index
  _W-        duplicate and subtract W ("go up")
  U          call U to join sets if they match
{W%},        remove the first column of indices
{…}/         for each index
  _(         duplicate and decrement ("go left")
  U          call U to join sets if they match
BF           call F on B, to get the final sets and sort
e`           RLE encoding
0f=          keep only the repetition counts
_1<4*=       check if it's the first value (if any) repeated 4 times

```

# Answer
> 4 votes
# JavaScript (ES6), 153 ~~166~~

Using template strings, there is a newline that is significant and counted

Test running the snippet in FireFox.

```
f=z=>![...'CDEM'].some(c=>((l=p=>z[p]==c&&[-1,1,w,-w].map(o=>l(p+o),z[p]='',++k))(z.indexOf(c),h=k,k=0),~h&&h-k),w=~z.search`
`,z=[...z],k=-1)&z.join``-1

// Ungolfed
U=z=>{
  w = ~z.search`\n`
  z = [...z]
  fill = p=>(
    c = z[p],
    z[p] = '',
    [-1,1,w,-w].forEach(o=>z[o+=p] == c && fill(o)),
    ++k
  )
  h = -1
  r = ['C','D','E','M'].every( c =>(
    k = 0,
    y = z.indexOf(c),
    y >= 0 && fill(y),
    v = h >= 0 ? h == k : true,
    h = k,
    v
  ))
  return r & 1-z.join``
}

// Test
out=x=>O.innerHTML+=x+'\n';

// Valid test cases
valid=[`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEDMMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DEMC`,
`DD
EE
MC
MC`,
`EEDDMMMCCC
EEEDDDMMCC`];
out('Valid')
valid.forEach(t=>out(t+'\n'+f(t)+'\n'));
invalid=[`EDM`,
`EDMCCMDE`,
`DDDDDDDDDDDDDD`,
`DDDDDDDDDDDDMCCCCCCCCCCC
DEEEEEEEEEEDMMMMMMMCCCCC
DEEEEEEEEEEMDMMCCCCCCCCC
DEEEEEEEEEEDMMMMMMMMCCCC
DDDDDDDDDDDDMMMMMMMMMMMC`,
`DDMMEECC
DMMEECCC`
];
out('Invalid')
invalid.forEach(t=>out(t+'\n'+f(t)+'\n'))
```

```
<pre id=O></pre>
```

# Answer
> 2 votes
# Javascript ES6, 360

Checks for equal numbers of C, D, E, M, then flood fills and checks for any orphaned letters. Not a winner, but I had to try.

```
i=>(I=i.split`
`.map(e=>e.split``),c=(i[m='match'](/C/g)||[])[l='length'],a=(x,y,z)=>{if(I[x][y]!=z)return;I[x][y]=0;x>0&&a(x-1,y,z);x<I[l]-1&&a(x+1,y,z);y>0&&a(x,y-1,z);y<I[0][l]-1&&a(x,y+1,z)},![...'CDEM'].some(k=>{if((i[m](eval(`/${k}/g`))||[])[l]!=c)return 1;I.some((w,x)=>(g=-1<(y=w.indexOf(k)),g&&a(x,y,k),g));})&&!I.map(e=>e.join``).join``[m](/[CDEM]/))

```

Fiddle

# Answer
> 2 votes
# JavaScript ES6, ~~328~~ ~~318~~ ~~316~~ ~~269~~ 178

```
l=>(d=[0,0,0,0],s=[...l.split`
`.join``].map(i=>(d["EDMC".search(i)]++,i)),!l||d.every(i=>i==d[0])&&(s.every((r,i)=>[1,-1,X=l.split`
`[0].length,-X].some(o=>s[o+i]==r))||d[0]<2))

```

Explanation:

```
l => (
  d = [0,0,0,0],          // array containing each letter count
  s = [...l.split`
`.join``]                 // removes newlines from input and converts it into array
  .map(i => (             // loops through the array
    d["EDMC".search(i)]++ // increases letter count
    ,i)),                 // returns unchanged value in order to preserve original array
  !l                      // input is empty
  || d.every(i=>i==d[0])  // each letter count is equal
  && (
    s.every((r, i) =>     // there is no orphaned letters
      [1,-1,X=l.split`
`[0].length,-X]           // letters on respectively: right, left, bottom, top
      .some               // at least one of them
        (o=>s[o+i]==r))   // equals original letter
    || d[0] < 2           // count of each letter equals 1
  )
)

```

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


title: The hue of a color

text:
# Question
Title: The hue of a color
You are given the RGB values of a color. Your task is simple: to calculate the hue, in the simplest definition.

Say the channels with highest, middle and lowest value are X, Y, Z (which are either red, green or blue) and their values are x, y, z. The hue of this color is (h(X)-h(Y))\*(1 + (x-y)/(x-z))/2 + h(Y), where:

```
h(red) = 0 (or 360 if one of X or Y is blue)
h(green) = 120
h(blue) = 240

```

The input consists of 3 integers from 0 to 255 which are not all equal, in any consistent order. The output can be floats, or integers rounded either up or down, which doesn't have to be consistent. If the integer part of the output is 0 or 360, you can print either of them.

You cannot call builtins for color space conversions, including implicit conversions such as while manipulating an image.

This is code-golf. Shortest code wins.

## Examples

```
Input:  0 182 255
Output: 197 (or 198)

Input:  127 247 103
Output: 110

Input:  0 0 1
Output: 240

Input:  255 165 245
Output: 307 (or 306)

```

## Edit

You don't have to follow the exact formula, but only have to give the same result as the above formula. I'd like to also see some answers golfing the formula itself.

# Answer
# Pyth, 27 bytes

```
*60%+c-Ft.<QJxQKeSQ-KhSQyJ6

```

Demonstration. Test harness.

Fomula taken from Wikipedia.

Essentially, the steps are:

1. `.<QJxQKeSQ`: Roate the largest value to the front of the list.
2. `-Ft`: Take the difference of the other two values.
3. `-KhSQ`: Subtract the minimum value from the maximum value.
4. `c`: Divide 2 by 3.
5. `+ ... yJ` Add twice the index of the maximum value in the list (0 if R, 2 if G, 4 if B).
6. `% ... 6`: Mod 6, to fix issues with negatives.
7. `*60`: Multiply by 60 to convert to degrees, and print.
> 6 votes

# Answer
# C#, ~~188~~ ~~210~~ ~~206~~ ~~197~~ 191 bytes

```
int H(int r,int g,int b){int[]a={r,g,b};System.Array.Sort(a);int x=a[2],y=a[1],c=x==g?1:(x==b?2:(y==b?3:0)),d=y==g?1:(y==b?2:(x==b?3:0));return(int)((c-d)*120*(1+(x-y)*1D/(x-a[0]))/2+d*120);}

```

Thanks to Sok for saving 4 bytes and to SLuck49 for saving 15!
> 9 votes

# Answer
## Pyth, ~~41~~ ~~55~~ ~~53~~ 51 bytes

```
A.)JohN,VQ*L120?qeQhSQ3j312T+/*-HKeeJhc-GheJ-GhhJ2K

```

Input is expected in the form `r,g,b`. Here's an explanation:

```
                                                        Implicit: Q=eval(input()), evaluates to (r,g,b)
               ?qeQhSQ                                  Is b the smallest?
                      3j312T                            Choose [0,1,2] or [3,1,2] based on above
          *L120                                         Convert to [0,120,240] or [360,120,240]
       ,VQ                                              Pair -> [[r,0/360],[g,120],[b,240]]
   JohN                                                 Order by 1st element in each pair, store in J
A.)J                                                    Pop biggest from J, set G = x, H = h(X)
                                                        Output calculation:
                                       -GheJ                x - y
                                            -GhhJ           x - z
                                     hc                     Divide and increment
                                 KeeJ                       Set K = h(Y)
                              *-HK                          Multiply by (h(X) - h(Y))
                             /                   2          Integer division by 2
                            +                     K         Add h(Y)

```

*Saved 4 bytes, thanks to @Jakube and @isaacg*
> 8 votes

# Answer
# Javascript (ES6), ~~145~~ ~~115~~ ~~108~~ ~~100~~ ~~97~~ 90 bytes

Returns floats. Assign to a function to use.

```
(r,g,b)=>([x,y,z]=[r,g,b].sort((a,b)=>b-a),m=x-z,(x-r?x-g?r-g+4*m:b-r+2*m:g-b+6*m)/m%6*60)

```

Saved 30 bytes by inlining everything into a single ternary operator sequence and waiting until the end to normalize to 0-360.

Thanks to edc65, Vasu Adari, and ETHproductions for saving even more bytes.

JSFiddle with tests. Try in Firefox.

If removing the function declaration `h=` is not legal, add 2 bytes.
> 8 votes

# Answer
# Octave, ~~65~~ ~~60~~ 50 bytes

### Edit: Saved 10 bytes thanks to pawel.boczarski

### An approximate solution...

```
@(c)mod(atan2d(.866*c*[0;1;-1],c*[2;-1;-1]/2),360)

```

### Test run

```
@(c)mod(atan2d(.866*c*[0;1;-1],c*[2;-1;-1]/2),360)
ans([0   182   255])
ans =  196.14

@(c)mod(atan2d(.866*c*[0;1;-1],c*[2;-1;-1]/2),360)
ans([127   247   103])
ans =  111.05

@(c)mod(atan2d(.866*c*[0;1;-1],c*[2;-1;-1]/2),360)
ans([0   0   1])
ans =  240.00

@(c)mod(atan2d(.866*c*[0;1;-1],c*[2;-1;-1]/2),360)
ans([255   165   245])
ans =  305.82

```

---

# Octave, 107 bytes

### My original (exact-ish) solution...

### Code:

```
function H=r(c) [b,i]=sort(c);h=60*[6*(i(1)~=3),2,4](i);H=(h(3)-h(2))*(1+(b(3)-b(2))/(b(3)-b(1)))/2+h(2);

```

### Explained:

```
function H=r(c)
   [b,i]=sort(c);
   h=60*[6*(i(1)~=3),2,4](i);
   H=(h(3)-h(2))*(1+(b(3)-b(2))/(b(3)-b(1)))/2+h(2);

```

This function takes a vector containing the R,G,B values as input `c` and sorts the input in ascending order

* `b` contains the sorted values \[z, y, x\]
* `i` contains the RGB plane associated with each value in b

The vector `h` is populated with the values

* `60*[6, 2, 4]` = `[360, 120, 240]` (but 3 bytes shorter)
* unless the lowest value is in Blue (`i(1) == 3`), in which case the first hue value becomes zero
* then use `(i)` to rearrange `h` into `[h(Z), h(Y), h(X)]` order

From there it's just a straight transcription of the formula. You can try it here.
> 6 votes

# Answer
# Pyth, 55

I know @Sok's answer beats mine, but since I finished mine just after he/she posted, I thought I would still post. This was my first time using Pyth so I'm sure I made some obvious mistakes.

```
DlZK*120ZRKJSQFNJ=Y+YxQN)=kl@Y1+k/*-leYk+1c-eJ@J1-eJhJ2

```

Input is expected to be `r, g, b`. You can try it here.
> 5 votes

# Answer
## PowerShell, ~~232~~ ~~226~~ ~~222~~ 161 Bytes

See revision history for previous versions

```
$z,$y,$x=($r,$g,$b=$args)|sort
$c=((2,(0,3)[$y-eq$b])[$x-ne$b],1)[$x-eq$g]
$d=((2,(0,3)[$x-eq$b])[$y-ne$b],1)[$y-eq$g]
(($c-$d)*120*(1+($x-$y)/($x-$z))/2+$d*120)

```

Hoo boy, let's see if I can walk through this. Since `\n` counts the same as `;` I left the line breaks in for clarity.

The first line takes input as three `$args` and stores them into `$r, $g, $b`. We're really only going to be using `$b` later, but we need all three so the `|sort` works appropriately. This makes `$z, $y, $x` the smallest-to-largest of the input arguments.

The next two lines setup `$c` and `$d` by using multiple index-into-an-array calls to set the numbers appropriately. Working from outside in, if `$x` is `-eq`ual to `$g` (i.e., green was the largest), we set `$c=1` ... else, if `$x` is `-n`ot`e`qual to `$b` (i.e., blue wasn't the largest) `$c` is either `0` or `3` depending if blue was the second largest ... else, `$c=2`. Similar logic sets `$d`.

We then calculate and print the output with the following, which is just the algorithm from the challenge golfed a little bit.

```
(($c-$d)*120*(1+($x-$y)/($x-$z))/2+$d*120)

```
> 5 votes

# Answer
# Ruby, ~~117~~ ~~96~~ 94 bytes

**Code:**

```
h=->r,g,b{z,y,x=[r,g,b].sort;v=x-z.to_f;({r=>(g-b)/v,g=>2+(b-r)/v,b=>4+(r-g)/v}[x]%6*60).to_i}

```
* Saved 21 bytes by removing `()` and using r,g,b variables.
* Taking modulus of 6 to convert negative value and multiplying it by 60 to convert to degrees that saved 2 bytes.

**Examples:**

```
irb(main):274:0> h.call 0,182,255
=> 197
irb(main):275:0> h.call 127,247,103
=> 110
irb(main):276:0> h.call 0,0,1
=> 240
irb(main):277:0> h.call 255,165,245
=> 306

```
> 4 votes

# Answer
# SWI-Prolog, 133 bytes

```
a(L,H):-L=[R,G,B],max_list(L,X),min_list(L,Y),member(X:I:J:U,[R:G:B:0,G:B:R:2,B:R:G:4]),Z is 60*(U+(I-J)/(X-Y)),(Z<0,H is Z+360;H=Z).

```

Example: `a([255,165,245],Hue).` outputs `Hue = 306.666666666666 .`

This uses the following formula:

* `Max = max(R,G,B)`, `Min = min(R,G,B)`.
* If `Max = R`, `U = 0`. Else if `Max = G`, `U = 2`. Else `U = 4`.
* If `Max = R`, `I = G` and `J = B`. Else if `Max = G`, `I = B` and `J = R`. Else `I = R` and `J = G`.
* `Z = U + (I - J)/(Max - Min)`
* `Hue` is either `Z` or `Z + 360` if `Z < 0`.
> 3 votes

# Answer
# Perl 5, 138 132 119 bytes

### Code:

```
($m,$c,$M)=sort@A=($R,$G,$B)=@ARGV;print 60*(6+$M>$m?($G>$c?$B-$R:$B>$c?$R-$G:$G-$B)/($M-$m)+($G>$c?2:$B>$c?4:0):0)%360

```

### Remarks:

Surely Perl can't win such challenge with all the Pyth'oresque golfing. But I wondered if this was possible to do with only 1 calculation step. Thanks to the modulus that worked out nicely. :)

### Test:

```
$ perl hue.pl 0 182 255
197
$ perl hue.pl 127 247 103
110
$ perl hue.pl 0 0 1
240
$ perl hue.pl 255 165 245
307

```
> 3 votes

# Answer
# R, 125 bytes

Very similar to beaker's Octave solution. Floating point output.

## Code:

```
h=function(x){
  o=seq(3)[order(-x)];
  y=c(60*c(6*(o[3]!=3),2,4)[o],x[o]);
  return((y[1]-y[2])*(1+(y[4]-y[5])/(y[4]-y[6]))/2+y[2]);
}

```

## Examples:

```
> h(c(0,182,255))
[1] 197.1765
> h(c(127,247,103))
[1] 110
> h(c(0,0,1))
[1] 240
> h(c(255,165,245))
[1] 306.6667

```
> 1 votes

# Answer
# Python, 154 bytes

```
def h(c):r=c[:];c.sort();c=c[::-1];x,y,z=c;i,j=[120if n==r[1]else 240if n==r[2]else 0if z==r[2]else 360for n in[x,y]];print ((i-j)*(1+(x-y+0.)/(x-z))/2)+j

```

Accepts a list of values. Not sure if this can be broken down further. Here it is ungolfed:

```
def hue(color):
 rgb=color[:]  # copy list
 color.sort()  # sort list
 color=color[::-1]  # reverse sort
 x,y,z=color   # pull out x,y,z

 # The line
 #   i,j=[120if n==r[1]else 240if n==r[2]else 0if z==r[2]else 360for n in[x,y]]
 # is basically the following, twice, once for x/hx and the second time for y/hy

 if x==rgb[1]: # if x is green
  hx = 120
 else:
  if x==rgb[2]: # if x is blue
   hx = 240
  else:
   if z==rgb[2]: # if z is blue and x is red
    hx = 0
   else:       # if x is red and y is blue
    hx = 1

 print ((hx-hy)*(1+(x-y+0.)/(x-z))/2)+hy  # calculate, print

```
> 1 votes

# Answer
# JavaScript 108

Alternate method.

```
function H(r,g,b){a=[r,g,b].sort(),M=a[2],c=M-a[0],h=M==r?(g-b)/c%6:M==g?(b-r)/c+2:(r-g)/c+4
return h*60|0;}

```

**JavaScript 194**

Using the example method.

```
Array.prototype.i=[].indexOf
function H(r,g,b,a){a=[r,g,b].sort(),i=[a.i(r),a.i(g),a.i(b)],x=[i[2]?360:0,120,240],hx=x[i.i(2)]|0,hy=x[i.i(1)]|0
return (hx-hy)*(1+(a[2]-a[1])/(a[2]-a[0]))/2+hy|0}

var input = document.getElementById("input").innerHTML;
var output = document.getElementById("output");
var html = "";

input.replace(/(\d+)\,(\d+)\,(\d+)/g, function(m, r, g, b) {
  html += H(r, g, b) + "\n";
});

output.innerHTML = html;
```

```
<pre id="input">
0,182,255
127,247,103
0,0,1
255,165,245
</pre>

<pre id="output">

</pre>
```
> 0 votes

---
Tags: code-golf
---


title: Fixing a logic system

text:
# Question
Title: Fixing a logic system
You are given a set of logic statements. Your challenge is to remove any ones that contradict the others, but in the optimal way (i.e. removing a minimal number of statements).

### Challenge

You will write a program or a function that takes as input a list of statements, removes **the minimal number** of statements such that there is a **solution** and outputs the rest.

### Logic

Statements consist of *variables* `A-Z` and *operators* between them.

There are 5 *operators*: `-` (not), `v` (or), `^` (and), `->` (if) and `<->` (iff).

Truth table:

```
A | B | -A | AvB | A^B | A->B | A<->B
0 | 0 |  1 |  0  |  0  |   1  |   1
0 | 1 |  1 |  1  |  0  |   1  |   0
1 | 0 |  0 |  1  |  0  |   0  |   0
1 | 1 |  0 |  1  |  1  |   1  |   1

```

These *operators* can be combined together with parenthesis `()`:

```
A | B | -(AvB) | Av(-A) | A^(-A) | (AvB)->(-B)
0 | 0 |    1   |    1   |    0   |      1
0 | 1 |    0   |    1   |    0   |      0
1 | 0 |    0   |    1   |    0   |      1
1 | 1 |    0   |    1   |    0   |      0

```

*Logic systems* consist of 1 or more *statements*.

A *solution* to the *logic system* is a state where all of the *statements* are simultaneously true.

### Examples of logic systems:

```
AvB
-(A<->B)
(AvB)->(-B)

```

The only *solution* is `A = 1, B = 0`.

```
A^B
-(B<->A)

```

This one has no *solution*; with no combination of `A` and `B` both of the *statements* are true.

### Input

You will receive a set of *statements* as input. This can be taken via STDIN or function arguments, formatted as an array (in a convenient format) or a newline-separated or space-separated string.

The statements will be of the following form (in almost-ABNF):

```
statement        = variable / operation
operation        = not-operation / binary-operation
not-operation    = "-" operand
binary-operation = operand binary-operator operand
operand          = variable / "(" operation ")"
variable         = "A"-"Z"
binary-operator  = "v" / "^" / "->" / "<->"

```

Example statements:

```
A
Av(-B)
(A<->(Q^C))v((-B)vH)

```

### Output

You must return the (possibly) reduced set of statements, in the exact form you received them. Again, the list can be formatted as an array of strings or a newline-separated or space-separated string.

### Rules

* You should always remove the minimal number of statements. If there are multiple possible solutions, output one of them.
* You may assume that the input always contains at least 1 statement and that no statements are repeated in the input.
* You may not assume that the output always contains a statement. (see examples)
* Using standard loopholes contradicts with your answer being valid, and one of them must be removed.
* This is , so the shortest answer in bytes wins.

### Examples

Input:

```
A^(-A)

```

Output:

```
(nothing)

```

Input:

```
A^B A<->(-B) A<->B

```

Output:

```
A^B A<->B

```

Input:

```
["AvB","A^B"]

```

Output:

```
["AvB","A^B"]

```

# Answer
# Ruby, ~~299~~ ~~298~~ ~~283~~ 279 bytes

```
class Object;def * o;!self|o;end;def s;w=join.gsub(/\W/,"").chars.uniq;n=w.size;(0..2**n).any?{|i|n.times{|j|eval(w[j]+"=#{i[j]>0}")};all?{|e|eval([%w[<-> ==],%w[-> *],%w[- !],%w[^ &],%w[v |]].inject(e){|x,i|x.gsub(*i)})}}?self:combination(size-1).map(&:s).max_by(&:size);end;end

```
* Expects an array of expressions.
* If you're going to run it, set $VERBOSE=nil from inside ruby so you don't get lots of warnings about redefining constants.
* Note that it actually sets the variable "v" as well but it doesn't make a difference.
* Uses truth values because they have all of the required operators already, except implication. Unfortunately Ruby doesn't have a boolean class so we have to monkey-patch Object to get implication :)
* Could make it shorter if we just set ALL of the uppercase variables, but then it would take a huge amount of time to run. Should probably have a caveat in the question about that.

Ungolfed:

```
class Object
  def * o
    !self|o
  end
end

def sat? exs
  #exs: an array of expressions
  s=[%w[<-> ==], %w[-> *], "-!", "^&", %w[v ||]]

  w=exs.join.gsub(/\W/,"").chars.uniq #variable names
  n=w.size
  if (0...2**n).any? {|i|
    n.times do |vi|
      eval("#{w[vi]}=#{i[vi]==1}")
    end
    exs.all?{|ex|eval(s.inject(ex){|x,i|x.gsub(i[0],i[1])})}
  }
    exs
  else
    exs.combination(exs.size-1).map{|sm|sat?(sm)}.max_by(&:size)
  end
end

```
> 4 votes

# Answer
# Python 3, 431 bytes

Not very golfed right now, but I figure I'd get the ball rolling with an answer. Try it here, `g()` is the main function.

```
import re,itertools as H
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper());l=i.split()
 def e(s):
  def f(a):
   for v,w in a:exec(v+'='+w)
   return eval(re.sub('[^A-Z()]+',lambda x:{'v':' or ','^':'*','<->':'==','->':'<=','-':'not '}[x.group()],s))
  return[c for c in H.product("01",repeat=len(y))if f(zip(y,c))]
 for n in range(len(l),-1,-1):
  for q in H.combinations(l,n):
   if e('('+')^('.join(q)+')'):return' '.join(q)

```
> 5 votes

---
Tags: code-golf
---