title: Prime parity peregrination

text:
# Question
Title: Prime parity peregrination
The purpose of this challenge is to graphically depict a walk on the plane, where the direction of each step \\$k\\$ is determined by the primality of \\$k\\$ and the parity of its binary expansion. Specifically,

* **Initial** direction is fixed, say North.
* All steps have the same **length**.
* The **direction** of step \\$k\\$ can be North, West, South or East, and is determined as follows:
    + If \\$k\\$ is not prime, the direction does not change.
    + If \\$k\\$ is prime and the binary expansion of \\$k\\$ has an even number of ones, turn right.
    + If \\$k\\$ is prime and the binary expansion of \\$k\\$ has an odd number of ones, turn left.

As a **worked example**, assume that the initial direction is North. The first steps are:

* \\$k=1\\$ is not prime. So we move one step in the current direction, which is North.
* \\$k=2\\$ is prime, and its binary expansion, `10`, has and odd number of ones. So we turn left, and are now facing West. We move one step in that direction.
* \\$k=3\\$ is prime, and its binary expansion, `11`, has and even number of ones. So we turn right, and are now facing North. We move one step in that direction.
* \\$k=4\\$ is not prime. So we move one step in the current direction, which is North.

# The challenge

**Input**: positive integer \\$N\\$.

**Output**: plot of the \\$N\\$-step walk as defined above.

# Additional rules

* The **initial direction** can be freely chosen (not necessarily North), but should be the same for all \\$N\\$.
* The **turning rule** can be the opposite to that described above, that is, turn right for odd parity and left for even; but it has to be the same for all \\$N\\$.
* The output has to be a **graphical depiction** of the walk. For instance:
    + The walk can be drawn with line segments.
    + The visited points can be shown with a marker, such as a dot; with or without connecting line segments.
    + A two-colour raster image can be provided, with one colour corresponding to visited points and another for non-visited.
* The scales of the horizontal and vertical axes need not be the same. Also axis labels and similar elements are optional. As long as the walk can be clearly seen, the plot is valid.
* Note that some points are visited more than once. The plot is not sensitive to this. For instance, if line segments are shown in the plot, each unit segment is displayed the same no matter how many times it has been traversed.
* The code should work for any `N` given unlimited resources. It is acceptable if in practice it fails for large `N` due to time, memory or data-type limitations.
* Input and output are flexible as usual. In particular, any of the standard means for outputting images can be used.
* The shortest code in bytes wins.

# Test cases

The following plots use North as initial direction; even parity turns right; and the walk is depicted with line segments.

`N = 7`:

`N = 3000`:

`N = 20000`:

`N = 159000`:

`N = 1200000`:

`N = 11000000`:

# Answer
# Sledgehammer 0.4, ~~22~~ 20 bytes

```
⢂⡐⠥⡄⠡⢒⣩⣀⣼⡝⢄⡎⣛⠅⡉⣱⡆⢀⡠⣽

```

Decompresses into this Wolfram Language function:

```
ListPlot[AnglePath[Array[If[PrimeQ@#, ArcSin[(-1)^ThueMorse@#], 0] &, #]]]

```

### Ungolfed

First we define a function that returns the angle to turn at each step:

```
If[PrimeQ[#],
    ArcSin[(-1)^ThueMorse@#],
    0
]&

```

`ThueMorse` is the parity of the sum of binary digits. We use `-1^(...)` rather than `2*...-1` for a slightly complicated reason: Wolfram Language automatically converts arithmetic expressions in source to a canonical form, so expressions like `2/x` are stored as `Times[2, Power[x, -1]]`. This makes the frequency of `Power` very high, and thus compressing it very cheap.

(Multiplying by `Boole@PrimeQ@` is slightly longer, and implicit `Boole` casting of Booleans had not been implemented at the time of the challenge.)

From here, Mathematica's `AnglePath` and `ListPlot` do exactly what we need:

```
ListPlot[AnglePath[Array[%, #]]]&

```

In the interactive app, output is a rescalable vector Graphics object.
> 12 votes

# Answer
# MATL, ~~25~~ ~~24~~ 21 bytes

```
Q:qJyZpbB!sEq*^YpYsXG

```

Try it at MATL online

Thanks @LuisMendo for a nice golfing session in chat that ultimately led to this 21 byte version, by suggesting `Eq*^`

## Explanation

```
Q:q % Push 0:n
J   % Push 1i for later use.
y   % Duplicate 0:n from below
Zp  % Vector result of isprime()
b   % Bubble 0:n from bottom of stack
B!s % Sum of bits in binary representation
Eq  % Double minus one to get an odd number
*   % Multiply by isprime result to get either zero or aforementioned odd number
^   % Exponentiate 1i by an odd number or zero to get -i, 1 or i (corresponding to left turn, straight ahead, right turn).
Yp  % Cumulative product to get a vector of directions
Ys  % Cumulative sum to get vector of positions
XG  % Plot

```

Example for \\$k=12345\\$:
> 15 votes

# Answer
# Wolfram Language (Mathematica), ~~98~~ ~~96~~ ~~91~~ ~~77~~ ~~76~~ 63 bytes

```
ListPlot@AnglePath@Array[Pi/2If[PrimeQ@#,2ThueMorse@#-1,0]&,#]&

```

-14 bytes: Thanks to @lirtosiast for showing me how to use `AnglePath`...

-13 bytes: ...and `ThueMorse`!

usage example:

```
%[20000]

```

Step-by-step explanation:

* `If[PrimeQ@#, 2 ThueMorse@# - 1, 0] &` is a function that takes the step index and returns 0 for non-primes, -1 for even-binary primes, and +1 for odd-binary primes. `ThueMorse@#` replaces the previous solution's `Total[#~IntegerDigits~2]` (which is the same, modulo 2).
* `Array[Pi/2*%,#]` makes a list of this function with the index going from 1 to the function argument (20000 in the example), and multiplies every element by π/2 to make it into a direction-change angle (radians). We now have 0 for non-primes, -π/2 for even-binary primes, and +π/2 for odd-binary primes.
* `AnglePath[%]` converts this list of direction-change angles into a path. This instruction replaces the previous solution's double-use of `Accumulate`.
* `ListPlot[%]` converts the list of positions into a XY dot plot. If a line is preferred, use `ListLinePlot` instead. These plotting functions have lots of options to make the plots look better.
> 8 votes

# Answer
# C (gcc), 179 bytes

```
o;i;d;k;h;f(n,p)char*p;{h=2*n+1;memset(p,0,h*h);p+=h--*n+n;*p=1;for(d=k=0;k++<n;){for(i=1;k%++i%k;);for(o=k;o/2;o=o/2^o&1);i==k?d+=o*2+3:0;p+=(d%2*h+1)*((d&2)-1);*p=1;}return++h;}

```

Try it online!

A function. First argument is N, second argument is an allocated buffer of size at least \\$4 n^2 + 4 n + 1\\$ bytes. A square image is written to this buffer, its side length is returned. In the image, `0` is a white pixel, `1` is a black pixel.

# C (gcc), 219 bytes

```
o;i;d;k;h;f(n,p)char*p;{h=2*n+1;p+=sprintf(p,"P1 %d %d ",h,h);memset(p,48,h*h);k=h--*n+n;*(p+2*k+1)=0;p+=k;*p=49;for(d=k=0;k++<n;){for(i=1;k%++i%k;);for(o=k;o/2;o=o/2^o&1);i==k?d+=o*2+3:0;p+=(d%2*h+1)*((d&2)-1);*p=49;}}

```

Try it online!

A function. First argument is N, second argument is an allocated buffer of size at least \\$4 n^2 + 4 n + 2 \times \lfloor log\_{10}(2n+1)\rfloor + 9\\$ bytes. A square image in PBM format is written to the buffer.

Cropped output for 20000:

Both versions start with west and turn right on odd, left on even.

I tried the larger testcases with neither of them, as the output with 20000 was ~1.5 GB, and 150000 would have been ~90GB. This is all stored in memory while the program executes.

Explanation of the upper one:

```
o;         /* Temporary variable for calculating parity */
i;         /* Temporary variable for primality test */
d;         /* d % 4 = direction */
k;         /* Step */
h;         /* height/width of image */
f(n,p)char*p;{ /* Function taking int and char pointer */
  h=2*n+1;     /* Image sidelength = 2 * N + 1, so N in each direction */
  memset(p,0,h*h); /* Reset buffer */
  p+=h--*n+n;  /* Position p at image center; decrement h */
  *p=1;        /* Put a dot at center */
  for(d=k=0;   /* Set direction and step to 0 */
    k++<n;){   /* Loop over [1..N] */
    for(i=1;k%++i%k;); /* Primality test */
    for(o=k;o/2;o=o/2^o&1); /* Parity test */
    i==k?d+=o*2+3:0; /* Change direction if necessary */
    p+=(d%2*h+1)*((d&2)-1); /* Move according to direction */
    *p=1; /* Set pixel to black */
  }
  return++h; /* Add 1 back to h and return */
}

```
> 8 votes

# Answer
# MATL, ~~31~~ ~~30~~ ~~28~~ 26 bytes

```
J4:^0i:Zpl_G:B!s^*hYs)YsXG

```

*3 Bytes saved thanks to @LuisMendo*

*2 Bytes saved thanks to @Sanchises*

Try it at MATL Online

**Explanation**

This solution uses complex numbers to represent the X and Y components of the 2D plane

```
J      % Push the literal complex number 0 + 1j to the stack
4:     % Create the array [1, 2, 3, 4]
^      % Raise 0 + 1j to each power in the array, [1, 2, 3, 4]

```

At this point, we have four points (`(0, 1), (-1, 0), (0, -1), (1, 0)`) in an array represented by complex numbers. These are the four cardinal directions. Now we want to use these to "walk".

Essentially the way that this works is that we start heading in the zero'th direction (the 0'th element of the array which is `(-1, 0)`). For each step, we need to determine the change in this heading. We will use integers to track this change. If we want to turn "right", we increment this integer by 1 (referencing the *next* element in the 4-point array) and if we want to go "left", we decrement this integer by 1 (referencing the *previous* element in the 4-point array). If we want to continue on our path, we keep the integer value constant (referencing the *same* element in the 4-point array).

This part of the code creates an array of all of those `0`, `-1`, and `1` values.

```
0      % Push a literal 0 to the stack (the starting point)
i      % Explicitly grab the input (N)
:      % Create an array from 1...N
Zp     % Determine if each element is a prime (1) or not (0)
l_     % Push the literal -1 to the stack
G      % Explicitly grab the input again (N)
:      % Create an array from 1...N
B      % Convert to binary representation (each row is the binary representation of
       % each element in the vector)
!      % Transpose
s      % Sum down the columns to count number of 1's
^      % Raise the -1 to each element. For odd number of 1's in the
       % binary expansion this yields -1, and even yields 1

*      % Multiply this -1 or 1 by the result of the prime check (element-wise).
       % For non-primes this yields a 0, for primes with an even number of 1's in
       % the binary representation this is a 1, and for primes
       % with an odd number of 1's in

h      % Horizontally concatenate with the initial 0

```

Now we have an array of the differences between successive integers so we can compute the cumulative sum of those up to get the indices which we can then use to lookup the direction at each step in the original 4-element array.

Conveniently, MATL has wrap-around indexing such that index `5` wraps around to the beginning of a 4-element array. We can use this to our advantage so that we can increment and decrement this integer without worrying about the fact that the reference direction array is only 4 elements.

```
Ys     % Compute the cumulative sum
)      % Use this to modularly index into the original array of four points

```

Now we have an array of directions of steps takes, so we can compute the cumulative sum of these directions to trace out the path that was taken.

```
Ys     % Compute the cumulative sum
XG     % Plot as a 2D plot

```
> 7 votes

# Answer
# Perl 6, ~~213~~ 182 bytes

~~{my @p=\[\\+\] \[\\\*\]({{.is-prime??.base(2).comb(~1)%2??i!!-i!!1+0i}(++$)}...\*)\[^$\_\];{"\<svg viewBox='{.min xx 2,.elems xx 2}'\>\>.&{"L{.re} {.im}"}}' fill='none' stroke='black'/\>"}(minmax |@p».reals)}~~

