title: The Quantum Drunkard's Walk

text:
# Question
Title: The Quantum Drunkard's Walk
It is well known that a person on a grid under the influence of alcohol has an equal chance of going in any available directions. However, this common-sense statement does not hold in the realm of *very small* drunkards, whose behavior is very much as if they take *every* available path at once, and the possible paths they take can interfere with each other. Your task is to display the possible positions of such a quantum drunkard after `n` steps.

## Specification

The drunkard in question occupies a square grid, and may be considered to be a 3-state cellular automaton using a Von Neumann (plus-shaped) neighborhood which follows these simple rules:

* `Empty` goes to `Awake` if it is adjacent to exactly one `Awake`, and otherwise goes to `Empty`
* `Awake` goes to `Sleeping`
* `Sleeping` goes to `Sleeping`

The initial state of the board is a single `Awake` surrounded by an infinite field of `Empty`s.

## Challenge

Given a nonnegative integer `n`, create an ASCII representation of the drunkard after `n` steps. Each state should be represented by a different character, and solutions should state which character means which state. If you use spaces for `Empty`, you don't need to include a run of them at the end of a line.

This is , so shortest answer wins. Standard loopholes apply, leading and trailing whitespace is allowed, string array/2d char array output is allowed, etc.

## Examples

These examples use  for `Empty`, `@` for `Awake`, and `#` for `Sleeping`.

```
n=0
@

n = 1
 @
@#@
 @

n = 2
  @
  #
@###@
  #
  @

n = 3
   @
  @#@
 @ # @
@#####@
 @ # @
  @#@
   @

n=6

      @
      #
    @###@
     @#@
  @  ###  @
  #@# # #@#
@###########@
  #@# # #@#
  @  ###  @
     @#@
    @###@
      #
      @

n=10
          @
          #
        @###@
         @#@
         ###
        # # #
       #######
      #  ###  #
  @  ##  ###  ##  @
  #@# ### # ### #@#
@###################@
  #@# ### # ### #@#
  @  ##  ###  ##  @
      #  ###  #
       #######
        # # #
         ###
         @#@
        @###@
          #
          @

```

## Interesting Note

By looking up the sequence of the number of occupied cells in the OEIS, I found that the quantum drunkard is isomorphic to the much better-studied toothpick sequence. If you can incorporate that knowledge into a better golf, I will be suitably impressed.

# Answer
> 34 votes
# Wolfram Language (Mathematica), ~~92~~ 91 bytes

```
Print@@@CellularAutomaton[{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}},{j={{1}},0},{j#}]&

```

A perfect challenge to use Mathematica's builtin `CellularAutomaton`!

Try it online!

Empty = 0, Awake = 1, Sleeping = 2

Animation of the first 256 iterations (white = empty, gray = awake, black = sleeping):

### Explanation

```
CellularAutomaton[ ... ]

```

Run `CellularAutomaton` with specifications...

```
{7049487784884,{3,{a={0,3,0},3-2a/3,a}},{1,1}}

```

Apply the 3-color totalistic rule 7049487784884, with Von Neumann neighborhood...

```
{j={{1}},0}

```

On a board with a single 1 in the middle, with a background of 0s...

```
{j#}

```

Repeat `<input>` times (`{j#}` evaluates to `{{{#}}}`). The array automatically expands if a cell outside of the border is not the same as the background

```
7049487784884

```

This rule comes from the base-3 number `220221220221220221220221220`, which means "change all `1` or `2` to `2`, and change `0` to `1` if and only if there is an odd number of `1`s around it."

```
Print@@@

```

Print the array.

### Semi-proof of "'odd `1`s' is equivalent to 'exactly one `1`'":

Consider this 5x5 grid of pixels. White is a `0` or a `2` cell (non-awake pixels), and gray is a `1` cell.

If a `1` cell was generated around three `0` cells, then the grid must look like this: it has three `1`s arranged in a U-shape (or a rotated version) as follows:

Due to the self-similarity of this cellular automaton, any pattern that appears in the cellular automaton must appear on the diagonal (by induction). However, this pattern is not diagonally symmetric. i.e. it cannot occur on the diagonal and cannot appear anywhere on the cellular automaton.

### Awake/Sleeping are equivalent

Note that a `0` cell cannot be surrounded by exactly one or three `2` cells and rest `0` cells, since that would imply that some steps prior, the cell had a neighbor of one or three `1` cells -- and must have turned into a `1` already (contradiction). Therefore, it is okay to ignore the distinction between `1` and `2` and state 'change all `1` to `1`, and a `0` to a `1` if and only if it has an odd number of nonzero neighbors.'

The resulting cellular automaton is indeed identical to the original, the only difference being there is no distinction between "awake" and "asleep" drunkards. This pattern is described in OEIS A169707.

```
Print@@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{j={{1}},0},{j#}]&

```

Try it online!

Side-by-side comparison of the first 16 iterations:

Adding two consecutive iterations gives a result that follows the challenge specs (94 bytes):

```
Print@@@Plus@@CellularAutomaton[{750,{2,{a={0,2,0},2-a/2,a}},{1,1}},{{{1}},0},{Ramp@{#-1,#}}]&

```

Try it online!

# Answer
> 11 votes
# Python 2, 192 bytes

```
x=input()
o=c={x+x*1j}
R=range(x-~x)
exec"n=[C+k for k in-1j,1j,-1,1for C in c];n={k for k in n if(k in o)<2-n.count(k)};o|=c;c=n;"*x
print[[`(X+Y*1jin c)+(X+Y*1jin o|c)`for Y in R]for X in R]

```

Try it online!

-17 bytes thanks to Mr. Xcoder
-9 bytes using Jonathan's output format
-11 bytes thanks to Lynn
-3 bytes thanks to ovs

# Answer
> 10 votes
# C, ~~360~~ ~~354~~ ~~343~~ 319

```
#define A(i,b,e)for(int i=b;i<e;++i)
#define B(b,e)A(r,b,e){A(c,b,e)
#define W(n)(n<0?-(n):n)
#define C(r,c)b[W(r)*s+W(c)]
#define D C(r,c)

q(n){char N,s=n+2,(*b)[2]=calloc(s,2*s);C(0,0)
[1]=1;A(g,0,n+1){B(0,s)*D=D[1];}B(0,g+2){N=(*C
(r-1,c)+*C(r+1,c)+*C(r,c-1)+*C(r,c+1))&1;D[1]=
*D?2:N;}}}B(2-s,s-1)putchar(*D+32);puts("");}}

```

Newlines after non-`#define` lines are just for presentation here, so they’re not counted. I included a wrapper function, so it’s −6 (313) if the function isn’t counted and you assume `n` comes from elsewhere. `q(10)` outputs:

```
          !
          "
        !"""!
         !"!
         """
        " " "
       """""""
      "  """  "
  !  ""  """  ""  !
  "!" """ " """ "!"
!"""""""""""""""""""!
  "!" """ " """ "!"
  !  ""  """  ""  !
      "  """  "
       """""""
        " " "
         """
         !"!
        !"""!
          "
          !

```

Using  for empty, `"` for sleeping, and `!` for awake.

This works like so:

* `A(i,b,e)` is “∀i∈\[b,e).”, `B(b,e)` is “∀r∈\[b,e).∀c∈\[b,e).”
* Observe that after *n* generations, the board is 2*n* \+ 1 square.
* Because of the symmetry of the board, this only needs to simulate the lower right quadrant, so we allocate an *n* \+ 1 square matrix with 1 row & column of padding for the later neighbour lookup (so *n* \+ 2).
* Allocating with `calloc` lets us simultaneously multiply the width by the height and clear the board to `0` (empty).
* When looking up a cell by its coordinates (`C` and `D`), it uses the absolute value of the row and column (`W`) to automatically mirror the coordinates.
* The board is stored as an array of pairs of integers representing the current and previous generations. The integers in question are `char` so we can avoid `sizeof`.
* The generation looked up most frequently (by the neighbour test) is the past generation, so it’s placed at index 0 in the pair so it can be accessed with `*`.
* At each generation (`g`), the current generation is copied over the previous generation using a `B` loop, then the new generation is generated from the old.
* Each cell is represented using `0` for empty, `1` for awake, and `2` for sleeping. Counting neighbours was originally a calculation of the number of bits set in the low 4 bits of the cell when the 4 neighbours are shifted & OR’d together as flags (`N`), using `16` for sleeping. But with the observation that an odd number of neighbours is equivalent to exactly 1 neighbour, we can save several characters just using a mask with 1.
* At the end, the board is printed in full by iterating over the lower right quadrant using the same absolute value coordinate trick, minus padding so we don’t print the outer padding on the board. This is also why the `B` loop includes an opening curly bracket, because we have the extra newline statement in the outer loop.
* The ASCII codes conveniently map 0+32 (empty) to a space, 2+32 (sleeping) to `"`, and 1+32 (awake) to `!`.

All in all I think this is a surprisingly readable golf because of the nice structure of the problem.

# Answer
> 6 votes
# MATL, 39 bytes

```
QtE:=&*G:"tt0=w1Y6Z+Xj1=*w|gJ*+]Q|U31+c

```

This displays

* `Empty` as  (space)
* `Awake` as `#`
* `Sleeping` as `!`.

**Try it online!** You can also watch the pattern **grow** in ASCII art, or **graphically** (modified code).

### Explanation

The code uses complex numbers `0`, `1`, `j` to represent the three states: empty, wake, sleeping respectively.

```
Q         % Implicitly input n. Add 1
tE        % Duplicate and multiply by 2
:         % Range [1 2 ... 2*n]
=         % Test for equalty. Gives [0 ... 0 1 0... 0], with 1 at position n
&*        % Matrix of all pairwise products. Gives square matrix of size 2*n
          % filled with 0, except a 1 at position (n,n). This is the grid
          % where the walk will take place, initiallized with an awake cell
          % (value 1). The grid is 1 column and row too large (which saves a
          % byte)
G:"       % Do n times
  tt      %   Duplicate current grid state twice
  0=      %   Compare each entry with 0. Gives true for empty cells, false
          %   for the rest
  w       %   Swap: moves copy of current grid state to top
  1Y6     %   Push 3×3 matrix with Von Neumann's neighbourhood
  Z+      %   2D convolution, maintaining size
  Xj      %   Real part
  1=      %   Compare each entry with 1. This gives true for cells that
          %   have exactly 1 awake neighbour
  *       %   Multiply, element-wise. This corresponds to logical "and":
          %   cells that are currently empty and have exactly one awake
          %   neighbour. These become 1, that is, awake
  w       %   Swap: moves copy of current grid state to top
  |g      %   Absolute value, convert to logical: gives true for awake or
          %   sleeping cells, false for empty cells
  J*+     %   Mulltiply by j and add, element-wise. This sets awake and
          %   sleeping cells to sleeping. The grid is now in its new state
]         % End
Q         % Add 1, element-wise. Transforms empty, awake, sleeping
          % respectively from 0, 1, j into 1, 2, 1+j
|U        % Abolute value and square, element-wose. Empty, awake, sleeping
          % respectively give 1, 4, 2
31+c      % Add 31 element-wise and convert to char. Empty, awake, sleeping
          % respectively give characters ' ' (codepoint 32), '#' (codepoint
          % 35) and '!' (codepoint 33). Implicitly display

```

# Answer
> 5 votes
# Befunge, ~~384~~ 304 bytes

```
&:00p->55+,000g->>00g30p:40p\:50p\5>>40g!50g!*vv0g05g04p03-<
@,+55_^#`g00:+1$_^>p:4+4g5%2-50g+5#^0#+p#1<v03_>30g:!#v_:1>^
#v_>$99g,1+:00g`^ ^04+g04-2%5g4:\g05\g04\p<>g!45*9+*3+v>p:5-
 >\50p\40p\30p:#v_>>0\99g48*`!>v >30g:1-30^>>**\!>#v_>v^9 9<
