title: Get the length of a Sumac Sequence

text:
# Question
Title: Get the length of a Sumac Sequence
Heavily based on this closed challenge.

Codidact post, Sandbox

# Description

A Sumac sequence starts with two non-zero integers \\$t\_1\\$ and \\$t\_2.\\$

The next term, \\$t\_3 = t\_1 - t\_2\\$

More generally, \\$t\_n = t\_{n-2} - t\_{n-1}\\$

The sequence ends when \\$t\_n ≤ 0\\$. All values in the sequence must be positive.

# Challenge

Given two integers \\$t\_1\\$ and \\$t\_2\\$, compute the Sumac sequence, and output its length.

If there is a negative number in the input, remove everything after it, and compute the length.

You may take the input in any way (Array, two numbers, etc.)

# Test Cases

(Sequence is included for clarification)

```
[t1,t2]   Sequence          n
------------------------------
[120,71]  [120,71,49,22,27] 5
[101,42]  [101,42,59]       3
[500,499] [500,499,1,498]   4
[387,1]   [387,1,386]       3
[3,-128]  [3]               1
[-2,3]    []                0
[3,2]     [3,2,1,1]         4

```

# Scoring

This is . Shortest answer in each language wins.

# Answer
> 8 votes
## x86 machine code (8086), ~~15~~ 13 bytes

-2 bytes thanks to @EasyasPi.

```
00000000  31 C9 48 7C 07 40 41 29-D8 93 EB F6 C3            1.H|.@A).....

```

Callable function.

Expects `AX` = t1, `BX` = t2. Output is to `CX`.

Disassembly:

```
31C9          XOR     CX,CX    ; Set CX to 0
          LOP:
48            DEC     AX       ; --AX
7C07          JL      END      ; If AX < 0, jump to 'END'
40            INC     AX       ; ++AX
41            INC     CX       ; ++CX
29D8          SUB     AX,BX    ; AX -= BX
93            XCHG    BX,AX    ; Swap AX and BX
EBF6          JMP     LOP      ; Jump to tag 'LOP'
          END:
C3            RET              ; Return to caller

```

## Example run

Tested with DOS debug:

<pre><code>-r
AX=0078  BX=0047  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=0000   NV UP EI PL NZ NA PO NC
1000:0000 31C9          XOR     CX,CX
-t

AX=0078  BX=0047  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=0002   NV UP EI PL ZR NA PE NC
1000:0002 48            DEC     AX
...
-t

AX=FFFA  BX=0020  CX=0005  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=000C   NV UP EI NG NZ NA PE CY
1000:000C C3            RET
```
</code></pre>

# Answer
> 7 votes
# JavaScript (ES6), 24 bytes

```
f=(a,b)=>a>0&&1+f(b,a-b)

```

Try it online!

# Answer
> 7 votes
# convey, <sup>39</sup> 37 bytes

*-2 thanks to Jo King!*

```
{0(>>"!+?`}
,?"-v>^0^
^>>", 8~^
^<<<<

```

Try it online!

The Sumac Sequence gets calculated in the lower left part, with `{` taking the input and copying the sequence into `(` via `"` (copy):

```
{ (
,?"-v
^>>",
^<<<<

```

The sequence then gets converted to – is it greater than 0 `0(`? Taking `!` that by itself, only 1s gets passed through into `+`:

```
0(>>"!+
    >^

```

There the accumulator loops around, waiting 8 steps `8~` so both the generating loop and the accumulator loop have the same speed. If there is an input waiting for `+`, `?` pushes the accumulator into `+`, otherwise – if the sequence stopped thanks to a 0 – it gets pushed into the output `}`.

```
 +?}
 0^
8~^

```

Everything put together:

# Answer
> 6 votes
# 05AB1E, 7 bytes

```
λ-}(d1k

```

Try it online! or Try all cases!

**Commented**:

```
λ }      # start a recursive environment:
         #   this produces an infinite sequence starting with input
 -       #   and calculates t_n according to t_n = t_{n-2} - t_{n-1}
   (     # negate every value
    d    # for every value: is it non-negative?
     1k  # find the first index of a 1 (smallest n such that -t_n >= 0)

```

# Answer
> 5 votes
# Husk, ~~16~~ ~~13~~ ~~12~~ ~~11~~ 9 bytes

Saved ~~1~~ ~~2~~ 4 bytes thanks to Leo!

```
L↑>0ƒ·:G-

```

Try it online!

~~I wish it would parse the correct function without parentheses.~~ Leo found a 9-byte solution that doesn't use parentheses or even composition!

This my first time using `ƒ` (`fix` from Haskell).

I'm told `fix` looks something like this:

```
fix :: (a -> a) -> a
fix f = let x = f x in x

```

Supposing the first argument (`²`) is 120, and the second argument () is 71, `f` (`o:²G-⁰`) would be something like `prevSequence -> 120 : scanl (-) 71 prevSequence`. So the `x` from above would become

```
x = 120 : scanl (-) 71 x
x = 120 : 71 : scanl (-) (120 - 71) (drop 1 x) //where drop 1 x is 71 : scanl (-) ...
x = 120 : 71 : 49 : scanl (-) (71 - 49) (drop 2 x)
...

```

and so on until it makes an infinite sequence.

Then `↑>0` takes () while each element is positive, and `L` finds the length of that sequence.

# Answer
> 5 votes
# Husk, 10 bytes

```
L↑>0¡(→Ẋ`-

```

Try it online!

...still haven't managed to get Razetime's (*edit: non-existant*) 9-byte answer (unless zero-based indexing is Ok), but ~~I'm trying...~~ (*edit: I've now given-up*).
*(Edit 2: ...but a 9-byte answer has now been found by user & Leo!)*

**Commented code:**

```
L            # length of
 ↑>0         # initial elements that are greater than zero of
    ¡(       # infinite list by repeatedly appending list with
      →      # last element of
       Ẋ`-   # pairwise differences between elements of list so far

```

# Answer
> 5 votes
# sed -r 4.2.2, 44

* Thanks to @seshoumara for -2 bytes

```
:
s/^(1+) \1(1+)/\2 &/
t
s/1+ ?/1/g
s/.*-1//

```

Try it online!

### Explanation

The inputs are space-separated unary. Term 2 is given before term 1. E.g. (5, 3) would be `111 11111`; (5, -3) would be `-111 11111`.

* Line 1: loop label (unnamed - works in 4.2.2)
* Line 2: generate term n+2 by removing term n+1 from term n; Prefix term n+2 to the beginning of the pattern space
* Line 3: if the substitution on line 2 was successful, jump back to the loop label
* Line 4: Count the terms by replacing each term (followed by optional space) with 1
* Line 5: Handle negative inputs
* End of program: Implicit output of counter

# Answer
> 4 votes
# Charcoal, ~~33~~ 24 bytes

```
ＮθＮηＷ‹⁰θ«⊞υω≦⁻θη≧⁻ηθ»ＩＬυ

```

Try it online! Link is to verbose version of code. Edit: Saved 9 bytes when @Razetime pointed out I was using an inefficient algorithm. Explanation:

```
ＮθＮη

```

Input the initial values.

```
Ｗ‹⁰θ«

```

Repeat while the first value is positive.

```
⊞υω

```

Keep count of the number of iterations.

```
≦⁻θη

```

Subtract the second number from the first number, storing the result in the second number.

```
≧⁻ηθ

```

Subtract that result from the first number, resulting in the original second number.

```
»ＩＬυ

```

Finally print the number of iterations.

# Answer
> 4 votes
# Vyxal `2`, ~~20~~ ~~8~~ 7 bytes

```
⁽-Ḟ±ċTh

```

Try it Online!

Wow it's a been a while since I posted this, and a lot of things have been added/changed since.

## Explained

```
⁽-dḞ±ċTh
⁽-d       # lambda x, y: x - y
   Ḟ      # Using the input as an initial vector, apply the above lambda infinitely, using all previously generated items as its stack
    ±ċ    # Is the sign of each item not 1?
      Th  # First occurrence of 1

```

# Answer
> 4 votes
# Ruby, 25 bytes

```
f=->a,b{a>0?f[b,a-b]+1:0}

```

Attempt This Online!

# Answer
> 3 votes
# TI-BASIC, 27 Bytes

```
While A>0
A-B->B
A-B->A
N+1->N
End
N

```

Takes t1 and t2 as input in A and B. Nothing fancy, the key is that when A is updated, B is the previous t1-t2, so the third line is able to recover t2 via t1-(t1-t2)-\>A without juggling a 3rd variable. There's a way to generate the sequence in 27 bytes as well with input as a list in Ans and dim( calls, but it proves too complex to trim out negative input and retrieve the true length of the sequence.

# Answer
> 3 votes
# Raku, 20 bytes

*-4 bytes thanks to Jo King*

```
{+(|@_,*-*...^0>=*)}

```

Try it online!

The parenthesized expression is a list where the first terms are the two arguments to the function (`|@_`), successive terms are generated by subtracting the previous two terms (`* - *`), and the list stops just before the term (`...^`) for which zero is greater than or equal to it (`0 >= *`). Then the `+` operator converts that list to a number, its length.

# Answer
> 2 votes
# Retina 0.8.2, 31 bytes

```
\d+
$*
+`(1+)¶\1$
$&¶$%`
\G1+¶?

```

Try it online! Takes the integers on separate lines but link includes test suite that splits on comma for convenience. Explanation:

```
\d+
$*

```

Convert to unary. Note that the signs are ignored at this stage, so that if the first number is negative, the next stage uselessly computes the sequence as if it was positive.

```
+`(1+)¶\1$
$&¶$%`

```

Compute additional terms until the last number is zero or greater than the absolute value of the previous number.

```
\G1+¶?

```

Count the number of leading positive terms.

# Answer
> 2 votes
# C (gcc), 27 bytes

```
f(a,b){a=a>0?f(b,a-b)+1:0;}

```

This is the C equivalent of Arnauld's JavaScript answer

Try it online!

A and that's actually the work of att. My function was initially 28 bytes and non-reusable.

# Answer
> 2 votes
# Python 3, 29 bytes

```
f=lambda a,b:a>0and-~f(b,a-b)

```

Try it online!

# Answer
> 2 votes
# PowerShell, 46 bytes

```
param($a,$b)for(;$a-gt0;$i++){$a-=$b=$a-$b}+$i

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~141~~ 125 bytes

```
def F(I):
 i=1
 if I[0]<0:
  return 0
 if I[1]<0:
  return 1
 while I[i-1]-I[i]>0:
  I.append(I[i-1]-I[i])
  i+=1
 return i+1

```

Thanks to @Razetime for pointing out the sequence itself didn't need to be returned.

# Answer
> 2 votes
# Prolog (SWI), ~~102~~ 93 bytes

```
d(A,B,C):-B<1,write(C);E is C+1,F is A-B,d(B,F,E).
:-read(A),(A<0,write(0);read(B),d(A,B,1)).

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~42~~ 35 bytes

Saved 7 bytes thanks to Neil!!!

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

```

Try it online!

# Answer
> 1 votes
# MathGolf, 12 bytes

```
æ`‼->▲](mσb=

```

Takes the two inputs in reversed order.

Try it online.

**Explanation:**

```
     ▲        # Do-while true with pop,
æ             # using the following four commands:
 `            #  Duplicate the top two values on the stack
  ‼           #  Apply the following two commands separated on the current stack:
   -          #   Subtract the top two items from one another
    >         #   Check if the second top item is larger than the top item
      ]       # After the do-while, wrap everything on the stack into a list
       (      # Decrease each value by 1
        m     # Map over each value:
         σ    #  And take its sign: 1 if >0; 0 if ==0; -1 if <0
           =  # And then get the first 0-based index in this list of
          b   # value -1
              # (after which the entire stack joined together is output implicitly)

```

# Answer
> 1 votes
# , ~~43~~ 37 bytes

*Edit: -6 bytes after peeking at Arnauld's answer: please upvote that one!*

```
f=function(a,b)`if`(a>0,1+f(b,a-b),0)

```

Try it online!

# Answer
> 1 votes
## Batch, 65 bytes

```
@set/aa=%1-%2,b=%3+1,c=b-1
@if %1 gtr 0 %0 %2 %a% %b%
@echo %c%

```

`c` is provided so that the output is zero if the first parameter is negative, otherwise `@echo %3` would work. (On the first pass `%3` is the empty string, but `b=+1` still computes the correct value for `b`. `c=%3+0,b=c+1` would also work.)

# Answer
> 1 votes
# Jelly, 9 bytes

```
Rȧ_@RÐ¿@L

```

Try it online!

As posted on Codidact

Takes \\$t\_1\\$ on the left and \\$t\_2\\$ on the right. `R}ȧ_@RÐ¿L` works given the arguments in the opposite order.

```
R            Ascending range from 1 to t_1 (truthy if positive),
 ȧ           and:
     Ð¿      collecting intermediate results, loop while
    R        positive
       @     on the reversed arguments:
  _          subtract
   @         the first from the second.
        L    Return the length of the conjunction.

```

`¿` and family, given a dyad, replace the right argument with the previous left argument on each successive iteration. This is incredibly bothersome for some tasks, but perfect for working with this exact kind of sequence.

# Answer
> 0 votes
# PARI/GP, 25 bytes

```
f(a,b)=if(a>0,1+f(b,a-b))

```

Attempt This Online!

---
Tags: code-golf, number, sequence
---


# Question
Title: Produce n n-squares of integers with rotating *'s in consecuitive corners
The objective is to produce output of n squares (nxn) of random integers (`0-9`) with a moving `*` that rotates clockwise around the corners, starting from the top left. The squares should be side by side and separated by a single space.

If `n = 0`, the output should be empty.

Output for `n=1`:

`*`

Output for `n=2`:

```
*3 4*
14 07

```

Output for `n=3`:

```
*34 82* 291
453 224 924
145 158 57*

```

Output for `n=4`:

```
*153 135* 0154 0235
2352 5604 3602 2065
2245 6895 3561 7105
7225 5785 479* *662

```

Notice how, for each square, the `*` rotates around the corners of the square, from left to right, beginning in the top left corner of the first, then moving to the top right of the second, and so on.

The shortest answer (measured in bytes) wins.

# Answer
# 05AB1E, ~~50~~ 49 bytes

```
3mF9Ý.R}J¹ô¹ävy`¦'*ìN4%©>ir}®iRr}®<iR})ˆ}¯øvyðý}»

```

**Explanation**

Examples for input = 4.

First we create a string of input^3 random numbers between 0 and 9.

```
3mF9Ý.R}J

```

producing

```
6799762549425893341317984133999075245812305412010122884262903656

```

Then we split that into pieces each the size of the input.
That is further split into input pieces.

```
¹ô¹ä

```

This gives us a matrix of numbers.

```
[['6799', '7625', '4942', '5893'],
 ['3413', '1798', '4133', '9990'],
 ['7524', '5812', '3054', '1201'],
 ['0122', '8842', '6290', '3656']]

```

We then loop over the rows of the matrix, inserting asterisks in the right places.

```
v                          } # for each row in matrix
 y`                          # flatten list to stack
   ¦'*ì                      # replace the first digit of the last number with "*"
       N4%©>ir}              # if row-nr % 4 == 0, move the number with "*" to the front
               ®iRr}         # if row-nr % 4 == 1, move the number with "*" to the front
                             # and reverse the number, moving "*" to the numbers right side
                    ®<iR}    # if row-nr % 4 == 2, reverse the number, moving "*"
                             # to the numbers right side
                         )ˆ  # wrap row in a list and add to global array