```
{{"<svg viewBox='{{.min,.min,+$_,+$_}(.minmax)}'><path d='{"L"X~$_}' fill='none' stroke='red'/></svg>"}(([\+] [\*]({-{.is-prime*.base(2).comb(~1)R**-1||i}(++$)i}...*)[^$_])».reals)}

```

Try it online!

(Really managed to pare this one down!)

This function outputs in SVG format.

* `{ -{ .is-prime * .base(2).comb(~1) R** -1 || i }(++$)i } ... *` is an infinite sequence of direction changes for each step, in the form of complex numbers, where `1` means "continue in the same direction," `i` means "turn left," and `-i` means "turn right."
* `[^$_]` limits that sequence to the number of steps provided as the function's argument.
* `[\*]` scans that sequence with (complex) multiplication, turning the list of relative direction changes into a list of absolute directions.
* `[\+]` scans *that* sequence with (complex) addition, producing a list of the visited coordinates.
* `».reals` converts that list of complex numbers into two-element lists of its real and imaginary parts.

The SVG image is just one single `path` element.

Output (converted to PNG) for N = 20000:
> 5 votes

# Answer
## LOGO, ~~177~~ 171 bytes

```
to d:c
if :c%2[rt 180
make"c:c-1]if:c<1[stop]d:c/2
end
to p
if:c>1[make"f 2
repeat:c-2[if:c%:f<1[stop]make"f:f+1]rt 90
d:c]end
to g:n
make"c 1
repeat:n[p
fw 2
make"c:c+1]end

```

To use, do something like this:

```
reset
pu
fw 100
pd
g 3000

```

Sorry, but I wasn't able to capture sample output. Explanation:

```
to d:c
if :c%2[rt 180
make"c:c-1]if:c<1[stop]d:c/2
end

```

This is a recursive procedure which rotates 180° for every set bit in its parameter, which effectively computes the parity of its binary expansion.

```
to p
if:c>1[make"f 2
repeat:c-2[if:c%:f<1[stop]make"f:f+1]rt 90
d:c]end

```

This is a very basic primality test. After special-casing 1, the procedure early returns if a factor is found. If however the current value is found to be prime, it turns right, and then uses the above procedure to change that into a left turn as appropriate.

```
to g:n
make"c 1
repeat:n[p
fw 2
make"c:c+1]end

```

This is just a simple loop to test all the numbers up to `n` for primality and to move two pixels after each one.
> 4 votes

# Answer
## C, 321 bytes

```
a,b,A,B,k,p,e,i,t,r;g(n,c,d,x,y,X,Y){x=y=Y=r=0;X=1;for(k=0;k++<=n;){r|=x==c&y==d;a=x<a?x:a;A=x>A?x:A;b=y<b?y:b;B=y>B?y:B;for(p=1,i=k;--i;p=p*i*i%k);for(e=1,i=k;i;e=-e)i&=i-1;if(p)t=X,X=-e*Y,Y=e*t;x+=X;y+=Y;}}f(n,x,y){A=a=B=b=0;g(n);printf("P1%d %d ",A-a+1,B-b+1);for(y=b;y<=B;++y)for(x=a;x<=A;++x)g(n,x,y),putchar(48+r);}

```

Try it online!

I started working on this before the other C answer was posted, but I figured I might as well post mine as well anyway. This one is a lot longer, but it also crops the output image to the dimensions of the result automatically.

Function is called as `f(n)`, and output is to stdout in netpbm format.

Example output for n=1000:

```
a,b,A,B,          // used to store x range [a,A] and y range [b,B]
k,p,e,i,t,        // temp variables used in g
r;g(n,c,d,        // takes n + coordinates, sets r to whether (c,d) is visited
x,y,X,Y){         // temp variables - position (x,y) and velocity (X,Y)
x=y=Y=r=0;X=1;    // initialization
for(k=0;k++<=n;){ // loops k over the step number
r|=x==c&y==d;     // set r to 1 if current coordinate is the requested one
a=x<a?x:a;A=x>A?x:A;b=y<b?y:b;B=y>B?y:B;    // update bounds
for(p=1,i=k;--i;p=p*i*i%k);                 // prime test
for(e=1,i=k;i;e=-e)i&=i-1;                  // parity test
if(p)t=X,X=-e*Y,Y=e*t;                      // if prime, turn accordingly
x+=X;y+=Y;}}      // move position in direction of velocity
f(n,x,y){         // main function; x and y are temp variables
A=a=B=b=0;g(n);   // obtain accurate bounds
printf("P1 %d %d\n",A-a+1,B-b+1);           // output netpbm header
for(y=b;y<=B;++y)for(x=a;x<=A;++x)          // loop through all coordinates
g(n,x,y),putchar(48+r);}                    // output 1 if visited, 0 otherwise

```

The prime test is essentially the one used in Lynn's answer to a different challenge, which relies on Wilson's theorem.

The parity test uses an adaptation of Kernighan's bit-counting method.

Since the prime test is very slow, and the algorithm re-runs the entire path generation function for each pixel drawn, any input much higher than 1000 times out on TIO.
> 4 votes

# Answer
# Jelly, 41 bytes

```
B§ḂḤ’×ıµ1Ẓ?€×\ÄŻÆiZ_Ṃ$€Z‘ḞŒṬµẈḢ⁾P1,;Lṭ@FK

```

Try it online!

Full program that takes a single argument \\$N\\$ and outputs a 1-bit PBM to STDOUT. Takes some inspiration from @Sanchises MATL answer. Starts off going South and turns left on odd bit parity.

Sample output for \\$N=3000\\$:

If ASCII Art were permissible, here’s an alternative 29-byte variant which yields (for \\$N=300\\$):

```
0000000000000000000000111110000000000
0000000000000000000000100010000000000
0000001110000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000111111111010000000000
0000001010000000100000101010000000000
0000001111111110100000101010000000000
0000000000100010100000101010000000000
0000000000111111100000101010001111111
0000000000000010000000101010001000001
0000000000000011100010101010001000001
0000000000000000100010101010001000001
0000111111100000100011111111111111111
0100100000100000100010001010001000001
0110100000111111100011111111111000111
0010100000000000000010101010000000101
1111100000000000000010101110000000101
1010000000000000000010100000000000101
1010000000000000000011111111111011101
1010000000000000000000100000001010101
1110000000000000000000111111101111101
0000000000000000000000000000100010101
0000000000000000000000000000100010101
0000000000000000000000000000100010101
0000000000000000000000000000111111111
0000000000000000000000000000000010100
0000000000000000000000000000000010100
0000000000000000000000000000000010100
0000000000000000000000000000000011100

```
> 4 votes

# Answer
# JavaScript - ~~675~~ ~~668~~ ~~660~~ ~~632~~ ~~556~~ 534 Bytes

First time here on CodeGolf, initially started with ~1500 Bytes Code. Golfed it to ~~less than half~~ ~~nearly~~ more than a third of it. Feel free to continue golfing. Bytes Counted with: this tool

Principle:
Draws into fixed size canvas with N and variable stroke length as input.

### Edits:

-07 Bytes - remove of missed if
-08 Bytes - change switch to if/else
-28 Bytes - change to tenary if/else
-76 Bytes - shorter prime test (runtime / 3)
-22 Bytes - use this prime function (runtime * 4)

### Golfed Code:

```
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}

```

### Ungolfed code with whitespaces:

```
function f(e,r){
    for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){

        // prime and odd/even check
        n=iP(a)?iO(a)?1:2:0;

        var u=i,c=f;

        t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));

        o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),
        i=u,f=c // renew old cords
    }
}

// check prime
function iP(h){
    for(i=n=h;n%--i;);
    return(1==i)
}

// check binary expression even/odd
function iO(e){
    for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)
        "1"==r[n]&&t++;
    return t%2!=0
}

```

### Examples:

> N = 7 - Length = 60
>
> ```
> f(7, 60);
> function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
> ```
>
> ```
> <canvas id="d" width="1900" height="900"/>
> ```
>
> N = 3000 - Length = 4
>
> ```
> f(3000, 4);
> function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
> ```
>
> ```
> <canvas id="d" width="1900" height="900"/>
> ```
>
> N = 20000 - Length = 2
>
> ```
> f(20000, 2);
> function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
> ```
>
> ```
> <canvas id="d" width="1900" height="900"/>
> ```
>
> N = 159000 - Length = 1
>
> ```
> f(159000, 1);
> function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
> ```
>
> ```
> <canvas id="d" width="1900" height="900"/>
> ```
> 4 votes

# Answer
# Red, ~~515~~ ~~480~~ 471 bytes

-1 byte thanks to Kevin Cruijssen!

```
func[n][a: 270 x: t: u: v: w: 0 y: 1
b: copy[line 0x0 0x1]repeat i n - 1[p: on
j: i + 1 repeat k i / 2[if j%(k + 1)= 0[p: off]]if p[s: 0
until[if j% 2 = 1[s: s + 1](j: j / 2)< 1]a: a + pick[-90 90]s% 2 + 1]append b 'line
append b as-pair x y x: x + cosine a y: y - sine a append b as-pair x y t: min x t
u: max x u v: min y v w: max y w]c: 500 /(max u - t w - v)view[base white 502x500
draw collect[foreach k b[keep either pair? k[as-pair k/1 - t * c k/2 - v * c][k]]]]]

```

A significant part of the code (~160 bytes) deals with normalizing the coordinates so that the graphics fits entirely in the canvas regardless of the size of the input.

Initial direction: South.

Here's the result for `n = 3000`

##

`n = 20000`
> 3 votes

# Answer
# Processing , 140+ bytes

```
void f(int N){for(int x,y,i,l,d,k=d=y=x=0;k++<N;d+=i<l?0:Integer.bitCount(k)%2*2-1,d&=3,point(x-=~-d%2,y+=(d-2)%2))for(i=1,l=k;0<l%++i%l;);}

```

Might not fulfill clearly seen
> 1 votes

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


# Question
Title: Better Hex Color Codes for Your Internet
Hex triplets such as `#ffffff` (white) or `#3764ef` (blueish) are often used to denote RGB colors. They consist of `#` followed by six hexadecimal digits (0-f), or sometimes three digits where the real color is obtained by doubling each digit. For example, `#fff` is `#ffffff` and `#1a8` is `#11aa88`.

Sadly, that three digit shorthand was the golfiest the internet had to offer, *until now*.

Write a program or function that takes in a string of 1 to 7 characters:

* The first character will always be `#`.
* The other characters will always be hexadecimal digits: `0123456789abcdef`.

The input is a shorthand form of a hex triplet (or the full form if 7 characters are given). You need to output a full hex triplet that expands the input shorthand based on these patterns:

```
Input   -> Output
#       -> #000000    (black)
#U      -> #UUUUUU
#UV     -> #UVUVUV
#UVW    -> #UUVVWW    (usual 3-digit shorthand)
#UVWX   -> #UXVXWX
#UVWXY  -> #UVWXYY
#UVWXYZ -> #UVWXYZ    (not shorthand)

```

Each of `U`, `V`, `W`, `X`, `Y`, and `Z` may be any hexadecimal digit. The output is always 7 characters.

For example:

```
Input -> Output
# -> #000000
#0 -> #000000
#4 -> #444444
#f -> #ffffff
#a1 -> #a1a1a1
#0f -> #0f0f0f
#99 -> #999999
#1a8 -> #11aa88
#223 -> #222233
#fff -> #ffffff
#1230 -> #102030
#d767 -> #d77767
#bbb5 -> #b5b5b5
#aabbc -> #aabbcc
#00000 -> #000000
#3764e -> #3764ee
#3764ef -> #3764ef
#123456 -> #123456
#f8f8f8 -> #f8f8f8

```

# Notes

* The input will always start with `#` and so must the output.
* You may assume all input letters are lowercase (`abcdef`) or uppercase (`ABCDEF`) as you prefer.
* Letters in the output may be in either case as you prefer. You can even mix cases.
* Alpha/transparency is not dealt with here (though there are hex versions of RGBA colors).

**The shortest code in bytes wins.**