$0\\\\0$        >\99g88*-!+\:4->#^_\>1-!48>^       >$3>48*+^

```

Try it online!

The problem with trying to implement this sort of thing in Befunge is the limited memory size (2000 bytes for both data and code). So I've had to use an algorithm that calculates the correct character for any given coordinate without reference to previous calculations. It achieves this by recursively looking back in time across all possible paths the drunkard might have followed to reach that point.

Unfortunately this is not a particular efficient solution. It works, but it's incredibly slow, and it becomes exponentially slower the larger the value of *n*. So while it could potentially work for any *n* up to about 127 (Befunge's 7-bit memory cell limit), in practice you'll inevitably lose interest waiting for the result. On TIO, it'll hit the 60 second timeout on anything higher than around 6 (at best). A compiler will do a lot better, but even then you probably wouldn't want to go much higher than 10.

Still, I thought it was worth submitting because it's actually quite a nice demonstration of a recursive "function" in Befunge.

# Answer
> 4 votes
# Python 2, 214 bytes

```
def f(n):k=n-~n;N=k*k;A=[0]*N;A[N/2]=2;exec"A=[[2*([j%k>0and A[j-1],j%k<k-1and A[j+1],j/k>0and A[j-k],j/k<k-1and A[j+k]].count(2)==1),1,1][v]for j,v in enumerate(A)];"*n;print[map(str,A)[k*x:][:k]for x in range(k)]

