title: Delannoy numbers

text:
# Question
Title: Delannoy numbers
Consider a grid from \\$(0,0)\\$ in the bottom-left corner to \\$(m,n)\\$ in the top-right corner. You begin at \\$(0,0)\\$, and can only move in one of these three ways:

* Directly north \\$(+0, +1)\\$,
* Directly east \\$(+1, +0)\\$, or
* Directly north-east \\$(+1, +1)\\$

How many different paths are there from your start at \\$(0,0)\\$ to \\$(m, n)\\$?

For example, if you're trying to reach \\$(3, 3)\\$, there are 63 different paths:

This value is given by \\$D(m,n)\\$, the Delannoy numbers. One formula for these numbers is

$$D(m,n) = \begin{cases} 1, & \text{if } m = 0 \text{ or } n = 0 \\ D(m-1, n) + D(m-1, n-1) + D(m, n-1), & \text{otherwise} \end{cases}$$

Others can be found on the Wikipedia page

---

You are to take two non-negative integers \\$n\\$ and \\$m\\$ and output \\$D(m,n)\\$. This is , so the shortest code in bytes wins

You may input and output in any convenient manner, and you may assume that no part of the calculation exceeds your language's integer maximum.

## Test cases

```
[m, n] -> D(m, n)
[5, 8] -> 13073
[5, 7] -> 7183
[3, 9] -> 1159
[8, 6] -> 40081
[8, 8] -> 265729
[1, 7] -> 15
[7, 0] -> 1
[11, 6] -> 227305
[0, 4] -> 1

```

And all possible outputs for \\$0 \le n, m \le 7\\$:

```
[m, n] -> D(m, n)
[0, 0] -> 1
[0, 1] -> 1
[0, 2] -> 1
[0, 3] -> 1
[0, 4] -> 1
[0, 5] -> 1
[0, 6] -> 1
[0, 7] -> 1
[0, 8] -> 1
[1, 0] -> 1
[1, 1] -> 3
[1, 2] -> 5
[1, 3] -> 7
[1, 4] -> 9
[1, 5] -> 11
[1, 6] -> 13
[1, 7] -> 15
[1, 8] -> 17
[2, 0] -> 1
[2, 1] -> 5
[2, 2] -> 13
[2, 3] -> 25
[2, 4] -> 41
[2, 5] -> 61
[2, 6] -> 85
[2, 7] -> 113
[2, 8] -> 145
[3, 0] -> 1
[3, 1] -> 7
[3, 2] -> 25
[3, 3] -> 63
[3, 4] -> 129
[3, 5] -> 231
[3, 6] -> 377
[3, 7] -> 575
[3, 8] -> 833
[4, 0] -> 1
[4, 1] -> 9
[4, 2] -> 41
[4, 3] -> 129
[4, 4] -> 321
[4, 5] -> 681
[4, 6] -> 1289
[4, 7] -> 2241
[4, 8] -> 3649
[5, 0] -> 1
[5, 1] -> 11
[5, 2] -> 61
[5, 3] -> 231
[5, 4] -> 681
[5, 5] -> 1683
[5, 6] -> 3653
[5, 7] -> 7183
[5, 8] -> 13073
[6, 0] -> 1
[6, 1] -> 13
[6, 2] -> 85
[6, 3] -> 377
[6, 4] -> 1289
[6, 5] -> 3653
[6, 6] -> 8989
[6, 7] -> 19825
[6, 8] -> 40081
[7, 0] -> 1
[7, 1] -> 15
[7, 2] -> 113
[7, 3] -> 575
[7, 4] -> 2241
[7, 5] -> 7183
[7, 6] -> 19825
[7, 7] -> 48639
[7, 8] -> 108545
[8, 0] -> 1
[8, 1] -> 17
[8, 2] -> 145
[8, 3] -> 833
[8, 4] -> 3649
[8, 5] -> 13073
[8, 6] -> 40081
[8, 7] -> 108545
[8, 8] -> 265729

```

# Answer
> 12 votes
# Jelly, 8 bytes

```
Żc@Ɱ,PṚḄ

```

Try it online!

Because I couldn't tolerate Jelly being tied with APL.

Again uses the formula

$$D(m,n) = \sum\_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k$$

but takes `m` and `n` as two separate arguments. This is essentially a port of my own Dyalog Extended answer.

```
Żc@Ɱ,PṚḄ    Dyadic link. Left arg: m, Right arg: n
Ż           Inclusive range 0..m (if m > n, the extra nCk terms will be zero)
    ,       [m, n]
 c@Ɱ        A table containing [[mC0 .. mCk], [nC0 .. nCk]]
     P      Vectorized product; [mC0 * nC0 .. mCk * nCk]
      ṚḄ    Reverse and unbinary; effectively sum mCk * nCk * 2^k for k = 0..m

```

Alternative 8 bytes, taking a single argument `[m, n]`:

```
c€ṂŻ$PṚḄ

```

Try it online!

# Answer
> 8 votes
# APL (Dyalog Unicode), 19 bytes

```
⊢/(1,2+/+\)⍣⎕⊢1,⎕⍴1

```

Try it online!

A full program that takes `n` and `m` on two separate lines. TIO link has an equivalent dfn for demonstration purposes.

### How it works

It goes through the table of Delannoy numbers row by row. Start with the zeroth row of `m + 1` ones, and calculate the next row n times:

```
Previous row: 1 a b c d e ...
Next row:     1 A B C D E ...

```

From the recurrence relation, we can observe the following:

```
A = 1 + 1 + a = 2 + a = (1) + (1 + a)
B = A + a + b = 2 + 2a + b = (1 + a) + (1 + a + b)
C = B + b + c = 2 + 2a + 2b + c = (1 + a + b) + (1 + a + b + c)
...

```

Therefore, we can compute the next row by taking the cumulative sum `+\`, then pairwise sum `2+/`, then prepending a 1. The desired value of `D(m,n)` is at the end of the row, so we apply `⊢/` at the end.

---

# APL (Dyalog Extended), 13 bytes

```
⊥⍤⌽(×/…⍤⌊!\,)

```

Try it online!

A straightforward implementation of the Wikipedia formula, also used by multiple other answers.

```
⊥⍤⌽(×/…⍤⌊!\,)  ⍝ Input: left arg = m, right arg = n
         !\    ⍝ Outer product by nCk function...
      …⍤⌊      ⍝ k = 0..min(n,m)
           ,   ⍝ [m, n]
    ×/         ⍝ Row-wise product; mCk * nCk for each k
⊥⍤⌽            ⍝ Reverse and evaluate in base 2; sum of mCk * nCk * 2^k

```

# Answer
> 7 votes
# Haskell, 37 bytes

```
m#n|m*n<1=1|i<-m-1,j<-n-1=i#n+m#j+i#j

```

Try it online!

Straightforward recursive implementation.

# Haskell, 41 bytes

```
0#n=1
m#n|j<-m-1=2*sum(map(j#)[0..n])-j#n

```

Try it online!

Based on a curious formula I found, but not quite short enough. $$ D(m,n)=2\sum\_{k=0}^{n-1}D(m-1,k)+D(m-1,n). $$

# Answer
> 5 votes
# , 24 21 19 bytes

```
2#.[:*/,!~/],i.@-@]

```

Try it online!

-3 thanks to the base 2 trick from Bubbler's APL answer.

-2 thanks to Bubbler.

Just this formula translated into J:

$$ D(m,n) = \sum ^ {\min(m, n)} _ {k=0} \binom m k \binom n k 2^k $$

# Answer
> 5 votes
# , 45 bytes

```
function(m,n,o=0:m,`$`=choose)m$o%*%(n$o*2^o)

```

Try it online!

Similar but independently-derived approach to pajonk's answer (version 2) - check it out \- but here maximizing 's vectorization & vector operators to avoid needing any loop.

# Answer
> 4 votes
# JavaScript (Node.js), 38 bytes

```
m=>g=n=>m*n?g(n--,m--)+g(n)+g(n,m++):1

```

Try it online!

Uses the specified formula, so will reach recursion limit on larger testcases.

-1 byte thanks to @dingledooper

-3 bytes thanks to @Arnauld

# Answer
> 4 votes
# Python 3, 49 bytes

```
D=lambda m,n:m*n<1or D(m-1,n)+D(m-1,n-1)+D(m,n-1)

```

Try it online!

Uses the formula specified in question, and looks like `m*n` works instead of `m and n`

-1 byte saved thanks to @CommandMaster forgot that we could use short-circuit evaluation

-4 again for @DingleDooper, genius one line short circuit

# Answer
> 4 votes
# Factor \+ `math.combinatorics math.unicode`, 65 bytes

```
[| m n | m n min [0,b] [| k | m k nCk n k nCk k 2^ * * ] map Σ ]

```

Try it online!

Inputs are re-used so often it's one of the odd times local variables are the terse way to go. Since recursion is generally verbose in Factor, I've gone with the formula

$$D(m,n) = \sum\_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} 2^k$$

# Answer
> 4 votes
# , 52 bytes

```
D=function(x)"if"(all(x),D(x-1:0)+D(x-1)+D(x-0:1),1)

```

Try it online!

Using the recursive formula and taking input as a tuple (thanks to @Dominic).

Taking input as two arguments:

### , 55 bytes

```
D=function(m,n)"if"(m*n,D(m-1,n)+D(m-1,n-1)+D(m,n-1),1)

```

Try it online!

Using the closed-form expression from Wikipedia results in 56 bytes with a loop, but take a look at @Dominic's 45 byte approach!

### , ~~68~~ ~~61~~ ~~58~~ 56 bytes

```
function(m,n,`$`=choose){for(k in 0:m)F=F+m$k*n$k*2^k;F}

```

Try it online!

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

```
Total//@DiamondMatrix@Table@##&