# Answer
# JavaScript, ~~86~~ ~~82~~ 77 bytes

```
x=>([s,a=0,b=a,c,d,e,f]=x,f?x:e?x+e:[s,a,d||a,c?b:a,d||b,v=c||b,d||v].join``)

```

just find out that remove recursive save 4 bytes...

idea from @Arnauld save 4 bytes, +1 more bytes
> 13 votes

# Answer
# Jelly, 24 bytes

```

x2
j0ị$
m0

0
Ḣ;LĿṁ6$$

```

A full program (the empty lines are actually empty lines).

**Try it online!** or see a test suite*

### How?

```
     - Link 1 (0 bytes), returns its input (e.g. "U" -> "U")
     - Link 2 (0 bytes), returns its input (e.g. "UV" -> "UV")
x2   - Link 3, doubles up (e.g. "UVW" -> "UUVVWW")
j0ị$ - Link 4, joins with final element (e.g. "UVWX" -> "UXVXWXX")
m0   - Link 5, reflects its input (e.g. "UVWXY" -> "UVWXYYXWVU")
     - Link 6 (0 bytes), returns its input (e.g. "UVWXYZ" -> "UVWXYX")
0    - Link 7, returns zero (link 7 is also link 0 since there are 7 links)
Ḣ;LĿṁ6$$ - Main link: string
Ḣ        - head (get the '#')
       $ - last two links as a monad:
   Ŀ     -   call link at index:
  L      -     length
      $  -   last two links as a monad:
    ṁ6   -     mould like 6 (e.g. "UVWXYYXWVU" -> "UVWXYY"
         -                    or  "UV" -> "UVUVUV")
 ;       - concatenate (prepend the '#' again)
         - implicit print

```

* the test-suite program had to be altered by swapping the order of what were the `Main link` and `Link 7`, while the footer became the `Main Link`. Furthermore the `#` had to be manually replaced, since the program as-is heads it.
> 6 votes

# Answer
## CJam, ~~45~~  ~~44~~  ~~42~~ ~~40~~ ~~36~~ 35 bytes

```
q(\0se|_,("6* 3* 2e* )f+ _W=+ "S/=~

```

Runs various code snippets based on the length of the input.
> 5 votes

# Answer
# PHP 7.1, 88 bytes

```
#<?for(;$i<6;)echo@$argn[_22222232532233423355224462[5*$i+++strlen($argn|aa)*.85]-1]?:0;

```

### PHP 5, 90 88 bytes

```
#<?for(;$i<6;)echo$argn[_10311001122011333002244012345[6*$i+++strlen($argn|aa)-8]+1]?:0;

```
> 4 votes

# Answer
# Java 10, ~~228~~ ~~227~~ ~~224~~ 182 bytes

```
s->{var x="$1$1";int l=s.length();return l>6?s:l>5?s+s.charAt(5):l<2?"#000000":s.replaceAll(l>4?"(.)(.)(.)(.)$":l==3?"([^#]{2})":"([^#])",l>4?"$1$4$2$4$3$4":l>3?x:l>2?x+"$1":x+x+x);}

```

Try it online.

**Explanation:**

```
s->{                      // Method with String as both parameter and return-type
  var x="$1$1";         //  Create a temp String to repeat a match
  int l=s.length();     //  Length of the String
  return l>6?           //  If the length is 7:
    s                   //   Return the input-String as is
   :l>5?                //  Else-if the length is 6:
    s+s.charAt(5)       //   Return the input-String with the last character repeated
   :l<2?                //  Else-if the length is 1:
    "#000000";          //   Simply return the literal String #000000
   :                    //  Else (the length is 2, 3, 4, or 5):
    s.replaceAll(       //   Return the input-String after a regex replace:
                        //    With as match:
     l>4?               //     If the length is 5:
      "(.)(.)(.)(.)$",  //      Use a match for pattern #(A)(B)(C)(D)
     :l==3?             //     Else-if the length is 3:
      "([^#]{2})"       //      Use a match for pattern #(AB)
     :                  //     Else (the length is 2 or 4):
      "([^#])",         //      Use a match for pattern #(A) or #(A)(B)(C)
                        //    And as replacement:
     l>4?               //     If the length is 5:
      "$1$4$2$4$3$4"    //      Change #ABCD to #ADBDCD
     :l>3?              //     Else-if the length is 4:
      x                 //      Change #ABC to #AABBCC
     :l>2?              //     Else-if the length is 3:
      x+"$1"            //      Change #AB to #ABABAB
     :                  //     Else (the length is 2):
      x+x+x);}          //      Change #A to #AAAAAA

```
> 3 votes

# Answer
# Python 3, ~~166~~ ~~162~~ ~~160~~ 152 bytes

```
import re
lambda x,d='(.)$',b=r'\1':re.sub(*[('$','0'*6),(d,b*6),('(..)$',b*3),('(\w)',b*2),('.'+'(.)'*4,r'#\1\4\2\4\3\4'),(d,b*2),('','')][len(x)-1],x)

```

I construct a list of regex replacement tuples for each pattern, and then extract the tuple at index `len(x)-1`, finally splatting (`*`) it into the arguments of `re.sub`:

```
lambda x, d='(.)$', b=r'\1':   # lambda expression, save often used strings
  re.sub(   # regex replacement of:
         *  # expand what follows into arguments, i.e. f(*(1,2)) -> f(1,2)
         [  # list of replacement patterns:
            # 1 character: replace the end with 6 zeroes
            ('$', '0'*6),
            # 2 chars: repeat the last character 6 times
            (d, b*6),
            # 3 chars: repeat the two non-#s 3 times.
            ('(..)$', b*3),
            # 4 chars: replace every non-# with twice itself
            ('(\w)', b*2),
            # 5 chars: has to be somewhat verbose..
            ('.'+'(.)'*4, r'#\1\4\2\4\3\4'),
            # 6 chars: repeat the last character
            (d, b*2),
            # 7 chars: complete already, replace nothing with nothing
            ('', '')
         ][len(x)-1], # select the element from the list that has the right length
        x)  # replace in argument x

```

*saved 8 bytes by memorizing `r'\1'` (thanks, Gábor Fekete)*
> 3 votes

# Answer
## PHP, ~~95~~ ~~93~~ ~~89~~ 87

```
<?=strtr(_1.intval([a6n,sot,c8c,lba,vf1,vf2][strlen($argn|aa)-2],33),_134256,$argn.=0);

```

Basically @JörgHülsermann's answer but greatly golfed down so I decided to post it as a seperate answer. I'd count this answer as an collective effort of me and Jörg.

```
-4 bytes thanks to @JörgHülsermann
-1 bytes thanks to @JörgHülsermann's base 33 numbers

```
> 3 votes

# Answer
# APL (Dyalog), 43 bytes

Requires `⎕IO←0` which is default on many systems.

```
'#',{6⍴(≢⍵)⊃'0'⍵ ⍵(2/⍵)(∊⍵,¨⊃⌽⍵)(⍵,⌽⍵)⍵}1↓⍞

```

Try it online!

`1↓⍞` drop the first character (the hash)

`{` apply the following anonymous function

`(≢⍵)⊃` use the length of the argument to pick one of the following seven values:
`'0'` a zero
the argument
the argument
`2/⍵` two (`2`) of each (`/`) of the argument ()
`∊⍵,¨⊃⌽⍵` the flattened () argument () followed each () by the first () of the reversed () argument ()
`⍵,⌽⍵` the argument () prepended (`,`) to the reversed () argument ()
the argument

`6⍴` repeat elements from that until a length of six is achieved

`}` end of anonymous function

`'#',` prepend a hash to that
> 2 votes

# Answer
# Python 2, ~~167~~ 165 bytes

*-2 bytes thanks to Trelzevir*

```
z=zip
lambda s:'#'+''.join([reduce(lambda x,y:x+y,c)for c in['0'*6,s[1:2]*6,z(s[1:2],s[2:3])*3,z(*z(s[1:2],s[2:3],s[3:4]))*2,z(s[1:4],s[-1]*3),s+s[-1],s][len(s)-1]])

```

It creates a list of strings and chooses based on the length of the string.
> 2 votes

# Answer
# Retina, 90 bytes

```
#(..)$
#$1$1$1
#(.)(.)(.)$
#$1$1$2$2$3
#(.)(.)(.(.))$
#$1$4$2$4$3
#$
#0
+`#.{0,4}(.)$
$&$1

```

Try it online! Includes test cases.

Explanation: The first translation handles two digits, the second one three, the third one four, and the fourth one zero. However, neither the second and fourth translations repeat the (last) digit, as that is done at the end anyway to cover all the remaining cases.
> 2 votes

# Answer
# Haskell, 130 127 122 118 109 95 bytes (by user1472751)

```
y a|l<-[last a]=[y"0",y$a++a,a++a++a,do c<-a;[c,c],(:l)=<<init a,a++l,a]!!length a
f(h:r)=h:y r

```

Try it online!
> 2 votes

# Answer
# PHP, 87 Bytes

use Base 35 Numbers

```
<?=strtr(_2.intval([i4w,qdi,j1y,apg,ruu,ruv][strlen($argn|aa)-2],35),_234156,$argn.=0);

```

Try it online!

or use Base 33 Numbers

```
<?=strtr(_1.intval([a6n,sot,c8c,lba,vf1,vf2][strlen($argn|aa)-2],33),_134256,$argn.=0);

```

Try it online!

# PHP, 89 Bytes

```
<?=strtr(_1.[11111,21212,12233,42434,23455,23456][strlen($argn|aa)-2],_123456,$argn."0");

```

Try it online!

`intval(["8kn",gd8,"9ft",wqq,i3j,i3k][strlen($argn|aa)-2],36)` \+ 3 Bytes using a 36 Base

## PHP, 102 Bytes

```
<?=strtr("01".substr("11111111112121212233424342345523456",5*strlen($argn)-5,5),str_split($argn."0"));

```

Try it online!

# PHP, 180 Bytes

```
<?=[str_pad("#",7,($l=strlen($p=substr($argn,1)))?$p:0),"#$p[0]$p[0]$p[1]$p[1]$p[2]$p[2]","#$p[0]$p[3]$p[1]$p[3]$p[2]$p[3]","#$p[0]$p[1]$p[2]$p[3]$p[4]$p[4]",$argn][($l>2)*($l-2)];

```

Try it online!
> 2 votes

# Answer
# Sed, 119 (118 Bytes + `-E`)

```
s/#//
s/^$/0/
s/^.$/&&/
s/^..$/&&&/
s/^(.)(.)(.)$/\1\1\2\2\3\3/
s/^(.)(.)(.)(.)$/\1\4\2\4\3\4/
s/^....(.)$/&\1/
s/^/#/

```

Straightforward text substitution.
> 2 votes

# Answer
# Powershell, ~~113~~ 111 bytes

```
param($s)-join($s+='0'*($s-eq'#'))[0,1+((,1*5),(2,1*2+2),(1,2,2,3,3),(4,2,4,3,4),(2..5+5),(2..6))[$s.Length-2]]

```

Explaned test script:

```
$f = {

param($s)           # parameter string
$s+='0'*($s-eq'#')  # append '0' if $s equal to '#'
$i=(                # get indexes from array
    (,1*5),         # $i = 1,1,1,1,1 if $s.length-2 = 0
    (2,1*2+2),      # $i = 2,1,2,1,2 if $s.length-2 = 1
    (1,2,2,3,3),    # $i = 1,2,2,3,3 if $s.length-2 = 2
    (4,2,4,3,4),    # $i = 4,2,4,3,4 if $s.length-2 = 3
    (2..5+5),       # $i = 2,3,4,5,5 if $s.length-2 = 4
    (2..6)          # $i = 2,3,4,5,6 if $s.length-2 = 5
)[$s.Length-2]
-join$s[0,1+$i]     # join chars from $s by indexes 0, 1 and $i

}

