title: The Crow vs The Taxicab

text:
# Question
Title: The Crow vs The Taxicab
Imagine travelling to a point lying **A** miles away horizontally and **B** miles away vertically from your current position. Or in other words, travelling from `(0, 0)` to point `(a, b)`. How far would you need to end up travelling? This seems like a straightforward question, but the answer depends on who you ask. If you're a crow, and you can travel *as the crow flies*, the distance travelled is just the Euclidean distance to `(a, b)`. This is

```
sqrt(a^2 + b^2)

```

But if you're just a boring human, you don't really want to walk that far, so you'll need to take a taxi. Most taxis wont drive in a straight line towards your destination because they generally try to stay on the roads. So the real distance you'll end up travelling is the sum of the vertical distance and the horizontal distance. Or the formula is:

```
abs(a) + abs(b)

```

This is called the Taxicab Distance. This picture nicely demonstrates the difference between the two:

To travel to `(6, 6)`, a crow can just fly on the green line, and this gives a distance of `6 * sqrt(2)` or roughly 8.49. A taxicab can take the red, blue or yellow paths, but they will all take 12.

This leads to the real question I'm asking. If a crow and a taxicab both leave from point `(0, 0)`, and travel to point `(a, b)`, how much longer is the taxicab's path? Or, in more math jargon,

> Given a two dimensional vector, determine the difference between the norm2 of the vector, and the norm1 of the vector.

You must write the shortest possible program or function to answer this question. You may choose to take 'a' and 'b' as two separate inputs, or as a two item tuple. You can take input and output in any reasonable format. If the difference is a non integer, you must be accurate to at least two decimal places.

You can always assume that 'a' and 'b' will be integers, and that they won't both be 0. (Though it is possible that either one of them will be zero)

As usual, standard loopholes apply and try to make your program as short as possible, counted in bytes.

I will upvote any answer that posts an explanation of how the code works, and demonstrates any cool tricks used to save bytes.

Here are some examples for you to test your code on:

```
#input    #output
3, 4      2
-3, 4     2
-3, -4    2
6, 6      3.51
42, 0     0
10, 10    5.86
3, 3      1.76

```

Have fun golfing! :)

# Answer
> 115 votes
# Taxi, ~~7394~~ 3773 bytes

```
Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Tom's Trims.Pickup a passenger going to Tom's Trims.Go to Tom's Trims:n.[a]Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Multiplication Station.1 is waiting at Starchild Numerology.Go to Starchild Numerology:s 2 l 2 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.Pickup a passenger going to Addition Alley.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to The Underground.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Multiplication Station.Go to The Underground:n 2 r 2 r.Switch to plan "b" if no one is waiting.Pickup a passenger going to Charboil Grill.Go to Charboil Grill:s 2 r 1 l 1 l 2 r.-1 is waiting at Starchild Numerology.Go to Starchild Numerology:e 2 r.Pickup a passenger going to Multiplication Station.Go to The Underground:w 1 r 2 r 1 r 2 l.[b]Go to Multiplication Station:s 1 l 1 r.Go to Tom's Trims:s 1 r 3 r.Switch to plan "c" if no one is waiting.Switch to plan "a".[c]Go to Multiplication Station:s 1 l 3 l.Pickup a passenger going to Cyclone.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 r 2 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Pickup a passenger going to Addition Alley.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Multiplication Station.-1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 1 l 1 l 3 l.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:w 1 r 2 r 1 r 4 l.Pickup a passenger going to Rob's Rest.Go to Rob's Rest:s 1 r 2 l 1 l 1 r 1 r.Go to Cyclone:s 1 l 1 l 1 l 1 r.Pickup a passenger going to Cyclone.[d]Pickup a passenger going to Multiplication Station.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:s 1 l 2 r 4 l.Pickup a passenger going to Addition Alley.Go to Cyclone:s 1 r 2 l 2 r.Switch to plan "e" if no one is waiting.Switch to plan "d".[e]Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Cyclone.99 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 1 l 1 l 3 l.Pickup a passenger going to The Underground.Go to Cyclone:e 1 l 2 r.Pickup a passenger going to Trunkers.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:n 1 r.Go to Trunkers:s 1 l.[f]Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Divide and Conquer.Pickup a passenger going to Trunkers.Go to Trunkers:s 1 l.Go to Sunny Skies Park:w 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l.Pickup a passenger going to Divide and Conquer.Go to Zoom Zoom:n.Go to Divide and Conquer:w 1 l 2 r 1 r.Pickup a passenger going to Addition Alley.Go to Cyclone:e 1 l 1 l 2 l.Pickup a passenger going to Addition Alley.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Divide and Conquer.2 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 1 l 3 l 2 r.Pickup a passenger going to Divide and Conquer.Go to Divide and Conquer:w 1 r 2 r 1 r 2 l 3 l.Pickup a passenger going to Sunny Skies Park.Go to Sunny Skies Park:e 1 l 1 l 2 l 1 l.Go to The Underground:s 1 l 1 r 2 l.Switch to plan "g" if no one is waiting.Pickup a passenger going to The Underground.Go to Trunkers:s 2 r 1 l.Switch to plan "f".[g]Go to Rob's Rest:n 3 l 2 l 1 l 2 r 1 r.Pickup a passenger going to What's The Difference.Go to Sunny Skies Park:s 1 l 1 l.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:e 3 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

```

# Try it online!

Engineer Toast, a much more experienced Taxi golfer, decided to take some time (probably a lot less than I did) and golf down my Taxi program by basically rewriting it. You can find my old answer body and links to my old TIOs in the edit history.

Engineer Toast's ungolfed square root algorithm: Try it online!

Ungolfed, with explanations:

```
[ Crow vs. Taxi ]

[ GET THE NEGATIVE ABSOLUTE VALUES OF BOTH STDINS ]

[Move the stdin values to Tom's Trims b/c:]
[1) Stdin doesn't count as a passenger waiting]
[2) Checking for no one waiting is shorter that keeping tracker of a count for just 2 iterations OR repeating all the code over again]
Go to Post Office:w 1 l 1 r 1 l.
Pickup a passenger going to Tom's Trims.
Pickup a passenger going to Tom's Trims.
Go to Tom's Trims:n.

[a]
[Clone the first waiting value]
[If we've already picked up both, move to the next process]
[Switch to plan "c" if no one is waiting.]
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:s 1 l 1 r.
Pickup a passenger going to Cyclone.
Go to Cyclone:n 1 l 1 l 2 r.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Multiplication Station.

[Add one to the value]
1 is waiting at Starchild Numerology.
Go to Starchild Numerology:s 2 l 2 r.
Pickup a passenger going to Cyclone.
Go to Cyclone:w 1 r 4 l.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:n 2 r 1 r.
Pickup a passenger going to The Underground.

[Pick up a clone of that one to feed into Multiplication Station]
Go to Cyclone:n 1 l 1 l.
Pickup a passenger going to Multiplication Station.

[Subtract one and see if that's more than zero]
Go to The Underground:n 2 r 2 r.
Switch to plan "b" if no one is waiting.

[It was more than zero so we make it negative]
[First, though, get rid of the pesky result from The Underground]
Pickup a passenger going to Charboil Grill.
Go to Charboil Grill:s 2 r 1 l 1 l 2 r.
-1 is waiting at Starchild Numerology.
Go to Starchild Numerology:e 2 r.
Pickup a passenger going to Multiplication Station.
Go to The Underground:w 1 r 2 r 1 r 2 l.

[b]
[Make sure it's a negative value and leave it at Multiplication Station]
[Either it was already negative OR we now have -1 as a passenger]
Go to Multiplication Station:s 1 l 1 r.

[Get the next stdin unless we've already gotten them both]
Go to Tom's Trims:s 1 r 3 r.
Switch to plan "c" if no one is waiting.
Switch to plan "a".

[ ADD THE TWO NEGATIVES AND INVERT TO GET THE TAXI DISTANCE]

[c]
[Pickup the two negative absolute values and clone them]
Go to Multiplication Station:s 1 l 3 l.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Cyclone.
Go to Cyclone:s 1 r 2 l 2 r.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Cyclone.
Pickup a passenger going to Addition Alley.

[Add the two clones values to get the negative Taxi distance]
Go to Addition Alley:n 2 r 1 r.
Pickup a passenger going to Multiplication Station.

[Invert to get the Taxi distance and store it at Rob's Rest]
-1 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 l 1 l 1 l 3 l.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station:w 1 r 2 r 1 r 4 l.
Pickup a passenger going to Rob's Rest.
Go to Rob's Rest:s 1 r 2 l 1 l 1 r 1 r.

[ FIND THE CROW DISTANCE ]
[Uses the Babylonian method: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method ]

[Square and Sum the cloned values]
Go to Cyclone:s 1 l 1 l 1 l 1 r.
Pickup a passenger going to Cyclone.
[d]
Pickup a passenger going to Multiplication Station.
Pickup a passenger going to Multiplication Station.
Go to Multiplication Station:s 1 l 2 r 4 l.
Pickup a passenger going to Addition Alley.
Go to Cyclone:s 1 r 2 l 2 r.
Switch to plan "e" if no one is waiting.
Switch to plan "d".
[e]
Go to Addition Alley:n 2 r 1 r.
Pickup a passenger going to Cyclone.

[Pickup our cycle counter]
[It's cheaper to do this than to check each iteration's value as equal to the last]
[Taxi can only handle integers up to 2^31-1 so 99 iterations is sufficient.]
99 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 l 1 l 1 l 3 l.
Pickup a passenger going to The Underground.

[Duplicate stdin to be stored as S at Trunkers and as x0 at Sunny Skies Park]
[a & b are always integers so Trunkers won't hurt S and it's close with a short name so it's good for golfing]
Go to Cyclone:e 1 l 2 r.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park:n 1 r.
Go to Trunkers:s 1 l.

[ This is our starting position for square root:           ]
[  • x at Sunny Skies Park                                 ]
[  • S at Trunkers                                         ]
[  • Taxi at Trunkers                                      ]
[  • The iterator as a passenger going to The Underground  ]

[f]

[Duplicate S so we don't lose it]
Pickup a passenger going to Cyclone.
Go to Cyclone:w 2 r.
Pickup a passenger going to Divide and Conquer.
Pickup a passenger going to Trunkers.
Go to Trunkers:s 1 l.

[Diplicate x for division and addition]
Go to Sunny Skies Park:w 1 r.
Pickup a passenger going to Cyclone.
Go to Cyclone:n 1 l.
Pickup a passenger going to Divide and Conquer.

[Gas will be super important in this loop]
Go to Zoom Zoom:n.

[Perform (x + S/x)/2]
[(/2) turns out to be a few bytes shorter than (*.5), mostly due to place names]
Go to Divide and Conquer:w 1 l 2 r 1 r.
Pickup a passenger going to Addition Alley.
Go to Cyclone:e 1 l 1 l 2 l.
Pickup a passenger going to Addition Alley.
Go to Addition Alley:n 2 r 1 r.
Pickup a passenger going to Divide and Conquer.
2 is waiting at Starchild Numerology.
Go to Starchild Numerology:n 1 l 1 l 3 l 2 r.
Pickup a passenger going to Divide and Conquer.
Go to Divide and Conquer:w 1 r 2 r 1 r 2 l 3 l.
Pickup a passenger going to Sunny Skies Park.
Go to Sunny Skies Park:e 1 l 1 l 2 l 1 l.
[Now we have the next iteration of x]

[Check the iterator]
Go to The Underground:s 1 l 1 r 2 l.
Switch to plan "g" if no one is waiting.
Pickup a passenger going to The Underground.

[Reset the loop]
Go to Trunkers:s 2 r 1 l.
Switch to plan "f".

[ ADD THE NEGATIVE SUM TO THE SQUARE ROOT TO GET THE NEGATIVE DIFFERENCE ]

[g]
Go to Rob's Rest:n 3 l 2 l 1 l 2 r 1 r.
Pickup a passenger going to What's The Difference.
Go to Sunny Skies Park:s 1 l 1 l.
Pickup a passenger going to What's The Difference.
Go to What's The Difference:n 1 r 1 l.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery:e 3 r.
Pickup a passenger going to Post Office.
Go to Post Office:n 1 l 1 r.

```

# Answer
> 10 votes
# Javascript (ES6), 36 bytes

-1 byte thanks to @dtkaias

```
(x,y,s=Math.hypot)=>s(x)+s(y)-s(x,y)

```

**Example code snippet:**

```
f=

(x,y,s=Math.hypot)=>s(x)+s(y)-s(x,y)

for(i=0;i<7;i++)
  a=[3,-3,-3,6,42,10,3][i],
  b=[4,4,-4,6,0,10,3][i],
  console.log(`f(${a},${b}) = ${f(a,b)}`)
```

