title: A Capital Cipher

text:
# Question
Title: A Capital Cipher
Your task is to decipher a non-empty string consisting of printable ASCII characters in the range **\[32..126\]**.

Reading the string character per character:

* each time you encounter a letter in lowercase, associate it with the next letter in uppercase, starting with **'A'**
* each time you encounter a letter in uppercase, replace it with the letter in lowercase it's associated with
* other characters do not require any special processing and are just left unchanged

## Example

For the input string `"endlAsEBAEE"`:

* Associate `e` to `A`, `n` to `B`, `d` to `C` and `l` to `D`
* Replace `A` with `e`
* Associate `s` to `E`
* Replace `EBAEE` with `sness`

The final output is `"endlessness"`.

## Clarifications and rules

* The input string is guaranteed to contain each lowercase letter at most once. All further instances will be replaced with the corresponding capital letter.
* The input string is guaranteed to be valid. (You will not encounter a capital letter that is not yet associated with a lowercase letter.)
* Once a capital letter has been associated to a lowercase letter, it may or may not be used later in the string. For instance, `C` and `D` are not used in the above example.
* This is , so the shortest answer in bytes wins!

## Test cases

**Inputs:**

```
abcd
honk! ABCD!
abrAcAdABCA
endlAsEBAEE
helCo wDrCd!
dermatoglyphics
progBamFinD AuzJles & cCdL DCKf
sphinx of black quKrtz, jOdge my vGw. K NODLM IPGZE HGF SOWBA GYVP QCV JKRX TGU.
petBr AiABD AEckBd a ABFG of AEFGlBH ABAABDs. hJw mIny AEFGLBH ABAABDM HEH ABCBD AEABD AEFG?

```

**Answers:**

```
abcd
honk! honk!
abracadabra
endlessness
hello world!
dermatoglyphics
programming puzzles & code golf
sphinx of black quartz, judge my vow. a quick brown fox jumps over the lazy dog.
peter piper picked a peck of pickled peppers. how many pickled peppers did peter piper pick?

```

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

```
fØaØA,y

```

Try it online!

### How it works

```
fØaØA,y  Main link. Argument: s (string)

 Øa      Yield the lowercase alphabet.
f        Filter; keep only characters that appear in the lowercase alphabet.
          Call the result r.
   ØA    Yield the uppercase alphabet (u).
     ,   Pair; yield [u, r].
      y  Translate s, using the substitutions in [u, r].

```

# Answer
> 4 votes
# 05AB1E, 6 bytes

Code:

```
AÃAus‡

```

Uses the **05AB1E** encoding. Try it online!

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

```
s=>s.replace(/[A-Z]/g,c=>s.match(/[a-z]/g)[parseInt(c,36)-10])

```

Each capital letter is converted to its base 36 value, less 10.

We then match on the lowercase letter that's at that index.

```
let f=

s=>s.replace(/[A-Z]/g,c=>s.match(/[a-z]/g)[parseInt(c,36)-10])

console.log(f('abcd'))
console.log(f('abrAcAdABCA'))
console.log(f('endlAsEBAEE'))
console.log(f('helCo wDrCd!'))
console.log(f('progBamFinD AuzJles & cCdL DCKf'))
console.log(f('sphinx of black quKrtz, jOdge my vGw. K NODLM IPGZE HGF SOWBA GYVP QCV JKRX TGU.'))
console.log(f('petBr AiABD AEckBd a ABFG of AEFGlBH ABAABDs. hJw mIny AEFGLBH ABAABDM HEH ABCBD AEABD AEFG?'))
```

# Answer
> 2 votes
# Pyth, 36 bytes

```
JKr1GVQI&}NG!}NH=XHNhK=tK)p?}NJ@_HNN

```

Try it here

### Explanation

```
JKr1GVQI&}NG!}NH=XHNhK=tK)p?}NJ@_HNN
JKr1G                                  Let J and K be the uppercase alphabet.
     VQ                                For each character in the input...
       I&}NG!}NH         )             ... if the character is lowercase and not
                                       yet in H, ...
                =XHNhK                 ... add the letter and the next uppercase
                                       letter to H...
                      =tK              ... and move to the next uppercase letter.
                          p?}NJ@_HNN   Print either the next character or the
                                       letter it represents.

```

# Answer
> 2 votes
# Stax, 11 bytes

```
Ñ·í=Üò°f1èb

```

Run and debug it

# Answer
> 2 votes
# , 79 bytes

```
function(x){s=utf8ToInt(x)
s[j]=s[s>96&s<123][s[j<-s>64&s<91]-64]
intToUtf8(s)}

```

Try it online!

# Answer
> 2 votes
## Perl 5 with `-p`, 27 bytes

```
eval"y/A-Z/".y/a-z//cdr."/"

```

Try it online!

-2 bytes thanks to @breadbox!

# Answer
> 2 votes
# Z80Golf, 37 bytes

```
00000000: 2505 cd03 8030 0176 fe7b 300c fe61 3011  %....0.v.{0..a0.
00000010: fe5b 3004 fe41 3003 ff18 e7d6 414f 0a18  .[0..A0.....AO..
00000020: f777 2318 f3                             .w#..

```

Try it online!

z80 does pretty good at this! Here is a disassembly:

```
  dec h         ; HL = cipher write pointer
  dec b         ; BC = cipher read pointer
                ; meaning of 'A'..'Z' is written to $ff00~$ff19
next:
  call $8003    ; getchar
  jr nc, ok     ; not EOF?
  halt
ok:
  cp '{'
  jr nc, other  ; a ≥ '{'
  cp 'a'
  jr nc, lower  ; 'a' ≤ a ≤ 'z'
  cp '['
  jr nc, other  ; '[' ≤ a ≤ '`'
  cp 'A'
  jr nc, upper  ; 'A' ≤ a ≤ 'Z'
other:
  rst $38
  jr next
upper:
  sub 'A'
  ld c, a
  ld a, (bc)
  jr other
lower:
  ld (hl), a
  inc hl
  jr other

```

We point both HL and BC at the `$ff00` range with `dec`, and use `rst $38` as a short alternative to `call $8000`, but otherwise there isn't much trickery going on.

# Answer
> 1 votes
# Retina, 25 bytes

```
~["T`L`"|""L$`[a-z]
$&-$&

```

Try it online! Explanation:

```
[a-z]

```

Match lowercase letters.

```
$`
$&-$&

```

Replace each letter with a degenerate range of itself. (This prevents the later transliteration from treating it as a character class; backslash can't be used because some lower case letters have a special meaning after a backslash.)

```
["T`L`"|""L

```

List the degenerate ranges, but without line separators, and with a preceding `T`L``.

```
~

```

Evaluate the resulting transliteration program on the original input.

# Answer
> 1 votes
# Python 2, 78 bytes

```
lambda s:''.join('@'<c<'['and filter(str.islower,s)[ord(c)-65]or c for c in s)

```

Try it online!

# Answer
> 1 votes
# Java (JDK 10), 109 bytes

```
s->{var r=s.replaceAll("[^a-z]","");for(char i=64;i++<64+r.length();)s=s.replace(i,r.charAt(i-65));return s;}

```

Try it online!

# Answer
> 1 votes
# C (gcc), 105 bytes

```
C;f(char*Z){for(char*z=--Z,c,*s;c=*++z;putchar(c))for(C=64,s=Z;*z>64&91>*z&&C^*z;c=*s)C+=*++s>96&*s<123;}

```

Try it online!

# Answer
> 0 votes
# Jelly, 11 bytes

```
ØAi
Çị¥¹Ç?€

```

Try it online!

# Answer
> 0 votes
# Pyth, 7 bytes

Fork of Dennis' brilliant Jelly answer

```
XQr1G@G

```

All testcases.

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


title: Number the positive rationals

text:
# Question
Title: Number the positive rationals
The positive rational numbers can be shown to be numerable with the following process:

1. Zero has the ordinal 0
2. Arrange the other numbers in a grid so that row a, column b contains a/b
3. Plot a diagonal zig-zag top right to bottom left
4. Keep a running tally of the unique numbers encountered along the zig-zag

Here's a picture of the zig-zag:

So, the numbers encountered are, in order

```
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, 6/1, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 2/6, 3/5, 4/4, 5/3 ...

```

And the simplified, unique numbers encountered are

```
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3, ...

```

# Challenge:

* Given *two* greater-than-zero integers **p** and **q**, output the **ordinal number** of p/q
* p and q are not necessarily co-prime
* Shortest code wins
* Standard loopholes are prohibited

## Test cases:

Here are the first 24 rational numbers encountered, and the desired output for each:

```
1/1: 1
2/1: 2
1/2: 3
1/3: 4
2/2: 1
3/1: 5
4/1: 6
3/2: 7
2/3: 8
1/4: 9
1/5: 10
2/4: 3
3/3: 1
4/2: 2
5/1: 11
6/1: 12
5/2: 13
4/3: 14
3/4: 15
2/5: 16
1/6: 17
1/7: 18
2/6: 4
3/5: 19

```

And, for further test cases, here are the 200 first positive rational numbers in order:

```
1, 2, 1/2, 1/3, 3, 4, 3/2, 2/3, 1/4, 1/5,
5, 6, 5/2, 4/3, 3/4, 2/5, 1/6, 1/7, 3/5, 5/3,
7, 8, 7/2, 5/4, 4/5, 2/7, 1/8, 1/9, 3/7, 7/3,
9, 10, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9,
1/10, 1/11, 5/7, 7/5, 11, 12, 11/2, 10/3, 9/4, 8/5,
7/6, 6/7, 5/8, 4/9, 3/10, 2/11, 1/12, 1/13, 3/11, 5/9,
9/5, 11/3, 13, 14, 13/2, 11/4, 8/7, 7/8, 4/11, 2/13,
1/14, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15, 16,
15/2, 14/3, 13/4, 12/5, 11/6, 10/7, 9/8, 8/9, 7/10, 6/11,
5/12, 4/13, 3/14, 2/15, 1/16, 1/17, 5/13, 7/11, 11/7, 13/5,
17, 18, 17/2, 16/3, 15/4, 14/5, 13/6, 12/7, 11/8, 10/9,
9/10, 8/11, 7/12, 6/13, 5/14, 4/15, 3/16, 2/17, 1/18, 1/19,
3/17, 7/13, 9/11, 11/9, 13/7, 17/3, 19, 20, 19/2, 17/4,
16/5, 13/8, 11/10, 10/11, 8/13, 5/16, 4/17, 2/19, 1/20, 1/21,
3/19, 5/17, 7/15, 9/13, 13/9, 15/7, 17/5, 19/3, 21, 22,
21/2, 20/3, 19/4, 18/5, 17/6, 16/7, 15/8, 14/9, 13/10, 12/11,
11/12, 10/13, 9/14, 8/15, 7/16, 6/17, 5/18, 4/19, 3/20, 2/21,
1/22, 1/23, 5/19, 7/17, 11/13, 13/11, 17/7, 19/5, 23, 24,
23/2, 22/3, 21/4, 19/6, 18/7, 17/8, 16/9, 14/11, 13/12, 12/13,
11/14, 9/16, 8/17, 7/18, 6/19, 4/21, 3/22, 2/23, 1/24, 1/25

```

Shout out to the inverse question, where the first move is down so you can't use the answers to generate additional test cases.

# Answer
> 4 votes
# Jelly,  ~~21~~  20 bytes

Probably beatable by a number of bytes using some clever mathematics...

```
:g/
ÇµSRRUĖ€UÐeẎÇ€Qi

```

A monadic link accepting a list of `[p,q]` which returns the natural number assigned to `p/q`.

**Try it online!** Or see the test-suite.

### How?

First note that the **Nth** diagonal encountered contains all of the grid's rational numbers for which the sum of the numerator and denominator equals **N+1**, so given a function which reduces a `[p,q]` pair to simplest form (`[p/gcd(p,q),q/gcd(p,q)]`) we can build the diagonals as far as need be\*, reduce all the entries, de-duplicate and find the index of the simplified input.

* actually one further here to save a byte

```
:g/ - Link 1, simplify a pair: list of integers, [a, b]
  / - reduce using:
 g  - Greatest Common Divisor -> gcd(a, b)
:   - integer division (vectorises) -> [a/gcd(a,b), b/gcd(a,b)]

ÇµSRRUĖ€UÐeẎÇ€Qi - Main Link: list of integers, [p, q]
Ç                - call last Link as a monad (simplify)
 µ               - start a new monadic chain (call that V)
  S              - sum -> the diagonal V will be in plus one
   R             - range -> [1,2,3,...,diag(V)+1]
    R            - range (vectorises) -> [[1],[1,2],[1,2,3],...,[1,2,3,...,diag(V)+1]]
     U           - reverse each       -> [[1],[2,1],[3,2,1],[diag(V)+1,...,3,2,1]]
      Ė€         - enumerate €ach     -> [[[1,1]],[[1,2],[2,1]],[[1,3],[2,2],[3,1]],[[1,diag(V)+1],...,[diag(V)-1,3],[diag(V),2],[diag(V)+1,1]]]
         Ðe      - apply only to the even indexed items:
        U        -   reverse each     -> [[[1,1]],[[2,1],[1,2]],[[1,3],[2,2],[3,1]],[[4,1],[3,2],[2,3],[1,4]],...]
           Ẏ     - tighten            -> [[1,1],[2,1],[1,2],[1,3],[2,2],[3,1],[4,1],[3,2],[2,3],[1,4],...]
            Ç€   - for €ach: call last Link as a monad (simplify each)
                 -                    -> [[1,1],[2,1],[1,2],[1,3],[1,1],[3,1],[4,1],[3,2],[2,3],[1,4],...]
              Q  - de-duplicate       -> [[1,1],[2,1],[1,2],[1,3],[3,1],[4,1],[3,2],[2,3],[1,4],...]
               i - index of V in that list

```

# Answer
> 3 votes
# Perl 6,  ~~94~~  90 bytes

```
->\p,\q{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first(p/q,:k)+1}

```

Test it

```
{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique.first($^p/$^q):k+1}

```

Test it

This basically generates the entire sequence of values, and stops when it finds a match.

## Expanded:

```
{  # bare block lambda with placeholder parameters $p,$q

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            …
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            …
            1      # finish at one
          )

        }
        … * # never stop generating values
      )

    Z/   # zip using &infix:« /  » (generates Rats)

      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            …
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            …
            1
          )
        }
        … * # never stop generating values
      )

  ).unique            # get only the unique values
  .first( $^p / $^q ) # find the first one that matches the input
  :k                  # get the index instead (0 based)
  + 1                 # add one               (1 based)
}