@(
    , ("#", "#000000")
    , ("#0", "#000000")
    , ("#4", "#444444")
    , ("#f", "#ffffff")
    , ("#a1", "#a1a1a1")
    , ("#0f", "#0f0f0f")
    , ("#99", "#999999")
    , ("#1a8", "#11aa88")
    , ("#223", "#222233")
    , ("#fff", "#ffffff")
    , ("#1230", "#102030")
    , ("#d767", "#d77767")
    , ("#bbb5", "#b5b5b5")
    , ("#aabbc", "#aabbcc")
    , ("#00000", "#000000")
    , ("#3764e", "#3764ee")
    , ("#3764ef", "#3764ef")
    , ("#123456", "#123456")
    , ("#f8f8f8", "#f8f8f8")
) |% {
    $s, $e = $_
    $r = &$f $s
    "$($e-eq$r): $r"
}

```

Output:

```
True: #000000
True: #000000
True: #444444
True: #ffffff
True: #a1a1a1
True: #0f0f0f
True: #999999
True: #11aa88
True: #222233
True: #ffffff
True: #102030
True: #d77767
True: #b5b5b5
True: #aabbcc
True: #000000
True: #3764ee
True: #3764ef
True: #123456
True: #f8f8f8

```
> 2 votes

# Answer
# JavaScript (ES6), 96 bytes

```
s=>'#'+(c=[u,v,w,x,y,z]=s.slice(1)||'0',z?c:y?c+y:(x?u+x+v+x+w+x:w?u+u+v+v+w+w:c.repeat(v?3:6)))

```

```
f=
s=>'#'+(c=[u,v,w,x,y,z]=s.slice(1)||'0',z?c:y?c+y:(x?u+x+v+x+w+x:w?u+u+v+v+w+w:c.repeat(v?3:6)))