```

Now we have the matrix with a "\*" on each row, but we want an asterisk per column.

```
[['*893', '4942', '7625', '6799'],
 ['099*', '4133', '1798', '3413'],
 ['7524', '5812', '3054', '102*'],
 ['0122', '8842', '6290', '*656']]

```

So we zip this list turning rows into columns and vice versa.

```
[['*893', '099*', '7524', '0122'],
 ['4942', '4133', '5812', '8842'],
 ['7625', '1798', '3054', '6290'],
 ['6799', '3413', '102*', '*656']]

```

All that's left now is to format the output.

```
vyðý}»

```

Joining the rows on spaces and the columns on newlines gives us the final result.

```
*893 099* 7524 0122
4942 4133 5812 8842
7625 1798 3054 6290
6799 3413 102* *656

```

Try it online!

**Old 50 byte solution**

```
F¹Fõ¹F9Ý.R«}}¦'*ì})¹ävyN4%©>iR}®iíÁ}®<ií}})øvyðý}»

```
> 4 votes

# Answer
# APL (Dyalog Unicode), 47 bytes

```
{⍉⎕FMT'*'@((⍳⍵),¨⍵⍴2⍴¨1(⍵1)⍵(1⍵))⊢⎕D[?10⍴⍨3⍴⍵]}

```

Try it online!

Anonymous prefix lambda.

`{``}` "dfn"; n is called

`⎕D[``]` index the list of digits with the indices:

`3⍴⍵` cyclically **r**eshape n into a list of length 3

`10⍴⍨` cyclically **r**eshape the number 10 into an array of those dimensions (3×n×n)

`?` random index (1…10) for each

yield that as argument to the upcoming function (separates indices from data)

`'*'@(``)` place asterisks **at** the following locations:

`1(⍵1)⍵(1⍵)` the list `[1,[n,1],n,[1,n]]`

`2⍴¨` cyclically reshape each into a list of length 2: `[[1,1],[n,1],[n,n],[1,n]]`

`⍵⍴` cyclically reshape that list into length n

`(``),¨` prepend an element to each, taking elements from this list:

`⍳⍵` indices 1…n

`⎕FMT` ForMaT as character matrix (joins layers with a line of spaces)

transpose
> 4 votes

# Answer
# Java 10, ~~370~~ ... ~~243~~ 242 bytes

```
n->{int j=n*n,k,m=1;var a=new String[j];var r="";for(m*=Math.pow(10,n-1);j-->0;a[j]=(k*=Math.random())+m+r)k=9*m;for(;++j<n;m=k<2?0:n*n-n,a[m+j]=a[m+j].replaceAll(k%3<1?"^.":".$","*"))k=j%4;for(j=0;j<n*n;r+=j%n<1?"\n":" ")r+=a[j++];return r;}

```

Returns the result-String with trailing newline.

-51 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
n->{                             // Method with integer parameter & String return-type
  int j=n*n,k,                   //  Index-integers
      m=1;                       //  Temp-integer
  var a=new String[j];           //  Create a String-matrix of size n by n
  var r="";                      //  Result-String, starting empty
  for(m*=Math.pow(10,n-1);       //  Start the temp-integer `m` at 10 to the power the
                                 //  input minus 1
      j-->0                      //  Loop `j` in the range [0,n²):
      ;                          //    After every iteration:
       a[j]=                     //     Set the j'th cell to:
         (k*=Math.random())      //      A random integer in the range [0,k)
         +m                      //      Add `m`
         +r;                     //      And then convert it to a String
    k=9*m;                       //   Set `k` to 9 multiplied by `m`, so the random
                                 //   integer will be in the range [0,9*m)
  for(;++j<n;                    //  Loop `j` in the range (-1,n):
      ;                          //    After every iteration:
       m=k<2?                    //     If `k` is 0 or 1:
             0                   //      Set `m` to 0 (first row)
            :                    //     Else:
             n*n-n,              //      Set `m` to n²-n instead (last row)
       a[m+j]=a[m+j].replaceAll( //     Then replace a digit in the (m*j)'th cell:
               k%3<1?            //      If `k` is 0 or 3 (first column):
                "^."             //       Replace its first digit
               :                 //      Else (last column instead):
                ".$",            //       Replace its last digit
               "*"))             //      And replace this digit with a "*"
    k=j%4;                       //   Set `k` to `j` modulo-4
  for(j=0;j<n*n;                 //  Loop `j` in the range [0,n²) again:
      ;                          //    After every iteration:
       r+=j%n<1?                 //     If `j` is divisible by `n`:
           "\n"                  //      Append a newline to the result
          :                      //     Else:
           " ";                  //      Append a space to the result instead
    r+=a[j++];                   //   Append the j'th value to the result
  return r;}                     //  Return the result-String

```
> 3 votes

# Answer
# PHP ,181 Bytes

```
for($i=-1;++$i<$c=($n=$argv[1])**3;){echo!($i%$q=$n*$n)?"\n":((!$m=$i%$n)?" ":"");echo(!$m&!($b=$i%$q/$n&3)|$m==$n-1&$b==1)&$i<$q|($m==$n-1&$b==2|!$m&$b==3)&$i>$c-$q?"*":rand(0,9);}

```
> 1 votes

# Answer
# Japt `-R`, ~~20~~ 19 bytes

I could save a byte by either filling each square with the same random digit but

```
Æ²ÆAöÃ¬h* òU zXÃÕm¸

```

Try it

## 18 bytes

By using the same random digit to fill each square. Dunno if that'd fit the definition of "pseudo-random" for this challenge, though.

```
Æ²çAö)h* òU zXÃÕm¸

```

Try it

```
Æ²ÆAöÃ¬h* òU zXÃÕm¸     :Implicit input of integer U
Æ                       :Map each X in the range [0,U)
 ²                      :  U squared
  Æ                     :  Map the range [0,U²)
   A                    :    10
    ö                   :    Random number in the range [0,A)
     Ã                  :  End map
      ¬                 :  Join
       h*               :  Replace 1st char with "*" (Handles the edge case of U=1 by instead inserting the "*" into the empty string)
          òU            :  Partitions of length U
             zX         :  Rotate 90 degrees clockwise X times
               Ã        :End map
                Õ       :Transpose
                 m      :Map
                  ¸     :  Join with spaces
                        :Implicit output, joined with newlines

```

```
Æ²çAö)h* òU zXÃÕm¸     :Implicit input of integer U
Æ²                     :As above
  ç                    :  Repeat to length U²
   Aö                  :   As above
     )                 :  End repeat
      h* òU zXÃÕm¸     :As above
                       :Implicit output, joined with newlines

```
> 1 votes

# Answer
# 05AB1E, 27 bytes

```
иLdć'*0ǝšIGDøí})øJ»εDižhΩ]J

```

Try it online or verify multiple dimensions.

**Explanation:**

Step 1: Create a matrix of the input by input amount of `1`s, with the top-left value replaced with a `"*"`:

```
и          # Repeat the (implicit) input the (implicit) input amount of times as list
           # (e.g. 5 → [5,5,5,5,5])
 L         # Convert each inner integer to a list in the range [1,input]
  d        # Convert each inner integer to a 1 (with a >=0 check)
   ć       # Extract head; pop and push remainder-list and first item separated
    '*0ǝ  '# Replace the first item in this list with a "*"
        š  # Prepend this list back to the matrix

```

Try just step 1 online.

Step 2: Rotate it the input-1 amount of times clockwise and keep each intermediate matrix in a list:

```
IG         # Loop the input-1 amount of times:
  D        #  Duplicate the current matrix
   øí      #  Rotate it once clockwise:
   ø       #   Zip/transpose; swapping rows/columns
    í      #   Reverse each inner row
 })        # After the loop: wrap all matrices on the stack into a list

```

Try just the first 2 steps online.

Step 3: Format these lists of loose matrices to the output-format by putting them next to each other with space delimiter:

```
ø          # Zip/transpose; swapping rows/columns
 J         # Join each inner-most list together to a string
  »        # Join each inner lists by spaces, and then these lines by newlines

```

Try just the first 3 steps online.

Step 4: Replace every 1 with a random digit, and output the final result:

```
ε          # Map over each character in the multi-line string:
 D         #  Duplicate the current character
  i        #  Pop, and if it's a 1:
   žh      #   Push constant "0123456789"
     Ω     #   Pop and push a random digit from this
]          # Close both the if-statement and map
 J         # Join this list of characters back to a string again

```
> 0 votes

---
Tags: code-golf, number, random
---