# Answer
> 9 votes
# Julia, 20 bytes

```
x->norm(x,1)-norm(x)

```

Takes `a` and `b` as a list.

Julia's `norm` second argument defaults to 2 - hence this would be equivalent to `norm(x, 1) - norm(x, 2)`.

# Answer
> 6 votes
# Java 8, 47 bytes

Golfed:

```
(a,b)->(a<0?-a:a)+(b<0?-b:b)-Math.sqrt(a*a+b*b)

```

This is about as basic as it gets: subtract the two calculated values to find the difference. This uses ternary logic instead of `Math.abs()` to save one byte each occurrence. Unfortunately, the parentheses are required due to operator precedence.

The output is whatever Java's `double` can hold, which is accurate to more than two decimal places and satisfies the accuracy requirement of the question.

Ungolfed:

```
public class TheCrowVsTheTaxicab {

  public static void main(String[] args) {
    int[][] inputs = new int[][] { { 3, 4 }, { -3, 4 }, { -3, -4 }, { 6, 6, }, { 42, 0 }, { 10, 10 }, { 3, 3 } };
    double[] outputs = new double[] { 2, 2, 2, 3.51, 0, 5.85, 1.76 };

    for (int i = 0; i < inputs.length; ++i) {
      double actual =
        f((a, b) -> (a < 0 ? -a : a) + (b < 0 ? -b : b) - Math.sqrt(a * a + b * b), inputs[i][0], inputs[i][1]);

      System.out.println("Input:    " + inputs[i][0] + ", " + inputs[i][1]);
      System.out.println("Expected: " + outputs[i]);
      System.out.println("Actual:   " + actual);
      System.out.println();
    }
  }

  private static double f(java.util.function.BiFunction<Integer, Integer, Double> f, int a, int b) {
    return f.apply(a, b);
  }
}

```

Output:

```
Input:    3, 4
Expected: 2.0
Actual:   2.0

Input:    -3, 4
Expected: 2.0
Actual:   2.0

Input:    -3, -4
Expected: 2.0
Actual:   2.0

Input:    6, 6
Expected: 3.51
Actual:   3.5147186257614305

Input:    42, 0
Expected: 0.0
Actual:   0.0

Input:    10, 10
Expected: 5.85
Actual:   5.857864376269049

Input:    3, 3
Expected: 1.76
Actual:   1.7573593128807152

```

# Answer
> 5 votes
# , 30 bytes

```
function(v)norm(v)-norm(v,'f')

```

Takes `v` as a 1-column matrix. `norm` computes a particular norm of a matrix, with the default being the L1 norm (taxicab), and `f` the L2 norm (`'f'` for Frobenius/Euclidean).

Try it online!

# Answer
> 4 votes
# Python 2, ~~40~~ ~~38~~ 36 bytes

*-2 bytes thanks to vaultah. -2 bytes thanks to sTertooy.*

Fun fact, 11 bytes of this code were just copied from the question and golfed.

```
lambda a,b:abs(a)+abs(b)-abs(a+b*1j)

```

Try it online!

# Answer
> 4 votes
# Mathematica, 32 bytes

```
N[Tr@Abs[a={##1}]-Sqrt@Tr[a^2]]&

```

or

# Mathematica, 31 bytes

```
N[Abs@#+Abs@#2-Sqrt[#^2+#2^2]]&

```

or @Not a tree's suggestion

# Mathematica, 26 bytes

```
N[Tr@Abs@{##}-Abs[#+I#2]]&

```

or @alephalpha's suggestion

# Mathematica, 19 bytes

```
N[#~Norm~1-Norm@#]&

```

# Answer
> 4 votes
# Dyalog APL, 13 bytes

```
+/∘|-.5*⍨+.×⍨

```

Try it online!

Explanation (input X):

```
+/∘|     - Sum of the element-wise absolute value of X
-        - Minus
.5*⍨+.×⍨ - Euclidean distance = sqrt(X . X)

```

# Answer
> 3 votes
# Japt, ~~11~~ 9 bytes

*-2 bytes thanks to @ETHproductions*

```
Nxa -MhUV

```

Try it online!

## Explained

```
Nxa -MhUV   // implicit: U and V are input integers, N = [U,V]

N a         // get absolute value of both inputs
 x          // sum those values
    -MhUV   // subtract hypot(U, V) -> sqrt(U^2 + V^2)

```

# Answer
> 3 votes
# J, 13 bytes

```
+/@:|-+/&.:*:

```

This is a function that takes the coordinates as an array, e.g.:

```
   (+/@:|-+/&.:*:) _3 4
2

```

Explanation:

```
+/             sum
  @:           of
    |          absolutes
     -         minus
      +/       sum
        &.:    under
           *:  square

```

# Answer
> 3 votes
# Scheme - 58 bytes.

```
(define (f a b) (-(+(abs a)(abs b))(sqrt(* a a)(* b b))))

```

# Answer
> 3 votes
# Pyth, 8 bytes

```
-s.aMQ.a

```

Try it online. Test suite.

### Explanation

```
-s.aMQ.aQ      Q (input) appended implicitly
  .aMQ         absolute values of input vector
 s             sum
-              subtract
      .aQ      norm2 of input vector

```

# Answer
> 3 votes
# APL (Dyalog), 14 bytes

Takes argument in the form `xJy`, e.g. `3J4`

```
||-2+/∘|9 11○⊢

```

Try it online!

`|` the magnitude ofDoc

`|` the argument's magnitude

`-` minus

`2+/` the pair-wise sum

of

`|` the magnitudes of

`9 11.○⊢` the the argument's real and the imaginary parts.Doc

Special trick for golfing was the use of the pairwise reduction (`2+/`) to supply `+/` with a no-op left argument, thereby avoiding parentheses: `||-(+/∘|9 11○⊢)`

# Answer
> 3 votes
# , ~~9~~ 8 bytes

-1 thanks to my colleague Marshall.

```
+&|-|@j.

```

Try it online!

Takes **A** as left argument and **B** as right argument.

`+` the sum

`&` of

`|` the magnitudes

`-` minus

`|` the magnitude

`@` of

`j.`**A** \+ **B** *i*

Golfing trick: combine the values to a single complex number because the diagonal is easy to get like that, while also keeping them separate because the sum is easy to get like that.

# Answer
> 2 votes
# 05AB1E, 7 bytes

```
ÄO¹nOt-

```

Try it online!

**Explanation**

```
Ä        # absolute value of inputs
 O       # sum
  ¹      # push input again
   n     # square
    O    # sum
     t   # sqrt
      -  # subtract

```

# Answer
> 2 votes
# MATL, ~~8~~ 7 bytes

```
|sG2&|-

```

**Try it online!**

### Explanation

```
|    % Implicit input: vector of two numbers. Absolute value, element-wise
s    % Sum of vector
G    % Push input again
2    % Push 2
&|   % 2-norm of input
-    % Subtract. Implicit display

```

# Answer
> 2 votes
# TI-Basic (TI-84 Plus CE), 10 bytes

```
sum(abs(Ans))-√(sum(Ans<sup>2</sup>
```

Program that input as a list of two integers in `Ans`, e.g. call with `{3,4}:prgmCROW` (replacing `3,4` with the input and `CROW` with the name of the program).

Explanation:

```
sum(abs(Ans))-√(sum(Ans<sup>2</sup>
        Ans               # The input list of two integers
    abs(   )              # Absolute value of each item in the list
sum(        )             # Sum of the list
                    Ans   # The input list of two integers
                       <sup>2</sup>  # Square of each item in the list
                sum(      # Sum of the list
              √(          # Square root of the sum
             -            # Difference of the two values

```

# Answer
> 2 votes
# Pyth, 7 bytes

```
a.aQsa0

```

Try it here

---

**Pyth,  ~~25~~  23 bytes**

THis is the initial solution, my first not-so-trivial Pyth solution and you can see just how bad I used to be at golfing in Pyth :)

```
K.aswJ.asw-+KJ^+^K2^J2 .5

```

Try it online!

# Answer
> 2 votes
# Common Lisp, 57 bytes

```
(defun g(a b)(+(abs a)(abs b)(-(sqrt(+(* a a)(* b b))))))

```

Try it online!

# Answer
> 2 votes
# Jelly, 7 bytes

```
²S½ạAS$

```

Try it online!

Format is list of two numbers.

# Answer
> 2 votes
# GNU APL 1.2, 24 bytes

```
∇f P
(+/|P)-(+/P*2)*.5
∇

```

`∇f P` declares a function `f` that takes a vector `P` containing the distances as an argument (e.g. `[3, 4]`)

APL operates on vectors, so `+/|P` applies the `|` operator (`abs` function) to each element in the vector and then evaluates `+` on each element (so add all the elements). This gives the taxi distance.

`P*2` yields a vector that is the same as `P` but with each element squared. `+/P*2` to add those together and then (with parentheses for precedence because APL is right-to-left) `*.5` to get the square root. This gives the crow distance.

Add an extra pair of parentheses for the taxi distance for precedence and compute the difference.

to end the function.

# Answer
> 2 votes
# Add++, ~~59~~ 57 bytes

```
D,f,@@,|@|+
D,g,@@,d*@d*+
_
$f>G>G
V
$g>?>?
S
-G
$f>x>0
O

```

Try it online!

This took me ages to solve. It doesn't round the final answer as that isn't possible in Add++. This is how the program works with the inputs `-3` and `-4` (`ACC` is the accumulator value)

```
D,        Define a function
  f,      called f
  @@,     that takes 2 arguments (e.g. -3, -4)
     |    absolute value;   STACK = [-3, 4]
     @    reverse stack;    STACK = [4, -3]
     |    absolute value;   STACK = [4, 3]
     +    sum;              STACK = [7]
          implicitly return the top of the stack

D,        Define a function
  g,      called g
  @@,     that takes 2 arguments (e.g. -3, -4)
     d    duplicate;  STACK = [-3, -4, -4]
     *    multiply;   STACK = [-3, 16]
     @    reverse;    STACK = [16, -3]
     d    duplicate;  STACK = [16, -3, -3]
     *    multiply;   STACK = [16, 9]
     +    sum;        STACK = [25]
          implicitly return the top of the stack

_         store the inputs in the second stack;  ACC = 0;  STACK = [-3, -4]
$f>G>G    apply f with -3 and -4 as arguments;   ACC = 7;  STACK = []
V         store ACC in the stack;                ACC = 7;  STACK = [7]
$g>?>?    apply g with -3 and -4 as arguments;   ACC = 25; STACK = [7]
S         square root the ACC;                   ACC = 5;  STACK = [7]
-G        subtract the stack value from the ACC; ACC = -2; STACK = []
$f>x>0    apply f with ACC and 0 as arguments;   ACC = 2;  STACK = []
O         output ACC as a number

```

# Answer
> 1 votes
# Pip, 15 bytes

```
ABa+ABb-RT$+g*g

```

Takes input from command-line arguments. Try it online!

### Explanation

In pseudocode, this is `abs(a) + abs(b) - sqrt(fold+(g*g))`. `a` and `b` are the first two cmdline args, and `g` is the list of cmdline args (i.e. argv). The `*` operator vectorizes, like many Pip operators, so `$+g*g` is the same thing as `a*a + b*b`. The rest is pretty straightforward.

Unfortunately, I can't save any bytes with `$+ABg`, because the precedence of operators with fold doesn't work like it should yet. `$+` ought to be slightly higher precedence than binary `-`, but at the moment it parses as `$+(ABg-RT$+g*g)`, giving the wrong answer. Doing `($+ABg)-RT$+g*g` doesn't save any bytes over the less-obfuscated version above.

# Answer
> 1 votes
# PHP\>=7.1, 54 bytes

```
[,$x,$y]=$argv;echo abs($x)+abs($y)-sqrt($x**2+$y**2);

```

PHP Sandbox Online

# PHP, 55 bytes

```
<?=abs($x=$argv[1])+abs($y=$argv[2])-sqrt($x**2+$y**2);

```

Try it online!

# PHP, 60 bytes

with an function instead of a full program

```
function f($x,$y){return abs($x)+abs($y)-sqrt($x**2+$y**2);}

```

Try it online!

# Answer
> 1 votes
# ,,,, 18 bytes

Essentially a port of my Python answer.

```
a:↔a:0•2*⇆2*+√↔+↔-

```

# Answer
> 1 votes
# Excel VBA, 34 Bytes

Anonymous VBE immediate window function that takes input from range `[A1:B1]` and outputs the difference between the Euclidean and Taxicab distances to the VBE immediate window.

```
?[ABS(A1)+ABS(B1)-SQRT(A1^2+B1^2)]

```

# Answer
> 1 votes
# Pari/GP, 25 bytes