```

Try it online!

# Explanation

Uses `0` for `empty`, `1` for `sleeping` and `2` for `awake`. Prints out a two-dimensional character (one-length strings) list.
Defines a function which takes in a non-negative integer `n`. Successively advances the cellular automaton until the desired state is reached. Finally, a conversion between the internal integer values and actual characters is applied.

# Answer
> 4 votes
# Lua, ~~251~~ ~~242~~ ~~239~~ 238 bytes

-8 bytes by simplifying the array initializer at the cost of some additional leading whitespace.
-1 byte by changing `c=i==2+...and print(s)` into `c=i~=2+...or print(s)`.
-3 bytes by building a complete string first and printing once at the end.
-1 byte thanks to Jonathan Frech by rewriting `or(g(...)==1 and` as `or(1==g(...)and`.

```
function g(x,y)return(a[x]or{})[y]or 0 end a={{1}}for i=2,2+...do n={}s=""for x=-i,i do n[x]=n[x]or{}q=a[x]or{}for y=-i,i do n[x][y]=q[y]and 0or(1==g(x+1,y)+g(x,y+1)+g(x-1,y)+g(x,y-1)and 1)s=s..(q[y]or" ")end s=s.."\n"end a=n end print(s)

```

Try it online!

Empty = Space
Awake = `1`
Sleeping = `0`

Takes input from the command line and prints to stdout.

By representing the states as `false`/`nil`, `1` and `0` internally, detecting "empty" doesn't need any code and the "exactly one awake" check can be done with just an addition.

# Answer
> 4 votes
# APL (Dyalog), 38 bytes

```
((2∘∧⌈1={2⊃+/1=⍵,⍉⍵}⌺3 3)(⌽0,⍉)⍣4)⍣⎕⍪1

```

Try it online!

-4 thanks to Adám.
-8 thanks to ngn.

# Answer
> 4 votes
# APL (Dyalog Classic), 38 bytes

```
((2∘∧⌈2|⍉∘g∘⍉+g←3+/0,,∘0)(⌽0,⍉)⍣4)⍣⎕⍪1

```

Try it online!

based on Erik the Outgolfer's solution

`⍪1` is a 1x1 matrix containing 1

eval'ed input

`( )⍣⎕` apply that many times

* `(⌽0,⍉)⍣4` surround with 0s, that is 4 times do: transpose (), add 0s on the left (`0,`), reverse horizontally ()
* `g←3+/0,,∘0` a function that sums horizontal triples, call it `g`
* `⍉∘g∘⍉` a function that sums vertical triples - that's `g` under transposition
* `2 | ⍉∘g∘⍉ + g←3+/0,,∘0` sum of the two sums modulo 2
* the greater between that and ...
* `2∘∧` the LCM of 2 and the original matrix - this turns 1s into 2s, while preserving 0s and 2s

# Answer
> 4 votes
# Jelly, ~~39~~ 29 bytes

```
-,1ṙ@€Sµ+Z
‘ṬŒḄ×þ`µÇ×¬Ḃ+Ḃ+µ³¡

```

Try it online!

Uses `0`,`1` and `2` for empty awake and sleeping. The footer in the link converts this to , `@` and `#`.

* -1 byte by using `ṬŒḄ` instead of `ḤḶ=¹`.
* -2 bytes by using `-` instead of `1N`. Also makes `¤` unnecessary.
* -1 byte by using `S` instead of `+/`.
* -6 bytes by using `Ḃ+Ḃ+` instead of `%3=1+=1Ḥ$+`. Now uses `2` for sleeping instead of `3`.

Explanation coming...

# Answer
> 3 votes
# Perl 5, 192 + 1 (`-n`) = 193 bytes

```
for$i(1..2*$_+1){push@a,[()x$_]}$a[$_][$_]=1;map{@b=();for$i(0..$#a){map$b[$i][$_]=$a[$i][$_]?2:$a[$i-1][$_]+($_&&$a[$i][$_-1])+$a[$i+1][$_]+$a[$i][$_+1]==1?1:0,0..$#a}@a=@b}1..$_;say@$_ for@a

```

Try it online!

Uses 0 for empty, 1 for awake, and 2 for asleep.

# Answer
> 3 votes
# Ruby, <sub>~~164~~</sub> 153 bytes

```
->n{(r=([e=' ']*(l=2*n+1)<<"
")*l)[n+n*l+=1]=a=?@
n.times{r=r.map.with_index{|c,i|c==a ??#:c==e ?r.values_at(i-1,i+1,i-l,i+l).one?{|v|v==a}?a:e:c}}
r*""}

```

Try it online!

Uses " " for Empty, "@" for Awake, and "#" for Sleeping (as in the example). I could save 6 bytes by using numbers instead, I suppose, but it looks better like this.

# Answer
> 2 votes
# Pip, ~~69~~ 61 bytes

60 bytes of code, +1 for `-l` flag.

```
YZG2*a+1y@a@a:1LaY{y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1}MC#yy

```

Takes `n` as a command-line argument. Uses `0` for empty, `1` for awake, and `2` for sleeping. (To get nicer ASCII-art as in the challenge's examples, replace the final `y` with `" @#"@y`.)

Try it online!

### Explanation

Setup:

```
YZG2*a+1y@a@a:1

                 Implicit: a is 1st cmdline arg; o is 1; v is -1
 ZG2*a+1         Square grid (i.e. nested list) of 0's, with side length 2*a+1
Y                Yank into y variable
        y@a@a:1  Set the element at coordinates (a,a) to 1

```

Main loop:

```
LaY{...}MC#y

La            Loop (a) times:
          #y  Len(y) (i.e. 2*a+1)
   {   }MC    Map this function to the coordinate pairs in a 2*a+1 by 2*a+1 grid
  Y           and yank the resulting nested list back into y

```

where the function body is:

```
y@a@b?2oN(y@(a+_)@(b+B)MP[0o0v0])=1

                                     The function args, representing the coords of the
                                     current cell, are a and b
y@a@b?                               Is the cell at these coords 0 or nonzero?
      2                              If nonzero (1 or 2), make it 2
                                     Else, if zero, we need to check the neighbors
                         [0o0v0]     List of [0; 1; 0; -1; 0]
                       MP            Map this function to each adjacent pair of values--
                                     i.e. call it four times with args (0; 1), (1; 0),
                                     (0; -1), and (-1; 0)
          y                           Index into the grid using
           @(a+_)                     a + the 1st item in the pair as the row and
                 @(b+B)               b + the 2nd item in the pair as the column
                                     The result of MP is a list of the values of the cells
                                     in the Von Neumann neighborhood
       oN(                      )    Get the number of 1's in that list
                                 =1  and test if it equals 1
                                     If so, the new value of this cell is 1; if not, it's 0

```

After the loop, we simply autoprint `y`. The `-l` flag means that the nested list is printed by concatenating the contents of each row and separating the rows with newlines.

# Answer
> 2 votes
# Java (OpenJDK 8), 220 bytes

```
n->{int s=n*2+3,i=0,x,y;char[][]a=new char[s][s],b;for(a[s/2][s--/2]=61;i++<n;a=b)for(b=new char[s+1][s+1],x=0;++x<s;)for(y=0;++y<s;)b[x][y]=a[x][y]>32?'0':(a[x][y-1]+a[x][y+1]+a[x-1][y]+a[x+1][y])%8==5?61:' ';return a;}

```

Try it online!

Note: the array returned contains a border or `'\0'` characters. Since the plane is supposed to be infinite, only non-border is used.

Character mapping:

* Empty:  (space)
* Awake: `=`
* Sleeping: `0`

## Saves

* 29 bytes saved thanks to Jonathan S.
* 9 further bytes thanks to Jonathan S. by swapping characters with others and "doing magic with primes and modular arithmetic"

# Answer
> 2 votes
# Python, ~~199~~ 192 bytes

This code runs on both Python 2 and Python 3, but it uses the popular 3rd-party Numpy library to do the array handling.

```
from numpy import*
def f(n):
 m=2*n+1;g=zeros((m+2,)*2,'i');g[n+1,n+1]=1
 while n:a=g[1:-1,1:-1];a[:]=(a<1)*(sum(g[r:r+m,c:c+m]&1for r,c in((0,1),(1,0),(1,2),(2,1)))==1)+(a>0)*2;n-=1
 return g

```

> Empty = 0
> Awake = 1
> Sleeping = 2

`print(f(6))` outputs

```
[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 1 2 2 2 2 2 2 2 2 2 2 2 1 0]
 [0 0 0 2 1 2 0 2 0 2 1 2 0 0 0]
 [0 0 0 1 0 0 2 2 2 0 0 1 0 0 0]
 [0 0 0 0 0 0 1 2 1 0 0 0 0 0 0]
 [0 0 0 0 0 1 2 2 2 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 2 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]]

```

If you want prettier printing, you can call it this way:

```
n=6;print('\n'.join(''.join(' @#'[v]for v in u)for u in f(n)))

```

which prints using the same characters as given in the question.

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


title: A Dance of Many Dimensions

text:
# Question
Title: A Dance of Many Dimensions
### Challenge

Given a `n`-dimensional array of integers and a permutation of the first `n` natural numbers, permute the array dimensions accordingly.

### Details

This challenge is inspired by MATLABs `permute`. demonstration The permutation is given as a list of integers, e.g. `[1,3,2]` means 1 gets mapped to 1, 2 gets mapped to 3 and 3 gets mapped to 2 (here the `i`th entry is the value `i` gets mapped to). But you can use other formats that are convenient, for instance as cycles or as a function. If it is more convenient you can also use 0-based indexing.

The array can be assumed to be a full "rectangular" `m1 x m2 x ... x mn`-array (i.e. you can assume it is not ragged/jagged).

You can assume that `n` is not too large, as many languages have a limit of the number of dimensions in a nested array.

If your language does not support multidimensional arrays, you can also take a string that represents the array as input.

### Examples

* Any `n`-dimensional array with the identity permutation `[1,2,3,...,n]` will be unchanged.
* The array `[[10,20,30],[40,50,60]]` with the permutation `[2,1]` gets mapped to `[[10,40],[20,50],[30,60]]`.
* The array `[[[1,2],[3,4]],[[5,6],[7,8]]]` with the permutation `[2,3,1]` gets mapped to `[[[1,3],[5,7]],[[2,4],[6,8]]]`.

# Answer
# Languages with built-in solutions

*based on this proposal by xnor*

## APL (Dyalog Unicode), 1 byte

Try it online!

## , 2 bytes

```
|:

```

Try it online!

## , 5 bytes

```
aperm

```

Try it online!

## Octave/MATLAB, 8 bytes

```
@permute

```

Try it online!

## Wolfram Language (Mathematica), 9 bytes

```
Transpose

```

Try it online!

## Julia, 11 bytes

```
permutedims

```

Try it online!
> 14 votes

# Answer
# Haskell, 168 bytes

`p` is a (type class polymorphic) function taking a permutation as a list of `Int`s, and a nested list representing a multidimensional array of `Int`s.

Call as `p [2,1] [[10,20,30],[40,50,60]]`, however if type defaulting doesn't succeed, you may have to add a type annotation like `:: [[Int]]` (nested appropriately) giving the type of the result.

```
import Data.List
class P a where p::[Int]->[a]->[a]
instance P Int where p _=id
instance P a=>P[a]where p(x:r)m|n<-p r<$>m,y:z<-sort r=last$n:[p(x:z)<$>transpose n|x>y]

```

Try it online!

Golfing challenges with nested arrays of arbitrary depth are a bit awkward in Haskell, because the static typing tends to get in the way. While Haskell lists (with the exact same syntax as in the challenge description) can be nested just fine, lists of different nesting depth are of incompatible types. Also, standard Haskell parsing functions require knowing the type of the value you are trying to parse.

As a result, it seems inevitable that the program needs to include type-related declarations, which are relatively verbose. For the golfed part, I settled on defining a type class `P`, such that `p` can be polymorphic over the type of the array.

Meanwhile, the TIO's testing harness shows a way to get around the parsing problem.

# How it works

* To sum up the essence of this algorithm: It performs a bubble sort on the permutation list, transposing neighboring dimensions when the corresponding permutation indices are swapped.
* As given by the `class P a` declaration, in any instance, `p` takes two arguments, a permutation (always of type `[Int]`) and an array.
* The permutation can be given in the form in the challenge description, although the way the algorithm works, the choice of indices is arbitrary, except for their relative order. (So both 0- and 1- based work.)
* The base `instance P Int` handles arrays of dimension 1, which `p` simply returns unchanged, since the one dimension can only be mapped to itself.
* The other `instance P a => P [a]` is defined recursively, calling `p` with dimension *n* subarrays in order to define it for dimension *n+1* arrays.
    + `p(x:r)m` first calls `p r` recursively on every element of `m`, giving a result array `n` in which all dimensions except the first have been permuted correctly relatively to each other.
    + The remaining permutation that needs to be performed on `n` is given by `x:y:z = x:sort r`.
    + If `x<y` then the first dimension of `n` is already correctly placed, and `n` is simply returned.
    + If `x>y`, then the first and second dimension of `n` need to be swapped, which is done with the `transpose` function. Finally `p(x:z)` is applied recursively to every element of the result, ensuring the original first dimension is transposed to the right position.
> 10 votes

# Answer
# Python 2, 312 bytes

This uses 0-indexing for the permutation

```
from numpy import*
from itertools import*
z=range
def f(i,r):
	l=array(i).shape;R={b:a for a,b in enumerate(r)};r=len(r);m=eval('['*r+'0'+q('for k in z(l[R[%s]])]',r-1,-1,-1))
	for d in product(*[z(p) for p in l]):exec'm'+q('[d[R[%s]]]',r)+'=i'+q('[d[%s]]',r)
	return m
q=lambda s,*j:''.join(s%(j)for j in z(*j))

```

Try it online!

*-2 bytes thanks to @Jonathan Frech.*
> 3 votes

# Answer
# Python 2, ~~41~~ 25 bytes

```
import numpy
numpy.einsum

```

Try it online!

The permutation vector `p` is given as a string of letters. So `[2,3,1]` can be be given as `'bca'`.

Thanks to @EriktheOutgolfer saved 16 bytes!
> 3 votes

# Answer
## JavaScript (ES6), ~~136~~ 132 bytes

```
(a,p,v=[],r=[],g=(a,[d,...p],_,h=(r,[i,...v])=>1/v[0]?h(r[i]=r[i]||[],v):r[i]=a)=>1/d?a.map((e,i)=>g(e,p,v[d]=i)):h(r,v))=>g(a,p)&&r

```

0-indexed. Explanation: `g` recursively iterates over the array `a` building up an array `v` of indices reordered using the permutation `p`. Once `p` is exhausted, `h` then recursively inserts the element into the result array `r` using the permuted indices.
> 2 votes

---
Tags: code-golf, array, permutations
---


title: Prime numbers between n and 2n

text:
# Question
Title: Prime numbers between n and 2n
Bertrand's postulate states that there is always at least 1 prime number between **n** and **2n** for all **n** greater than **1**.

# Challenge

Your task is to take a positive integer **n** greater than **1** and find all of the primes between **n** and **2n** (exclusive).

Any default I/O method can be used. Whoever writes the shortest code (in bytes) wins!

# Test cases

```
**n**    **2n**     **primes**

2    4      3
7    14     11, 13
13   26     17, 19, 23
18   36     19, 23, 29, 31
21   42     23, 29, 31, 37, 41
```

# Answer
# Jelly, 4 bytes

```
‘æRḤ

```

Try it online!

*waiting for OP's answer in comment...*

(doesn't work for `n=1`)
> 3 votes

# Answer
# Haskell, 45 bytes

*-2 bytes thanks to BMO.*

```
f n=[i|i<-[n+1..2*n],all((>0).mod i)[2..i-1]]

```

Try it online!
> 3 votes

# Answer
# Pari/GP, 20 bytes

```
n->primes([n+1,2*n])

```

Try it online!
> 3 votes

# Answer
# Japt, 6 bytes

```
ôU Åfj

```

## Explanation:

```
 ôU Åfj
U        // Implicit input                     7
 ôU      // Inclusive range [Input...Input+U]  [7,8,9,10,11,12,13,14]
    Å    // Remove the first item              [8,9,10,11,12,13,14]
     fj  // Filter primes                      [11,13]

```

Try it online!
> 3 votes

# Answer
# Octave, 27 bytes

```
@(n)(k=n+1:2*n)(isprime(k))

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~59~~ 57 bytes

```
def f(n):k=m=1;exec('m%k*k>n!=print(k);m*=k*k;k+=1;'*2*n)

```

Try it online!
> 2 votes

# Answer
# Octave, 24 bytes

```
@(n)(k=primes(2*n))(k>n)

```

Try it online!
> 2 votes

# Answer
# PL/SQL, 270 bytes

```
declare
 n number:=7;
 p number;
 v number:=0;
begin
 for i in (n+1)..(n*2)-1 loop
  p:=0;
  for j in 2..trunc(sqrt(n*2)) loop
   if mod(i,j)=0 then p := 1;
    exit;
   end if;
  end loop;
  if p =0 then
   dbms_output.put_line(i);
   v:=v+1;
  end if;
 end loop;
end;

```
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
·ÅPʒ‹

```

Try it online!

### How?

```
·ÅPʒ‹ || Full program.
      ||
·     || Double the input.
 ÅP   || Lists all the prime lower than or equal to ^.
   ʒ‹ || Filter-keep those which are greater than the input.

```
> 1 votes

# Answer
# APL NARS, 45 bytes, 26 chars

```
{⍵≤1:⍬⋄(0πt)/t←(⍵+1)..2×⍵}

```

Perhaps better the range in Axiom: When a\>b than a..b is the void set. Test

```
  g←{⍵≤1:⍬⋄(0πt)/t←(⍵+1)..2×⍵}
  g 7
11 13
  g 9
11 13 17
  g 0

  g 1

  g 2
3
  g 6.3
DOMAIN ERROR

```
> 1 votes

# Answer
# PowerShell, 57 bytes

```
param($n)(2*$n-1)..++$n|?{'1'*$_-match'^(?!(..+)\1+$)..'}

```

Try it online!

Takes input `$n`, constructs a range from `2*$n-1` to `++$n` (i.e., excluding the endpoints), and feeds that range into a `Where-Object` cmdlet. The clause is the regex pattern match against unary numbers. Thus, those numbers where that clause is true (i.e., they are prime) are filtered out of the range and left on the pipeline. Output is implicit.
> 1 votes

# Answer
## JavaScript (ES6), ~~63~~ 62 bytes

*Saved 1 bytes thanks to @Arnauld*

```
f=(n,q=n,x)=>n?q%x?f(n,q,x-1):f(n-1,q+1,q).concat(x<2?q:[]):[]

```
> 1 votes

# Answer
# APL (Dyalog Unicode), 39 bytes

```
⎕CY'dfns'⋄
{1↓(10pco(⍵+0⍵))/(-⍵)↑⍳⍵+⍵-1}

```

Try it online!

The characters `B←` are not counted towards the byte count because they're unnecessary and are added to TIO so it's easier to call the function. Also, `⍎'⎕CY''dfns''⋄⍬'` is the equivalent to `⎕CY'dfns'⋄`, but TIO doesn't accept the usual APL notation for that, so the extra characters are needed.

Thanks to @ErikTheOutgolfer for 1 byte.

### How it works:

```
⎕CY'dfns'⋄                          ⍝ Imports every direct function. This is needed for the primes function, 'pco'.
{1↓(10pco(⍵+0⍵))/(-⍵)↑⍳⍵+⍵-1}      ⍝ Main function, prefix.
   (10pco      )                   ⍝ Calls the function 'pco' with the modifier 10, which lists every prime between the arguments:
         (⍵+0⍵)                    ⍝ Vector of arguments, ⍵ and 2⍵.
                                   ⍝ The function returns a boolean vector, with 1s for primes and 0s otherwise.
 1↓                                ⍝ Drops the first element of the vector (because Bertrands postulate excludes the left bound).
                /                  ⍝ Replicate right argument to match the left argument.
                      ⍳⍵+⍵-1       ⍝ Generate range from 1 to 2⍵-1 (to exclude the right bound)
                     ↑             ⍝ Take from the range
                 (-⍵)              ⍝ The last ⍵ elements.

```
> 1 votes

# Answer
# Perl 6, 27 bytes

```
{grep &is-prime,$_^..^2*$_}

```

Try it

## Expanded:

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

  grep         # find all values

    &is-prime, # that are prime

               # from the following

      $_
      ^..^     # create a Range that excludes both endpoints
      2 * $_
}

```
> 1 votes

# Answer
# 05AB1E, 5 bytes

```
xŸ¦ʒp

```

Try it online!

# Explanation

```
xŸ¦ʒp  Full Program
x      double top of stack
 Ÿ     inclusive range
  ¦    remove first element (pop a: push a[1:])
   ʒ   filter to keep
    p  prime elements

```

-1 byte thanks to Mr. Xcoder
> 0 votes

# Answer
# C, 72 bytes

```
i,k;f(n){for(k=n*2;++n<k;i<k&&printf("%d ",n))for(i=1;++i<n;)i=n%i?i:k;}

```

Try it online!
> 0 votes

# Answer
# Java 8, ~~95~~ 92 bytes

```
q->{for(int n=q,i,x;++n<2*q;){for(x=n,i=2;i<x;x=x%i++<1?0:x);if(x>1)System.out.println(n);}}

```

-3 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
q->{                // Method with integer parameter and no return-type
  for(int n=q,i,x;++n<2*q;){
                    //  Loop `n` in the range (q,2q):
    for(x=n,        //   Set `x` to `n`
        i=2;i<x     //   Loop `i` in the range [2,n):
        ;           //     After every iteration:
         x=x%i++<1? //      If `x` is divisible by `i`:
            0       //       Set `x` to 0
           :        //      Else:
            x);     //       Leave it unchanged
    if(x>1)         //    If `x` is larger than 1 at the end of the inner loop
                    //    (which means it's a prime):
      System.out.println(n);}}
                    //     Print this prime `n`

```
> 0 votes

# Answer
# Wolfram Language (Mathematica) 28 bytes

This is fairly straightforward: within the range of (n+1,2n), select numbers that are primes.

```
Range[#+1,2#]~Select~PrimeQ&

```

**Example**

```
Range[#+1,2#]~Select~PrimeQ&[7]

(* {11, 13} *)

```
> 0 votes

# Answer
# Husk, 6 bytes

```
fṗtS…D

```

Try it online!

### Explanation

```
fṗtS…D -- example input: 7
   S…  -- range from itself (inclusive) to itself..
     D -- | .. doubled
       -- : [7,8,9,10,11,12,13,14]
  t    -- tail: [8,9,10,11,12,13,14]
fṗ     -- filter primes: [11,13]

```

## Alternative, 6 bytes

```
fṗ§…→D

```

Try it online!

### Explanation

```
fṗ§…→D -- example input: 7
  §…   -- range from ..
     D -- | .. itself incremented to
       -- | .. itself doubled
       -- : [8,9,10,11,12,13,14]
fṗ     -- filter primes: [11,13]

```
> 0 votes

# Answer
# Julia 0.4, 17 bytes

Prime related functions wered moved to a package in Julia 0.5, so this would require `using Primes` in newer versions, and also TIO doesn't have that package installed.

```
n->primes(n+1,2n)

```

Try it online!
> 0 votes

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


title: Recursive Collatz Conjecture

text:
# Question
Title: Recursive Collatz Conjecture
The Collatz conjecture postulates that if you take any positive integer, then repeat the following algorithm enough times:

```
if number is odd, then multiply by three and add one
if number is even, then divide by two

```

you'll eventually end up at 1. It seems to always work, but it's never been proven that it always does.

You've already golfed calculating how long it takes to get to 1, so I thought I'd switch things up a bit.

Starting with a given positive integer, calculate how long it takes to get to 1 (its "stopping time"). Then find *that* number's stopping time.

Repeat until you get to 1, or until you get to the entirely arbitrary limit of 100 iterations. In the former case, print how many iterations it took. In the latter case, print "Fail" or some other consistent output of your choice, as long as it's not an integer `1≤n≤100`. You may not output an empty string for this option. Outputting an integer outside of the range \[1, 100\], however, is allowed.

## Examples:

```
Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6

```

As I calculated `10^100` and `12345678901234567890` using a language that only supports reals for that size, if your language is more accurate you may get different results for those.

## Scoring

As this is , the answer with the shortest amount of bytes wins.

# Answer
> 3 votes
# Jelly, 24 bytes

```
×3‘$HḂ?’Ð¿L’
Ç1¹?ȷ2Ð¡i1’

```

Try it online!

# Answer
> 9 votes
# Python 2, 70 bytes

```
f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)

```

Returns **199** for one hundred or more iterations.

Try it online!

# Answer
> 6 votes
# Attache, 40 bytes

```
`-&3@`#@PeriodicSteps[CollatzSize@Max&1]

```

Try it online!

This is a new language that I made. I wanted to get around to making a proper infix language, and this is the result: a mathematica knock-off. Hooray?

## Explanation

This is a composition of a few functions. These functions are:

* `PeriodicSteps[CollatzSize@Max&1]` This yields a function which applies its argument until the results contain a duplicate element. This function, `CollatzSize@Max&1`, is applying `CollatzSize` to the greater of the input and `1`, to avoid the invalid input `0` to CollatSize.
* ``#` is a quoted operator; when applied monadically in this sense, it obtains the size of its argument
* ``-&3` is a bonded function, which bonds the argument `3` to the function ``-`, which reads as "minus 3". This is because the PeriodicSteps application yields `0`s, which need to be accounted for. (It also neatly handles out-of-bounds numbers like `5`, which map to `-1`.)

# Answer
> 4 votes
# C (gcc), 75 bytes

```
i,j;f(n){for(j=0;(i=n)&&j++<100;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j-1;}

```

Returns `-1` for `n>=100` iterations.

Try it online!

# C (gcc), 73 bytes

```
i,j;f(n){for(j=-1;(i=n)&&j++<99;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j;}

```

Returns `0` for `n>=100` iterations.

Try it online!

# Answer
> 4 votes
# , <sub>~~49~~</sub> 45 bytes

-4 bytes thanks to shorter Collatz Sequence code taken from @randomra's comment here.

```
(2-~[:#(>&1*-:+2&|*+:+>:@-:)^:a:)^:(<101)i.1:

```

Outputs `101` for invalid results.

Try it online!

# Explanation

Unsurprisingly, this explanation has become quickly outdated. I'm going to leave it in terms of the old 49 byte answer I had, which I'm including below. If you want an update, just let me know. The way that it finds the length of the recursive sequence remains the same, I've just used a shorter Collatz Sequence method.

```
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)^:(<101)i.1:

```

### Finding the length of the Collatz Sequence

This section of the code is the following

```
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)

```

Here's the explanation:

```
(1 -~ [: # %&2`(1+3&*)@.(2&|) ^: (1&<) ^: a:)  Given an input n
                                       ^: a:   Apply until convergence, collecting
                                                each result in an array.
                              ^: (1&<)         If n > 1 do the following, else
                                                return n.
                        (2&|)                  Take n mod 2.
           %&2                                 If n mod 2 == 0, divide by 2.
               (1+3&*)                         If n mod 2 == 1, multiply by 3
                                                and add 1.
         #                                     Get the length of the resulting
                                                array.
 1 -~                                          Subtract 1.

```

Unfortunately, the apply verb (`^:`) when told to store results stores the initial value too, so it means we're (like always) off by one. Hence why we subtract 1.

### Finding the length of the recursive sequence

```
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:) ^: (< 101) i. 1:  Given an input n.
                                      ^: (< 101)        Apply 100 times,
                                                         collecting results
                                                         in an array.
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)                   Collatz sequence length.
                                                 i. 1:  Index of first 1 (returns
                                                         101, the length of the
                                                         array if 1 not found).