```

Try it online!

Returns `{1}` instead of `1` when the second argument is 0. To fix this, ~~+4~~ +3 bytes: Try it online!

From Wikipedia:

> The Delannoy number \\$D(m,n)\\$ also counts... the number of cells in an *m*-dimensional von Neumann neighborhood of radius *n*...

Generates a matrix representing a radius-`m` dimension-`n` von Neumann neighborhood, and counts the number of cells.

---

Some other approaches:

**Multinomial formula, ~~38~~ 36 bytes**

```
Multinomial[k,#-k,#2-k]~Sum~{k,0,#}&

```

Try it online!

**Direct recursion, 46 bytes**

```
f=If[1##>0,f[#-1,#2]+f[#-1,#2-1]+f[#,#2-1],1]&

```

Try it online!

**Generating function, 46 bytes**

```
SeriesCoefficient[1/(2-x y),{x,1,#},{y,1,#2}]&

```

Try it online!

# Answer
> 3 votes
# 05AB1E,  ~~10~~ 8 bytes

```
WÝ€cPR2β

```

Try it online!

-2 thanks to the base 2 trick from Bubbler's APL answer.

Uses the direct formula from wikipedia.

```
W     push the minimum of m,n
Ý     push the range [0,min(n,m)]
€     and map each number to
 c    the input choose that number, vectorizes
P     product
R     reverse
2β    convert from base 2

```

# Answer
> 3 votes
# PowerShell Core, ~~79~~ 67 bytes

```
filter f($a){if($a*$_){(--$a|f $_)+(--$_|f $a)+($a+1|f $_)}else{1}}

```

Try it online!

* Saved 1 byte by using a filter
* Saved 3 bytes replacing the `-and` by a `*`
* Saved a whopping 12 bytes thanks to Zaelin Goodman

# Answer
> 3 votes
# Charcoal, 22 bytes

```
≔Ｅ⊕Ｎ¹θＦＮＵＭθ⁺κ⊗↨…θλ¹Ｉ⊟θ

```

Try it online! Link is to verbose version of code. Explanation: Uses @Delfad0r's curious formula.

```
≔Ｅ⊕Ｎ¹θ

```

Input `n` and create an array of `1`s representing `D(0,k)` for `0<=k<=n`.

```
ＦＮ

```

Repeat `m` times.

```
ＵＭθ⁺κ⊗↨…θλ¹

```

Add twice the cumulative sum to each element. (I have to use base `1` conversion because `Sum` returns `None` for an empty list. It was still shorter than adding the inclusive and exclusive cumulative sums.)

```
Ｉ⊟θ

```

Output `D(m,n)`.

# Answer
> 3 votes
# Julia 1.0, ~~47~~ 30 bytes

```
m%n=m*n<1||~-m%n+~-m%~-n+m%~-n

```

Try it online!

Boring port of the formula.

* -12 bytes thanks to @Sisyphus!
* -5 bytes thanks to @MarcMush!

# Answer
> 3 votes
# K (ngn/k), 18 bytes

```
{0/x(+':+\)/1,y#1}

```

Try it online!

Port of my APL answer that does not use the binomial coefficient built-in. See the linked answer for the explanation of how it computes Delannoy numbers using just cumulative sum `+\` and windowed sums `+':`.

```
{0/x(+':+\)/1,y#1}  x, y: two input integers
            1,y#1   (y+1) copies of 1; the 0th row of the grid of Delannoy numbers
   x(     )/        do x times:
     +':+\          calculate the next row
 0/                 base 0 = extract the last item

```

# Answer
> 2 votes
# Java, 62 bytes

```
int f(int m,int n){return n*m<1?1:f(m--,n-1)+f(m,n)+f(m,n-1);}

```

Try it online!

# Answer
> 2 votes
# Pari/GP, 45 bytes

```
d(m,n)=if(m*n,d(m-1,n)+d(m-1,n-1)+d(m,n-1),1)

```

Try it online!

# Answer
> 2 votes
# Ruby, 44 bytes

```
f=->m,n{m*n<1?1:f[m-1,n]+f[m-1,n-=1]+f[m,n]}

```

Try it online!

Using the formula in the question

# Answer
> 2 votes
# Desmos, 38 bytes

```
D(m,n)=\sum_{k=0}^mnCr(m,k)nCr(n,k)2^k

```

Try It On Desmos!

Try It On Desmos! (Prettified)

Implements the formula$$D(m,n)=\sum\_{k=0}^{\min(m,n)}\binom mk\binom nk2^k$$with the observation that \\$\min(m,n)\\$ can be replaced with \\$m\\$(or \\$n\\$).

# Answer
> 2 votes
# , 17 bytes

```
]{(2&+/\@[&0>:$#)

```

Try it online!

Uses the same algorithm as my 19-byte APL solution. I randomly came across the problem again and realized J has multiple tricks to shorten the code, so it is actually shorter than APL. Also beats Jonah's J solution which uses the direct formula.

Takes `m` and `n` as left and right argument respectively.

`2&+/` part comes from here.

```
]{(2&+/\@[&0>:$#)   NB. left arg = m; right arg = n
   xxxxxxxxxyyyy    NB. This part is a hook, so it evaluates as m x (y n)
            >:$#    NB. n+1 copies of 1
   xxxxx@[&0        NB. A trick idiom for "repeat x m times to (y n)"
   2&+/\   NB. Evaluate next row of Delannoy matrix:
       \   NB. For each prefix,
   2&+/    NB. Convert [a, b, ..., m, n] to 2a+2b+...+2m+n
]{         NB. Extract the last element, which is at index n (0-based)

```

# Answer
> 1 votes
# Jelly, 13 bytes

```
ṂŻc@ⱮµPæ«J$SH

```

Try it online!

Using the direct formula from Wikipedia.

```
Ṃ              Minimum
 Ż             [0, 1, ..., min(m, n)]
    Ɱ          For each in the input
  c@           swapped args: input choose k
     P         product (vectorizes)
      æ«J$     bitshift by [1, 2, 3, ...]
          S    sum
           H   halve (since J starts at 1)

```

# Jelly, 14 bytes

```
_45Bs2¤ß€Sµ1Ȧ?

```

Try it online!

Could use some work, probably.

```
             ? If
            Ȧ  all (m != 0, n != 0)
          S    take the sum of
       ß       this link
        €      applied to each of
_              (m, n) -
 45Bs2¤        [1, 0], [1, 1], [0, 1]
 45B           45 as binary: [1, 0, 1, 1, 0, 1]
    s2         sliced into size 2 chunks
           1   Otherwise, 1

```

# Answer
> 1 votes
# Red, 73 bytes

```
f: func[m n][either(m * n)= 0[1][(f m - 1 n)+(f m - 1 n - 1)+ f m n - 1]]

```

Try it online!

Uses the formula from the problem description.

# Answer
> 1 votes
# MMIX, 64 bytes (16 instrs)

Recursive, so takes forever.

```
00000000: dc020001 52020003 e3020001 f8030000  ṇ£¡¢R£¡¤ẉ£¡¢ẏ¤¡¡
00000010: fe020004 c1040000 27050101 f303fff9  “£¡¥Ḋ¥¡¡'¦¢¢ṙ¤”ż
00000020: 27060001 f304fff7 c1050100 22030304  '©¡¢ṙ¥”ẋḊ¦¢¡"¤¤¥
00000030: f304fff4 22030304 f6040002 f8040000  ṙ¥”ṡ"¤¤¥ẇ¥¡£ẏ¥¡¡

```

Disassembled:

```
delannoy    MOR   $2,$0,$1
            PBNZ  $2,0F
            SETL  $2,1
            POP   3,0           // if(!(m && n)) return(1,m,n)
0H          GET   $2,rJ
            SET   $4,$0
            SUBU  $5,$1,1
            PUSHJ $3,delannoy   // $3,$4,$5 = delannoy(m,n-1) = f(m,n-1),m,n-1
            SUBU  $6,$0,1       // $6 = m - 1
            PUSHJ $4,delannoy   // $4,$5,$6 = delannoy(n-1,m-1)
            SET   $5,$1
            ADDU  $3,$3,$4      // $3 += $4
            PUSHJ $4,delannoy   // $4,$5,$6 = delannoy(n-1,m)
            ADDU  $3,$3,$4
            PUT   rJ,$2
            POP   4,0           // return(f(m,n), m, n)

```

# Answer
> 1 votes
# C (gcc), ~~45~~ 43 bytes

```
D(m,n){m=m*n?D(m-1,n)+D(m-1,--n)+D(m,n):1;}

```

Try it online!

*Saved 2 bytes thanks to mousetail!!!*

# Answer
> 1 votes
# Arturo, ~~50~~ ~~48~~ 47 bytes

```
f:$[m,n][(0=m*n)?->1[+ +f m-1n-1f m n-1f m-1n]]

```

Try it

# Answer
> 1 votes
# Pyt, 19 bytes

```
Đ↓0⇹ŘĐ1⇹«04Ș⇹ɐćÁ*·+

```

Try it online!

Direct implementation of the formula on Wikipedia

```
Đ↓                     implicit input; Đuplicate on stack; get minimum of inputs (k)
  0⇹Ř                  create Řange [0,1,...,k]
     Đ1⇹«              2^k
         04Ș⇹          stack manipulation to have the range on top, then the input
             ɐć        for ɐll pairs of values in the two arrays, nćr
               Á*      multiply the two nCr lists element-wise
                 ·     dot-product with the powers of 2
                  +    remove that pesky 0; implicit print

```

---
Tags: code-golf, math, sequence, grid, path-finding
---


title: Score a curling end

text:
# Question
Title: Score a curling end
Curling is a sport where two teams aim to place stones as close to the centre of a target as possible. The winner of a curling end is the team whose stone is closest to the centre – they score as many points as the number of their stones closer to the centre than any of their opponents.

## Task

Given two lists of pairs of integers representing the Cartesian coordinates of both teams' stones, with the origin as target centre, output a positive integer if one team wins and a negative integer if the other wins; the sign must be consistent with input order. The magnitude of this integer is the number of points scored.

Ties are broken as follows:

* If there are no stones at all or there is a tie between teams for the closest stone, no points are scored and 0 should be returned.
* If there is a winning team, any of their stones at *exactly the same distance* as their opponent's closest stone do not count for points.

Input formatting is flexible – you may use a complex number to represent a stone's coordinates or tag the coordinates with their corresponding teams, for example. The distance of (x,y) from the origin is \\$\sqrt{x^2+y^2}\\$ – scaling is equal in both directions.

This is ; fewest bytes wins.

## Test cases

These assume the team whose stones' coordinates are listed **first** is associated with a **positive** output.

```
[],[] -> 0
[(1,0)],[] -> 1
[],[(0,1)] -> -1
[(2,0),(2,1),(2,2),(2,-1),(2,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2)],[(0,1),(0,-1)] -> -2
[(4,3),(3,3),(-3,-3),(-1,0)],[(4,1)] -> 1
[(-3,2)],[(2,2),(0,-8),(-1,-1),(3,6)] -> -2
[(0,0),(1,0),(0,1)],[(1,1),(1,-1),(-1,1),(-1,-1)] -> 3
[(-7,1)],[(5,5)] -> 0
[(1,0),(2,0)],[(-2,0)] -> 1
[(-3,-4),(0,5)],[(-1,2),(4,3),(4,-3),(-3,0)] -> -2

```

---

Obviously this question was inspired by the curling events at the 2022 Winter Olympics.

# Answer
> 6 votes
# APL(Dyalog Unicode), 14 bytes SBCS

```
(¯1⊥1⊥¨⌽<⌊/¨)|

```

Try it on APLgolf!

A tacit function which takes the coordinates as a pair of vectors of complex numbers.

`|` Absolute value on each of the complex numbers in the input.
`(...)` Apply the inner function on the absolute values.
`⌊/¨` Get the minimum of each of the vectors.
`⌽<` For each value in a vector, check if it is less than the minimum of the other vector.
`1⊥¨` Sum each boolean vector.
`¯1⊥` Get the difference between the two results.

The two uses of *Decode*  are usually the reductions `+/¨` and `-⍨/`, but they don't work so well in a tacit function as they have to be called monadically.

# Answer
> 3 votes
# Python3, 79 bytes:

```
f=lambda x,y,w=1:sum(y==[]or abs(j)<min(map(abs,y))for j in x)-(w and f(y,x,0))

```

Try it online!

# Answer
> 2 votes
# Charcoal, 26 bytes

```
ＦθＵＭιΣＸκ²Ｉ↨ＥθＬΦ§θ¬κ⬤ι‹λν±¹

```

Try it online! Link is to verbose version of code. Takes input as a pair of lists of tuples. Explanation:

```
Ｆθ

```

Loop over each team.

```
ＵＭιΣＸκ²

```

Replace each stone with its squared distance from the origin.

```
Ｉ↨ＥθＬΦ§θ¬κ⬤ι‹λν±¹

```

For each team, count how many stones are nearer than all of the other team's stones, then output the difference between the two values. (This particular formulation has been chosen because it works with empty lists.)

# Answer
> 2 votes
# JavaScript (Node.js), 144 bytes

```
(n,k,Z=Math.min,N=(F=L=>L.map(([x,y])=>x*x+y*y))(n),K=F(k),Q=Z(...N),R=Z(...K),G=(c,d)=>c.filter(e=>d.every(E=>e<E)).length)=>Q<R?G(N,K):-G(K,N)

```

Try it online!

I hope it can be golfed further.

# Answer
> 1 votes
# Burlesque, 49 bytes

```
m{m{)S[++}}Jqnuay{)L[}{J)<]<-{bxq.<_+fl}Z]}IE^p.-

```

Try it online!

There are issues with finding the minimum of an empty vector, so there needs to be a workaround.

```
m{      # Map
 m{     # Map
   )S[  # Square each
  ++    # Sum
 }      # -- Calc Mag sq
}       # -- Of each input
J       # Duplicate
qnuay   # If any empty
{       #
 )L[    # Map to length
}       #
{       # Else
 J      # Duplicate
 )<]    # Map to minima
 <-     # Reverse
 {      #
  bx    # Box Number
  q.<_+ # Append <
  fl    # Count
 }      # -- Count those less than minimum of other side
 Z]     # Zip with apply
}IE     # If Else (stack based)
^p      # Push to stack
.-      # Subtraction

```

# Answer
> 1 votes
# Vyxal , 23 bytes

I'd like to make code that works with strictly nested array-input, include empty arrays: `[ [], [] ], [ [], [[0, 1]] ]` etc.
I’d appreciate it if someone would do the refactoring, but with that condition in mind.

```
:vL:A[_vƛ∆/;:vgṘ¨Z<∑]÷-

```

Try it Online!

```
       # ḋ flag (Print rationals in their decimal form) useful for debugging
:vL:A  # Check if all arrays are not empty (and get lenghts)
[      # If so
_vƛ∆/; # Remove lengths and calculate all norms in both arrays
:vg    # Find minima
Ṙ      # Reverse
¨Z‹∑   # Zip, check for "less than" and sum boolean
]÷-    Find difference (in both cases: lengths or sums)

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 85 bytes

```
c=Count[#1,u_/;u<Min@#2]&;
f=c@@#-c@@Reverse@#&@Map[Norm,#/.{{}->{\[Infinity]}},{2}]&

```

Try it online!

This works with strictly nested array-input, include empty arrays: `[ [], [] ], [ [], [[0, 1]] ]` etc.
Mathematica has built-in `Infinity`, so I use it to replace empty results (as if stones cast far away).
Code is clumsy so I hope someone post more well-built answer

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


title: Base64 fixed point

text:
# Question
Title: Base64 fixed point
It can be proven that there's exactly one string of infinite length that remain same after `base64` encoding `Vm0wd2QyUXlVWGxWV0d4V1YwZ...`

Given a position, output the character on that position.

Your program would be run on AMD Ryzen 5 5500U@4GHz given 4GB memory and 1 minute (may decrease if RAM turns out to be hard limit). You can take input in any base, but not one number in two different bases. No multithread allowed. Largest handled range wins.

Test cases: (Position \\$3^k+b\\$, 0-base. Notice that \\$3^0=1\\$ so \\$b\\$ starts at -1)

```
  \b -          111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999
  k\ 10123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
   0 Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWV
   1 0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJ
   2 UXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UV
   3 RWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw
   4 TVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw1VTJ0V1ZXSkhhRzlVVmxaM1ZsWmFkR05GU214U2JHdzFWVEowVjFaW
   5 ZOcmFHaFNlbXhXVm0xNFlVMHhXbk5YYlVaclVqQTFSMVV5TVRSVk1rcElaSHBHVjFaRmIzZFdha1poVjBaT2NtRkhhRk5sYlhoWFZ
   6 MUdVMkpWYkRaWGExcHJZVWRGZUdOSE9WZGhhMHBvVmtSS1QyUkdTbkpoUjJoVFlYcFdlbGRYZUc5aU1XUkhWMjVTVGxOSGFGQlZiV
   7 djSE5WYlRGVFRWWlZlV042UmxoU2EzQmFWVmMxYjFZeFdYcGhTRXBWWVRKU1NGVnFSbUZYVm5CSVlVWk9WMVpHV2xkV2JHTjRUa2R
   8 YUZwaE1YQXpWRlphY21ReFpIUmtSMmhPWVROQ1NWZFhkRk5VTVZsM1RWaEdWMkV6YUdGWlZFWjNWRVp3Umxkc1pHdFdNSEJJV1ZWa
   9 V4V1JsWmhXVmROZUdFemNHaFNiVkpQVm14a00wMUdaRlZSYkdScVRWWnNOVlV5ZEd0aGJFNUdVMnhvVlZaV2NHaFdSVnBoWXpGa2R
  10 aDNWbGQ0YjFFd05WZFhiazVXWVRBMWIxUldXbGRPUm1SeVZtMTBhRlpyTlVkWk1GcHpWMjFLV1ZSWWFGZFdWbkJZV2tWVmVGWXhVb
  11 lhelF3Vm0xNFlWbFhUWGhqUldSVllYcFdUMVpzWXpWT1ZscHhVbTFHVjAxWGVGaFdSelZUVmpKS1NHRkdVbHBXUlZvelZsWmFZV1J
  12 Y21GSGNHeGlSbkIyVm0weE1HTXdOWE5pUmxwWVlsUnNXVlZ0ZUhkbGJGbDVUbFYwVjJKVldubFdNalZMVm1zeFIyTkdRbHBsYTFwe
  13 pGWVZXNXdXR0V4V25wV1Z6RkxVMGRHUjJKR1pHbFhSMmQ2VjFSS05GbFhUbGRUYmxKVFlsaFNWRlJXVm5kVFZscHlXa2h3VGxac2J
  14 TldWa3AwVW14a1RsWnJjRmxXYWtsNFRVWlZkMDFXV2s5V1JWcFlWV3BPYjJOc2JGZFhiSEJzWWxWYVNGbHJXbXRoUjBWM1kwWnNWM
  15 9WbXRzTkZrd1ZtRlpWa3AwVld4c1ZtRnJjSFphUjNoaFZsWkdkR1JHV2s1V01VcEpWMWQwYjFReFdYbFRibEpXWWtaYVYxbHNhRzl
  16 VjBaV2RFMVVVbXhXYlhoWFZtMXpOVlpWTVhKalJXaGFUVWRvZGxadGMzaFhSMFpKVjJ4a1YxSlZXVEJYVkVvMFlUSlNXRk5yWkZka
  17 tWYU1sZHNXbUZaVjA1WFVtNVNhMUpzY0U5V2JGSlhVMVphVlZOVVJsWk5hMVkwVlRKNFYxWXlTbFZpUmxwWFlsUkdkbFZyV2xabFY
  18 RkdUbWxTYTNCVlZrWmFWMlF4V1hoWGJrcFlZbFZhV0ZsWWNFZFdNVkpYVm0xMFdGSXdjSHBWTWpWTFZtMUdjazVXVWxwaGExcDZXV
  19 NXbFpYYUROV2FrcExVMFpXY2xwSFJsZGlTRUpaVjFod1MxSXhTWGxVYTJocFVtMW9WRlJYTVc5VU1WcHhVbXhPVTAxWGVGbFdWbWh
  20 VmxaclRrWlZlVk5zYkdoU2VteFlXV3hvYjJOc1dsVlNhemxUVFZkU01WWkhlRzloVmxwWFkwaG9WMUp0VWpaVVZscExZekZhYzJGS
  21 FFeFduUlRiR3hvVW0xb1dGVnVjRWRVUmxaMFRWVTVVMDFyY0VoWGEyUnZWRzFHTmxKVVFsZGlXR2hVVlhwR1NtVldVbGxoUmxacFl
  22 Sm9XVlpyVmt0aFJteHhVbTEwYTFKck5YbFpWV1J2VlRKS1JtTkdiRmhXYlZGM1YxWmFZVkl4WkZsYVIwWlRZWHBXVlZaR1pIcE5Wa
  23 JiRmROVm5CWVYxWmtSbVZHV2xsYVJUVlVVakpvVmxkV1pEQmtNV1JIWWtoT1ZtRXdOVkJWYlhoYVRXeFZlV042Vm1oaGVrWllWVEp
  24 V1RCV2JYaGhZVEExU0ZWWWFGaFhSMmhWV1cxek1XTldWblJOVnpsWVZteHdNRlJXV2s5V1ZrcHpWMjVvVm1KVVJYZFdNRnBoWkZaR
  25 xOV1dFSk1WbXBLTUZZeFduSk5WbVJZVjBkNFZWbHRkSGRXVm14VlZHdE9XRkpzU2xoWGExcExZVEF4V0ZWc2FGaGhNVnBvV1d0YVN
  26 WlRZekpHU0dKR1pGZGlSM1F6Vm0weGQxTXlVWGhWV0doWVYwZFNUMVpzWkZOalZsWjBUVmM1V2xadVFsbGFSV1JIWVcxS1NWRnJhR
  27 xSemxZWWtac05sWlhjRTlXVjBwWllVUk9WMkpZYUhKWk1qRlBVMGRXUjFwSGJGTlhSVVY0Vm0weGQxTnRWa1pPVldSWFYwZDRWVmx
  28 VkZkSVFsaFpWRVpMVkVaVmVVMVdaRk5OYXpWSFZqSXhSMVV3TVhWaFJsWllWak5TYUZwRVJtRldNWEJIWVVkNFUyVnRlRmhXUm1SN
  29 JSdlZHMUtSbU5IUmxkTlYxRjNXVlJCTVZOR1RsbGhSbVJwWWtWd1VGWnROWGRqTWs1SFZXeGtXR0V6VWxsVmJURTBWakZhZEdONlZ
  30 SmpSWGhXWVd0YWNsa3hXa2RqTVZwMFlrWk9UbFpXYkRaV2FrWmhXVlpzVjFSdVVsWlhSM2hXV1ZSR2QySXhWblJsU0dSVlRWZDRNR
  31 pWMnhvYVZkR1NsbFdiVEV3V1ZkV2MxcElTbUZTZW14V1dXeFdWMDVHYTNkV2JrNVhUVlp3UjFZeU5XRlpWa3BHVjIxb1lWSldjRkJ
  32 WlVab1YwMVhhSHBaVkVaTFpFWldjMXBHVmxkaVJuQlpWa2QwWVZkdFZsaFdhMmhUWWtaYWNGVnROVU5PYkdSVlVXMDVVMDFXY0RCV
  33 Fad1YySklRWGRXUmxwVFVUSkdSazFWVmxOaE1taGhXVlJHZDJOc1duUmxSM1JVVWpCYVNGbHJXbXRVYkVsNFVsaGtXRll6UWtoV2F
  34 WlhhRVJXUmxwaFpFVXhWVkZzY0ZkaVdHaFpWbXBHYjJFeFVuTlhiR2hXWWtkb1dGUlZaRk5XUmxwRlVteHdhMDFXY0RGWGExcGhWV
  35 9TRk5yWkZWaVIyaFVWbXhvUTFSV1duUk5XR1JUVFZaV05GVnNhRzlYUm1SSVpVWldWMDFIVVRCV2JGcHpWbFpPYzFSc1pGZGlSM2Q
  36 Vm14V1lVVjBXbFpyY0ZoWk1GWTBWMjFXY21ORmFGWmhhMW96VlRCa1MxSXhWbk5VYkdSWFRURkdObFp0TUhkbFJUVkhZa1pvVTFkS
  37 xkV1ZsWk9WbGw0VjJ0b2JGSnVRbGhXYWs1RFVrWndSVkp0ZEZkTmF6VklWako0YjJGWFJqWldiR3hZVmpOb1dGcEVSazlTTVZwWll
  38 ZDBVMVF4V2xkWGJrNXFVakpvWVZacVRtOVZSbFY0VjJ0a2FrMXJXa2hXYlhocllrZEtSMkl6YkZkaVZFVjNWMVphYzFkR1ZuSlhhe
  39 hSbGRUYmxKclRUTkNXRmxYZEhOT1JsSldWMnh3YTAxRVJsaFpWVnBoWVZkS2NsTnRhRmRTYkZweVZsZHplRkl4WkhWU2JGSm9UVEZ
  40 VG05aFJsWnhVbTVrVTFac1ducFdWM014VmpBeFZtSjZTbGRoYTI5M1YxWmtTbVZXU2xsaFJsSllVakZLV2xkWGVGZFpWbVJIWWtoT
  41 ZsaFIyaFVVakZLVmxaR1dtRlNNRFZIVmxoc2JGSXpVbGRVVjNSM1pXeFZlV1ZHVGxoaVZWWTFWbGQ0VTFZd01VZGpTSEJoVWxkU1Z
  42 cHpWbXBTVmsxWGFIWldiR1JMWTJzMVdHRkdXazVTYkc5NlYxWldZVll5VG5OYVNFcHJVbTFTVDFadGRIZFhWbHB4VTFSR2FFMVdjR
  43 tSMVpKV2tkd2FWSnNiM2RYYkZaclVqSkdjMU51VGxoaGEwcFdXV3RhWVZSR2JGVlJXR2hYVFdzMVNsa3dXbTloUlRGV1kwWldWMkp
  44 TUZaSGRHRlpWa3B6WTBVNVdsWXpVbWhVVjNoaFpFVXhTV0ZHVWs1V1ZGWkpWbTB3TVZZeFpFaFRhMnhTWVhwc1lWbHNVa2RrYkZKM
  45 FKNVZteFNWMkZHV25KalJFWldWak5DVkZacVNrdFdWa3BWVVd4d1YxSldjRmhYYTFKQ1pVWk9XRk5yYUdoU2F6VnpXV3hvYjFsV1d
  46 ZE5WbkF3VlRKNGMxWnRSbkpPVmxwWFlrWndNMVJVUm1Ga1IxWkpXa1pTVjJKRmNEWldha3A2VFZkR1JrMUlaRlJXUlZwWVdXdGFTM
  47 RWMFphY2xacmRHaFNiWFExVkZaYVMySkdTblJWYm5CWFlsaG9jbGxXV2twbFYwWkpXa1prYVZkSGFHOVdha3A2WlVaSmVHTkZaRmR
  48 VmtWVmQxWnNVa2RYYlZaSFZXNU9ZVkp0YUhCWldIQlhZakZhV0dSSFJsUk5hMncwVmxkNGExZEhTa2hWYkVKV1lsaG9lbFJzV2xOa
  49 VaYWNscEhSbE5XYmtKU1ZtMHdlRlV4WkZkaVJteHFVbTFTV1ZWdE1UUk5SbkJHVm1wQ1YxSXdjRWhaTUZKRFYyc3hSMWRZWkZkU1J
  50 UldXazlYUmtwMFpVaHdWMkpVVm5KWmEyUkxVMGRTUlZSc1pFNWhhMFY0Vm1wQ2ExTXhTWGxUYTFaWVlrZFNXRlJVUWt0VlZscDBZM
  51 9UMkZHU25WUmJrSldZV3R3ZGxSWGVHRmpiRnAwVW14b2FWWnJXVEJXTW5SdlV6SkdjMU5ZY0doU2JFcGhWakJvUTFkR1VuUmxSM1J
  52 Um14VlRWWktVRll3V21Gak1VNXlZVVpvVjJKSVFtOVhWRXA2WlVaWmVHTkZhRk5pUlRWUFZGVldkMVpzV1hoWGJFNVNUV3hHTlZWd
  53 xkRlNrbFdiR040WXpKR1YxTnVWbEppUmxwWVZGWmFkMVpHVmpaVGEzQnNVbTVDU0ZkcldtOWhWMFY2VVd4c1dGWnNTbEJXVkVwS1p
  54 SkdTRTlXWkdsV1dFSlhWbTB3TVZNeFdYaFhhMXBxVWxkb1ZsbHNhRzloUm13MlUydDBWRkpyY0hwWGExcHJZVmRGZDJKNlJsZGhhM
  55 llR3RXUjBWNVpVWm9XbFl6VWpKVVZWcHpZMVpPY21SR1RrNVdWRlkwVm1wSmVHTXhWWGxXYmxKc1VtMVNXRmxzVWtaTlJtUlhXa1p
  56 U2tkVGJuQlhWbnBHZWxaVVFYaFdiVW8yVTJ4a2FWWkZTWHBYYkZaV1pVWkplRmRzYkdGU1ZGWllXV3hrYjFkR1pGaE5SRVpTVFZkU
  57 1GWFIwNDJWbXhrVG1FelFrbFhWRUp2WXpGc1YxTnJXbGhpVjJoaFZGWmFkMVZHYTNoWGEyUnJVakJ3UjFSc1dtdGhSVEZZWkVST1Y
  58 WnJUV3R3U1ZWc2FHOWhiRXAwWlVac1YwMUhhRVJWTUZwM1VsWktjbU5IZUZkaE0wSTFWakowWVZZeVJsZFhXSEJvVW01Q1dGWnFUa
  59 dNR1JUV1Zad1dHUkZXbXhTYkhCNFZXMHhNR0Z0U2xaWGEyeGhVbFp3VkZaVVJtRlNNV1J4VTJ4a1RsWXhSak5XYlhCTFZXMVJkMDF
  60 ZUZkV1JuTmFSbWhYVFRGS2IxWlljRXRVTVVsNFYyNVdWbUY2YkZoV2JGSlhWbXhrV0dSSGRGWk5iRnA2VmpJMVUxUnNXa1pUYkZwY
  61 hSVFZteHdNRlZ0ZUd0V01rcHlVMnhhVjJKWVFreFVhMXB6VmpGT2RWTnJPVmRpU0VKWVYxZDBZVmxYVGtkWFdHUmhVbnBzY0ZSV1p
  62 ZFVWM1IzVjBaVmVXTkdUbGROVm5CSFdXNXdRMVl5Um5KWGJVWmhWbFp3Y2xwR1dtRmpNVTUwWVVkc1ZGSlZjR2hXYlRCNFRVWlplR
  63 pWbXBHZDFZeGNFZGFSbEpUVmtkNFdsZFdWbUZoTWtaWFZHdGFWR0pJUWxoVVZscExVa1prVjFkc2NHeFNia0pIVjJ0YWIyRkhTa2x
  64 Vm10a05HVldXa2RYYlhSV1RXeGFXRlpYZUd0V01rcFZZa2M1Vm1KWVRYaFZNbmhYVjBkV1NFOVdaRmRpUnpoNVZtMHhORkV4V2xoU
  65 dwR2EyTXlSa2RqUm1ST1RXMW9kbFp0Y0VOWlZsVjRXa1ZhVDFadFVsWlpiR1J2Vmtac2NtRkZUbE5OVm5CV1ZUSndRMkZGTVZkalJ
  66 TkdiSEpYYm1SWFRWWndNVlZYZUVkWFJscHpWMjVLVjJGcmNFOWFWVnAzVTFaT2RHUkdUbWxXYTNBelZtMXdRMkV5U1hsV2JHUllZV
  67 NTMVpXV205aE1WbDVVMnRvVlZkSGFGbFdiWGgzWTJ4cmVXTXphRmhXYkhBd1dWVmFVMVpHU2xaalJuQlhZVEZ3V0ZsVVJsWmxSbkJ
  68 VkZWM1YydFdWazFXVlhoVGJHUnFVbTVDV0ZsWGRIWmtNV3hWVW10d2JGSnNjRnBaYTFwVFlWWkplV0ZJV2xkV1JVcHlWbFJHYTFZe
  69 ZSc1pFNWhNMEpYVm0weE1GVXhXWGxTYmtwWVlsVmFhRlp0ZUZabFJsbDNXa1pPVkZJd1draFhhMlJ2VkdzeFJtRXpiRmRoYTFwVVZ
  70 eG9WbUp1UWtkVVZWcHJWakZ3Ums5V1pFNVdhM0EyVm0weE5GUXlSbGRUYmxaU1lrVktXVlp0ZUV0VlJsWlZVbXM1VjAxWFVucFdiW
  71 dOREJXUmxaaFUyMVJkMDFWYkdoU2JXaHdXVlJPUTFkc1pGaGxSbVJhVm14c05GWlhlR3RYUjBwSVZXeENWMkpZYUdoVVZWcDNWbXh
  72 VmxoU01taFlWMWN4TUdReFZrZFhibEpPVm1zMWNWVnRlR0ZOUmxKWFZXdE9WV0Y2UmxoWk1GSkRXVlphVjJOR1FsZFdSVVkwV1RJe
  73 5KV1ZFRjRWMGRTUlZSc2NGZFdNVXBKVm0xd1FtVkhUbk5YYmtaV1lraENUMVZxUmt0VFZsbDRWMjFHVkUxVmNIcFhhMmhIVmxkS1I
  74 aGhXVlJHWVUweFVuTlhiWFJZVWpGS1NWcEZaSGRVYkZwelYxUkdWMVpGYnpCWlZFWmhVMFpPY2xkc1VtbFNNMmhaVjFjd01WRXhTW
  75 lSbkJYV2xWYVlXTXlUa1phUjBaVFlsWktVRlpVUWxkVE1VNVhWMWhvVm1Fd05WaFVWM1JYVGtaWmVVNVZkRlZpUm5Bd1ZsZDRWMWR
  76 ZUZSc1pGZGliRXBRVm14b1UxWnNVbGRYYms1T1RWWnNOVnBWWkVkV01ERnlZMFZvV2sxR1NsQldiRnBoVW14a2RXTkdaR2xYUjJoN
  77 xaMFRsVk9WMDFXY0ZaVk1uQkRWR3hLYzJKRVRsVldiSEJvVmtSR1lWSnNaSE5oUmxaWFpXeGFNbGRyWkRSWlYwNVhWRzVLYTFKck5
  78 ZGtNVXBYVW01T2FsSnRVazlWYlRWRFUyeGFkR1ZIY0U1V2JGWTFWVEowYTFaSFNraGxSbVJhWVRKU2RsWXdXbk5qTWtaSFZHMW9VM
  79 9VbnBzV1ZWcVFuZGxWbGw1WlVoT1dHSlZWalJXYkdodlYyc3hSMk5HYUZwbGExcFlXWHBHZDFOSFZrZGFSMnhVVWxWd2FGWnRkR0Z
  80 VmtkS1NHRkdhRmRoYXpWMlZsVmFZV05XU25Ka1JtUlhZVE5CZUZkWGRHRldNVmw1VTJ0YWFsSnNXbGhaYkdoRFZFWldObEp0UmxkT
  81 xob2FGWkhlR0ZrVmtaelkwWmtWMDB5YURKWFdIQkxVekZKZUZWdVNsaGlSMmh3VldwR1MyRkdaRmhrUjBaVVRWVTFTRll5TlV0WFI
  82 TnNWbE5XUlVwWVZGVmFkMVpHV1hkYVJUbFRZa1UxZVZSc1dtdGhWbVJJWVVac1YySllRa3RhVlZwS1pWWktkVlZzVW1sU2JrSlJWb
  83 9WRkpzV25oV01uaFBZVlpKZUZOc2JGZFNiRXBNV1dwQmVHTXhjRWRoUjNCVFZqRktkbFpHV2xaTlZrNUhWMnRvVDFaVWJHOVZiWFJ
  84 YlhoTFpXeFplV042Vm1oU2JIQXdWbGQwYzFkc1dsZGpTRnBYWVd0d1RGVnFSazlqYlZaSVVteGtUazFFVVhkV2JYQkRXVlpSZVZSd
  85 ZOSFZraFBWbkJYWWtkM01GWnFTVEZVTWtaelUxaHNhRkl5YUZkWmEyUlRWa1paZDFkc1dtdE5XRUpJVmtkNFQxUnNXWGhUYWxaWFV
  86 QldOVlZ0ZUd0V1JtUklZVVpXV21KVVJsUldNRnB6WXpKR1JsUnNWbE5pV0dnMFZsY3hOR0V5Um5KTlZtaFdZV3RhV0ZadWNFWk5Sb
  87 VaRmhTYlhoWldrVmtSMVpXU25OWGFrSlZWbXhWTVZaVVNrdFdiR1J5WWtaYWFWZEhhRkZXYlhCTFV6Sk9jMVJ1VGxSaVIxSlBWbTE
  88 VW5CV01GWkxWVlphYzFWcmRGTk5WV3cwV1RCV2ExbFdTblJoU0VKWFlrWndNMXBWV21GU01XUjBaRVphVGxKRldsbFdiVEF4VlRKS
  89 xaaGExcFBXbFphVjJOc2NFZGFSMnhUVFRKb00xWnNZM2hPUm14WVUxaG9WbUpIYUU5V2JuQnpWakZzY2xkdVpFNVNiRXBYV1ZWak5
  90 SlhaREZrUjFkdVNsZGlWVnB4Vm0weE5HVldXWGxPVjNSVllrVndNVlZYZUd0WFIwVjRWMjVLV2xac2NFdGFSRXBQVW0xR1IyTkZOV
  91 dia3BvVW0xU2NGWnJXbUZXVmxwelZtMUdXbFl3TVRWV1IzUnpWVzFLU0ZWck9WWmhhMXBNVkZaYWEyTXhjRVZWYkhCWFlUSjNNRlp
  92 VmsxcmNGcFpWVnB2VmpKR2NtRXphRnBXUlhCSVZXcEdUMk14V25OVWJXeFVVbFZ3V1ZadE1IZGxSMGwzVFVob1dHSnJXbFJaVkU1V
  93 ZwM1kyeGFjMWRyWkdwTlYxSXdXbFZhVDJGV1NYcFpNMmhYWWtkUk1GbHFTa3BsUm1SeVlVWk9XRk5GU25aV1Z6QjRZakZaZUdKSVV
  94 VlNiRkpvWVRCd2RsWkdaSHBsUlRWWFZtNVNiRkl6VWxoVmFrSjNVMVp3Vmxkck9WaGlWVlkwVmpKd1QxWXdNVWRqU0hCYVpXdGFXR
  95 JVbXhvVjFKdGFIWlhWbHBQVW1zMVYySkdjR2hOYkVwVlZtcENZV014WkVoV2ExcHJVbTVDV0ZsdGRFdFhiR1J5Vm0xMFUwMVdjSHB
  96 VDFkd1RsWnNiM2RXUmxwcVRsWmtSMWR1VG1wU1JVcG9WbXhhV21ReFduSlhhM1JyVm10YWVWWXllR0ZVYlVwelUyNXNWMkpHU2tOY
  97 d4b1YySlVWa1JhVmxwaFkyeHdTV05IZUZOaVNFRjNWbXRrTUdNeFpFaFRhMmhXWW10S1YxbFhkSGRrVm5CWVpVZEdXRll3TlVkWGE
  98 SldjR2hYYkZaaFZESk9jMXBJVW1wU2F6VlpWVzEwZDJSc1duUk5TR2hQVWpGR05GWXlkR3RoYkVwWVZXeHNXbUV4VlhoWk1uaFhZM
  99 tTVlJzV21oTlJGWlJWbGN4TkdReFduTldXR3hyVWpOU1YxUlZVa2RYUm10M1ZXdGtWMkpWY0ZwWlZWcHZWMnhhVjFacVVsWmlSbkJ

```

| User | Language | Tested N | Time | Output |
| --- | --- | --- | --- | --- |
| Anders Kaseorg | Rust | \\$\frac{10^{23500000}-1}9\\$ | 59.471s | `x` |
| Neil | JavaScript (Node.js) | \\$\frac{10^{90000}-1}9\\$ | 56.409s | `x` |

# Answer
# Rust, \\$3^{38\\,000\\,000}\\$ in ~1 minute

### How it works

Given position \\$n\\$, we convert \\$3n\\$ into a base-\\$\frac43\\$ representation with digits \\$0, 1, 2, 3\\$ using a relatively fast divide-and-conquer algorithm. Iterating through these base-\\$\frac43\\$ digits from most to least significant gives the shifts needed to maintain a three-character sliding window of the Base64 fixed point.

For example, given position \\$27\\$, we compute

$$3 · 27 = (3210201101)\_{\frac43},$$

so we can jump the sliding window to the following positions (in units of \\$\frac13\\$ of a 6-bit character).

$$0 · \frac43 + 3 = 3, \quad 3 · \frac43 + 2 = 6, \quad 6 · \frac43 + 1 = 9, \quad 9 · \frac43 + 0 = 12, \\ 12 · \frac43 + 2 = 18, \quad 18 · \frac43 + 0 = 24, \quad 24 · \frac43 + 1 = 33, \quad 33 · \frac43 + 1 = 45, \\ 45 · \frac43 + 0 = 60, \quad 60 · \frac43 + 1 = 81.$$

### Usage

Accepts a base-ten integer on STDIN, and outputs a character to STDOUT.

```
$ cargo build --release
$ python3 -c 'import gmpy2; print(gmpy2.mpz(3) ** 38000000)' > /tmp/in
$ time target/release/base64 < /tmp/in
1

real    1m0.092s
user    1m0.023s
sys     0m0.068s

```

### Code

**`Cargo.toml`**

```
[package]
name = "base64"
version = "0.1.0"
edition = "2021"

[dependencies]
rug = "1.19.0"

```

**`src/main.rs`**

```
use rug::Integer;
use std::io::BufRead;

const ALPHABET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

fn encode_low(n: Integer, k: u32) -> (Integer, Integer, Integer) {
    if k == 1 {
        let t = n * 3;
        let l = Integer::from(&t & 3);
        (3.into(), t >> 2, l)
    } else {
        let k0 = k / 2;
        let (p0, h0, l0) = encode_low(&n & !((!Integer::ZERO) << (k0 * 2)), k0);
        let k1 = k - k0;
        let (p1, h1, l1) = encode_low((n >> (k0 * 2)) * &p0 + h0, k1);
        (p1 * p0, h1, l1 << (k0 * 2) | l0)
    }
}

fn encode(n: Integer) -> Integer {
    if n == 0 {
        Integer::ZERO
    } else {
        let k = (n.significant_bits() + 1) / 2;
        let (_, h, l) = encode_low(n, k);
        encode(h) << (k * 2) | l
    }
}

fn char_at(n: Integer) -> char {
    let e = encode(n);
    let mut a: u32 = 0x566d30;
    for i in (0..e.significant_bits()).step_by(2).rev() {
        let k = 6 - e.get_bit(i + 1) as u32 * 4 - e.get_bit(i) as u32 * 2;
        a = (ALPHABET[((a >> (k + 12)) & 0x3f) as usize] as u32) << 16
            | (ALPHABET[((a >> (k + 6)) & 0x3f) as usize] as u32) << 8
            | (ALPHABET[((a >> k) & 0x3f) as usize] as u32);
    }
    char::from((a >> 16) as u8)
}

fn main() {
    for line in std::io::stdin().lock().lines() {
        let n: Integer = line.unwrap().parse().unwrap();
        println!("{}", char_at(n));
    }
}

```
> 10 votes

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

```
var btoa = s => Buffer.from(s).toString('base64');
var fp = (n, m = n + 1n) => m > 9n ? btoa(fp(n / 4n * 3n, (m + 3n) / 4n * 3n)).slice(Number(n % 4n), Number(n % 4n + m - n)) : "Vm0wd2QyU".slice(Number(n), Number(m));

```

Try it online! Link includes test cases. Using Node because it has a reasonably convenient `btoa` builtin, so it won't win any speed records but at least it scores reasonably well in time complexity.

Since the above code is recursive and stack space is expensive, here's an iterative version, although this only returns one character at a time so there's only one test case: Try it online!

```
var btoa = s => Buffer.from(s).toString('base64');
function fp(n) {
	stack = [];
	while (n) {
		stack.push(Number(n % 4n));
		n = n / 4n * 3n;
	}
	s = "Vm0wd2QyU";
	while (stack.length) s = btoa(s).substr(stack.pop(), 9);
	return s[0];
}
console.log(fp(3n ** 100000n));

```
> 4 votes

---
Tags: fastest-code
---


title: Roll a painted cube

text:
# Question
Title: Roll a painted cube
There is a 1x1x1 cube placed on a infinite grid of 1x1 squares. The cube is painted on every side, so it leaves a mark on the grid when it moves.

The sides of the cube are colored 6 distinct colors, re-presentable with any 6 distinct values. A 7th value represents a blank space.

The cube can roll around the grid. Every step it rotates precisely 90 degrees around one edge that touches the ground. Then the side facing down will leave a mark in that spot.

Given the path of the cube, output the pattern it leaves on the grid.

You may assume every spot is hit at most once. 0 bonus points if you use proper paint mixing rules in this case, but this is not necessary.

## Test Cases

```
Path:        Pattern

EEE          YMBG

ESE          YM
              RB

SEN          YY
             RM

NNNN         Y
             R
             B
             C
             Y

```

## IO

You can use any 4 distinct values to represent the directions, except complete or partial functions.

Output as a 2d array, a string, or a image. Any 6 values can be used to represent the colors of the cube sides. Extra respect for those who output as a image though.

You may leave extra blank spaces around the edges.

# Answer
# Vyxal, 28 bytes

```
6ɾ£⟑½4ʁ=⁺…*9+⟑¥Ṗi£;¥h;1pṅ2ø∧

```

Try it Online!

Expects a list of numbers 0, 2, 4, 6 for `NESW` respectively. Outputs a string with numbers 1 to 6 for each of the colors.

It represents cube rotations as permutations of sides of the cube. The lexicographically 9th permutation represents rotating 90 degrees around the vertical axis and the lexicographically 325th permutation represents rotating 90 degrees around the vertical axis and then rolling west.

Rolling in direction \\$n\\$ can be represented as rotating \\$90(n/2+1)\\$ degrees around the vertical axis, rolling west and then rotating rotating \\$90(3-n/2)\\$ degrees around the vertical axis. This corresponds to sequences of three 9th permutations and one 325th permutation.

```
6ɾ£                     # save [1,2,3,4,5,6] to the register
   ⟑                    # map input:
    ½                   #   halve
     4ʁ                 #   push [0,1,2,3]
       =                #   equals?
        ⁺…*             #   times 316
           9+           #   plus 9
                        #     Now we have a list with three nines and one 325
             ⟑          #   for each:
              ¥         #      push register
               Ṗi       #      index into permutations
                 £      #      save register
                  ;     #   end for
                   ¥h   #   first item of register
                     ;  # end map

```

Now we have the sequence of bottom side colors after rolling the cube along the path.

```
1p       # prepend 1
  ṅ      # join by nothing
   2     # push 2
    ø∧   # canvas draw

```
> 9 votes

# Answer
# JavaScript (ES6), 154 bytes

*-7 thanks to @l4m2*

Expects a list of directions in \\$0..3\\$ for `NWSE` and returns a matrix filled with \\$-3..3\\$ for `MRB.YCG`.

A rather naive implementation.

```
a=>a.map(d=>m[[A,B,C]=[[-B,A,C],[A,C,-B],[B,-A,C],[A,-C,B]][d],y+=--d%2][x+=~-d%2]=B,m=(b=[...a+0,C=3]).map(_=>b.map(_=>0)),m[x=y=a.length][x]=B=1,A=2)&&m

```

Try it online!

### How?

The sides of the cube are arranged in such a way that the sum of two opposite faces is always \\$0\\$, which is similar to how 6-sided dice are designed (except the sum is \\$7\\$ in that case).

We only need to keep track of \\$3\\$ orthogonal faces \\$A\\$, \\$B\\$, \\$C\\$. By convention, we define \\$B\\$ as the face currently touching (and painting) the ground.

When rotating the cube, the value of a 'hidden' face is given by \\$-X\\$ where \\$X\\$ is the value of its 'visible' counterpart.

### Commented

```
a =>                 // a[] = input array
a.map(d =>           // for each direction d in a[]:
  m[                 //
    [A, B, C] = [    //   apply the cube rotation ...
      [-B,  A,  C],  //     0: North
      [ A,  C, -B],  //     1: West
      [ B, -A,  C],  //     2: South
      [ A, -C,  B]   //     3: East
    ][d],            //   ... according to d
    y += --d % 2     //   add dy to y
  ][x += ~-d % 2]    //   add dx to x
  = B,               //   set m[y][x] = B
                     //   initialization:
  m = (              //     set up a square matrix m[]
    b = [ ...a + 0,  //     using an array b[] twice as large as a[]
          C = 3 ]    //     with an additional (dummy) element
  )                  //
  .map(_ =>          //     fill all cells ...
    b.map(_ => 0)    //     ... with 0's
  ),                 //
  m[                 //     initialize (x, y) to the center square
    x = y = a.length //
  ][x] = B = 1,      //     and set this square to 1 (yellow)
  A = 2              //     we start with (A,B,C) = (2,1,3)
) && m               // end of map(); return m[]

```
> 6 votes

# Answer
# 05AB1E, ~~39~~ 38 bytes

```
6LIĆv¤ˆā•R∊j% uWQöñ•4ô₂S£y;δè`‡<è}2¯IΛ

```

Uses `0,2,4,6` for `N,E,S,W` respectively, and uses `1,2,3,4,5,6` for the colors `B,R,M,C,G,Y` of the challenge description respectively.

Try it online or verify all test cases.

**Explanation:**

*General explanation:*

1. `6LIĆv¤ˆā•R∊j% uWQöñ•4ô₂S£y;δè`‡<è}` is to generate the output values in the correct order based on the 'rolling' cube.
2. `2¯IΛ` is to output it in the correct output-format.

For step 1, I start with a list `[1,2,3,4,5,6]` as this starting position:

```
1     U
2345  FRBL
6     D

```

(The diagram next to it indicates `U`p; `F`ront; `R`ight; `B`ack; `L`eft; and `D`own respectively.)

For the four directions, the following changes take place:

| Direction | Cube 'roll' change | Changes pattern | Actual changes |
| --- | --- | --- | --- |
| `N`orth | `123456``263154` | `xx.x.x` | `1246``2614` |
| `E`east | `123456``521463` | `x.x.xx` | `1356``5163` |
| `S`outh | `123456``413652` | `xx.x.x` | `1246``4162` |
| `W`est | `123456``326415` | `x.x.xx` | `1356``3615` |

These are basically the changes I do in my code as well with a transliterate on `123456`, after which I use this to index into the current state of the cube.

For step 2: I use the Canvas builtin `Λ` (see this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin) to draw the characters from step 1 in the directions of the given input.

*Code explanation:*

```
6L                   # Push list [1,2,3,4,5,6]
  I                  # Push the input-list
   Ć                 # Enclose; append its own head (to have an extra iteration)
    v                # Pop and for-each `y` over these input-directions:
     ¤               #  Push the last item of the list (without popping)
      ˆ              #  Pop and add this last digit to the global array
     ā               #  Push a list in the range [1,length] (without popping the list);
                     #  a.k.a. push list [1,2,3,4,5,6] again
      •R∊j% uWQöñ•   #  Push compressed integer 124613562614516341623615
       4ô            #  Split it into parts of size 4: [1246,1356,2614,5163,4162,3615]
         ₂S£         #  Split it into parts [2,6]: [[1246,1356],[2614,5163,4162,3615]]
            y        #  Push the current direction `y`
             ;       #  Halve it
              δ      #  Map over each inner list with halve the direction as argument:
               è     #   Modular 0-based index halve the direction into the inner list
                `    #  Pop and push both integers to the stack
                 ‡   #  Transliterate the digits of the first to the second in list
                     #  [1,2,3,4,5,6]
                  <  #  Decrease each by 1 to a 0-based index
                   è #  Index it into the current list
   }2                # After the loop: Push 2
     ¯               # Push the global array
      I              # Push the input-list
       Λ             # Use the Canvas builtin with these three options,
                     # and output immediately afterwards implicitly

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•R∊j% uWQöñ•` is `124613562614516341623615`.
> 4 votes

# Answer
# Python NumPy, 165 bytes

```
def f(p):
 s=r_[:4];y=x=len(p);o=pad([[s]],y)[...,y+1:-y]
 for c in p:s=s[2*c];_,j,k,l=c;y+=j+k-3;x+=(k+l)%4-1;o[y,x]=s[argmin(s):][1:4]
 return o
from numpy import*

```

Attempt This Online!

Takes a list of lists as input S=\[2,3,1,0\],N=\[3,2,0,1\],W=\[2,0,3,1\],E=\[1,3,0,2\] and returns an NxNx3 array of RGB values.

### How?

Represents cube orientations (and 90 degree rotations) as permutations of its four long diagonals.

Each diagonal connects two opposite corners of the cube:

```
   3----------2
  /|\        /|
 / | \      / |
0----------1  |
|  |   \   |  |
|  1----\--|--0
| /      \ | /
|/        \|/
2----------3

```

This wireframe shows the outline of a cube and one of the diagonals (diagonal 3). All eight corners are labelled by the diagonal (0,1,2,3) they belong to.

As the rotations we are interested in are fully characterised by the permutation they induce on the corners and as they preserve oppositeness of corners it may look like a good idea to encode such rotations as permutations of the four diagonals. And it is.

Now, we can see that the (orthogonal) orientations of the cube map 1:1 to permutations of 0,1,2,3.

Let us against normal convention write permutation abcd

as

```
ba
cd

```

and think of corners of the bottom face like in the picture (in the picture a,b,c,d = 0,1,2,3)

Now for example rolling the cube repeatedly over the (bottom) back edge will map:

```
10  ->  32  ->  01  ->  23  ->  10
23      10      32      01      32

```

(Always the bottom face is shown.)

For the (bottom) right edge it would be

```
 10  ->  02  ->  23  ->  31  ->  10
 23      31      10      02      23

```

Note that every orientation maps to a unique permutation and, conversely, each permutation actually represents an orientation (not in the examples but over all possible orientations)

Further note that by singling out a "null" orientation O\_n `0123` each orientation o doubles as a rotation r, viz. the r that takes O\_n to o. Also, te effect of two consecutive rotations is the product of the corresponding permutations.

Finally, note the identity of the bottom face and therefore the colour applied is easily read off the permutation representation of the orientation: the total of 24 orientations / permutations splits into six groups of four which differ by quarter turns:

```
10  ~~  03  ~~  32  ~~  21
23      12      01      30

```

In practical terms, we can given an orientation; find the position of zero and then read ccw. This yields one of the six permutations of 1,2,3; a different one depending on which of the six faces of the cube is facing down.
> 4 votes

# Answer
# Charcoal, 47 bytes

```
≔YMCRGBηＦＳ«✳ι§η⁰≔⭆§⪪”)⊟Z➙.κ⊗φαμ”⁶⌕RULι§ηＩκη»§η⁰

```

Try it online! Link is to verbose version of code. Uses `ULDR` instead of `NWSE`. Explanation:

```
≔YMCRGBη

```

Start with the six colours.

```
ＦＳ«

```

Loop over the path.

```
✳ι§η⁰

```

Draw the square just being exited.

```
≔⭆§⪪”)⊟Z➙.κ⊗φαμ”⁶⌕RULι§ηＩκη

```

Permute the colours according to the direction.

```
»§η⁰

```

Draw the final square.
> 3 votes

# Answer
# HTML + Javascript graphical output, ~~269~~ 254 bytes

Building on Arnaulds answer, this draws the colored fields to a `<svg>`.

-15 bytes by switching from `<canvas>` to `<svg>`.

Directions are entered as 0..3 for `NWSE`. Colors are mapped from 1..6 as

```
1: hsl(60,90%,50%)  = #f2f20d
2: hsl(120,90%,50%) = #0df20d
3: hsl(180,90%,50%) = #0df2f2
4: hsl(240,90%,50%) = #0d0df2
5: hsl(300,90%,50%) = #f20df2
6: hsl(360,90%,50%) = #f20d0d

```

```
w=a=>{A=1,B=2,C=3,x=y=a.length,c=`<svg viewBox=${[0,0,3*x,3*y]}>`;(f=()=>(c+=`<rect x=${x} y=${y} width=1 height=1 fill=hsl(${B*60},90%,50%) />`))();for(d of a){[A,B,C]=[[7-B,A,C],[A,C,7-B],[B,7-A,C],[A,7-C,B]][d],y+=--d%2,x+=~-d%2,f()}document.write(c)}

w([3,2,3])
```
> 2 votes

# Answer
# Python3, 580 bytes:

```
m=['abcd','afce','fbed']
E=enumerate
def f(d):
 v,s,c,x,y,U,P=[[m[0][0]]],0,0,0,0,0,0
 v[0][0]=m[0][0]
 for i in d:
  X,Y={'N':(-1,0),'S':(1,0),'E':(0,1),'W':(0,-1)}[i]
  if(0,0)!=(U,P)and((not U and X)or(not P and Y)):[(s,c)]=[(j,a.index(m[s][c]))for j,a in E(m)if m[s][c]in a and j!=s]
  U,P=X,Y
  c+=[-1,1][::[1,-1][s%2]][::[-1,1][i in['N','W']]][i in['E','N']];x+=X;y+=Y
  c%=4
  if y==len(v[0]):y=len(v[0]);v=[I+['']for I in v]
  if y<0:y=0;v=[['']+I for I in v]
  if x==len(v):x=len(v);v=v+[[''for _ in v[0]]]
  if x<0:x=0;v=[[''for _ in v[0]]]+v
  v[x][y]=m[s][c]
 return v

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~126 124 122~~ 119 bytes

2 bytes saved by changing colours from `ABCEFG` to `123456`, 2 bytes saved by deleting `[]` from `[1,2,3]`, 3 bytes saved by changing directions from `0,1,2,3` to `-2,-1,0,1`.

```
->n{a=($/+?.*w=n.size*4)*w
a[q=w*w/2]=?2
c=1,2,3
n.map{|i|c[j=i&1,2]=c[j+1]*s=i|1,-c[j]*s
a[q+=s+j*w*s]="#{c[1]%7}"}
a}

```

Try it online!

Takes an array of numbers `-2,-1,0,1` corresponding to `W,N,E,S` or equivalently `x-=1,z-=1, x+=1,z+=1`. Outputs the path of the cube traced on a string of `w*w` periods, where `w` is four times the length of the input.

The cube is represented as a vector `c=[x,y,z]` starting at `[1,2,3]` which rolls in the `xz` plane. The colour is determined by the current `y` coordinate. If the cube is rotated 180 degrees, the y coordinate becomes negative, so the possible values are `-3,-2,-1,1,2,3` with opposite faces adding to zero. To display, the number is taken mod 7 and this is converted to a character, so the possible displayed colours are `1,2,3,4,5,6` with opposite faces adding to 7.

The vector is rotated by 90 degrees by swapping two coordinates and changing the sign of one of them, similar to Arnauld's answer, but where he uses an array, I use the formula `c[j,2]=c[j+1]*s,-c[j]*s` where `c[j,2]` is a block of 2 array elements starting at `j`=0 or 1 and `s` is the sign of the rotation, +1 or -1.

`s` is also the sign of the direction of movement and is calculated as `i|1`. `s` equals -1 for `-2|1` and `-1|1`, and 1 for `0|1` and `1|1`. `j` is calculated as `i&1` and equals 0 for even numbers `-2` and `0` (travel in `x` direction) and 1 for odd numbers `-1` and `1` (travel in `z` direction.)

**Commented code**

```
->n{a=($/+?.*w=n.size*4)*w            #make a string of w*w periods separated in lines by /n
a[q=w*w/2]=?2                         #set q to the centre of the field (padding by the /n characters ensures w*w/2 is central horizontally as well as vertically)
c=1,2,3                               #put a 2 at position q. Set up a vector c for colours x,y,z
n.map{|i|                             #iterate through array of directions. j=1 for vertical, 0 for horizontal. s=1 for increase, -1 for decrease
c[j=i&1,2]=c[j+1]*s=i|1,-c[j]*s       #in accordance with value of j, swap c[0]&c[1] or c[1]&c[2] and change the sign of one in accordance with s
a[q+=s+j*w*s]="#{c[1]%7}"}            #modify the value of q by s (horizontal) or (1+w)s (vertical) and save colour%7 at a[q]
a}                                    #return the final string a.

```
> 1 votes

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


title: Group elements by their displacement

text:
# Question
Title: Group elements by their displacement
Consider the array `[5, 6, 8, 3, 9, 4, 2, 1, 7]`. If we list how far each number has moved from it's (1-indexed*) index, we have (considering absolute distance):

```
Array: [5, 6, 8, 3, 9, 4, 2, 1, 7]
Index: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Dists:  4  4  5  1  4  2  5  7  2

```

We can then group the elements of the array based on their distance away from their indices:

```
[[3], [4, 7], [5, 6, 9], [8, 2], [1]]

```

Additionally, we can optionally include empty lists to indicate distances not there (e.g. `0`):

```
[[], [3], [4, 7], [], [5, 6, 9], [8, 2], [], [1], []]

```

Note that the maximum distance an element can be from its index is `len(list) - 1` and the minimum is `0`, so the list (including empty lists) will always be the same length or less as the original list.

*: Note that it doesn't matter if we use 1 or 0 indexing

---

Given a list of `n` positive integers, group the elements of the list by their absolute distance from their indices. The input is guaranteed to be a permutation of `[1, 2, 3, ..., n]` and will have a minimum of `3` elements. You may choose to include empty lists in the output, but only if the length of the output is the same length as the input.

The elements of the groups can be separated with any clear, consistent, non-digit separator, and the groups themselves should be separated in the same way, but with a separator that's different from that used to separate the elements of the groups. For example, spaces and newlines, or nested lists.

This is so the shortest code in bytes wins.

## Test cases

```
[1, 3, 2] -> [[1], [3, 2]]
[3, 2, 4, 1] -> [[2], [4], [3], [1]]
[1, 2, 3, 4] -> [[1, 2, 3, 4]]
[2, 5, 3, 1, 4, 6] -> [[3, 6], [2, 4], [5, 1]]
[2, 1, 3, 6, 5, 7, 4] -> [[3, 5], [2, 1, 7], [6], [4]]
[1, 7, 4, 2, 8, 6, 3, 5] -> [[1, 6], [4], [2], [8, 5], [3], [7]]
[2, 6, 8, 3, 1, 7, 9, 5, 4] -> [[2, 3, 7], [9], [5], [6, 1], [8, 4]]
[5, 6, 8, 3, 9, 4, 2, 1, 7] -> [[3], [4, 7], [5, 6, 9], [8, 2], [1]]
[1, 7, 5, 10, 8, 9, 6, 3, 4, 2] -> [[1], [6], [5], [8, 9], [7, 3, 4], [10], [2]]
[10, 8, 5, 9, 2, 3, 4, 7, 6, 1, 11, 12] -> [[11, 12], [7], [5], [2, 3, 4, 6], [9], [8], [10, 1]]
[3, 5, 10, 11, 6, 7, 12, 14, 8, 2, 9, 13, 1, 4] -> [[6, 7, 8, 13], [3, 9], [5], [12], [14], [10, 11], [2], [4], [1]]
[6, 14, 8, 9, 12, 4, 13, 7, 5, 15, 10, 11, 3, 1, 2] -> [[7, 10, 11], [4], [5], [6, 8, 9, 15], [13], [12], [3], [14], [1, 2]]
[8, 12, 13, 7, 16, 5, 14, 15, 3, 10, 2, 4, 1, 9, 11, 6] -> [[10], [5], [7], [11], [9], [3], [8, 14, 15], [4], [2], [12, 13, 6], [16], [1]]
[14, 5, 10, 1, 2, 4, 13, 9, 7, 12, 8, 11, 3, 15, 16, 6] -> [[9, 11, 15, 16], [4, 7, 12], [5, 1, 2, 8], [13], [10], [3, 6], [14]]
[19, 8, 16, 15, 2, 6, 11, 18, 12, 9, 3, 14, 4, 1, 7, 5, 17, 13, 10] -> [[6, 17], [9], [14], [2, 12], [11], [13], [8], [3, 7], [4, 10], [18], [15, 5], [16, 1], [19]]
[19, 11, 7, 5, 3, 1, 20, 16, 17, 15, 10, 13, 6, 18, 2, 12, 9, 4, 14, 8] -> [[5, 10, 13], [3], [7, 18, 12], [1, 15, 14], [6], [16, 17, 9], [11], [8], [20, 2], [4], [19]]

```

# Answer
# , 10 bytes

```
</.~]|@-#\

```

Try it online!

* `</.~` Group by...
* `]|@-#\` Absolute value of `|@` input minus all length prefixes (ie, 1 2 3... n)
> 7 votes

# Answer
# Jelly, 4 bytes

```
ạJĠị

```

A monadic Link that accepts the list of integers and yields a list of lists of integers.

Does not perform the optional empty list insertions.

**Try it online!**

### How?

Pretty simple for Jelly this one...

```
ạJĠị - Link: list of integers, A
 J   - range of length of A -> [1,2,...,length(A)]
ạ    - A absolute difference that (vectorises)
  Ġ  - group indices of that by their values
   ị - use those to index back into A

```
> 6 votes

# Answer
# JavaScript, 151

```
x=>x.map((y,i)=>[y,Math.abs(y-i-1)]).sort((a,b)=>a[1]-b[1]).reduce((g,z)=>d-z[1]?(d=z[1],[...g,[z[0]]]):[...g.slice(0,-1),[...g.at(-1),z[0]]],[[]],d=0)

```
> 5 votes

# Answer
# Vyxal, 11 bytes

```
ż-ȧZ⁽tṡfyĠ•

```

Try it Online!

The pains of not having tons of array focused built-ins

## Explained

```
ż-ȧZ⁽tṡfyĠ•
ż           # The range [1, len(input)]
 -ȧ         # and the absolute difference with the input
   Z        # Zip those together
    ⁽tṡ     # and sort that by tail - this is a work around way to group one list by the results of a function applied to it
       fy   # flatten and uninterleave this - this pushes the original list and the absolute differences but sorted
         Ġ  # group the indexes on consecutive items
          • # and mold the other list to the shape of that.

```
> 5 votes

# Answer
# Factor, 52 bytes

```
[ dup '[ dup _ index 1 + - abs ] collect-by values ]

```

The `collect-by` word postdates build 1525, the one TIO uses, so here's a screenshot of running the above code in build 2101's listener:

`collect-by` is a combinator that collects values in an associative array by a given quotation. The quotation calculates the difference between an element and its index. Then we take only the values from the associative array, discarding the keys.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 28 bytes

```
GatherBy[#,i=0;Abs[#-++i]&]&

```

Try it online!
> 4 votes

# Answer
# , 32 bytes

```
function(x)split(x,(x-seq(x))^2)

```

Try it online!

(51 bytes if we want to include the empty lists for displacements that don't occur:
`function(x)Map(function(n)x[abs(x-s)==n],s<-seq(x))`, painfully long because of the double "`function`" keyword, although this could be replaced by "`\`" in ≥4.1 for 37 bytes)
> 4 votes

# Answer
# Python 2, 111 bytes

```
o={}
for a,b in[[abs(x+1-y),y]for x,y in enumerate(input())]:o.setdefault(a,[]).append(b)
print[o[p]for p in o]

```

Try it online!

Not particularly short or clever but it was fun. Unbelievably `o.setdefault(a,[]).append(b)` is shorter than any way I could find of using a comparison.
> 4 votes

# Answer
# Japt `-Q`, 4 bytes

```
üÈaY

```

Try it

* saved 1 by 0-indexing

```
ü      - sort and group by:
 È     - f(value,index)
  aY   - distance(value,index)

```
> 4 votes

# Answer
# 05AB1E, 4 bytes

```
.¡Nα

```

Input and index-comparison are both 0-based.

Try it online or verify all test cases.

The groups are sorted based on their first occurrence, rather than their index-difference, which is allowed in the comments. If this wouldn't have been the case, it would be this 14 bytes monstrosity instead (with 1-based input/comparison), since 05AB1E lacks a sort + group-by builtin in one, and doing them one at a time when comparing it to their index isn't exactly ideal..

```
āøΣÆÄ}.¡ÆÄ}€€н

```

Try it online or verify all test cases.

**Explanation:**

```
.¡       # Group the (implicit) input-list by:
  N      #  Push the 0-based index
   α     #  Get the absolute difference of this index and the number
         # (after which the list of lists is output implicitly as result)

ā        # Push a list in the range [1,input-length]
 ø       # Create pairs with the input-list
  Σ      # Sort this list of pairs by:
   Æ     #  Reduce the pair by subtracting
    Ä    #  And take the absolute value of that
  }.¡ÆÄ  # After the sort-by, do the same with a group-by
    }€   # After the group-by, map over each list of pairs:
      €  #  Map over each inner pair:
       н #   Only leave the first value
         # (after which the list of lists is output implicitly as result)

```
> 4 votes

# Answer
# BQN, ~~13~~ 11 bytesSBCS

Saved 2 bytes thanks to Razetime

```
{⊔˜|-↕≠}

```

Run online!

Outputs with empty lists (the first group is at the back though)

The best train I could get was `⊢⊔˜(|⊢-↕∘≠)` (also ~~13~~ 11 bytes). Razetime found two even smaller trains: `⊢⊔˜·|⊒˜⊸-` and `(|⊒˜⊸-)⊸⊔`, both 9 bytes!

```
{⊔˜|-↕≠}
  ⊔˜        # Group the elements of
           # the input by
    |-↕≠  # the displacements
       ↕≠  # Indices of the input: range (↕) to length (≠)
     -     # Distance from each element to its corresponding index
    |       # Absolute value

```
> 4 votes

# Answer
# JavaScript (ES6), 48 bytes

The output includes empty lists.

```
a=>a.map((_,i)=>a.filter((v,j)=>(v+=~j)*v==i*i))

```

Try it online!
> 3 votes

# Answer
# C (gcc), ~~91~~ ~~86~~ 84 bytes

```
j;i;f(a,n)int*a;{for(i=n*n;i--;j||puts(""))abs(a[j=i%n]-j)-i/n||printf("%d ",a[j]);}

```

Try it online!

*Saved 5 bytes thanks to tsh!!!*
*Saved 2 bytes thanks to ceilingcat!!!*

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Outputs the \\$0\\$-indexed numbers (separated by spaces) in displacements groups on separate lines for each possible displacement (so there may be empty lines).
> 3 votes

# Answer
# Python 2, 70 bytes

```
l=input()
d=[[]for _ in l]
n=1
for x in l:d[abs(x-n)]+=x,;n+=1
print d

```

Try it online!

Full program. Output includes empty lists.

-11 thanks to @loopywalt
> 3 votes

# Answer
# Python 3 \+ pandas, 48 bytes

```
lambda s:s.groupby(abs(s-s.index-1)).apply(list)

```

Input `pd.Series[int]`, output `pd.Series[List[int]]`. Could be 46 bytes if we use 0-indexed.

TIO didn't have pandas installed (although it installed NumPy). So no TIO link available.
> 3 votes

# Answer
# Ruby, 42 bytes

```
->a{r=0;a.group_by{|x|(x-r+=1)**8}.values}

```

Try it online!
> 3 votes

# Answer
# Husk, 5 bytes

```
kS≠€¹

```

Try it online!

```
k           # group each x in input by
 S≠         # difference between x and
   €        # index of x in
    ¹       # input

```
> 3 votes

# Answer
# Haskell, 83 bytes

```
g a=(\l->map(\k->[fst m|m<-zip a$map(\n->abs$1+n-a!!n)l,snd m==k])l)[0..length a-1]

```

Try it online!
> 3 votes

# Answer
# Haskell, 50 bytes

```
(\a->[[y|(j,y)<-a,abs(j-y)==i]|(i,_)<-a]).zip[0..]

```

Try it online! Uses 0-indexing
> 3 votes

# Answer
# Haskell, 43 bytes

```
f x=[[b|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

```

Try it online!

*Zero indexing. Outputs with empty lists*.

Nothing really clever here. I'm quite surprised that this is the shortest of *3* Haskell answers.

## Explanation

We have a first list comprehension

```
f x=[...|y<-x]

```

From `x` it takes all the possible distances we are looking for. Since `x` is a permutation every number we want appears and it appears exactly once.

Inside we have a second comprehension.

```
f x=[[...|(a,b)<-zip[0..]x,...]|y<-x]

```

Here we take an index and a value from `x`. Using `zip` to get the indexes.

```
f x=[[...|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

```

We filter only the ones such that their absolute difference is the desired distance.

```
f x=[[b|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

```

Then we return the value.
> 3 votes

# Answer
# Python3, 96 bytes:

```
f=lambda x,i=1,d={}:f(x[1:],i+1,{**d,(j:=abs(x[0]-i)):d.get(j,[])+[x[0]]})if x else[*d.values()]

```

Try it online!
> 2 votes

# Answer
# Charcoal, 11 bytes

```
ＩＥθΦθ⁼κ↔⁻λμ

```

Try it online! Link is to verbose version of code. 0-indexed. Output includes empty lists. Lists are double-spaced from each other. Explanation:

```
  θ         Input array
 Ｅ          Map over elements
    θ       Input array
   Φ        Filtered where
         λ  Inner value
          μ Inner index
       ↔⁻   Absolute difference
     ⁼      Equal to
      κ     Outer index
Ｉ           Cast to string
            Implicitly print

```
> 2 votes

# Answer
# Scala 3, 64 bytes

```
l=>l.indices.map(d=>l.indices.filter(i=>(i+1-l(i)).abs==d)map l)
```

Attempt This Online!

Includes empty lists.
> 2 votes

# Answer
# Haskell + hgl, 18 bytes

```
cr<<<bgB(Uc aD)<eu

```

*0 indexed*

# Haskell + hgl, 21 bytes

```
cr<<<bgB(Uc aD)<zp nN

```

*1 indexed*

## Explanation

The main crux of this is `bgB` which groups a list into chunks using a conversion function. This function was inspired by this answer.

The first thing we do in each answer is pair every element with it's index. For zero indexed that's `eu`, but for one indexed it's a little more expensive `zp nN`.

Then we do the grouping. We use `bgB` and our conversion function is the absolute difference `aD`. Since we need to operate on a tuple we have to uncurry `aD` with `Uc`.

Once we've made the groups we need to go remove the indexes, `cr` gets the second element of a tuple so we triple map `cr` to get the second element of every tuple.

## Reflection

This feels very big for what it's doing. It's nice we have the `bgB` to work with, but it doesn't quite fit here. The issue is that `bgB` is a very local function but index is a non-local property. So we need to put the indexes in, and then take them out. Not to mention this adds the currying necessary.

It's possible to imagine a version of `bgB` that doesn't have this issue, but it seems like it would be very specific to this problem.
> 2 votes

# Answer
# APL(Dyalog Unicode), 24 bytes SBCS

```
{⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}¨⍳≢⍵}

```

Outputs with empty lists.

Try it on APLgolf!

Idk how to convert this to tacit lol, I'm sure it's possible though.

```
{⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}¨⍳≢⍵}
{                      }             ⍝  a dfn in which...
                   ¨                 ⍝  for each element in...
                    ⍳≢⍵              ⍝  the range 1 to the length of the input...
 ⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}                  ⍝  apply the following function,
                                         with original the input passed in as the left argument:
   {     1+|⍺-⍳≢⍺ }                  ⍝  calculate the distance between the original list
                                         and its indices + 1...
      ⍸⍵=                            ⍝  and keep the ones that are equal to the right argument
                                         (which is an element from the range we are looping over)
    ⍺[           ]                   ⍝  then index the input (left argument)
                                         with the filtered list of indices

```
> 2 votes

# Answer
# Python/NumPy, 47 bytes (@tsh)

```
lambda a:[[*a[abs(a-sorted(a))==i]]for i in~-a]
```

Attempt This Online!

#### Python/NumPy, 49 bytes

```
lambda a:[[*a[(a-sorted(a))**2==i*i]]for i in~-a]
```

Attempt This Online!

Avoiding explicit numpy import saves 15.

#### Python/NumPy, 64 bytes

```
lambda a:[[*a[abs(a-sort(a))==i]]for i in~-a]
from numpy import*
```

Attempt This Online!

This version exploits that OP doesn't care for order.

#### Python/NumPy, 71 bytes

```
lambda a:[[*a[abs(a-sort(a))==i]]for i in sort(a)-1]
from numpy import*
```

Attempt This Online!

Expects a numpy array but outputs a plain list of lists instead of a list of arrays which would be 3 bytes shorter but looks rather ugly.
> 1 votes

# Answer
# Arturo, 34 bytes

```
$=>[0gather&=>[abs&-dup+1]|values]

```

Try it
> 1 votes

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


title: Collect the elements of an array

text:
# Question
Title: Collect the elements of an array
Add++, the Language of the Month, has the "collect" builtin as `BC`. Your task is to implement this builtin.

---

Consider a non-empty array, where each element is either:

* A positive digit between `1` and `9` inclusive, or
* A non-empty list of positive digits between `1` and `9`

For example, all the following such arrays meet this definition:

```
[1, 2, 3, 4, 5]
[7, [5, 3], 2]
[1, [2, 2], 3, [4, 4], 5]
[[1], 2, 3, [4], 5, [4], 2]
[[9, 4, 2]]
[[1], 2, 3, 4, 5, [6], 7]
[6, [1, 9, 4]]

```

Note that elements can be repeated, both the digits, the inner lists and the elements of the inner lists.

The `BC` builtin "collects" adjacent digits in the array, and groups them into a list, while leaving the existing lists untouched. Applying this to the above lists, the examples make this clear:

```
[[1, 2, 3, 4, 5]]
[[7], [5, 3], [2]]
[[1], [2, 2], [3], [4, 4], [5]]
[[1], [2, 3], [4], [5], [4], [2]]
[[9, 4, 2]]
[[1], [2, 3, 4, 5], [6], [7]]
[[6], [1, 9, 4]]

```

For example, with `[[1], 2, 3, 8, 9, [6], 7]`, we group the `2, 3, 8, 9` together, and the `7` to give `[[1], [2, 3, 8, 9], [6], [7]]`

You should take a ragged list as input, that meets the list format described above, and output a list of lists after the `BC` builtin has been applied to the input. This is , so the shortest code in bytes wins.

## Test cases

```
[[9, 4, 2]] -> [[9, 4, 2]]
[6, [1, 9, 4]] -> [[6], [1, 9, 4]]
[7, [5, 3], 2] -> [[7], [5, 3], [2]]
[1, 2, 3, 4, 5] -> [[1, 2, 3, 4, 5]]
[1, [2, 2], 3, [4, 4], 5] -> [[1], [2, 2], [3], [4, 4], [5]]
[[1], 2, 3, 8, 9, [6], 7] -> [[1], [2, 3, 8, 9], [6], [7]]
[[1], 2, 3, [4], 5, [4], 2] -> [[1], [2, 3], [4], [5], [4], [2]]
[9, 8, 7, 6, [5, 4, 3], 2, 1] -> [[9, 8, 7, 6], [5, 4, 3], [2, 1]]
[[8, 2], 9, 5, 1, [6, 4], [4, 5]] -> [[8, 2], [9, 5, 1], [6, 4], [4, 5]]
[7, [5, 3], 2, [1, 2, 3], 9, 8, 7, 8, 9, [3, 4], [1], [2]] -> [[7], [5, 3], [2], [1, 2, 3], [9, 8, 7, 8, 9], [3, 4], [1], [2]]

```

# Answer
# , ~~76~~ ~~75~~ 71 bytes

Or **\>=4.1, 64 bytes** by replacing the word `function` with a `\`.

*Edit: -1 byte thanks to @Dominic van Essen.*

```
function(x){y[]=cumsum(c(T,y<-sapply(x,is.list))|y);tapply(x,y,unlist)}

```

Try it online!

### Explanation

```
function(x)            # take x as input
{
y[]=                   # assign to elements of y (to preserve length of y)
cumsum(                # cumulative sum of
 c(T,                  # TRUE followed by
 y<-sapply(x,is.list)) # which elements of x are lists themselves
                       # (assign this to y)
|y                     # or y
);                     # this creates a mask on the positions of lists or first non-list elements
tapply(x,y,unlist)     # apply unlist to x splitted by y
}

```
> 8 votes

# Answer
# Python 2, 68 bytes

```
lambda L:eval(re.sub("[^\d]{3,}","],[",`[[0,L,0]]`))[1:-1]
import re
```

Textually replaces every stretch of more than 2 non digit characters (i.e. everything that is not ", ") with "\],\[". A little trickery at the ends is required to guarantee balanced brackets.

Attempt This Online!

#### Old Python 2, 73 bytes

```
lambda L:[map(int,x[1::3])for x in re.findall("(?:.\d.)+",`L`)]
import re
```

Attempt This Online!

Just a stoopid regex that finds stretches of digits alternating with two arbitrary other characters (in the repr of the input).
> 7 votes

# Answer
# , 22 19 bytes

```
<@;;.1~2+./\1,#@$&>

```

Try it online!

-3 thanks to Bubbler

This is a little tricky in J, which requires boxes for heterogeneous arrays. The task becomes to "collect" iff the box contents are atoms. Contents which are already lists (either 1 items or more) should remain as single boxes.

Our strategy is then to "cut" (start a new group) unless adjacent elements are both atoms.
> 6 votes

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

```
##&@@@#&/@Split[#,#>0<#2&]&

```

Try it online!

```
          Split[#        ]  group adjacent items which
                 ,#>0<#2&     are both positive (non-lists)
##&@@@#&/@                  remove extraneous brackets

```

At times like this, it'd be nice if `@@`, `@@@` generalized to more `@`s...
> 6 votes

# Answer
# J-uby, 46 bytes

```
:slice_when+:|%([~:*&0|:!=&0]*2)|:map+:flatten

```

Try it online!

Today I learned about `slice_when`, and J-uby's `+`.

-4 from translating GB's idea.

# Ruby, 49 bytes

```
->a{a.slice_when{_1*0!=0||_2*0!=0}.map &:flatten}
```

Attempt This Online!

-6 bytes from GB.
> 6 votes

# Answer
# Japt, ~~6~~ 5 bytes

If the sub-arrays in the input could be nested another level deep in the output then the last 3 bytes could be removed.

```
ó* mc

```

Try it
> 6 votes

# Answer
# Factor \+ `splitting.extras`, ~~43~~ 42 bytes

```
[ [ array? ] split*-when [ flatten ] map ]

```

Try it online!

## Explanation

* `[ array? ] split*-when` Split on arrays (sublists) and keep the delimiters.
* `[ flatten ] map` Flatten each element. `flatten` doesn't touch arrays of depth 1 but otherwise decreases depth to 1.

```
                        ! { 1 { 2 2 } 3 { 4 4 } 5 }
[ array? ] split*-when  ! { { 1 } { { 2 2 } } { 3 } { { 4 4 } } { 5 } }
[ flatten ] map         ! { { 1 } { 2 2 } { 3 } { 4 4 } { 5 } }

```
> 5 votes

# Answer
# Ruby, 46 bytes

```
->l{l.chunk{|x|x*0}.flat_map{|a,b|a==0?[b]:b}}

```

Try it online!
> 5 votes

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

```
ŒḊ€aJŒg⁸ṁF€

```

Try it online!

```
ŒḊ€   Depth of each (1 for lists, 0 for numbers)
aJ    Replace each 1 with its index  [0 0 1 0 1 1] -> [0 0 3 0 5 6]
Œg    Group runs of equal elements [[0 0] [3] [0] [5] [6]]
⁸ṁ    Reshape the original input to this list
F€    Flatten each element (turns entries like [[1 2]] back into [1 2])

```

This approach feels elegant in theory, but a lot of bytes are wasted on `€@µ€`, so there might be saves.

Jonathan Allan saved a byte! Thanks.
> 5 votes

# Answer
# Haskell + hgl, 21 bytes

In order to do this I needed to add support for `Either` types to hgl. I was planning on doing this eventually and I don't think knowledge of this challenge influenced the way things were implemented. So this is *non-competing* for whatever that means to you.

```
fR p<tv(mst p)<+gB ø

```

This takes a `List (Either Int (List Int))` to represent a ragged array. Surprisingly we can do flip the order of the `Either` at no cost to bytes.

```
fL p<tv(mst p)<+gB ø

```

## Relfections

There are some things here that could be improved.

* `m<mst` should get it's own command. It's not used here but if I had had it this could have been 1 byte shorter:
```
fR p<sQ<m2t p<+gB ø

```
where `m2t = m<mst`. (Implemented in 871c2406)
* There needs to be a `Bitraversable` class. The whole reason we have `mst p` a very costly construct is that we need to massage the correct monoid instance onto the left hand side of the `Either`. If we had `Bitraversable`, the entire `tv(mst p)` could just be a `bisequence`.
* Other `Bifunctor` classes might have also helped here and are probably needed in the long run. `Either` isn't the only type that would benefit from this. We have other bifunctors like `(,)` and `These` which would benefit as well.
* Here I expressed ragged lists as lists of either the element or more lists. This works for ragged lists of max depth 2 fine, but it would also be possible to represent ragged lists more generally using the free monad combinator. If I had that I could have tried an approach with that, and even so I should probably have that for future challenges where the depth restriction might not exist.

Most of these basically boil down to "better bifunctor" support, so I think some of that is warranted.
> 5 votes

# Answer
# Python 2, ~~84~~ 79 bytes

```
s=[]
for x in input()+[{}]:
 if x>9:
    if s:print s
    s=x[:0];print x
 else:s+=x,
```

Attempt This Online!

-5 bytes thanks to @ovs
> 4 votes

# Answer
# Add++, 6 bytes

```
L*~,BC

```

Try it online!

~~Wow holy crap a challenge where Add++ will probably win.~~ Nevermind I tied myself with vyxal.

## Explained

```
L*~,BC
L*~,   ; a lambda that dumps its arguments onto the stack and returns the entire stack that:
    BC ; calls the built-in this challenge is all about.

```
> 3 votes

# Answer
# Vyxal 2.7.1, 6 bytes

```
ƛf⁼;Ġ•

```

Try it Online!

The link uses the latest version of vyxal (2.7.3 at the time of writing) which has a bug fix where molding no longer wraps singletons in lists, hence the extra `vf`.

## Explained

```
ƛf⁼;Ġ•
ƛf⁼;     # For each item in the input, does the flattened version equal the item? For integers, this returns a list, which does not equal the item. For lists, this just returns the list - this wouldn't work if there wasn't any depth restriction.
   Ġ    # Group on consecutive items
    •   # and mold the input to that shape

```
> 3 votes

# Answer
# Jelly, 11 bytes

Really not sure if this is optimal, it's just the first way I though of...

```
,⁻;ɗƝŻœṗ⁸F€

```

**Try it online!**

### How?

```
,⁻;ɗƝŻœṗ⁸F€ - Link: list, A
    Ɲ       - for each of the neighbours:
   ɗ        -   last three links as a dyad, f(left, right):
,           -     pair them        (e.g. [1,2] and 3 -> [[1,2],3]])
  ;         -     concatenate them (e.g. [1,2] and 3 -> [1,2,3])
 ⁻          -     are these not equal? (i.e. was either left or right a list?)
     Ż      - prefix a zero
        ⁸   - use A as the right argument of...
      œṗ    - partition right at truthy indices of left
         F€ - flatten each

```
> 3 votes

# Answer
# Retina 0.8.2, 34 bytes

```
(?<=^\[|], )[^][]+(?=, \[|]$)
[$&]

```

Try it online! Link includes test cases. Would be 32 bytes if I could be bothered to remove all of the spaces from the lists. Explanation: Simply matches sublists composed of non-lists that are between two lists or positioned at the start and/or end of the main list and wraps them in a list. Using lookarounds to anchor the match avoids having to explicitly capture the sublist thus saving a byte.

```
(?<=^\[|], )

```

Match at the beginning of the main list or after a list.

```
[^][]+

```

Match anything that isn't a list.

```
(?=, \[|]$)

```

Match at the end of the main list or before a list.

```
[$&]

```

Wrap the sublist in a list.
> 3 votes

# Answer
# Python 3, 87 bytes

```
lambda L:[[*x]for t,g in groupby(L,type)for x in[g,[g]][t==int]]
from itertools import*

```

Try it online!

Group the list by type (int or list), then wrap the int groups in list.

I thought `groupby` would be great for this job, however the `itertools` import ended up costing too many characters.

# Python 2, 84 bytes

```
def f(L,s=[]):t=s and[s];return L and[f(L[1:],s+L[:1]),t+L[:1]+f(L[1:])][L>[[]]]or t

```

Try it online!

```
f=lambda L,s=[]:L and[f(L[1:],s+L[:1]),(s and[s])+L[:1]+f(L[1:])][L[0]>9]or s and[s]

```

Try it online!

I tried to golf @pxeger's answer by using recursive function, but wasn't able to save any bytes.

These 2 functions simply loop through each element. If the current element is a digit, accumulate it in the list `s`. If the current element is a list, add the accumulated elements (`s`) if not empty to the result, followed by the current element.
> 3 votes

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

```
a=>a.flatMap(c=n=>n[0]?c=[,n]:c[0]?c.push(n)&&[]:[c=[n]])

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 6 bytes

```
.γd}€˜

```

Try it online or verify all test cases.

**Explanation:**

```
.γ     # Adjacent group-by:
  d    #  Transform every integer into a 1 (with a >=0 check)
   }€  # After the group-by: map over each group:
     ˜ #  Flatten it
       # (after which the list of lists is output implicitly as result)

```
> 3 votes

# Answer
# Burlesque, ~~13~~ 11 bytes

```
{n!z?}gB)FL

```

Try it online!

```
{
 n!   # Not for ints (if 0 then 1 else 0); most common element for lists
 z?   # Is zero
}gB   # Group by is list
)FL   # Flatten each resulting list (double groups those already as lists)

```

Since the lists are always non-zero we can get away with this hack.

An alternative is doing a list/int only op and then seeing if there's an error (e.g `tpis` transpose-iserr) unfortunately no single op I know can test for `is list`
> 3 votes

# Answer
# Charcoal, 29 bytes

```
⊞υ⟦⟧ＦＡ¿⁺ι⟦⟧⊞⊞Ｏυι⟦⟧⊞§υ±¹ι⭆¹Φυλ

```

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

```
⊞υ⟦⟧

```

Push an empty list to the result in case the first element of the input is not a list.

```
ＦＡ

```

Loop through all of the elements of the input list.

```
¿⁼ι⟦⟧«

```

If adding the empty list to the element doesn't produce an empty list, then...

```
⊞⊞Ｏυι⟦⟧

```

... the element was a list, so push it to the result, plus another empty list in case the next element of the input is not a list, otherwise...

```
⊞§υ±¹ι

```

... append the element to the last list of the result.

```
⭆¹Φυλ

```

Filter out any empty lists (e.g. from consecutive lists in the input) and pretty-print the result.
> 2 votes

# Answer
# Retina, 29 bytes

```
["[["|"], ["]"]]"L`\b[^][]+\b

```

Try it online! Link includes test cases. Explanation: Based on @loopywalt's idea. Would be 28 bytes if I could be bothered to remove all the spaces from the lists.

```
L`\b[^][]+\b

```

List all runs of digits and separators (but excluding `[]`s).

```
["[["

```

Precede the entire result with `[[`.

```
|"], ["

```

Separate each run with `], [`.

```
]"]]"

```

Suffix `]]` to the result.
> 2 votes

# Answer
# Perl 5 & probable regex polyglot, 53 bytes

```
s/(?<!\]),\[|],(?!\[)/],[/g;s/^\[+(.*[^]])]+$/[[\1]]/

```

Try it online!

First change all "`],`" or "`,[`" to "`],[`"; then make sure it's all enclosed in "`[[`...`]]`".
I forgot the second bit on my first attempt, so it seemed a bit golfier than it turned out...
> 2 votes

# Answer
# Julia 1.0, 81 bytes

```
+(x,y=[])=x>[] ? x[1] isa Int ? x[2:end]+[[y...;x[1]]] : [y;[x[1]];+x[2:end]] : y

```

Try it online!

a recursive approach

# Julia 1.0, 82 bytes

```
f(;y=[])=y
f(x::Int,X...;y=[])=f(X...;y=[[y...;x]])
f(x,X...;y=[])=[y;[x];f(X...)]

```

Try it online!

the same idea, but with multiple dispatch
> 1 votes

# Answer
# Vyxal, 12 bytes

```
⁽-ḊƛÞj∷ßw;Þf

```

Try it Online!
> 1 votes

# Answer
# Arturo, 37 bytes

```
$=>[chunk&=>[integer?&]|map=>flatten]

```

Try it
> 1 votes

---
Tags: code-golf, array, ragged-list
---


title: Natural Pi #0 - Rock

text:
# Question
Title: Natural Pi #0 - Rock
## Goal

Create a program/function that takes an input `N`, check if `N` random pairs of integers are relatively prime, and returns `sqrt(6 * N / #coprime)`.

## TL;DR

These challenges are simulations of algorithms that only require nature and your brain (and maybe some re-usable resources) to approximate Pi. If you really need Pi during the zombie apocalypse, these methods don't waste ammo! There are eight more challenges to come. Checkout the sandbox post to make recommendations.

## Simulation

**What are we simulating?** Well, the probability that two random integers are relatively prime (ie coprime or gcd==1) is `6/Pi/Pi`, so a natural way to calculate Pi would be to scoop up two buckets (or handfuls) of rocks; count them; see if their gcd is 1; repeat. After doing this a ~~couple~~ lot of times, `sqrt(6.0 * total / num_coprimes)` will tend towards `Pi`. If calculating the square-root in post-apocalyptic world makes you nervous, don't worry! There is Newton's Method for that.

**How are we simulating this?**

* Take input `N`
* Do the following `N` times:
    + Uniformly generate random positive integers, `i` and `j`
    + With `1 <= i , j <= 10^6`
    + If `gcd(i , j) == 1`: `result = 1`
    + Else: `result = 0`
* Take the sum of the `N` results, `S`
* Return `sqrt(6 * N / S)`

## Specification

* **Input**
    + Flexible, take input in any of the standard ways (eg function parameter,STDIN) and in any standard format (eg String, Binary)
* **Output**
    + Flexible, give output in any of the standard ways (eg return, print)
    + White space, trailing and leading white space is acceptable
    + Accuracy, please provide at least 4 decimal places of accuracy (ie `3.1416`)
* **Scoring**
    + Shortest code wins!

## Test Cases

Your output may not line up with these, because of random chance. But on average, you should get about this much accuracy for the given value of `N`.

```
Input     ->  Output
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??

```

# Answer
# APL, 23 bytes

```
{.5*⍨6×⍵÷1+.=∨/?⍵2⍴1e6}

```

Explanation:

* `?⍵2⍴1e6`: generate a 2-by-⍵ matrix of random numbers in the range \[1..106\]
* `1+.=∨/`: get the GCD of each pair and see how many are equal to 1. This calculates S.
* `.5*⍨6×⍵÷`: (6 × ⍵ ÷ S)0.5
> 12 votes

# Answer
# Jelly, ~~20 18~~ 16 bytes

-2 bytes thanks to @Pietu1998 (chain & use count 1s, `ċ1` in place of less than two summed `<2S`)

-2 bytes thanks to @Dennis (repeat 1e6 multiple times before sampling to avoid chaining)

```
Ḥȷ6xX€g2/ċ1÷³6÷½

```

(Extremely slow due to the random function)

How?

```
Ḥȷ6xX€g2/ċ1÷³6÷½ - Main link: n
 ȷ6              - 1e6
   x             - repeat
Ḥ                -     double, 2n
    X€           - random integer in [1,1e6] for each
       2/        - pairwise reduce with
      g          -     gcd
         ċ1      - count 1s
           ÷     - divide
            ³    - first input, n
             6   - literal 6
              ÷  - divide
               ½ - square root

```

**TryItOnline**
> 11 votes

# Answer
# Python 2, ~~143~~ ~~140~~ ~~132~~ ~~124~~ ~~122~~ ~~124~~ 122 bytes

It has been quite some time since I have tried golfing, so I may have missed something here! Will be updating as I shorten this.

```
import random as r,fractions as f
n,s=input(),0
k=lambda:r.randrange(1e6)+1
exec's+=f.gcd(k(),k())<2;'*n
print(6.*n/s)**.5

```

Test me here!

*thanks to Jonathan Allan for the two-byte save :)*
> 9 votes

# Answer
# Mathematica, ~~49~~ ~~48~~ 51 bytes

Saved one byte and fixed one bug thanks to @LegionMammal978.

```
(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&

```
> 8 votes

# Answer
# R, ~~103~~ ~~99~~ ~~95~~ ~~99~~ ~~98~~ 94 bytes

Can likely be golfed down a bit. Cut down 4 bytes due to @antoine-sac, and another 4 bytes by defining an alias for `sample`, using `^.5` instead of `sqrt`, and `1e6` instead of `10^6`. Added 4 bytes to ensure that the sampling of `i` and `j` is truly uniform. Removed one byte after I realized that `6*N/sum(x)` is the same as `6/mean(x)`. Used `pryr::f` instead of `function(x,y)` to save 4 bytes.

```
N=scan()
s=sample
g=pryr::f(ifelse(o<-x%%y,g(y,o),y))
(6/mean(g(s(1e6,N,1),s(1e6,N,1))==1))^.5

```

Sample output:

```
N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709

```
> 8 votes

# Answer
## Actually, 19 bytes

```
`6╤;Ju@Ju┤`nkΣß6*/√

```

Try it online!

Explanation:

```
`6╤;Ju@Ju┤`nkΣß6*/√
`6╤;Ju@Ju┤`n         do this N times:
 6╤;                   two copies of 10**6
    Ju                 random integer in [0, 10**6), increment
      @Ju              another random integer in [0, 10**6), increment
         ┤             1 if coprime else 0
            kΣ       sum the results
              ß      first input again
               6*    multiply by 6
                 /   divide by sum
                  √  square root

```
> 7 votes

# Answer
# MATL, 22 bytes

```
1e6Hi3$YrZ}Zd1=Ym6w/X^

```

Try it online!

```
1e6      % Push 1e6
H        % Push 2
i        % Push input, N
3$Yr     % 2×N matrix of uniformly random integer values between 1 and 1e6
Z}       % Split into its two rows. Gives two 1×N arrays
Zd       % GCD, element-wise. Gives a 1×N array
1=       % Compare each entry with 1. Sets 1 to 0, and other values to 0
Ym       % Mean of the array
6w/      % 6 divided by that
X^       % Square root. Implicitly display

```
> 7 votes

# Answer
# Scala, ~~149~~ 126 bytes

```
val& =BigInt
def f(n: Int)={math.sqrt(6f*n/Seq.fill(n){val i,j=(math.random*99999+1).toInt
if(&(i).gcd(&(j))>1)0 else 1}.sum)}

```

Explanation:

```
val& =BigInt                //define & as an alias to the object BigInt, because it has a gcd method
def f(n:Int)={              //define a method
  math.sqrt(                //take the sqrt of...
    6f * n /                //6 * n (6f is a floating-point literal to prevent integer division)
    Seq.fill(n){            //Build a sequence with n elements, where each element is..
      val i,j=(math.random*99999+1).toInt //take 2 random integers
      if(&(i).gcd(&(j))>1)0 else 1        //put 0 or 1 in the list by calling
                                          //the apply method of & to convert the numbers to
                                          //BigInt and calling its bcd method
    }.sum                   //calculate the sum
  )
}

```
> 6 votes

# Answer
# Pyth, 21 bytes

```
@*6cQ/iMcmhO^T6yQ2lN2

```

Try it online.

### Explanation

```
                Q          input number
               y           twice that
         m                 map numbers 0 to n-1:
             T                 10
            ^ 6                to the 6th power
           O                   random number from 0 to n-1
          h                    add one
        c        2         split into pairs
      iM                   gcd of each pair
     /            lN       count ones
   cQ                      divide input number by the result
 *6                        multiply by 6
@                   2      square root

```
> 6 votes

# Answer
# JavaScript (ES7), ~~107~~ ~~95~~ 94 bytes

```
n=>(n*6/(r=_=>Math.random()*1e6+1|0,g=(a,b)=>b?g(b,a%b):a<2,q=n=>n&&g(r(),r())+q(n-1))(n))**.5

```

The ES6 version is exactly 99 bytes, but the ES7 exponentiation operator `**` saves 5 bytes over `Math.sqrt`.

### Ungolfed

```
function pi(n) {
  function random() {
    return Math.floor(Math.random() * 1e6) + 1;
  }
  function gcd(a, b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
  function q(n) {
    if (n == 0)
      return 0;
    return (gcd(random(), random()) == 1 ? 1 : 0) + q(n - 1));
  }
  return Math.sqrt(n * 6 / q(n));
}

```
> 5 votes

# Answer
# PHP, ~~82~~ ~~77~~ 74 bytes

```
for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;

```

Run like this:

```
echo 10000 | php -R 'for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;' 2>/dev/null;echo

```

# Explanation

Does what it says on the tin. Requires PHP\_GMP for `gcd`.

# Tweaks

* Saved 3 bytes by using `$argn`
> 5 votes

# Answer
## Racket 92 bytes

```
(λ(N)(sqrt(/(* 6 N)(for/sum((c N))(if(= 1(gcd(random 1 1000000)(random 1 1000000)))1 0)))))

```

Ungolfed:

```
(define f
  (λ (N)
    (sqrt(/ (* 6 N)
            (for/sum ((c N))
              (if (= 1
                     (gcd (random 1 1000000)
                          (random 1 1000000)))
                  1 0)
              )))))

```

Testing:

```
(f 100)
(f 1000)
(f 100000)

```

Output:

```
2.970442628930023
3.188964020716403
3.144483068444827

```
> 5 votes

# Answer
# Perl, 64 bytes

```
sub r{1+~~rand 9x6}$_=sqrt$_*6/grep{2>gcd r,r}1..$_

```

Requires the command line option `-pMntheory=gcd`, counted as 13. Input is taken from stdin.

**Sample Usage**

```
$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772

```
> 4 votes

# Answer
# R, 94 bytes

```
N=scan();a=replicate(N,{x=sample(1e6,2);q=1:x[1];max(q[!x[1]%%q&!x[2]%%q])<2});(6*N/sum(a))^.5

```

Relatively slow but still works. Replicate N times a function that takes 2 random numbers (from 1 to 1e6) and checks if their gcd is less than 2 (using an old gcd function of mine).
> 4 votes

# Answer
## PowerShell v2+, ~~118~~ 114 bytes

```
param($n)for(;$k-le$n;$k++){$i,$j=0,1|%{Random -mi 1};while($j){$i,$j=$j,($i%$j)}$o+=!($i-1)}[math]::Sqrt(6*$n/$o)

```

Takes input `$n`, starts a `for` loop until `$k` equals `$n` (implicit `$k=0` upon first entering the loop). Each iteration, get new `Random` numbers `$i` and `$j` (the `-mi`nimum `1` flag ensure we're `>=1` and no maximum flag allows up to `[int]::MaxValue`, which is allowed by the OP since it's larger than `10e6`).

We then go into a GCD `while` loop. Then, so long as the GCD is `1`, `$o` gets incremented. At the end of the `for` loop, we do a simple `[math]::Sqrt()` call, which gets left on the pipeline and output is implicit.

Takes about 15 minutes to run with input `10000` on my ~1 year old Core i5 laptop.

### Examples

```
PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 100
3.11085508419128

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 1000
3.17820863081864

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 10000
3.16756133579975

```
> 4 votes

# Answer
# Java 8, ~~164~~ 151 bytes

```
n->{int c=n,t=0,x,y;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}

```

## Explanation

```
n->{
    int c=n,t=0,x,y;
    while(c-->0){                          // Repeat n times
        x=1+(int)(Math.random()*10e6);     // Random x
        y=1+(int)(Math.random()*10e6);     // Random y
        while(y>0)y=x%(x=y);               // GCD
        if(x<2)t++;                        // Coprime?
    }
    return Math.sqrt(6f*n/t);              // Pi
}

```

### Test Harness

```
class Main {
    public static interface F{ double f(int n); }
    public static void g(F s){
        System.out.println(s.f(100));
        System.out.println(s.f(1000));
        System.out.println(s.f(10000));
    }
    public static void main(String[] args) {
        g(
            n->{int c=n,t=0,y,x;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}
        );
    }
}

```

**Update**

* **-13** \[16-10-05\] Thanks to *@TNT* and added test harness
> 3 votes

# Answer
# Pyt, 24 bytes

```
Đ0⇹`⇹ɽɽǤ⁻?ŕ:ŕ⁺;⇹⁻łŕᵮ/6*√

```

Try it online!

```
Đ                           implicit input; Đuplicate on stack (N, i) where i is a counter
 0                          push 0 (S)
  ⇹                         swap top two items on stack
   `             ł          do... while top of stack is not 0
    ⇹                       swap top two items on stack
     ɽɽ                     get two ɽandom 32-bit integers
       Ǥ⁻?                  if the ǤCD of the two random integers is >1:
          ŕ                 ŕemove the GCD
           :ŕ⁺              otherwise ŕemove the GCD and increment S
              ;⇹⁻           either way, swap and decrement N
                 ŕ          ŕemove i (which is now 0)
                  ᵮ         cast S to a ᵮloat
                   /        N/S
                    6*√     sqrt(6*N/S); implicit print

```
> 2 votes

# Answer
# Frink,  ~~84~~ 89

```
r[]:=random[10^6]+1
g=n=eval[input[1]]
for a=1to n
g=g-1%gcd[r[],r[]]
println[(6*n/g)^.5]

```

I got lucky: **g=n=...** saves a byte over **g=0 n=...**; and **1%gcd()** gives (0,1) vs (1,0) so I can subtract. And unlucky: **n** is preassigned and **a** used because loop variables and their bounds are local and undefined outside the loop.

## Verbose

```
r[] := random[10^6] + 1     // function. Frink parses Unicode superscript!
g = n = eval[input[""]]     // input number, [1] works too
for a = 1 to n              // repeat n times
   g = g - 1%gcd[r[], r[]]  // subtract 1 if gcd(i, j) > 1
println[(6*n/g)^.5]         // ^.5 is shorter than sqrt[x], but no super ".", no ½

```
> 1 votes

# Answer
# Perl 6, ~~56~~ 53 bytes

```
{sqrt 6*$_/(1..10⁶).roll(*).map(*gcd*==1)[^$_].sum}

```

Try it online!
> 1 votes

# Answer
# AWK, 109 bytes

```
func G(p,q){return(q?G(q,p%q):p)}{for(;i++<$0;)x+=G(int(1e6*rand()+1),int(1e6*rand()+1))==1;$0=sqrt(6*$0/x)}1

```

Try it online!

I'm surprised that it runs in a reasonable amount of time for 1000000.
> 1 votes

# Answer
# Pyt, ~~37~~ 35 bytes

```
←Đ0⇹`25*⁶⁺Đ1⇹ɾ⇹1⇹ɾǤ1=⇹3Ș+⇹⁻łŕ⇹6*⇹/√

```

Explanation:

```
←Đ                                              Push input onto stack twice
  0                                             Push 0
   ⇹                                            Swap top two elements of stack
    `                      ł                    Repeat until top of stack is 0
     25*⁶⁺Đ1⇹ɾ⇹1⇹ɾ                              Randomly generate two integers in the range [1,10^6]
                  Ǥ1=                           Is their GCD 1?
                     ⇹3Ș                        Reposition top three elements of stack
                        +                       Add the top 2 on the stack
                         ⇹⁻                     Swap the top two and subtract one from the new top of the stack
                            ŕ                   Remove the counter from the stack
                             ⇹                  Swap the top two on the stack
                              6*                Multiply top by 6
                                ⇹               Swap top two
                                 /              Divide the second on the stack by the first
                                  √             Get the square root

```
> 1 votes

# Answer
# J, 27 Bytes

```
3 :'%:6*y%+/(1:=?+.?)y#1e6'

```

### Explanation:

```
3 :'                      '  | Explicit verb definition
                     y#1e6   | List of y copies of 1e6 = 1000000
            (1:=?+.?)        | for each item, generate i and j, and test whether their gcd is 1
          +/                 | Sum the resulting list
      6*y%                   | Divide y by it and multiply by six
    %:                       | Square root

```

Got pretty lucky with a `3.14157` for `N = 10000000`, which took `2.44` seconds.
> 1 votes

# Answer
# Japt, ~~23~~ 18 bytes

```
*6/UÆ2ÆÒL³öÃrjÃx)¬

```

Try it
> 1 votes

---
Tags: code-golf, math, random, pi, approximation
---