```
x->n=normlp;n(x,1)-n(x,2)

```

Try it online!

# Answer
> 1 votes
## Forth (gforth), 68 bytes

```
abs swap abs 2dup + s>d d>f dup * swap dup * + s>d d>f fsqrt  f- f.s

```

Try it online !

The coordinates are two numbers on the stack.

PS my first code golf... don't hit too hard ;-)!

# Answer
> 1 votes
# Ruby, 31 bytes

Creates a complex number to calculate the distance with.

```
->x,y{x.abs+y.abs-(x+y*1i).abs}

```

Try it online!

# Answer
> 1 votes
# Ruby (2.0.0 - 2.3.0), 57bytes

```
x,y=$*.map(&:to_i);puts x.abs+y.abs-Math.sqrt(x**2+y**2)

```

This assumes taking input from ARGV e.g.

```
ruby -e 'x,y=$*.map(&:to_i);puts x.abs+y.abs-Math.sqrt(x**2+y**2)' -- -3 4

```

This feels like a cheat since Ruby comes with a math lib that has abs and sqrt functions (unlike the guy who wrote his own abs and sqrt functions, though I didn't see anything specifically forbidding the use of such functions).

The first trick is using `.map` instead of `.each` which saves a byte, then using the `&:symbol` notation to pass map a proc we execute `to_i` on each item in the array, and use multiple assignment to assign values to x and y.

A longer version would be:

```
(x, y) = ARGV.map{ |string| string.to_i }

```

(since map returns an array, multiple assignment is probably the way to do it, this does throw away any additional parameters, but we're assuming only two inputs anyway)

Then I just removed all of the spaces in the equation.

Here's a longer version, 84 bytes

```
$*.map!(&:to_i);puts$*.inject(0){|x,y|x+y.abs}-Math.sqrt($*.inject(0){|x,y|x+y**2})

```

The goal here was to not repeat myself, e.g. having to write `x` or `abs` twice and my squaring twice `x**2 + y**2`

It did not work.

But what's interesting is that puts doesn't need a space, I guess the lexer is smart enough to see the special char and know it's a special var.

`inject` and `reduce` are synonyms, inject has a signature of

```
inject(initial) {| memo, obj | block }

```

In our case we need to set the initial to 0, then we have our accumulator (i.e.: memo = 0) and the object from each iteration.

The down side to this method is that it will take more than two inputs and will either sum or square, add, then sqrt all the values in the array.

I *think*--though I don't have a Ruby 2.4.0 to test with--that this will work as well, which comes in at 72 bytes:

```
$*.map!(&:to_i);puts$*.sub{|x,y|x+y.abs}-Math.sqrt($*.sum{|x,y|x+y**2})

```

Sum defaults to 0 and as far as I can tell, works the same as inject/reduce.

# Answer
> 1 votes
# Google Sheets, 31 Bytes

Worksheet function that takes input from range `[A1:B1]` and outputs the difference between the Euclidean and Taxicab distances

```
=ABS(A1)+ABS(B1)-SQRT(A1^2+B1^2

```

# Excel, 32 bytes

Same as above but formatted for MS Excel

```
=ABS(A1)+ABS(B1)-SQRT(A1^2+B1^2)

```

# Answer
> 1 votes
# Japt, 7 bytes

Takes input as an array.

```
x²¬nUxa

```

Try it (includes all test cases)

```
x²¬nUxa     :Implicit input of array U
x           :Sum of
 ²          :  Squares
  ¬         :Square root
   n        :Subtract from
    Uxa     :  Sum of absolute values of U

```

# Answer
> 1 votes
# Husk, 7 bytes

```
-√ṁ□¹ṁa

```

Try it online!

```
-√ṁ□¹ṁa
     ṁa     # sum of absolute values
-           # minus
 √ṁ□¹       # square root of sum of squares

```

# Answer
> 1 votes
# Factor, 27 bytes

```
[ dup l1-norm swap norm - ]

```

Try it online!

# Answer
> 1 votes
# Thunno 2, 6 bytes

```
ÆH¤AS_

```

Try it online!

#### Explanation

```
ÆH¤AS_  # Implicit input
  ¤AS   # abs(a) + abs(b)
ÆH   _  #                 - hypot(a, b)
        # Implicit output

```

# Answer
> 1 votes
# Vyxal, 6 bytes

```
₌∆/ȧ∑ε

```

Try it Online!

#### Explanation

```
₌∆/ȧ∑ε  # Implicit input
₌       # Parallel apply:
 ∆/     #  Hypotenuse
   ȧ    #  Absolute value
    ∑   # Sum the absolute values
     ε  # Absolute difference
        # Implicit output

```

# Answer
> 1 votes
# Desmos, 33 bytes

```
f(a,b)=abs(a)+abs(b)-\sqrt{aa+bb}

```

Try it on Desmos!

# Answer
> 0 votes
# Casio-Basic, 27 bytes

```
abs(a)+abs(b)-norm([a,b]

```

Turns out you can just leave off that last bracket and it'll work fine. Having `norm` as a built-in makes it even shorter!

24 bytes for the code, 3 bytes to add `a,b` as parameters.

# Answer
> 0 votes
# QBIC, 27 bytes

```
?abs(:)+abs(:)-sqr(a^2+b^2)

```

# Answer
> 0 votes
# Scala 8, 48 bytes

```
a=>b=>Math.abs(a)+Math.abs(b)-Math.sqrt(a*a+b*b)

```

Explained:

```
a=>b=>                   A curried function with two parameters, 'a' and 'b'.
Math.abs(a)              The absolute value of 'a'.
+Math.abs(b)             Plus the absolute value of 'b'.
-Math.sqrt(a*a+b*b)      Minus the squareroot of 'a' squared plus 'b' squared.

```

I'm not very experienced with Scala for there is probably a few improvements that could be made.

# Answer
> 0 votes
# ExtraC, 82 bytes

```
import math
lambda dbl f,x,y,abs(x)plus abs(y)minus sqrt(x times x plus y times y)

```

Try it online!

Presenting my new language, ExtraC! It's supposed to look like python, but it's really just C. Oh, and it has almost no symbols available to it.

Simply put, this imports the `math` library (for `sqrt`), and defines a function `f` which takes two integers and returns a double.

Example usage:

```
import math
lambda dbl f,x,y,abs(x)plus abs(y)minus sqrt(x times x plus y times y)
// end submission
let x be readint, y be readint
disp(f(x, y))

```

Which, for input `3 3` would output: `1.75736` Try it online!

# Answer
> 0 votes
# Java 7, ~~92~~ 73 bytes

```
double c(int a,int b){return Math.abs(a)+Math.abs(b)-Math.sqrt(a*a+b*b);}

```

Ungolfed, I think it is self explanatory:

```
double c(int a,int b){
    return Math.abs(a)+Math.abs(b)-Math.sqrt(a*a+b*b);
}

```

# Answer
> 0 votes
# PHP 7, 109 bytes (insane variant)

```
$a[0]=($s=array_sum)($a=($m=array_map)(function($n){return$n*$n;},$argv));
$a=$m(sqrt,$a);
echo$s([-$a[0]]+$a);

```

linebreaks are for reading convenience only. Run with `-nr`.

# Answer
> 0 votes
# Perl 5, 41 + 2 (-pa) = 43 bytes

```
$_=abs($F[1])-sqrt($F[0]**2+$F[1]**2)+abs

```

Try it online!

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


title: Am I a Fibonacci Number?

text:
# Question
Title: Am I a Fibonacci Number?
## Your Task:

Write a program or function to check if a number that is inputted is a *Fibonacci number*. A Fibonacci number is a number contained in the Fibonacci sequence.

The Fibonacci Sequence is defined as: `F(n) = F(n - 1) + F(n - 2)`

With the seeds being `F(0) = 0` and `F(1) = 1`.

## Input:

A non-negative integer between 0 and 1,000,000,000 that may or may not be a Fibonacci number.

## Output:

A truthy/falsy value indicating whether or not the input is a Fibonacci number.

## Examples:

```
0-->truthy
1-->truthy
2-->truthy
12-->falsy

```

## Scoring:

This is , lowest byte count wins.

# Answer
> 36 votes
# Neim, 2 bytes

```
f

```

Explanation:

```
f       Push an infinite fibonacci list
       Is the input in that list?

```

Works the same as my It's Hip to be Square answer, but uses a different infinite list: `f`, for fibonacci.

Try it!

# Answer
> 19 votes
# Regex (ECMAScript), ~~392~~ ~~358~~ ~~328~~ ~~224~~ ~~206~~ ~~165~~ ~~164~~ ~~162~~ 161 bytes

*-1 byte by using ECMAScript non-participating capture group behavior*
*-2 bytes by by calculating \\$F\_{2n+3}\\$ differently*
*-1 byte by moving around a remainder*

The techniques that need to come into play to match Fibonacci numbers with an ECMAScript regex (in unary) are a far cry from how it's best done in most other regex flavors. The lack of forward/nested backreferences or recursion means that it is impossible to directly count or keep a running total of anything. The lack of lookbehind makes it often a challenge even to have enough space to work in.

Many problems must be approached from an entirely different perspective, and seem unsolvable until the arrival of some key insight. It forces you to cast a much wider net in finding which mathematical properties of the numbers you're working with might be able to be used to make a particular problem solvable.

In March 2014, this is what happened for Fibonacci numbers. Looking at the Wikipedia page, I initially couldn't figure out a way, though one particular property seemed tantalizingly close. Then the mathematician teukon outlined a method that made it quite clear it would be possible to do, using that property along with another one. He was reluctant to actually construct the regex. His reaction when I went ahead and did it:

> You're crazy! ... I thought you might do this.

As with my other ECMAScript unary math regex posts, I'll give a **warning:** I highly recommend learning how to solve unary mathematical problems in ECMAScript regex. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See that post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

So **do not read any further if you don't want some unary regex magic spoiled for you**. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.

The challenge I initially faced: A positive integer *x* is a Fibonacci number if and only if 5x2 \+ 4 and/or 5x2 \- 4 is a perfect square. But there is no room to calculate this in a regex. The only space we have to work in is the number itself. We don't even have enough room to multiply by 5 *or* take the square, let alone both.

teukon's idea on how to solve it (originally posted here):

> The regex is presented with a string of the form `^x*$`, let z be its length. Check whether or not z is one of the first few Fibonacci numbers by hand (up to 21 should do). If it is not:
>
> 1. Read a couple of numbers, a Use forward look-aheads to build a2, ab, and b2.
> 2. Assert that either 5a2 \+ 4 or 5a2 \- 4 is a perfect square (so a must be Fn-1 for some n).
> 3. Assert that either 5b2 \+ 4 or 5b2 \- 4 is a perfect square (so b must be Fn).
> 4. Check that z = F2n+3 or z = F2n+4 by using the earlier built a2, ab, and b2, and the identities:
>     * F2n-1 = Fn2 \+ Fn-12
>     * F2n = (2Fn-1 \+ Fn)Fn
>
> In brief: these identities allow us to reduce the problem of checking that a given number is Fibonacci to checking that a pair of **much** smaller numbers are Fibonacci. A little algebra will show that for large enough n (n = 3 should do), F2n+3 \> Fn \+ 5Fn2 \+ 4 so there should always be enough space.

And here is a mockup of the algorithm in C which I wrote as a test before implementing it in regex. My final golfed regex is rather different. There turned out to be no need to find both \\$a\\$ and \\$b\\$, because \\$b\\$ is the Lucas number \\$L\_n\\$, which along with \\$F\_n\\$ can be used to derive \\$F\_{2n+2}\\$ and \\$F\_{2n+3}\\$ as needed:

* \\${L\_n}^2 = 5{F\_n}^2±4\\$
* \\$L\_{2n} = ({5{F\_n}^2 + {L\_n}^2}) / 2 = 5{F\_n}^2±2 = {L\_n}^2∓2\\$
* \\$F\_{2n} = L\_n F\_n\\$
* \\$F\_{2n+1} = ({L\_{2n} + F\_{2n}})/2\\$
* \\$F\_{2n+2} = F\_{2n} + F\_{2n+1}\\$
* \\$F\_{2n+3} = F\_{2n+1} + F\_{2n+2}\\$

So with no further ado, here is the regex:

`^(?=(x*).*(?=x{4}(x{5}(\1{5}))(?=\2*$)\3+$)(|x{4})(?=xx(x*)\5)\4(x(x*))(?=(\6*)\7+$)(?=\6*$\8)\6*(?=x\1\7+$)(x*)(\9x?)|)(\9\10(\5\10)\12?|xx?x?|x{5}|x{8}|x{21})$`

Try it online!

And the pretty-printed, commented version:

```
^                          # tail = N = input number
(?=
    (x*)                   # \1+1 = potential number for which 5*(\1+1)^2 ± 4 is a
                           # perfect square; this is true iff \1+1 is a Fibonacci number,
                           # which we shall call F_n. Outside the surrounding lookahead
                           # block, \1+1 is guaranteed to be the largest number for which
                           # this is true such that \1 + 5*(\1+1)^2 + 4 <= N.
    .*
    (?=                    # tail = (\1+1) * (\1+1) * 5 + 4
        x{4}
        (                  # \2 = (\1+1) * 5
            x{5}
            (\1{5})        # \3 = \1 * 5
        )
        (?=\2*$)
        \3+$
    )
    (|x{4})                # \4 = parity - determined by whether the index of Fibonacci
                           #               number \1+1 is odd or even;
    (?=
        xx                 # tail = arithmetic mean of (\1+1) * (\1+1) * 5 and \6 * \6
                           #      = ((F_n * F_n * 5) + (L_n * L_n)) / 2 = L_{2n}
        (x*)\5             # \5 = floor(tail / 2) = floor(L_{2n} / 2)
    )
    \4
    # require that the current tail is a perfect square
    (x(x*))                # \6 = potential square root, which will be the square root
                           #      after the following two lookaheads; \7 = \6-1
    (?=(\6*)\7+$)          # \8 = must be zero for \6 to be a valid square root
    (?=\6*$\8)
    # \6 is now the Lucas number L_n corresponding to the Fibonacci number F_n.
    \6*
    (?=x\1\7+$)            # tail = F_{2n} = L_n * F_n = \6 * (\1+1), where \6 is larger
    (x*)(\9x?)             # \9 = floor(tail / 2);
                           # \10 = ceil(tail / 2); the remainder tail % 2 will always be
                           #       the same as the remainder discarded by \5, because
                           #       F_{2n} is odd iff L_{2n} is odd, thus this ceil()
                           #       can complement the floor() of \5 when adding \5 + \10
|                          # Allow everything above to be skipped, resulting in all
                           # capture groups being unset.
)
(
    # Note that if the above was skipped using the empty alternative in the lookahead,
    # the following will evaluate to 0. This relies on ECMAScript NPCG behavior.
    \9\10(\5\10)           # \12  = F_{2n+1} = (L_{2n} + F_{2n})/2 = \5 + \10;
                           # head = F_{2n+2} = F_{2n}   + F_{2n+1}
                           #                 = \9+\10   +   \12
    \12?                   # head = F_{2n+3} = F_{2n+2} + F_{2n+1}    (optionally)
                           #                 = head     +   \12
|
    xx?x?|x{5}|x{8}|x{21}  # The Fibonacci numbers 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

```

The multiplication algorithm is not explained in those comments, but is briefly explained in a paragraph of my abundant numbers regex post.

I was maintaining six different versions of the Fibonacci regex: four that ratchet from shortest length to fastest speed and use the algorithm explained above, and two others that use a different, much faster but much more lengthy algorithm, which as I found can actually return the Fibonacci index as a match (explaining that algorithm here is beyond the scope of this post, but it's explained in the original discussion Gist). I don't think I would maintain that many very-similar versions of a regex again, because at the time I was doing all my testing in PCRE and Perl, but my regex engine is fast enough that concerns of speed are not as important anymore (and if a particular construct is causing a bottleneck, I can add an optimization for it) – though I'd probably again maintain one fastest version and one shortest version, if the difference in speed were big enough.

The "return the Fibonacci index minus 1 as a match" version (not heavily golfed):

Try it online!

All of the versions are on github with the full commit history of golf optimizations:

regex for matching Fibonacci numbers - short, speed 0.txt (the shortest but slowest one, as in this post)
regex for matching Fibonacci numbers - short, speed 1.txt
regex for matching Fibonacci numbers - short, speed 2.txt
regex for matching Fibonacci numbers - short, speed 3.txt
regex for matching Fibonacci numbers - fastest.txt
regex for matching Fibonacci numbers - return index.txt

# Answer
> 18 votes
## JavaScript (ES6), 34 bytes

```
f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

```

Recursively generates the Fibonacci sequence until it finds an item greater than or equal to the input, then returns item == input.

# Answer
> 13 votes
## Retina, 23 bytes

```
^$|^(^1|(?>\2?)(\1))*1$

```

Try it online!

Input in unary, outputs `0` or `1`.

### Explanation

The Fibonacci sequence is a good candidate for a solution with forward references, i.e. a "backreference" that refers either to a surrounding group or one that appears later in the regex (in this case, we're actually using both of those). When matching numbers like this, we need to figure out a recursive expression for the *difference* between sequence elements. E.g. to match triangular numbers, we usually match the previous segment plus one. To match square numbers (whose differences are the odd numbers), we match the previous segment plus two.

Since we obtain the Fibonacci numbers by adding the second-to-last element to the last one, the differences between them are also just the Fibonacci numbers. So we need to match each segment as the sum of the previous two. The core of the regex is this:

```
(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

```

Now this ends up adding the Fibonacci numbers starting at **1**, i.e. **1, 1, 2, 3, 5, ...**. Those add up to **1, 2, 4, 7, 12, ...**. I.e. they are one less than the Fibonacci numbers, so we add a `1` at the end. The only case this doesn't cover is zero, so we have the `^$` alternative at the beginning to cover that.

# Answer
> 9 votes
# Python 3, 48 bytes

```
lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

```

Try it online!

# Answer
> 7 votes
# Python 2, ~~48~~ 44 bytes

```
f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

```

**Try it online**

*Thanks to Jonathan Allan for saving 4 bytes*

# Answer
> 6 votes
# 05AB1E, ~~8~~ 7 bytes

```
>ÅF¹å¹m

```

Explanation:

```
>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

```

Try it online!

-1 thanks to Jonathan Allan for the 0-not-a-fibonacci-number workaround.

# Answer
> 5 votes
# Jelly,  ~~8 7~~  6 bytes

```
-r‘ÆḞċ

```

**Try it online!**

### How?

```
-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

```

Notes:

* the increment, , is needed so this works for **2** and **3**, since they are the **3rd** and **4th** Fibonacci numbers - beyond **3** all Fibonacci numbers are greater than their index.
* the `-` is needed (rather than just `‘R`) so this works for **0** since **0** is the **0th** Fibonacci number;

# Answer
> 5 votes
# Perl 6, 23 bytes

```
{$_∈(0,1,*+*...*>$_)}

```

# Answer
> 5 votes
# Seriously, 3 bytes

```
,fu

```

Try it online!

Returns the index +1 in the list of Fibonacci numbers if truthy, otherwise returns falsy.

**Explanation:**

```
,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)

```

# Answer
> 5 votes
# ZX81 BASIC 180 151 100 ~94 tokenized BASIC bytes

With thanks to Moggy on the SinclairZXWorld forums, here is a much neater solution that saves more bytes.

```
 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

```

This will output 1 if a Fibonacci number is entered, or zero if not. Although this saves bytes, it's much slower than the old solutions below. For speed (but more BASIC bytes) remove the `VAL` wrappers around the string literal numbers. Here is the old(er) solutions with some explanations:

```
 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

```

The amendments above saves further BASIC bytes to condensing the `IF` statements into a single `PRINT` in line 12; other bytes were saved by using the `VAL` keyword and, and using `GOTO CODE "£"`, which in the ZX81 character set is 12. Strings save more bytes over numbers as all numeric values are stored as floats so therefore take more space on the VAR stack.

# Answer
> 4 votes
## C#, 109 bytes

```
bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

```

Definitely could be improved, but I didn't have time.

# Answer
> 4 votes
# \>\<\>, ~~21~~ 19+3 = ~~24~~ 22 bytes

```
i1\{=n;
?!\:@+:{:}(

```

Input is expected to be on the stack at program start, so +3 bytes for the `-v` flag.

Try it online!

This works by generating Fibonacci numbers until they are greater than or equal to the input number, then checking the last generated number for equality with the input. Outputs `1` if it was a Fibonacci number, `0` otherwise.

To ensure that `0` is handled correctly, the seed is `-1 1` \- the first number generated will be `0` rather than `1`.

Thanks to @cole for pointing out that `i` can be used to push `-1` onto the stack when STDIN is empty. Very clever!

Previous version:

```
01-1\{=n;
}(?!\:@+:{:

```

# Answer
> 3 votes
# Mathematica, 37 bytes

```
!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

```

*-4 bytes from @ngenisis*

# Answer
> 3 votes
# Pari/GP, 32 bytes

```
n->!prod(x=0,n+1,fibonacci(x)-n)

```

Try it online!

# Answer
> 3 votes
# PHP, 44 bytes

```
for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

```

Try it online!

# PHP, 58 bytes

```
for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

```

Try it online!

# Answer
> 3 votes
# Dyalog APL, 17 bytes

```
0∊1|.5*⍨4 ¯4+5××⍨

```

Try it online!

# Answer
> 3 votes
# MATL (16 bytes)

```
2^5*4-t8+hX^tk=s

```

Try it online!

Not the golfiest solution, but wanted to use the direct method of checking if "5\*x^2+/-4" is a perfect square.

## Explanation:

```
2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

```

## Note:

In the "0" case it returns "2" because both 4 and -4 are perfect squares, same with 1 which produces "1 1". Consider any non-zero output as "truthy", and 0 as "falsy".

# Answer
> 3 votes
# Java (JDK), 37 bytes

```
s->s.matches(".?|(\\2?+(\\1|^.))*..")

```

Try it online!

This works for numbers up to 1,836,311,903 (47th fibonacci number) included. Above that, the result is undefined (including a potential infinite loop).

## Credits

* Thanks to Kevin Cruijssen and David Conrad for helping golfing :)
* Thanks to Kevin Cruijssen for porting the regex version, saving 12 bytes in the process!

# Answer
> 3 votes
# C# (.NET Core), 51 bytes

```
bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

```

Try it online!

-6 bytes thanks to @Oliver!

This solution uses a pretty straightforward recursive function.

* The variable `n` is the number to be tested.
* The variables `a` and `b` are the 2 most recent numbers in the sequence.
* Checks if the first of the 2 most recent number is less than input. When this is the case, a recursive call is made to the next numbers in the series.
* Otherwise, check whether the first number is equal to input and return the result.

The TIO link demonstrates this working for 1134903170 which exceeds the maximum value required by the challenge.

# Answer
> 3 votes
# Alchemist, ~~205~~ 134 bytes

Big thanks to ASCII-only for rather clever merging of states, saving 71 bytes!!

```
_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

```

Try it online or verify in batch!

## Ungolfed

```
# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop

```

# Answer
> 3 votes
# Vyxal `r`, 4 bytes

```
ÞFce

```

Try it Online! \- show all boolean results
Try it Online! \- show only numbers returning truthy

Thanks to Steffan. This based on the alternative 5 byte answer below, removing the need for the `$`.

# Vyxal, 5 bytes

```
ÞF0pc

```

Try it Online! \- show all boolean results
Try it Online! \- show only numbers returning truthy

```
ÞF   # All 1-indexed Fibonacci numbers as a LazyList.
0p   # Prepend the list with 0
c    # Is the input contained in the list?

```

Alternative 5 bytes:

```
ÞFc$e

```

Try it Online! \- show all boolean results
Try it Online! \- show only numbers returning truthy

```
ÞF   # All 1-indexed Fibonacci numbers as a LazyList.
c    # Is the input contained in the list?
$    # Swap above result with the input (this creates a copy of the input)
e    # Exponentiate. For an input of zero this will yield 0**0 == 1; for other
     # Fibonacci numbers, 1**{n>0} == 1; otherwise 0**{n>0} == 0.

```

The above two solutions work around the fact that there's no 0-indexed version of `ÞF`. Alternatively using `∆F` requires a different workaround, but it can also be done in 5 bytes:

```
Þn∆Fc

```

Try it Online! \- show all boolean results
Try it Online! \- show only numbers returning truthy

```
Þn  # All integers in an infinite list (0, 1, -1, 2, -2, ...)
∆F  # nth Fibonacci number, 0-indexed
c   # Contains - Check if one thing contains another

```

Using `ʀ` (Inclusive range \[0..input\]) instead of `Þn` wouldn't work, because the Fibonacci numbers \\$2\\$ and \\$3\\$ are not members of the lists \\$\[0,1,1\]\\$ and \\$\[0,1,1,2\]\\$ respectively. It would be necessary to use `›ʀ` (the range \[0..input+1\]), but for non-Fibonacci numbers that is exponentially slower than using `Þn` (and `Þn∆Fc` is in turn a bit slower than `ÞFc$e`).

Note that `Þn` includes negative numbers, and `∆F` on a negative number returns a negative Fibonacci number. However, `Þn∆Fc` only returns truthy for nonnegative Fibonacci numbers, probably due to a bug in Vyxal.

---

Without using any Fibonacci builtins (**7 bytes**):

```
k≈⁽+dḞc

```

Try it Online! \- show all boolean results
Try it Online! \- show only numbers returning truthy

The is based on lyxal's answer to Fibonacci function or sequence.

```
k≈   # the list [0, 1]
⁽+d  # lambda x, y: x + y
Ḟ    # Create an infinite sequence based on the function and the initial list.
c    # Does the list contain the input?

```

# Answer
> 2 votes
# Jelly, 5 bytes

```
ȷḶÆḞi

```

Try it online!

Returns 0 for non-Fibonacci numbers, and the 1-indexed position of the number in the Fibonacci sequence for Fibonacci numbers.

Explanation:

```
ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found

```

# Answer
> 2 votes
# R, ~~43~~ 40 bytes

```
pryr::f(x%in%DescTools::Fibonacci(0:45))

```

`pryr::f` creates a function:

```
function (x)
x %in% DescTools::Fibonacci(0:45)

```

Uses `DescTools::Fibonacci` to create the first `x+1` fibonacci numbers and checks for inclusion. `x+1` because the third fibnum is 2, and that wouldn't be enough to check for inclusion of 3.

Luckily `Desctools::Fibonacci(0)=0`, so that is a nice freebee.

-3 bytes thanks to MickyT

# Answer
> 2 votes
# Julia 0.4, 29 bytes

```
!m=in(0,sqrt(5*m*m+[4,-4])%1)

```

Try it online!

---

If this isn't how you do a Julia answer, let me know. I'm unsure of how input works on TIO.

# Answer
> 2 votes
# Haskell, 31 bytes

```
f=0:scanl(+)1f
(`elem`take 45f)

```

Try it online! This exploits the fact that the input will be in the range from 0 to 1,000,000,000, hence we need to check only the first 45 Fibonacci numbers. `f=0:scanl(+)1f` generates an infinite list of Fibonacci numbers, `take 45f` is the list of the first 45 Fibonacci numbers and `elem` checks whether the input is in this list.

---

### Unrestricted version: 36 bytes

```
f=0:scanl(+)1f
g n=n`elem`take(n+3)f

```

Try it online! For any `n`, taking the first `n+3` Fibonacci numbers will guarantee that `n` will be in this list if it's a Fibonacci number.

Note that this approach is incredible inefficient for high numbers that are not Fibonacci numbers, because all `n+3` Fibonacci numbers need to be computed.

# Answer
> 2 votes
# Common Lisp, ~~61~~ 54 bytes

```
(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

```

Try it online!

The reduction in size with respect to the previous version:

```
(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

```

was triggered by the idea that to generate the sequence of the Fibonacci numbers only two variables are necessary, not three.

# Answer
> 2 votes
# Javascript (ES6 without the \** operator), 44 bytes

```
f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

```

Relies on the ratio between successive Fibonacci numbers approaching the golden ratio. The value of c is the fractional part of the input divided by the golden ratio - if the input is Fibonacci then this will be very close to 1 and the value of c-c² will be very small.

Not as short as some of the other JS answers but runs in O(1) time.

# Answer
> 2 votes
# R, ~~32~~ 31 bytes

Takes input from stdin, returns `TRUE` or `FALSE` as appropriate.

```
any(!(5*scan()^2+-1:1*4)^.5%%1)

```

# Answer
> 2 votes
# D, 98 79 bytes 77 bytes

*-19 bytes: changed square number algorithm (which also had the side effect of not needing `import std;`) and realized the non-UFCS way was 1 byte shorter*

golfed:

```
int p(real z){return z^^.5%1==0;}int f(int z){return p(5*z*z+4)||p(5*z*z-4);}

```

readable:

```
int p(real z){
    return z^^.5%1==0
}
int f(int z){
    return p(5*z*z+4)||p(5*z*z-4);
}

```

where `f` is the function that tests if a number is a fibonacci number.

This uses the fact that `a positive integer z is a Fibonacci number if and only if one of 5z^2 + 4 or 5z^2 − 4 is a perfect square.` wikipedia

Also `real` instead of `float` for one less byte, and returning an `int` instead of `bool` to save another byte (since ints are truthy if they're nonzero, and D implicitly casts expressions to the function's return value if possible, in this case casting a bool to an int).

There's probably some way to avoid having the extra function `p` (used to check if a number is a perfect square) but I can't find it out.

edit: replaced z^^2 with z\*z

# Answer
> 1 votes
# 05AB1E, 7 bytes

```
ÅFå¤¹_~

```

Try it online!

# Answer
> 1 votes
# Mathematica, 33 bytes

```
AtomQ@*InverseFunction[Fibonacci]

```

# Answer
> 1 votes
# JS (ES6), 57 bytes

```
n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

```

Uses carusocomputing's method. Alot golfier than my other answer.

### Ungolfed

```
n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}

```

# Answer
> 1 votes
# C (gcc), ~~76~~, ~~52~~, 71 bytes,

## ~~Thanks GPT4 with a bit of prompt engineering~~

### Way off, just plain wrong, good for the three test inputs but...

## GTP4 after some serious tutoring finally 58 bytes

```
f(n,a,b){for(a=b=1;a<n;b+=a,a=b-a);return n==a||n==b||!n;}

```

```
F(n){return n<2?n:F(n-1)+F(n-2);}i;f(n){for(i=0;F(i)<n;i++);int x=F(i)==n;}

```

```
f(n,i,j){for(i=0,j=1;j<n;i=j,j+=i);return j==n||!n;}

```

Try it online!

# Answer
> 1 votes
## \>\<\>, ~~40~~ 83 bytes

Added 43 bytes so that it takes the correct input

```
i:0(?vc4*-
 v&a~<
+>l2(?v$&:a*&*
v   ~&<
>10r:&1)?v1n;
=?v&:&)?v>:{+::&:&
  >1n;n0<

```

A less golfy version would be:

```
// Read input
i:0(?vc4*-
     >~a&v
         >l2(?v$&:a*&*+
              >&~04.
// Determine if in Fibonacci
 10r:&1)?v1n;
         >:{+::&:&=?v&:&)?v
                    >1n;n0<

```

# Answer
> 1 votes
# AWK, ~~56 63~~  61 bytes

```
{for(n[++j]++;n[j]<$1;n[++j]=n[j]+n[j-1]){}$0=$0?n[j]==$1:1}1

```

Try it online!

Brute force is fun. :) If you want it to work for arbitrarily large numbers, add a `-M` argument, but that is outside the scope of the problem.

7 bytes added to account for `0` as input, but shaved a couple off using the ternary operator.

# Answer
> 1 votes
## CJam, 37 bytes

```
ri1T{\1$+_3$-g"1T 0_ 1"S/=~}g]W=

```

CJam has no Fibonnaci built-in. On the bright side, this does use `g` twice, and I think this is the first time I've ever used it!

# Answer
> 1 votes
# k, 20 bytes

```
{*x=*|(*x>)(|+\)\1 1}

```

Generates fibonacci numbers until it overshoots. Then it checks the last one it generated for equality. `1` is truthy, `0` is falsey.

Try it online.

# Answer
> 1 votes
# Mathematica, 30 bytes

```
Or@@EvenQ[2Sqrt[5#^2+{4,-4}]]&

```

# Answer
> 1 votes
# Java 8, 94 bytes

```
x->{int i=0;for(;c(i++)<=x;);return c(i-2)==x;}int c(int n){return n<1?0:n<2?1:c(n-1)+c(n-2);}

```

**Explanation:**

Try it here. (NOTE: It's a bit slow for very large test-cases.)

```
x->{                 // Method (1) with integer parameter and boolean return-type
  int i=0;           //  Index
  for(;c(i++)<=x;);  //  Loop as long as the Fibonacci number is smaller or equal to the input
  return c(i-2)==x;  //  And then return if the input equals the previous Fibonacci number
}                    // End of method (1)

                     // Method to get `n`th Fibonacci number
int c(int n){        // Method (2) with integer parameter and integer return-type
  return n<1?        //  If `n`==0:
    0                //   Return 0
   :n<2?             //  Else if `n`==1
    1                //   Return 1
   :                 //  Else:
    c(n-1)+c(n-2);   //   Return recursive calls with `n-1` and `n-2`
}                    // End of method (2)

```

# Answer
> 1 votes
# \>\<\>, 33+3 = 36 bytes

3 bytes added for the -v flag

```
10:{:}=?!v1n;
)?v:@+10.\:{:}
n0/;

```

Try it online!

**Or 54 bytes without using the -v flag**

```
 0ic4*-:0(?v$a*+10.
:{:}=?!v1n;\10
v:@+d1.\:{:})?
\0n;

```

Try it online!

# Answer
> 1 votes
# Actually, 2 bytes

```
fu

```

Try it online!

Pushes either a positive number for truthy or 0 for falsy.

# Answer
> 1 votes
# Cubix, 22 ~~24~~ bytes

0 is truthy, nothing is falsey

```
@0O1I!^/@.W<rq\?-p+;;u

```

Try it online!

```
    @ 0
    O 1
I ! ^ / @ . W <
r q \ ? - p + ;
    ; u
    . .

```

Watch it run

~~I may be able to get a couple more out of this~~ ... found them with a change to the initial redirect into the loop

* `I` get the integer to check
* `!` check for 0 input
    + `^O@` if zero, output and halt
* `/01` initialise the stack for doing the sequence
* `W<W` change lane onto the redirect back to self, then change lane into looping section
* `+p-?` bring the check value to the top, subtract and check
    + `/@` On a positive result reflect and halt
    + `\^O@` On a zero result reflect, output and halt
    + `u;\qr;` Remove the check, move check value to bottom, rotate the sum, remove the low value. Continue into loop.

# Answer
> 1 votes
# Java, 40 bytes

```
r->Math.abs((r*Math.sqrt(5)-~r)%2*r-r)<2

```

This is a straight Java port of @xnor's answer.

# Answer
> 1 votes
# , 57 bytes

A nice, clean, no-nonsense solution:

```
int f(int n,int x=0,int y=1){return y<n?f(n,y,x+y):y==n;}

```

---

This one is 58 bytes but doesn't use recursion, and so might be more practical for larger inputs:

```
alias f=(n){int x,y=1;for(;y<n;y+=x,x=y-x){}return y==n;};

```

---

And here's one where the function declaration itself is only 54 bytes, though it depends on the mach library.

```
import mach.range : r=recur, l=last;
import mach.math.vector : v=vector;
const z=v(0,1);

// The 54-byte function
alias f=n=>z.r!(a=>v(a.y,a.x+a.y),a=>a.y>n).l(z).y==n;

// Exploded for readability
alias f=n=>(
    vector(0,1) // Seed the sequence
        .recur!(v=>vector(v.y,v.x+v.y),v=>v.y>n) // Compute Fib numbers until N
        .last(vector(0,1)).y == n // If the last number was N, return true
        // Value in parens "last(...)" is a fallback for n==0 and empty seq.
);

```

---

# Answer
> 1 votes
# Japt, ~~8~~ 7 bytes

```
ÆMgXÃøU

```

Test it

---

## Explanation

Implicit input of integer `U`.

```
Æ   Ã

```

Generate an array of integers from 0 to `U-1` and pass each through a function where `X` is the current element.

```
MgX

```

Get the `X`th Fibonacci number.

```
øU

```

Check if the array contains (`ø`) the original input `U`. Implicitly return the boolean result.

# Answer
> 1 votes
# cQuents, 8 bytes

```
=0,1?Z+Y

```

Try it online!

## Explanation

```
=0,1        Set sequence start to 0,1
    ?       Mode: Query (assumes increasing sequences)
     Z+Y    Each item is the previous two summed

```

# Answer
> 1 votes
### C, 36 bytes

```
f(x,a,b){return x>b?f(x,b,a+b):x==b}

```

It puts some warnings, and requires at least 32-bit integers. Newer C standards probably won't even compile it. It should be called as `f(142857,0,1)`.

Bonus: it can calculate Fibonacci-ness with different initial values, too.

# Answer
> 1 votes
# Ruby, ~~64 41~~ 40 bytes

```
->n,a=b=1{a,b=b,a+b;a<n ?redo:a>n ?p: 1}

```

Try it online!

# Answer
> 1 votes
# Brachylog, ~~16~~ 14 bytes

```
1;0⟨t≡+⟩ⁱhℕ↙.!

```

Try it online!

Takes input through the output variable and outputs through success or failure, and in the case of success the input variable is unified with 1.

```
1;0               Starting with [1,0],
        ⁱ         iterating
   ⟨ ≡ ⟩          replacing
   ⟨t  ⟩          the first element of the pair with the last element
   ⟨  +⟩          and the last element with the sum of the pair
         h        until the first element
          ℕ↙      is greater than or equal to
            .     the output variable,
             !    and stopping then,
         h        the first element of the pair is equal to the output variable.

```

`ℕ↙.!` is necessary for it to terminate on false test cases.

# Answer
> 1 votes
# k4, ~~30~~ 26 bytes

-4 thanks to ngn!

```
{x in(x>*|:){x,+/-2#x}/!2}

```

---

the above is a simple while iterator. `(cond){func}/arg`.

```
            {x,+/-2#x}           / x join sum over last 2 elements of x (i.e. append next Fib)
     (x>*|:)          /!2        / while outer func input is greater than last element (x>*|:) of inner func output, pass inner func output to inner func
 x in                            / check if x is in array. returns boolean

```

# Answer
> 1 votes
# CSASM v2.1.2.3, 259 bytes

```
func main:
push 0
pop $1
push 1
pop $2
in ""
conv i32
pop $a
push $a
push 1
comp.lte
push $f.o
brfalse c
.lbl b
push 1
print
ret
.lbl a
push 0
print
ret
.lbl c
clf.o
push $1
dup
push $2
add
pop $1
pop $2
push $1
push $a
comp.gt
push $f.o
brtrue a
push $1
push $a
comp
push $f.o
brtrue b
br c
ret
end

```

**Commented and ungolfed:**

```
func main:
    ; Seed the sequence ($1 = new value, $2 = old value)
    push 0
    pop $1
    push 1
    pop $2

    ; Get the input, convert it to an integer and store it in the accumulator
    in ""
    conv i32
    pop $a

    ; If $a <= 1, print truthy (1)
    push $a
    push 1
    comp.lte
    push $f.o
    brfalse loop

.lbl isFib
    ; Print a truthy value
    push 1
    print
    ret
.lbl notFib
    ; Print a falsy value
    push 0
    print
    ret

    ; Keep generating new Fibonacci numbers until $1 is >= $a
    .lbl loop
        ; Clear the Comparison flag
        clf.o

        ; Get the next Fibonacci pair:
        ; $2 = $1, $1 = $1 + $2
        push $1
        dup
        push $2
        add
        pop $1
        pop $2

        ; If $1 > $a, the input wasn't a Fibonacci number
        push $1
        push $a
        comp.gt
        push $f.o
        brtrue notFib

        ; If $1 == $a, the input was a Fibonacci number
        push $1
        push $a
        comp
        push $f.o
        brtrue isFib

        ; Still need to generate more numbers
        br loop
    ret
end

```

# Answer
> 1 votes
# dc, 34 bytes

```
d0r^+0 1[d3R+d4Rd_5R>s]dssx0r4R-^p

```

Try it online!

Prints 1 if the number at the top of the stack is a fibonacci number, 0 otherwise.

# Answer
> 1 votes
# Bash, 87 bytes

```
read z;f=0;g=1;h=1
for((;;)){
h=$(($f+$g))
if [ $z == $f ];then echo 1;fi
f=$g;g=$h
}

```

Attention endless loop, no break - stop the code after some seconds manually

Try it online!

# Answer
> 1 votes
# Prolog (SWI), 36 bytes

```
\N:-1+N+0.
Y+N+X:-X<N,X+Y+N+Y;X=:=N.

```

Try it online!

# Answer
> 1 votes
# Thunno 2, 5 bytes

```
ĖÆF$Ƈ

```

Attempt This Online!

#### Explanation

```
ĖÆF$Ƈ  # Implicit input
Ė      # Push [0..input]
 ÆF    # For each n, get the nth Fibonacci number
       # (starting at 0->0, 1->1, 2->1, etc.)
   $Ƈ  # Is the input in this list?
       # Implicit output

```

# Answer
> 1 votes
# Desmos, ~~58~~ 41 bytes

*-17 bytes thanks to Aiden Chow!*

```
f(n)=0^{mod((5nn+[4,0^n4-4])^{.5},1).min}

```

Try it on Desmos!

Checks if either \\$5n^2+4\\$ or \\$5n^2-4\\$ is a perfect square.

# Answer
> 0 votes
# Swift, 66 bytes

```
func f(n:Int){var a=0,b=1,c=0;while n>a{c=a;a=b;b=c+b};print(n<a)}

```

---

Try it out! \- *NOTE: Prints `False` as truthy and `True` for falsy.*

# Answer
> 0 votes
# Groovy, ~~44~~ ~~43~~ 37 bytes

```
{n->[-4,4].any{!((n*n*5+it)**0.5%1)}}

```

---

If `(5*(n**2)±4)**0.5` is ever an integer, the number is a fibbonacci number.

# Answer
> 0 votes
# JS (ES6), 78 bytes

```
n=>{y=n?0:1;f=x=>x<3?1:f(x-1)+f(x-2);for(x=0;x<n+2;x++)f(x)==n?y=1:0;return y}

```

### Ungolfed:

```
var f = n => {
    var y = n ? 0 : 1;
    f=x=>x<3?1:f(x-1)+f(x-2);//from this: https://codegolf.stackexchange.com/a/25142/70700
    for (var x = 0; x < n + 2; x++){
        if(f(x) == n){
            y = 1;
        }else{
            y = 0;
        }
    }
    return y;
};

```

# Answer
> 0 votes
# C (gcc), 50 bytes

```
a,b,c;f(n){for(a=0,b=1;n>(c=a);b=c)a+=b;n=(n==c);}

```

Try it online!

# Answer
> 0 votes
## Clojure, 61 bytes

```
(def s(lazy-cat[0 1](map +(rest s)s)))#((set(take(inc %)s))%)

```

This actually constructs the Fibonacci sequence `s`, grabs enough elements from it and checks if the input is found. Returns `nil` for falsy and the input number for truthy.

# Answer
> 0 votes
# Javascript, 89 bytes

```
function f(n){s=Math.sqrt;c=Math.ceil;x=5*n**2;a=s(x-4);b=s(x+4);return c(a)==a||c(b)==b}

```

This uses the fact that all fibonacci numbers have the property that 5x^2+4 or 5x^2-4 must be square. It takes the square root of these numbers and checks if they equal their ceiling value.

# Javascript, 69 bytes (if it doesn't need to be a function)

```
s=Math.sqrt;c=Math.ceil;x=5*n**2;a=s(x-4);b=s(x+4);n=c(a)==a||c(b)==b

```

This one does the exact same thing, except instead of calling a function, you set `n` to the number to test, and `n` is set to true/false based on the result.

This is my first code golf entry, so let me know if there's anything to improve here. :)

# Answer
> 0 votes
# QBIC, 24 bytes

```
≈g<:|g=p+q┘p=q┘q=g]?g=a

```

## Explanation

```
≈g<:|   WHILE g (running fibonacci total) is less than input
g=p+q   Get the next fib by adding p (n-2, starts as 0) and q (n-1, starts as 1)
┘       (Syntactic linebreak)
p=q     increase n-2
┘       (Syntactic linebreak)
q=g     increase n-1
]       WEND
?g=a    PRINT -1 if g equals input (is a fib-number), or 0 if not.

```

# Answer
> 0 votes
# Python 3, ~~56 53~~ 50 bytes

* Thanks to @Fedone for 3 bytes: as a function

```
def f(m):
 a=b=1
 while a<m:b,a=a,a+b
 print(a==m)

```

Try it online!

# Answer
> 0 votes
# Swift, 72 bytes

```
func f(i:Int,a:Int=0,b:Int=1)->Bool{return a<i ?f(i:i,a:b,b:a+b) :i==a}

```

Un-golfed:

```
func f(i:Int, a:Int=0, b:Int=1)->Bool{
    return a<i ? f(i: i, a: b, b: a+b) : i==a
}

```

I am recursively calling `f` until `a` is equal to or greater then `i`. Then, I check to see if `i` and `a` are equal.

You can try it here

# Answer
> 0 votes
## Python 3, 59 Bytes

```
f=5*int(input())**2
print(not((f+4)**0.5%1and(f-4)**0.5%1))

```

# Answer
> 0 votes
# \[Python 3\], 48 bytes

```
m=0;k=1;exec("k,m=m,m+k\nif k==n:print(1)\n"*n)

```

If n is the input, we generate the first n Fibonacci numbers and check if our input is one of them.

# Answer
> 0 votes
# MathGolf, 4 bytes

```
⌠rf╧

```

Try it online!

## Explanation

We need to increment the input twice before creating the range because we know that \\$F\_{n+1} \geq n,\forall n \geq 0\\$.

```
⌠      increment twice
 r     range(0, n)
  f    pop a, push fibonacci(a) (maps to the range)
   ╧   pop a, b, a.contains(b) (check if input is in list)

```

# Answer
> 0 votes
# brev, 46 bytes

```
(c(fn(or(= x z)(and(< x z)(f y(+ x y)z))))0 1)

```

---
Tags: code-golf, sequence, decision-problem, fibonacci
---


title: Print the Black Mirror episode title

text:
# Question
Title: Print the Black Mirror episode title
Given two integers, *s* and *e*, print the title of *Black Mirror* series #*s* episode #*e*.

Expected output is as below, case sensitive. Output for blank cells and invalid inputs is unspecified.

```
e↓s→                          1                  2                     3               4                              5                6
 1 | The National Anthem       | Be Right Back    | Nosedive            | USS Callister | Striking Vipers              | Joan Is Awful  |
 2 | Fifteen Million Merits    | White Bear       | Playtest            | Arkangel      | Smithereens                  | Loch Henry     |
 3 | The Entire History of You | The Waldo Moment | Shut Up and Dance   | Crocodile     | Rachel, Jack, and Ashley Too | Beyond the Sea |
 4 |                           |                  | San Junipero        | Hang the DJ   |                              | Mazey Day      |
 5 |                           |                  | Men Against Fire    | Metalhead     |                              | Demon 79       |
 6 |                           |                  | Hated in the Nation | Black Museum  |                              |                |

```

(The episode "White Christmas" is grouped with series 2 on Netflix, but originally aired as a standalone special, so it is not part of the challenge. The film *Bandersnatch* is likewise standalone and exempt.)

This question was posted before the release of series 6, at a time when it appeared the future of *Black Mirror* was in jeopardy. I have added series 6 to the challenge; answers posted before this edit are still considered valid.

# Answer
# Husk, 162 bytes

```
!x'x!¶¨Σṅ←ÿ‼⌋xżFE«Ȯ⌊Żψ'xΣẏ>ï?₀fẏu₈eṙ‼ḂkxẇïBȦrxΣ«QẆḟṁŸ)⁶ıex₉?²tx«‼UÜUÄd□Δ'xS▲⌋ȷ9oxṀËäαγFxHȦ∂↕εṄ|≠USSχ⁷ıżxŻKȦ£Ġx£%Øx□´'ËDJxẎȦlḊh₈Ċż_ṀÿKi▼V₉→xSmi►&η$x£ƒ´,⌋ȷ@,Ädÿ¿◄θ⁰

```

Try it online!

A perfect task for Husk's string compression. Seasons are separated with newlines and episodes are separated with 'x'. Then:

```
!x'x!¶¨...
      ¨...     Big compressed string
     ¶         Split on newlines
    !          Take the line corresponding to given season
 x'x           Split on 'x'
!              Take the title of the given episode

```
> 5 votes

# Answer
# 05AB1E, 213 bytes

```
.•Ω?"Λ1äγÍθ}Æuмï∍βb6G¨—Wc“jép¡úórÑ9ǝ‘øδs@!иésb•#`”0á½Ú©ÿ0ŽÚÿ0Çˆ,—É, ÿÍ±…«00
0€€ƒ³à¬ÿ0ßà‡ÈÝìs0€€îÆ„ª of€î00
0€ïƒ©‚ƒ0„¸Ÿâ0€€Ò´doœÂ00
«¢d in ÿï¹0ÄÃÿ0†•ÿ0À…€¾ ÿ–›0†ŽŠ€ÿ0…±†¤ŠÄ
ƒÏ—´0USS„Òÿ0Aÿ0Cÿ0ÂŒ ÿ DJ0îÊÿ”¶¡0δ¡IèIèðÚ

```

Try it online or verify all test cases.

**Explanation:**

```
.•Ω?"Λ1äγÍθ}Æuмï∍βb6G¨—Wc“jép¡úórÑ9ǝ‘øδs@!иésb•
            "# Push compressed string "head the rocodile rkangel ister ipero and test dive the hem and ereens ers"
 #           # Split it on spaces
  `          # Pop and push each string separated to the stack
”0á½Ú©ÿ0ŽÚÿ0Çˆ,—É, ÿÍ±…«00
0€€ƒ³à¬ÿ0ßà‡ÈÝìs0€€îÆ„ª of€î00
0€ïƒ©‚ƒ0„¸Ÿâ0€€Ò´doœÂ00
«¢d in ÿï¹0ÄÃÿ0†•ÿ0À…€¾ ÿ–›0†ŽŠ€ÿ0…±†¤ŠÄ
ƒÏ—´0USS„Òÿ0Aÿ0Cÿ0ÂŒ ÿ DJ0îÊÿ”
             # Push dictionary string "0 Striking Vipÿ0 Smithÿ0 Rachel, Jack, ÿ Ashley Too00\n
             # 0 The National Antÿ0 Fifteen Million Merits0 The Entire History of You00\n
             # 0 Be Right Back0 White Bear0 The Waldo Moment00\n
             #  Hated in ÿ Nation0 Noseÿ0 Playÿ0 Shut Up ÿ Dance0 San Junÿ0 Men Against Fire\n
             #  Black Museum0USS Callÿ0Aÿ0Cÿ0 Hang ÿ DJ0 Metalÿ",
             # with all `ÿ` automatically filled with the strings on the stack
 ¶¡          # Split it on newlines
   0δ¡       # Split each line on 0s
             #  [[""," Striking Vipers"," Smithereens"," Rachel, Jack, and Ashley Too","",""],
             #   [""," The National Anthem"," Fifteen Million Merits"," The Entire History of You","",""],
             #   [""," Be Right Back"," White Bear"," The Waldo Moment","",""],
             #   [" Hated in the Nation"," Nosedive"," Playtest"," Shut Up and Dance"," San Junipero"," Men Against Fire"],
             #   [" Black Museum","USS Callister","Arkangel","Crocodile"," Hang the DJ"," Metalhead"]]
      Iè     # Index the first input-integer into it (0-based and with wraparound)
        Iè   # Index the second input-integer into that list (0-based and with wraparound)
          ðÛ # Remove any leading spaces
             # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to use the dictionary?* and *How to compress strings not part of the dictionary?*) to understand how the used compressed and dictionary strings work.
> 4 votes

# Answer
# Stax, 202 bytes

```
ü○b(╠◘qÅñÿ[%Uδö╬ε#êc∙╪≈ü╒┘ú┴tÆ↔nU¥┴♣ßª•┼<\╣`vΘ╒°²~♦∙'E♂○N½←àp▄û'XpéIê┼z♂Qìa~Æq7-T⌐ ○¡B▬#√╤cçµM╖Æ♦N╜Ü◄4òτ`≈úG{╧►)┴╬║º,Φ┤╫ÿα►]Q╬≈♠ [εjy0z▲dΘÜ╚é6♥#ö»ë'KC▬.W◙)lH↓√↓ö¿▐▌φ┬;┼ΣuΓuΣiè‼x╘ö╝▐┴ßIG•∙¿╦↓AQt}yd◘$éⁿ≤←

```

Run and debug it

This program takes episode and season as input, separated by a space.
> 3 votes

# Answer
# Vyxal, 192 bytes

```
`λƛ ¬ε Ṫṅ¥ṗXṠ↳ ÷⁋ Ṗ≈sXλƛ ∆ɾ ∧Ġ of λß
Be ¬ẏ λǑX∧… ∞↑Xλƛ W…±o ɽ⁋
₁ḣ¦ḭX∨±∨ḊXż≬ Up λ¬ ↔÷X⟑ɖ ∨Ǐ °↔X←Ġd in λλ ⌐±
USS ⟑«iḊꜝrXArk›ǎXC≥ẋo∩ȧeX⟩ẇ λλ DJX∆↑÷≠X¬⁼ ¢⁋
Ẇ± Ŀʀ□ẊX€∧□Ṅ↳¾X₄ð, ¢…, λ¬ §⋏ ⟑⋏`↵\X/?i?i

```

Try it Online!

```
`...`         # Dictionary-compressed string
     ↵        # Split on newlines
      \X/     # Split on Xs (vectorised)
         ?i?i # Index input twice

```
> 3 votes

# Answer
# Charcoal, 224 bytes

```
§⪪§⪪”}∨⊙α⁷ξ{⪪\`Ｇ↔Iλ?Ｉ⟧∧≕EαγＲ≔³E↙\`UκêΣJ4⧴Ｕ↙�～Ｂ⁺^dF]η8A⊖ξ≡Ｗ¦¶⧴hNνＸ^#Ol▶⊙｜Ｑ|,/(:ZＮQξζG↥≧⟲ψ∨]⮌⊖≦#Rς+vQlＫ≧⦄⁴φＣ7“L¡⊘[⁸⮌!⌕↗Ｏp;⧴‹Hr,◧⁹‖·›↨χ➙⌕↙bＭ″G@ⅉ<↔ＧnQＳ§‖⎚Þ⟧⊗¤E*ⅈ⁶℅Orν%Ｆ¤×Xbη＆◨χＪＷCＸz�Π8D>νＢ⁶≔Ｘ″~↖≡@/ÀＹ#¦▷Ｉ¿↷Φ№!｜↔δＭKＵλÀE§χＵo:γ@▷”¶Ｎ⸿Ｎ

```

Try it online! Link is to verbose version of code. Explanation:

```
    ”...”       Compressed table of episode titles
   ⪪     ¶      Split on `\n`s
  §       Ｎ     Cyclically index by series
 ⪪         ⸿    Split on `\r`s
§           Ｎ   Cyclically index by episode
                Implicitly print

```

Because Charcoal uses cyclic 0-indexing the last series and last episode of each series will wrap around to 0 so they actually appear first in the table.
> 2 votes

# Answer
# JavaScript, 353 bytes

```
s=>e=>`The National Anthem|Fifteen Million Merits|The Entire History of You||||Be Right Back|White Bear|The Waldo Moment||||Nosedive|Playtest|Shut Up and Dance|San Junipero|Men Against Fire|Hated in the Nation|USS Callister|Arkangel|Crocodile|Hang the DJ|Metalhead|Black Museum|Striking Vipers|Smithereens|Rachel, Jack, and Ashley Too`.split`|`[s*6+e-7]

```

Try it online!
> 1 votes

# Answer
# Python 3, 360 bytes

```
lambda s,e:"The National Anthem|Fifteen Million Merits|The Entire History of You||||Be Right Back|White Bear|The Waldo Moment||||Nosedive|Playtest|Shut Up and Dance|San Junipero|Men Against Fire|Hated in the Nation|USS Callister|Arkangel|Crocodile|Hang the DJ|Metalhead|Black Museum|Striking Vipers|Smithereens|Rachel, Jack, and Ashley Too".split("|")[s*6+e-7]

```

Try it online!
> 0 votes

# Answer
# Bash, 291 + 45 bytes

up to series 6

```
base64 -w0|cut -d2 -f$2|cut -d3 -f$1|tr 45 \ ,

```

Attempt This Online!

The input is generated with `cat table | tail -n 6 | sed "s/ *| */|/g" | cut -d "|" -f 2-7 | tr "\n| ," "2345" | sed "s/332$//" | base64 -d`.
> 0 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: Help me do my washing

text:
# Question
Title: Help me do my washing
Help! My **Completely Automated Lights From Darks Separator V3001.01** broke! :(

# Guidelines

---

## Task

Write a program that will take an input of an array (or a list in some languages) of any amount of strings that are either the letter L or the letter D (representing lights or darks) and output an array that contains two arrays, one with all the L's, and one with all the D's.

---

## Rules

* It's code golf so the shortest answer in bytes wins
* Input will only ever contain capitals
* There must be the same number of L's in the output as there is in the input, same goes for the D's
* The input may only have one element (or maybe even *zero* elements)
* If one or both of the output arrays contain no elements, output an empty list (in some languages this may mean you need to output a string)
* Always have the first array be the array of L's

---

## Example output:

`["L","D","L","D","D"] -> [["L","L"],["D","D","D"]]`

`["L","L","L"] -> [["L","L","L"],[]]`

`["D","D"] -> [[],["D","D"]]`

`[] -> [[],[]]`

# Answer
> 12 votes
# APL, 8 bytes

```
'DL'~⍨¨⊂

```

Explanation:

* : enclosed input
* `~⍨¨`: without each
* `'DL'`: 'D' and 'L'

Examples:

```
      ('DL'~⍨¨⊂) 'LDLDD'
┌──┬───┐
│LL│DDD│
└──┴───┘
      ('DL'~⍨¨⊂) 'LLL'
┌───┬┐
│LLL││
└───┴┘
      ('DL'~⍨¨⊂) 'DD'
┌┬──┐
││DD│
└┴──┘
      ('DL'~⍨¨⊂) ''
┌┬┐
│││
└┴┘

```

# Answer
> 13 votes
# Python 3, 37 bytes

```
lambda a:[[c]*a.count(c)for c in"LD"]

```

Try it online!

# Answer
> 5 votes
# Haskell, 28 bytes

```
f l=[filter(==[c])l|c<-"LD"]

```

Try it online!

If the input can be a list of characters, the `[]` around `c` can be removed.

# Answer
> 4 votes
# PHP, 46 bytes

Assumed given list is: `$arr = ['L','L','D','D','L','D','D','D','D','L'];`

`foreach($arr as $b){$a[$b][]=$b;};print_r($a);`

# Answer
> 3 votes
# Mathematica, 27 bytes

```
Rest/@Gather[{L,D}~Join~#]&

```

Pure function taking a list of `L`s and `D`s (symbols, not characters/strings) as input and returning a list of two lists. For example,

```
Rest/@Gather[{L,D}~Join~#]& @ {D, L, L, D, L}

```

returns `{{L, L, L}, {D, D}}`. Try it online!

`Gather` by itself is close to what we want, but fails to meet the spec in two ways: it doesn't produce empty lists if the input is missing `L`s or `D`s, and it doesn't always sort `L`s to the left. Replacing the input `#` with `{L,D}~Join~#` solves both problems at once: it means there will be at least one `L` and at least one `D`, and the `L`s will be returned first since an `L` was encountered first. `Rest/@` then removes the initial `L` and `D`.

(I tried a solution using `Count`, but due to currying issues, it didn't seem to be shorter: `±q_:=#~Table~Count[q,#]&/@{L,D}` is 31 bytes.)

# Answer
> 3 votes
## Haskell, 32 bytes

```
import Data.List
partition(>"K")

```

Just a boring library function.

Try it online!

# Answer
> 3 votes
# Japt, ~~13~~ ~~12~~ 10 bytes

```
2Æf¥"LD"gX

```

Test it (`-Q` flag for visualisation purposes only)

---

## Explanation

Implicit input of array `U`.

Generate the array `[0,1]` and pass each element through a function, with `X` being the current element.

Filter `U` by checking for equality...

```
"LD"gX

```

...with the character in string `LD` at index `X`.

# Answer
> 3 votes
# Ruby, 26 bytes

```
->x{x.partition{|e|e==?L}}

```

Try it online!

# Answer
> 2 votes
# Prolog (SWI), 42, 37 bytes

```
l('L').
w(L,D,W):-partition(l,W,L,D).

```

Try it online!

Given that `W` is a list of washing, `w/3` will unify `L` and `D` into lists of Lights and Darks respectively, by partitioning the washing against a predicate which succeeds if an item is a Light.

\[Edit: golfed -5 thanks to Fatalize\]

# Answer
> 2 votes
# Common Lisp, ~~66~~ 65 bytes

```
(defun f(x)`(,(remove"D"x :test'equal),(remove"L"x :test'equal)))

```

Try it online!

If, instead of strings, we use symbols, then it is much shorter:

# Common Lisp, ~~42~~ ~~41~~ 40 bytes

```
(defun f(x)(mapcar'remove'(D L)`(,x,x)))

```

Try it online!

```
(f '(D D L L D L D)) ; => ((L L L) (D D D D))

```

# Answer
> 2 votes
# PHP7, ~~52~~ 45 bytes

*-7 bytes thanks to @Jörg Hülsermann*

```
foreach($argv as$a)$$a[]=$a;print_r([$L,$D]);

```

Use with CLI as `php -r a.php L L L D D L D`

The script goes through the provided arguments and appends them to an array based on its value.

# Answer
> 2 votes
# Racket, 48 bytes

```
(compose list((curry partition)(λ(x)(eq? x'L))))

```

Just apply this anonymous function to, e.g., `'(L D L D D L)`

# Answer
> 2 votes
## Mathematica, ~~22~~ 18 bytes

*4 bytes saved by the genius of CalculatorFeline!*

```
Cases@@@{#|L,#|D}&

```

Try it online, or at the Wolfram sandbox!

Input is a list of the symbols `L` and `D` — not strings, just the letters on their own, like in Greg Martin's answer. The syntax `#|L` is shorthand for `Alternatives[#,L]`, but the `@@@` syntax replaces the head `Alternatives` with `Cases`, so this code is equivalent to `{Cases[#,L],Cases[#,D]}&`.

# Answer
> 1 votes
# Pyth, ~~10~~ 9 bytes

```
mc@dQ1"LD

```

Test suite.

# Answer
> 1 votes
# 05AB1E, 8 bytes

```
'LÃ¹'DÃ)

```

Try it online!

# Answer
> 1 votes
# Javascript (ES6), 37 bytes

This is based on a (now deleted) Javascript (ES6) answer.

```
a=>[(b=c=>a.filter(d=>c==d))`L`,b`D`]

```

**Ungolfed version:**

```
function(array) {
  function filter(character){
    return array.filter(function(d) {
      return character == d;
    });
  }
  return [filter("L"), filter("D")];
}

```

**Example code snippet:**

```
f=

a=>[(b=c=>a.filter(d=>c==d))`L`,b`D`]

console.log(f(["L", "D", "L", "D", "D"]))
```

# Answer
> 1 votes
# Java 8, ~~110~~ 106 bytes

```
a->{String[]r={"",""};for(char c:a)r[c/69]+=c;return new char[][]{r[1].toCharArray(),r[0].toCharArray()};}

```

-4 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
a->{                      // Method with char-array parameter and 2D char-array return-type
  String[]r={"",""};      //  Two Strings in an array
  for(char c:a)           //  Loop over the characters of the input
    r[c/69]+=c;           //   Append either of the two String with the character
                          //   c/69 will result in 0 for 'D' and 1 for 'L'
                          //  End of loop (implicit / single-line body)
  return new char[][]{    //  Return a 2D character-array
    r[1].toCharArray(),   //   With the String for L's converted to a char-array
    r[0].toCharArray()};  //   and String D's converted to a char-array
}                         // End of method

```

# Answer
> 1 votes
# C#, 61 bytes

```
using System.Linq;a=>new[]{a.Where(c=>c<69),a.Where(c=>c>68)}

```

Full/Formatted Version:

```
using System;
using System.Linq;

class P
{
    static void Main()
    {
        Func<char[], System.Collections.Generic.IEnumerable<char>[]> f =
            a => new[] { a.Where(c => c < 69), a.Where(c => c > 68) };

        Console.WriteLine(string.Join(", ", f(new[]{ 'L', 'D', 'L', 'D', 'D' }).SelectMany(a => a.Select(c => c))));

        Console.ReadLine();
    }
}

```

# Answer
> 1 votes
# F#, 37 bytes

```
let f s=List.partition(fun a->a="L")s

```

Try it online!

Takes input as a list of strings, and returns two lists, the first with elements where `fun a -> a="L"` is true and the other with elements that result in false.

# Answer
> 1 votes
# Jelly, 10 bytes

```
ẎfÐ€⁾LDW€€

```

Try it online!

In Jelly a string is a list of 1-char Python strings, e.g. `['a', 'b', 'c']`. That's why you get output such as `[[['L'], ['L']], [['D'], ['D'], ['D']]]`, since 1-char Jelly strings behave the same.

Doesn't work as a full program, hence the `ÇŒṘ` at the bottom.

# Answer
> 1 votes
# Perse, 21 bytes

```
part(i,fn(x){x=="L"})

```

I may or may not have implemented the list partition function specifically for this challenge. Takes the input as an array of strings.

# Answer
> 1 votes
# Husk, 7 bytes

```
Mof-"DL

```

Try it online!

### Explanation

```
Mof-"DL
M   "DL    For each character in ['D','L']:
 of-         keep only those strings that are not empty if that character is removed

```

# Answer
> 1 votes
# Octave, 21 bytes

```
@(A){A(a=A>72),A(~a)}

```

Input is an array of characters, output is a cell array. Recycled from my answer here.

Sample execution on ideone.

# Answer
> 1 votes
# , 35 bytes

```
x=scan(,'');list(x[i<-x>'D'],x[!i])

```

Try it online!

Reads from stdin.

# Answer
> 1 votes
# Julia, 26 bytes

```
g(s)=s[s.=="L"],s[s.=="D"]

```

# Answer
> 1 votes
# Ruby, 20 bytes

```
->l{[l-[?D],l-[?L]]}

```

Try it online!

# Answer
> 1 votes
# Thunno 2, 8 bytes

```
`LDdẊcx×

```

Try it online!

#### Explanation

```
`LDdẊcx×  # Implicit input                   ->  ["L","D","L","D","D"]
`LD       # Push the string "LD"             ->  ["L","D","L","D","D"]  "LD"
   d      # Split it into characters         ->  ["L","D","L","D","D"]  ["L","D"]
    Ẋ     # Store it in x without popping    ->  ["L","D","L","D","D"]  ["L","D"]
     c    # Count occurrences in the input   ->  [2,3]
      x×  # Multiply by x elementwise        ->  [["L","L"],["D","D","D"]]
          # Implicit output

```

# Answer
> 0 votes
# Haskell (Lambdabot), 41 bytes

```
reverse.map tail.group.sort.("LD"++).join

```

Try it online!

# Answer
> 0 votes
# PowerShell, 27 bytes

```
($args-eq'L'),($args-eq'D')

```

Try it online!

---

Edit: previously `$args.where({$_-eq'L'},'sp')` for 28 bytes. Could be `$args.where({+"0x$_"},'sp')` for 27 if not for the rule that L's must come first.

# Answer
> 0 votes
# Retina, ~~21~~ 11 bytes

-10 bytes thanks to CalculatorFeline

```
O^`.
LD
L D

```

Try it online!

# Answer
> 0 votes
# CJam, 14 bytes

```
"LD"qf{1$e=*}`

```

Input is a list of characters (string), output is a list of lists of characters (list of strings).

Try it online!

Explanation:

```
"LD"  e# Push the string "LD"                  | "LD"
q     e# Push the input                        | "LD" "LDLLDLDDL"
f{    e# Foreach char in "LD", push input and: | ['L "LDLLDLDDL"
  1$  e#   Copy from 1 back                    | ['L "LDLLDLDDL" 'L
  e=  e#   Count occurences                    | ['L 5
  *   e#   Repeat character                    | ["LLLLL"
}     e# End                                   | ["LLLLL" "DDDD"]
`     e# Stringify:                            | "[\"LLLLL\" \"DDDD\"]"
e# Implicit output: ["LLLLL" "DDDD"]

```

# Answer
> 0 votes
# Perl 5, 70 bytes

```
$"='","';@L=(L)x y/L//;@D=(D)x y/D//;$_="[[\"@L\"],[\"@D\"]]";s/""//g

```

Try it online!

# Answer
> 0 votes
## Javascript, 38 bytes

```
q=>['L','D'].map(x=>q.filter(y=>x==y))

```

# Answer
> 0 votes
# , 13 bytes

```
<@-."1 0&'DL'

```

Try it online!

# Answer
> 0 votes
# Vyxal, 53 bitsv2, 6.625 bytes

```
‛LDƛ?Oẋf

```

Try it Online!

Ports Thonnu 2

## Explained

```
‛LDƛ?Oẋf
‛LDƛ      # To each character in the string "LD":
    ?O    #   Count the character in the input
      ẋ   #   And list repeat it that many times
       f  #   flatten that

```

Created with the help of Luminespire.

---
Tags: code-golf, array, sorting
---


title: Optimal Duck Game Moves

text:
# Question
Title: Optimal Duck Game Moves
## How to play the duck game

**This is a 2-player game.**

First, we start with a line of blue rubber ducks (represented here as circles):

> ```
>
>
> ```

Now, in each turn, the current player can turn either one blue duck or two adjacent blue ducks red.

So, a valid move would be indexes 2 and 3 (0-indexed):

> ```
>
>
> ```

Then, the other player could choose index 0:

> ```
>
>
> ```

And so on. The last player to move loses.

### Example game

Starting with 7 blue ducks:

> Initial board
>
> ```
>
>
> ```

> Player 1 chooses **3,4**
>
> ```
>
>
> ```

> Player 2 chooses **0**
>
> ```
>
>
> ```

> Player 1 chooses **6**
>
> ```
>
>
> ```

> Player 2 chooses **1,2**
>
> ```
>
>
> ```

> Player 1 chooses **5**
>
> ```
>
>
> ```

Player 1 was the last one to move, so Player 2 wins.

---

## Challenge

The duck game can be solved. Your challenge today is to accept a board state and output one of the moves which will guarantee a win for the current player.

For example, with the board state , choosing either index 0 or index 2 will guarantee a win for the current player (feel free to try it).

## Input/Output

* You should take in a list/array/etc. containing two distinct values representing blue and red ducks.
For example,  could be `[1, 1, 1, 0, 0, 1, 1]`.
* You should output one or two integers representing the ducks which should be taken in the next move.
For example, the input  could have output `[0]` or `[2]`.

## Clarifications

* The input board state will always have at least one move which guarantees a win for the current player.
* You may output **any** of the moves which guarantee a win.
* This is , so shortest solution in bytes wins.

## Test cases

These test cases use 1 for blue ducks and 0 for red ducks. The output side contains all possible outputs.

```
Input  ->  Output
[1, 1, 1, 0, 0, 1, 1]  ->  [0], [2]
[1, 1, 1, 1, 1, 1, 1]  ->  [1], [3], [5]
[1, 1, 0, 1, 1, 1, 1]  ->  [0,1], [3,4], [5,6]
[1, 0, 1, 1, 0, 1, 1]  ->  [0]
[1, 1, 1]  ->  [0,1], [1,2]
[1, 0, 0, 1, 1, 0, 0, 1]  ->  [3], [4]

```

# Answer
> 5 votes
# Charcoal, ~~71~~ 52 bytes

```
Ｆ⊕⍘⮌Ｓ²⊞υ⎇ιΦ⁺Ｅθ⟦λ⟧Ｅθ⟦λ⊕λ⟧∧⁼ΣＸ²κ＆ΣＸ²κι¬§υ⁻ιΣＸ²κ⟦⟦⟧⟧Ｉ⊟υ

```

Try it online! Link is to verbose version of code. Takes input as a string of `0`s and `1`s representing red and blue ducks respectively and outputs a double-spaced list of winning `0`-indexed duck moves. Explanation: Uses dynamic programming to find winning moves.

```
Ｆ⊕⍘⮌Ｓ²

```

Loop over numeric positions indices from `0` to the input as a position index, some of which will be unreachable from the input position.

```
⊞υ⎇ιΦ⁺Ｅθ⟦λ⟧Ｅθ⟦λ⊕λ⟧∧⁼ΣＸ²κ＆ΣＸ²κι¬§υ⁻ιΣＸ²κ⟦⟦⟧⟧

```

Find all legal moves that result in forced losses from this position, but special case a list of an empty list for position index `0` which should really be a loss for the player to move (this would save `6` bytes).

```
Ｉ⊟υ

```

Output all winning moves from the input position.

# Answer
> 4 votes
# Python3, 333 bytes:

```
def M(l):
 for i,a in enumerate(l):
  if a:
   yield[i]
   if i<len(l)-1and l[i+1]:yield[i,i+1]
def K(l):
 for m in M(l):
  L=l[:]
  for i in m:L[i]=0
  yield L,m
def P(l,p=1):
 F=1
 for L,_ in K(l):
  if any(L):
   if p in(u:=[*P(L,not p)]):yield from u;F=0
 if F:yield not p
f=lambda l:[m for L,m in K(l)if any(L)and not any(P(L))]

```

Try it online!

# Answer
> 3 votes
# JavaScript (V8), 78 bytes

-5 bytes from Arnauld

```
f=x=>x.some(r=(v,i,[...e])=>v?r=f(e,e[i]=0)?f(e,e[i-1]=0)?0:[i-1,i]:[i]:0)?r:r

```

Try it online!

# JavaScript (V8), 81 bytes

```
f=(x,e)=>x.some((v,i)=>r=v?f(e=[...x],e[i]=0)?f(e,e[i-1]=0)?0:[i-1,i]:[i]:0)?r:!e

```

Try it online!

returns `false` if impossible, returns `true` if win immediately because of endgame.

# Answer
> 1 votes
# Haskell, 178 bytes

```
z f=zipWith f[0..]
n=Nothing
f x|and x=Just[]
f x|h:_<-filter(\j->all(\k->k<length x&&not(x!!k))j&&n==f((\k->z(\i y->y||elem i k)x)j))$concat$z(\i _->[[i],[i,i+1]])x=Just h
f x=n

```

Attempt This Online!

---
Tags: code-golf, game
---