```

---

`({1…($+=2)…1}…*)` generates the infinite sequence of numerators (`|(…)` is used above to flatten)

```
(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)
…

```

`(1,{1…(($||=1)+=2)…1}…*)` generates the infinite sequence of denominators

```
1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)
…

```

# Answer
> 3 votes
# Python 3, ~~157~~, ~~146~~, ~~140~~, 133 bytes

```
def f(p,q):a=[(i+i-abs(j-i-i))/(abs(j-i-i+.5)+.5)for i in range(p+q)for j in range(4*i)];return sorted(set(a),key=a.index).index(p/q)

```

Try it online!

won 11 bytes thanks to Jonathan Frech

won 6 more bytes and then 7 thanks to Chas Brown

# Answer
> 3 votes
# Python 2, ~~157~~ ~~144~~ ~~137~~ ~~134~~ ~~126~~ 125 bytes

```
def f(p,q):a=[((j-i)/(i+1.))**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted(set(a),key=a.index).index(p*1./q)

```

Try it online!

4 bytes saved due to Mr. Xcoder; 1 byte from Jonathon Frech.

As noted by Mr. Xcoder, we can do a bit better in Python 3 since, amongst other things, integer division defaults to float results, and we can more easily unpack `list`s:

### Python 3, 117 bytes

```
def f(p,q):a=[((j-i)/-~i)**(j%-2|1)for j in range(p-~q)for i in range(j)];return-~sorted({*a},key=a.index).index(p/q)

```

Try it online!

# Answer
> 2 votes
# J, 41, 35, 30 bytes

*-11 bytes thanks to FrownyFrog*

```
%i.~0~.@,@,[:]`|./.[:%/~1+i.@*

```

Try it online!

# original 41 bytes post with explanation

```
%>:@i.~[:([:~.@;[:<@|.`</.%"1 0)~(1+i.@*)

```

## ungolfed

```
% >:@i.~ [: ([: ~.@; [: <@|.`</. %"1 0)~ 1 + i.@*

```

## explanation

```
                  +
                  | Everything to the right of this
                  | calculates the list
p (left arg)      |                                      create the
divided by q      |                                      diagonals.  yes,
      (right)     |                                     +this is a         +create this list
   |              |        ++ finally rmv ^alternately  |primitive ADVERB  |1..(p*q), and pass
   |   + the index          | the boxes,  |box, or      |in J              |it as both the left
   |   | of that  |         | and remove  |reverse and  |                  |and right arg to the
   |   | in the   |         | any dups    |box, each    |                  |middle verb, where each
   |   | list on  |         |             |diagonal     |                  |element will divide the
   |   | the right|         |             |             |       +----------+entire list, producing
   |   | plus 1   |         |             |             |       |          |the undiagonalized grid
   |   |          |         |             |             |       |          |
   |   |          |         |             |             |       |          |
   |   |          +         |             |             |       |          |
  ┌+┬──|──────────┬─────────|─────────────|─────────────|───────|──────────|─────────────┐
  │%│┌─+───────┬─┐│┌──┬─────|─────────────|─────────────|───────|────────┬─|────────────┐│
  │ ││┌──┬─┬──┐│~│││[:│┌────|─────────────|─────────────|───────|─────┬─┐│┌+┬─┬────────┐││
  │ │││>:│@│i.││ │││  ││┌──┬|───────┬─────|─────────────|───────|────┐│~│││1│+│┌──┬─┬─┐│││
  │ ││└──┴─┴──┘│ │││  │││[:│+──┬─┬─┐│┌──┬─|─────────────|─┬─────|───┐││ │││ │ ││i.│@│*││││
  │ │└─────────┴─┘││  │││  ││~.│@│;│││[:│┌|───────────┬─+┐│┌─┬─┬+──┐│││ │││ │ │└──┴─┴─┘│││
  │ │             ││  │││  │└──┴─┴─┘││  ││+────────┬─┐│/.│││%│"│1 0││││ ││└─┴─┴────────┘││
  │ │             ││  │││  │        ││  │││┌─┬─┬──┐│<││  ││└─┴─┴───┘│││ ││              ││
  │ │             ││  │││  │        ││  ││││<│@│|.││ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │││└─┴─┴──┘│ ││  ││         │││ ││              ││
  │ │             ││  │││  │        ││  ││└────────┴─┘│  ││         │││ ││              ││
  │ │             ││  │││  │        ││  │└────────────┴──┘│         │││ ││              ││
  │ │             ││  │││  │        │└──┴─────────────────┴─────────┘││ ││              ││
  │ │             ││  ││└──┴────────┴────────────────────────────────┘│ ││              ││
  │ │             ││  │└──────────────────────────────────────────────┴─┘│              ││
  │ │             │└──┴──────────────────────────────────────────────────┴──────────────┘│
  └─┴─────────────┴──────────────────────────────────────────────────────────────────────┘

```

Try it online!

# Answer
> 2 votes
# Python 3, 121 bytes

```
import math
def o(x,y):
 p=q=n=1
 while x*q!=p*y:a=p+q&1;p+=1+a*~-~-(p<2);q+=1-~-a*~-~-(q<2);n+=math.gcd(p,q)<2
 return n

```

# Answer
> 2 votes
# Rust, 244 bytes

I created a simple formula to find the "plain" ordinal of a "plain" zigzag, without the constraints of the puzzle, using triangular numbers formulas: https://www.mathsisfun.com/algebra/triangular-numbers.html . This was modified with modulo 2 to account for the zig-zags flipping their direction each diagonal row in the puzzle. This is function h()

Then for the main trick of this puzzle: how to 'not count' certain repeating values, like 3/3 vs 1/1, 4/2 vs 2/1, in the zig-zag trail. I ran the 1-200 examples, and noticed the difference between a plain zig-zag triangular counter, and the one the puzzle wishes for, has a pattern. The pattern of "missing" numbers is 5, 12, 13, 14, 23, etc, which resulted in a hit in the OEIS. It is one described by Robert A Stump, at https://oeis.org/A076537 , in order to "deduplicate" numbers like 3/3, 4/2, and 1/1, you can check whether GCD\>1 for the x,y of all "previous" ordinals in the zigzag. This is the 'for' loops and g() which is the gcd.

I guess with some builtin gcd it would have been shorter, but I kind of couldn't find one very easily (im kind of new at Rust and Integer confused me), and I like the fact that this one uses straight up integer arithmetic, and no builtins or libraries of any kind.

```
fn f(x:i64,y:i64)->i64 {
        fn h(x:i64,y:i64)->i64 {let s=x+y;(s*s-3*s+4)/2-1+(s+1)%2*x+s%2*y}
        fn g(x:i64,y:i64)->i64 {if x==0 {y} else {g(y%x,x)}}
        let mut a=h(x,y);
        for i in 1..x+y {for j in 1..y+x {if h(i,j)<h(x,y) && g(i,j)>1 {a-=1;}}}
        a
}

```

# Answer
> 1 votes
# JavaScript (ES6), 86 bytes

Takes input in currying syntax `(p)(q)`.

```
p=>q=>(g=x=>x*y?x*q-y*p?g(x+d,g[x/=y]=g[x]||++n,y-=d):n:g(x+!~d,y+=!~(d=-d)))(d=n=y=1)

```

Try it online!

# Answer
> 0 votes
# Javascript, 79 bytes

```
a=(p,q)=>p*q==1?1:1+((p+q)%2?q==1?a(p-1,q):a(p+1,q-1):p==1?a(p,q-1):a(p-1,q+1))

```

(I am new to code golfing, so this can probably be improved easily)

## Explanation

```
let a = (p, q) => p * q == 1 // If they are both 1
    ? 1
    // Do a recursive call and increment the result by 1
    : 1 + (
        (p + q) % 2 // If on an even-numbered diagonal
        ? q == 1 // If at the beginning of the diagonal
            ? a(p - 1, q) // Go to previous diagonal
            : a(p + 1, q - 1) // Go one back
        : p == 1 // rougly the same
            ? a(p, q - 1)
            : a(p - 1, q + 1)
    )

```

---
Tags: code-golf, rational-numbers
---


title: Execute a Superb Shuffle™

text:
# Question
Title: Execute a Superb Shuffle™
For the purposes of this question, a deck of cards is formatted in this way:

```
[
  "AS", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "10S", "JS", "QS", "KS",
  "AD", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "10D", "JD", "QD", "KD",
  "AH", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "10H", "JH", "QH", "KH",
  "AC", "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "10C", "JC", "QC", "KC",
  "J", "J"
]

```

Cards are always formatted as value, followed by suits. E.g. `AS` is the Ace of Spades. The two single J's are Jokers. We want to shuffle this deck of cards, but the shuffle must be Superb™.

A Superb Shuffle™ is one in which:

* No two cards (except Jokers) of the same suit are adjacent.
* No card (except Jokers) is adjacent to one of the same value.
* No card (except Jokers) is adjacent to one of an adjacent value (one higher or one lower in this order, A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Notice that Ace can not be adjacent to either a 2 or a King).
* The Jokers can be in any position.
* The definition of a Superb Shuffle™ *does not* require the cards to be in a different order each time they are shuffled. Which isn't very superb, but it is Superb™.

Because that's Superb™.

An example might be:

```
[
  "AS", "5D", "9H", "KC", "2D", "6H", "10C", "QS", "3H", "7C", "9S",
  "KD", "4C", "6S", "10D", "AC", "3S", "7D", "JH", "J", "4D", "8H",
  "QC", "AD", "5H", "9C", "JS", "2H", "6C", "8S", "QD", "3C", "5S",
  "9D", "KH", "2S", "6D", "10H", "J", "3D", "7H", "JC", "KS", "4H",
  "8C", "10S", "AH", "5C", "7S", "JD", "2C", "4S", "8D", "QH"
]

```

---

The challenge:

* Write some code to execute a superb shuffle
* Use any language.
* The input can be **either**:
    + a deck of cards as described above *in the same order*, as an array or other list structure.
    + No input (the code generates a deck of cards in that order)
* The output must be a full deck of cards in a Superb Shuffle™ as described above.
* Attempt to perform your Superb Shuffle™ in the smallest number of bytes.
* A link to an online interpreter such as Try It Online is preferred, but optional.

Happy shuffling!

# Answer
> 5 votes
# Japt, ~~6~~ ~~5~~ 4 bytes

Splits the input array into sub-arrays of every 16th element and flattens.

```
óG c

```

Try it

# Answer
> 34 votes
# Ruby, 31 bytes

```
->x{(0..53).map{|r|x[r*17%54]}}

```

Try it online!

### Explanation:

I'm picking one card, then skipping over the next 16 and start from the first card when I reach the last card of the deck. 17 and 54 are mutually prime, so I'm sure to pick all cards.

The 17th position is guaranteed to be a different suit and the difference in value is at least 2: the 13th (or 15th) card has the same value and a different suit, so by skipping other 4 (or 2), the value is right.

# Answer
> 11 votes
# Python 3, 21 bytes

```
lambda x:(x*17)[::17]

```

Try it online!

### Explanation:

The same idea as my Ruby answer, but even shorter in Python: I use 17 decks, and pick every 17th card.

# Answer
> 4 votes
# Java 10, ~~72~~ 65 bytes

```
d->{var r=d.clone();for(int i=54;i-->0;r[i*7%54]=d[i]);return r;}

```

Similar as *@GB*'s Ruby answer, but by using `i*7%54` on the result-array, instead of `i*17%54` on the input-array to save a byte.

Try it online.

**Explanation:**

```
d->{              // Method with String-array as both parameter and return-type
  var r=d.clone();//  Result-String, starting as a copy of the input
  for(int i=54;i-->0;
                  //   Loop `i` in the range (54, 0]
    r[            //    Set an item in the result-array at index:
      i*7%54      //     Index `i` multiplied by 7, and then take modulo-54
     ]=d[i]);     //    To the `i`'th item in the input-Deck
  return r;}      //  Return the result-Array

```

# Answer
> 4 votes
# JavaScript, 35 bytes

```
x=>x.map((a,i)=>i%2?a:x[(i+20)%54])

```

Try it online!

Taking an array of deck as input, and replacing each odd value with another card that is "20 cards" away on the deck.

# Answer
> 3 votes
# Perl 6, ~~21 20~~ 18 bytes

*Thanks to Brad Gilbert b2gills for -2 bytes*

```
{.[$++*17%$_]xx$_}

```

Try it online!

Yet another port of G B's answer. ~~Note that, while the global variable `$!` is not reset between functions, the value doesn't matter, since any order of the output is valid.~~ However, `$` *is* reset.

### Explanation:

```
{                } #Anonymous code block
             xx$_  #Repeat size of inputted array (54) times
 .[         ]      #Get from the inputted array, the value at index
    $++*17%$_         #The incremented variable, multiplied by 17, modded by size of the array

```

# Answer
> 3 votes
# JavaScript, 27

Another one based off of the ruby answer

```
d=>d.map((_,i)=>d[i*17%54])

```

Edited in an obvious shortening

# Answer
> 2 votes
# 05AB1E, ~~9~~ ~~7~~ 5 bytes

```
ā17*è

```

Port of *@GB*'s Ruby answer, so make sure to upvote him!

-2 bytes by printing each card with a new-line delimiter instead of wrapping it to a result-list
-2 bytes thanks to *@Mr.Xcoder*

Try it online.

**Explanation:**

```
ā        # 1-indexed length range [1 ... length_of_input_list (54)]
 17*     #  `k`: Multiply each index by 17
    è    #  And then replace each item with the 0-indexed `k`'th card of the input-list
         #  (with automatic wrap-around)

```

# Answer
> 2 votes
# T-SQL, 31 bytes

```
SELECT c FROM t ORDER BY i*7%54

```

If you don't care about an extra column in the output I can get it down to **29 bytes**:

```
SELECT*FROM t ORDER BY i*7%54

```

So you can verify my output is "Superb", here is the deck it produces:

```
 J, 5H,  8S, KH, 3D,  8C, JD, AS, 6H,  9S, AC, 4D, 9C, QD,
2S, 7H, 10S, 2C, 5D, 10C, KD, 3S, 8H,  JS, 3C, 6D, JC,
AH, 4S,  9H, QS, 4C,  7D, QC, 2H, 5S, 10H, KS, 5C, 8D,
KC, 3H,  6S, JH, AD,  6C, 9D,  J, 4H,  7S, QH, 2D, 7C, 10D

```

(Generated using the new SQL 2017 addition, `STRING_AGG`):

```
SELECT STRING_AGG(c,', ')WITHIN GROUP(ORDER BY i*7%54)FROM t

```

The hard part for me was not the select code, it was populating the input table (which is allowed for SQL per our IO rules).

Because SQL is inherently unordered (it only guarantees a certain order if you include an explicit `ORDER BY` clause), I had to include that original order as a field *i* in the input table *t*. This also means I can use it to sort, using the same "relatively prime" factor/mod process everyone else is using. I found that `i*7%54` worked just as well as `i*17%54`.

Here are the commands to set up and populate the input table *t*, based on my solution to this related question:

```
CREATE TABLE t (i INT IDENTITY(1,1), c VARCHAR(5))

--Insert 52 suited cards
INSERT t(c)
SELECT v.value+s.a as c
FROM STRING_SPLIT('A-2-3-4-5-6-7-8-9-10-J-Q-K','-')v,
     (VALUES('S',1),('D',2),('H',3),('C',4))s(a,b)
ORDER BY s.b

--Insert Jokers
INSERT t(c) SELECT 'J'
INSERT t(c) SELECT 'J'

```

# Answer
> 2 votes
# Jelly,  ~~5~~  4 bytes

```
s⁴ZẎ

```

**Try it online!**

Turns out the way ~~everyone else~~ *everyone else except The random guy* is doing it saves a byte :(
Credit to G B for their method.

---

The way I went...

```
ṙÐe20

```

**Try it online!**

### How?

Fix every other card and intersperse it with a rotation of the deck left by 20 places (18 and 22 places also work; furthermore so does either direction of rotation as well as fixing either odd or even cards)

```
ṙÐe20 - Link: list of the card strings (lists of characters)
   20 - place a literal twenty on the right
 Ðe   - apply to even indices:
ṙ     -   rotate left (by 20)

```

That is (using `T` for `10` and `rj` & `bj` for the `J`s):

```
input: AS 2S 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC rj bj
  ṙ20: 8D 9D TD JD QD KD AH 2H 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC rj bj AS 2S 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AD 2D 3D 4D 5D 6D 7D
ṙÐe20: AS 9D 3S JD 5S KD 7S 2H 9S 4H JS 6H KS 8H 2D TH 4D QH 6D AC 8D 3C TD 5C QD 7C AH 9C 3H JC 5H KC 7H bj 9H 2S JH 4S KH 6S 2C 8S 4C TS 6C QS 8C AD TC 3D QC 5D rj 7D

```

# Answer
> 2 votes
# PowerShell 3.0, ~~30~~ 26 Bytes

```
$args[(0..53|%{$_*17%54})]

```

<sup>-4 thanks to Mazzy</sup>
Old code at 30 bytes

```
param($d)0..53|%{$d[$_*17%54]}

```

Another port of G B's method.

# Answer
> 1 votes
# Charcoal, 8 bytes

```
Ｅθ§θ×¹⁷κ

```

Try it online! Link is to verbose version of code. Another port of @GB's Ruby answer. Explanation:

```
 θ          Input array
Ｅ           Map over elements
       κ    Current index
     ¹⁷     Literal 17
    ×       Multiply
   θ        Input array
  §         Cyclically index
            Implicitly print each result on its own line

```

# Answer
> 1 votes
# Red, 44 bytes

```
func[a][append/dup a a 16 prin extract a 17]

```

Try it online!

Another interpetation of G B's code. I append 16 copies of the deck to itself and then extract each 17th card.

---
Tags: code-golf, array, card-games
---


title: Dead Frog Walking

text:
# Question
Title: Dead Frog Walking
## Introduction

Jonny wants to play Frogger. However, he's not very good. In fact, he will only try to move forward, and only after the platforms have moved.

Find out if Jonny's frog manages to reach the end of the path or if it dies on its way.

## Challenge

The program will be receiving as input a Frogger grid composed by `0`s and `1`s, with the following format:

* The grid will be of a random width and length, and at least 3x3
* `1` represents platforms
* `0` represents water
* `F` represents the starting position of the frog
* Every first and last line of the grid will be composed by only `1`s, and will not move, and the frog `F` will be placed at random on the last line
* Every intermediate layer will always be moving, and will have a `<` or `>` at the end of every line indicating if it moves left or right

Replacing these symbols with your own is allowed, as long as they're all distinct and you specify the replacements in your answer.

The input may be in any compatible format (string with line breaks, array of strings, array of characters, ...).

## Challenge Rules

* Every turn, all platforms will move one square, based on the direction indicated by the `<` or `>` sign
* Platforms reappear on the other side of the grid if they get pushed off "screen"
* If the frog is on a moving platform, it will move along with it
* After that, the frog will jump one square towards the top row. The frog will move every turn.
* The frog dies if it jumps in water (`0`) or it touches the side of the grid along with a moving platform

Your program has to output a truthy value if the frog survives and a falsy value otherwise.

This is , so the shortest answer in bytes win. Standard loopholes apply.

## Examples

### Example 1

### Input

```
11111
00111>
00101<
1F111

```

### Output

`1`

### Execution

Turn 1:

```
11111
10011
01010
1F111

11111
10011
0F010
11111

```

Turn 2:

```
11111
11001
F0100
11111

11111
F1001
10100
11111

```

Turn 3:

```
11111
1F100
01001
11111

1F111
11100
01001
11111

```

### Example 2

### Input

```
11111
00100<
00100<
1F111

```

### Output

`0`

### Execution

Turn 1:

```
11111
01000
01000
1F111

11111
01000
0F000
11111

```

Turn 2:

```
11111
10000
F0000
11111

11111
F0000
10000
11111

```

Turn 3:

```
11111
00001
00001
11111

```

# Answer
# Python 2, ~~168~~ ~~165~~ ~~152~~ ~~145~~ ~~137~~ 129 bytes

```
s=input();x=s[-1].find('F');L=len(s[0]);i=k=1
for l in s[-2:0:-1]:d=('<'in l)%-2|1;k*=l[(x-d*i)%L]>'0'>-1<x+d<L;x+=d;i+=1
print k

```

Try it online!

Input format is a list of strings; characters having meanings as given in the problem statement.

### Explanation:

`i` is the turn number (starting with Turn 1); `x` is the position of the frogger at the start of that turn.

The row the frogger is about to step onto is the string `l` (note that via the slicing, these come in bottom to top order). `d=('<'in l)%-2|1` yields `-1` or `1` depending on the direction the row is moving.

Since this is the `i`th turn, that row will have shifted from it's original position by `i` bytes; and so the character the frogger is about to jump onto is `l[(x-d*i)%L]` where `L` is the width of the row, so we want that character to be equal to `'1'`; i.e., `>'0'`.

In addition, we want to check that the frogger will not be shifted off the edge at the beginning of the *next* turn; that is the function of expression `-1<x+d<L`.

These conditions are chained (since `'0'>-1` is always `True`); and if at any time the resulting expression is false, `k` will become (and then stay) `0`.

In any case, we update the frogger's position `x+=d` and bump the row number; then lather, rinse, repeat.
> 4 votes

# Answer
# Python 2, ~~246~~ ~~245~~ ~~244~~ 242 bytes

-3 byte thanks to Mr. Xcoder
-1 byte thanks to Jonathan Frech

```
m=input()
exec"""for i,r in enumerate(m):
 d=-int(min('1',r[-1]));q=r[d*2]
 if m[i+1:]:r=sum([r[d+1:d-1],[[q,' '][q<'L']]][::d-~d],[])+r[-1:]
 if'F'in r:j=r.index('F');r[j]='L';m[i-1][j]=min('F',m[i-1][j])
 m[i]=r
"""*~-len(m)
print'F'in m[0]

```

Try it online!

## Explanation

* `d` is the direction each layer will move
* `q` is the character that will be wrapped around
    + `[q,' '][q<'L']` will drop the frog off-screen
* `sum([r[d+1:d-1],[[q,' '][q<'L']]][::d-~d],[])+r[-1:]` will remove the last character (the direction), then remove the first character and append it or remove second last and prepend it (based on `d`), and append the direction back, effectively moving the entire row to the left/right.
* `if'F'in r:j=r.index('F');r[j]='L';m[i-1][j]=min('F',m[i-1][j])` will make the frog jump forward
* `min('F',m[i-1][j])` will make the frog fall in the water
* The characters comparison (`min` and `<`) follow the order `' ' < '0' < '1' < 'F' < 'L'`

The input will be a list of list of characters:
`' '` \- water
`'F'` \- frog
`'L'` \- plataform
`'0'` \- move the layer to the left
`'1'` \- move the layer to the right
> 1 votes

# Answer
# Java 8, ~~293~~ 277 bytes

```
a->{for(int l=a.length-1,x=a[l].indexOf('F'),y=l,i,t=a[0].length()-1,b;y>0;y--){for(i=l;i-->1;a[i]=a[i].endsWith("<")?a[i].substring(1,t+1)+a[i].charAt(0*(x-=b))+"<":a[i].charAt(t)+a[i].substring(0*(x+=b),t)+">")b=i==y?1:0;if(x<0|x>t||a[y].charAt(x)<49)return 0>1;}return 1>0;}

```

Uses the default characters as specified in the challenge description (`01F<>`).

Try it online.

**Explanation:**

```
a->{                         // Method with String-array parameter & boolean return-type
  for(int l=a.length-1,      //  Amount of rows minus 1
       x=a[l].indexOf('F'),  //  Start x-position of the frog
       y=l,                  //  Start y-position of the frog
       i,                    //  Index-integer
       t=a[0].length()-1,    //  Length of the rows minus 1
       b;                    //  Temp integer
       y>0;                  //  Loop as long as the frog hasn't reached the other side
       y--){                 //    Jump forward once after every turn
    for(i=l;l-->1;           //   Inner loop over all the moving rows
        ;a[i]=               //     After every iteration: Change the moving row to:
         a[i].endsWith("<")? //      If the current platform moves to the left:
          a[i].substring(1,t+1)
                             //       Last part of the platform
                             //        i.e. "00101<" → "0101"
          +a[i].charAt(0     //       Appended with the first character
                             //        i.e. "00101<" → '0'
            *(x-=b))         //       We are moving left, so subtract `b` from `x`
          +"<"               //       And append the direction "<" again
                             //        so "00101<" becomes "01010<"
         :                   //      Else (the platform moves to the right):
          a[i].charAt(t)     //       Take the last character
                             //        i.e. "00111>" → '1'
          +a[i].substring(0  //       And append the first part of the platform
                             //        i.e. "00111>" → "0011"
            *(x+=b),t)       //       We are moving right, so add `b` to `x`
          +">")              //       And append the direction "<" again
                             //        so "00111>" becomes "10011>"
      b=i==y?                //    If the frog is on the current row:
         1                   //     Set `b` to 1
        :                    //    Else:
         0;                  //     Set `b` to 0
    if(x<0|x>t               //   If the Frog is out of bounds
       ||a[y].charAt(x)<49)  //   Or jumped into the water
      return 0>1;}           //    Return false
  return 1>0;}               //  If the loop ended the frog made it to the other side,
                             //  so return true

```
> 0 votes

---
Tags: code-golf, array, decision-problem, grid
---


title: ASCII Hilbert Curve

text:
# Question
Title: ASCII Hilbert Curve
Given an integer `n` output the `n`th iteration of the Hilbert Curve in ASCII using the characters `_` and `|`.

Here are the first 4 iterations:

```
n=1
 _
| |

n=2
 _   _
| |_| |
|_   _|
 _| |_

n=3
 _   _   _   _
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _
| |___| |___| |

n=4
 _   _   _   _   _   _   _   _
| |_| | | |_| | | |_| | | |_| |
|_   _| |_   _| |_   _| |_   _|
 _| |_____| |_   _| |_____| |_
|  ___   ___  | |  ___   ___  |
|_|  _| |_  |_| |_|  _| |_  |_|
 _  |_   _|  _   _  |_   _|  _
| |___| |___| |_| |___| |___| |
|_   ___   ___   ___   ___   _|
 _| |_  |_|  _| |_  |_|  _| |_
|  _  |  _  |_   _|  _  |  _  |
|_| |_| | |___| |___| | |_| |_|
 _   _  |  ___   ___  |  _   _
| |_| | |_|  _| |_  |_| | |_| |
|_   _|  _  |_   _|  _  |_   _|
 _| |___| |___| |___| |___| |_

```

# Clarifications

* My question is similar to Draw the Hilbert Curve and Draw the Hilbert curve using slashes.
* The conversion between underscores (`_`) and vertical bars (`|`) is `u=2*v-1` where `u` is the number of `_`s and `v` is the number of `|`s.
* To maintain consistency with my original post the curve must start and end at the bottom.
* You can have a full program or a function.
* Output to stdout (or something similar).
* You can have leading or trailing white-spaces, the output just needs to line up so that it looks like the examples.
* This is code-golf so shortest answer in bytes wins.

# Answer
# Befunge, ~~444~~ ~~368~~ 323 bytes

```
&1>\1-:v
0v^*2\<_$00p>
_>:10p\:20pv^_@#-*2g00:+1,+55$
^!-<v*2g000<>$#<0>>-\:v
g2*^>>10g20g+v \ ^*84g_$:88+g,89+g,\1+:00
v#*!-1g02!g01_4^2_
>::00g2*-!\1-:10g-\20g-++>v
87+#^\#p01#<<v!`g01/2\+76:_
vv1-^#1-g01:\_$:2/20g`!
_ 2/^>:10g#vv#`g02/4*3:\+77
v>0p^^/2:/2_
<^2-1-g02</2`#*3:
0g+10p2*:^*3_1
! "#%$
%$"#!
 !!##%
|||_
 _ __

```

Try it online!

The typical approach to drawing the Hilbert Curve is to follow the path as a series of strokes and turns, rendering the result into a bitmap or some area of memory, and then writing out that rendering when the path is complete. This is just not feasible in Befunge when we only have 2000 bytes of memory to work with, and that includes the source of the program itself.

So the approach we've taken here is to come up with a formula that tells us exactly which character to output for a given x,y coordinate. To understand how this works, it's easiest to ignore the ASCII rendering to start with, and just think of the curve as made up of box characters: , , , , , and .

When we look at the curve like that, we can immediately see that right hand side is an exact mirror of the left hand side. Characters on the right can simply be determined by looking up their partner on the left, and reflecting it horizontally (i.e. occurrences of  and  are swapped, as are  and ).

Then looking at the bottom left corner, again we can see that the lower half is a reflection of the top half. Thus the characters on the bottom are simply determined by looking up their partner above, and reflecting it vertically (i.e. occurrences of  and  are swapped, as are  and ).

The remaining half of this corner is a little less obvious. The right hand block can be derived from a vertical reflection of the block diagonally adjacent to it.

And the left hand block can be derived from a vertical reflection of the block in the very top left of the full curve.

At this point, all we're left with is the top left corner, which is just another Hilbert Curve one iteration lower. In theory, we should now just need to repeat the process again, but there's a bit of a catch - at this level, the left and right halves of the block aren't exact mirrors of each other.

So at anything other than the top level, the bottom corner characters need to be handled as a special case, where the  character is reflected as , and the  character is reflected as .

But other than that, we really can just repeat this process recursively. At the last level we hardcode the top left character as , and the character below it as .

Now that we have a way to determine the shape of the curve at a particular x,y coordinate, how do we translate that into the ASCII rendering? It's actually just a simple mapping that translates each possible tile into two ASCII characters.

* becomes `_` (space plus underscore)
* becomes  (two spaces)
* becomes `|_` (vertical bar plus underscore)
* becomes  (vertical bar plus space)
* becomes  (again a vertical bar plus space)
* becomes `__` (two underscores)

This mapping isn't intuitive at first, but you can see how it works when looking at two corresponding renderings side by side.

And that's basically all there is to it. Actually implementing this algorithm in Befunge is another problem altogether, but I'll leave that explanation for another time.
> 8 votes

# Answer
# C, 267 bytes

```
const n=4,s=1<<n,a[]={1,-s,-1,s};l,p,q;
t(d){d&=3;p-q||printf("%.2s",&"__|      _|       |___ _|_| | | "[l*8+d*2]);p+=a[l=d];}
h(d,r,n){n--&&(h(d+r,-r,n),t(d+r),h(d,r,n),t(d),h(d,r,n),t(d-r),h(d-r,-r,n));}
main(){for(;p=s*s-s,l=1,q<s*s;++q%s||putchar(10))h(0,1,n),t(3);}

```

Try it online!

`h()` uses recursion to generate the strokes of hlibert curve. `t()` only prints out the stroke character if the pen position `p` is equal to the current output position `q`.

This is inefficient but simple.

If the curve starts at top-left, the code can be reduced to 256 bytes.
> 3 votes

---
Tags: code-golf, ascii-art, fractal
---


title: Up and down, up and down

text:
# Question
Title: Up and down, up and down
### Challenge:

Given a positive integer input **n**, create a vector that follows this pattern:

```
0  1  0 -1 -2 -1  0  1  2  3  2  1  0 -1 -2 -3 -4 -3 -2 -1 ... ±(n-1) ±n

```

Or, explained with words: The vector starts at `0`, and makes increments of `1` until it reaches the smallest odd positive integer that isn't part of the sequence, then it makes decrements until it reaches the smallest (in magnitude) even negative integer that isn't part of the sequence. It continues this way until `n` is reached. The sequence will end on positive `n` if `n` is odd, and negative `n` if `n` is even.

The output format is flexible.

### Test cases:

```
n = 1
0  1
-----------
n = 2
0  1  0 -1 -2
-----------
n = 3
0  1  0 -1 -2 -1  0  1  2  3
-----------
n = 4
0  1  0 -1 -2 -1  0  1  2  3  2  1  0 -1 -2 -3 -4
-----------
n = 5
0  1  0 -1 -2 -1  0  1  2  3  2  1  0 -1 -2 -3 -4 -3 -2 -1  0  1  2  3  4  5

```

You may choose to take the **n** zero-indexed. `n = 1` would then give `0 1 0 -1 -2`.

This is , so the shortest code in each language wins! Explanations are encouraged as always!

# Answer
# , ~~58~~ ~~54~~ ~~50~~ ~~48~~ 43 bytes

*-2 bytes thanks to MickyT*

```
function(n)diffinv(rep(1:n%%2*2-1,1:n*2-1))

```

Try it online!

```
function(n)
 diffinv(                           # take cumulative sum, starting at 0 of
             1:n%%2*2-1,            # a vector of alternating 1,-1
         rep(                       # repeated
                        1:n*2-1))   # 1, 3, 5, etc. times

```
> 10 votes

# Answer
# Perl 6,  ~~60~~  26 bytes

```
{flat {((1,-*...*)ZX*(-$++...0...$++)xx$_)}(),$_*($_%2||-1)}

```

Try it

```
{[...] (-1,-*...*)Z*0..$_}

```

Try it

## Expanded:

```
{  # bare block lambda with implicit parameter $_

  [...]  # reduce using &infix:«...» (sequence generator)

          ( -1, -* ... * ) # (-1, 1, -1, 1 ... *)

      Z*                   # zip multiplied with

          0 .. $_          # range up to and including input
}

```

`(-1,-*...*)Z*0..$_` generates the sequence `0 1 -2 3 -4 5`
> 8 votes

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

*Saved 2 bytes thanks to @Emigna*

```
Ýā®sm*Ÿ

```

Try it online!

My first 05AB1E answer (I think), so I may be missing some tricks...

### Explanation

```
Ý         # push range [0 ... n]   stack: [[0 ... n]]
 ā        # push range [1 ... len(prev)]  [[0 ... n], [1 ... n+1]]
  ®       # push value of register        [[0 ... n], [1 ... n+1], -1]
   s      # swap top two values           [[0 ... n], -1, [1 ... n+1]]
    m     # power                         [[0 ... n], [-1, 1, -1, 1, ...]]
     *    # multiply                      [[0, 1, -2, 3, -4, 5, ...]]
      Ÿ   # range interpolation           [[0, 1, 0, -1, -2, -1, ...]]

```

I have to thank @Dennis for the original usage of `Ÿ`, otherwise I ~~may not~~ probably would never have known about it...
> 7 votes

# Answer
# JavaScript (ES6), 56 bytes

```
f=(n,b=d=1,k=0)=>[k,...k-d*n?f(n,k-b?b:(d=-d)-b,k+d):[]]

```

Try it online!

### Commented

```
f = (               // f = recursive function taking:
  n,                //   n = input
  b =               //   b = boundary value, initialized to 1
  d = 1,            //   d = current direction, initialized to 1
  k = 0             //   k = current sequence value, initialized to 0
) =>                //
  [                 // update the sequence:
    k,              //   append the current value
    ...k - d * n ?  //   if |k| is not equal to |n|:
      f(            //     append the (spread) result of a recursive call:
        n,          //       use the original input
        k - b ?     //       if k has not reached the boundary value:
          b         //         leave b unchanged
        :           //       else:
          (d = -d)  //         reverse the direction
          - b,      //         and use a boundary of higher amplitude and opposite sign
        k + d       //       update k
      )             //     end of recursive call
    :               //   else:
      []            //     stop recursion and append nothing
  ]                 // end of sequence update

```
> 6 votes

# Answer
# Python 2, ~~69~~ ~~57~~ 56 bytes

```
f=lambda n:[0][n:]or f(n-1)+range(-n,n+1)[::n%2*2-1][2:]

```

Try it online!

For each `n` up to the `input` the `range(-n,n)` (inclusive) is calculated, inverted when `n` is an even number, has the fist two numbers (after the inversion) removed, and then appended to the output.
> 6 votes

# Answer
# 05AB1E, ~~15~~ 14 bytes

```
ÝDÉ·<*Ý€û˜ÔsF¨

```

Try it online!

**Explanation**

```
Ý                # push range [0 ... n]
 D               # duplicate
  É·<            # (x % 2 == 1)*2-1 for each
     *           # multiply
      Ý          # range [0 ... a] for each
       €û        # palendromize each
         ˜       # flatten
          Ô      # connected uniqueified
           sF¨   # remove the last n elements

```
> 6 votes

# Answer
# Jelly, ~~11~~ 9 bytes

```
²ḶÆ½-*0;Ä

```

Try it online!

### How it works

```
²ḶÆ½-*0;Ä  Main link. Argument: n

²          Square; yield n².
 Ḷ         Unlength; yield [0, ..., n²-1].
  Æ½       Take the integer square root of each k in the range.
    -*     Compute (-1)**r for each integer square root r.
      0;   Prepend a zero.
        Ä  Accumulate; take the sums of all prefixes.

```
> 6 votes

# Answer
# Haskell, ~~48~~ 42 bytes

```
f n=0:[(-1)^i*x|i<-[0..n-1],x<-[1-i..i+1]]

```

Try it online!

*Thanks to Οurous for -1 byte*

Even though it's kind of obvious in hindsight, it took me a while to arrive at `(-1)^i*x` which is `x` when `i` is even and `-x` when `i` is odd. Previous iterations where:

```
(-1)^i*x
x-2*mod i 2*x
(-1)^mod i 2*x
[x,-x]!!mod i 2
(1-sum[2|odd i])*x

```
> 6 votes

# Answer
# Haskell, 43 bytes

```
f n=scanl(-)0[(-1)^k|k<-[1..n],_<-[2..2*k]]

```

Try it online!

Computes the negated cumulative sums of the list `[(-1)^k|k<-[1..n],_<-[2..2*k]]`, which is the first `n` rows of

```
[-1,
 +1, +1, +1,
 -1, -1, -1, -1, -1,
 +1, +1, +1, +1, +1, +1, +1…

```
> 6 votes

# Answer
# , 25 bytes

-5 bytes thanks to FrownyFrog!

```
>:@*:$i.;@(<@i:@*_1&^)@,]

```

Try it online!

# , 30 bytes

```
>:@*:{.;@([:(i:@*_1&^)&.>i.,])

```

Explanation:

`i.,]` creates list 0..n

`&.>` for each number in the list execute the verb in (...) and box the result (I need boxing because the results have different length)

`[:( _1&^)` find -1 to the `i`th power (-1 or 1)

`i:@*` make a list -n..n or n..-n, depending on the sign of the above

`;@` unbox

`>:@*:` find n^2 + 1

`}.` and take so many numbers from the list

Try it online!
> 4 votes

# Answer
# C# (.NET Core), ~~300~~ 167 bytes

I've never done any of these before, but this one seemed fun. I see why people use those "golfing" languages as 167 seems way higher than some of the other answers. But, you gotta go with what you know.

```
static int[] f(int n){if (n==1) return new int[]{0,1};var a=f(n-1);return a.Concat(a.Skip(a.Length-(n-1)*2).Select(x=>-x)).Concat(new int[]{(n%2)!=0?n:-n}).ToArray();}

```

Try it online!

```
// Recursive Worker Function
static public int[] f( int n )
{
    // Start with the simple case
    if ( n == 1 ) return new int[]{0,1};

    // Recusively build off of that
    var a = f(n-1);

    // To be added at the end
    int[] b = { (n%2) !=0 ? n : -n };

    // Skip some based on length
    int s = a.Length - (n-1)*2;

    // With the rest, multiply by -1 and then append to the end
    // And append the part
    return a.Concat( a.Skip(s).Select( x => -x ) ).Concat( b ).ToArray();
}

```
> 4 votes

# Answer
# Python 2, ~~65~~ 56 bytes

```
r=k=0;exec'print r;r+=1-k**.5//1%2*2;k+=1;'*-~input()**2

```

The output format is a bit ugly. **:/**

Try it online!
> 3 votes

# Answer
# Java 8, ~~85~~ ~~83~~ 79 bytes

```
n->{for(int p=0,i=0;i<=n*n;p+=1-(int)Math.sqrt(i++)%2*2)System.out.println(p);}

```

-6 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
n->{                            // Method with integer parameter and no return-type
  for(int p=0,                  //  Set both `p` to 0
      i=0;i<=n*n;               //  Loop `i` in the range [0, `n*n`]
      p+=                       //    After every iteration, increase `p` by:
         1-                     //     1, minus:
           (int)Math.sqrt(i++)  //     The square-root of `i`, truncated to its integer
           %2*2)                //     Modulo 2, and multiplied by 2
     System.out.println(p);}    //   Print integer `p` with a trailing new-line

```
> 3 votes

# Answer
# , ~~48 46~~ 42 bytes

```
for(i in 1:scan())F=c(F,-(-1)^i*(2-i):i);F

```

Try it online!

A port of the Ruby answer by Kirill L. - and saved 6 bytes thanks to the same Kirill L.! Now shorter than Giuseppe's solution ;)

A port of this Octave answer by Luis Mendo using `approx` is less golfy. `n=n^2+1` can be replaced by `,,n^2+1`; or by `0:n^2+1`(positional argument `xout`) for the same byte count :

### , 56 bytes

```
f=function(n)approx((0:n)^2+1,-(-1)^(0:n)*0:n,n=n^2+1)$y

```

Try it online!
> 3 votes

# Answer
# APL (Dyalog Unicode), 17 bytes

```
+\0,¯1*⍳(/⍨)1+2×⍳

```

Try it online!

Golfed 2 bytes thanks to @FrownyFrog by converting to a train. See the older answer and its explanation below.

---

# APL (Dyalog Unicode), 19 bytes

```
+\0,∊⊢∘-\⍴∘1¨1+2×⍳⎕

```

Try it online!

(Uses `⎕IO←0`)

My first approach was to construct multiple ranges and concatenate them together, this easily went over 30 bytes. Then I started analysing the sequence

```
      +\⍣¯1⊢0  1  0 ¯1 ¯2 ¯1  0  1  2  3  2  1  0 ¯1 ¯2 ¯3 ¯4
0 1 ¯1 ¯1 ¯1 1 1 1 1 1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1

```

`+\⍣¯1` denotes the inverse cumulative sum

There is a repeating pattern of 1s and ¯1s, where the length of each consecutive sequence of 1s or ¯1s is 1+2×n. And each subsequence alternates between 1 and ¯1. What I can do now is to create the 1s and ¯1s list, and then scan by +

```
      ⍳4 ⍝ creates range 0..4
0 1 2 3
      2×⍳4
0 2 4 6
      1+2×⍳4
1 3 5 7
      ⍴∘1¨1+2×⍳4 ⍝ for-each create that many 1s
┌─┬─────┬─────────┬─────────────┐
│1│1 1 1│1 1 1 1 1│1 1 1 1 1 1 1│
└─┴─────┴─────────┴─────────────┘
      ⊢∘-\⍴∘1¨1+2×⍳4 ⍝ alternate signs
┌─┬────────┬─────────┬────────────────────┐
│1│¯1 ¯1 ¯1│1 1 1 1 1│¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1│
└─┴────────┴─────────┴────────────────────┘
      ∊⊢∘-\⍴∘1¨1+2×⍳4 ⍝ flatten
1 ¯1 ¯1 ¯1 1 1 1 1 1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1
      0,∊⊢∘-\⍴∘1¨1+2×⍳4
0 1 ¯1 ¯1 ¯1 1 1 1 1 1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1 ¯1
      +\0,∊⊢∘-\⍴∘1¨1+2×⍳4 ⍝ cumulative sum
0 1 0 ¯1 ¯2 ¯1 0 1 2 3 2 1 0 ¯1 ¯2 ¯3 ¯4

```
> 3 votes

# Answer
# Haskell, 47 bytes

```
(#0)
m#n|m>n=[-n..n]++map(0-)(m#(n+1))|1>0=[-m]

```

Try it online!
> 2 votes

# Answer
# MATL, ~~17~~ 15 bytes

*-2 bytes thanks to Luis Mendo!*

```
0i:oEqG:EqY"Ysh

```

Try it online!

Explanation for `n=3`:

```
0		% push 0
 i:		% read input as integer, push range
		% stack: [0, [1 2 3]]
   o		% modulo 2, stack: [0, [1 0 1]]
    Eq		% double and decrement, stack: [0, [1 -1 1]]
      G:	% push input and range again
		% stack: [0, [1 -1 1], [1 2 3]]
        Eq	% double and decrement,
		% stack: [0, [1 -1 1], [1 3 5]]
	  Y"	% run-length decoding
		% stack: [0, [1 -1 -1 -1 1 1 1 1 1]]
	    Ys	% cumulative sum
		% stack: [0, [1  0 -1 -2 -1  0  1  2  3]]
	      h	% horizontally concatenate
		% end of program, automatically print the stack

```
> 2 votes

# Answer
# Octave, ~~44~~ ~~42~~ 41 bytes

*2 bytes removed thanks to @StewieGriffin, and 1 byte further removed thanks to @Giuseppe!*

```
@(n)interp1((t=0:n).^2,-t.*(-1).^t,0:n^2)

```

Try it online!
> 2 votes

# Answer
# Java (JDK 10), 98 bytes

```
n->{var s="0";for(int i=0,r=0,d=1;i++<n;s+=" "+r,d=-d)for(r+=d;r!=i&r!=-i;r+=d)s+=" "+r;return s;}

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~52~~ 47 bytes

```
f=->n{n<1?[0]:f[n-1]+(2-n..n).map{|x|-~0**n*x}}

```

Try it online!

Below is the original 52-byte version with an explanation:

```
f=->n{n<1?[0]:f[n-1]+[(r=*2-n..n).map(&:-@),r][n%2]}

```

Try it online!

### Walkthrough

```
f=->n{           #Recursive approach
 n<1?[0]         #Init with 0 if n=0
 :f[n-1]         #else make a recursive call
 +               #and append an array of numbers
 [(r=*2-n..n)    #Init r as splatted range from 2-n to n
 .map(&:-@)      #"-@" is unary minus, so this a fancy way to do map{|x|-x} for -1 byte
                 #For even n use this negated r, e.g. for n=4: [2, 1, 0, -1, -2, -3, -4]
 ,r]             #For odd n use r directly, e.g. for n=3: [-1, 0, 1, 2, 3]
 [n%2]           #Odd/even selector
}

```
> 2 votes

# Answer
# Prolog (SWI), 113 bytes

```
0-I-[0|I].
N-[H|T]-R:-N is -H*(-1)^N,A is N-1,A-[H|T]-R;I is H-(-1)^N,N-[I|[H|T]]-R.
N-O:-X is -N*(-1)^N,N-[X]-O.

```

Try it online!
> 2 votes

# Answer
## Python 3, 83 bytes

```
def c(n):print([(-1)**j*(abs(j-i)-j)for j in range(n+1)for i in range(2*j)][:-n+1])

```
> 1 votes

# Answer
# Husk, ~~18~~ 17 bytes

```
:ṁoṡ₁ŀ⁰_₁⁰
*^⁰_1⁰

```

Try it online!
> 1 votes

# Answer
# Charcoal, 19 bytes

```
Ｆ⊕ＮＩ×∨﹪ι²±¹…·∧ι⁻²ιι

```

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

```
  Ｎ                 Input as a number
 ⊕                  Increment
Ｆ                   Loop over implicit range
                ²   Literal 2
                 ι  Current index
               ⁻    Subtract
              ι     Current index
             ∧      Logical And
                  ι Current index
           …·       Inclusive range
       ι            Current index
        ²           Literal 2
      ﹪             Modulo
          ¹         Literal 1
         ±          Negate
     ∨              Logical Or
    ×               Multiply
   Ｉ                Cast to string and implicitly print

```

Alternative explanation:

```
Ｆ⊕Ｎ

```

Loop over the integers from `0` to the input inclusive.

Cast the results to string before printing.

```
×∨﹪ι²±¹

```

Negate alternate sets of results.

```
…·∧ι⁻²ιι

```

Form a list from the previous index to the current index, excluding the previous index.
> 1 votes

# Answer
# Jelly,  ~~11~~  12 bytes

Bah, I thought I had 11 wih `_2+ỊrN)N;¥/`

```
_2+ỊrN×-*$)Ẏ

```

**Try it online!**

### How?

```
_2+ỊrN×-*$)Ẏ - Main Link: n           e.g. 4
          )  - for x in [1...n]:           1       2          3               4
_2           -   subtract 2 from x        -1       0          1               2
   Ị         -   is x insignificant?       1       0          0               0
  +          -   add                       0       0          1               2
     N       -   negate x                 -1      -2         -3              -4
    r        -   inclusive range          [0,-1]  [0,-1,-2]  [1,0,-1,-2,-3]  [2,1,0,-1,-2,-3,-4]
         $   -   last two links as a monad:
       -     -     minus one              -1      -1         -1              -1
        *    -     raised to the power x  -1       1         -1               1
      ×      -   multiply                 [0,1]   [0,-1,-2]  [-1,0,1,2,3]    [2,1,0,-1,-2,-3,-4]
           Ẏ - tighten                    [0,1,0,-1,-2,-1,0,1,2,3,2,1,0,-1,-2,-3,-4]

```
> 1 votes

# Answer
# APL (Dyalog Unicode), ~~34~~ 32 bytes

```
⎕CY'dfns'⋄-0,∘∊1↓¨2to/S×¯1*S←⍳,⊢

```

Try it online!

Requires `⎕IO←0`

-2 bytes thanks to @FrownyFrog
> 1 votes

# Answer
# Stax, 10 bytes

```
╗)SΘ█☼₧ΘP(

```

Run and debug it
> 1 votes

# Answer
### Scala, 119 Bytes

```
def a(n: Int)={lazy val s:Stream[Int]=0#::Stream.from(0).map{x=>s(x)+1 -2*(Math.sqrt(x).toInt%2)}
s.take(n*n+1).toList}

```

Ungolfed:

```
def a(n: Int)={
  lazy val s:Stream[Int]= 0#::Stream.from(0).map //Give the starting point and indexing scheme
  {
    x=>
    {
      val sign = 1-2*(Math.sqrt(x).toInt%2) //Determine whether we are adding or subtracting at the current index
      s(x)+sign
    }
  }
  s.take(n*n+1).toList //Take the desired values
}

```

This can probably be golfed much better, but I wanted a solution utilizing lazy Streams.
> 1 votes

# Answer
# Stacked, 44 bytes

```
[~>0\:2%\#,2*1-tr[...rep]flatmap,$sumonpref]

```

Try it online! It's been a while since I programmed in Stacked, but I think I still got it.

## Alternatives

**73 bytes:** `[0\|>:2%tmo*2 infixes[:...|>\rev...|>rev#,$#'sortby 1#behead]flatmap 0\,]`

This goes with the "ranges from generated indices" approach used in my Attache answer. This proved to be pretty long, since Stacked has no builtin for reversed ranges nor collapsing. (That's what `:...|>\rev...|>rev#,$#'sortby 1#behead` does.)

**53 bytes:** `[0\|>:2%tmo _\tpo#,tr[...rep]flatmap 0\,inits$summap]`

...so I decided to go for an approach which instead finds the cumulative sum (`inits$summap`) over `1` and `-1` repeated by the odd integers, as in the R answer.

**46 bytes:** `[~>0\:2%\#,2*1-tr[...rep]flatmap,inits$summap]`

...but I realized that the negative integers *and* the odd integers could be made in one go, by multiplying both generated arrays (the mod 2 values of the range and the range itself) by `2` then subtracting `1`. This gives alternating `1`s and `-1`s for the first range and the odd integers for the second!

**44 bytes:** `[~>0\:2%\#,2*1-tr[...rep]flatmap,$sumonpref]`

... and then I remembered I had a builtin for mapping prefixes. ^-^
> 1 votes

# Answer
# Julia 0.6, 44 bytes

```
n->[(i%2*2-1)*[0:i;(n>i)*~-i:-1:1]for i=1:n]

```

Try it online!

Since OP mentions "the output format is flexible", this prints an array of sub arrays, eg. U(3) =\> `[[0, 1], [0, -1, -2, -1], [0, 1, 2, 3]]`.

`i%2*2-1` decides the sign of the current subarray - negative for even numbers, positive for odd.

`[0:i;(n>i)*~-i:-1:1]` is in two parts. 0:i is straightforward, the range of values from 0 to the current i. In the next part, ~-i:-1:1 is the descending range from i-1 to 1. But we want to append this only if we're not yet at the final value, so multiply the upper end of the range by (n\>i) so that when n==i, the range will be 0:-1:1 which ends up empty (so the array stops at n correctly).

---

And here's a version that can support random access - the inner lambda here returns the i'th term of the sequence without having to have stored any of the terms before it. This one gives the output as a single neat array too.

### 49 47 bytes

```
n->map(i->((m=isqrt(i))%2*2-1)*(m-i+m^2),0:n^2)

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 83 bytes

```
n=>[v=0].concat(...[...Array(n),c=d=-1].map(t=>[...Array(c+=2)].map(t=>v+=d,d=-d)))

```

Try it online!
> 0 votes

# Answer
# Jelly, ~~17 16~~ 15 bytes

```
-*N×ŒḄ)j00;ḣN‘$

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), ~~56~~ 51 bytes

*-5 bytes thanks to user202729*

```
Join@@MapAt[-#&,Table[Range[-k,k],{k,#}],1;;-1;;2]&

```

Try it online!
> 0 votes

# Answer
# Clean, 59 bytes

```
import StdEnv
$m=foldr(\a=(++)[~a..a]o map~)[][0..m-1]++[m]

```

Try it online!

Defines the function `$ :: Int -> [Int]` generating the required list.

A direct port of user1472751's Haskell solution ended up being slightly better:

# Clean, 53 bytes

```
import StdEnv
$n m|m>n=[~n..n]++map~($(n+1)m)=[~m]

```

#

```
$0

```

Try it online!
> 0 votes

# Answer
# Ruby, 59 bytes

```
->n{a,*b=-1;n.times{|z|b+=[*(z*a).step(z*a=-a,a)]};b+[n*a]}

```

Try it online!
> 0 votes

# Answer
# C# (.NET Core), 97 bytes

```
n=>{var r="";int m=0,a=0,i=0;for(;++i<=n;)for(m=i%2>0?1:-1;a!=i*m;a+=m)r+=a+" ";r+=n*m;return r;}

```

Try it online!

Another different approach in C#.
> 0 votes

# Answer
# CJam, 59 bytes

```
1]q~:X*ee{~[\_-1\#@*](2*)*}%:+W%~[]\_@+{@@+_@+}XX*(*W%0\+p;

```

Try it online!

Suggestions for improvement are welcome!

EDIT: forgot leading zero
> 0 votes

# Answer
# Python 3, 83 bytes

```
lambda n:numpy.cumsum([0]+sum([[(-1)**i]*(i-~i)for i in range(n)],[]))
import numpy

```

Try it online!

I'll throw in a numpy solution, just for fun.
> 0 votes

# Answer
**Swift, 293 bytes**

```
let odd = n % 2 != 0
var i = 0
var inc = 1
var s : [Int] = [0]
repeat {
    i += inc
    if (inc == 1 && i % 2 != 0) || (inc == -1 && i % 2 == 0) {
        if !s.contains(i) {
            inc = -inc
        }
    }
    s.append(i)
} while !((odd && i == n) || (!odd && i == -n))
print("\(s)")

```
> 0 votes

# Answer
# Attache, 38 bytes

```
Collapse@@{`::&>Pairs!On[Even,`-,0:_]}

```

Try it online!

I'm struggling to break 38 bytes... I'll post an explanation once I'm convinced I can't get lower than this (or if I golf it!).
> 0 votes

# Answer
# JavaScript (Node.js), 51 bytes

```
n=>{for(p=i=0;i<=n*n;p+=1-(i++**.5|0)%2*2)alert(p)}

```

Try it online!

I ~~stole~~ ~~toke~~ ~~ripped off~~ used @KevinCruijssen's answer.

Thanks to @StewieGriffin for adding one more byte to my count (I forgot to output the last number) read the comments
> 0 votes

# Answer
# Yabasic, 83 bytes

An anonymous function that takes `Input`, `n` as an integer and outputs to the console.

```
Input""n
For i=1To n
For j=-i To i-1
k=i-Abs(j)
?(-1)^(i+1)*k;
If k=n End
Next
Next

```

Try it online!
> 0 votes

---
Tags: code-golf, sequence, integer
---


title: Visualize a Nim board like an expert

text:
# Question
Title: Visualize a Nim board like an expert
# Background

In the game of Nim, players alternate removing "stones" from "piles": on each turn, a player must remove between one and all stones from a *single* pile. The object of Nim is to take the last stone or, in the misere variant, to force your opponent to do so -- however, it turns out the strategies are nearly identical.

Nim makes a fun bar game. You can use matchsticks or coins for the "stones," and the "piles" are typically arranged in a line. Below is a classic setup with piles of 1, 3, 5, and 7:

If you've never played Nim before, you might try your hand at it before attempting this challenge. Here's a version called "Pearls Before Swine".

## Strategy

Optimal strategy in Nim is tricky enough that most lay people lose consistently to an expert, but simple to describe with binary arithmetic.

Doing mental binary XOR operations, however, is tough, so luckily there is an equivalent way to visualize the correct strategy which is easier to implement in real time, even when drunk.

There are only three steps:

1. Mentally group the "stones" in each line into subgroups whose sizes are powers of 2, starting with the largest possible size: 8, 4, 2, and 1 are sufficient for most games.
2. Try to match each group with a twin in another line, so that every group has a pair.
3. If this isn't possible, remove unpaired "stones" from a single line (this will always be possible - see the Wikipedia link for why) so that step 2. becomes possible.

Or, said another way: "Remove some stone(s) from a single pile such that if you then group the piles into powers of 2 all groups may be paired with a group in some other pile." With the caveat that you cannot break up larger powers of 2 into smaller ones -- eg, you cannot group a line with 8 stones into two groups of 4.

For example here's how you'd visualize the board above:

This board is perfectly balanced, so you'd want your opponent to move first.

## The Challenge

Given a list of positive integers representing the size of Nim "piles", return a plain text visualization of the Nim board as seen by an expert.

What constitutes a valid visualization is best explained by example, but you must:

1. Assign a distinct character to each "power-of-2 subgroup" and its pair (unpaired subgroups do not qualify), and use that character to represent the "stones" in both subgroup and pair.
2. Represent any unpaired "stones" (ie, the ones an expert would remove when playing normal -- not misere -- Nim) using a hyphen: `-`.

There will be multiple ways to achieve a valid visualization, and all are valid. Let's work through some test cases:

## Test Cases

### Input: 1, 3, 5, 7

Possible Output 1:

```
A
BBA
CCCCD
CCCCBBD

```

You may optionally include spaces between the characters, as well as blank lines between the rows:

Possible Output 2:

```
A

B B A

C C C C D

C C C C B B D

```

### Input: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

The order and choice of characters can be whatever you like:

Possible Output 1:

```
G
E E
E E G
C C C C
C C C C F
B B B B D D
B B B B D D F
H H I - - - - -
A A A A A A A A I
A A A A A A A A H H

```

Unicode symbols are ok too:

Possible Output 2:

```
◎
◈  ◈
◈  ◈  ◎
△  △  △  △
△  △  △  △  ◉
◐  ◐  ◐  ◐  ◀  ◀
◐  ◐  ◐  ◐  ◀  ◀  ◉
▽  ▽  ◒  -  -  -  -  -
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ◒
▥  ▥  ▥  ▥  ▥  ▥  ▥  ▥  ▽  ▽

```

### Input: 7

From the rules it follows that any "single pile" must be completely removed.

Possible Output 1:

```
-------

```

Possible Output 2:

```
- - - - - - -

```

### Input: 5, 5

Possible Output:

```
A A A A B
A A A A B

```

## Additional Rules

* This is code golf with standard rules. Shortest code wins.
* Input is flexible, and may be taken in whatever list-ish form is convenient to you.
* Output is flexible too, as the above examples illustrate. Most reasonable variations will be allowed. Ask if you're unsure about something.

# Answer
> 2 votes
# Ruby, ~~169~~ ~~164~~ 148 bytes

```
->a{s=eval a*?^
c=?@
m={}
a.map{|x|z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0
n=1
eval'x&1>0?[$><<(m[n]||c.next!)*n,m[n]=!m[n]&&c*1]:0;n*=2;x/=2;'*x
puts}}

```

Try it online!

First, we initialize

* the nim-sum with `s=eval a*?^` (which is shorter than `a.reduce:^`)
* the variable `c`, which stores the first unused unique character
* a map `m` that maps power-of-two lengths to characters used to represent them

Then, looping over each pile, we run the following:

```
z=x-(x^s);[$><<?-*z,x-=z,s=0]if z>0

```

Per Wikipedia's strategy, if *nim-sum XOR pile* is less than *pile*, we should remove stones from that pile such that its length becomes *nim-sum XOR pile*. By storing the difference in the variable `z`, we can test to see whether this difference is positive, and if so 1.) print that many dashes, 2.) subtract it from the pile, and 3.) set the nim-sum variable to zero to prevent further stone removal.

```
n=1
eval'[...];n*=2;x/=2;'*x

```

Now we "loop" over each bit and keep track of their values by repeatedly dividing `x` by `2` and multiplying the accumulator `n` by `2`. The loop is actually a string evaluated `x` times, which is far greater than the `log2(x)` times it's necessary, but no harm is done (aside from inefficiency). For each bit, we run the following if the bit is 1 (`x&1>0`):

```
$><<(m[n]||c.next!)*n

```

Print a character `n` times. If we already printed an unpaired group of this many stones, use that character; otherwise, use the next unused character (advancing `c` in-place due to the `!`).

```
m[n]=!m[n]&&c*1

```

If `m[n]` existed (i.e. we just completed a pair), then `m[n]` is reset. Otherwise, we just started a new pair, so set `m[n]` to the character we used (`*1` is a short way to make a copy of `c`).

# Answer
> 4 votes
# Python 2, ~~150~~ ~~196~~ 206 bytes

```
def f(p):
 c=48;s=[l*'.'for l in p];m=2**len(bin(l))
 while m:
  if sum(m*'.'in l for l in s)>1:
   for i,l in enumerate(s):s[i]=l.replace('.'*m,chr(c)*m,`s`.count(chr(c)*m)<2)
   c+=1
  else:m/=2
 return s

```

Try it online!

# Answer
> 1 votes
## JavaScript (ES6), 215 bytes

```
f=
(a,c=0,x=eval(a.join`^`),i=a.findIndex(e=>(e^x)<e),b=a.map(_=>``),g=e=>(d=e&-e)&&a.map((e,i)=>e&d&&(a[i]-=d,b[i]=(c++>>1).toString(36).repeat(d)+b[i]))&&g(e-d))=>g(eval(a.join`|`),b[i]='-'.repeat(a[i]-(a[i]^=x)))||b
```

```
<textarea oninput=o.textContent=/\d/.test(this.value)?f(this.value.match(/\d+/g)).join`\n`:``></textarea><pre id=o>
```

Only visualises up to 36 different characters. I'm relieved this works for `1, 3, 4, 5`.

# Answer
> 1 votes
# Clean, 454 bytes

*still golfing*

```
import StdEnv,Text,Data.List
$p=join"\n"[{#toChar c+'-'\\c<-e}\\e<-[take i(e++[0,0..])\\e<-r[[~c\\c<-reverse e,_<-[1..c]]\\e<-hd[q\\q<-foldr(\h t=[[a:b]\\a<-h,b<-t])[[]][[c\\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))|sum c<=k]\\k<-p]|sum[1\\a<-q&b<-p|sum a<>b]<2&&foldr(bitxor)0(flatten q)==0]]1&i<-p]]
r[]_=[]
r[h:t]n|all((<)0)h=[h:r t n]
#[m:_]=removeDup[e\\e<-h|e<0]
#(a,[x:b])=span(all((<>)m))t
=r([[if(e==m)n e\\e<-k]\\k<-[h:a]++[x]]++b)(n+1)

```

Try it online!

Defines the function `$ :: [Int] -> String`, taking the pile sizes and returning a string where `-` denote stones to be removed, and groups are represented by ASCII characters ascending from `-`. If enough groups are needed the characters will wrap back around eventually, and due to the `foldr` it requires more than a gigabyte of memory to run the second test-case.

Indented version of the giant comprehension:

```
$p=join"\n"[
    {#
        toChar c+'-'
        \\c<-j
    }
    \\j<-[
        take i(e++[0,0..])
        \\e<-r[
            [
                ~c
                \\c<-reverse e
                ,_<-[1..c]
            ]
            \\e<-hd[
                q
                \\q<-foldr(\h t=[
                    [a:b]
                    \\a<-h
                    ,b<-t
                ])[[]][
                    [
                        c
                        \\c<-subsequences(takeWhile((>=)k)(iterate((*)2)1))
                        |sum c<=k
                    ]
                    \\k<-p
                ]
                |sum[
                    1
                    \\a<-q
                    &b<-p
                    |sum a<>b
                ]<2&&foldr(bitxor)0(flatten q)==0
            ]
        ]1
        &i<-p
    ]
]

```

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


title: Calculate Phi (not Pi)

text:
# Question
Title: Calculate Phi (not Pi)
No, I don't mean \\$\phi = 1.618...\\$ and \\$π = 3.14159...\\$. I mean the *functions*.

* \\$\phi(x)\\$ is the number of integers less than or equal to \\$x\\$ that are relatively prime to \\$x\\$.
* \\$π(x)\\$ is the number of primes less than or equal to \\$x\\$.
* Let's say that "not pi" is then \\$\bar{\pi}(x)\\$ and define it to be the number of *composites* less than or equal to \\$x\\$.

## Task

Given a strictly positive integer \\$x\\$, **calculate** \\$\phi(\bar{\pi}(x))\\$. Scoring is in bytes.

## Examples

Each line consists of the input (from 1 to 100, inclusive) and the corresponding output separated by a space.

```
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 4
11 4
12 2
13 2
14 6
15 4
16 6
17 6
18 4
19 4
20 10
21 4
22 12
23 12
24 6
25 8
26 8
27 16
28 6
29 6
30 18
31 18
32 8
33 12
34 10
35 22
36 8
37 8
38 20
39 12
40 18
41 18
42 12
43 12
44 28
45 8
46 30
47 30
48 16
49 20
50 16
51 24
52 12
53 12
54 36
55 18
56 24
57 16
58 40
59 40
60 12
61 12
62 42
63 20
64 24
65 22
66 46
67 46
68 16
69 42
70 20
71 20
72 32
73 32
74 24
75 52
76 18
77 40
78 24
79 24
80 36
81 28
82 58
83 58
84 16
85 60
86 30
87 36
88 32
89 32
90 48
91 20
92 66
93 32
94 44
95 24
96 70
97 70
98 24
99 72
100 36

```

Use this link to calculate the expected output for any input. Also, a list of inputs and outputs for \\$x \le 1000\\$ is provided here on pastebin. (Generated with this Minkolang program.)

---

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

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

```
## Language Name, N bytes

```

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

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

```

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

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

```

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

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

```

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

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

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

# Answer
# GS2, ~~12~~ 10 bytes

```
V@'◄l.1&‼l

```

The source code uses the CP437 encoding. Try it online!

### Test run

```
$ xxd -r -ps <<< 564027116c2e3126136c > phinotpi.gs2
$ wc -c phinotpi.gs2
10 phinotpi.gs2
$ gs2 phinotpi.gs2 <<< 1000
552

```

### How it works

```
V          Read an integer n from STDIN.
 @         Push a copy of n.
  '        Increment the copy of n.
   ◄l      Push 1 and call primes; push the list of all primes below n+1.
     .     Count the primes.
      1    Subtract the count from n.
       &   Decrement to account for 1 (neither prime nor composite).
        ‼l Push 3 and call primes; apply Euler's totient function.

```
> 28 votes

# Answer
# Regex (.NET), ~~122~~ 113 bytes

```
^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+

```

Assuming input and output are in unary, and the output is taken from the main match of the regex.

Breakdown of the regex:

* `^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))` calculates π̅(x) and captures the rest of the string in capturing group 6 for assertion in the second part.

+ `.*$` sets the pointer to the end of the string so that we have the whole number `x` in one direction.
    + `(?<=^(\3+(.+.))(.*?(?>(.\4)?)))` matches from right to left and checks for composite number by looping from x to 0.
        - `(.*?(?>(.\4)?))` is a "variable" which starts from 0 in the first iteration and continues from the number in previous iteration and loops up to x. Since the smallest composite number is 4, `(.\4)?` never fails to match if capturing group 4 is available.
        - `^(\3+(.+.))` checks what is left by the "variable" above (i.e. `x - "variable"`) whether it is a composite number.
* `((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+` calculates φ(π̅(x)), by limiting the left-to-right operations with `(?=\6$)`.

+ `.*(?=\6$)` sets the pointer to position π̅(x). Let's denote y = π̅(x).
    + `(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))` matches from right to left and checks for relative prime by looping from (y - 1) to 0
        - `(.+?(?>\9?))` is a "variable" which starts from 1 in the first iteration and continues from the number in previous iteration and loops up to y
        - `(?!(.+.)\8*(?=\6$)(?<=^\8+))` matches from **left to right** 1 and checks whether the "variable" and y are relative prime.
            * `(.+.)\8*(?=\6$)` picks a divisor of "variable" which is larger than 1, and a side effect is that we have whole number y on the left.
            * `(?<=^\8+)` checks whether the divisor of "variable" is also the divisor of y.

1 In .NET, look-ahead **sets** the direction to LTR instead of following the current direction; look-behind **sets** the direction to RTL instead of reversing the direction.

Test the regex at RegexStorm.

**Revision 2** drops non-capturing groups and uses atomic groups instead of conditional syntax.
> 46 votes

# Answer
# J, ~~15~~ 14 bytes

```
5 p:<:-_1 p:>:

```

This is a tacit, monadic verb. Try it online with J.js.

### How it works

```
                Right argument: y
            >:  Increment y.
       _1 p:    Calculate the number of primes less than y+1.
    <:          Decrement y.
      -         Calculate the difference of the results to the left and right.
5 p:            Apply Euler's totient function to the difference.

```
> 20 votes

# Answer
## Seriously, 27 bytes

```
,;R`p`MΣ(-D;n;;╟@RZ`ig1=`MΣ

```

Yay, I beat CJam! Try it online

Explanation (`a` refers to top of stack, `b` refers to second-from-top):

```
,;       take input and duplicate it
R`p`MΣ   push sum([is_prime(i) for i in [1,...,a]]) (otherwise known as the pi function)
(-D      rotate stack right by 1, subtract top two elements, subtract 1, push
            (@ could be used instead of (, but I was hoping the unmatched paren would bother someone)
;n;;     dupe top, push a b times, dupe top twice (effectively getting a a+1 times)
╟        pop n, pop n elements and append to list, push
@        swap top two elements
RZ       push [1,...,a], zip a and b
`ig1=`   define a function:
  i        flatten list
  g1=      compute gcd(a,b), compare to 1 (totient function)
MΣ       perform the function a on each element of b, sum and push

```

Note: since the posting of this answer, I have added the pi and phi functions to Seriously. Here is a noncompetitive answer with those functions:

```
,;▓1-@-▒

```

Explanation (some commands are shifted to not overlap others):

```
,    get input (hereafter referred to as x)
;    duplicate x
 ▓   calculate pi(x) (we'll call this p)
1-   calculate 1-p
@-   bring x back on top, calculate x-1-p (not pi(x))
  ▒  calculate phi(not pi(x))

```
> 19 votes

# Answer
# Julia, ~~52~~ 50 bytes

```
x->count(i->gcd(i,p)<2,1:(p=x-endof(primes(x))-1))

```

This creates an unnamed function that accepts and integer and returns an integer. To call it, give it a name, e.g. `f=x->...`.

Ungolfed:

```
function phinotpi(x::Integer)
    # The number of composites less than or equal to x is
    # x - the number of primes less than or equal to x -
    # 1, since 1 is not composite
    p = x - length(primes(x)) - 1

    # Return the number of integers i between 1 and p such
    # that gcd(i, p) = 1. This occurs when i is relatively
    # prime to p.
    count(i -> gcd(i, p) == 1, 1:p)
end

```
> 13 votes

# Answer
# Mathematica, 24 bytes

```
EulerPhi[#-PrimePi@#-1]&

```
> 9 votes

# Answer
## Minkolang 0.11, 12 bytes (NOT competitive)

**This answer is NOT competitive.** I implemented pi and phi as built-ins before I posted the question, which gives me an unfair advantage. I post this only for those who are interested in the language.

```
nd9M-1-9$MN.

```

Try it here.

### Explanation

```
n      Read in integer from input
d      Duplicate
9M     Pops off the top of stack as x and pushes pi(x)
-      Subtracts the top two elements on the stack (x - pi(x))
1-     Subtracts 1 (x-1 - pi(x))
9$M    Pops off the top of stack as x and pushes phi(x) (phi(x-1 - pi(x)))
N.     Outputs as integer and stops.

```
> 7 votes

# Answer
# Pyth, 14 bytes

```
JlftPTSQ/iLJJ1

```

Demonstration, Verifier

We calculate composites using a simple filter, take its length, and save it to `J`. Then, we take the gcd of `J` with every number up to `J`, and count how many results equal 1.
> 7 votes

# Answer
# CJam, 28 bytes

```
ri){mf1>},,_,f{){_@\%}h)=}1b

```

Try it this fiddle in the CJam interpreter or verify all test cases at once.

### How it works

```
ri                            Read an integer N from STDIN.
  )                           Increment it.
   {    },                    Filter; for each I in [0 ... N]:
    mf                          Push I's prime factorization.
      1>                        Discard the first prime.
                              If there are primes left, keep I.
          ,                   Count the kept integers. Result: C
           _,                 Push [0 ... C-1].
             f{          }    For each J in [0 ... C-1], push C and J; then:
               )                Increment J.
                {    }h         Do:
                 _                Push a copy of the topmost integer..
                  @               Rotate the integer below on top of it.
                   \%             Take that integer modulo the other integer.
                                If the residue is non-zero, repeat the loop.
                                This computes the GCD of C and J+1 using the
                                Euclidean algorithm.
                       )        Increment the 0 on the stack. This pushes 1.

                        =     Push 1 if the GCD is 1, 0 if not.
                          1b  Add all Booleans.

```
> 5 votes

# Answer
# Python, 137 ~~139~~

```
n=input()
print n,len([b for b in range(len([a for a in range(n)if not all(a%i for i in xrange(2,a))]))if all(b%i for i in xrange(2,b))])

```
> 5 votes

# Answer
## Retina, 48 bytes

```
.+
$*
M&`(..+)\1+$
.+
$*
(?!(..+)\1*$(?<=^\1+)).

```

Try it online!

### Explanation

```
.+
$*

```

Convert input to unary.

```
M&`(..+)\1+$

```

Count composite numbers not greater than the input by counting how often we can match a string that consists of at least two repetitions of a factor of at least 2.

```
.+
$*

```

Convert to unary again.

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

```

Compute φ by counting from how many positions it is not possible to find a factor (of at least 2) of the suffix from that position which is also a factor of the prefix (if we do find such a factor then this `i <= n` shares a factor with `n` is therefore not coprime to it). The `.` at the end ensures that we don't count zero (for which we can't find a factor of at least 2).
> 5 votes

# Answer
## Regex (.NET), ~~88~~ 86 bytes

```
^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(((?!(..+)\6*(?<=^\6+)\3$))?.)*\3)(?<-5>.)*

```

Try it online! (As a Retina program.)

Uses the same I/O as n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ 's answer, i.e. unary input and it matches a substring of the length of the result.

It might be possible to shorten this further by replacing one or both of the balancing groups with forward references.

Alternative at the same byte count:

```
^(?=((?=(..+)\2+$)?.)+)(?=(?<-2>.)*(.+))(?=(?((..+)\4*(?<=^\4+)\3$).|(.))*\3)(?<-5>.)*

```

There are also some alternatives for the first half, e.g. using a negative lookahead instead of a positive one for the compositive numbers, or using a conditional there as well.

### Explanation

I'll assume that you have a basic understanding of balancing groups, but in short, capturing groups in .NET are stacks (so each time you reuse the capturing group the new capture is pushed on top) and `(?<-x>...)` pops a capture from stack `x`. That's very helpful for counting things.

```
^                   # Only look at matches from the beginning of the input.
(?=                 # First, we'll compute the number of composites less than
                    # or equal to the input in group 2. This is done in a
                    # lookahead so that we don't actually advance the regex
                    # engine's position in the string.
  (                 #   Iterate through the input, one character at a time.
    (?=(..+)\2+$)?  #     Try to match the remainder of the input as a
                    #     composite number. If so the (..+) will add one
                    #     one capture onto stack 2. Otherwise, this lookahead
                    #     is simply skipped.
    .
  )+
)
(?=                 # It turns out to be more convienient to work with n minus
                    # the number of composites less than or equal to n, and to
                    # have that a single backreference instead of the depth of
                    # a stack.
  (?<-2>.)*         #   Match one character for each composite we found.
  (.+)              #   Capture the remainder of the input in group 3.
)
(?=                 # Now we compute the totient function. The basic idea is
                    # similar to how we computed the number of composites,
                    # but there are a few differences.
                    # a) Of course the regex is different. However, this one
                    #    is more easily expressed as a negative lookahead (i.e.
                    #    check that the values don't share a factor), so this
                    #    won't leave a capture on the corresponding stack. We
                    #    fix this by wrapping the lookahead itself in a group
                    #    and making the entire group optional.
                    # b) We only want to search up the number of composites,
                    #    not up to the input. We do this by asserting that we
                    #    can still match our backreference \3 from earlier.

  (                 #   Iterate through the input, one character at a time.
    ((?!            #     Try not to match a number that shares a factor with
                    #     the number of composites, and if so push a capture
                    #     onto stack 5.
      (..+)\6*      #     Look for a factor that's at least 2...
      (?<=^\6+)     #     Make sure we can reach back to the input with that
                    #     factor...
      \3$           #     ...and that we're exactly at the end of the number
                    #     of composites.
    ))?
    .
  )*
  \3                #   Match group 3 again to make sure that we didn't look
                    #   further than the number of composites.
)
(?<-5>.)*           # Finally, match one character for each coprime number we
                    # found in the last lookahead.

```
> 5 votes

# Answer
# PARI/GP, 27 bytes

```
n->eulerphi(n-1-primepi(n))

```
> 4 votes

# Answer
# Jelly, **7 bytes**

```
ÆC_@’ÆṪ

```

### How it works

```
ÆC_@’ÆṪ  Input: n

ÆC       Count the primes less than or equal to n.
    ’    Yield n - 1.
  _@     Subtract the count from n - 1.
     ÆṪ  Apply Euler's totient function.

```
> 4 votes

# Answer
# Gaia, 5 bytes

```
ṗ⁈l(t

```

Try it online!

```
ṗ⁈l(t   ~ Full program.

 ⁈      ~ Reject the elements that:
ṗ         ~ Are prime.
  l     ~ Length.
   (    ~ Decrement.
    t   ~ Euler's totient.

```
> 4 votes

# Answer
# PARI/GP, 35 bytes

```
n->eulerphi(sum(x=2,n,!isprime(x)))

```
> 3 votes

# Answer
# SageMath 26 bytes

```
euler_phi(n-1-prime_pi(n))

```

Works well even for `n=0` and `n=1`, thanks to Sage's implementation.
> 3 votes

# Answer
# Jelly, 6 bytes

```
_ÆC’ÆṪ

```

Try it online!

This is a collaboration between caird coinheringahhing and Mr. Xcoder in chat

# Explanation

```
_ÆC’ÆṪ   ~ Full program.

 ÆC      ~ Count the primes less than or equal to Z.
_        ~ Subtract from the input.
   ’     ~ Decrement.
    ÆṪ   ~ Euler's totient function.

```
> 3 votes

# Answer
# Ohm v2, 7 bytes

```
³³Pl-‹φ

```

Try it online!
> 3 votes

# Answer
# Octave, ~~52~~ 51

```
@(b)nnz((d=[1:(c=b-1-nnz(primes(b)))])(gcd(d,c)<2))

```

*Edit: saved 1 byte thanks to Thomas Kwa*

Explanation:

```
@(b)                                            # Define anonymous func with parameter b
  nnz(                                          # Count elements in φ(c)
    (                                           #
      d = [1:                                   # Create d= array of 1 to π̅(b)
            ( c = b - 1 - nnz(primes(b)) )      # Calculate c=π̅(b) by subtracting the
                                                #  number of elements in the array of prime
          ]                                     #  numbers from the number of ints in 2:b
    )(gcd(d, c) < 2)                            # Calculate φ(c) by using gcd to filter
  )                                             # relative primes from d

```
> 2 votes

# Answer
# MATL, 9 bytes

```
:Zp~sq_Zp

```

Uses version (10.1.0) of the language/compiler.

**Try it online!**

### Explanation

```
:       % implicitly input a number "N" and produce array [1,2,...,N]
Zp      % true for entries that are prime
~       % negate. So it gives true for entries of [1,2,...,N] that are non-prime
s       % sum elements of array. So it gives number of non-primes
q       % subtract 1. Needed because number 1 is not prime, but not composite either
_       % unary minus
Zp      % with negative input, computes totient function of absolute value of input
        % implicit display

```
> 2 votes

# Answer
## GAP, 33 Bytes

```
n->Phi(n-Number([-2..n],IsPrime))

```

`Number(l,p)` counts how many elements from `l` satisfy `p`. To compensate for the fact that 1 is neither prime nor composite, I have to subtract from n one more than the number of primes up to n. Instead of doing `-1` for two bytes, I start the list by -2 instead of 1 or 2, thus adding one more number that is considered prime by `IsPrime` for only one extra byte.
> 2 votes

# Answer
## Python 3.5 - 130 bytes

```
from math import*
def p(n,k,g):
 for i in range(1,n+1):k+=factorial(i-1)%i!=i-1
 for l in range(1,k):g+=gcd(k,l)<2
 return g

```

If it's not acceptable to pass the function through as p(n,0,0) then +3 bytes.

This takes advantage of the fact that I use Wilson's theorem to check if a number is composite and have to call into the math module for the factorial function. Python 3.5 added a gcd function into the math module.

The first loop of the code will increment k by one if the number is composite and increment by 0 else-wise. (Although Wilson's theorem only holds for integers greater than 1, it treats 1 as prime, so allows us to exploit this).

The second loop will then loop over the range of number of composites and increment g only when the value of not pi and l are co-prime.

g is then the number of values less than or equal to the number of composite numbers less than or equal to n.
> 2 votes

# Answer
# Python 3 \+ sympy, ~~59~~ 58 bytes

*\*-1 byte by replacing `compositepi(k)` with `k+~primepi(k)`.*

```
lambda k:totient(k+~primepi(k))
from sympy.ntheory import*

```

Try it online!
> 2 votes

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

```
LDpÈÏg<Õ

```

Try it online!

# How it works

```
L             # this gets us the list of numbers [1 .. a]
 D            # duplicates this list
  p           # applies isPrime to each element of the list, vectorised.
   È          # is the element even? (does 05AB1E not have a logical not?)
    Ï         # push elements of the first list where the same index in the
              # second list is 1
     g<       # finds the length and subtracts 1 (as the list contains 1)
              # this is the not pi function
       Õ      # euler totient function

```
> 1 votes

# Answer
# Pyt, 6 bytes

```
řṗ¬Ʃ⁻Ț

```

Explanation:

```
                Implicit input
ř               Push [1,2,...,input]
 ṗ              [is 1 prime?, is 2 prime?, ..., is input prime?]
  ¬             [is 1 not prime?, is 2 not prime?, ... is input not prime?]
   Ʃ            Number of non-primes (sums the array - booleans implicitly converted to ints)
    ⁻           Subtract one to remove the counting of '1'
     Ț          Euler's totient function

```

Try it online!
> 1 votes

# Answer
# APL NARS, 38 bytes, 19 chars

```
{⍵≤3:0⋄13π¯1+⍵-2π⍵}

```

13π is the totient function and 2π is the count prime function\<= its argument. Test

```
  b←{⍵≤3:0⋄13π¯1+⍵-2π⍵}
  (⍳12),¨b¨⍳12
1 0  2 0  3 0  4 1  5 1  6 1  7 1  8 2  9 2  10 4  11 4  12 2
  (95..100),¨b¨(95..100)
95 24  96 70  97 70  98 24  99 72  100 36

```
> 1 votes

# Answer
# Add++, 21 bytes

```
L,RþPbL1_dRdVÞ%bLG!!+

```

Try it online!

## How it works

This simply implements \\$\overline\pi(n)\\$ and \\$\varphi(n)\\$ without using the two explicit functions (mainly because they aren't builtin). The code can therefore be split into two sections: \\$\overline\pi(n)\\$ and \\$\varphi(n)\\$.

### \\$\overline\pi(n)\\$

```
RþPbL1_

```

Here, operating on the input directly, we generate a range from **\[0 .. n\]** with `R`, then remove any primes with `þP` (filter false (`þ`) prime elements (`P`)). Unfortunately, this doesn't remove **1**, as it isn't prime. Therefore, after taking the number of elements left with `bL`, we decrement once `1_` to remove the count for **1**. This leaves \\$x = \overline\pi(n)\\$ on the stack.

### \\$\varphi(n)\\$

```
dRdVÞ%bLG!!+

```

This one is rather longer, due once again to **1**. First, we duplicate \\$x\\$ and create a range to operate over with `dR`. Next, we save a copy of this range for a check we'll address later. Then, using filter true `Þ%`, we remove any elements that divide \\$x\\$, or keep any elements that have a GCD of **1** with \\$x\\$. Finally, we take the length of this list with `bL`.

Unfortunately, this yields **0** when the result should be **0** and \\$n - 1\\$ when the correct result is \\$n\\$. In order to fix this discrepancy, we retrieve the saved range with `G`, and convert it into a boolean value with `!!`. This makes empty ranges (which would yield **0**) into **0** and every other range into **1**. Finally, we add this value to our previous result and return it.

Yes, I did really want to try the new LaTex
> 1 votes

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