```

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

Returns `true` when it fails. Returns `0` for `1`.

```
f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

```

### Test cases

```
f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

console.log(f(2))    // 1
console.log(f(5))    // fail
console.log(f(10))   // 8
console.log(f(100))  // 13
console.log(f(1))    // 0
```

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~39~~ ~~60~~ ~~53~~ ~~52~~ 49 bytes

-3 bytes thanks to @ngn

```
0∘{99<⍺:⋄1=⍵:0⋄1+(⍺+1)∇{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}⍵}

```

Try it online!

Uses @ngn code for Collatz, but previously used @Uriel's code.

Here's the old version that didn't meet the specification:

```
{1=⍵:0⋄1+∇{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}⍵}

```

# Answer
> 2 votes
# Perl 6, 56 bytes

```
{($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}

```

Try it online!

Returns `101` for a non-terminating sequence.

# Answer
> 2 votes
# Husk, 21 bytes

```
←€1↑101¡ȯ←€1¡?½o→*3¦2

```

Try it online! Returns `-1` on failure, `0` on input `1`.

## Explanation

```
←€1↑101¡ȯ←€1¡?½o→*3¦2  Implicit input (a number).
             ?½o→*3¦2  Collatz function:
             ?     ¦2   if divisible by 2,
              ½         then halve,
               o→*3     else multiply by 3 and increment.
        ȯ←€1¡?½o→*3¦2  Count Collatz steps:
            ¡           iterate Collatz function and collect results in infinite list,
          €1            get 1-based index of 1,
        ȯ←              decrement.
       ¡               Iterate this function on input,
   ↑101                take first 101 values (initial value and 100 iterations),
←€1                    get index of 1 and decrement.

```

# Answer
> 2 votes
# C (gcc), ~~70~~ 73 bytes

```
g(x){x=x-1?g(x%2?3*x+1:x/2)+1:0;}f(x,m){for(m=0;(x=g(x))&&100>m++;);x=m;}

```

Try it online!

Returns `101` when number of iterations exceeds 100.

# Answer
> 2 votes
# Clean, ~~146~~ ... 86 bytes

*-11 bytes thanks to Ørjan Johansen*

```
import StdEnv
?f l n=hd[u\\1<-iterate f n&u<-l]

```

#

```
?(?(\b|isOdd b=3*b+1=b/2)[0..])[0..99]

```

As a partial function literal.

Try it online!

Aborts with `hd of []` if the number of iterations exceeds 100.
Exits with `Heap Full` for inputs above ~`2^23` unless you specify a larger heap size.

# Answer
> 1 votes
# Python 2, ~~99~~ ~~98~~ 97 bytes

* Saved a byte by using `c and t or f` instead of `t if c else f`.
* Saved a byte by outputting `-1` instead of `f` or `'f'` for non-halting inputs.

```
exec"f,F="+"lambda n,i=0:n<2and i or %s"*2%("f([n/2,3*n+1][n%2],-~i),","i>99and-1or F(f(n),-~i)")

```

Try it online!

# Answer
> 1 votes
## BiwaScheme, 151 chars

```
(define(f n i s)(if(= s 0) 'F(if(= n 0)i(f(letrec((c(lambda(m k)(if(= m 1)k(c(if(=(mod m 2)0)(/ m 2)(+(* m 3)1))(+ k 1))))))(c n 0))(+ i 1)(- s 1)))))

```

You can try it here.

# Answer
> 1 votes
**(Emacs, Common, ...) Lisp, 105 bytes**

Returns t for iterations \> 100

```
(defun f(n k c)(or(> c 100)(if(= n 1)(if(= k 0)c(f k 0(1+ c)))(f(if(oddp
n)(+ n n n 1)(/ n 2))(1+ k)c))))

```

Expanded:

```
(defun f (n k c)
  (or (> c 100)
      (if (= n 1)
          (if (= k 0) c
            (f k 0 (1+ c)))
        (f (if (oddp n) (+ n n n 1) (/ n 2))
           (1+ k) c))))
(f (read) 0 0)

```

# Answer
> 1 votes
# APL NARS, 115 bytes, 63 chars

```
{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}

```

Probably using loops it would be more clear... There are 4 functions, 2 nested and ricorsive, and the first only for define and initialize to =0, the variable d, seen from the 2th function as a global variable counter.

```
q←{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}

```

This 3th function, would be the function that return how many call there are for resolve the Collatz conjecture for its arg

```
{⍵=1:d⋄99<d+←1:¯1⋄∇q⍵}

```

This is the 2th function, if has its arg =1,stop its recursion and return d the number of time it is called itself-1; else if itself is called more than 99times stop its recursion and return -1(fail) else calculate Collatz conjecture for its arg, and call itself for the Collatz sequence length value. For me even if all this seems run could be a big problem if is defined a global variable and one variable in a function of the same name, when the programmer sees it as just a local variable.

```
  f←{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}
  f 2
1
  f 3
5
  f 5
¯1
  f 10
8
  f 100
13
  f 12313
7
  f 1
0

```

# Answer
> 1 votes
# , ~~119~~ 107 bytes

Partially uses Jarko Dubbeldam's collatz code from here. Returns `0` for \>100 iterations (failure).

```
pryr::f(x,{N=n=0
while(x-1){while(x-1){x=`if`(x%%2,3*x+1,x/2);n=n+1}
x=n
n=0
N=N+1
if(N==100)return(0)}
N})

```

Try it online!

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


title: Riffle shuffle a string - Robbers

text:
# Question
Title: Riffle shuffle a string - Robbers
Cops post

A ***riffle shuffle*** is a way of shuffling cards where the deck is split into 2 roughly equal sections and the sections are riffled into each other in small groups. This is how to riffle shuffle a string:

* Split the string into equal sections.
* Reverse the string, and starting from the start of each string.
* Put runs of a random length between 1 and the number of characters left into the final string
* Then remove these characters from the strings.

**An example**

```
"Hello World!"      Output string = ""
"Hello ", "World!"  ""
"Hell", "World!"    " o"
"Hell", "World"     " o!"
"Hel", "World"      " o!l"
"Hel", "Wo"         " o!ldlr"
"H", "Wo"           " o!ldlrle"
"H", ""             " o!ldlrleoW"
"", ""              " o!ldlrleoWH"

```

The final product from `Hello World!` could be `o!ldlrleoWH` and that is what you would output.

## Robbers

Your task is to take a Cops submission and rearrange so that it produces a valid riffle shuffler program. You may not add, remove or change any characters in the original program to result in your solution.

If the program works, even if it is not the cops intended solution, it is a valid crack.

The winner is the person who cracks the most Cops submissions!

# Answer
> 2 votes
# Python 3, HyperNeutrino

```
from random import*
def r(i):
    s=len(i)//2;L,R=i[:s][::-1],i[s:][::-1];o=[]
    while L and R:s=randint(1,len(L));o+=L[:s];L,R=R,L[s:]
    return o+L+R

```

Try it online!

Proof of Same Character Set

# Answer
> 2 votes
# Jelly, HyperNeutrino

```
œs2UŒṖ€X€ż/

```

Try it online!

# Answer
> 1 votes
# Pyth, notjagan

```
jk.iFmO./_dc2Q

```

**Try it here!**

### Explanation

The Pyth interpreter also offers a nice pseudo-code if you check the "Debug" box.

* `c2Q` **c**hops the input into **2** pieces of equal length, with initial pieces one longer if necessary.
* `m` **m**aps a function over the pieces. Variable: `d`.

+ `_d` reverses **d**
    + `./` partitions the reverse of **d**; returns all divisions of the reversed **d** into disjoint contiguous substrings.
    + `O` chooses a rand**O**m partition.
* `.iF` **F**olds (reduces) the list by **.i**nterleaving.
* And finally `jk` **j**oins the list of strings.

# Answer
> 1 votes
# , Giuseppe

```
function(s){n<-nchar(s)
s<-methods::el(strsplit(s,''))
l<-head(s,n/2)
r<-tail(s,n/2)
o<-{}
while(length(l)|length(r)){if(length(r)){y<-sample(length(r),1)
o<-c(o,rev(head(r,y)))
r<-tail(r,-y)}
if(length(l)){x<-sample(length(l),1)
o<-c(o,rev(head(l,x)))
l<-tail(l,-x)}}
cat(o,sep='')}

```

Try it online!

# Answer
> 1 votes
# Pushy, FlipTack

```
L2/:v;O@N[1LU:'.;FL0=?x?i

```

Try It Online

---
Tags: string, random, permutations, cops-and-robbers
---


title: String replicator

text:
# Question
Title: String replicator
In Vim, you can repeat a command by preceding it with a number, like `3dd` is equivalent to `dd dd dd`. Well, this repeating pattern is not restricted to Vim commands. String can be replicated in this way, too.

### Specification:

Given a string, consisting of only digits, alphabetical characters (both upper-case and lower-case) and spaces, with an optional trailing newline, as input, write a program that does the following job:

* Each "word" consists of digits and alphabets. If a letter is preceded with a number (there may be more than one digit in a number, or the number is zero), repeat that letter for the given times. For example:

```
a2bc -> abbc
3xx1yz -> xxxxyz
10ab0c0d0e -> aaaaaaaaaab # No 'cde' because there's a zero
2A2a2A2a -> AAaaAAaa

```
* Words are separated by spaces. There's a maximum of one space between every two adjacent words.

Easy, right? Here's the additional stuff:

* If there's a number before the space, repeat the next word for the given times. The number will always be attached to the end of the previous word, or at the start of the string. Example:

```
a2bc3 2d -> abbc dd dd dd
3 3a -> aaa aaa aaa
33a -> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
0 abcd0 efgh3 2x -> xx xx xx
a3 0xc b -> a c c c b

```
* If an empty word ought to be repeated, don't output multiple spaces in a row. Squash them:

```
a3 0x2 b -> a b b   # NOT 'a    b b'

```

In other words, your program should never output two spaces together.
* Input is never empty, but it's not necessary for the output to be non-empty:

```
0 3x -> (empty)

```

* Input and output can be taken in any preferred ways. A function taking input from arguments and giving output via return values is acceptable as well.

If it's a program, it must not exit with error (i.e. return value is zero).
* Numbers are always decimal, and never starts with a zero, unless the number itself is zero, in which case there's only one zero. I.e. you don't need to consider `077a` or `000a` given as input.
* All numbers are under 2^31 (2,147,483,648). Maximum output length is under 2^32 (4,294,967,296) bytes.
* The program may optionally output one trailing space and/or one trailing newline. Those space and newline do not affect the validity of output. Even if the correct output should be empty, an output of a space followed by a newline will qualify.

In short, a valid input matches this regular expression:

```
([0-9]+ )?([0-9A-Za-z]*[A-Za-z])([0-9]* [0-9A-Za-z]*[A-Za-z])*( ?\n?)

```

And for a valid output:

```
([A-Za-z]+)( [A-Za-z]+)*( ?\n?)

```

Sample test cases:

```
abcdefg -> abcdefg
a3bcd -> abbbcd
a3bbbc -> abbbbbc
3a0b -> aaa
abc 3d -> abc ddd
abc3 d -> abc d d d
5 1x5 1y0 z -> x x x x x y y y y y
a999 0x b -> a b
999 0s -> (empty)
0 999s -> (empty)
0 999s4 t -> t t t t
a3 0xc b -> a c c c b
ABC3 abc -> ABC abc abc abc

```

This is a , so the shortest program in bytes in each language wins!

# Answer
> 3 votes
# JavaScript (Node.js), ~~102~~ ~~129~~ ~~110~~ 106 bytes

```
s=>s[p="replace"](/(\d+)( \w*[A-Z])/gi,g=(_,a,b)=>b.repeat(a))[p](/(\d+)(.)/g,g)[p](/ +/g,(_,i)=>i?" ":"")

```

Try it online!

Thanks for @Arnauld for -4 bytes.

# Answer
> 2 votes
# Perl 6, 88 bytes

```
{$_=$^a;s:g/(\d+):(\w)/{$1 x$0||'_'}/;s:g/(\d+)\s([\w& \D]+)/ {$1 xx$0}/;~S:g/_//.words}

```

Test it

## Expanded:

```
{ # bare block lambda with placeholder parameter ｢$a｣

  # store a copy of the argument in ｢$_｣
  # (shorter than ｢-> $_ is copy {…}｣)
  $_ = $^a;
  # note that ｢$_｣ is the default scalar,
  # and many things operate on it by default (like ｢s///｣)

  # do the character repeats
  s :global
  /

    (\d+)           # repeat count
    :               # don't backtrack (prevents it from matching word repeats)
    (\w)            # character to repeat

  /{

    $1 x $0         # do the repeat

    || '_'          # replace with ｢_｣ if the repeat was 0 (matched by [\w & \D])
                    # this is so “words” don't get removed yet

  }/;

  # do the word repeats
  s :global
  /

    (\d+)           # repeat count

    \s              # shortest way to match a space

    ([
      \w & \D       # word character and not a digit (doesn't match next repeat)
    ]+)             # match that at least once

  / {               # add a space (as we removed it by matching it)

    $1 xx $0        # list repeat (adds a space between values when stringified)

  }/;

  # the following is the result
  ~                 # stringify (adds spaces between values in a list) # (3)
    S :global /_//  # remove all _ not in-place                        # (1)
    .words          # get a list of words                              # (2)
}

```

The `~(…).words` combination removes extraneous spaces, which is useful if a “word” gets removed.

# Answer
> 1 votes
# Python 2, ~~286~~ ~~275~~ ~~260~~ ~~257~~ 238 bytes

-19 bytes thanks to ovs

```
def f(s,j=' '.join):exec"s=s.split(%s[-1]):s[i]=s[i][:-1];s[i-1]=j([s[i-1]]*int(w[-1]))\ns=list(j(s[::-1])%s):s[i]='';s[i-1]*=int(w)\nprint j(''.join(s[::-1]).strip().split())"%((')[::-1]\nfor i,w in enumerate(s):\n if str.isdigit(w',)*2)

```

`f` takes a string as an argument and prints the formatted string.

Here's a repl.it with the test cases.

Ungolfed code:

```
def f(s, j=' '.join):
    s = s.split()[::-1]
    for i, w in enumerate(s):
        if str.isdigit(w[-1]):
            s[i] = s[i][:-1]
            s[i - 1] = j([s[i - 1]] * int(w[-1]))
    s = list(j(s[::-1]))[::-1]
    for i, w in enumerate(s):
        if str.isdigit(w):
            s[i] = ''
            s[i - 1] *= int(w)
    print j(''.join(s[::-1]).strip().split())

```

Still working on improvements.

# Answer
> 1 votes
# Perl 5, 77 + 1 (`-p`) = 78 bytes

```
s/\d+( .*?)(\d*)( |$)/$1x$&.$2.$3/eg&&redo;s/\d+(\D)/$1x$&/eg;s/ +/ /g;s;^ +;

```

Try it online!

# Answer
> 0 votes
# Clean, ~~443~~ ... 306 bytes

```
import StdEnv,StdLib
^ =last
$n|n>"9"=1=toInt n
?v c| ^v<c=init v=v
q=groupBy
f[a:t]|a<"a"=repeatn($a)(hd t)++f(tl t)|t>[]=[a:f t]=[a," "]
f e=e
@l#[h:t]=[[toString[c:if(c<'1')[]k]\\[c:k]<-q(\a b=max a b<'a')s]\\s<-q(\a b=min a b>' ')l|s>[' ']]
=flatten(map f[?h"a":[?u":"\\u<-t&v<-map^[h:t],_<-[1.. $v]]])

```

Try it online!

# Answer
> 0 votes
# Lua, 113 bytes

```
a="(%d+)(%a)"g=a.gsub function r(c,s)return s:rep(c)end g(g(g(g(...,a,r),"(%d+)( %a*)",r)," +"," "),"%a.*",print)

```

Try it online!

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


# Question
Title: Create an N-Dimensional Simplex (Tetrahedron)
The Simplest N-Dimensional shape one can create for any dimension is a Simplex, and this is a set of N+1 points that are all equal distance away from eachother.

For 2 dimensions, this is an equilateral triangle, for 3 dimensions, this is an regular tetrahedron, at 4 dimensions is the 5-Cell and so on.

## The Challenge

Given an Integer dimension N as input, output an Array/List/Stack/Whatever of N Dimensional points that represent a Simplex of this dimension. That is, N+1 vertexes that are equal and non-zero distance from eachother.

Reference implementation in Lua

## Examples

```
1 -> [[0], [1]]
2 -> [[0, 0], [1, 0], [0.5, 0.866...]]
4 -> [[0, 0, 0, 0], [1, 0, 0, 0], [0.5, 0.866..., 0, 0], [0.5, 0.288..., 0.816..., 0], [0.5, 0.288..., 0.204..., 0.790...]]

```

## Notes

* Input is a number in any standard format, and will always be an integer greater than 1 and less than 10
* Hardcoding is allowed for input of 1, but nothing higher.
* Reasonable error is allowed in the output. Issues with floating point arithmetic or trig may be ignored.
* Any transformation of the N dimensional simplex is allowed, aslong as it remains Regular and Non-zero.
* Standard Loopholes are forbidden.
* This is , so fewest bytes wins.

# Answer
> 4 votes
# Jelly, 11 bytes

```
‘½‘÷ẋW
=þ;Ç

```

**Try it online!**

Works by generating the identity matrix of size **N** and concatenating it with the list generated by repeating **N** times the singleton **√(N + 1) + 1**, divided by **N**.

```
‘½‘÷ẋW – Helper link (monadic). I'll call the argument N.

‘      – Increment N (N + 1).
 ½     – Square root.
  ‘    – Increment (√(N + 1) + 1).
   ÷   – Divide by N.
    ẋ  – Repeat this singleton list N times.
     W – And wrap that into another list.

––––––––––––––––––––––––––––––––––––––––––

=þ;Ç   – Main link.

=þ     – Outer product of equality.
  ;Ç   – Concatenate with the result given by the helper link applied to the input.

```

# Answer
> 5 votes
# Python ~~78~~ 66 Bytes

```
lambda n:[i*[0]+[n]+(n+~i)*[0]for i in range(n)]+[n*[1+(n+1)**.5]]

```

Surely can be improved, ~~especially at handling n=1\`\`\`. (How is that even a simplex?)~~ Just realized that's not necessary. Can probably be improved still ^^

Try it online!

`[i*[0]+[1]+(n+~i)*[0]for i in range(n)]` creates identity matrix. All points have distance `sqrt(2)` from each other. (thanks to Rod for improving)

Now we need a `n+1`-th point with the same distance to all other points. We have to choose `(x, x, ... x)`.

Distance from `(1, 0, ... )` to `(x, x, ... x)` is `sqrt((x-1)²+x²+...+x²)`. If we want an `n` dimensional simplex this turns out to be `sqrt((x-1)²+(n-1)x²)`, as we have one `1` and `n-1` `0`s in the first point. Simplify a bit: `sqrt(x²-2x+1+(n-1)x²) = sqrt(nx²-2x+1)`

We want this distance to be `sqrt(2)`.

`sqrt(2) = sqrt(nx²-2x+1)`
`2 = nx²-2x+1`
`0 = nx²-2x-1`
`0 = x²-2/n*x+1/n`

Solving this quadratic equation (one solution, other one works fine, too):

`x = 1/n+sqrt(1/n²+1/n) = 1/n+sqrt((n+1)/n²) = 1/n+sqrt(n+1)/n = (1+sqrt(n+1))/n`

Put that in a list `n` times, put that list in a list and join with identity matrix.

---

-4 Bytes thanks to Alex Varga:

Multiply each vector by `n`. This changes the creation of the identity matrix to `lambda n:[i*[0]+[n]+(n+~i)*[0]` (same length) and gets rid of the division by `n` in the additional point, so it becomes `n*[1+(n+1)**.5]`, saving two brackets and the `/n`.

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

```
IdentityMatrix@#~Join~{Table[1-(#+1)^.5,#]/#}&

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog), ~~20~~ 18 bytes

*1 byte thanks to @ngn*

```
∘.=⍨∘⍳⍪1÷¯1+4○*∘.5

```

Try it online!

# Answer
> 1 votes
## JavaScript (ES7), 70 bytes

```
n=>[a=Array(n++).fill((1+n**.5)/--n),...a.map((_,i)=>a.map(_=>+!i--))]

```

Port of @PattuX's Python answer.

# Answer
> 1 votes
# Octave, 31 bytes

Saved 2 bytes thanks to Luis Mendo.

```
@(n)[n*eye(n);~~(1:n)+(n+1)^.5]

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 205 bytes

```
f1 = Sqrt[# (# + 1)/2]/# /(# + 1) & ;
f2 = Sqrt[# (# + 1)/2]/# & ;
simplex[k_] := {ConstantArray[0, k]}~Join~Table[
   Table[f1[n], {n, 1, n - 1}]~Join~{f2[n]}~Join~
    ConstantArray[0, k - n],
   {n, k}]

```

Simplex function in Mathematica Starting from `{0,0,...]},{1,0,0,...]}`, Placing first point at origin, Second point on `x` axis Third point in `x,y` plane, Fourth point in `x,y,z` space, etc. This progression reuses all the previous points, adding one new point at a time in new dimension

```
simplex[6]={{0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0}, {1/2, Sqrt[3]/2, 0, 0, 0,
  0}, {1/2, 1/(2 Sqrt[3]), Sqrt[2/3], 0, 0, 0}, {1/2, 1/(2 Sqrt[3]),
  1/(2 Sqrt[6]), Sqrt[5/2]/2, 0, 0}, {1/2, 1/(2 Sqrt[3]), 1/(
  2 Sqrt[6]), 1/(2 Sqrt[10]), Sqrt[3/5], 0}, {1/2, 1/(2 Sqrt[3]), 1/(
  2 Sqrt[6]), 1/(2 Sqrt[10]), 1/(2 Sqrt[15]), Sqrt[7/3]/2}}

```

### Verification

```
In[64]:= EuclideanDistance[simplex[10][[#[[1]]]],simplex[10][[#[[2]]]]] & /@ Permutations[Range[10],{2}]//Simplify
Out[64]= {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

```

# Answer
> 0 votes
# Pari/GP, 37 bytes

```
n->concat((n+1)^.5-matid(n),1^[1..n])

```

Try it online!

# Answer
> 0 votes
# Ruby, 55 bytes

rather than returning similar magnitudes for all dimensions and using the formula `(1+(n+1)**0.5)/n` I scale up by a factor of `n` to simplify the formula to `(1+(n+1)**0.5)`

```
->n{(a=[n]+[0]*~-n).map{a=a.rotate}+[[1+(n+1)**0.5]*n]}

```

Try it online!

**ungolfed in test program**

A lambda function taking `n` as an argument and returning an array of arrays.

```
f=->n{
  (a=[n]+[0]*~-n).map{        #setup an array `a` containing `n` and `n-1` zeros. perform `n` iterations (which happens to be the the size of the array.)
  a=a.rotate}+                #in each iteration rotate `a` and return an array of all possible rotations of array `a`
  [[1+(n+1)**0.5]*n]          #concatenate an array of n copies of 1+(n+1)**0.5
}

p f[3]                        # call for n=3 and print output

```

**output**

```
[[0, 0, 3], [0, 3, 0], [3, 0, 0], [3.0, 3.0, 3.0]]

```

# Answer
> 0 votes
# , 38 bytes

```
function(n)rbind(diag(n,n),1+(n+1)^.5)

```

Try it online!

---
Tags: code-golf, arithmetic
---


# Question
Title: Collection from a sequence that constitute a perfect square
Given the sequence OEIS A033581, which is the infinite sequence, the **n**'th term (0-indexing) is given by the closed form formula **6 × n2** .

Your task is to write code, which outputs all the subsets of the set of N first numbers in the sequence, such that the sum of the subset is a perfect square.

# Rules

* The integer `N` is given as input.
* You cannot reuse a number already used in the sum. (that is, each number can appear in each subset at most once)
* Numbers used can be non-consecutive.
* Code with the least size wins.

# Example

The given sequence is {0,6,24,54,96,...,15000}

One of the required subsets will be {6,24,294}, because

```
6+24+294 = 324 = 18^2

```

You need to find all such sets of all possible lengths in the given range.

# Answer
# 05AB1E, 10 bytes

```
Ý¨n6*æʒOÅ²

```

**Try it online!**

## How?

```
Ý¨n6*æʒOÅ² || Full program. I'll call the input N.

Ý          || 0-based inclusive range. Push [0, N] ∩ ℤ.
 ¨         || Remove the last element.
  n        || Square (element-wise).
   6*      || Multiply by 6.
     æ     || Powerset.
      ʒ    || Filter-keep those which satisfy the following:
       O   ||---| Their sum...
        Å² ||---| ... Is a perfect square?

```
> 3 votes

# Answer
# Haskell, ~~114 104 103~~ 86 bytes

```
f n=[x|x<-concat<$>mapM(\x->[[],[x*x*6]])[0..n-1],sum x==[y^2|y<-[0..],y^2>=sum x]!!0]

```

Thanks to Laikoni and Ørjan Johansen for most of the golfing! :)

Try it online!

The slightly more readable version:

```
--  OEIS A033581
ns=map((*6).(^2))[0..]

-- returns all subsets of a list (including the empty subset)
subsets :: [a] -> [[a]]
subsets[]=[[]]
subsets(x:y)=subsets y++map(x:)(subsets y)

-- returns True if the element is present in a sorted list
t#(x:xs)|t>x=t#xs|1<2=t==x

-- the function that returns the square subsets
f :: Int -> [[Int]]
f n = filter (\l->sum l#(map(^2)[0..])) $ subsets (take n ns)

```
> 3 votes

# Answer
# Pyth, 12 bytes

-2 bytes thanks to Mr. Xcoder

```
fsI@sT2ym*6*

```

Try it online!

2 more bytes need to be added to remove `[]` and `[0]`, but they seem like valid output to me!

---

Explanataion

```
    fsI@sT2ym*6*
    f                  filter
           y           the listified powerset of
            m*6*ddQ    the listified sequence {0,6,24,...,$input-th result}
        sT             where the sum of the sub-list
     sI@  2            is invariant over int parsing after square rooting

```
> 2 votes

# Answer
# Clean, ~~145~~ ... 97 bytes

```
import StdEnv
@n=[[]:[[6*i^2:b]\\i<-[0..n-1],b<- @i]]
f=filter((\e=or[i^2==e\\i<-[0..e]])o sum)o@

```

Try it online!

Uses the helper function `@` to generate the power set to `n` terms by concatenating each term of `[[],[6*n^2],...]` with each term of `[[],[6*(n-1)*2],...]` recursively, and in reverse order.

The partial function `f` is then composed (where `->` denotes `o` composition) as:
`apply @ -> take the elements where -> the sum -> is a square`

Unfortunately it isn't possible to skip the `f=` and provide a partial function *literal*, because precedence rules require it have brackets when used inline.
> 2 votes

# Answer
# JavaScript (ES7), 107 bytes

```
n=>[...Array(n)].reduce((a,_,x)=>[...a,...a.map(y=>[6*x*x,...y])],[[]]).filter(a=>eval(a.join`+`)**.5%1==0)

```

### Demo

```
let f =

n=>[...Array(n)].reduce((a,_,x)=>[...a,...a.map(y=>[6*x*x,...y])],[[]]).filter(a=>eval(a.join`+`)**.5%1==0)

console.log(f(6).map(a => JSON.stringify(a)).join('\n'))
console.log(f(10).map(a => JSON.stringify(a)).join('\n'))
```

### Commented

```
n =>                      // n = input
  [...Array(n)]           // generate a n-entry array
  .reduce((a, _, x) =>    // for each entry at index x:
    [                     //   update the main array a[] by:
      ...a,               //     concatenating the previous values with
      ...a.map(           //     new values built from the original ones
        y =>              //     where in each subarray y:
          [ 6 * x * x,    //       we insert a new element 6x² before
            ...y       ]  //       the original elements
      )                   //     end of map()
    ],                    //   end of array update
    [[]]                  //   start with an array containing an empty array
  )                       // end of reduce()
  .filter(a =>            // filter the results by keeping only elements for which:
    eval(a.join`+`) ** .5 //   the square root of the sum
    % 1 == 0              //   gives an integer
  )                       // end of filter()

```
> 1 votes

# Answer
# Jelly, 12 bytes

```
Ḷ²6×ŒPSÆ²$Ðf

```

Try it online!

Output is a list of subsets including `0`s and the empty subset.
> 1 votes

# Answer
# Wolfram Language (Mathematica), 49 bytes

Brute force approach

```
Select[Subsets[6Range[#]^2],Sqrt@Tr@#~Mod~1==0&]&

```

Try it online!
> 1 votes

# Answer
# Japt, 15 bytes

```
ò_²*6Ãà k_x ¬u1

```

Try it

---

## Explanation

Generate on array of integers from 0 to input (`ò`) and pass each through a function (`_ Ã`), squaring it (`²`) & mutiplying by 6 (`*6`). Get all the combinations of that array (`à`) and remove those that return truthy (`k`) when passed through a function (`_`) that adds their elements (`x`), gets the square root of the result (`¬`) and mods that by 1 (`u1`)
> 0 votes

---
Tags: code-golf, math, sequence, subsequence
---


# Question
Title: Maximum Area of a Polygon with Vertices of a Polygon
### Rules

Given a list of integer coordinates, **l**, with a length of at least 4, and an integer **n** such that **n** is smaller than the length of **l** (but at least 3), return the largest area of an **n**-sided polygon satisfies:

* is simple (not self-intersecting).
* has all the coordinates of its **n** vertices in the list **l**.
* has no three consecutive collinear vertices.

Note that the polygon given in the input should comply to the three points above as well.

### Test Cases

Here are a few test cases:

```
[(0,0), (0,-1), (-1,-1), (-1,0)], 3 -> 0.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 3 -> 3
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 5 -> 5.5
[(0,0), (1,0), (2,1), (2,2), (1,3), (0,3), (-1,2), (-1,1)], 6 -> 6

```

You can try any test cases you like here.

Make your code as short as possible.

# Answer
# Python 2, 172 bytes

-1 byte thanks to J843136028

bug fix thanks to Jonathan Frech

```
from itertools import*
def f(l,n,L=()):
 for p in combinations(l,n):
  r=0;j=-1
  for i in range(n):r+=(p[j][0]+p[i][0])*(p[j][1]-p[i][1]);j=i
  L+=abs(r/2.),
 print max(L)

```

Try it online!
> 0 votes

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


title: Riffle shuffle a string - Cops

text:
# Question
Title: Riffle shuffle a string - Cops
Robbers post

A ***riffle shuffle*** is a way of shuffling cards where the deck is split into 2 roughly equal sections and the sections are riffled into each other in small groups. This is how to riffle shuffle a string:

* Split the string into equal sections.
* Reverse the strings, and starting from the start of each string.
* Put runs of a uniformly random length between 1 and the number of characters left in the current string into the final string
* Then remove these characters from the string.
* Repeat for the other half, until both halves are empty.

**An example**

```
"Hello World!"      Output string = ""
"Hello ", "World!"  ""
"Hell", "World!"    " o"
"Hell", "World"     " o!"
"Hel", "World"      " o!l"
"Hel", "Wo"         " o!ldlr"
"H", "Wo"           " o!ldlrle"
"H", ""             " o!ldlrleoW"
"", ""              " o!ldlrleoWH"

```

The final product from `Hello World!` could be `o!ldlrleoWH` and that is what you would output.

## Cops

Your task is to make a program (or function) that will riffle shuffle a string. If the inputted string is of odd length, just split it into two uneven length strings with a relative length of `+1` and `+0` (`abc => [ab, c] or [a, bc]`). You may take input in the normal fashion and produce output in the normal fashion.

Your Cops submission will consist of 4 things

* The language you used
* The length of your program in bytes
* **Your program, riffle shuffled.**
* Anything else you want to add

You are aiming to keep your code from being uncracked by the Robbers for 7 days. After that period, your program is *safe* and you should edit in your original program. **Your submission may still be cracked until you reveal your solution.** The shortest, safe solution will be the winner!

# Answer
> 2 votes
# \>\<\>, 46 bytes

```
 }lr]l:l~\r[-r}x>o?
<!l>x![; ?=\?(0:2i
:,2-%2:

```

There’s almost no obfuscations in the real code, but I suspect a 2D language will be hard enough to crack anyway.

Disclaimer: Written before it was specified that it had to be uniformly random. This is not uniformly random, and I'm not sure how I'd even implement a uniformly random algorithm in \>\<\> to begin with.

# Answer
> 2 votes
# Python 3, 154 bytes (list of chars -\> list of chars) (function) Cracked

```
[=o;]1-::[]:s[i,]1-::[]s:[i=R,L;2//)i(nel=s
:)i(r fed
*tropmi modR+L+o nruter
]:s[L,R=R,L;]s:[L=+o;))L(nel,1(tnidnar=s:R dna L elihw
]nar morf

```

I doubt this will be too hard to crack, especially since riffling once is rather ineffective (you can see entire program components in the output...). This is mostly just to get things rolling. There might be some whitespace (including newlines) that I didn't copy correctly. The SHA-384 hash of my intended solution is `5924530418bf8cd603c25da04ea308b124fdddfc61e7060d78b35e50ead69a7fbde9200b5ee16635cc0ee9df9c954fa1`.

# Answer
> 2 votes
# Jelly, 11 bytes, Cracked

This is a golfed version so someone can probably crack it easily just by making a golfy version. There are probably a few different approaches but I suspect this approach will be decently common with golfing languages.

```
Ṗ/Œż€X€U2sœ

```

The SHA-384 hash of my intended program is `86025a659b3c5fc38e943f72b1f26e28e2e751a7118a589073f1d24fa61ff6b02753d6a0f3f0c7fee6555de69fd06a74` (using UTF-8 encoding).

# Answer
> 1 votes
# , 283 bytes, Cracked

```
/n,s(daeh-<l
))'',s(tilpsrts(le::sdohtem-<s
)s(rahcn-<n{)s(noitcnufhtgnel(fi
})x-,l(liat-<l
)))x,l(daeh(ver,o(c-<o
)1,)l(htgnel(elihw
}{-<o
)2/n,s(liat-<r
)2'=pes,o(tac
}})y-,r(liat-<r
)))y,r(daeh(ver,o(c-<o
)1,)r(htgnel(elpmas-<y{))r(l(fi{))r(htgnel|)l(htgnel()'htgne}(lpmas-<x{))le

```

I realize now that writing a longer answer has more "runs" of characters that are preserved, alas.

Good luck!

# Answer
> 1 votes
# Röda, 118 bytes

```
2//x#=z}][=]:y[x
}]0>)b..a(#[]1-::[]:y[x
x#%)(reelihw}]0>b#[fi)b(g
getnI]0>a#[fi)a(g{]mo:z[x=b]zdnar=y|x|{=:[g{xx=a
 f

```

It takes a stream of characters as input and outputs a stream of characters.

# Answer
> 1 votes
# APL (Dyalog Unicode), 62 bytes

```
(g÷f¨()⍵(≢~⊃⍵⍺⍉⍨⍨}(←(←'')⊂f≢(g∘⌈¨}{?↑-⍵↑⋄)≢)))≢⊂{,⋄⍵⍵↑2f≢∘⊃?()

```

SHA-384 of my intended solution: `3209dba6ce8abd880eb0595cc0a334be7e686ca0aa441309b7c5c8d3118d877de2a48cbc6af9ef0299477e3170d1b94a`

This is probably easy enough, especially since most of the people in the APL chat helped me build this answer.

# Answer
> 0 votes
# Pyth, 14 bytes, Cracked

```
_Qm/dc2iF.jk.O

```

Pretty standard-issue Pyth implementation to test the waters. May be quite easy to crack, but I guess we'll see how it fares.

# Answer
> 0 votes
# Random Brainfuck, 273 bytes

```
]<.[<<]<[<<]<[<]<,.[<]-<<<]>>>>>]<+>-[<]<+>-[<<]>]>+<]<]>[>>]]>[>>]<]<+>-[[<<]>]>[>>]<-[[[>>]]>[>]<+>-[[<]<[[?>>]<+>-[[<]-<]>]<[>>]<<+>>+>-[[<<,[>]<.[<]>[>]<+>-[<]>[>]->>>]<<<<<]>+-[<<-[>]>+<-[>>]<]<+>-[[[<<]]<[<]>+<-[[><]<[[>]<+>-[>],]<+>-[<]<->>+]>[[<-[<?<<+>>>[,]>+<-[[>

```

Random brainfuck is the same as normal brainfuck, but it introduces the `?` character, which sets the current cell to a random value. Fun note; I had a version of this that only worked for inputs of less than 256 characters, for obvious reasons, but the code itself was longer than that. When I changed it to handle longer, it turned out to be one byte shorter than the original. ¯\\\_(ツ)\_/¯.

# Answer
> 0 votes
# Pushy, 25 bytes, Cracked

```
iUL1[N@O;?x?v:/2L=0LF;.':

```

Takes input as a `"quoted string"` on the command line.

---
Tags: string, random, permutations, cops-and-robbers
---


title: Implement a whitespace golfer

text:
# Question
Title: Implement a whitespace golfer
Some two-dimensional esolangs, such as Forked, and some non-esolangs, such as Python, can sometimes require spaces before lines of code. This isn't very golfy. Also, I'm lazy and writing a 2d lang that needs lots of spaces before code. Your task is to write a tool that makes these languages golfier.

Of course, this will not be perfect; it cannot be used, for instance, when a number is the first character on a line of source. However, it will generally be useful.

# Challenge

You will write a program or function that either...

* ...takes one argument, a filename or a string, or...
* ...reads from standard input.

Your program will act like `cat`, except:

* If the first character on any line is a number, your code will print *x* spaces, where *x* is that number.
* Otherwise, it will simply be printed.
* As will every other character in the input.

# Test cases

Input:

```
foo bar foo bar
1foo bar foo bar foo bar
2foo bar foo bar foo bar foo bar

```

Output:

```
foo bar foo bar
 foo bar foo bar foo bar
  foo bar foo bar foo bar foo bar

```

---

Input:

```
--------v
8|
8|
80
8,
7&

```

Output:

```
--------v
        |
        |
        0
        ,
       &

```

---

Input:

```
foo bar
bar foo
foo bar

```

Output:

```
foo bar
bar foo
foo bar

```

---

Input:

```
0123456789
1234567890
2345678901
3456789012
4567890123

```

Output:

```
123456789
 234567890
  345678901
   456789012
    567890123

```

# Rules

* Output must be exactly as input, except for lines where the first character is a number.
* Your program cannot append/prepend anything to the file, except one trailing newline if you desire.
* Your program may make no assumptions about the input. It may contain empty lines, no numbers, Unicode characters, whatever.
* If a number with more than one digit starts a line (e.g. `523abcdefg`), only the first digit (in the example, 5) should turn into spaces.

# Winner

Shortest code in each language wins. Have fun and good luck!

# Answer
# Retina, 9 bytes

```
m`^\d
$*

```

Try it online! Note: Trailing space on last line.
> 12 votes

# Answer
# Cubically, ~~69~~ 66 bytes

```
RBR3B~(+50<7?6{+54>7?6{-002+7~?6{(@5*1-1/1)6}}}(-6>7?6&@7+70-4~)6)

```

Try it online!

## Explanation:

First we do this initialization:

```
RBR3B

```

To set up this cube:

```
   533
   004
   000
411223455441
311222331440
311222331440
   555
   555
   200

```

The most important thing about this cube is that face `5` sums to 32, which is the value required to print spaces. Coincidentally, it also happens to be fairly short for all other computation. After that is done:

```
~( . . . )                                    Takes the first input, then loops indefinitely

  +50<7?6{+54>7?6{-002+7~?6{(@5*1-1/1)6}}}    Handle leading digit:
  +50<7?6{                               }    If input is greater than 47 ('0' is 48)
          +54>7?6{                      }     And input is less than 58 ('9' is 57)
                                              Then input is a digit
                  -002+7                      Set notepad equal to value of input digit
                        ~                     Take next input (only convenient place for it)
                         ?6{           }      If the notepad isn't 0
                            (        )6       While the notepad isn't 0:
                             @5                 Print a space
                               *1-1/1           Decrement the notepad by one
                                              Leading digit handled

     (-6>7?6&@7+70-4~)6                       Handle rest of line:
     (               )6                       While the notepad isn't 0:
      -6>7?6&                                   Exit if End of Input
             @7                                 Print the next character
               +70-4                            Set notepad to 0 if it was a newline
                    ~                           Take the next character

```
> 11 votes

# Answer
# Husk, ~~15~~ 13 bytes

-2 bytes thanks to @Zgarb

```
mΓo+?oR' i;±¶

```

Try it online!

Uses the same technique as @Jonathan Allan

### Explanation

```
             ¶  -- split input into a list of lines
m               -- apply the following function to each line
 Γ              --   deconstruct the string into a head and a tail
  o+            --   prepend to the tail of the string ...
    ?      ±    --     if the head is a digit (n)
     oR' i      --       the string of n spaces
                --     else
          ;     --       the head of the string
                -- implicitly print list of strings line-by-line

```
> 6 votes

# Answer
# JavaScript (ES8), ~~38~~ 37 bytes

```
a=>a.replace(/^\d/gm,a=>''.padEnd(a))

```

~~I don't think it can be improved much more.~~
*Saved 1 byte thanks to Shaggy* \- Use ES8 features.
> 5 votes

# Answer
# Ruby, ~~24~~ 21+1 = ~~25~~ 22 bytes

Uses the `-p` flag. -3 bytes from GB.

```
sub(/^\d/){"%#$&s"%p}

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~98~~ ~~74~~ ~~67~~ 65 bytes

*-24 bytes thanks to Jonathan Allan. -7 bytes thanks to Mr. Xcoder.*

```
for i in open('f'):print' '*int(i[0])+i[1:]if'/'<i[:1]<':'else i,

```

Try it online!

Takes input in the file named `f`.
> 4 votes

# Answer
# 05AB1E, 10 bytes

```
v0y¬dićú},

```

Try it online!
> 3 votes

# Answer
# Python 3, 95 bytes

```
lambda y:'\n'.join(re.sub('^\d',lambda x:' '*int(x.group()),z)for z in y.split('\n'))
import re

```

Try it online!

-4 bytes by stealing the regex idea from ThePirateBay
> 2 votes

# Answer
# Jelly, 19 bytes

```
V⁶ẋ
ḢÇ¹e?ØD;
ỴÇ€Yḟ0

```

A monadic link taking and returning lists of characters, or a full program printing the result.

**Try it online!**

### How?

```
V⁶ẋ - Link 1, make spaces: character (a digit)
V   - evaluate as Jelly code (get the number the character represents)
 ⁶  - a space character
  ẋ - repeat

ḢÇ¹e?ØD; - Link 2, process a line: list of characters
Ḣ        - head (get the first character and modify the line)
         -   Note: yields zero for empty lines
     ØD  - digit characters = "0123456789"
    ?    - if:
   e     - ...condition: exists in? (is the head a digit?)
 Ç       - ...then: call the last link as a monad (with the head as an argument)
  ¹      - ...else: identity (do nothing; yields the head)
       ; - concatenate with the beheaded line

ỴÇ€Yḟ0 - Main link: list of characters
Ỵ      - split at newlines
 Ç€    - call the last link (1) as a monad for €ach
   Y   - join with newlines
    ḟ0 - filter out any zeros (the results of empty lines)

```
> 2 votes

# Answer
# Perl 5, 13 + 1 (-p) = 14 bytes

```
s/^\d/$"x$&/e

```

Try it online!
> 2 votes

# Answer
# Python 2, ~~76 72~~ 68 bytes

*-4 bytes thanks to @ovs*!

@DeadPossum suggested switching to Python 2, which saved 4 bytes too.

Just thought it's nice to have a competitive full program in Python 2 that does not *explicitly* check if the first character is a digit. This reads the input from a file, `f`.

```
for i in open('f'):
 try:r=int(i[0])*" "+i[1:]
 except:r=i
 print r,

```

Try it online! (courtesy of @ovs)
> 2 votes

# Answer
# Haskell, 63 bytes

```
unlines.map g.lines
g(x:r)|x<';',x>'/'=(' '<$['1'..x])++r
g s=s

```

Try it online! The first line is an anonymous function which splits a given string into lines, applies the function `g` to each line and joins the resulting lines with newlines. In `g` it is checked whether the first character `x` of a line is a digit. If this is the case, then `['1'..x]` yields a string with length equal to the value of the digit `x` and `' '<$` converts the string into as many spaces. Finally the rest of the line `r` is appended. If `x` is not a digit we are in the second equation `g s=s` and return the line unmodified.
> 2 votes

# Answer
# Java 8, 105 99 97 93 bytes

*Saved few more bytes thanks to Nevay's suggestion,*

```
s->{int i=s.charAt(0);if(i>47&i<58)s=s.substring(1);while(i-->48)s=" "+s;System.out.print(s);}

```
> 2 votes

# Answer
# Japt (v2.0a0), ~~11~~ 10 bytes

Japt beating Jelly *and* 05AB1E? That doesn't seem right!

```
r/^\d/m_°ç

```

Test it

---

## Explanation

Implicit input of string `U`

```
r/^\d/m

```

Use Regex replace (`r`) all occurrences of a digit at the beginning of a line (`m` is the multiline flag - the `g` flag is enabled by default in Japt).

```
_

```

Pass each match through a function, where `Z` is the current element.

```
°

```

The postfix increment operator (`++`). This converts `Z` to an integer without increasing it for the following operation.

```
ç

```

Repeat a space character `Z` times.

Implicitly output the resulting string.
> 2 votes

# Answer
# , ~~138~~ 128 bytes

*-9 bytes thanks to CriminallyVulgar*

```
n=readLines();for(d in grep("^[0-9]",n))n[d]=gsub('^.?',paste0(rep(' ',eval(substr(n[d],1,1))),collapse=''),n[d]);cat(n,sep='
')

```

This is pretty bad, but it's a bit better now... R is, once again, terrible at strings.

Try it online!
> 2 votes

# Answer
# Jelly, 19 bytes

```
Ḣ⁶ẋ;µ¹µḣ1ẇØDµ?
ỴÇ€Y

```

Try it online!

-5 bytes total thanks to Jonathan Allan's comments and by looking at his post

# Explanation

```
Ḣ⁶ẋ;µ¹µḣ1ẇØDµ?  Main link
             ?  Ternary if
                if:
       ḣ1       the first 1 element(s) (`Head` would modify the list which is not wanted)
         ẇ      is a sublist of (essentially "is an element of")
          ØD    "0123456789"
                then:
  ẋ             repeat
 ⁶              ' '
Ḣ               n times where n is the first character of the line (head)
   ;            concatenate the "beheaded" string (wording choice credited to Jonathan Allan)
                else:
     ¹          Identity (do nothing)
    µ µ     µ   Link separators
ỴÇ€Y            Executed Link
Ỵ               Split by newlines
  €             For each element,
 Ç              call the last link on it
   Y            Join by newlines

```
> 1 votes

# Answer
# Pyth,  ~~16~~  15 bytes

```
jm.x+*;shdtdd.z

```

**Try it online!**

---

# Explanation

```
jm.x+*;shdtdd.z   - Full program that works by reading everything from STDIN.

             .z  - Read all STDIN and split it by linefeeds.
 m               - Map with a variable d.
  .x             - Try:
     *;shd           - To convert the first character to an Integer and multiply it by a space.
    +     td         - And add everything except for the first character
            d        - If the above fails, just add the whole String.
j                 - Join by newlines.

```

Let's take an example that should be easier to process. Say our input is:

```
foo bar foo bar
1foo bar foo bar foo bar
2foo bar foo bar foo bar foo bar

```

The program above will do the following:

* `.z` \- Reads it all and splits it by newlines, so we get `['foo bar foo bar', '1foo bar foo bar foo bar', '2foo bar foo bar foo bar foo bar']`.
* We get the first character of each: `['f', '1', '2']`.
* If it is convertible to an integer, we repeat a space that integer times and add the rest of the String. Else, we just place the whole String. Hence, we have `['foo bar foo bar', ' foo bar foo bar foo bar', ' foo bar foo bar foo bar foo bar']`.
* Finally, we join by newlines, so our result is:

```
foo bar foo bar
 foo bar foo bar foo bar
  foo bar foo bar foo bar foo bar

```
> 1 votes

# Answer
# , 9 bytes

```
ç^ä/x@"é

```

Try it online!

### Explanation

```
ç  /      ' On lines matching
 ^ä       ' (Start)(digit)
    x     ' Delete the first character
     @"   ' (Copy Register) number of times
       é  ' Insert a space

```
> 1 votes

# Answer
# Cubically, 82 bytes

```
R3D1R1D1+0(?6{?7@7~:1+2<7?6{+35>7?6{:7-120?6{(B3@5B1-0)6}:0}}}?6!@7~-60=7&6+4-3=7)

```

Note: This will not work on TIO. To test this, use the Lua interpreter with the experimental flag set to true (to enable conditionals). There's currently a bug with conditional blocks on the TIO interpreter. When using the TIO interpreter, you should replace `?6!` with `!6` and `&6` with `?6&`, which keeps the byte count the same.

```
R3D1R1D1          Set the cube so that face 0 has value 1 and the rest of the values are easy to calculate

+0                Set the notepad to 1 so that it enters the conditional below
(                 Do
  ?6{               If the notepad is 1 (last character was \n or start of input)
    ?7@7              Output the current character if it's \n
    ~                 Get the next character
    :1+2<7?6{         If the input is >= '0'
      +35>7?6{          If the input is <= '9'
        :7-120            Set the notepad to the input - '0'
        ?6{               If the notepad isn't 0
          (                 Do
            B3@5              Output a space
            B1-0              Subtract 1 from notepad
          )6                While notepad > 0
        }                 End if
        :0              Set notepad to 1
      }                 End if
    }                 End if
  }                 End if

  ?6!@7             If the notepad is 0 (did not attempt to print spaces), print current character

  ~                 Get next character
  -60=7&6           If there is no more input, exit the program
  +4-3=7            Check if current character is \n, setting notepad to result
)                 Repeat forever

```

This isn't as short as the other Cubically answer, but I thought I'd give this a try anyway :D
> 1 votes

# Answer
# \>\<\>, 60 bytes

```
!^i:0(?;::"/")$":"(*0$.
v"0"-
>:?!v1-" "o
;>:o>a=&10&?.i:0(?

```

Try it online!

### How It Works:

```
..i:0(?;... Gets input and ends if it is EOF
...
...
...

.^......::"/")$":"(*0$. If the inputted character is a digit go to the second line
...                     Else go to the fourth
...
...

....        If it was a digit
v"0"-       Subtract the character "0" from it to turn it into the corresponding integer
>:?!v1-" "o And print that many spaces before rejoining the fourth line
...

.^..               On the fourth line,
....               Copy and print the input (skip this if it was a digit)
....v              If the input is a newline, go back to the first line.
;>:o>a=&10&?.i:0(? Else get the input, ending on EOF

```
> 1 votes

# Answer
# Gema, 21 characters

```
\N<D1>=@repeat{$1;\ }

```

Sample run:

```
bash-4.4$ gema '\N<D1>=@repeat{$1;\ }' <<< 'foo bar foo bar
> 1foo bar foo bar foo bar
> 2foo bar foo bar foo bar foo bar
>
> --------v
> 8|
> 8|
> 80
> 8,
> 7&'
foo bar foo bar
 foo bar foo bar foo bar
  foo bar foo bar foo bar foo bar

--------v
        |
        |
        0
        ,
       &

```
> 0 votes

# Answer
# PHP, 83 chars

```
preg_replace_callback('/^\d/m',function($m){return str_repeat(' ',$m[0]);},$argv);

```
> 0 votes

---
Tags: code-golf, number, whitespace
---