title: Polyglot Quiz (Cops' thread)

text:
# Question
Title: Polyglot Quiz (Cops' thread)
*This is the cops' thread of a challenge. The robbers' thread can be found here*

In this challenge as a cop you will choose two programming languages **A** and **B**, as well as a non-empty string **S**. You are then going to write 4 programs:

1. A program which outputs exactly **S** when run in both **A** and **B**.
2. A program which outputs **S** in **A** but not in **B**.
3. A program which outputs **S** in **B** but not in **A**.
4. A program which doesn't output **S** in either **A** or **B**.

You will then reveal all 4 programs (including which number each program is) and **S**, but keep the languages hidden.

Robbers will try to figure out a pair of languages such that they print the correct results for the 4 programs, and cops will try to make posts that are hard to figure out while remaining as short as possible.

**Warning: There is a slight difference in the rules from "normal"**

Cops' posts here can have 4 different states:

1. Vulnerable
2. Cracked
3. Safe
4. Revealed

All cops' posts start as *vulnerable*. If a robber finds and posts a solution to a *vulnerable* post they will receive 1 point and the post will become *cracked*. If a post lasts 10 days in *vulnerable* without being solved it automatically becomes *safe*. A cop with a *safe* post may choose to reveal **A** and **B** and their *safe* post will become *revealed*. A robber can still solve a *safe* post, if they do they receive a point and the post becomes *revealed*.

Only *revealed* posts are eligible for scoring. Robbers are only permitted to solve *vulnerable* and *safe* posts.

## Scoring

Cops will be scored on the sum size of all four programs as measured in bytes, with the goal being to have an answer with as low a score as possible. Answers that are not *revealed* effectively have infinite score by this measure until they become *revealed*.

## Languages and Output

In the interest of fairness, we are going to require that languages are free and reasonably cross platform. Both languages you choose must be freely available on Linux and FreeBSD (the two largest foss operating systems). This includes languages which are free and open source.

Your selected languages must predate this challenge.

Since this challenge requires that **A** and **B** produce different outputs for the same program, there is no requirement for what "counts" as a different language, the fact that they produce different outputs is enough.

Programs do not have to compile, run without error or "work" in the cases where they do not need to output **S**. As long as **S** is not the output it is valid.

Programs here should be complete programs not functions, expressions or snippets.

Running a program is assumed to be done with no input. All four programs must be deterministic, within an environment. It is fine for example if as a part of an error the program outputs the name of the file or your host name, this is not considered non-determinism since it is determined by the environment running the program. However if it is included in the output please indicate what the file is named etc.

# Answer
# A = HQ9+, B = Python 3, 291 bytes, Cracked

**S** is `Hello, world!`

1. Both **A** and **B** work

```
#console.log("Hello, world!")/*
print("hello, world!".capitalize())
#*/

```
2. **A** only

```
console.log("Hello, world!")/*
print("hello, world!")
*/

```
3. **B** only

```
#console.log("Hello, world!")/*
print("Hello, world!")
#*/

```
4. Neither work

```
console.log(String.fromCharCode(49-1)+"ello, world!")/*
print(String.fromCharCode(49-1)+"ello, world!")
*/

```

GG
> 8 votes

# Answer
# \[A\] and \[B\], 64 Bytes, Cracked by @Steffan

S = "Cop"

Both *A* and *B* works

```
main=print"Cop"

```

Works only *A*

```
main=print
 "Cop"

```

Works only *B*

```
main=
print"Cop"

```

None works

```
main=print
"Cop"

```
> 6 votes

# Answer
# 05AB1E and yup, 8 bytes, Cracked by *@FryAmTheEggman*

\\$S\\$: `0`

1. Works in \\$A\\$=05AB1E and \\$B\\$=yup:

```
0#?

```

2. Works in just \\$A\\$=05AB1E:

```
0?

```

3. Works in just \\$B\\$=yup:

```
0#

```

4. Works in neither \\$A\\$=05AB1E nor \\$B\\$=yup:

```
0

```

---

**Explanation now that it's cracked:**

```
0#?    # 05AB1E: Push 0; pop and split on spaces (no-op that just pops); print
       # without newline, which implicitly uses the last value that was on the now
       # empty stack, which is the 0
       # yup: Push 0; pop and print it without newline; no-op character '?'

0?     # 05AB1E: Push 0; pop and print it without newline
       # yup: Push 0; no-op character '?', so don't print anything

0#     # 05AB1E: Push 0; no-op pop; implicitly output 0 with trailing newline
       # yup: Push 0; pop and print it without newline

0      # 05AB1E: Push 0; implicitly output 0 with trailing newline
       # yup: Push 0; don't print anything

```
> 5 votes

# Answer
# Hexagony and Labyrinth, 44 bytes, Cracked by Aiden Chow

**S** = `1234`

1. Works in both A and B

```
"123_1234!@

```
2. Works in A, but not in B

```
123+1
234!@

```
3. Works in B, but not A

```
1234@
;!;!;

```
4. Does not work in A or B

```
;!;!;
1234@

```
> 4 votes

# Answer
# ??? and ???, 69 bytes, vulnerable

S = `A`

1. Both A and B work:

```
:-%~! v
put(97)
.% >`a

```
2. Works in A, but not B:

```
:-%~v!
put(a)
.% >97

```
3. Works in B, but not A:

```
:-%~!<
put a.
.%^97C

```
4. Works in neither A or B:

```
put(97)

```
> 4 votes

# Answer
# Glypho and Somme, 747 bytes, revealed

## Explanation

For this approach, I thought it would make sense to choose two languages which cared very little about the actual content of their source codes, and instead cared about some properties the code has.

Glypho is a language who cares about the distinct permutations formed by chunks of 4 bytes. It has 15 commands, and is a stack-based language. For example, the string `UU{u` corresponds to the `push` command, since it is equivalent to `aabc` (in terms of uniqueness).

Somme is a language which is usually a fairly innocuous stack-based language, but once multiple lines are involved, the columns are summed and converted into a corresponding command. (Addition is performed by treating space, 32, as 0, `!` as 1, etc., then taking the result mod 95.)

Hence, the programs consist almost entirely of red herrings.

Recall that

**S** = `owo!owo!owo!owo!owo!owo!owo!owo!`

a string chosen because I thought it was funny.

## Both **Glypho** and **Somme** work:

```
UU{uOOwo!??!oOoOowwoSRSR<ww<W!WOOOw0oWoW>ww>!
!
owwo!0!0
!!
QwQwOwOw!?!?.,.,owwo@?@?<ww<W!W!OwOwoWWo>ww>!

!owwo!!0w
!W
QwwQOwOw!???oOoOoow
@?@?<ww<W!W!OwwOoWoW>ww>!

!owww!000

!WQwqQOwwO!?!?ooO!owow@??@<w><W!!WOww0ooW!>w>w!

!owOo!00!
SSSQQwqOwoO!??!oO!O>!>?
#A` C=Z6fyC[U`SSmT5@)m`>3] =^OE^;"owO!"*4/qK_(_

```

This corresponds to the Glypho (shorthand) program (`[eeeeeeeeeee]` is a loop that never runs):

```
11+d+d+[1d+d+d+dddd+d+dd++++1-+dod1d+d+d++oo1-+d1d+-+*1d+-+o1-+][eeeeeeeeeee]
11+                                                                 stack: 2
   d+d+                                                             stack: 8 (loop counter)
       [                                                    1-+]    loop 8 times
        1d+d+d+                                                     stack: LC, 8
               dddd                                                 stack: LC, 8, 8, 8, 8, 8
                   +d+dd++++                                        stack: LC, 8, 112
                            1-+                                     stack: LC, 8, 111
                               do                                   output and keep 'o'
                                 d1d+d+d++                          stack: LC, 8, 111, 119
                                          oo                        output 'wo'
                                            1-+                     stack: LC, 7
                                               d1d+-+*              stack: LC, 35
                                                      1d+-+         stack: LC, 33
                                                           o        output '!'
                                                            1-+     stack: LC-1

```

In Somme, this corresponds to the following program after the columns are summed:

```
F1+7*1-::8+\3B*m,m,m,m,m,m,m,m,0;!fw'@9AH     `
F                                                   stack: 15
 1+                                                 stack: 16
   7*1-                                             stack: 111
       ::                                           stack: 111, 111, 111
         8+\                                        stack: 111, 119, 111
            3B*                                     stack: 111, 119, 111, 33
               m,                                   map output (,) over stack
                 m,m,m,m,m,m,m,                     ...eight times in total
                               0;                   exit with exit code 0
                                 !fw'@9AH     `     (never executed)

```

## Only **Glypho** works:

```
[[4]?!?!?00?OwOw
o
oo  owoo
0 0o]]4[00wO<!!<w#w#?##?owow[44[?!?!?0?0OwwO

oooo 0wo
w0  0]44[00wO<!?<w##w?#?#owow[8[8?!!!??0wOwOw
oo
o o woow0 0 ]44]0ww0<!!!w###??#wowow[ww[?!?!?00wOwOw
##>o o woow00 o]44]0www<!??ww#""#w"owwo"4*4/q]]]]]]

```

This corresponds to the following Glypho (shorthand) program:

```
1d+dd+*[11+d+d+dd+\1-+*1-+dddo1d+d+d++oo1d+d*d*d+1+o!1-+]!n
1d+dd+*                                                       stack: 8
       [                                             1-+]     loop 8 times
        11+d+d+dd+                                            stack: LC, 8, 16
                  \1-+*1-+dd                                  stack: LC, 8, 111, 111, 111
                            do                                output and keep 'o'
                              1d+d+d++                        stack: LC, 8, 111, 111, 119
                                      oo                      output 'wo'
                                        1d+d*d*d+1+           stack: LC, 8, 111, 33
                                                   o          output '!'
                                                    !         discard 111
                                                     1-+      stack: LC-1
                                                         !n   discard; no-op

```

And also to the (gibberish) Somme program:

```
u>B-t$?@+@@v)IUnX'PFK;~{k**bj2Q1J02is?F}zRC/)mmU-U-w

```

This errors out immediately because `u` is not a command that exists.

## Only **Somme** works:

```
if print("owO") then: #V
  print("Owo")
end
#e0;*~E>dbqAMz}+Gra=y:Pie
between each output call, do:
  print("!")     n[\@6l{: 0
end
repeat twice
X[*g20@"kW({4L-rSk$w.4})~*;Ke

```

This corresponds to the following Somme program:

```
F1+7*1-::8+\3B*r`,{`FF+2+*0;
F1+7*1-::8+\3B*                 same as previous
               r                reverse stack
                `,{`            push this string
                    FF+2+       push 32
                         *      execute that string 32 times
                                (once for each character)
                          0;    exit with exit code 0

```

And to the (gibberish) Glypho (shorthand) program:

```
eeeeee*eeeeeeeeee-!ee-e1e1e[neeee]]eeeeeeee

```

This errors out immediately due to `e` (execute) having no parameters.

## Neither **\[A\]** nor **\[B\]** work:

Didn't need to spend too much time here, since the answer was probably fine without it.

```
print("owo!"*8)
#&7("owo!"-1)

```

Thanks for reading!
> 4 votes

# Answer
# Python and PARI/GP, 48 bytes, Cracked by @Steffan

An easy one.

**S** is `Cop`

1. Both **A** and **B** work

```
print("Cop")

```
2. **A** only

```
print('Cop')

```
3. **B** only

```
print('Cop)'

```
4. Neither work

```
print("Cop)"

```
> 3 votes

# Answer
# \[A\] and \[B\], 46 bytes, Cracked by @mousetail

**S** is `0`

1. Both **A** and **B**, 14 bytes

```
print('0')
out

```
2. **A** but not **B**, 15 bytes

```
print('0')
out#

```
3. **B** but not **A**, 17 bytes

```
print('0',)
out #

```
4. Neither **B** nor **A**, 0 bytes

Yeah, I'm not wasting any bytes here `:-)`
> 3 votes

# Answer
# ??? and ???, 54 bytes

String: `8356830650`

Works in A and B (hex):

```
00000000: 300b 3366 b87e 0b00 247e e239 2a83 2a3b  0.3f.~..$~.9*.*;
00000010: 0fd6 30                                  ..0

```

Works in A (hex):

```
00000000: a4ac b3bb 762b 3a74 d6                   ....v+:t.

```

Works in B (hex):

```
00000000: 300b 01f9 3033 1f0b 3131 5ee2 8891 5ebb  0...03..11^...^.
00000010: 2d88 7661 8976 0bce 0000 0b2b            -.va.v.....+

```

Works in neither:

```
We're no strangers to love
You know the rules and so do I (do I)
A full commitment's what I'm thinking of
You wouldn't get this from any other guy

I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

We've known each other for so long
Your heart's been aching, but you're too shy to say it (say it)
Inside, we both know what's been going on (going on)
We know the game and we're gonna play it

And if you ask me how I'm feeling
Don't tell me you're too blind to see

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

(Ooh, give you up)
(Ooh, give you up)
(Ooh) Never gonna give, never gonna give (give you up)
(Ooh) Never gonna give, never gonna give (give you up)

We've known each other for so long
Your heart's been aching, but you're too shy to say it (to say it)
Inside, we both know what's been going on (going on)
We know the game and we're gonna play it

I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

```

Or the empty program.
> 3 votes

# Answer
# \[A\] and \[B\], ACTUALLY 3 BYTES!!!, Cracked

**S** is `0`

* Both, 0 bytes:

* Only **A**, 1 byte:

```
!

```
* Only **B**, 1 byte:

```
r

```
* Neither, 1 byte:

```
"

```
> 3 votes

# Answer
# ??? and ???, 300 bytes

S = `A\n` (as in, `A` with a trailing newline)

1. Works in *A* and *B*

```
puts A

n = A[ exit ]
n = 8
m = n - 1
p = m - n
n = 3 * 10
p /= 2
t = p * p

```
2. Works in *A* but not *B*

```
puts 'A'

n = A[ exit ]
n = 8
m = n - 1
p = m - n
n = 3 * 10
p /= 2
t = p * p

```
3. Works in *B* but not *A*.

```
puts A

n = A[exit]
n = 8
m = n - 1
p = m - n
n = 3 * 10
p /= 2
t = p * p

```
4. Works in neither *A* nor *B*

```
n = A[ exit ]

puts A
n = 8
m = n - 1
p = m - n
n = 3 * 10
p /= 2
t = p * p

```
> 3 votes

# Answer
# Lightlang and PDAsephone, 141 bytes, revealed

## Explanation

My thought process for this approach was to choose two obscure esolangs with interpreters not on TIO. Since there are no interpreters online available, I recommend you download `lightlang.py` and `PDASephone.java`.

My strategy with this one was further devious. If you were hurriedly scanning through esolangs, and found this language, the program will not complete immediately. The `_` command in Lightlang sleeps for one second, meaning the program takes about 13 seconds to complete.

Lightlang is a curious language which only has 1 bit of memory, whose implementation clocks in at 35 sloc. My solutions use the "interesting" parts of the language, bouncing, jumping, and conditional skipping, to produce varied output. The program otherwise is just a garden path through toggling a bit on and off and printing it occasionally.

PDAsephone is a language with a PDA (push-down automaton) datatype. Unfortunately, I didn't want to spend bytes (or mental energy) getting a non-trivial PDA functional in the language, especially when the other language is so simple that it would be hard to replicate any meaningfully complex behavior implemented in PDAsephone. Hence, I use it just for its stack-based capabilities, and most of the work done is to make it play nice with Lightlang.

**S** = `0110100`

Both **Lightlang** and **PDAsephone** work:

```
__@;"1_&^"0^!^!.$$:.__/!^#&!^&$$:."0:v..^:..___

```

Only **Lightlang** works:

```
[*)`!$]^|>,=+!+/#(]+|!!-+)$'%)}|^!]>*].==`^{;"|

```

Only **PDAsephone** works:

```
'**"0-'})'"1=/:+?.`/:~'{++:.>.'+*/(:./:-./::'..

```

Neither **Lightlang** nor **PDAsephone** work: (the empty program)

Thanks for reading!
> 3 votes

# Answer
# ??? and ???, 43 bytes, safe

output: `2147483647`

|  |  |
| --- | --- |
| both | `-print /*"\r"%S #*/|2**31-1` |
| only A | `-print %S` |
| only B | `2**31-1` |
| neither |  |

hint:
none of the languages are esoteric or recreational, both are practical and one of them is even quite popular, the other one is free open source but not available on any service like TIO, it's a script for a domain-specific tool
> 3 votes

# Answer
# ??? and ???, 406 bytes, cracked by Conor O'Brian

S=`2`

Both A and B:

```
# print("22222222222") //
!\print("22222222222")# 2
\\     ("11111111111")<<n
;;;;;;;;;;;;;;;;;;;;;;;;;

```

## A but not B:

```
# print("11111111110") //
!\print("11111111110")# 2
\\     ("11111111110")<<n
;;;;;;;;;;;;;;;;;;;;;;;;;

```

## B but not A:

```
print("22222222222") //
!\print("22222222222")# 2
\\     ("11111111111")<<n
;;;;;;;;;;;;;;;;;;;;;;;;;

```

## Neither A nor B:

```
# print("11111111111") //
!\print("11111111111")# 1
\\\    ("11111111111")>>n
;;;;;;;;;;;;;;;;;;;;;;;;;

```
> 2 votes

# Answer
# Pyth and V, 11 bytes, Cracked by @Steffan

S = `3`

Both:

```
l"aa3

```

Only A:

```
3

```

Only B:

```
dl3P1é3

```

None: (empty)
> 1 votes

---
Tags: code-golf, cops-and-robbers, polyglot
---


title: 5 Seconds to Find Pie

text:
# Question
Title: 5 Seconds to Find Pie
Pi times  (or Pie if you like ambiguous notation) to 100 decimal places is:

```
8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...

```

(OIES A019609) (argument for possible irrationality)

Your task is to write a program that takes in a positive integer N, and outputs Pi\*e truncated to N decimal places. e.g. if N = 2, then the output should be `8.53`.

This is an optimization problem, so the submission that can give the correct output for the highest value of N will win.

To ensure all submissions are judged using the same computing power, **your code must be run on ideone**, using any language they support. According to the ideone faq, there is a 5 second run time limit for not logged in users. This 5 second limit is the one you must use, **not** the 15 second limit for logged in users. (See faq for other limits like memory, code size, etc.)

Specifically, anyone not logged into ideone should be able to run your program on ideone for all values of N from 1 to some maximum Nmax, and see correct output *nearly all of the time*. without any `Time limit exceeded` or `Memory limit exceeded`, etc. errors. The submission with the largest Nmax wins.

(Whether the actual time taken is a smidge over 5 seconds doesn't matter as long as ideone doesn't give errors. "*Nearly all of the time*" is defined as more than 95% of the time for any particular N.)

# Details

* You may use any mathematical method you like to calculate Pi*e, \**but you may not hardcode the output beyond the first dozen digits of Pi, e or Pi*e\**.
    + Your program should be able to work for any N, given unlimited resources.
    + You may use built in Pi or e constants if your language happens to have them.
* You may not access websites or resources external to your code (if ideone even allows this).
* Beyond hardcoding and accessing external resources, anything that ideone allows is almost certainly fine.
* Your input and output must (obviously) work with whatever ideone provides for i/o (stdin/stdout only it seems). It's fine if you need quotes around the input N or the output is something like `ans = ...`, etc.
* Please include a link to an ideone snippet of your code with your Nmax as input.
* If there happens to be a tie (only likely if multiple submissions hit the 64kB output character limit) the highest votes answer wins.

# Answer
## Python - 65535

http://ideone.com/knKRhn

```
from math import exp, log

def divnr(p, q):
  """
    Integer division p/q using Newton-Raphson Division.
    Assumes p > q > 0.
  """

  sp = p.bit_length()-1
  sq = q.bit_length()-1
  sr = sp - sq + 1

  s = []
  t = sr
  while t > 15:
    s = [t] + s
    t = (t>>1) + 1
  # Base-case division
  r = (1 << (t<<1)) / (q >> sq-t)

  for u in s:
    r = (r << u-t+1) - (r*r * (q >> sq-u) >> (t<<1))
    t = u
  return (r * (p >> sq)) >> sr

def pibs(a, b):
  if a == b:
    if a == 0:
      return (1, 1, 1123)
    p = a*(a*(32*a-48)+22)-3
    q = a*a*a*24893568
    t = 21460*a+1123
    return (p, -q, p*t)
  m = (a+b) >> 1
  p1, q1, t1 = pibs(a, m)
  p2, q2, t2 = pibs(m+1, b)
  return (p1*p2, q1*q2, q2*t1 + p1*t2)

def ebs(a, b):
  if a == b:
    if a == 0:
      return (1, 1)
    return (1, a)
  m = (a+b) >> 1
  p1, q1 = ebs(a, m)
  p2, q2 = ebs(m+1, b)
  return (p1*q2+p2, q1*q2)

if __name__ == '__main__':
  n = input()

  pi_terms = int(n*0.16975227728583067)

  # 10^n == e^p
  p = n*2.3025850929940457

  # Lambert W_0(p/e) a la Newton
  k = log(p) - 1
  w = k - (k-1)/(k+1)
  while k > w:
    k = w
    w -= (k - p*exp(-k-1))/(k+1)

  # InverseGamma(e^p) approximation
  e_terms = int(p / w)

  pp, pq, pt = pibs(0, pi_terms)
  ep, eq = ebs(0, e_terms)

  z = 10**n
  p = 3528*z*ep*abs(pq)
  q = eq*abs(pt)

  pie = divnr(p, q)
  print pie,

```

---

Ideone doesn't seem to have `gmpy2` installed, which is unfortunate for at least two reasons. One, because it would make the calcuation a lot faster, and two, because it makes any formula requiring an arbitrary precision square root impractical.

The formula I use for *π* was listed by Ramanujan as Formula (39):

which converges at the rate of *~5.89* digits per term. To my knowledge, this is the fastest converging series of its kind that doesn't require the evaluation of an arbitrary precision square root. Formula (44) in the same paper (convergence rate *~7.98* digits per term) is most often referred to as *the* Ramanujan Formula.

The formula I use for *e* is the sum of inverse factorials. The number of terms required is calculated as Γ-1(*10n*), using an approximation I found on mathoverflow. The Lambert W0 component is found using Newton's Method.

The calculation of each of these summations is done via the Fast E-function Evalution (more generally known as binary-splitting), originally devised by Karatsuba. The method reduces a summation to *n* terms to a single rational value *p/q*. These two values are then multiplied to produce the final result.

**Update:**
Profiling revealed that over half of the time needed for the calculation was spent in the final division. Only the upper most *log2(10n)* bits of *q* are needed to obtain full precision, so I trim a few off beforehand. The code now fills the Ideone output buffer in *3.33s*.

**Update 2:**
Since this is an challenge, I decided to write my own division routine to combat CPython's slowness. The implementation of `divnr` above uses Newton-Raphson Division. The general idea is to calculate *d = 1/q · 2n* using Newton's Method, where *n* is the number of bits the result requires, and compute the result as *p · d \>\> n*. Runtime is now *2.87s* \- and this is without even chopping off bits before the calculation; it's unnecessary for this method.
> 14 votes

# Answer
## PARI/GP : 33000

This is basically the program given at OEIS, modified to take input and format output correctly. It should serve as a baseline to beat, if nothing else.

I *assume* this is accurate. I checked it at 100 and 20k against OEIS, and it matched for both. It's quite hard to find further digits online to check against.

For 33,000 it takes about 4.5s, so it could probably be bumped a small bit. I just got tired of fiddling with the input and ideone's slow-ass submit/compile/run loop.

```
{
    m=eval(input());
    default(realprecision, m+80);
    x=Pi*exp(1);
    s="8.";
    d=floor(x);
    x=(x-d)*10;
    for (n=1, m, d=floor(x);
         x=(x-d)*10;
         s=Str(s,d));
    print(s);
}

```

Ideone.com link
> 4 votes

# Answer
# Python 3

Since the built in pi and e don't have enough digits, I decided to calculate my own.

```
import decimal
import math
decimal.getcontext().prec=1000000
decimal=decimal.Decimal;b=2500
print(str(sum([decimal(1/math.factorial(x)) for x in range(b)])*sum([decimal(1/16**i*(4/(8*i+1)-2/(8*i+4)-1/(8*i+5)-1/(8*i+6))) for i in range(b)]))[0:int(input())+2])

```

IDEOne link

### Output for STDIN = 1000:

```
8.5397342226735669504281233688422467204743749305568824722710929852470173635361001388261308713809518841081669216573834376992066672804294594807026609638293539437286935503772101801433821053915371716284188665787967232464763808892618434263301810056154560438283877633957941572944822034479453916753507796910068912594560500836608215235605783723340714760960119319145912948480279651779184356994356172418603464628747082162475871780202868607325544781551065680583616058471475977367814338295574582450942453416002008665325253385672668994300796223139976640645190237481531851902147391807396201201799703915343423499008135819239684881566321559967077443367982975103648727755579256820566722752546407521965713336095320920822985129589997143740696972018563360331663471959214120971348584257396673542429063767170337770469161945592685537660073097456725716654388703941509676413429681372333615691533682226329180996924321063261666235129175134250645330301407536588271020457172050227357541822742441070313522061438812060477519238440079

```
> 2 votes

# Answer
# Scala - 1790

IDEOne at http://ideone.com/A2CIto.

We use Wetherfield's formula for π (and Machin-formula code crudely ported from here). We calculate e using the ordinary power series.

```
object Main extends App {
  import java.math.{BigDecimal => JDecimal}
  import java.math.RoundingMode._
  import scala.concurrent.Future
  import scala.concurrent.Await
  import scala.concurrent.ExecutionContext.Implicits._
  import scala.concurrent.duration._
  val precision = 1800

  def acotPrecision(numDigits: Int)(x: BigDecimal) = {
    val x1 = x.underlying
    val two = JDecimal.valueOf(2)
    val xSquared = x1 pow 2
    val unity = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    var sum = unity.divide(x1, HALF_EVEN)
    var xpower = new JDecimal(sum.toString)
    var term = unity

    var add = false

    var n = JDecimal.valueOf(3).setScale(numDigits)
    while (term.setScale(numDigits, HALF_EVEN).compareTo(JDecimal.ZERO) != 0) {
      xpower = xpower.divide(xSquared, HALF_EVEN)
      term = xpower.divide(n, HALF_EVEN)
      sum = if (add) sum add term else sum subtract term
      add = !add
      n = n add two
    }
    sum
  }

  def ePrecision(numDigits: Int) = {
    val zero = JDecimal.ZERO
    var sum = zero
    var term = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    var n = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    while(term.setScale(numDigits, HALF_EVEN).compareTo(zero) != 0) {
      sum = sum add term
      term = term.divide(n, HALF_EVEN)
      n = n add JDecimal.ONE
    }
    sum
  }

  val acot = acotPrecision(precision) _

  def d(x: Int) = JDecimal.valueOf(x)

  def piFuture = Future(d(4) multiply (
    (d(83) multiply acot(107)) add (d(17) multiply acot(1710)) subtract (d(22) multiply acot(103697))
    subtract (d(24) multiply acot(2513489)) subtract (d(44) multiply acot(18280007883L))
   add (d(12) multiply acot(7939642926390344818L))
   add (d(22) multiply acot(BigDecimal("3054211727257704725384731479018")))
  ))

  def eFuture = Future(ePrecision(precision))

  Await.result(
    for (pi <- piFuture;
         e <- eFuture) yield println((pi multiply e).setScale(precision - 10, DOWN))
  , 5 seconds)
}

```
> 2 votes

# Answer
# Java, 15,053

```
interface M{
  static void main(String[]a){
    int n=new Integer(new java.util.Scanner(System.in).nextInt()),i=1,x=n/100+9;
    var t=java.math.BigInteger.TEN.pow(n+=x).shiftLeft(1);
    var p=t;
    var s=t.TEN.pow(n-x);
    var e=s;
    for(;i<5e4;
      e=s.add(e.divide(s.valueOf(50001-i))))
      p=p.add(t=t.multiply(t.valueOf(i)).divide(t.valueOf(i+++i)));
    System.out.print((""+p.multiply(e)).substring(0,n-x));
  }
}

```

Outputs the digits without decimal dot after the leading `8`.

Try it on ideone.

Increasing the `5e4`/`50001` will both increase the run-time and digit-accuracy. With 50,000 iterations, which runs in ~4-5 seconds usually, \\$15\text{,}053\\$ is the largest amount of digits we can reach with 100% accuracy. With an input of \\$15\text{,}054\\$, the last couple digits will be incorrect.

Uses a combination of my Java answer for the *Calculate 500 digits of pi* challenge and a port of this stackoverflow C# .NET answer with BigIntegers.
> 0 votes

---
Tags: code-challenge, optimization, pi
---


title: Sᴍᴀʟʟ Cᴀᴘꜱ Cᴏɴᴠᴇʀᴛᴇʀ

text:
# Question
Title: Sᴍᴀʟʟ Cᴀᴘꜱ Cᴏɴᴠᴇʀᴛᴇʀ
Portable Spec.

*Iɴꜱᴘɪʀᴇᴅ ʙʏ @ConorO'Brien's ᴜꜱᴇʀɴᴀᴍᴇ.*

*Aʟꜱᴏ ᴛʜᴀɴᴋꜱ ᴛᴏ @Dᴏᴏʀᴋɴᴏʙ ꜰᴏʀ ꜱʜᴏᴡɪɴɢ ᴍᴇ ᴛʜᴇ ᴇxɪꜱᴛᴇɴᴄᴇ ᴏꜰ `ǫ` ᴀɴᴅ `x`.*

Sᴍᴀʟʟ Cᴀᴘꜱ ᴀʀᴇ ᴘʀᴇᴛᴛʏ ᴄᴏᴏʟ. Tʜᴇʏ ᴀʀᴇ ᴜɴɪᴄᴏᴅᴇ ᴄʜᴀʀᴀᴄᴛᴇʀꜱ ᴛʜᴀᴛ ʀᴇᴘʟᴀᴄᴇ ꜱᴍᴀʟʟ ʟᴇᴛᴛᴇʀꜱ. Tʜᴇʏ ʟᴏᴏᴋ ᴊᴜꜱᴛ ʟɪᴋᴇ ᴛʜᴇ ᴄᴀᴘɪᴛᴀʟ ᴏɴᴇꜱ, ʙᴜᴛ ꜱᴍᴀʟʟᴇʀ, ᴀɴᴅ ʟᴏᴏᴋ ʀᴇᴀʟʟʏ ᴏꜰꜰɪᴄɪᴀʟ. Yᴏᴜʀ ᴛᴀꜱᴋ ɪꜱ ᴛᴏ ᴡʀɪᴛᴇ ᴀ ᴘʀᴏɢʀᴀᴍ ᴛʜᴀᴛ ᴄᴏɴᴠᴇʀᴛꜱ ʀᴇɢᴜʟᴀʀ ᴛᴇxᴛ ɪɴᴛᴏ ꜱᴍᴀʟʟ ᴄᴀᴘꜱ.

Hᴇʀᴇ ɪꜱ ᴀ ʟɪꜱᴛ ᴏꜰ ᴛʜᴇ ᴜɴɪᴄᴏᴅᴇ ᴄʜᴀʀᴀᴄᴛᴇʀꜱ ꜰᴏʀ ꜱᴍᴀʟʟ ᴄᴀᴘꜱ:

```
ᴀ ʙ ᴄ ᴅ ᴇ ꜰ ɢ ʜ ɪ ᴊ ᴋ ʟ ᴍ ɴ ᴏ ᴘ ǫ ʀ ꜱ ᴛ ᴜ ᴠ ᴡ x ʏ ᴢ

```

## Cʟᴀʀɪꜰɪᴄᴀᴛɪᴏɴꜱ

* Rᴇɢᴜʟᴀʀ ᴄᴀᴘꜱ ʀᴇᴍᴀɪɴ ʀᴇɢᴜʟᴀʀ ᴄᴀᴘꜱ ᴀɴᴅ ꜱᴏ ᴅᴏ ᴘᴜɴᴄᴛᴜᴀᴛɪᴏɴꜱ, ꜱᴘᴀᴄᴇꜱ, ᴇᴛᴄ.
* Iɴᴘᴜᴛ ᴄᴀɴ ʙᴇ ᴍᴜʟᴛɪᴘʟᴇ ʟɪɴᴇꜱ.
* Tʜɪꜱ ɪꜱ , ꜱᴏ ꜱʜᴏʀᴛᴇꜱᴛ ᴄᴏᴅᴇ ɪɴ **ʙʏᴛᴇꜱ** ᴡɪɴꜱ!

## Tᴇꜱᴛ Cᴀꜱᴇꜱ

```
Hello World -> Hᴇʟʟᴏ Wᴏʀʟᴅ

abcdefghijklmnopqrstuvwxyz -> ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ

Welcome to Programming Puzzles and Code Golf Stackexchange!
It is a website ->
Wᴇʟᴄᴏᴍᴇ ᴛᴏ Pʀᴏɢʀᴀᴍᴍɪɴɢ Pᴜᴢᴢʟᴇꜱ ᴀɴᴅ Cᴏᴅᴇ Gᴏʟꜰ Sᴛᴀᴄᴋᴇxᴄʜᴀɴɢᴇ!
Iᴛ ɪꜱ ᴀ ᴡᴇʙꜱɪᴛᴇ.

```

# Answer
# Retina, 73 bytes

```
T`a-z`ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ

```

This is exactly what Retina's transliterate mode was made for. It replaces all lowercase letters (`a-z`) with their corresponding small caps version. Annoyingly, the character codes of the small caps characters are all over the place, so it can't take advantage of ranges for the second part: ideally it would be `T`a-z`ᴀ-ᴢ`.

Try it online.
> 30 votes

# Answer
# Pyth, ~~61~~ ~~59~~ 58 bytes

```
LXbGsmC+*7389<dGCd"#ʙ'(*ꜰɢʜɪ-.ʟ0ɴ2;ǫʀꜱ>?CDxʏE

```

This defines a named function `y`. Try it online in the Pyth Compiler/Executor.

The code contains no unprintable characters.

### Idea

Among the small caps, there are 14 characters in the range **7424 – 7458**, and all of them require three bytes to be stored verbatim. By subtracting **7389** from their code points, we map them in the printable ASCII range **35 – 69**, so each of them will occupy only one byte.

To decode the string, we simply add **7389** to the code points of all characters that come before **a**.

### Code

```
L                       Define y(b):
 Xb                       Transliterate b...
   G                      by replacing the lowercase ASCII letters...
                          with the characters of result of the following:
     m            "…          Map; for each d in that string:
        *7389<dG              Calculate (7389 * (d < 'abc...xyz')).
       +        Cd            Add the product to int(d).
      C                       Cast to character.
    s                       Turn the resulting char array into a string.

```
> 25 votes

# Answer
## Javascript (ES6), 114 bytes

```
a=>a.replace(/[a-z]/g,b=>'ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ'[b.charCodeAt()-97])

// snippet
var o = document.getElementById("o");
var t = document.getElementById("t");
t.onkeyup = _=>o.textContent = (a=>a.replace(/[a-z]/g,b=>'ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ'[b.charCodeAt()-97]))(t.value);
```

```
<!-- snippet -->
<input id="t" placeholder='Sample Text' />
<pre id="o"></pre>
```
> 12 votes

# Answer
# CJam, ~~78~~ ~~74~~ ~~67~~ ~~66~~ 63 bytes

```
q'{,97>"#ʙ'(*ꜰɢʜɪ-.ʟ0ɴ2;ǫʀꜱ>?CDxʏE"{_'a<7389*+}%er

```

This uses the same idea as my other answer.

The code contains no unprintable characters. Try it online in the CJam interpreter.

### How it works

```
q       e# Read all input and push it on the stack.
'{,     e# Push the range of all characters up to 'z'.
97>     e# Remove the first 97 characters. This leaves lowercase letters.

"#ʙ'(*ꜰɢʜɪ-.ʟ0ɴ2;ǫʀꜱ>?CDxʏE"

{       e# Map; for each character in that string:
  _'a<  e#   Check if a copy of the character is lower than 'F'. Pushes 1 or 0.
  7389* e#   Multiply the resulting Boolean by 7389.
  +     e#   Add the product to the character's code point.
}%      e#
er      e# Perform transliteration; replace each letter in the input by the
        e# corresponding character of the modified string.

```
> 11 votes

# Answer
# Python 3, 140 bytes

```
import sys;print(sys.stdin.read().translate(dict(zip(range(97,123),'ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ'))))

```

Try it online!

Hooray for built-in Unicode support! Now works with multi-line input.

*-10 bytes thanks to @Bakuriu*
> 10 votes

# Answer
## \>\<\>, ~~118~~ 116 Bytes

-2 bytes thanks to @torcado.

I'll try to think of a way to remove that entire alphabet from my code later.

I haven't been able to test it with newlines, but I see no reason for it not working with them.

```
!oi:0(?;::"{"($"`")*0$.
v"a"%&"ᴢʏxᴡᴠᴜᴛꜱʀǫᴘᴏɴᴍʟᴋᴊɪʜɢꜰᴇᴅᴄʙᴀ"&
>:?!v1-$~
~00.>

```

Try it online.

Emoticons found in the code: `0:(`, `:0`, `:"{`, `>:`, `0=`, and the debatable ones: `i:`, `>:?`, `:?`, `?;`
> 8 votes

# Answer
# Julia, 126 bytes

```
t->join([(i=Int(c);96<i<123?split("ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ","")[i-96]:c)for c=t])

```

Ungolfed:

```
function f(t::AbstractString)
    # Split the small caps into an array (this particular Unicode
    # string does not like to be indexed for whatever reason)
    s = split("ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ", "")

    # Create an array with replaced letters
    r = [(i = Int(c); 96 < i < 123 ? s[i-96] : c) for c in t]

    # Join the array back into a string
    join(r)
end

```
> 6 votes

# Answer
## Perl 5, 84 bytes

**(83 bytes script and `-p`)**

```
use utf8;y/a-z/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/

```

Nothing particularly different, but it's worth noting the necessity of the `use utf8;` statement to get legible text. A warning is displayed as well, but I believe the consensus is that they are acceptable:

```
$perl -p smallcaps.pl <<< 'Programming Puzzles and Code Golf'
Wide character in print, <> line 1.
Pʀᴏɢʀᴀᴍᴍɪɴɢ Pᴜᴢᴢʟᴇꜱ ᴀɴᴅ Cᴏᴅᴇ Gᴏʟꜰ
$perl -p smallcaps.pl <<< 'Programming Puzzles and Code Golf' 2> /dev/null
Pʀᴏɢʀᴀᴍᴍɪɴɢ Pᴜᴢᴢʟᴇꜱ ᴀɴᴅ Cᴏᴅᴇ Gᴏʟꜰ

```

---

## Perl, 80 bytes

**(74 bytes script and `-pMutf8`)**

Thanks @hobbs!

```
y/a-z/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/

```

```
$perl -pMutf8 -e'y/a-z/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/' <<< 'Programming Puzzles and Code Golf' 2> /dev/null
Pʀᴏɢʀᴀᴍᴍɪɴɢ Pᴜᴢᴢʟᴇꜱ ᴀɴᴅ Cᴏᴅᴇ Gᴏʟꜰ

```
> 5 votes

# Answer
## 05AB1E, 73 bytes (non-competing)

Yet again, I wish Adnan had published this language earlier.

```
A"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"‡

```

Try it online!

Explanation:

```
A                              - Push a-z
 "ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"   - Push "ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"
                             ‡ - Pop a, b, c Push a.transliterate(b -> c)

```
> 5 votes

# Answer
# Java, ~~306~~ ~~275~~ ~~217~~ ~~215~~ 189 bytes

Well, Java is definetely not the best language to accomplish this task in... but, here it is anyway:

```
void p(String s){for(int i=1;i<27;s=s.replace("abcdefghijklmnopqrstuvwxyz".charAt(++i),"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ".charAt(i)));System.out.print(s);

```

Thanks to @ThomasKwa and @DHall for help in shaving off 91 characters!
> 3 votes

# Answer
# Ruby, 89 bytes

```
p ARGV[0].tr "a-z","ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"

```

To use:

```
ruby <file-name> "<string>"

```
> 3 votes

# Answer
# Julia, 105 bytes

```
t->map(c->96<c<123?["ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"...][c-'`']:c,t)

```

This is simple - for each character in `t`, it checks to see if the character, `c`, is lowercase (`96<c<123`) - if it is, it subtracts the character with value 96 (`'`'`) from the character, and looks up the corresponding character in the array `[ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"...]`. If it's not lowercase, then just use `c` itself. The `map` function applies this procedure for each character in the string.

Alternative, if we can restrict input to ASCII less than 127:

### Julia, 104 bytes

```
t->join(['\1':'`';"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ{|}~"...][t.data])

```

In this case, the array is longer, including all characters between ASCII 1 (`'\1'`) and 126 (`'~'`), with the lowercase letters replaced as appropriate - it then uses the characters in `t`, expressed as unsigned integers (`t.data`), to lookup the values in the array, and `join`s the new characters back into a string at the end.
> 3 votes

# Answer
# Sed, 97 bytes

```
y/abcdefghijklmnopqrstuvwxyz/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/

```
> 3 votes

# Answer
# Sacred JavaScript ES6, 600 Bytes

Hey look, I answered!

```
( ))) ) )( ) ))( ))) () (((  (( ()((( ))( )  ( )() (((( () ) () ( () )( )(( ((() () (((  (( ()((( (( (((((((() ) )( ) ))((  )( ) )((( ) ( () )( )(( ) (( ) ( ()(((((( (((( ()() )    ((() ( () () (( )( ( )) ((   ((    (((( ()(  ((() () (((  (( ()((( (( (((( (((((( () (())( ) ) ((() ) )( ) )) ( )((()))) ())() ( () ((() )  ( ()((()() ) )(()) ()(  ()( () )()()(( () )(()(()())()   ()()) ( ( ) ()))))    )  (()  ()(((( )  )()  )  ( )(( ( (( ) )( ((  ((()( ( ((((() () (( )  ( )()( ()((( )  )((((( ( ( ) (( ) ) )( )(( )) (((( ((() ()   ) (  )  (( (( ((()(((()((((() ((() () (( ))((( ( ( )) ((  )( () ( ()

```

Here's a cool image:

# JavaScript ES6, 120 Bytes

This is the code.

```
k=>k.match(/./g).map(z=>new Array(26) .fill(0).map((q,e)=>"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"[e])[z.charCodeAt()-97]||z).join``)

```

This is the snippet.

```
while(1)alert(prompt().match(/./g).map(z=>new Array(26) .fill(0).map((q,e)=>"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"[e])[z.charCodeAt()-97]||z).join``
```
> 2 votes

# Answer
# Scala, 125 bytes

```
(s:String)=>s.map(c=>('a'to'z'zip "ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"toMap).getOrElse(c,c))

```

An anonymous function that has string as an input and output. Iterate through its chars and get the unicode version of them by matching them from dict/map. Return original char if the unicode one doesn't exist.

### Usage

1. Open Scala REPL and paste the code above
2. It will create a function (`resX`) that can be called by passing a string (e.g. `resX("my String")`)
> 2 votes

# Answer
## Perl 6, 78 bytes

The simplest command line version:

```
$ perl6 -pe'tr/a..z/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/' # 76 + 2 = 78

```

It gets a bit larger if you put it into a file.

```
$_=$*IN.slurp-rest;tr/a..z/ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ/;.print # 102

```
> 2 votes

# Answer
# Japt v2.0a0, ~~81~~ ~~80~~ ~~78~~ 75 bytes

```
r\aÈcg"ʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢᴀʙᴄᴅᴇꜰɢ

```

Try it
> 2 votes

# Answer
# Vyxal `U`, 56 bytes

```
ka`#Ẏṗ'(*¥ṫ§Ẋ⟨ẎṫẊ₅-.Ẏẏ0Ẋ¦2;Ṫ₆Ẏ↓¥ṫε>?CDxẎḋE`C:70<7389*+CĿ

```

Try it Online!

Port of CJam.

## How?

```
ka`#Ẏṗ'(*¥ṫ§Ẋ⟨ẎṫẊ₅-.Ẏẏ0Ẋ¦2;Ṫ₆Ẏ↓¥ṫε>?CDxẎḋE`C:70<7389*+CĿ
ka                                         # Push the lowercase alphabet
  `#Ẏṗ'(*¥ṫ§Ẋ⟨ẎṫẊ₅-.Ẏẏ0Ẋ¦2;Ṫ₆Ẏ↓¥ṫε>?CDxẎḋE` # Push string "#ʙ'(*ꜰɢʜɪ-.ʟ0ɴ2;ǫʀꜱ>?CDxʏE"
                             C             # Convert to character codes: [35, 665, 39, 40, 42, 42800, 610, 668, 618, 45, 46, 671, 48, 628, 50, 59, 491, 640, 42801, 62, 63, 67, 68, 120, 655, 69]
                              :            # Duplicate
                               70<         # For each, is it less than 70?
                                  7389*    # Multiply by 7389
                                       +   # Add
                                        C  # Convert from character codes
                                         Ŀ # Transliterate the implicit input from the lowercase alphabet to this

```

Previous answer:

## Vyxal, 61 bytes

```
ka»7ȧ∵ẋǍ}Żq(ṗ⌐>⁋8≤M?↵:‡⌊&fǍ≈⁋D5£ɾ|øP₂@ġĿ≤ǔxτ¶_ṙɾ|ȧ.,=»»₃↲»τCĿ

```

Try it Online!

## How?

```
ka»7ȧ∵ẋǍ}Żq(ṗ⌐>⁋8≤M?↵:‡⌊&fǍ≈⁋D5£ɾ|øP₂@ġĿ≤ǔxτ¶_ṙɾ|ȧ.,=»»₃↲»τCĿ
ka                                                            # Push the lowercase alphabet
  »7ȧ∵ẋǍ}Żq(ṗ⌐>⁋8≤M?↵:‡⌊&fǍ≈⁋D5£ɾ|øP₂@ġĿ≤ǔxτ¶_ṙɾ|ȧ.,=»         # Push compressed integer 454193002670633612531343815167055208136573147142298478503419521655224802790872780438775790455172058745698867697958481400
                                                     »₃↲»     # Push compressed integer 42802
                                                         τ    # Convert the big integer to that custom base as a list: [7424, 665, 7428, 7429, 7431, 42800, 610, 668, 618, 7434, 7435, 671, 7437, 628, 7439, 7448, 491, 640, 42801, 7451, 7452, 7456, 7457, 120, 655, 7458]
                                                          C   # Convert it from character codes to characters
                                                           Ŀ  # Transliterate the implicit input from the lowercase alphabet to that

```
> 2 votes

# Answer
# Python, 99 bytes

```
def s(t):return"".join([(a,"ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"[(ord(a)+7)%26])[96<ord(a)<123] for a in t])

```

I tried to find some pattern in the Unicode codes for small capitals, but I'm not sure there is one.
> 2 votes

# Answer
# Raku, 69 bytes

```
{S:g[(q)|<[a..wyz]>]=$0??'ǫ'!!'ᴀ'.uniname.subst(/.$/,$/).uniparse}

```

Try it online!

Special handling for `q`; for other lowercase letters other than `x`, generate the Unicode name for the small caps (eg, `LATIN LETTER SMALL CAPITAL S`) and parse it.

I saved a few bytes by using the Unicode name of the character  (`LATIN LETTER SMALL CAPITAL A`) as a template, and replacing the final character with the letter I want to convert.
> 2 votes

# Answer
# Lua, 160 bytes

```
function c(a)
return a:lower():gsub("%w",function(d)b=a.byte(d)-96;return("ᴀʙᴄᴅᴇꜰɢʜɪᴊᴋʟᴍɴᴏᴘǫʀꜱᴛᴜᴠᴡxʏᴢ"):sub(b,b)end)end

```
> 1 votes

# Answer
# Jelly, 65 bytes

```
“⁾ḋḷ?D8=ƙʂȤ£²^ĖẸI)¡e[µ°⁾ṢJ*MĠɓ¤Ḃġ⁽vEEɲạ®G{(ŀ³⁻¹ƭTẸⱮ’ṃ“ȥ3’Ọ
Øaż¢Fy

```

Attempt This Online!

```
“⁾ḋḷ?D8=ƙʂȤ£²^ĖẸI)¡e[µ°⁾ṢJ*MĠɓ¤Ḃġ⁽vEEɲạ®G{(ŀ³⁻¹ƭTẸⱮ’ṃ“ȥ3’Ọ : Link 1

“⁾ḋḷ?D8=ƙʂȤ£²^ĖẸI)¡e[µ°⁾ṢJ*MĠɓ¤Ḃġ⁽vEEɲạ®G{(ŀ³⁻¹ƭTẸⱮ’       : Compressed integer for 454193002670633612531343815167055208136573147142298478503419521655224802790872780438775790455172058745698867697958481400

                                                     “ȥ3’  : Compressed integer for 42802

                                                    ṃ      : Base decompression; convert x to base length(y) then index into y; results in character codes

                                                         Ọ : Cast to characters
Øaż¢Fy : Main Link
Øa     : Lowercase alphabet
   ¢   : Last link as a nilad
  ż    : Zip; interleave x and y
    F  : Flatten list
     y : Translate the elements of y according to the mapping in x; change the characters

```

Integers used to get the character codes borrowed from Steffan's Vyxal Answer
> 1 votes

---
Tags: code-golf, conversion, unicode
---


title: Fibonacci word fractal

text:
# Question
Title: Fibonacci word fractal
The **Fibonacci word** is a sequence of binary strings defined as:

* \\$F\_0 = \\$ `0`
* \\$F\_1 = \\$ `01`
* \\$F\_n = F\_{n-1} F\_{n-2}\\$

The first few Fibonacci words are:

```
0
01
010
01001
01001010
0100101001001
010010100100101001010
...

```

Each of these strings is a prefix of the next, so they are all prefixes of the single infinite word \\$F\_\infty\\$ =

```
010010100100101001010010010100100101001010010010100101001001010010010100101001001010010010100101001...

```

(The definition above is borrowed from this sandbox challenge by pxeger.)

Now we can define a fractal curve based on the Fibonacci words.

Starting from some point on the plane, for each digit at position \\$k\\$ of the Fibonacci word \\$F\_\infty\\$:

* Draw a segment with length \\$1\\$ forward,
* If the digit is \\$0\\$:
    + Turn 90° to the left if \\$k\\$ is even,
    + Turn 90° to the right if \\$k\\$ is odd.

This is called the **Fibonacci word fractal**.

For example, the first 21 digits in \\$F\_\infty\\$ are `010010100100101001010`, which would give the following shape:

```
┌
│ ┌─┐
└─┘ │
   ┌┘
   │
   └┐
┌─┐ │
│ └─┘

```

To be clearer, let's mark the starting point by `^`, and replace the other chars by its corresponding digit in the Fibonacci word:

```
0
1 010
010 1
   00
   1
   00
010 1
^ 010

```

Here are some more steps of the Fibonacci word fractals, taken from Wikipedia:

## Task and rules

Given a non-negative integer \\$n\\$, draw *at least* \\$n\\$ steps of the infinite Fibonacci word fractal.

You may draw more steps than \\$n\\$. But the extra steps should still belong to the infinite Fibonacci word fractal.

Or alternatively, you may take no input, and draw every step of the infinite Fibonacci word fractal (as an animation, or an infinite sequence of outputs).

You may output as either or .

For , you may choose any characters to draw the curve as long as the output is clear.

The fractal curve consists of a chain of line segments. For each step, you may choose to draw one of the followings, but your choice must be consistent (taking \\$n=21\\$ as an example):

* the starting point of the segment:

```
# ###
### #
   ##
   #
   ##
### #
# ###

```
* the ending point of the segment:

```
#
# ###
### #
   ##
   #
   ##
### #
  ###

```
* the whole segment.

```
#
# ###
### #
   ##
   #
   ##
### #
# ###

```

The direction don't need to be consistent. You may arbitrarily rotate or reflect the curve.

This is , so the shortest code in bytes wins.

# Answer
> 8 votes
# , 79 bytes

```
load'plot'
[:plot 0;/@|:[:+.@([:+/\1*/\@,-.+0j1*]*_1^#\)@;_2&(],<@;@{.)&(1;1 0)

```

J Playground

Generates more than required, because it:

* First iterates fib `n` times
* Uses complex numbers with product scans and sum scan to calculate all the coords at once
* plots those coordinates

# Answer
> 7 votes
# Vyxal, ~~41~~ ~~39~~ ~~33~~ ~~32~~ ~~31~~ ~~30~~ ~~28~~ ~~26~~ ~~25~~ ~~24~~ ~~23~~ 19 bytes

```
1₀?(~p)yNYdÞR8%2×ø∧

```

Try it Online!

Takes `n` and draws the nth fibonacci number of steps.

Outputs as ascii art.

I may have forgotten you can use any non-whitespace character :p...

*-4 thanks to emanresuA even if I somehow didn't notice it for 4 days*

## Explained (old)

```
1₀?(~p)f:ẏu$ed*ÞR8%2×ø∧
1₀                        # Push 1 and 10 to the stack. These will form the initial terms for the Fibonacci words
  ?(  )                   # Input number of times:
    ~p                    #   Without popping the top two items on the stack, prepend the top to the second-top. This gives [1, 10, 101, 10110, 10110101, 1011010110110, ...] - the sequence but with inverted bits
       f:                 # Push two copies of the top of the stack as a list of digits
         ẏu$e             # Push -1 to the power of each index in the range [0, len(top)]. This determines both a) whether a turn is needed and b) which general direction to make the turn if a turn is needed for each bit in the Fibonacci word. The result will be 0 (no turn, keep going), 1 (turn to the right) or -1 (turn to the left).
             d*           # Double the list so it can be used with the canvas drawing element and multiply the bit list by the direction list. More on the canvas a little later
               ÞR         # Take the cumulative sums of the list, remove the last item, and prepend a 0. Yes, that's a thing that's 2 bytes in Vyxal.
                 8%       # Modulo each item by 8. This is so that each number can be mapped to a canvas direction that is one of [0, 2, 4, 6]. 0 = up, 2 = right, 4 = down, 6 = left
                   2×ø∧   # For each direction in that list, draw a line of *s of length 2 on the global canvas in that direction. Think of the canvas as a kind of turtle but ascii thing, where each direction moves the turtle and leaves a trail of *s behind. The global canvas is implicitly printed at end of execution. This could also be ø^, but ø∧ looks better :p

```

# Answer
> 7 votes
# Desmos, 111 bytes

```
p->p+1,d->d+90(1-floor(pk+k)+floor(pk))(1-2mod(p,2)),L->join(L[1]+(cosd,sind),L)
L=[(0,0)]
gg~g+1
k=2-g
p=2
d=0

```

Paste the first line in a ticker, the second line in a collapsed folder, and the rest of the lines in the regular expression boxes. Also make sure Desmos is set to degrees mode, and not radians.

Then click the ticker (the metronome in the top left corner) to run the code.

Theoretically, this can go on infinitely, but due to Demsos's list length cap at 10000 elements, we can only generate 9999 segments before erroring out. But it doesn't really matter, because Desmos already starts lagging pretty badly (at least on my computer) around 3 or 4k segments, so it would take a while to actually get to 9999 segments (I left it running for around 15 minutes or so and got up to around 7000 segments).

Also, the list `L` is stored in a collapsed folder because Desmos lags really, really badly if not collapsed; it is trying to render the entire list while it is constantly being updated by the tickers. Open the folder at your own risk :P

Fun little tidbit: Setting `d`'s initial value to something other than `0` will cause the code to produce a rotated fractal. Try it out!

Try It On Desmos!

Try It On Desmos! - Prettified

Around 7000 segments

---

Here's a longer version without actions (it runs a lot faster!):

### 125 bytes

```
gg~g+1
k=2-g
L=[1...n]
S=∑_{a=0}^L90(1-floor(ak+k)+floor(ak))(-1)^a
C(l)=∑_{i=1}^Ll[i]
f(n)=join((0,0),(C(cosS),C(sinS)))

```

The function `f(n)` will take in a positive integer `n` and output the first `n` segments of the fractal.

The restriction of 9999 segments also applies to this answer; Desmos lists can only contain up to 10000 elements. Theoretically though, the code can produce any amount of segments if there was no restriction on list length.

`f(9999)` takes about 30 seconds to load on my computer.

Try It On Desmos!

Try It On Desmos! - Prettified

3000 segments (if you don't want to load the 9999 segments)

# Answer
> 6 votes
# Python, 83 bytes

```
from turtle import*
a,b=[i:=0],[-1]
while 1:a,b=b,b+a;lt(b[i]**i*90);fd(5);i+=1

```

-6 thanks to tsh

Draws it infinitely.

Very slow because it generates another term of the Fibonacci sequence at every iteration. This is much faster if you want to test it:

```
from turtle import*
a,b=[i:=0],[90]
while 1:
 if i>=len(b):a,b=b,b+a
 lt(b[i]*(-1)**i);fd(5);i+=1

```

Try it on repl.it!

You can also add a `speed(0)` at the beginning to make it draw faster.

# Answer
> 5 votes
# Charcoal, ~~29~~ 26 bytes

```
≔1θＦＮ«#↷∧Ｉ§θι⁺²×⁴ι≔⭆θ⍘⊕κ²θ

```

Try it online! Link is to verbose version of code. Outputs the start point of each segment. Explanation: Actually calculates the complementary sequence A005614 because it's golfier.

```
≔1θ

```

Start with `1`.

```
ＦＮ«

```

Repeat `n` times.

```
#

```

Output the start point of the segment.

```
↷∧Ｉ§θι⁺²×⁴ι

```

Calculate the amount of rotation in multiples of 45°. This is `0` if the element of A005614 was `0` or `2` plus `4` times the number of steps so far (`k`).

```
≔⭆θ⍘⊕κ²θ

```

Extend the string holding A005614 by incrementing each digit in base 2 i.e. replace `0` with `1` and `1` with `10`. (Note that this is very inefficient since it calculates the string to length `F(n+2)` which is `28657` for the example of `n=21`.)

Previous more efficient 29-byte version:

```
ＦＮ«#Ｗ№⍘Ｌυ²11⊞υω⊞υω↷∧﹪Ｌυ²⁺²×⁴ι

```

Try it online! Link is to verbose version of code. Outputs the start point of each segment. Explanation: The Fibonacci word A003849 is simply the Fibbinary sequence A003714 modulo 2.

```
ＦＮ«

```

Loop `n` times.

```
#

```

Output the start point of the segment.

```
Ｗ№⍘Ｌυ²11⊞υω

```

Increase the length of the predefined empty list as necessary so that it reaches a Fibbinary number, i.e. its binary representation does not contain `11`.

```
⊞υω

```

Increase the length of the predefined empty list again. The above loop will then find the next Fibbinary number on the next pass through the outer loop, but this also complements the least significant bit which simplifies the next calculation.

```
↷∧﹪Ｌυ²⁺²×⁴ι

```

Calculate the amount of rotation in multiples of 45°. This is `0` if the Fibbinary number was odd or `2` plus `4` times the number of steps so far (`k`).

# Answer
> 4 votes
# Wolfram Language (Mathematica), 75 bytes

```
Graphics@Line@AnglePath@Nest[Flatten@{#,p(-1)^Tr[1^(p=#)]}&,p=0;Pi/2,#]&

```

Takes n and draws the nth fibonacci number of steps.

> n=14

-24 bytes from @alephalpha
-4 bytes from @att

# Answer
> 4 votes
# 05AB1E, ~~37~~ ~~34~~ 32 bytes

```
Tηλèì}āsÏV0YvDyÈiÍëÌ])8%AY¥>2šrΛ

```

Takes advantage of the mentioned *at least* in the challenge rules to save 2 bytes.
Outputs using the lowercase alphabet as characters (but could also use any single digit instead by replacing the `A`).

Try it online.

**Explanation:**

Step 1: Get the Fibonacci word \\$F\_n\\$ based on the input \\$n\\$, but with the 0s and 1s reversed:

```
T         # Push 10
 η        # Pop and push its prefixes: [1,10]
  λ       # Start a recursive environment,
   è      # to generate the (0-based) (implicit) input'th value
          # Starting with a(0)=1 and a(1)=10
          # Where every following a(n) is calculated as:
          #  (implicitly push a(n-2) and a(n-1)
    ì     #  Prepend a(n-1) in front of a(n-2)
  }       # Close the recursive environment

```

Try just step 1 online.

Step 2: Generate a list of \\$k+1\\$ at the 1-positions:

```
   ā      # Push a list in the range [1,length] (without popping the string)
    s     # Swap so the string is at the top of the stack again
     Ï    # Only keep the 1-based values at the truthy (==1) positions

```

Try just step 2 online.

Step 3: Using this list of \\$k+1\\$ indicating when to turn clockwise/counterclockwise, transform it to a list of 05AB1E Canvas directions (0=↑; 2=→; 4=↓; 6=←):

```
      V   # Pop and store this list in variable `Y`
0         # Push a 0
 Yv       # Loop `y` over list `Y`:
   D      #  Duplicate the current value
    yÈi   #  If `y` is even:
       Í  #   Increase the value by 2
      ë   #  Else (`y` is odd):
       Ì  #   Decrease the value by 2
  ]       # Close both the if-else and loop
   )      # Wrap all values on the stack into a list
    8%    # Modulo-8 each

```

Try just step 3 online.

Step 4: Modify the list from step 2 to a list of lengths, and using this modified list and the directions-list from step 3, draw the lowercase alphabet in this pattern with the Canvas builtin:

```
A         # Push constant "abcdefghijklmnopqrstuvwxyz"
 Y        # Push list `Y` from step 2
  ¥       # Pop and push its deltas/forward-differences
   >      # Increase each value by 1
    2š    # Prepend a 2
      r   # Reverse the three values on the stack
       Λ  # Use the Canvas builtin with these three options
          # (after which the result is output immediately)

```

See this 05AB1E tip of mine for an in-depth explanation about the Canvas builtin `Λ` and how the generated directions- and length-lists are used.

# Answer
> 4 votes
# MATL, ~~28~~ ~~27~~ 26 bytes

*Inspired by Sanchises' answer to a loosely related challenge. I think the approach is also similar to that in Jonah's answer here.*

```
JO2B1i:"6Mh]htn:Eq*^YpYsXG

```

The output is rotated 90 degrees clockwise with respect to the examples in the challenge text. The initial segment is not drawn. More steps than necessary are drawn.

**Try it at MATL online!**

With input `11` this gives the last image shown in the challenge (rotated):

### Explanation

```
J       % Push imaginary unit, j: (*)
O       % Push 0: (**)
2B      % Push 2 in binary, that is, [1 0]. This is F_1, with 0 and swapped
1       % Push 1. This is F_0, with 1 instead of 0
i       % Input n
:"      % Do n times
  6M    %   Push first input to the latest function that took more than 1 input.
        %   In the first iteration this does nothing; in iteration k>1 it gives
        %   F_{k-1}
  h     %   Concatenate F_k and F_{k-1} to produce F_{k+1}
]       % End. The top of the stack contains F_{k+1}
h       % Concatenate 0 (**) with F_{k+1}: (***)
t       % Duplicate
n:      % Range [1 2 3 ... L], where L is the length of the above
Eq      % Times 2, minus 1, element-wise. Gives [1 3 5 ...]
*       % Multiply with (***), element-wise
^       % Imaginary unit (*) raised to this, element-wise
Yp      % Cumulative product. This generates the directions: 1, j, -1 or -j
Ys      % Cumulative sum. This generates the path, starting at 0
XG      % Plot as complex numbers

```

# Answer
> 4 votes
# Prolog (SWI), 242 bytes

```
N+A+B+R:-N<1,R=B;append(B,A,C),N-1+B+C+R.
D-X/Y-N-K-Q:-Q=[H|T],(N/\1>0,V=X+2-N;V=X),(N/\1>0,W=Y;W=Y+1-N),new(L,line(X,Y,V,W)),send(D,display,L),M is(N-K*H)mod 4,D-V/W-M-(-1)*K-T;1=1.
\X:-new(D,window()),X+[1]+[1,0]+R,D-0/0-1-1-R,send(D,open).

```

`\X` will calculate the `X`th Fibonacci word and thus draw at least `X` steps.

Uses the XPCE toolkit for creating GUI applications in Prolog, here's an example output for goal `\20.`:

In the `A-B-C-D-E` predicate, no expressions are evaluated until calling `new` to create the line, which makes the code very slow:

```
?- time(\16).
% 36,098 inferences, 15.493 CPU in 15.518 seconds (100% CPU, 2330 Lips)

```

Here is a faster and more readable version that evaluates every iteration:

```
_-_-_-_-[]-fast.
D-X/Y-N-K-[H|T]-fast:-
    % Flip K (odd/even position)
    Z is(-1)*K,
    % Calculate the new X,Y location
    (N/\1>0,V is X+2-N;V=X),
    (N/\1>0,W=Y;W is Y+1-N),
    % Send new line to display
    new(L,line(X,Y,V,W)),
    send(D,display,L),
    % Set new direction depending on H and previous direction N
    M is(N-K*H)mod 4,
    D-V/W-M-Z-T-fast.
fast(X):-
    % 0s and 1s are flipped for shorter calculation (if 0 becomes if 1)
    new(D,window()),X+[1]+[1,0]+R,D-0/0-1-1-R-fast,send(D,open).
```

```
?- time(fast(25)).
% 3,374,631 inferences, 2.311 CPU in 2.319 seconds (100% CPU, 1460457 Lips)

```

# Answer
> 3 votes
# , ~~99~~ ~~82~~ ~~76~~ ~~74~~ 73 bytes

*Edit: -2 bytes thanks to pajonk*

```
function(n,`?`=cumsum){while(n<-n-1)T=c(F,F<-T)
plot(?1i^?c(1,3)*T,,"l")}

```

Try it at rdrr.io

`while(n<-n-1)T=c(F,F<-T)` generates the `n`-th Fibonacci word in reverse, with zeros and ones exchanged.
Then, `cumsum(c(1,3)*m)` calculates cumulative sum multiplied by 1 (at odd indices) or 3 (at even indices), to give the current direction. `i` raised to this power gives a step in the right direction, and the cumulative sum of this gives the position at each step: `cumsum(1i^cumsum(c(1,3)*m))` (the function `cumsum` is re-assigned to the low-precedence `?` operator to save bytes (and obfuscate).
So we just plot this on the complex plane, using `"l"` to join the points with lines.

This would be 66 bytes in  version ≥4.1 by replacing `function` with `\`, but this isn't currently supported by the online interpreter at rdrr.io.

# Answer
> 2 votes
### HTML+Javascript, ~~228~~ ~~216~~ 210 bytes

`f(n)` draws at least `n` segments. The size adapts so that the fractal does not get too small.

*12 bytes saved thanks to Neil*

```
f=o=>{for(k=b=n=0,l='01';!l[o];)m=l,l+=k,k=m
d='M1,1';p=5;for(w of l)e=1-(b&2),d+='hv'[b&1]+e,b+=w|0?0:n%2*2+1,b%=4,p+=e,n++
document.write(`<svg viewBox=0,0,${p},${p} style=fill:none;stroke:#000><path d=`+d)}
f(2000)
```

-13 bytes with a fixed-size canvas, which limits the number of segments that are visible. (And low `n` are really hard to see.) For `viewBox="0 0 999 999"`, approx. `n ≤ 75000`.

```
f=o=>{for(k=b=n=0,l='01';!l[o];)m=l,l+=k,k=m
d='M1,1';for(w of l)d+='hv'[b&1]+(1-(b&2)),b+=w|0?0:n%2*2+1,b%=4,n++
document.write(`<svg viewBox=0,0,999,999 style=fill:none;stroke:#000><path d=`+d)}
f(75000)
```

**Non-competing bonus:** I was also experimenting with a recursive solution in HTML/Pug, but it ended at 500 bytes, and it's really slow and memory-heavy. See it on Codepen.

---
Tags: code-golf, ascii-art, graphical-output, fibonacci, fractal
---


title: Count alternating permutations

text:
# Question
Title: Count alternating permutations
An **alternating permutation** is a permutation of the first \\$ n \\$ integers \\$ \\{ 1 ... n \\} \\$, such that adjacent pairs of values in the permutation alternate between increasing and decreasing (or vice versa).

Equivalently, it is a permutation where there are no "runs" of continuously increasing or decreasing values with a length \\$ \> 2 \\$.

For example, `2 4 1 5 3 6` is an alternating permutation for \\$ n = 6 \\$, because \\$ 2 \< 4 \\$, and \\$ 4 \> 1 \\$, and \\$ 1 \< 5 \\$, and \\$ 5 \> 3 \\$, and \\$ 3 \< 6 \\$: each pair alternates in their relative comparisons.

However, `1 3 2 4 6 5` is not a valid alternating permutation, because it contains the continuously increasing sequence `2 4 6` (\\$ 2 \< 4 \\$ and \\$ 4 \< 6 \\$).

In this challenge we will consider the number of alternating permutations for a given positive integer \\$ n \\$.

For example, for \\$ n = 4 \\$, there are \\$ 4! = 24 \\$ permutations, of which \\$ 10 \\$ are alternating permutations:

```
1 3 2 4
1 4 2 3
2 1 4 3
2 3 1 4
2 4 1 3
3 1 4 2
3 2 4 1
3 4 1 2
4 1 3 2
4 2 3 1

```

You may notice that every permutation has a duplicate which is just its reverse. Thus, for this challenge, when there is a pair of permutations which are the reverses of each other, you should only count it once.

Note that for \\$ n = 1 \\$, there is only one permutation, just `1`, which doesn't have a distinct reverse. So for \\$ n = 1 \\$, the output is still \\$ 1 \\$.

For \\$ n = 0 \\$, there is also only one permutation, the empty one, but you do not need to handle it (we only care about \\$ n \ge 1 \\$).

Your task, finally, is to output the sequence of the number of alternating permutations for positive integers \\$ n \\$, excluding reverse-duplicates. This sequence starts:

```
1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765

```

This is A000111 (after \\$ n = 0 \\$) in the OEIS, and it is half of A001250 (after \\$ n = 1 \\$).

## Rules

* As with standard challenges, you may choose to either:
    + Take an input \\$ n \\$ and output the \\$ n \\$th term in the sequence
    + Take an input \\$ n \\$ and output the first \\$ n \\$ terms
    + Output the sequence indefinitely, e.g. using a generator
* You may use \\$ 0 \\$\- or \\$ 1 \\$-indexing
* You may use any standard I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# Python 3.8, 54 bytes

*-4 bytes thanks to @ovs*
*-2 bytes thanks to @Albert.Lang*

Prints the sequence indefinitely.

```
s,*a=1,
while[print(s)]:a=s,*[s:=s+x for x in a[::-1]]

```

Try it online!

### Explanation

I originally found this method in one of the Python implementations on the OEIS page. Here is a simple explanation of how it works.

The alternating permutation in this problem can be viewed as a chain of alternating less-than and greater-than signs such that it begins with `>`: `? > ? < ? > ? < ...`. Let \\$ P(n,e) \\$ be the number of alternating permutations of size \\$ n \\$ whose last element is \\$ e \\$. Given this, the number of alternating permutations of size \\$ n \\$ is simply \\$ \sum\_{i=1}^n P(n,i) \\$. Our goal now is to come up with a convenient algorithm to compute \\$ P \\$.

Let's take the example \\$ P(5,4) \\$, for which the permutation would be in the form:

```
? > ? < ? > ? < 4

```

Now, the number to the left of the `4` must be either `1`, `2`, or `3`, while the rest of the numbers will be from the set `{1, 2, 3, 5}`. In other words, the four unknown numbers must form an alternating permutation whose last element is between `1` and `3`. This however, is exactly the same as asking the answer to \\$ P(4,1) + P(4,2) + P(4,3) \\$. One might argue that there is a difference in that the missing numbers do not necessarily form a permutation from `1` to `n`. However, as long as they are all distinct, this will not matter, since comparisons only care about the relative ordering of the numbers.

More generally, we can say that \\$ P(n,e) = \sum\_{i=1}^{e-1} P(n-1,i) \\$. But, this formula only makes sense if the rightmost comparison is a `<` (odd \\$ n \\$). Instead if it were a `>` (even \\$ n \\$), we would have \\$ P(n,e) = \sum\_{i=e+1}^{n} P(n-1,i) \\$.
> 9 votes

# Answer
# , ~~36~~ 35 bytes

```
while(T<-rev(diffinv(T)))show(T[1])

```

Try it online!

Port of @dingledooper's answer.
> 5 votes

# Answer
# PARI/GP, 23 bytes

```
n->2*abs(polylog(-n,I))
```

Attempt This Online!

Based on the PARI/GP code on OEIS by M. F. Hasler.

---

# PARI/GP, 35 bytes

```
n->Vec(1/(1-sin(x+O(x^n))))[n]*n--!
```

Attempt This Online!

The exponential generating function of the sequence is \\$1/(1-\sin(x))\\$.
> 5 votes

# Answer
# APL (Dyalog Unicode), 12 bytes

Full program. Port of dingledooper's answer.

```
⊃(⌽0,+\)⍣⎕,1

```

Try it online!

---

**31 bytes:**

```
{1<⍵:2÷⍨(k!⍵-1)+.××∘⌽⍨∇¨k←⍳⍵⋄1}

```

Try it on APLgolf!

Implements a formula from OEIS:

$$ 2\times a(n+1) = \sum\_{k=0..n} {n \choose k}\times a(k)\times a(n-k) $$

---

**31 bytes:**

```
{+/2((-\⍳⍵-1)≡⍥×-/)¨∪⍋⍤,¨,⍳⍴⍨⍵}

```

Try it on APLgolf!

Generates all permutations and counts the alternating ones that start with an increment.
> 4 votes

# Answer
# Charcoal, 22 bytes

```
⊞υ¹ＦＮ≔⊞Ｏ⮌ＥυΣ…υ⊕λ⁰υＩ§υ⁰

```

Try it online! Link is to verbose version of code. Works for `n=0`. Explanation: Uses a formula from OEIS.

```
⊞υ¹

```

Start with the empty permutation.

```
ＦＮ

```

Repeat `n` times.

```
≔⊞Ｏ⮌ＥυΣ…υ⊕λ⁰υ

```

Take the cumulative sums of the list, reverse the result, and append a zero.

```
Ｉ§υ⁰

```

Output the first element of the final list.
> 3 votes

# Answer
# 05AB1E, ~~9~~ 8 bytes

```
$F0).sO`

```

Port of *@dingledooper*'s Python answer, but outputs the \\$n^{th}\\$ value instead to save a byte.

Try it online or verify the first 25 test cases.

Outputting the infinite sequence for a direct port would be:

```
1[0ª.sO¤,

```

Try it online.

**Explanation:**

```
$         # Push 1 and the input
 F        # Pop and loop the input amount of times:
  0       #  Push a 0
   )      #  Wrap the entire stack into a list
    .s    #  Get the suffixes of this list
      O   #  Sum each inner suffix-list
       `  #  Pop and push all values to the stack
          # (after the loop, the top value is output implicitly as result)

```

```
1         # Start with 1
 [        # Loop indefinitely:
  0ª      #  Append 0 to the current list (convert an integer to a digit-list
          #  before appending, which happens for the 1 in the first iteration)
    .s    #  Get the suffixes of this list
      O   #  Sum each inner suffix-list
       ¤  #  Push the last integer (without popping the list)
        , #  Pop and output it with trailing newline

```
> 3 votes

# Answer
# Haskell + hgl, 22 bytes

```
he<ix(rS(+)<he*^rv)[1]

```

This uses the by Chai Wah Wu that everyone else is using. It produces an infinite list of the results in order.

## Explanation

First we have the iterative step `rS(+)<he*^rv` this gives the cumulative sums of the first element with the list reversed. With `ix` we iterate this infinitely starting with `[1]`. Then from there we just get the head of every element in the list with `he`.

# New method, 25 bytes

```
cn(mF~<lt3<<fce)<tv e1<e1

```

This method isn't new, but it hasn't been used here yet and it's pretty neat. And it's rather close to edging out the Chai Wah Wu method.

## Explanation

From the comments on the OEIS:

```
Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that no three terms are equal. [Theorem 7 of Corteel, Martinez, Savage, and Weselcouch] - Eric M. Schmidt, Jul 17 2017
```

First we use `e1` to get the range from \\$1\\$ to \\$n\\$. The next step is `tv e1` which is a little hard to explain, because `tv` is fundamentally a pretty weird operation. Instead we can talk about the equivalent but *slightly* longer `sQ<m e1`. `m e1` maps `e1` across the lists to creates ranges of increasing size. `sQ` creates a list of ways to pick one element in order from each list.

So the result now is all the non-negative integer sequences whose values are smaller than their indexes. Now we count all the ones that don't have any value repeated 3 times. `cn` will take a predicate and count the number of elements satisfying that predicate so we use that. Now we just need a predicate that says "Contains no element 3 or more times". One way to do this is

```
pred x = mF(lt3<fce x)x

```

Here `fce` counts the number of times an element appears in a list, add it with `lt3` and `lt3<fce x` says "does this element appear less than three times in `x`". We use `mF` to collect the result of running this over every element of `x`, so it says "does all the elements of `x` appear less than 3 times in `x`". Now we use a bit of monad magic t make this point free and we have `mF~<lt3<<fce`.

# Naive method, 31 bytes

```
dv2<P1<cn(fo<pa nq<pa cp)<pm<e0

```

## Explanation

First we get all the permutations of size \\$n+1\\$. Now we count the satisfactory permutations with `cn`. To determine if a permutation is satisfactory we first compare consecutive elements `pa cp`. This gets us the direction of each change between elements, if there are two consecutive equal elements now that means that there is a run of 3 which is monotonic, and thus that permutation is invalid, so we use `pa nq` to compare the consecutive elements and `fo` to ensure they are all unequal.

Once we've counted those we need to divide by two, rounding up. Do do this I do the old plus 1, divide by 2 trick. `dv2>P1`

# Reflections

The nice thing about this problem is there are many ways to approach it. Since I've tried this so many ways I have gotten quite a bit of useful reflection out of this.

### Reflections on the Chai Wah Wu method

Overall this is the method with the least room for improvement. hgl doesn't seem to have any major gaps.

* `rS(+)` which gives the cumulative sums might be worth having a short hand. Hard to say.
* `[1]` is a little long, but I'm not sure if it's worth having a 2 bytes shorthand especially, when `[1]` never needs any whitespace padding while an alias would.

### Reflections on the new method

* While I was working on this I found a bug with `mL` and related functions. It wouldn't have hurt this answer even if I went with the strategy that used those functions, but it was confusing and should be fixes.
* There aren't really many functions having to do with sub-sequences. Originally I had tried to get all the subsequences longer than 3 and check that none of them contained only 1 type of element. However the only subsequence function was `ss` which just gets all the subsequences. If I had a function `ss3` which gets subsequences of size 3, then this could be
```
cn(no lq<ss3)<tv e1<e1

```
which would have been 3 bytes shorter tying it with the shortest method. But moreover there should just be more than one function dealing with sub-sequences.

### Relfections on the naive method

* There should be a shorthand for "all permutations of n elements". `pm<e1` is the shortest way to achieve that right now. Would save 2 bytes overall.
* It might also be nice to have a "permutations such that" function, however it would need to be 2 bytes to save anything for this answer.
* The naive method uses `pa cp`, and it's not even the first time I've used `pa cp`. The alternative answer here uses `pa cp` and this change would have saved bytes there too. With a 3 byte name this would save 2 bytes here and 2 bytes on that answer.
* `dv2<P1` is abysmal. There should be a built in for integer division rounding up. It would save another 3 bytes on the naive approach, which if combined with the above would put it much more on par with other methods.
* Doesn't make a difference here, but for a short bit I was frustrated that while we have `ce`, which counts the number of elements equal to some element, we don't have something which counts elements *not* equal to some element. Wouldn't have saved bytes here, but it's worth having.
> 3 votes

# Answer
# HOPS, 7 bytes

```
bous(1)
```

Attempt This Online!

This sequence is the Boustrophedon transform of the sequence \\$1,0,0,0,\dots\\$.

HOPS is an extremely powerful language for integer sequences. To print the first 20 terms (0-indexed) of the sequence, just run `hops --prec=20 "bous(1)"`
> 3 votes

# Answer
# Factor, 50 bytes

```
[ { 1 } [ 0 suffix reverse cum-sum ] repeat last ]

```

Try it online!

Returns the (1-indexed) \\$n\\$th term in the sequence. It uses dingledooper's method, but a comment by @Neil is what I based this answer on: "zero-prefixed cumulative sum of reverse of previous row."
> 2 votes

# Answer
# C (gcc), <sup>~~106~~</sup> 105 bytes

```
*a;*b;c;i;j;f(n){a=calloc(n,8);for(*a=i=1;n/i;++i,a=b)for(b=calloc(n,8),j=i,c=0;j--;)b[i-j]=c+=a[j];n=c;}

```

Try it online!

*Uses the same method dingledooper explains in his Python answer.*
*Saved a byte thanks to ceilingcat!!!*

Inputs a positive integer \\$n\\$.
Returns the \\$1\\$-based \\$n^\text{th}\\$ element of the sequence.
> 2 votes

# Answer
# JavaScript (V8), 55 bytes

A port of dingledooper's algorithm.

A full program that prints the sequence forever.

```
for(a=[s=1];;)a=[s,...a.reverse(print(s)).map(x=>s+=x)]

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 19 bytes

```
2Abs@PolyLog[-#,I]&

```

Try it online!

Equivalent to the PARI/GP answer by alephalpha, but I first came across this representation in Peter Luschny's An introduction to the Bernoulli function.
> 2 votes

# Answer
# Vyxal, 11 bytes

```
ɾṖƛ¯±¯A;∑½⌈

```

Try it Online!

The `½⌈` is because of the requirement to handle reversed lists.

```
ɾṖ          # Permutations of 1...n
  ƛ    ;∑   # Count where...
     ¯      # Deltas of...
    ±       # Signs of ...
   ¯        # Deltas
      A     # Are all nonzero
         ½⌈ # Halve the final result and round up

```

The is-alternating code `¯±¯A` works because, for example with `[1, 6, 2, 4, 3]`:

```
¯    # Deltas - [5, -4, 2, -1] - Signs should be alternating
 ±   # Signs - [1, -1, 1, -1] - Should be list of alternating 1s and -1s
  ¯  # Deltas - [-2, 2, -2] - If there are two consecutive equal values in ^ there should be a 0
   A # All - 1 - if and only if there's no zeroes in ^ the list is alternating.

```
> 1 votes

---
Tags: code-golf, sequence, number-theory, combinatorics, permutations
---