console.log(
  f('#'),
  f('#U'),
  f('#UV'),
  f('#UVW'),
  f('#UVWX'),
  f('#UVWXY'),
  f('#UVWXYZ')
)
```
> 1 votes

# Answer
# Windows batch, ~~389 372 362 349~~ 231 bytes

*I totally copied @Neil code...*

```
@call:c %s:~1,1% %s:~2,1% %s:~3,1% %s:~4,1% %s:~5,1% %s:~6,1%
@exit/b
:c
@for %%r in (#%1%2%3%4%5%6.%6 #%1%2%3%4%5%5.%5 #%1%4%2%4%3%4.%4 %s%%1%2%3.%3
%s%%1%2%1%2.%2 %s%%1%1%1%1%1.%1 #000000.0)do @if not %%~xr.==. @echo %%~nr&exit/b

```
> 1 votes

# Answer
## Perl, 61 bytes

```
say+(/./g,0)[0,1,(unpack+S7,"g+g+ÜRÉ/Â¥[ [")[y/#//c]=~/./g]

```

Run with `perl -nE`. Assumes that the input is exactly as described (gives incorrect results if the input has a trailing newline).

The string "g+g+ÜRÉ/Â¥\[ \[" encodes the 7 16-bit numbers `11111,11111,21212,12233,42434,23455,23456` as 14 latin1 characters. Here’s a hexdump for clarity:

```
0000001d: 672b 672b dc52 c92f c2a5 9f5b a05b       g+g+.R./...[.[

```
> 1 votes

# Answer
# Pyth, 35 bytes

```
+\#@<R6[J|tQ\0K*6JKKs*R2JjeJJ+JeJ)l

```

Try it online here, or verify all test cases here.

```
+\#@<R6[J|tQ\0K*6JKKs*R2JjeJJ+JeJ)lQ   Implicit: Q=eval(input())
                                       Trailing Q inferred
          tQ                           Remove first char of input
         |  \0                         The above, or "0" if empty
        J                             *Store in J (also yields stored value)
              K*6J                    *Repeat J 6 times, store in K
                  KK                  *2 more copies of the above
                    s*R2J             *Duplicate each char of J in place
                         jeJJ         *Join chars of J on last char of J
                             +JeJ     *Append last char of J to J
       [                         )     Wrap the 5 starred results in an array
    <R6                                Trim each to length 6
   @                              lQ   Choose result at index of length of input
                                       (Modular indexing, so length 7 selects 0th element)
+\#                                    Prepend #, implicit print

```
> 1 votes

# Answer
# Python 2, 99 bytes

```
def a(s):s=s[1:]or'0';l=len(s);print('#'+(l/4*s[-1]).join(i+i*(l==3)for i in(l<5)*6*s)+s+s[-1])[:7]

```

Try it online!
> 1 votes

# Answer
## **Python 2 - 179 bytes**

```
n=raw_input()                                #prompts for string
t=len(n)                                     #the length of the string is stored to 't'
if t==1:n+="0"*6                             #if t is only one char long, it needs to be black, so n is assigned 6 zeroes
if t==2:n+=n[1]*5                            #if t is two chars long, it adds the last character times 5 at the end
if t==3:n+=n[1:3]*2                          #if t is 3 chars, it multiplies the last two digits times 3
if t==4:n="#"+n[1]*2+n[2]*2+n[3]*2           #if t is 4 chars, it multiplies each char by two
if t==5:n=n[:2]+n[4]+n[2]+n[4]+n[3]+n[4]     #if t is 5 chars, it makes it work
if t==6:n+=n[t-1]                            #if t is 6 chars, it adds the last character to the end
print n                                      #it prints out n

```

Can anyone help me save some bytes? All of the if statements seem like they could be shortened into something shorter, I just don't know what.
> 0 votes

# Answer
TXR Lisp: 171 bytes

Indented:

```
(do let ((s (cdr @1)))
  (caseql (length s)
    (0 "#000000")
    (1 `#@s@s@s@s@s@s`)
    (2 `#@s@s@s`)
    (3 `#@[mappend list s s]`)
    (4 `#@[s 0]@[s 3]@[s 1]@[s 3]@[s 2]@[s 3]`)
    (5 `#@s@[s 4]`)
    (6 `#@s`))))

```

This is an anonymous function: the `do` macro generates a `(lambda ...)` form.

It is idiomatic coding style, suitable for production; the only golfing is squashing whitespace:

```
(do let((s(cdr @1)))(caseql(length s)(0"#000000")(1`#@s@s@s@s@s@s`)(2`#@s@s@s`)(3`#@[mappend list s s]`)(4`#@[s 0]@[s 3]@[s 1]@[s 3]@[s 2]@[s 3]`)(5`#@s@[s 4]`)(6`#@s`))))

```
> 0 votes

# Answer
# Braingolf, 95 bytes

```
l1-.1e$_!&@4>[!@]|.2e$_!&@!@2!@2|.3e$_<@V2[R<!@!@v]|.4e$_<@VRM&,2>[@v!@R]|.5e$_<@!&@@|.6e$_&@|;

```

Try it online!

This is effectively Braingolf's equivalent of a switch-case on the amount of characters after the `#` in the input.

### Explanation

Stuff that always runs:

```
l1-.1  Implicit input to stack
l      Push length of stack
 1-    Decrement last item in stack
   .   Duplicate last item in stack
    1  Push 1

```

If `#X`:

```
e$_!&@4>[!@]|
e              If last 2 items (input length - 1 and 1) are equal..
 $_            ..Pop last item silently
   !&@         ..Print entire stack as chars without popping
      4>       ..Push 4 and move it to start of stack
        [..]   ..While loop, decrements first item in stack when it reaches ]
               ..If first item in stack is 0 when reaching ], exit loop
               ..This loop will run 5 times
         !@    ....Print last char without popping
            |  endif

```

If `#XX`

This one may be golfable a little, I might look at it when I get home

```
.2e$_!&@!@2!@2|
.2               Duplicate last item and push 2
  e              If last 2 items (input length - 1 and 2) are equal..
   $_            ..Pop last item silently
     !&@         ..Print entire stack as chars without popping
        !@2      ..Print last 2 items as chars without popping
           !@2   ..Print last 2 items as chars without popping
              |  Endif

```

If `#XXX`

```
.3e$_<@V2[R<!@!@v]|
.3                   Duplicate last item and push 3
  e                  If last 2 items (input length - 1 and 3) are equal..
   $_                ..Pop last item silently
     <@              ..Move first item in stack to the end, then pop and print
       V2            ..Create new stack and push 2 to it
         [.......]   ..While loop, see above for explanation
          R<         ....Switch to stack1 and move first item to end of stack
            !@!@     ....Print last item on stack twice without popping
                v    ....Move to stack2 for loop counting
                  |  Endif

```

You get the idea
> 0 votes

# Answer
# Ruby, 127 bytes

```
c=~/#(.)?(.)?(.)?(.)?(.)?(.)?/
$6?c:'#'+($5?$1+$2+$3+$4+$5*2:$4?$1+$4+$2+$4+$3+$4:$3?$1*2+$2*2+$3*2:$2?($1+$2)*3:$1?$1*6:"0"*6)

```

Try it online!
> 0 votes

# Answer
# Ruby, 118 bytes

```
def f c
c.sub!'#',''
s=c.size
t=c[3]
s>5?'#'+c:f(s<1?'0':s<2?c*6:s<3?c*3:s<4?c*2:s<5?c[0]+t+c[1]+t+c[2]+t:c+c[-1])
end

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 24 bytes

```
ćU©0®Ð€D®S¤ý®¤«)JIgè6∍Xì

```

Try it online or verify all test cases.

**Explanation:**

```
ć           # Extract the head of the (implicit) input-string;
            # pop and push remainder and head
 U          # Pop and store the head in variable `X`
  ©         # Store the remainder in variable `®` (without popping)
  0         # Push a 0
  ®Ð        # Push `®` three times
    €D      # Duplicate each character in the last copy (which becomes a character-list)
  ®S        # Push variable `®` again, converted to a character-list
    ¤       # Get its last character (without popping the list itself)
     ý      # Join the list by this character
  ®         # Push variable `®` once again
   ¤        # Get its last character (without popping the string itself)
    «       # Append it to the string
  )         # Wrap all values into a list
   J        # Join the inner list from `€D` together to a list,
            # or in case of input `#`, join everything together to string "0"
            #  i.e. "#" → (["","0","","","",""] → ) "0"
            #  i.e. "#4" → ["4","0","4","4","44","4","44"]
            #  i.e. "#a1" → ["a1","0","a1","a1","aa11","a11","a11"]
            #  i.e. "#1a8" → ["1a8","0","1a8","1a8","11aa88","18a88","1a88"]
            #  i.e. "#abcd" → ["abcd","0","abcd","abcd","aabbccdd","adbdcdd","abcdd"]
            #  i.e. "#3764e" → ["3764e","0","3764e","3764e","33776644ee","3e7e6e4ee","3764ee"]
            #  i.e. #123456 → ["123456","0","123456","123456","112233445566","16263646566","1234566"]
    Ig      # Push the length of the input
      è     # Index (0-based) this into the list (with automatic wraparound for length=7)
       6∍   # Extend/shorten the string to length 6
         Xì # And prepend variable `X` (the "#")
            # (after which the result is output implicitly)

```
> 0 votes

---
Tags: code-golf, string, hexadecimal, color
---


# Question
Title: Write the shortest code to match a tail-repeating string where one character falls off the head in each repetition
In this code-golf, you will attempt to match a string that is tail-repeating with one character falling off the head on each iteration. The code needs to be able to accept a string, and return to the user whether the string meets the above criteria.

Examples:

```
"", "x", and "xx" -> False

```

EDIT: There is some speculation about whether this is theoretically correct. I will accept any implementation that returns the same value for the three above values as of now. However I do not have an official position on whether this is true or false. Hopefully someone can formalize this.

The above cases will always be false regardless of the circumstance because the string is too short to have the property of tail repetition with one character falling off the head. For example "xx"'s first "tail" would be "x" and there is nothing after the "xx", so it would be false. The character does not matter here, "x" is an example.

```
"abb" -> True

```

"abb" is the simplest string I can think of that should be true, because if you take what we will call the "tail" off of it, you get "bb", then knock one character off the head, and you get "b", which is the next character in the string.

```
"abcbcc" -> True

```

"abcbcc" is the next simplest string I can think of that should be true. So far in contemplating this problem, testing the truth from the beginning to the end of the string seems difficult, so I'll explain from the end up.

```
"c", "cb", "cba"

```

When you examine the string in reverse it seems easier to determine where the "first tail" ends. It ends at the first "c" in "abc", but this can only be inferred from examining the string in reverse, to the best of my knowledge so far.

Here is an example of a string that does not match:

```
"abcbca" -> False

```

If we try to apply the above reverse-proof method to it:

```
"a", "cb"

```

we realize at the second step when the first character in the second string is not "a", that this must be false.

Shortest code in characters to implement this logic in any programming language wins.

EDIT: If you find a solution other than the suggested one, it is still a valid entry (and very cool!)

# Answer
# Brachylog, 8 bytes

```
aa₁ᶠc?ẹṀ

```

Try it online!

Takes input through the input variable and outputs through success or failure. I don't quite get why length-zero and length-one initial heads have to have the same output as the very straightforwardly illegal `"xx"`, but fortunately ruling them out only takes two bytes.

```
    c       The concatenation of
   ᶠ        every
 a₁         suffix (in descending order of length) of
a           some adfix of the input
     ?      is the input,
      ẹṀ    which has multiple elements.

```

Instead of using a sane algorithm to walk backwards through the input and match each repetition, or determine the initial head from the length of the input then generate the rest and check for equality, this brute-forces the initial head from the set of all adfixes of the input (not just prefixes, because that would be a byte longer).
> 2 votes

# Answer
# Python

Used the fact that the length of a valid string will always be a Triangle Number.

```
t=raw_input()
x=int(len(t+t)**.5)
print t==''.join(t[i:x]for i in range(x))

```

A Ruby solution might be shorter, will post soon.
> 5 votes

# Answer
## GolfScript, 25 chars

```
.,,{1$<..,{(;.@\+\}*;}%?)

```

**NB** This requires the most recent version of Golfscript, which supports a `string array ?` indexof function.

This implements the interpretation whereby `""` and `"x"` are not in the language, which IMO is a funny way to define it. It is a statement which takes one argument on the stack and leaves an integer which can be interpreted as a boolean in standard GolfScript fashion (i.e. 0 for false, anything else for true). To turn this into a full program prepend `n-` and postpend some suitable manipulation depending on what output you want (e.g. `"true""false"if`).
> 4 votes

# Answer
## Ruby, 63 characters

```
t=->x{b="";x.size>1&&(b,x=$2+b,$1while x=~/(.*)(.)#{b}/;x=="")}

```

This method returns true iff the string fits the definition.

Usage:

```
p t["abcbbc"]  # -> false
p t["abcbcc"]  # -> true

```
> 3 votes

# Answer
# Perl regex, ~~24~~ 69

```
^.(.+)(?{$a=$+})((??{"\Q$a"})(?{$a=substr$a,1}))*(?(?{''eq$a})$|(*F))

```

Obviously not a genuine CS regular expression, ~~but those modern recursive regexes can work wonders~~ and the edited (but fixed) version is not that short at all. I'm starting to wonder if actual Perl code, with the ability to reverse the starting string, wouldn't be shorter than that.
> 3 votes

# Answer
## Haskell, 48 characters

```
import List
f x=any((==x).concat.tails)$inits x

```

Brute force. Note that this returns true for `f "x"` and `f ""`. Example usage in GHCi:

```
> f "abb"
True
> f "abcbcc"
True
> f "abcbca"
False

```
> 3 votes

# Answer
## VBA, 113 characters

Adding my 2 VBA cents...

```
Function t(s)
k=Right(s,Len(s)-1)
t=Round(Len(k)/2)
If t>0 Then If Left(k,t)<>Right(k,t) Then t=t(k)
End Function

```

This returns a 1 or 0.

Usage is `MsgBox t("abcbcc")`, or to get a `"True"/"False"` outsput, use `MsgBox CBool(t("abcbcc"))`
> 2 votes

# Answer
# C, 191 bytes

That's the best I can golf this in C:

```
main(){char a[9],*b=a,p[9],c=0,i=strlen(gets(a)),j=0,k=0;p[0]='\0';while(i>=0){b[strlen(b=a+(i-=++j))-k]='\0';k=strlen(b);if(strcmp(p,b+1)&&c++)exit(puts("false"));strcpy(p,b);}puts("true");}

```
> 2 votes

# Answer
# Pyth, ~~33~~ 22 bytes

This is my second attempt on Pyth :)

```
qz_jk.__<z/t@+1*8lz2 2
                       print(
q                       is_equal(
 z                       input(),
  _                       reverse(
   jk                      concat(
     ._                     all_prefixes(
       _                     reverse(
        <z                    input()[:
          /t@h*8lz2 2          divide(decrement(root(increment(multiply(8,len(z))),2)),2)
                                ])))))

```

---

Previous attempt:

```
KJ<z/t@+1*8lz2 2;WnkJ=K+K=JtJ;qKz

```

Try it online!

How it works:

```
KJ<z/t@+1*8lz2 2;WnkJ=K+K=JtJ;qKz
                                    z=input()
KJ<z/t@+1*8lz2 2                    K=J=z[:(root(1+8*len(z),2)-1)/2]
  <z                                    z[:
       +1*8lz                                    1+8*len(z)
      @      2                              root(          ,2)
     t                                                        -1
                 WnKJ               while not_equal(k,J):
                     =K+K=JtJ        K=plus(K,J=tail(J))
                              qKz   equal(K,z)

```
> 2 votes

# Answer
# Element, 40 characters

```
_)#3:s;m;$'[m~)#4:m;$'[(#2:'."]#s~=[1`]]

```

This is a language of my own creation. It is designed so that all operators are one character long and always perform the same function. This allows the programs to be much shorter than many other programming languages. In some challenges, however, I must program something for which there is no built-in function, causing the program to grow in size. Element has no built-in regex matching of any kind, so I think that I actually did pretty well on this challenge.

This is a complete program that will take one line of input as the string to test, and it will print a `1` for true and nothing for false.

As for why I am answering code golf questions in Element, it is partially to raise awareness, partially a publicity stunt, and partially an exercise to test the language.

A description of Element can be found here, and the (hopefully working) source of an interpreter for Element (written in Perl) can be found here.
> 1 votes

# Answer
## Scala 113:

```
def t(s:String):Boolean={
val k=s.tail
val l=k.size
if(l<2)false else
if(k.take(l/2)==k.drop(l/2))true else
t(k)}

```

Takes rekursively the rest of the string, and tests whether first half equals second.

ungolfed:

```
def tailrepeating (s: String): Boolean = {
  val k=s.tail
  if (k.size < 2) false else
  if (k.take (k.size /2) == k.drop (k.size / 2)) true else
  tailrepeating (k) }

```
> 1 votes

# Answer
## bash 111

```
#!/bin/bash
s=$1
l=${#s}
for i in $(seq 1 $((l-2)))
do
test "${s:i:$(((l-i)/2))}" = "${s:$(((l+i)/2))}"&&exit 0
done||false

```

111 chars without shebang. Invocation:

```
./tailrepeated.sh foobalaa && echo "true" || echo "false"

```
> 1 votes

# Answer
# C (gcc), 80 bytes

```
i,j,k,l;f(b,e)char*b;{for(i=j=k=e<2;e--;k|=l?i-=++j:b[e]-b[j+e])l=++i>j;b=!k*l;}

```

Try it online!

Rejects `"x"` and `""`. -1 if `"x"` can be accepted, and another -1 if `""` is ok as well.
> 1 votes

# Answer
Here is my own un-golfed answer in C for testing.

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

int tailrep(char *str, char *sub, int sublen, int len) {
    if (str == sub) {
        return 1;
    }

    int i;
    for (i = 0; i < sublen; i++) {
        char *a,  *b;
        a = str + len - sublen;
        b = sub + sublen - 1;

//        printf("%p->%c %p->%c\n", a - i, a[-i], b - i, b[-i]);
        if (a[-i] != b[-i]) {
            return 0;
        }
    }

    return tailrep(str, sub - sublen - 1, sublen + 1, len - sublen);
}

int istailrep(char *str) {
    int len = strlen(str);
    if (len < 3) {
        return 0;
    }
    return tailrep(str, str + len - 1, 1, len - 1);
}

int main() {
    // must be false
    assert(!istailrep(""));
    assert(!istailrep("a"));
    assert(!istailrep("aa"));
    assert(!istailrep("aab"));
    assert(!istailrep("abcbbc"));
    assert(!istailrep("abcdabcdabcd"));

    // must be true
    assert(istailrep("aaa"));
    assert(istailrep("abb"));
    assert(istailrep("abcbcc"));
    assert(istailrep("abcdbcdcdd"));
    assert(istailrep("abcdebcdecdedee"));
    printf("yay\n");
    return 0;
}

```
> 0 votes

---
Tags: code-golf, string, decision-problem
---


title: Hamilton is coming to town

text:
# Question
Title: Hamilton is coming to town
It's almost Christmas, so Santa has to plan his route. You're helping him, for reasons unknown.

Santa needs help planning the route and wants you to give him a solution, but since you're all ungrateful and unwilling to give to the man who has given you so much, so have decided to give him a program with as few bytes as possible to accomplish the following.

The houses Santa needs to visit can be represented by coordinates on the Cartesian plane (the coordinates of the houses need not be integers, there cannot be more than 1 house at any point, and there is no house at the origin). These coordinates will be the input. Starting at the origin, Santa will visit each coordinate and then return to the origin.

Santa rides his sleigh at a constant one unit per second in a straight line between houses. However, when Santa crosses any lattice point (a point with integer x and y coordinates) he stops for one second to eat a cookie (the initial and final crossings of the origin do not count, though crossing it on the path between, say, `(-1,-1)` and `(1,1)` would). When he stops at a house, he spends five seconds to deliver a present (so he spends six seconds at houses on lattice points).

Write a program that takes as its input a set of coordinates and prints the **smallest** number of seconds Santa needs to deliver all of the presents to the houses and return to the origin, rounded to three digits. Take 25% off your code if it also prints any order of coordinates Santa visits that minimizes the time.

---

**Test cases**

```
(1,1) (2,4) (2,2)
==> 14.301
==> (Bonus) (1,1) (2,2) (2,4)

(3,4) (2,-1) (0,-3.5) (1,6)
==> 27.712
==> (Bonus) (0,-3.5) (2,-1) (3,4) (1,6)

```

This is code golf. Standard rules apply. Shortest code in bytes wins.

---

Note that this *is* a modification of the Travelling Salesman Problem, so your program does not need to terminate in any reasonable amount of time for an unreasonable number of inputs (this is a problem in O(n!) after all).

# Answer
# Perl 6, 198 bytes (264 bytes - 25% bonus)

Managed to actually get this sucker into a Whatever block by inlining the helper functions from the original version.

```
*.permutations.map({([+] -1,5*@_,|(for (0,0),|@_ Z |@_,(0,0) ->((\i,\j),(\x,\y)){my ($s,\p)=0,i.Rat.nude[1]*j.Rat.nude[1]*abs(i -x).Rat.nude[0];(i+(x -i)*$_/p)%%1&&(j+(y -j)*$_/p)%%1&&$s++ for ^p;sqrt(abs(i -x)²+abs(j -y)²)+(p??$s!!abs(j.Int -y.Int))})),@_}).min

```

Try it online!

No doubt there are still a few little improvements that can be made. Trickiest part was figuring out how to calculate the number of lattice points crossed. The solution I went with uses the denominators of each X coordinate to calculate an iteration interval that is guaranteed to hit each whole number along with X axis, thus allowing a check for landing on a lattice point. There is a catch, of course, that if there is no movement along X then the lattice points crossed will be the absolute value of the floor value of each Y coordinate.

This will be, nonetheless, very tricky for languages that don't have built in rationals, because of floating point errors (I can already see the .1 + .2 = .3 issue cropping up if any two X or Y coordinates are 10 apart).

Ungolfed version:

```
*                           #  Whatever block, takes a list of coordinates
.permutations.map({         #  Get all combinations and to each of them ...
 (                          #   Implicitly return a list consisting of
  [+]                       #    The sum of
   -1,                      #     -1 (to discount lattice +1 on return to origin)
   5*@_,                    #     5 * number of coordinates (or stops)
   |(for                    #     each value in the loop across
    (0,0),|@_ Z |@_,(0,0)   #      the coordinates (zipping with the origin
                            #        first/last for the return)
    ->((\i,\j),(\x,\y)) {   #      deconstructing into i,j,x,y
     my ($s,\p)=0,          #      set S (lattice stops) to 0
       i.Rat.nude[1]        #      set P (x check interval) to denominator of i
       *j.Rat.nude[1]       #       times denominator of p (psuedo lcm)
       *abs(i -x).Rat.nude[0]; #    times x-diff numerator (bc Rat simplification)
     (i+(x -i)*$_/p)%%1&&   #      check X is whole, if so,
      (j+(y -j)*$_/p)%%1&&  #       check Y is whole, if so,
      $s++                  #        increment S (trip crossed a lattice point)
     for ^p;                #      do the checks for 0 to P
     sqrt(                  #      implicitly return
      abs(i -x)²+abs(j -y)² #       the distance
     )+(p                   #        plus, if X values were different,
      ??$s                  #         S value, else
      !!abs(j.Int -y.Int)   #         Y difference = vertical lattice crossings
     )
    }
   )                        #
   ,@_)                     #   And the permutation
.min                        #  Find best (smallest) time

```

I'll probably add a more readable version because this golfing got unreadable fast.
> 1 votes

---
Tags: code-golf, number, graph-theory
---


title: Shortest Unique Substrings

text:
# Question
Title: Shortest Unique Substrings
# Input

An alphanumeric string `s`.

# Output

The shortest string that occurs exactly once as a (contiguous) substring in `s`. Overlapping occurrences are counted as distinct. If there are several candidates of the same length, you must output all of them in the order of occurrence. In this challenge, the empty string occurs `n + 1` times in a string of length `n`.

# Example

Consider the string

```
"asdfasdfd"

```

The empty string occurs 10 times in it, so it is not a candidate for unique occurrence. Each of the letters `"a"`, `"s"`, `"d"`, and `"f"` occurs at least twice, so they are not candidates either. The substrings `"fa"` and `"fd"` occur only once and in this order, while all other substrings of length 2 occur twice. Thus the correct output is

```
["fa","fd"]

```

# Rules

Both functions and full programs are allowed, and standard loopholes are not. The exact formatting of the output is flexible, within reason. In particular, producing no output for the empty string is allowable, but throwing an error is not. The lowest byte count wins.

# Test cases

```
"" -> [""]
"abcaa" -> ["b","c"]
"rererere" -> ["ererer"]
"asdfasdfd" -> ["fa","fd"]
"ffffhhhhfffffhhhhhfffhhh" -> ["hffff","fffff","hhhhh","hfffh"]
"asdfdfasddfdfaddsasadsasadsddsddfdsasdf" -> ["fas","fad","add","fds"]

```

# Leaderboard

Here's the by-language leaderboard that I promised.

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

```

```
<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 45056;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

# Answer
> 3 votes
# Pyth, ~~27~~ 26 bytes

```
&zhfTmf!/>zhxzYYm<>zkdUzUz

```

Try it here.

Note that due to a bug in the online compiler, the empty string case only works correctly on the command line version, which can be found here.

You can also cure the bug by giving a newline as the input for the online compiler.

### Explanation:

```
                                   z = input(), implicit.
&z                                 Prints empty string if input is empty.
  hfT                              Take the first non-empty list from
     m                  Uz         A list of list of substrings of z, divided by length
                m<>zkdUz           with some shorter strings repeated later, to no effect.
      f                            Where the substrings are filtered on
       !/      Y                   There being 0 occurrences of the substring in
         >z                        The slice of z
           hxzY                    from the character after the first character
                                   of the first occurrence of the substring in z
                                   to the end of z.

```

# Answer
> 13 votes
# Python 3, ~~124~~ ~~123~~ ~~111~~ 96 bytes

```
f=lambda s,n=1:[x for x in[s[i:i+n]for i in range(len(s)+1)]if s.find(x)==s.rfind(x)]or f(s,n+1)

```

Looks for strings such that the first occurrence from the left is the same as the first occurrence from the right. The `+1` in the `range` is to accommodate for the empty string case.

Now if only Python had a `.count()` which counted *overlapping* matches, then this would have been a fair bit shorter.

# Answer
> 6 votes
# Mathematica, ~~95~~ ~~94~~ 79 bytes

```
Cases[Tally@StringCases[#,___,Overlaps->All],{s_,1}:>s]~MinimalBy~StringLength&

```

`StringCases` gets me all possible substrings, the `Tally` and `Cases` filter out those that appear more than once and `MinimalBy` finds those that are shortest.

# Answer
> 4 votes
## GolfScript, 44 bytes

```
:S;-1:x{;S,x):x-),{S>x<}%:^1/{^\/,2=},.!}do`

```

Takes input as a string on stdin and outputs in a double-array syntax: e.g. `[["b"] ["c"]]`. Online demo

### Dissection

```
:S;          # Store input in S and pop it
-1:x         # Store -1 in x
{            # do-while loop
  ;          #   Pop x the first time and [] every subsequent time
  S,x):x-),  #   Increment x and build an array [0 1 ... len(S)-x]
  {S>x<}%    #   Map that array to [substr(S,0,x) substr(S,1,x) ...]
  :^         #   Store in ^ (to avoid the token coalescing with the next char)
  1/         #   Split by length 1 to iterate over 1-elt arrays rather than strings
  {^\/,2=},  #   Filter to arrays which occur exactly once as a subarray of ^
  .!         #   Duplicate and test emptiness
}do          # end do-while loop: loop if the filtered array is empty
`            # Stringify for output

```

This is arranged such that no special case is required for the empty string (which I've included as a test case in the online demo linked above).

# Answer
> 3 votes
# Java, 168 ~~176 233~~

Here's a pretty basic nested loop example.

```
void n(String s){for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)for(String b;i<=t-l;)if(s.indexOf(b=s.substring(i,i+++l),s.indexOf(b)+1)<0){System.out.println(b);q++;}}

```

Or a *bit* more readable:

```
void t(String s){
    for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)
        for(String b;i<=t-l;)
            if(s.indexOf(b=s.substring(i,i++ +l),s.indexOf(b)+1)<0){
                System.out.println(b);
                q++;
            }
}

```

# Answer
> 3 votes
# JavaScript (ES6), 109 ~~110~~

**Edit** search instead of indexOf, as the input string is alphanumeric. Thanks @IsmaelMiguel

Recursive function, looking for substrings starting with length 1 and going up.

```
F=(s,n=1,r)=>
s?[...s].map((a,i)=>~s.indexOf(a=s.substr(i,n),s.search(a)+1)?r:r=[...r||[],a])&&r||F(s,n+1):[s]

```

**Ungolfed** and explained

```
 F = function(s, n=1) { // start with length 1
   var i, a, p, r;
   if (s == "") // special case for empty input string
     return [s];
   for (i = 0; i < s.length; i++)
   // for each possibile substring of length n
   // (should stop at s.length-n+1 but going beyond is harmless)
   // Golfed: "[...s].map((a,i)" ... using i, a is overwrittem
   {
     a = s.substr(i, n); // substring at position i
     p = s.search(a); // p is the first position of substring found, can be i or less
     p = s.indexOf(a, p + 1) // p is now the position of a second instance of substring, or -1 if not found
     if (~p) // ~p is 0 if p is -1
     {
       ; // found more than once, do nothing
     }
     else
     {
       r = r || []; // if r is undefined, then it becomes an empty array
       r.push(a); // save substring
       // Golfed: "r=[...r||[],a]"
     }
   }
   if (r) // if found some substring, saved in r
   {
     return r;
   }
   return F(s, n+1) // recursive retry for a bigger length
 }

```

**Test** In FireFox/FireBug console

```
;["", "abcaa", "rererere", "asdfasdfd", "ffffhhhhfffffhhhhhfffhhh",
 "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"]
.forEach(x=>console.log(x,F(x)))

```

*Output*

```
 [""]
abcaa ["b", "c"]
rererere ["ererer"]
asdfasdfd ["fa", "fd"]
ffffhhhhfffffhhhhhfffhhh ["hffff", "fffff", "hhhhh", "hfffh"]
asdfdfasddfdfaddsasadsasadsddsddfdsasdf ["fas", "fad", "add", "fds"]

```

# Answer
> 3 votes
## J, ~~61~~ ~~58~~ ~~44~~ ~~42~~ ~~40~~ ~~38~~ 37 bytes

```
[:>@{.@(#~#@>)#\<@(~.#~1=#/.~)@(]\)]

```

Here is a version split up into the individual components of the solution:

```
unqs =. ~. #~ 1 = #/.~               NB. uniques; items that appear exactly once
allsbsq =. #\ <@unqs@(]\) ]        NB. all unique subsequences
shrtsbsq =. [: >@{.@(#~ #@>) allsbsq NB. shortest unique subsequence

```
* `x #/. y` computes for each distinct element in `x` how often in occurs in `y`. If we use this as `y #/. y`, we get the for each distinct element in `y` its count. For instance, `a #/. a` for `a =. 1 2 2 3 4 4` yields `1 2 1 2`.
* `1 = y` checks which items of `y` are equal to `1`. For instance, `1 = a #/. a` yields `1 0 1 0`.
* `u~` is the *reflexive* of a monadic verb `u`. This is, `u~ y` is the same as `y u y`. Thus, `#/.~ y` is the same as `#/.~ y`. When applied to a dyadic verb, `u~` is the *passive* of `u`. That is, `x u~ y` is the same as `y u x`. These are used in quite a few other places which I do not explicitly mention.
* `~. y` is the *nub* of `y`, a vector with duplicates removed. For instance, `~. a` yields `1 2 3 4`.
* `x # y` (*copy*) selects from `y` the items at the indices where `x` contains a `1`.
* Thus, `(1 = y #/. y) # (~. y)` creates a vector of those elements of `y` which appear only once. In tacit notation, this verb is written as `~. #~ 1 = #/.~`; let's call this phrase `unqs` for the rest of the explanation.
* `x ]\ y` creates an `x` by `1 + y - x` array of all *infixes* of the vector `y` of length `x`. For instance, `3 ]\ 'asdfasdfd` yields

```
asd
sdf
dfa
fas
asd
sdf
dfd

```
* `# y` is the *tally* of `y`, that is, the number of elements in `y`.
* `u\ y` applies `u` to each *prefix* of `y`. Incidentally, `#\ y` creates a vector of integers from `1` to `#y`.
* `< y` puts `y` into a box. This is needed because arrays cannot be ragged and we compute an array of suffixes of different lengths; a boxed array counts as a scalar.
* Thus, `(i. # y) <@:unqs@(]\) y` generates a vector of `#y` boxed arrays of the length *k* (for all 0 ≤ *k* \< `#y`) infixes of *y* that occur exactly once. The tacit form of this verb is `i.@# <@unqs@(]\) ]` or `i.@# <@(~. #~ 1 = #/.~)@(]\) ]` if we don't use the `unqs` name. Let's call this phrase `allsbsq` for the rest of this explanation. For instance, `allsbsq 'asdfasdfd'` yields:

```
┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┐
││ │fa│dfa│sdfa│asdfa│asdfas│asdfasd│asdfasdf│
││ │fd│fas│dfas│sdfas│sdfasd│sdfasdf│sdfasdfd│
││ │  │dfd│fasd│dfasd│dfasdf│dfasdfd│        │
││ │  │   │sdfd│fasdf│fasdfd│       │        │
││ │  │   │    │asdfd│      │       │        │
└┴─┴──┴───┴────┴─────┴──────┴───────┴────────┘

```
* `(#@> y) # y` takes from vector of boxed arrays `y` those which aren't empty.
* `{. y` takes the first element of vector `y`.
* `> y` removes the box from `y`.
* Thus, `> {. (#@> y) # y` yields the unboxed first non-empty array from vector of boxed arrays `y`. This phrase is written `>@{.@(#~ #@>)` in tacit notation.
* Finally, `[: >@{.@(#~ #@>) allsbsq` assembles the previous phrase with `allsbsq` to create a solution to the problem we have. Here is the full phrase with spaces:

```
[: >@{.@(#~ #@>) i.@# <@(~. #~ 1 = #/.~)@(]\) ]

```

# Answer
> 3 votes
# Scala, 120 bytes

```
readLine.inits.flatMap(_.tails).toList.groupBy(l=>l).filter(x=>x._2.length<2).map(_._1).groupBy(_.length).minBy(_._1)._2

```

I started off with 140 which at least already fits into a tweet.

```
(                                        // added for comments
 readLine                                // input
.inits.flatMap(_.tails).toList           // get all substrings of that string
.groupBy(l=>l).filter(x=>x._2.length<2)  // remove substrings that occur more than once
.map(_._1).groupBy(_.length)             // take the substring and group by length
.minBy(_._1)._2                          // take the list of shortest substrings
)

```

# Answer
> 3 votes
# CJam, ~~52 43~~ 40 bytes

```
]]q:Q,,{)Q,1$-),f{Q><}:R{R\a/,2=},}%{}=p

```

Input is the string without quotes

**Explanation**:

```
]]                                       "For empty string input case";
  q:Q                                    "Read the input and store in Q";
     ,,                                  "Take length of input and 0 to length array";
       {                          }%     "Map the above array on this code block";
        )Q                               "Increment the number in the current iteration, L";
         Q,1$                            "Take input's length and copy the above number";
             -)                          "Get upper limit of next loop to get substrings";
               ,f{   }                   "Get 0 to above number array and for each";
                  Q><                    "Get the L length substring at Ith index where";
                                         "I loops from 0 to Q, - L + 1";
                      :R                 "Store this list of substring of length L in R";
                        {R\a/,2=},       "Filter to get unique substrings";
                                    {}=  "Get the first non empty substring array";
                                         "This leaves nothing on stack if all are empty";
                                       p "Print the top stack element. At this point, its";
                                         "Either the first non empty substring array or";
                                         "the ]] i.e. [""] which we added initially";

```

Example:

```
asdfdfasddfdfaddsasadsasadsddsddfdsasdf

```

Output

```
["fas" "fad" "add" "fds"]

```

Try it online here

# Answer
> 3 votes
# Haskell, 169 162 155 153 151 138 120 115

```
import Data.List
l=length
q k=filter$(==)k.l
p y=q(minimum.map l$y)$y
f x=p$concat$q 1$group$sort$(tails x>>=inits)

```

To use it:

```
f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

```

Which gives:

```
["add","fad","fas","fds"]

```

Btw. I hate the last line of my code (repetition of `h y`). Anyone hints to get rid of it?

# Answer
> 2 votes
# PHP, ~~171~~ ~~152~~ ~~134~~ 125

```
function f($s){while(!$a&&++$i<strlen($s))for($j=0;$b=substr($s,$j++,$i);)strpos($s,$b)==strrpos($s,$b)&&($a[]=$b);return$a;}

```

http://3v4l.org/RaWTN

# Answer
> 2 votes
# Haskell, 135 Bytes

```
import Data.List
f ""=[""]
f g=map(snd)$head$groupBy(\a b->fst a==fst b)$sort[(length y,y)|[y]<-group$sort[x|x@(_:_)<-tails g>>=inits]]

```

# Answer
> 2 votes
# Rebol, 136 bytes

```
f: func[s][repeat n length? b: copy s[unless empty? x: collect[forall s[unless find next find b t: copy/part s n t[keep t]]][return x]]]

```

Ungolfed:

```
f: func [s] [
    repeat n length? b: copy s [
        unless empty? x: collect [
            forall s [
                unless find next find b t: copy/part s n t [keep t]
            ]
        ][return x]
    ]
]

```

Usage example:

```
>> f ""
== none

>> f "abcaa"
== ["b" "c"]

>> f "rererere"
== ["ererer"]

>> f "asdfasdfd"
== ["fa" "fd"]

>> f "ffffhhhhfffffhhhhhfffhhh"
== ["hffff" "fffff" "hhhhh" "hfffh"]

>> f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"
== ["fas" "fad" "add" "fds"]

```

NB. I suppose the heart of the code is how the `find` part is working. Hopefully this will help explain...

```
>> find "asdfasdfd" "df"
== "dfasdfd"

>> next find "asdfasdfd" "df"
== "fasdfd"

>> find next find "asdfasdfd" "df" "df"
== "dfd"

>> ;; so above shows that "df" is present more than once - so not unique
>> ;; whereas below returns NONE because "fa" found only once - ie. bingo!

>> find next find "asdfasdfd" "fa" "fa"
== none

```

# Answer
> 2 votes
# Groovy (Java regex on Oracle implementation), 124

```
c={m=it=~/(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))/;o=m.collect({it[1]});o.findAll({it.size()==o.min({it.size()}).size()});}

```

Tested on Groovy 2.4 + Oracle JRE 1.7. The regex should work for Java 6 to Java 8, since the bug that allows the code above to work is not fixed. Not sure for previous version, since there is a look-behind bug in Java 5 which was fixed in Java 6.

The regex finds the shortest string which doesn't have a duplicate substring elsewhere, at every position in the input string. The code outside takes care of filtering.

```
(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))

```
* Since the strings can overlap, I surround the whole thing in look-ahead `(?=...)`.
* `(.*?)` searches from the shortest substring
* `(?=(.*))` captures the rest of the string to mark the current position.
* `(?<=^(?!.*\1(?!\2$)).*)` is an emulation of variable-length look-behind, which takes advantage of the implementation bug which allows `(?<=.*)` to pass the length check.
* `(?!.*\1(?!\2$))` simply checks that you can't find the same substring elsewhere. The `(?!\2$)` rejects the original position where the substring is matched.

The limit of the outer look-around construct doesn't apply to the nested look-around construct. Therefore, the nested negative look-ahead `(?!.*\1(?!\2$))` actually checks for the whole string, not just up to the right boundary of the look-behind.

# Answer
> 1 votes
# Haskell, 119

```
f s=[r|n<-[1..length s],l<-[map(take n)$take(length s-n+1)$iterate(drop 1)s],r<-[[j|j<-l,[j]==[r|r<-l,r==j]]],r/=[]]!!0

```

# Answer
> 1 votes
# Brachylog, 10 bytes

```
sᶠ≡ᵍ~gˢlᵍt

```

Try it online!

```
sᶠ            The list of every substring of the input
  ≡ᵍ          grouped by identity,
    ~gˢ       with length-1 groups converted to their elements and other groups discarded,
       lᵍ     and grouped by their length,
         t    has the output as its last group.

```

Although  doesn't naturally sort by the value it groups by, instead ordering the groups by the first occurrence of each value, the first occurrences of every length are in decreasing order. I'm not 100% sure that the uniqueness filtering can't mess this up, but I haven't come up with a test case this fails yet.

# Answer
> 1 votes
# 05AB1E, 10 bytes

```
Œʒ¢}é.γg}н

```

Outputs nothing for an empty string.

Try it online or verify all test cases.

**Explanation:**

```
Œ           # Get all substrings of the (implicit) input-String
 ʒ          # Filter it by:
  ¢         #  Count how many times the current substring occurs in the (implicit) input-String
            #  (only 1 is truthy in 05AB1E, so the filter will leave unique substrings)
   }é       # After the filter: sort the remaining substrings by length
     .γg}   # Then group them by length as well
         н  # And only leave the first group containing the shortest substrings
            # (which is output implicitly as result)

```

This takes advantage of 05AB1E's only having `1` as truthy value, and everything else as falsey. The shortest unique substring is always guaranteed to occur exactly once for all possible input-strings. (For an input-string containing only the same characters (i.e. `aaaaa`), the input-strings itself as substring occurs just once, so the result is `["aaaaa"]`. For an input-String with repeating pattern (i.e. `"abcabc"`), there are still unique substrings that only occur once (`["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]`), so this will result in `["ca"]`.)

# Answer
> 0 votes
# Python 2, 150

```
import re
a=input()
r=range
l=len(a)
d=0
for i in r(l):
 if d:break
 for j in r(l-i):
  k=a[j:i+j+1]
  if len(re.findall("(?="+k+")",a))<2:d=1;print k

```

# Answer
> 0 votes
# Perl 5 `-a`, ~~114~~ 87 bytes

```
map{//;(grep$' eq$_,@q)-1||($l||=y///c)-y///c||say}@q=map{"@F"=~/(?=(.{$_}))/g}1..y///c

```

Try it online!

Old method: 114 bytes

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


title: Golf the smallest circle!

text:
# Question
Title: Golf the smallest circle!
## The problem:

Given a non-empty set of points in the Cartesian plane, find the smallest circle that encloses them all (Wikipedia link).

This problem is trivial if the number of points is three or less (if there's one point, the circle has a radius of zero; if there are two points, the line segment that joins the points is the diameter of the circle; if there are three (non-colinear) points, it's possible to get the equation of a circle that touches them all if they form a non-obtuse triangle, or a circle that touches only two points and encloses the third if the triangle is obtuse). So, for the sake of this challenge, the number of points should be greater than three.

## The challenge:

* **Input:** A list of 4 or more non-colinear points. The points should have X and Y coordinates; coordinates can be floats. To ease the challenge, no two points should share the same X coordinate.
For example: `[(0,0), (2,1), (5,3), (-1,-1)]`
* **Output:** A tuple of values, `(h,k,r)`, such that \\$(x-h)^2 + (y-k)^2 = r^2\\$ is the equation of the smallest circle that encloses all points.

## Rules:

* You can choose whatever input method suits your program.
* Output should be printed to `STDOUT` or returned by a function.
* "Normal", general-purpose, languages are preferred, but any esolang is acceptable.
* You can assume that the points are not colinear.
* This is code-golf, so the smallest program in bytes wins. The winner will be selected one week after the challenge is posted.
    + Please include the language you used and the length in bytes as header in the first line of your answer: `# Language: n bytes`

## Test cases:

* 1:
    + Input: `[(-8,0), (3,1), (-6.2,-8), (3,9.5)]`
    + Output: `[-1.6, 0.75, 9.89]`
* 2:
    + Input: `[(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]`
    + Output: `[-1.73, 0.58, 11.58]`
* 3:
    + Input: `[(0,0), (1,2), (3,-4), (4,-5), (10,-10)]`
    + Output: `[5.5, -4, 7.5]`
* 4:
    + Input: `[(6,6), (-6,7), (-7,-6), (6,-8)]`
    + Output: `[0, -0.5, 9.60]`

Happy golfing!!!

---

## Related challenge:

# Answer
# Wolfram Language (Mathematica), ~~28~~ 27 bytes

```
#~BoundingRegion~"MinDisk"&

```

Try it online!

Built-ins are handy here. Output is a disk object with the centre and radius. Like others, I’ve found the 2nd and 3rd test cases to be different to the question.

Thanks to @lirtosiast for saving a byte!

If a list is required as output, this can be done in 35 bytes (at the cost of an additional 8 bytes). Thanks to @Roman for pointing this out.
> 26 votes

# Answer
# JavaScript (ES6),  ~~298 ... 243~~  242 bytes

Returns an array `[x, y, r]`.

```
p=>p.map(m=([c,C])=>p.map(([b,B])=>p.map(([a,A])=>p.some(([x,y])=>H(x-X,y-Y)>r,F=s=>Y=(d?((a*a+A*A-q)*j+(b*b+B*B-q)*k)/d:s)/2,d=c*(A-B)+a*(j=B-C)+b*(k=C-A),r=H(a-F(a+b),A-F(A+B,X=Y,j=c-b,k=a-c)))|r>m?0:o=[X,Y,m=r]),q=c*c+C*C),H=Math.hypot)&&o

```

Try it online!

or see a formatted version

## How?

### Method

For each pair of points \\$(A,B)\\$, we generate the circle \\$(X,Y,r)\\$ whose diameter is \\$AB\\$.

$$X=\frac{A\_x+B\_x}{2},\\;Y=\frac{A\_y+B\_y}{2},\\;r=\sqrt{\left(\frac{A\_x-B\_x}{2}\right)^2+\left(\frac{A\_y-B\_y}{2}\right)^2}$$

For each triple of distinct points \\$(A,B,C)\\$, we generate the circle \\$(X,Y,r)\\$ which circumscribes the triangle \\$ABC\\$.

$$d=A\_x(B\_y-C\_y)+B\_x(C\_y-A\_y)+C\_x(A\_y-B\_y)$$ $$X=\frac{({A\_x}^2+{A\_y}^2)(B\_y-C\_y)+({B\_x}^2+{B\_y}^2)(C\_y-A\_y)+({C\_x}^2+{C\_y}^2)(A\_y-B\_y)}{2d}$$ $$Y=\frac{({A\_x}^2+{A\_y}^2)(C\_x-B\_x)+({B\_x}^2+{B\_y}^2)(A\_x-C\_x)+({C\_x}^2+{C\_y}^2)(B\_x-A\_x)}{2d}$$ $$r=\sqrt{(X-A\_x)^2+(Y-A\_y)^2}$$

For each generated circle, we test whether each point \\$(x,y)\\$ is enclosed within it:

$$\sqrt{(x-X)^2+(y-Y)^2}\le r$$

And we eventually return the smallest valid circle.

### Implementation

In the JS code, the formula to compute \\$(X,Y)\\$ for the triangle's circumscribed circle is slightly simplified. Assuming \\$d\neq0\\$, we define \\$q={C\_x}^2+{C\_y}^2\\$, leading to:

$$X=\frac{({A\_x}^2+{A\_y}^2-q)(B\_y-C\_y)+({B\_x}^2+{B\_y}^2-q)(C\_y-A\_y)}{2d}$$ $$Y=\frac{({A\_x}^2+{A\_y}^2-q)(C\_x-B\_x)+({B\_x}^2+{B\_y}^2-q)(A\_x-C\_x)}{2d}$$

This way, the helper function \\$F\\$ requires only two parameters \\$(j,k)\\$ to compute each coordinate:

* \\$(B\_y-C\_y,\\;C\_y-A\_y)\\$ for \\$X\\$
* \\$(C\_x-B\_x,\\;A\_x-C\_x)\\$ for \\$Y\\$

The third parameter used in \\$F\\$ (i.e. its actual argument \\$s\\$) is used to compute \\$(X,Y)\\$ when \\$d=0\\$, meaning that the triangle is degenerate and we have to try to use the diameter instead.
> 21 votes

# Answer
# , 59 bytes

```
function(x)nlm(function(y)max(Mod(x-y%*%c(1,1i))),0:1)[1:2]

```

Try it online!

Takes input as a vector of complex coordinates. `Mod` is the distance (modulus) in the complex plane and `nlm` is an optimization function: it finds the position of the center (output as `estimate`) which minimizes the maximum distance to the input points, and gives the corresponding distance (output as `minimum`), i.e. the radius. Accurate to 3-6 digits; the TIO footer rounds the output to 2 digits.

`nlm` takes a numeric vector as input: the `y%*%c(1,1i)` business converts it to a complex.
> 14 votes

# Answer
# Jelly, ~~100~~ 98 bytes

```
_²§½
1ịṭƊZIṚṙ€1N1¦,@ṭ@²§$µḢZḢ×Ø1œị$SḤ÷@P§
ZṀ+ṂHƲ€_@Ç+ḷʋ⁸,_²§½ʋḢ¥¥
œc3Ç€;ŒcZÆm,Hñ/$Ʋ€$ñ_ƭƒⱮṀ¥Ðḟ⁸ṚÞḢ

```

Try it online!

In contrast to my Wolfram language answer, Jelly needs quite a lot of code to achieve this (unless I’m missing something!). This full program takes the list of points as its argument and returns the centre and radius of the smallest enclosing circle. It generates circumcircles for all sets of three points, and diameters for all sets of two points, checks which include all of the points and then picks the one with the smallest radius.

Code for the make\_circumcircle bit was inspired by code at this site, in turn inspired by Wikipedia.
> 9 votes

# Answer
# Python 2 (PyPy), ~~244~~ 242 bytes

```
P={complex(*p)for p in input()}
Z=9e999,
for p in P:
 for q in{p}^P:
	for r in{p}^P:R,S=1j*(p-q),q-r;C=S.imag and S.real/S.imag-1jor 1;c=(p+q-(S and(C*(p-r)).real/(C*R).real*R))/2;Z=min(Z,(max(abs(c-t)for t in P),c.imag,c.real))
print Z[::-1]

```

Try it online!

This uses the brute-force O(n^4) algorithm, iterating through each pair and triangle of points, calculating the centre, and keeping the centre that needs the smallest radius to enclose all points. It calculates the circumcentre of 3 points via finding the intersection of two perpendicular bisectors (or, if two points are equal it uses the midpoint with the third).
> 3 votes

# Answer
# APL(NARS), 348 chars, 696 bytes

```
f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

```

This is one 'implementation' of formulas in Arnauld solution...Results and comments:

```
  s1 (¯8 0)(3 1)(¯6.2 ¯8)(3 9.5)
¯1.6 0.75  9.885469134
  s1 (7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
¯1.732305109 0.5829680042  11.57602798
  s1 (0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
5.5 ¯4  7.5
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)
0 ¯0.5  9.604686356
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
2 ¯1.5  11.67261753
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)(7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
1.006578947 ¯1.623355263  12.29023186
  s1 (1 1)(2 2)(3 3)(4 4)
2.5 2.5  2.121320344
  ⎕fmt s3 (1 1)(2 2)(3 3)(4 4)
┌0─┐
│ 0│
└~─┘

```

f: finds the combination of alpha ojets in the omega set

```
f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

```

((X,Y), r) from now represent one circonference of radius r and center in (X Y).

c: finds if the point in ⍺ is inside the circumference ((X Y) r) in ⍵ (result \<=0) ot it is external (result \>0) In the case of circumference input in ⍵ it is ⍬ as input, it would return 1 (out of circumference) each possible input in ⍺.

```
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}

```

p: if ⍵ is an array of ((X Y) r); for each of the ((X Y) r) in ⍵ writes 1 if all points in the array ⍺ are internal to ((X Y) r) otherwise writes 0 NB Here's something that do not goes because I had to round to epsilon= 1e¯13. in other words in limit cases of points in the plane (and probably built on purpose) it is not 100% solution insured

```
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}

```

s2: from 2-point in ⍵, it returns the circumference in the format ((X Y) r) that has diameter in those 2 points

```
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}

```

s3: from 3 points it return the circumference in the format ((X Y) r) passing through those three points If there are problems (for example points are aligned), it would fail and return ⍬.

```
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}

```

note that -.× find the determinant of a matrix nxn and

```
  ⎕fmt ⊃{⍵,1}¨(¯8 0)(3 1)(¯6.2 ¯8)
┌3─────────┐
3 ¯8    0 1│     |ax  ay 1|
│  3    1 1│   d=|bx  by 1|=ax(by-cy)-bx(ay-cy)+cx(ay-by)=ax(by-cy)+bx(cy-ay)+cx(ay-by)
│ ¯6.2 ¯8 1│     |cx  cy 1|
└~─────────┘

```

s: from n points in ⍵, it finds the type circumferences of those found by s2 or those of type s3 that contain all n points.

```
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}

```

s1: from the set found from the s above calculates those that have minimum radius and returns the first one that has minimal radius. The three numbers as arrays (the first and second coordinates are the coordinates of the center, while the third is the radius of the circumference found).

```
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

```
> 2 votes

# Answer
# Python ~~212~~ 190 bytes

This solution is incorrect, and I have to work now so I do not have time to fix it.

```
a=eval(input())
b=lambda a,b: ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
c=0
d=1
for e in a:
    for f in a:
        g=b(e,f)
        if g>c:
            c=g
            d=[e,f]
print(((d[0][0]+d[1][0])/2,(d[0][1]+d[1][1])/2,c/2))

```

Try it online!

I figured out which two points are furthest and then I generated an equation for a circle based off those points!

I know this isn't the shortest in python, but it's the best I could do! Also this is my first attempt at doing one of these, so please be understanding!
> 1 votes

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


# Question
Title: Add 2 positive integers by playing with bits
Given 2 positive integers in any format you'd like, return their sum using only logic gates and bit shifts (see example below). Don't worry about overflow.

EDIT: Using pre-written addition is obviously not allowed. So no `a + b`, `Add(a, b)`, `a - (-b)` etc.

This is code golf, so standard loopholes apply. Shortest program in characters wins.

Some test cases:

```
3, 4 => 7
5, 7 => 12
9, 10 => 19
12, 31 => 43

```

Example code in C#, readable (471 characters):

```
int Add(int numA, int numB)
{
    int result = 0;
    int mask = 1;
    int carryOver = 0;
    while (numA > 0 || numB > 0)
    {
        int A_bit = numA & 1;
        int B_bit = numB & 1;
        if ((carryOver ^ A_bit ^ B_bit) == 1)
        {
            result |= mask;
        }
        carryOver = carryOver == 1 ? A_bit | B_bit : A_bit & B_bit;
        numA >>= 1;
        numB >>= 1;
        mask <<= 1;
    }
    return carryOver == 1 ? result | mask : result;
}

```

Example code in C#, unreadable (118 characters):

```
int r=0,m=1,c=0;while(a>0|b>0){int A=a&1,B=b&1;if((c^A^B)==1)r|=m;c=c==1?A|B:A&B;a>>=1;b>>=1;m<<=1;}return c==1?r|m:r;

```

# Answer
> 3 votes
# JavaScript (ES6), 71 bytes

Takes input as `(a)(b)`.

```
a=>g=(b,r=0,m=1,c,y=a&m,z=b&m)=>m?g(b,!(y^z)^!c?r|m:r,m<<1,c?y|z:y&z):r

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 28 bytes

```
f=(a,b)=>b?f(a^b,(a&b)<<1):a

```

Try it online!

# Answer
> 2 votes
# Logicode, 185 Bytes

Seeing as Logicode only has AND, OR, and NOT operators, I thought it might be fun to try to implement addition in Logicode for this challenge.

```
circ t(a,m)->cond a&m->1/0
circ x(a,b)->(a&!b)|(b&!a)
circ f(a,b,c,m,n)->cond n&10000000->0/f(a,b,(t(a,m)&(t(b,m)|c))|(t(b,m)&c),m+0,n+0)+x(x(t(a,m),t(b,m)),c)
circ a(a,b)->f(a,b,0,1,1)

```

Try it Online!

# Answer
> 2 votes
# C (gcc)

Not golfed to the max

```
c;d(a,b){while(b){
c=1;while(~b&c)b^=c,c<<=1;b^=c;
c=1;while( a&c)a^=c,c<<=1;a^=c;}
return a;}

```

Explanation, it's basically

```
while(b--)a++;

```

Will not work for negative b

Try it online

# Answer
> 1 votes
# APL (Dyalog Unicode), 13 bytesSBCS

Anonymous tacit prefix function. Takes list of two equal-length binary representations.

```
⊃(≠/,1⌽¨∧/)⍣≡

```

Try it online!

`(``)⍣≡` apply the following function until two consecutive applications are identical:

`∧/` AND of the two (lit. AND-reduce, so this enclose the result to reduce rank)

`1⌽¨` shift the content of that enclosure a single step left

`≠/,` prepend the XOR of the two (lit. XOR-reduction, so this also encloses)

eventually the all carries have been done, so the second element (AND) is all-zero

pick the first element

# Answer
> 1 votes
# Retina 0.8.2, 65 bytes

```
+`(.?)(,\d*)(\d)
$2;$1$3
+`(.),
,;$1
{`00
0
01|10
1
}`;11
1;0
\D

```

Try it online! Link includes test cases in decimal; the header and footer perform base 2 conversion. Explanation:

```
+`(.?)(,\d*)(\d)
$2;$1$3
+`(.),
,;$1

```

Interleave the bits of both numbers, starting from the right.

```
{`00
0
01|10
1
}`;11
1;0

```

XOR each pair of bits together, and also AND the bits and carry 1 in that case. Repeat so that the carries propagate if necessary.

```
\D

```

Delete the separator punctuation.

---
Tags: code-golf, binary
---