title: SuperSquares NxN

text:
# Question
Title: SuperSquares NxN
Given an integer **N** from 1-9, you must print an **N**x**N** grid of **N**x**N** boxes that print alternating 1s and **N**s, with each box having an alternating starting integer.

**Examples**

```
Input: 1
Output:

1

Input: 2
Output:

12  21
21  12

21  12
12  21

Input: 3
Output:

131  313  131
313  131  313
131  313  131

313  131  313
131  313  131
313  131  313

131  313  131
313  131  313
131  313  131

Input: 4
Output:

1414  4141  1414  4141
4141  1414  4141  1414
1414  4141  1414  4141
4141  1414  4141  1414

4141  1414  4141  1414
1414  4141  1414  4141
4141  1414  4141  1414
1414  4141  1414  4141

1414  4141  1414  4141
4141  1414  4141  1414
1414  4141  1414  4141
4141  1414  4141  1414

4141  1414  4141  1414
1414  4141  1414  4141
4141  1414  4141  1414
1414  4141  1414  4141

```

An array (of NxN arrays) or text in this format is acceptable.

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

```
#^Array[Plus,#+0{,,,}]~Mod~2&

```

Try it online!

Returns a \\$(N\times N)\times(N\times N)\\$ array.

```
  Array[    ,#+0{,,,}]          N x N x N x N array, where values are
#^                                N^
        Plus                        (sum of indices
                      ~Mod~2         mod 2)

```
> 10 votes

# Answer
# , 33 23 19 bytes

```
]^2|i.+/2|+/^:2~@i.

```

Try it online!

*Note: In TIO I added a formatting function to box each element, which is now a list of digits, to make the correctness more obvious. If you remove it, the results will still be correct but because of the way J prints by default it won't be immediately clear.*

*-10 thanks to power trick stolen from att's Wolfram answer*

* `2|...+/^:2~@i.` Creates a 0-1 checkerboard in the n x n x n dimensions of the input
* `i.+` Creates n versions of that, adding 0, 1, ... n elementwise.
* `]^` Raises input to those 0-1 matrices, creating matrices of 1 and n. This is really the end of the golf.
> 5 votes

# Answer
# Vyxal, 16 bytes

```
₀Ẏ:v꘍:£vv‡¥꘍?‹*›

```

Try it Online!

A huge mess.
> 3 votes

# Answer
# GeoGebra, 92 bytes

```
n=2
a=Zip(Zip(Mod(b-a,2),b,1…n),a,1…n)
b=(n-1)a+1
l=Zip(Zip(b+Mod(d,2)(n+1-2b),d,c),c,a)

```

Try It On GeoGebra!

`n` is the input, and `l` is the output.

The output is in the form of an array of depth 4:

* Inside the outermost list (layer 1) is the rows of the supersquare (layer 2)
* Inside the second layer is each individual matrix in the supersquare (layer 3)
* Insde the third layer is each row of a particular matrix entry in the supersquare (layer 4)

The default input is `n=2`, but you can change this to whatever input you want.

Output for `n=2` (layers labelled):

```
{{{{1, 2}, {2, 1}}, {{2, 1}, {1, 2}}}, {{{2, 1}, {1, 2}}, {{1, 2}, {2, 1}}}}
||||__4_|        |                  |                                      |
|||______3_______|                  |                                      |
||_______________2__________________|                                      |
|____________________________________1_____________________________________|

```
> 3 votes

# Answer
# Pari/GP, 48 bytes

```
n->matrix(n,,i,j,matrix(n,,k,l,n^((i+j+k+l)%2)))

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 10 bytes

```
L4ãOÉmIFIô

```

The modulo-2 exponent trick is taken from *@att*'s Mathematica answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
L           # Push a list in the range [1,(implicit) input]
 4ã         # Create all possible quartets of these values,
            # by using the cartesian power of 4
   O        # Sum each inner list
    É       # Check for each sum whether it's odd
     m      # Take the (implicit) input to the power of these 0s/1s,
            # so all 0s become 1 and all 1s become the input-digit
      IF    # Loop the input amount of times:
        Iô  #  Split the list into an input amount of parts
            # (after which the multi-dimensional matrix is output implicitly)

```
> 2 votes

# Answer
# C (gcc), ~~114~~ 111 bytes

```
k;j;i;f(n){for(i=0;n*n/++i;puts(i%n?"":"\n"))for(j=0;n/++j;putchar(32))for(k=0;n/++k;)printf("%d",i+j+k&1?:n);}

```

Try it online!

*Saved 3 bytes thanks to ceilingcat!!!*
> 2 votes

# Answer
# **Python 3, 181 bytes**

```
def s(n):
    a=f'1{n}'*n
    b,c=' '.join(([a[:n],a[1:n+1]]*n)[:n]),' '.join(([a[1:n+1],a[:n]]*n)[:n])
    return '\n\n'.join((['\n'.join(([b,c]*n)[:n]),'\n'.join(([c,b]*n)[:n])]*n)[:n])

```
1. Creates a single row for a single box
2. Makes a complete row (N rows) of alternating boxes
3. Return a string containing N rows of N-rows boxes
> 1 votes

# Answer
# PowerShell Core, 111 bytes

```
param($a)($s=1..($a*$a))|%{$b++
-join($s|%{"1$a"[($_+$b)%2]
.($g={if(!($_%$a)){$args;$b+=1-$a%2}})' '})
.$g ''}

```

Try it online!

-2 bytes thanks to mazzy!
-9 bytes thanks to mazzy again!
> 1 votes

# Answer
# Charcoal, 24 bytes

```
ＮθＥθＥθ⪫Ｅθ⭆θ∨¬﹪⁺⁺⁺ιλνπ²θ

```

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

```
Ｎθ                          Input `n` as an integer
   θ                        Input `n`
  Ｅ                         Map over implicit range
     θ                      Input `n`
    Ｅ                       Map over implicit range
        θ                   Input `n`
       Ｅ                    Map over implicit range
          θ                 Input `n`
         ⭆                  Map over implicit range and join
               ⁺⁺⁺ιλνπ       Sum of all indices
             ¬﹪       ²      Is divisible by `2`
           ∨                Logical Or
                      θ     Input `n`
      ⪫                     Join with spaces
                            Implicitly print

```
> 1 votes

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

```
f=(n,w=4,y)=>w?[...Array(n)].map(_=>f(n,w-1,y=!y)):y?n:1

```

Try it online!
> 1 votes

# Answer
# Python, 89 bytes

```
f=lambda n,s=" \n\n",p=0:s.join(j[s>"":]or f(n,s[:-1],j>"1")for j in(n*str(10+n))[p:n+p])
```

Attempt This Online!

Returns a single string. Most lines have a trailing space.
> 1 votes

# Answer
# Labra, 69 bytes

```
()[]([])
()[<><{}>]<[{}<[]>]>
<[]><<>>[](<>[])<<>>
{}(())<<><<>><<>>>

```

I've been waiting for a month and a half for a question Labra could actually compete in.

Prints as a list: \[\[\[\[1, 2\], \[2, 1\]\], \[\[2, 1\], etc...

```
For input = 3 (Which Labra receives as [3])
()[]([])                    [1,0]
()[<><{}>]                  Starting at n=1, n=[1,0][n]: [1,0,1,0,1,...]
          <[{}<[]>]>        Index with [1...input[1]]:   [0,1,0]
<[]><<>>                    Index into first line:       [1,0,1]
        [](<>[])            Put in list and add [0,1,0]: [[1,0,1],[0,1,0]]
                <<>>        Index with [0,1,0]:          [[1,0,1],[0,1,0],[1,0,1]]
{}(())                      Input (already a list) + 1:  [3,1]
      <          >          Index that with
       <>                   previous line:       [[1,0,1],[0,1,0],[1,0,1]]
         <<>>               indexed with itself: [[[0,1,0],[1,0,1],[0,1,0]],[[1,0,1],[0,1,0],...
             <<>>           twice:               [[[[1,0,1],[0,1,0],[1,0,1]],[[0,1,0],[1,0,1],[0,1,0]],...
                            giving:                      [[[[1,3,1],[3,1,3],[1,3,1]],[[3,1,3],[1,3,1],[3,1,3]],...
                            (implicit output)

```
> 1 votes

# Answer
# PHP, 129 bytes

```
for(;$a++<$n=$argn;){for($b=0;$b++<$n;){for($c=0;$c++<$n;){for($d=0;$d++<$n;)echo($a+$b+$c+$d)%2?$n:1;echo" ";}echo"
";}echo"
";}

```

I feel like there's probably a way that this could be done better with a recursive function, but I can't wrap my head around it.

Try it online!
> 0 votes

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


title: Is this a Hamiltonian cycle?

text:
# Question
Title: Is this a Hamiltonian cycle?
There is a 3x3 square block made of 1x1 square blocks, with coins in each 1x1 block, starting from top left block you want to collect all the coins and return to top left block again, if possible provide instructions to achieve this.

Rules

* From block \\$(x,y)\\$ in one step you can move right(R) to \\$(x,y+1)\\$ ,left(L) to \\$(x,y-1)\\$ ,up(U) to \\$(x-1,y)\\$ ,down(D) to \\$(x+1,y)\\$ assuming the block to which we jump is not empty and is well inside our block
* We can take only one coin at a time.
* Just after performing the jump we collect 1 coin from our new position.
* Provide the route to take in form of a string, for example like RLRRDULU...
* You should collect all coins
* If there doesn't exist a solution route print/output -1
* If there exist multiple solution you are free to provide any

> Each 1x1 block can have upto 69 coins

Examples :

```
integer in each place denotes number of coins at each block

1 1 1
1 1 1
1 2 1
here DDRUDRUULL and RRDDLUDLUU both are correct (there might be more but you can print any one of your choice)

2 4 4
2 1 3
1 2 3
here DDUURDDRUULRLRDDLRUULL is a valid answer

5 5 1
5 4 5
5 2 2
here DURLRLRLRDLDUDUDUDRLRURLRLRDUDUULL is a valid answer

2 4 2
2 1 1
1 1 2
here doesn't exist a valid solution for this case so output -1

29 7 6
8 5 4
4 28 3
here doesn't exist a valid solution for this case so output -1

4 3 5
5 4 5
3 5 2
here DUDURLRDLDRULRLRDLRLRRLRUUDUDUDUDULL is valid solution

18 8 33
16 4 38
10 28 25
here DUDUDUDUDUDUDUDUDUDUDURLRLRLRLRLRLRDLDUDURLRLRDLRLRLRLRLRLRLRLRRUUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRUULL is a valid solution

69 69 69
69 69 69
69 69 69
here doesn't exist a valid solution for this case so output -1

7 5 9
21 10 68
15 3 56
here
DUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDRRLRLRUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUUDUDUDUDUDUDUDUDUDLRLRLRLRLRLUDUDUDUDUL is a valid solution

17 65 29
16 35 69
19 68 56
here doesn't exist a valid solution for this case so output -1

```

This is so the goal is to minimize your source code with answers being scored in bytes, but feel free to showcase any of your approach, I will be glad to read all those.

Edit : As mentioned we are starting from top left block, so the number of coins in the top-left block is apparently not decremented when the game starts.Also, as mentioned coin in a block can be as big as 69 so your code should be able to give output in reasonable time(not more than 60 seconds or timeouts), you can test your code in last 3 examples, feel free to ask for some more examples.

Note that it is promised that coin exist in each cell.

Edit : releaxed IO as suggested, return a list or string representing the moves, you can use 4 distinct values for L,R,U,D. If there is no solution, return a consistent value distinct from any solution

# Answer
# Python NumPy, 245 bytes

```
def f(A,d="RL",e="DU"):
 for x in r_[:A[0]]:
  B=A[c_[[2,8,6,0],[1,5,7,3]]]-1;p="";m=A[4];t=m==sum(diff(B));B[3,0]-=x
  for b,c in B:q,r=d;y=min(c-x,b);p+=x*d+q+(u:=c-x-y)*e+y*d+q;x=b-y;d=e;e=r+q;m-=u;t&=y>-1<m
  if t:return p
from numpy import*
```

Attempt This Online!

Not very golfed yet; apologies. This takes a flat array as input and returns a path or `None` if there is none.

#### How?

It essentially walks the boundary clockwise stepping back and forth as needed to collect all the coins using the centre as a reservoir.

If we label the blocks

```
a+1 b+1 c+1
d+1  e  f+1
g+1 h+1 i+1

```

then we are looking for a nonnegative solution to

```
 a = a1+a2
 c = c1+c2
 g = g1+g2
 i = i1+i2
 e = e1+e2+e3+e4
 b = a2+e1+c1
 f = c2+e2+i1
 h = i2+e3+g1
 d = g2+e4+a1

```
> 4 votes

---
Tags: code-golf, grid, path-finding, restricted-time
---


title: Implement SKI combinator calculus

text:
# Question
Title: Implement SKI combinator calculus
This challenge is to golf an implementation of SKI formal combinator calculus.

# Definition

## Terms

`S`, `K`, and `I` are terms.

If *x* and *y* are terms then `(xy)` is a term.

## Evaluation

The following three steps will be repeated until none of them apply. In these, x, y, and z must be terms.

`(Ix)` will be replaced by `x`

`((Kx)y)` will be replaced by `x`

`(((Sx)y)z)` will be replaced by `((xz)(yz))`

# Input

A string or array, you do not have to parse the strings in the program.

The input is assumed to be a term.

If the simplification does not terminate, the program should not terminate.

# Examples

`(((SI)I)K)` should evaluate to `(KK)` (`(((SI)I)K)` \> `((IK)(IK))` \> `(K(IK))` \> `(KK)`)

The evaluation order is up to you.

This is . Shortest program in bytes wins.

# Answer
> 10 votes
# Wolfram Language, 63 bytes

```
#//.{{I,x_}->x,{{K,x_},y_}->x,{{{S,x_},y_},z_}->{{x,z},{y,z}}}&

```

Try it online!

God, I love pattern matching in Wolfram Language. Represents `(xy)` as `{x,y}` (a list of two elements).

Alternatively, if we represent `(xy)` with `x>y`, we can do it in **55 bytes**.

```
#//.{I>x_->x,(K>x_)>y_->x,((S>x_)>y_)>z_->(x>z)>(y>z)}&

```

Try it online!

# Answer
> 14 votes
# Seed, ~~5925~~ ~~5909~~ ~~5890~~ 5871 bytes

```
112 [encoded data, 5867 characters]

```

Try it online!

Made possible thanks to Abigail's `perl` answer. Inspired by HighlyRadioactive's comment.

Last iteration was golfed with bx6.

# Answer
> 11 votes
# C (gcc), ~~666~~ ~~616~~ ~~518~~ ~~483~~ 476 bytes

Who doesn't love classy, Arthur Whitney-styled code? No regular expressions involved, only clever parsing and evaluation.

PS: Yes, obviously, a few bytes can be shaved off, but for the artistic style of the obfuscated code, I'll keep them. Also for the byte count :p. Also, this code utilizes undefined behaviour in hope that nothing will break (hopefully).

@ceilingcat insisted on golfing it down from 666 bytes, so here is the golfed version:

```
#define J putchar
#define H O->a
#define G H->a
#define K O->b
typedef struct x{struct x*a,*b;int q;}Y;Y*O;z=1;A(q){O=calloc(6,4);O->q=q;}h(Y*O){Y*u;O=H&&H->q==2?z=K:H&&G&&G->q==1?z=H->b:H&&G&&G->a&&!G->a->q?u=A(3),(u->a=A(3))->a=G->b,(u->b=A(3))->a=H->b,u->a->b=u->b->b=K,z=u:(O->q==3?H=h(H),K=h(K):0,O);}r(x){Y*O;x=getchar()-73;x=x+33?A(x?x!=10:2):!getchar(K=r(H=r(O=A(3))))+O;}q(Y*O){O&&J(O->q["SKI "],O->q-3||J(41,q(K),q(H),J(40)));}main(){Y*O=r();for(;z;O=h(O))z=0;q(O);}

```

Try it online!

# Answer
> 5 votes
# Rust Macros, 480 441 bytes

```
macro_rules!s{({I$($t:tt)+}$s:tt)=>{s![{$($t)+}$s]};({K$x:tt$y:tt$($t:tt)*}$s:tt)=>{s![{$x$($t)*}$s]};({S$x:tt$y:tt$z:tt$($t:tt)*}$s:tt)=>{s![{$x$z($y$z)$($t)*}$s]};({($($c:tt)*)$($t:tt)*}{$($r:tt)*})=>{s![{$($c)*}{{$($t)*}$($r)*}]};({$($c:tt)*}{{$($t:tt)*}$($s:tt)*})=>{s![{$($c)*$($t)*}{$($s)*}]};({$($c:tt)*}{})=>{concat!($(s![$c]),*)};(($($t:tt)*))=>{concat!("(",s!($($t)*),")")};($t:tt)=>{stringify!($t)};($($t:tt)*)=>{s![{$($t)*}{}]};}

```

Try it online!

The macro takes in tokens and spits out a string literal. Input is in a flattened, left-associative format as seen on Wikipedia. Make sure there is some whitespace between combinators when using it. ungolfed:

```
macro_rules! ski {
    ({I $($t:tt)+} $s:tt) => {ski![ {$($t)+} $s]};
    ({K $x:tt $y:tt $($t:tt)*} $s:tt) => {ski![ {$x $($t)*}$s] };
    ({S $x:tt $y:tt $z:tt $($t:tt)*} $s:tt) => {ski![ {$x $z ($y $z) $($t)*} $s ]};
    ({($($c:tt)*) $($t:tt)+}{$($r:tt)*}) => {ski![ {$($c)+} {{$($t)*} $($r)*} ]};
    ({$($c:tt)*} { {$($t:tt)*} $($s:tt)* }) =>{ski![ { $($c)* $($t)* } {$($s)*} ]};
    ({$($c:tt)*} {}) => {concat!($(ski![$c]),*)};
    (($($t:tt)*)) => {concat!("(", ski!($($t)*), ")")};
    ( $t:tt) =>{stringify!($t)};
    ($($t:tt)*) => {ski![ {$($t)*} {}]};
}

```

Macros declared with `macro_rules` perform substitution based on rules similar to a regex-based substitution. The general strategy is here is an execution stack, where the instructions are being stored and executed, and a call stack, which is a stack of execution stacks and is used to traverse into functions created with `()`.

Rule number ten serves as the entry point to the macro, matching on all inputs and setting up the call and execution stacks in the form `{instructions}{}`. Note that matched pairs of brackets count as a single token, and closing brackets stop greedy matches.

Rule one implements the `I` combinator. It matches when the call stack is `I` followed by one or more instructions. It simply passes on all the matched instructions.

Rule two implements the `K` combinator. It behaves similarly to `I` but uses two arguments instead of one.

Rule three is the same but for `S`.

Rule four implements traversing into parentheses by pushing the instructions remaining on the execution stack after the parentheses onto the call stack, and replacing the call stack with the instructions in the parentheses.

Rule five catches an edge case by stopping infinite recursion when there are no instructions after the parentheses. was made redundant by an earlier bug fix and removed.

Rule six is when the execution stack can't be simplified and there are more instructions on the call stack, the instructions in the top execution stack on the call stack are concatenated on the bottom of the main execution stack.

Rule seven is when the execution stack can't be simplified and the call stack is empty. Here all the tokens are split, fed back into this macro for stringification, and concatenated.

Rule eight is where I say I lied because parenthesized groups need further evaluation because that strategy I had above evaluated these groups lazily. This rule simply feeds the instructions in the parentheses back into the original macro and concatenates parentheses around the results.

Rule nine is our terminal rule, where the tokens passed in are stringified and returned.

Assuming the recursion limit is removed and rustc gets unlimited memory this is a proof of turing completeness for rust's macro system (not the only one- rust's macros are trivially ℒ-hard, a macro that binds an inputted `$` can create and execute arbitrary macros). A playground link that lets you view the ungolfed macro's expansion steps is below.

Playground

# Answer
> 4 votes
# APL (Dyalog Unicode), ~~127~~ 124 bytes

Full program. No use of regex.

```
∊{0=≡⍵:⍵
1⌽')(',∇¨⍵}{0=d←|≡⍵:⍵
'I'≡⊃⍵:⊃⌽⍵
(2≤d)∧'K'≡⊃⊃⍵:⊃⌽⊃⍵
(3≤d)∧'S'≡⊃∊⍵:x y,⍥⊂¨⊃⌽(((s x)y)z)←⍵
∇¨⍵}⍣≡⍎⍕{3⍴''''⍵}¨@{⍵∊⎕A}⍞

```

Try it online!

The program has three distinct parts:

* Input handling
* Evaluation
* Output formatting

### Input handling

This part transforms the traditional SKI notation into a nest APL data structure.

```
      ⍎⍕{3⍴''''⍵}¨@{⍵∊⎕A}⍞

```

prompt for one line of input text
E.g. `"(((SI)I)K)"`

`@{``}`**at** locations where:

the argument characters

are members of

`⎕A` the uppercase Alphabet

`{` replace each one by:

`3⍴` a cyclical **r**eshape into length 3, of

`''''⍵` the string consisting of a quote character (`'`) and the argument character
E.g. `["(","(","(","'S'","'I'",")","'I'",")","'K'",")"]`

stringify (this forces the now nested array into a flat space-separated string)
E.g. `"((( 'S' 'I' ) 'I' ) 'K' )"`

evaluate as APL code
E.g. `[["SI","I"],"K"]`

### Evaluation

This part simplifies the data structure according to the three given rules.

```
           {0=d←|≡⍵:⍵
'I'≡⊃⍵:⊃⌽⍵
(2≤d)∧'K'≡⊃⊃⍵:⊃⌽⊃⍵
(3≤d)∧'S'≡⊃∊⍵:x y,⍥⊂¨⊃⌽(((s x)y)z)←⍵
∇¨⍵}

```

`0=``:` if 0 equals
`d←` the variable `d` which is (assigned for later use)
`|≡⍵` the absolute depth (maximum nesting level) of the argument:

return the argument as-is (this ensures the continuation of already evaluated parts)

`'I'≡``:` if `"I"` matches
`⊃⍵` the first element of the argument

`⊃⌽⍵` return the last element of the argument (lit. the first of the reversed; this implements `(Ix)``x`)

`(2≤d)∧``:` if 2 is less than or equal to the depth (`d`), AND
`'K'≡⊃⊃⍵` if `"K"` matches the first element of the first element of the argument:

`⊃⌽⊃⍵` return the last element of the first element of the argument (lit. the first of the reversed first; this implements `((Kx)y)``x`)

`(3≤d)∧``:` if 3 is less than or equal to the depth (`d`), AND
`'S'≡` if `"S"` matches
`⊃∊⍵` the first element of the **e**nlisted (flattened) argument:

`(((s x)y)z)←⍵` destructure the argument into individual variables
`⊃⌽` pick the last element (lit. first of the reversed) from that (`z`)
`x y,⍥⊂¨` pair up each of `x` and `y` with that (this implements `(((Sx)y)z)``((xz)(yz))`)

`∇¨⍵` otherwise, call self on each element of the argument

### Output Formatting

Here, we transform the data structure back into traditional SKI notation.

```
∊{0=≡⍵:⍵
1⌽')(',∇¨⍵}

```

`0=≡⍵:` if zero is equal to the depth of the argument (i.e. it is a single character)

return that as-is

`∇¨⍵` otherwise, call self on each element of the argument
`')(',` prepend `")("`
`1⌽` cyclically rotate one character from the front to the rear.

# Answer
> 3 votes
# perl -p, 135 bytes

```
1 while s/\((I)(?<T>[SKI]|\((?&T)(?&T)\))\)|\(\((K)((?&T))\)(?&T)\)|\(\(\((S)((?&T))\)((?&T))\)((?&T))\)/$1?$2:$3?$4:"(($6$8)($7$8))"/e

```

Try it online!

Just a regexp applying the three rules. Reads a string from `STDIN`, applies all the rules until there's nothing to apply, writes the result to `STDOUT`.

`(?<T>[SKI]|\((?&T)(?&T)\))` is a recursive pattern recognizing a term. The rest of the pattern is just a mechanically translation of the given rules.

# Answer
> 3 votes
# Retina 0.8.2, 171 bytes

```
{T`()`<>
<<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>)
<<$1$7<$4$7>
<<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+>
$1
<I((\w|(<)|(?<-3>>))+)>
$1
T`<>`()

```

Try it online! Explanation:

```
{`

```

Repeat the transformations until there are no more available.

```
T`()`<>
T`<>`()

```

Temporarily switch `()`s with `<>`s to avoid having to quote numerous `()`s.

```
<<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>)
<<$1$7<$4$7>

```

Process `S` operations. (The last capture includes the trailing `>` in order to avoid repeating it in the replacement.)

```
<<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+>
$1

```

Process `K` operations.

```
<I((\w|(<)|(?<-3>>))+)>
$1

```

Process `I` operations.

The `(\w|(<)|(?<-[N]>>))+` construct is an example of a .NET regex balancing group. It tries to match characters, but it's only allowed to match `>`s if it's already seen the same number of `<`s. (`N` needs to be replaced with the number of the `(<)` capturing group. As written it fails if the `<>`s aren't balanced correctly, but you can use conditional regex to check for that.)

# Answer
> 3 votes
# Wolfram Language, 44 bytes

```
s[a_][b_][c_]:=b@c//a@c;k[a_][b_]:=a;i@a_:=a

```

This defines them as actual functions in Wolfram, so `s[i][i][k]` returns `k[k]`, etc.

Try it online!

# Answer
> 2 votes
# 05AB1E, 92 bytes

```
ΔDŒʒ„)(©S¢Ë}ʒÁ®Å?y®S¢O_~}©vy"(Iÿ)"y:}®ãvy`"((Kÿ)ÿ)"yθ:}®3ãvy`"(((Sÿ)ÿ)ÿ)"yĆ1.I`"((ÿÿ)(ÿÿ))":

```

05AB1E has no regex, so uses a brute-force approach using all valid substrings. Because of this, it's extremely slow for larger test cases.

Executes in the order `(Ix)``((Kx)y)``(((Sx)y)z)`.

Try it online or verify a few more test cases.

**Explanation:**

```
Δ                        # Continue until the result no longer changes:
 D                       #  Duplicate the current string
                         #  (will use the implicit input-string in the first iteration)
  Œ                      #  Take all its substrings
   ʒ                     #  Filter those substrings by:
    „)(                  #   Push ")("
       ©                 #   Store it in variable `®` (without popping)
        S                #   Convert it to a list of characters: [")","("]
         ¢               #   Count each in the substring
          Ë              #   Check that the counts are equal for both
   }ʒ                    #  After the filter: filter once more:
     Á                   #   Rotate the substring once towards the left
      ®                  #   Push string ")(" from variable `®`
       Å?                #   Check if the rotated substring starts with this
     y                   #   Push the substring again
      ®S¢                #   Count the [")","("] again
         O_              #   Check that the sum of both counts is 0
     ~                   #   Check if either of the two was truthy
    }©                   #  After the filter: store it in variable `®` (without popping)
 v                       #  Loop over each valid substring:
  y                      #   Push the substring
   "(Iÿ)"                #   Push this string, with the `ÿ` automatically filled with
                         #   the substring
  y                      #   Push the substring again
  :                      #   Replace all "(Ia)" with "a"
 }®                      #  After the loop: push the list of valid substrings again
   ã                     #  Take all pairs of valid substrings
    v                    #  Loop over these pairs:
     y`                  #   Pop and push the pair separated to the stack
       "((Kÿ)ÿ)"         #   Push this string, with the `ÿ` automatically filled again
     yθ                  #   Pop and push only the last substring of the pair: [a,b] → b
     :                   #   Replace all "((Kb)a)" with "b"
 }®                      #  After the loop: push the list of valid substrings again
   3ã                    #  Take all triplets of valid substrings this time
     v                   #  Loop each each triplet:
      y`                 #   Pop and push the triplet separated to the stack
        "(((Sÿ)ÿ)ÿ)"     #   Push this string, with the `ÿ` automatically filled again
      y                  #   Push the current triplet again
       Ć                 #   Enclose; append its own head: [a,b,c] → [a,b,c,a]
        1.I              #   Get the 0-based 1st permutation: [a,b,c,a] → [a,b,a,c]
           `             #   Pop and push the quartet separated to the stack
            "((ÿÿ)(ÿÿ))" #   Push this string, with the `ÿ` automatically filled again
      :                  #   Replace all "(((Sc)b)a)" with "((ca)(ba))"
                         # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Scala 3 (compile-time), 113 bytes

```
type A=AnyKind
type S[X[a<:A]<:[b<:A]=>>A]=[Y[z<:A]]=>>[Z<:A]=>>X[Z][Y[Z]]
type K[X<:A]=[Y<:A]=>>X
type I[X<:A]=X

```

Try it in Scastie

It works at compile time and it doesn't exactly return a value (you can check it with `=:=` or other mechanisms), but Dotty's type system is Turing-complete (Scala 2's too, actually).

Pretty straightforward - it uses higher-kinded types and curried type lambdas like functions.

Ungolfed (and modified slightly for clarity):

```
type S =
  [X <: [a <: AnyKind] =>> [b <: AnyKind] =>> AnyKind] =>> //X is a type lambda with 2 parameters (curried) and returning a type of any kind
  [Y[z <: AnyKind]] =>> //Y is a type lambda taking one parameter and returning a type of any kind
  [Z <: AnyKind] //Z is a type of any kind
  =>> X[Z][Y[Z]] //The result of Skyz, as defined in the question
type K = [X <: AnyKind] =>> [Y <: AnyKind] =>> X
type I = [X <: AnyKind] =>> X

```

`SIIK` or `(((SI)I)K)` would be written as `S[I][I][K]`.

---

### With match types, 200 bytes

```
final class S
final class K
final class I
type R[T]=T match{case(((S,x),y),z)=>R[((x,z),(y,z))]case((K,x),y)=>R[x]case(I,x)=>R[x]case(a,b)=>R[a]match{case`a`=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}

```

*Thanks to @HTNW on SO for helping me with this*

Try it in Scastie

A term `(xy)` is represented as the tuple `(x,y)`.

---

### Using literal types, 164 bytes

```
type R[T]=T match{case((('S',x),y),z)=>R[((x,z),(y,z))]case(('K',x),y)=>R[x]case('I',x)=>R[x]case(a,b)=>R[a]match{case`a`=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}

```

Try it in Scastie

This one uses literal-based singleton types (the `Char`s `'S'`, `'K'`, and `'I'`).

---

### Slightly unethical version, 158 bytes

```
type R[T]=T match{case(((0,x),y),z)=>R[((x,z),(y,z))]case((1,x),y)=>R[x]case(2,x)=>R[x]case(a,b)=>R[a]match{case`a`=>(a,R[b])case _=>R[(R[a],R[b])]}case T=>T}

```

Same approach as above, but this time, S is the singleton type of `0`, K is `1`, and I is `2`.

Try it in Scastie

# Answer
> 2 votes
# KamilaLisp, 137 bytes

```
(defmacro f(x)(match x((a b c)(S a b c)[(tie a c b c)/ 2])((a b)(K a b)a)(a(I a)a)((a b)(a b)(tie(f a)(f b)))(x)))(def g $(iterate /= f))

```

Ungolfed:

```
;; SKI calculus implementation using KamilaLisp macros
(defmacro ski (x) (match x
    ((a b c) (S a b c) [(tie a c b c) / 2])
    ((a b)   (K a b)   a)
    ((a)     (I a)     a)
    ((a b)   (a b)     (tie (ski a) (ski b)))
    (x)
))

;; iterate /=  =>  fixed point
(def ski-red $(iterate /= ski))

;; an example expression
(println@ski-red '(S I I K))

```

# Answer
> 2 votes
# Maude, 138 bytes

```
fmod F is
sort T .
ops S K I : -> T .
op __ : T T -> T .
vars x y z : T .
eq I x = x .
eq (K x)y = x x .
eq ((S x)y)z = (x z)(y z) .
endfm

```

```
Maude> red ((S I)I)K .
reduce in F : ((S I) I) K .
rewrites: 3 in 0ms cpu (0ms real) (~ rewrites/second)
result T: K K

```

# Answer
> 1 votes
# Haskell, 83 bytes

```
data T=S|K|I|T:$T
e(x:$y)=e x!e y
e x=x
I!x=x
K:$x!_=x
S:$x:$y!z=x!z!(y!z)
x!y=x:$y

```

Try it online!

---
Tags: code-golf, math, interpreter, combinatory-logic
---


title: Patience, young "Padovan"

text:
# Question
Title: Patience, young "Padovan"
Everyone knows the Fibonacci sequence:
You take a square, attach an equal square to it, then repeatedly attach a square whose side length is equal to the largest side length of the resulting rectangle.
The result is a beautiful spiral of squares whose sequence of numbers is the *Fibonacci sequence*:

But, what if we didn't want to use squares?

If we use equilateral triangles—instead of squares—in a similar fashion, we get an equally beautiful spiral of triangles and a new sequence: the *Padovan sequence*, aka A000931:

**Task:**

Given a positive integer, \\$N\\$, output \\$a\_N\\$, the \\$N\\$th term in the Padovan sequence OR the first \\$N\\$ terms.

Assume that the first three terms of the sequence are all \\$1\\$. Thus, the sequence will start as follows: $$ 1,1,1,2,2,3,... $$

**Input:**

* Any positive integer \\$N\ge0\\$
* Invalid input does not have to be taken into account

**Output:**

* The \\$N\\$th term in the Padovan sequence **OR** the first \\$N\\$ terms of the Padovan sequence.
* If the first \\$N\\$ terms are printed out, the output can be whatever is convenient (list/array, multi-line string, etc.)
* Can be either \\$0\\$-indexed or \\$1\\$-indexed

**Test Cases:**
(0-indexed, \\$N\\$th term)

```
Input | Output
--------------
0     | 1
1     | 1
2     | 1
4     | 2
6     | 4
14    | 37
20    | 200
33    | 7739

```

(1-indexed, first \\$N\\$ terms)

```
Input | Output
--------------
1     | 1
3     | 1,1,1
4     | 1,1,1,2
7     | 1,1,1,2,2,3,4
10    | 1,1,1,2,2,3,4,5,7,9
12    | 1,1,1,2,2,3,4,5,7,9,12,16

```

**Rules:**

# Answer
> 71 votes
# Jelly, 10 bytes

```
9s3’Ẓæ*³FṀ

```

Try it online!

1-indexed. Computes the largest element of: $$\begin{bmatrix}0&0&1 \\ 1&0&1 \\ 0&1&0\end{bmatrix}^n$$ where the binary matrix is conveniently computed as: $$\begin{bmatrix}\mathsf{isprime}(0)&\mathsf{isprime}(1)&\mathsf{isprime}(2) \\ \mathsf{isprime}(3)&\mathsf{isprime}(4)&\mathsf{isprime}(5) \\ \mathsf{isprime}(6)&\mathsf{isprime}(7)&\mathsf{isprime}(8)\end{bmatrix}$$

(this is a total coincidence.)

```
9s3         [[1,2,3],[4,5,6],[7,8,9]]    9 split 3
   ’        [[0,1,2],[3,4,5],[6,7,8]]    decrease
    Ẓ       [[0,0,1],[1,0,1],[0,1,0]]    isprime
     æ*³    [[0,0,1],[1,0,1],[0,1,0]]^n  matrix power by input
        FṀ                               flatten, maximum

```

# Answer
> 34 votes
# Jelly,  ~~10 9~~  8 bytes

```
ŻṚm2Jc$S

```

A monadic Link accepting `n` (0-indexed) which yields `P(n)`.

**Try it online!**

### How?

Implements \\$P(n) = \sum\_{i=0}^{\lfloor\frac{n}2\rfloor}\binom{i+1}{n-2i}\\$

```
ŻṚm2Jc$S - Link: integer, n       e.g. 20
Ż        - zero range                  [0, 1, 2, 3, 4, ..., 19, 20]
 Ṛ       - reverse                     [20, 19, ..., 4, 3, 2, 1, 0]
  m2     - modulo-slice with 2         [20, 18, 16, 14, 12, 10,  8,  6,  4,  2,  0]  <- n-2i
      $  - last two links as a monad:
    J    -   range of length           [ 1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11]  <- i+1
     c   -   left-choose-right         [ 0,  0,  0,  0,  0,  0,  0, 28,126, 45,  1]
       S - sum                         200

```

---

And here is a "twofer"
...a totally different method also for **8 bytes** (this one is 1-indexed, but much slower):

```
3ḊṗRẎ§ċ‘ - Link: n
3Ḋ       - 3 dequeued = [2,3]
   R     - range = [1,2,3,...,n]
  ṗ      -   Cartesian power         [[[2],[3]],[[2,2],[2,3],[3,2],[3,3]],[[2,2,2],...],...]
    Ẏ    - tighten                   [[2],[3],[2,2],[2,3],[3,2],[3,3],[2,2,2],...]
     §   - sums                      [ 2,  3,   4,    5,    5,    6,     6,...]
       ‘ - increment                 n+1
      ċ  - count occurrences         P(n)

```

# Answer
> 29 votes
# Oasis, 5 bytes

**nth** term 0-indexed

```
cd+1V

```

Try it online!

**Explanation**

```
   1V   # a(0) = 1
        # a(1) = 1
        # a(2) = 1
        # a(n) =
c       #        a(n-2)
  +     #              +
 d      #               a(n-3)

```

# Answer
> 19 votes
# Haskell, 26 bytes

```
(l!!)
l=1:1:1:2:scanl(+)2l

```

Try it online! Outputs the n'th term zero-indexed.

I thought that the "obvious" recursive solution below would be unbeatable, but then I found this. It's similar to the classic golfy expression `l=1:scanl(+)1l` for the infinite Fibonacci list, but here the difference between adjacent elements is the term 4 positions back. We can more directly write `l=1:1:zipWith(+)l(0:l)`, but that's longer.

If this challenge allowed infinite list output, we could cut the first line and have 20 bytes.

**27 bytes**

```
f n|n<3=1|1>0=f(n-2)+f(n-3)

```

Try it online!

# Answer
> 12 votes
# Python 2, 30 bytes

```
f=lambda n:n<3or f(n-2)+f(n-3)

```

Try it online!

Returns the n'th term zero indexed. Outputs `True` for 1.

# Answer
> 8 votes
# Wolfram Language (Mathematica), 33 bytes

```
a@0=a@1=a@2=1;a@n_:=a[n-2]+a[n-3]

```

1-indexed, returns the nth term

Try it online!

# Answer
> 7 votes
# Octave / MATLAB, ~~35~~ 33 bytes

```
@(n)[1 filter(1,'cbaa'-98,2:n<5)]

```

Outputs the first *n* terms.

Try it online!

### How it works

Anonymous function that implements a recursive filter.

`'cbaa'-98` is a shorter form to produce `[1 0 -1 -1]`.

`2:n<5` is a shorter form to produce `[1 1 1 0 0 ··· 0]` (*n*−1 terms).

`filter(1,[1 0 -1 -1],[1 1 1 0 0 ··· 0])` passes the input `[1 1 1 0 0 ··· 0]` through a discrete-time filter defined by a transfer function with numerator coefficient `1` and denominator coefficients `[1 0 -1 -1]`.

# Answer
> 6 votes
# , 22 bytes

*-2 bytes thanks to ngn and Galen*

## closed form, 26 bytes

```
0.5<.@+1.04535%~1.32472^<:

```

Try it online!

## iterative, 22 bytes

```
(],1#._2 _3{ ::1])^:[#

```

Try it online!

# Answer
> 5 votes
# Retina, ~~47~~ 42 bytes

```
K`0¶1¶0
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*
6,G`

```

Try it online! Outputs the first `n` terms on separate lines. Explanation:

```
K`0¶1¶0

```

Replace the input with the terms for `-2`, `-1` and `0`.

```
"$+"+`.+¶(.+)¶.+$
$&¶$.(*_$1*

```

Generate the next `n` terms using the recurrence relation. `*_` here is short for `$&*_` which converts the (first) number in the match to unary, while `$1*` is short for `$1*_` which converts the middle number to unary. The `$.(` returns the decimal sum of its unary arguments, i.e. the sum of the first and middle numbers.

```
6,G`

```

Discard the first six characters, i.e. the first three lines.

# Answer
> 5 votes
# Perl 6, 24 bytes

```
{(1,1,1,*+*+!*...*)[$_]}

```

Try it online!

A pretty standard generated sequence, with each new element generated by the expression `* + * + !*`. That adds the third-previous element, the second-previous element, and the logical negation of the previous element, which is always `False`, which is numerically zero.

# Answer
> 5 votes
# Cubix, 20 bytes

This is 0 indexed and outputs the *N*th term

```
;@UOI010+p?/sqq;W.\(

```

Try it online!

Wraps onto a cube with side length 2

```
    ; @
    U O
I 0 1 0 + p ? /
s q q ; W . \ (
    . .
    . .

```

Watch it run

* `I010` \- Initiates the stack
* `+p?` \- Adds the top of stack, pulls the counter from the bottom of stack and tests
* `/;UO@` \- If counter is 0, reflect onto top face, remove TOS, u-turn, output and halt
* `\(sqq;W` \- If counter is positive, reflect, decrement counter, swap TOS, push top to bottom twice, remove TOS and shift lane back into the main loop.

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~20~~ ~~18~~ 17 bytesSBCS

This code is 1-indexed. It's the same number of bytes to get `n` items of the Padovan sequence, as you have to drop the last few extra members. It's also the same number of bytes to get 0-indexing.

**Edit:** -2 bytes thanks to ngn. -1 byte thanks to ngn

```
4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

```

Try it online!

**Explanation**

```
4⌷2(⊢,⍨2⌷+/)⍣⎕×⍳3

  ⍺(. . . .)⍣⎕⍵   This format simply takes the input ⎕ and applies the function
                   inside the brackets (...) to its operands (here marked ⍵ and ⍺).
  2(. . .+/)⍣⎕×⍳3  In this case, our ⍵, the left argument, is the array 1 1 1,
                   where we save our results as the function is repeatedly applied
                   and our ⍺, 2, is our right argument and is immediately applied to +/,
                   so that we have 2+/ which will return the pairwise sums of our array.
       2⌷          We take the second pairwise sum, f(n-2) + f(n-3)
    ⊢,⍨            And add it to the head of our array.
4⌷                 When we've finished adding Padovan numbers to the end of our list,
                   the n-th Padovan number (1-indexed) is the 4th member of that list,
                   and so, we implicitly return that.

```

# Answer
> 4 votes
# Python 2, ~~56~~ 48 bytes

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

```

Try it online!

Returns nth value, 0-indexed.

# Answer
> 4 votes
# 05AB1E, 7 bytes

Thanks to Kevin for -1 byte!

```
Ì1λè₂₃+

```

Try it online!

### Previous version: 05AB1E, 8 bytes

```
1Ð)λ£₂₃+

```

Try it online!

Bear with me, I haven't golfed in a while. I wonder if there's a shorter substitute for `1Ð)` which works in this case (I've tried `1D)`, `3Å1` etc. but none of them save bytes). Outputs the first \\$n\\$ terms of the sequence. Or, without the `£`, it would output an infinite stream of the terms of the sequence.

```
1Ð)λ£₂₃+ | Full program.
1Ð)      | Initialize the stack with [1, 1, 1].
   λ     | Begin the recursive generation of a list: Starting from some base case,
         | this command generates an infinite list with the pattern function given.
    £    | Flag for λ. Instead of outputting an infinite stream, only print the first n.
     ₂₃+ | Add a(n-2) and a(n-3).

```

# Answer
> 4 votes
# K (ngn/k), ~~24~~ 20 bytes

-4 bytes thanks to ngn!

```
{$[x<3;1;+/o'x-2 3]}

```

Try it online!

0-indexed, first N terms

# Answer
> 4 votes
# x86 32-bit machine code, 17 bytes

```
53 33 db f7 e3 43 83 c1 04 03 d8 93 92 e2 fa 5b c3

```

Disassembly:

```
00CE1250 53                   push        ebx
00CE1251 33 DB                xor         ebx,ebx
00CE1253 F7 E3                mul         eax,ebx
00CE1255 43                   inc         ebx
00CE1256 83 C1 04             add         ecx,4
00CE1259 03 D8                add         ebx,eax
00CE125B 93                   xchg        eax,ebx
00CE125C 92                   xchg        eax,edx
00CE125D E2 FA                loop        myloop (0CE1259h)
00CE125F 5B                   pop         ebx
00CE1260 C3                   ret

```

It is 0-indexed. The initialization is conveniently achieved by calculating eax * 0. The 128-bit result is 0, and it goes in edx:eax.

At the beginning of each iteration, the order of the registers is ebx, eax, edx. I had to choose the right order to take advantage of the encoding for the `xchg eax` instruction - 1 byte.

I had to add 4 to the loop counter in order to let the output reach `eax`, which holds the function's return value in the `fastcall` convention.

I could use some other calling convention, which doesn't require saving and restoring `ebx`, but `fastcall` is fun anyway :)

# Answer
> 3 votes
# Jelly, 11 bytes

```
5B+Ɲ2ị;Ʋ⁸¡Ḣ

```

Try it online!

0-indexed.

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

Implements the recursive definition of A000931, but with \\$a(0)=a(1)=a(2)=1\\$, as specified in the challenge.

Returns the \\$N\\$th term, 0-indexed.

```
f=n=>n<3||f(n-2)+f(n-3)

```

Try it online!

# Answer
> 3 votes
# Lua 5.3, ~~49~~ 48 bytes

```
function f(n)return n<4 and 1or f(n-2)+f(n-3)end

```

Try it online!

Vanilla Lua doesn't have coercion of booleans to strings (even `tonumber(true)` returns `nil`), so you have to use a pseudo-ternary operator. This version is 1-indexed, like all of Lua. The `1or` part has to be changed to `1 or` in Lua 5.1, which has a different way of lexing numbers.

# Answer
> 3 votes
# Ruby, 26 bytes

```
f=->n{n<3?1:f[n-2]+f[n-3]}

```

Try it online!

# Answer
> 2 votes
# Japt `-N`, 12 bytes

```
<3ªßUµ2 +ß´U

```

Try it

# Answer
> 2 votes
# Japt, ~~12~~ 9 bytes

Returns the `n`th term, 1-indexed.

```
@1gZÔä+}g

```

Try it

```
@1gZÔä+}g     :Implicit input of integer U
        g     :Starting with the array [0,1] do the following U times, pushing the result to the array each time
@             :  Pass the array through the following function as Z
 1g           :    Get the element at 0-based index 1, with wrapping, from the following
   ZÔ         :    Reverse Z
     ä+       :    Get the sums of each consecutive pair of elements
       }      :  End function
              :Implicit output of the last element in the array

```

# Answer
> 2 votes
# TI-BASIC (TI-84), 34 bytes

```
[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1

```

0-indexed \\$N\\$th term of the sequence.

Input is in `Ans`.
Output is in `Ans` and is automatically printed out.

~~I figured that enough time had passed, plus multiple answers had been posted, of which there were many which out-golfed this answer.~~

**Example:**

```
0
               0
prgmCDGFD
               1
9
               9
prgmCDGFD
               9
16
              16
prgmCDGFD
              65

```

**Explanation:**

```
[[0,1,0][0,0,1][1,1,0]]^(Ans+5:Ans(1,1      ;full program (example input: 6)

[[0,1,0][0,0,1][1,1,0]]                     ;generate the following matrix:
                                            ; [0 1 0]
                                            ; [0 0 1]
                                            ; [1 1 0]
                       ^(Ans+5              ;then raise it to the power of: input + 5
                                            ; [4  7 5]
                                            ; [5  9 7]
                                            ; [7 12 9]
                               Ans(1,1      ;get the top-left index and leave it in "Ans"
                                            ;implicitly print Ans

```

# Answer
> 2 votes
# Pyth, 16 bytes

```
L?<b3!b+y-b2y-b3

```

This defines the function `y`. Try it here!

Here's a more fun solution, though it's 9 bytes longer; bytes could be shaved though.

```
+l{sa.pMf.Am&>d2%d2T./QY!

```

This uses the definition given by David Callan on the OEIS page: "a(n) = number of compositions of n into parts that are odd and \>= 3." Try it here! It takes input directly instead of defining a function.

# Answer
> 2 votes
# Perl 5, 34 bytes

```
sub f{"@_"<3||f("@_"-2)+f("@_"-3)}

```

Try it online!

# Answer
> 2 votes
# R + pryr, ~~38~~ 36 bytes

Zero-indexed recursive function.

```
f=pryr::f(`if`(n<3,1,f(n-2)+f(n-3)))

```

Try it online!

Thanks to @Giuseppe for pointing out two obviously needless bytes.

# Answer
> 2 votes
# Java, 41 bytes

Can't use a lambda (runtime error). Port of this Javascript answer

```
int f(int n){return n<3?1:f(n-2)+f(n-3);}

```

TIO

# Answer
> 2 votes
# 05AB1E, 8 bytes

This implementation of the binomial formula: `a(n) = Sum_{k=0..floor(n/2)} binomial(k+1, n-2k)` is interestingly the same length as the recursive solution.

```
;Ý·-āscO

```

Try it online!

**Explanation**

```
;Ý        # push [0 ... floor(input/2)]
  ·       # double each
   -      # subtract each from input
    ā     # push range [1 ... len(list)]
     s    # swap
      c   # choose
       O  # sum

```

# Answer
> 2 votes
# C (clang), ~~41~~ 33 bytes

```
a(i){return i<3?1:a(i-2)+a(i-3);}

```

Try it online!

# Answer
> 2 votes
# Husk, ~~9~~ 8 bytes

```
↑ƒ(+ḋ7Ẋ+

```

Try it online!

There ~~*might* be~~ is a shorter version using `fix`. -1 from Leo!

# Answer
> 2 votes
# Perl 5, ~~38~~ 36 bytes (full program)

*-2 bytes thanks to dingledooper*

By the challenge's specification, this is \\$1\\$-indexed:

```
1x<>.1~~/^(...?)*$(?{++$i})\1/;say$i

```

Try it online!

This uses the same trick as Fibonacci function or sequence, with the 1 byte modification of inserting an extra `.` in the regex, so that the number of ordered partitions as a sum of the numbers \\$2\\$ and \\$3\\$ is counted. For example, \\$11\\$ can be represented \\$9\\$ ways:

```
2+2+2+2+3
2+2+2+3+2
2+2+3+2+2
2+3+2+2+2
3+2+2+2+2
2+3+3+3
3+2+3+3
3+3+2+3
3+3+3+2

```

This tells us that the term at index \\$11-1\\$ (in the \\$1\\$-indexing requested by the challenge) is \\$9\\$.

In the form of a full program, Xcali's recursive answer is longer at **43 bytes**:

```
sub f{"@_"<3||f("@_"-2)+f("@_"-3)}say f(<>)

```

Try it online!

But the most mathematically consistent indexing for the Padovan sequence would have it start with \\$0,1,0,1,1,1,2,2,3...\\$ at index \\$0\\$, based on the Fibonacci indexing in which \\$0,1,1,2,3,5,8...\\$ starts at index \\$0\\$. By this challenge's specification that would be “\\$3\\$-indexing”. The regex backtracking method golfs best with “\\$2\\$-indexing”, and the recursive method golfs best with “\\$0\\$-indexing”.

With “\\$2\\$-indexing” and higher, **~~1~~ 0** bytes must be taken to coerce the return value into an integer, because the term at index \\$1\\$ is \\$0\\$, and `++$i` would never get executed – which would leave it with a non-value if it were not initialized. This can be golfed by adding the boolean falsey return value of the regex match operator (which gets coerced to the integer `0`) to `$i`, though Perl gives the runtime warning `Use of uninitialized value $i in addition (+)` if this happens with `use warnings` enabled.

Something similar happens with the “\\$2\\$-indexing” recursive version, requiring the use of a `^1` XOR which gives the warning `Possible precedence problem on bitwise ^ operator` with `use warnings` enabled.

\\$0\\$-indexing”: `1x<>.11~~/^(...?)*$(?{++$i})\1/;say$i` **37 bytes** \- Try it online!
\\$1\\$-indexing”: `1x<>.1~~/^(...?)*$(?{++$i})\1/;say$i` **36 bytes** \- Try it online!
\\$2\\$-indexing”: `$_=1x<>;say/^(...?)*$(?{++$i})\1/+$i` **36 bytes** \- Try it online!
\\$3\\$-indexing”: `$_=1x<>;say/^.(...?)*$(?{++$i})\1/+$i` **37 bytes** \- Try it online!

\\$0\\$-indexing”: `sub f{"@_"<3||f("@_"-2)+f("@_"-3)}say f(<>)` **43 bytes** \- Try it online!
\\$1\\$-indexing”: `sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}say f(<>)` **48 bytes** \- Try it online!
\\$2\\$-indexing”: `sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}say f(<>)` **51 bytes** \- Try it online!
\\$3\\$-indexing”: `sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}say f(<>)` **48 bytes** \- Try it online!

# Perl 5 `-n`, ~~43~~ ~~42~~ 40 bytes (full program with implied loop)

It is longer when required to be executed in a loop, due to the need to initialize `$i` each time, but this can be golfed to cost only 4 bytes:

```
1x$_.1~~/^(...?)*$(?{++$i})\1/;$i=!say$i

```

Try it online!

Alternative **40 bytes** (doesn't work for “\\$2\\$-indexing” and higher):

```
1x$_.1~~/^(...?)*$(?{++$i})\1/;$i%=say$i

```

Try it online!

\\$0\\$-indexing”: `1x$_.11~~/^(...?)*$(?{++$i})\1/;$i=!say$i` **41 bytes** \- Try it online!
\\$1\\$-indexing”: `1x$_.1~~/^(...?)*$(?{++$i})\1/;$i=!say$i` **40 bytes** \- Try it online!
\\$2\\$-indexing”: `$i=0;1x$_~~/^(...?)*$(?{++$i})\1/;say$i` **39 bytes** \- Try it online!
\\$3\\$-indexing”: `$i=0;1x$_~~/^.(...?)*$(?{++$i})\1/;say$i` **40 bytes** \- Try it online!

\\$0\\$-indexing”: `sub f{"@_"<3||f("@_"-2)+f("@_"-3)}say f($_)` **43 bytes** \- Try it online!
\\$1\\$-indexing”: `sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}say f($_)` **48 bytes** \- Try it online!
\\$2\\$-indexing”: `sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}say f($_)` **51 bytes** \- Try it online!
\\$3\\$-indexing”: `sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}say f($_)` **48 bytes** \- Try it online!

# Perl 5 `-pl`, ~~43~~ ~~42~~ 40 bytes (full program with implied loop)

The initialization can be golfed in this form as well (but this doesn't work for “\\$2\\$-indexing” and higher):

```
1x$_.1~~/^(...?)*$(?{++$i})\1/;$i%=$_=$i

```

Try it online!

\\$0\\$-indexing”: `1x$_.11~~/^(...?)*$(?{++$i})\1/;$i%=$_=$i` **41 bytes** \- Try it online!
\\$1\\$-indexing”: `1x$_.1~~/^(...?)*$(?{++$i})\1/;$i%=$_=$i` **40 bytes** \- Try it online!
\\$2\\$-indexing”: `$i=0;1x$_~~/^(...?)*$(?{++$i})\1/;$_=$i` **39 bytes** \- Try it online!
\\$3\\$-indexing”: `$i=0;1x$_~~/^.(...?)*$(?{++$i})\1/;$_=$i` **40 bytes** \- Try it online!

\\$0\\$-indexing”: `sub f{"@_"<3||f("@_"-2)+f("@_"-3)}$_=f($_)` **42 bytes** \- Try it online!
\\$1\\$-indexing”: `sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}$_=f($_)` **47 bytes** \- Try it online!
\\$2\\$-indexing”: `sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}$_=f($_)` **50 bytes** \- Try it online!
\\$3\\$-indexing”: `sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}$_=f($_)` **47 bytes** \- Try it online!

# Perl 5, ~~47~~ 45 bytes (anonymous function with no side effects)

```
sub{my$i;1x"@_".1~~/^(...?)*$(?{++$i})\1/;$i}

```

Try it online! \- displays terms \\$1\\$ through \\$46\\$ with “\\$1\\$-indexing”

As a function already, Xcali's **34 byte** answer is shorter, although significantly slower:

Try it online! \- displays terms \\$0\\$ through \\$45\\$ with “\\$0\\$-indexing”

\\$0\\$-indexing”: `sub{my$i;1x(2+pop)~~/^(...?)*$(?{++$i})\1/;$i}` **46 bytes** \- Try it online!
\\$1\\$-indexing”: `sub{my$i;1x"@_".1~~/^(...?)*$(?{++$i})\1/;$i}` **45 bytes** \- Try it online!
\\$2\\$-indexing”: `sub{my$i;(1x pop)=~/^(...?)*$(?{++$i})\1/+$i}` **45 bytes** \- Try it online!
\\$3\\$-indexing”: `sub{my$i;(1x pop)=~/^.(...?)*$(?{++$i})\1/+$i}` **46 bytes** \- Try it online!

\\$0\\$-indexing”: `sub f{"@_"<3||f("@_"-2)+f("@_"-3)}` **34 bytes** \- Try it online!
\\$1\\$-indexing”: `sub f{"@_"<3?pop>0:f("@_"-2)+f("@_"-3)}` **39 bytes** \- Try it online!
\\$2\\$-indexing”: `sub f{"@_"<3?pop==1^1:f("@_"-2)+f("@_"-3)}` **42 bytes** \- Try it online!
\\$3\\$-indexing”: `sub f{"@_"<3?1&pop:f("@_"-2)+f("@_"-3)}` **39 bytes** \- Try it online!

# Perl 6, ~~27~~ ~~26~~ ~~25~~ 24 bytesSBCS (anonymous function)

```
{+m:ex/^(...?)*$/}o¹x*+2

```

Try it online!

Thanks to Jo King for extending the idea to this language.

\\$0\\$-indexing”: `{+m:ex/^(...?)*$/}o¹x*+2` **24 bytes** \- Try it online!
\\$1\\$-indexing”: `{+m:ex/^(...?)*$/}o¹x*+1` **24 bytes** \- Try it online!
\\$2\\$-indexing”: `{+m:ex/^(...?)*$/}o¹x*` **22 bytes** \- Try it online!
\\$3\\$-indexing”: `{+m:ex/^.(...?)*$/}o¹x*` **23 bytes** \- Try it online!

Sean's non-regex answer (shown below adapted to different indexings) is still shorter, but only by 2 bytes (though it's longer at “\\$3\\$-indexing” and ties at “\\$2\\$-indexing”). Fibonacci is not even close.

\\$0\\$-indexing”: `{(1,1,1,*+*+!*…*)[$_]}` **22 bytes** \- Try it online!
\\$1\\$-indexing”: `{(0,1,1,*+*+!*…*)[$_]}` **22 bytes** \- Try it online!
\\$2\\$-indexing”: `{(1,0,1,*+*+!*…*)[$_]}` **22 bytes** \- Try it online!
\\$3\\$-indexing”: `{(0,1,~0,*+*+!*…*)[$_]}` **23 bytes** \- Try it online!
\\$3\\$-indexing”: `{(0,1,0,*+*+*%1…*)[$_]}` **23 bytes** \- Try it online!
\\$3\\$-indexing”: `{(0,1,0,*+*+*×0…*)[$_]}` **23 bytes** \- Try it online!

Note that the same regex method used in the Perl 5 versions can also be directly ported to Perl 6:

\\$0\\$-indexing”: `{my$i;¹x$_+2~~/^(...?)*${++$i}./;$i}` **36 bytes** \- Try it online!
\\$1\\$-indexing”: `{my$i;¹x$_+1~~/^(...?)*${++$i}./;$i}` **36 bytes** \- Try it online!
\\$2\\$-indexing”: `{my$i;¹x$_~~/^(...?)*${++$i}./;+$i}` **35 bytes** \- Try it online!
\\$3\\$-indexing”: `{my$i;¹x$_~~/^.(...?)*${++$i}./;+$i}` **36 bytes** \- Try it online!

# Answer
> 2 votes
# , 14 bytes

```
(>:%1-*:*>:)t.

```

Try it online!

Asks for the (input)-th Taylor coefficient of the generating function $$x \mapsto \frac{x+1}{1-x^2\cdot(x+1)}.$$

(The parenthesized train `>:` `%` `1` `-` `*:` `*` `>:` is read as: “increment over one minus square times increment.”)

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 34 bytes

```
int f(int g)=>g<3?1:f(g-2)+f(g-3);

```

Try it online!

# Answer
> 1 votes
# C++ (gcc), ~~81~~ ~~75~~ 74 bytes

-6 bytes to small golfing

-1 byte thanks to @ceilingcat

```
int a(int n){int a=1,b=1,c=1,d,i=2;for(;i++<n;c=d)d=a+b,a=b,b=c;return c;}

```

Try it online!

Simple function to compute the values iteratively. No loop occurs for `n<3`, so the first cases default to the initial 1.

# Answer
> 1 votes
# Gaia, ~~16~~ ~~14~~ 12 bytes

```
7b@⟨ṇ;(++⟩ₓ(

```

Try it online!

0-based index. Only holds the last 3 values.

```
7b		| push [1 1 1]
  @		| push input
   ⟨     ⟩ₓ	| do the following that many times (0 times if 0 or less)
    ṇ		| pop the first element and leave the rest below
     ;		| copy from below
      (		| take the first element
       +	| add the two together
	+	| and concatenate to the list. End loop.
	   (	| finally, take the first element

```

# Gaia, 14 bytes

```
ø@⟨18b+ₔ…Σ¦⟩ₓ<

```

Try it online!

Returns the first `n` elements, 1-based index. `<` could also be `E` to get just the `n`th element.

Uses the identity from the OEIS page \\$a(n+5)=\sum\limits\_{i=1}^n a(i)\\$.

This is quite inefficient, as it repeatedly copies the first few lists.

```
ø		| push empty list
 @⟨	   ⟩ₓ	| do (input) number of times:
   18b		| push [1 0 0 1 0] by converting 18 to bits
      +ₔ	| append cumulative list (initially empty) to end of bits
	…Σ¦	| and calculate the cumulative sums, replacing old cumulative list
	     <	| finally, take the first (input) elements of cumulative sums

```

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

```
If[#<3,1,#0[#-2]+#0[#-3]]&

```

Try it online!

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

0-indexed.

```
f(n)=if(n<3,1,f(n-2)+f(n-3))

```

Try it online!

---

# Pari/GP, 35 bytes

1-indexed.

```
n->Vec((1+x+O(x^n))/(1-x^2-x^3))[n]

```

Try it online!

The generating function of the sequence is \\$\frac{1+x}{1-x^2-x^3}\\$.

# Answer
> 1 votes
# dc, ~~50~~ 48 bytes

```
 2+sx3si1d:a[liddddd3-;ar2-;a+r:a1+silx>M]dsMx;ap

```

It's 1-indexed! Try it online! Previous version!

Golfed off two bytes by only populating the first element in the array.

Probably can be golfed a bit more, but it's tricky because you have to a: seed the initial values, and b: use arrays since `dc` doesn't let you pick from arbitrary stack positions.

`2+sx3si` adds two to the user input at top of stack into register `x`, and starts an increment counter register `i` at 3. We have to add two because the array is now populated in such a way that it's 3-indexed.

`1d:a` populates element 1 of array `a` with a 1. The 50 byte version populated elements 1 and 2 with `1d2:a1:a`. The mechanism works with just the single element populated, however, it just takes a little while to get enough 1s in place such as to start the sequence. Even though going from `1d2:a1:a` to `1d:a` saves 4 bytes, we now have to `2+` our input. Still two bytes saved. Initially, I thought I had to seed the first three elements with `1dd3:a2:a1:a` (+4 bytes), but... `dc` returns a zero for any unassigned array element, and if we start macro `M` (below) by creating the third element, adding 0 to 1... we're good to go.

Macro `M`:

`liddddd` loads register `i` and makes a bunch of copies of it. We subtract 3 from one of these, get the corresponding element from `a` and then swap top of stack. Subtract 2, get the corresponding element from `a`, add the two elements to get our new value, then swap the top of stack. At this point, `:a` puts our new value into `a` at position `i`. `1+si` to increment `i`, and `lx>M` to keep running `M` until we hit our target (stored in `x`). `dsMx` runs `M`, and once `M` has finished running, the stack should be full of leftover `i` values, the topmost of which is the last one we made. Load the value from `a` with `;a` and print it with `p`.

# Answer
> 1 votes
# Brain-Flak, 96 bytes

```
(()()()){({}[()]<{({}[()])<>(())(<>)}{}>)}{}{({}[()]<<>({}<(({}(({}))<>)<>[{}])>)<>({}<>)<>>)}<>

```

Try it online!

# Answer
> 1 votes
# Clojure, 46 bytes

```
(defn f[n](if(< n 3)1(+(f(- n 2))(f(- n 3)))))

```

Just for completeness sake :)

Try it online!

# Answer
> 1 votes
# CJam, 16 bytes

```
qi7Yb{((_j\(j+}j

```

0-indexed, returns nth item
Try it online!

Explanation: It uses a recursive function to add a(n-2) to a(n-3) to find a(n).

```
qi7Yb{((_j\(j+}j
qi               - reads input as integer
  7Yb            - push an array of [1, 1, 1]. It does this by pushing 7, then
                   turning it into binary.
     {        }j - define a recursive function to calculate a(n), where the
                   predefined values for n = 0,1,2 are 1,1,1
      ((         - subtract 2 from n | Stack: n-2
        _        - duplicate | Stack: n-2, n-2
         j       - find a(n-2) | Stack: n-2, a(n-2)
          \      - swap the top two items in the stack | Stack: a(n-2), n-2
           (     - decrement | Stack: a(n-2), n-3
            j    - find a(n-3) | Stack: a(n-2), a(n-3)
             +   - add, finding a(n)
                 - implicit output

```

In pseudocode:

```
read input as integer
define padovan_sequence(n):
    return padovan_sequence(n-2) + padovan_sequence(n-3)
print(padovan_sequence(n))

```

# Answer
> 1 votes
# Stax, 7 bytes

```
ÉKΦΘÄO¢

```

Run and debug it

# Answer
> 1 votes
# , 17 bytes

```
$[2&(],_2{+/\)3##

```

Try it online!

```
                #   length of input, 1
              3#    1,1,1
 [                     N times:
  2       +/\          sums of length 2 windows
       _2{             pick second to last
     ],                append
$                   take N
{                   (or pick Nth term for same score)

```

# Answer
> 1 votes
# x86, 19 bytes

```
f:	xor eax, eax
.a:	push edi
.a2:	sub edi, 3
	jc  .l
	call .a
	inc edi
	jmp .a2
.l:	inc eax
	pop edi
	ret

```

Try it online!

# Answer
> 1 votes
# Julia, 21 bytes

```
!n=n<3||!(n-2)+!(n-3)

```

Try it online!

# Answer
> 1 votes
# Arn `-al`, 9 bytes

I'm not particularly sure why this works...

```
w®¦€•3=⁺■

```

Try it! 1-indexed, outputs the nth term

# Explained

Unpacked: `1 1 1{#+}->` Exploits Arn's weird precedence bugs to save a byte. A more "normal" version would have `{_ _+}` as the block or something like `{#_+}` (as `#` is a suffix)

```
[ ... ]      Implied by `-a` flag
  1          First entry = 1
  1          Second entry = 1
  1          Third entry = 1
    {        Other entries determined by
        _      a[n - 1], throwaway implied
      #        This implies the `_` before it while allowing + to not have it b/c bugs
        _    a[n - 2], implied
      +      Plus
        _    a[n - 3]
    }        Return this last value
  ->         Sequence has length of
    _        STDIN; implied
         Then, get last item

```

# Answer
> 1 votes
# Vyxal, 8 bytes

```
‡_+T⁺
ḞẎ

```

Try it Online! Woo, we beat Jelly!

```
‡  T      # A triadic lambda function taking three arguments...
 _+       # Pop the first and add the next two
    ⁺NL   # With the initial vector [1, 1, 1]...
       Ḟ  # Create an infinite generator that calls the function with the last <arity> (3 in this case) arguments and appends that to the list.
        Ẏ # Get the first n items.

```

NL in the explanation represents a literal newline. In Vyxal,  takes the index of the next character in the Vyxal codepage and adds 101 to it. As Vyxal's codepage is aligned with ASCII, a newline is #10, so the number 111 can be represented by  and a newline.

# Answer
> 1 votes
# tinylisp, 63 bytes

```
(d f(q((x y z u)(i u(f y z(a x y)(s u 1))x
(d g(q((x)(f 1 1 1 x

```

Try it online!

-10 from dlosc

# Answer
> 0 votes
# Groovy, 22 bytes

```
a->a<3?1:f(a-2)+f(a-1)

```

Try it online!

# Answer
> 0 votes
# C# (.NET Core), 144 bytes, 0-indexed.

```
using C=System.Console;class A{static void Main(){int i=int.Parse(C.ReadLine());C.Write(p(i));}static int p(int i){return i<3?1:p(i-2)+p(i-3);}}

```

Try it online!

Quite frankly, this is not my best work ever. But here it is.

# Answer
> 0 votes
# Excel, ~~79 77~~ 65 bytes

*-2 bytes, sequence didn't need to be horizontal*

*-12 bytes, change lower bound to 1 and handle errors from COMBIN*

```
=LET(k,A1+2,m,SEQUENCE(INT(k/2)),SUM(IFERROR(COMBIN(m,k-2*m),0)))

```

It uses the equation \\$P(k-2)=\sum\_{m=\lceil k/3\rceil}^{\lfloor k/2\rfloor}{m \choose k-2m}.\\$

```
=LET(
k=A1+2                        'k = N + 2
m=SEQUENCE(INT(k/2))          'm = 1 .. floor k/2
SUM(IFERROR(COMBIN(m,k-2*m))) 'Sum of combinations (m, k-2m)

```

# Answer
> 0 votes
# MMIX, 40 bytes (10 instrs)

(jxd)

```
00000000: e3010000 e3020001 e3030001 22ff0102  ẉ¢¡¡ẉ£¡¢ẉ¤¡¢"”¢£
00000010: c1010200 c1020300 c103ff00 27000001  Ḋ¢£¡Ḋ£¤¡Ḋ¤”¡'¡¡¢
00000020: 5b00fffb f8020000                    [¡”»ẏ£¡¡

```

(disassembly and explanation)

```
pado    SETL $1,0       // a(4) - pad(0) except that doesn't work properly
        SETL $2,1       // a(5) - pad(1)
        SETL $3,1       // a(6) - pad(2)
0H      ADDU $255,$1,$2 // a(n + 3) = a(n) + a(n + 1)
        SET  $1,$2      // shift down
        SET  $2,$3
        SET  $3,$255
        SUBU $0,$0,1    // one cycle done
        PBNZ $0,0B      // return if done
        POP  2,0

```

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


title: Word Search Helper

text:
# Question
Title: Word Search Helper
I've been doing word searches recently, and I thought it would be *so* much easier if all of the words read left-to-right. But rewriting all the lines takes a lot of effort! So I'm enlisting code golfers to help.

(Disclaimer: The above story may or may not be remotely accurate.)

Your code will take a rectangular grid and output all of the lines through it in both directions.

The output must contain all 8 rotations of the grid (cardinals and main diagonals), 'read off' top to bottom, left to right. (This means that every "row" will be duplicated - once forwards, and once backwards.)

The line divisions can either be a space or a line break. If you choose spaces, the grid rotation divisions must be line breaks; otherwise, the grid rotation divisions must be two line breaks.

**Example input** (taken as an array of characters, multiline string, or other reasonable format)

```
ABCDE
FGHIJ
KLMNO
PQRST

```

**Example output** (using the first option for divisions)

```
ABCDE FGHIJ KLMNO PQRST
E DJ CIO BHNT AGMS FLR KQ P
EJOT DINS CHMR BGLQ AFKP
T OS JNR EIMQ DHLP CGK BF A
TSRQP ONMLK JIHGF EDBCA
P QK RLF SMGA TNHB OIC JD E
PKFA QLGB RMHC SNID TOJE
A FB KGC PLHD QMIE RNJ SO T

```

The order of the rotations "read off" does not matter as long as all eight cardinals and primary intercardinals are done once.

This is , so shortest code wins. Standard loopholes apply.

# Answer
> 5 votes
## Python 3, 181 bytes

```
def f(s):
 for k in [1,0]*4:
  b=list(zip(*[([' ']*(len(s)-1-n)*k+list(i)+[' ']*n*k)[::-1] for n,i in enumerate(s)]))
  print([' '.join(i).replace(' ','') for i in b])
  if k==0:s=b

```

## Explanation

```
def f(s):
 for k in [0]*4:                  # loop 4 times, we don't need the index so [0]*4 is shorter than range(4)
  l=len(s)-1                      # number of line

  # rotation of 45°
  a=[(['.']*(l-n)+list(i)+['.']*n)[::-1] for n,i in enumerate(s)]
  # tranform matrice :
  #  ABC      ..ABC      CBA..
  #  DEF  --> .DEF.  --> .FED.
  #  GHI      GHI..      ..IHG
  b=list(zip(*a))                 # transpose
  #  CBA..      C..
  #  .FED.  --> BF.
  #  ..IHG      AEI
  #             .DH
  #             ..G
  print(' '.join(''.join(i).replace('.','') for i in b))

  # rotation of 90°
  a=[(list(i))[::-1] for n,i in enumerate(s)]
  # tranform matrice :
  #  ABC      CBA
  #  DEF  --> FED
  #  GHI      IHG
  b=list(zip(*a))                 # transpose
  #  CBA       CFI
  #  FED   --> BEH
  #  IHG       ADG
  print(' '.join(''.join(i) for i in b))
  s=b

```

## Results

```
>>> f(['ABCDE','FGHIJ','KLMNO','PQRST'])
['E', 'DJ', 'CIO', 'BHNT', 'AGMS', 'FLR', 'KQ', 'P']
['EJOT', 'DINS', 'CHMR', 'BGLQ', 'AFKP']
['T', 'OS', 'JNR', 'EIMQ', 'DHLP', 'CGK', 'BF', 'A']
['TSRQP', 'ONMLK', 'JIHGF', 'EDCBA']
['P', 'QK', 'RLF', 'SMGA', 'TNHB', 'OIC', 'JD', 'E']
['PKFA', 'QLGB', 'RMHC', 'SNID', 'TOJE']
['A', 'FB', 'KGC', 'PLHD', 'QMIE', 'RNJ', 'SO', 'T']
['ABCDE', 'FGHIJ', 'KLMNO', 'PQRST']

>>> f(['ABCDEF','GHIJKL','MNOPQR','STUVWX'])
['F', 'EL', 'DKR', 'CJQX', 'BIPW', 'AHOV', 'GNU', 'MT', 'S']
['FLRX', 'EKQW', 'DJPV', 'CIOU', 'BHNT', 'AGMS']
['X', 'RW', 'LQV', 'FKPU', 'EJOT', 'DINS', 'CHM', 'BG', 'A']
['XWVUTS', 'RQPONM', 'LKJIHG', 'FEDCBA']
['S', 'TM', 'UNG', 'VOHA', 'WPIB', 'XQJC', 'RKD', 'LE', 'F']
['SMGA', 'TNHB', 'UOIC', 'VPJD', 'WQKE', 'XRLF']
['A', 'GB', 'MHC', 'SNID', 'TOJE', 'UPKF', 'VQL', 'WR', 'X']
['ABCDEF', 'GHIJKL', 'MNOPQR', 'STUVWX']

```

**with a cleaner output (189 bytes)**

```
j=' '.join
def f(s):
 for k in [1,0]*4:
  b=list(zip(*[([' ']*(len(s)-1-n)*k+list(i)+[' ']*n*k)[::-1] for n,i in enumerate(s)]))
  print(j(j(i).replace(' ','') for i in b))
  if k==0:s=b

```

.

```
>>> f(['ABCDE','FGHIJ','KLMNO','PQRST'])
E DJ CIO BHNT AGMS FLR KQ P
EJOT DINS CHMR BGLQ AFKP
T OS JNR EIMQ DHLP CGK BF A
TSRQP ONMLK JIHGF EDCBA
P QK RLF SMGA TNHB OIC JD E
PKFA QLGB RMHC SNID TOJE
A FB KGC PLHD QMIE RNJ SO T
ABCDE FGHIJ KLMNO PQRST

```

# Answer
> 2 votes
# MATL, 40 bytes

```
t!tP!tP!GXKZyqXI"IZ}w_w2$:"K@2$Xd!]K!XKx

```

Input is a 2D char array in Matlab notation:

```
['ABCDE'; 'FGHIJ'; 'KLMNO'; 'PQRST']

```

The output contains each "word" on a separate line.

**Try it online!**

```
t          % input 2D char array. Duplicate. The original copy will produce
           % the words left to right when displayed
!          % transpose. This will produce the words up to down
tP!        % duplicate, flip upside down, transpose. This will produce the
           % words right to left
tP!        % Same. This will produce the words down to up
GXK        % push input again. Copy to clipboard K
Zy         % get size (length-2 vector; [4 5] in the example)
q          % decrement by 1 (gives  [3 4] in the example)
XI         % copy to clipboard I
"          % loop: do this twice, consuming the decremented length-2 vector
  I        %   push decremented size vector again
  Z}       %   split into its two elements (pushes 3 and 4 in the example)
  w_w      %   swap, negave, swap (results in -3, 4 in the example)
  2$:      %   binary range: indices of diagonals  ([-3 -2 -1 0 1 2 3 4]
           %   in the first iteration in the example, [-4 -3 -2 -1 0 1 2 3]
           %   in the second)
  "        %   for each
    K      %     push input (first iteration) or its tranposed version (second)
    @      %     push index of diagonal
    2$Xd!  %     extract that diagonal as a row vector
  ]        %   end for each
  K!XKx    %   update clipboard K with transposed version for next iteration
           % end loop. Display

```

# Answer
> 2 votes
# 05AB1E (legacy), 24 bytes

```
4F=íøDεÐS0:«NFÁ}}øí0мõK,

```

Input as a list of lines; outputs as list of strings as well, each on a separated newline to STDOUT.

Try it online.

**Explanation:**

Unfortunately 05AB1E doesn't have an (anti-)diagonals builtin, so 17 of the bytes are to accomplish that in a similar matter as my 05AB1E answer for the *Diamondize a Matrix* challenge.

Uses the legacy version of 05AB1E, since it can zip/transpose on a list of strings, whereas the new 05AB1E version requires it to be a character-matrix.

```
4F             # Loop 4 times:
  =            #  Print the current list with trailing newline (without popping)
               #  (which will use the implicit input-list in the first iteration)
   íø          #  Rotate once 90 degrees clockwise:
   í           #   Reverse each line
    ø          #   Zip/transpose; swapping rows/columns
     D         #  Duplicate this rotated grid
      ε        #  Map over each line:
       ÐS0:«   #   Append the length amount of "0"s:
       Ð       #    Triplicate the string
        S      #    Convert the top copy to a list of characters
         0:    #    Replace all these characters in another copy to "0"
           NF  #   Loop the (0-based) map-index amount of times:
             Á #    Rotate once towards the right
            }  #   Close the loop
      }        #  Close the map
       øí      #  Rotate once 90 degrees counterclockwise
         0м    #  Remove all "0"s from each inner string
           õK  #  Remove potential empty strings
             , #  Pop and output this list of diagonals with trailing newline

```

# Answer
> 1 votes
# Jelly, 13 bytes

```
KṄḲ
ZUÇƊƬŒDÇ€

```

Try it online!

Ok, so this is fairly liberal with I/O, but I don't think any of the assumptions are a major issue:

* The output for each row is in a different order than specified in the question. Because of

> The order of the rotations "read off" does not matter as long as all eight cardinals and primary intercardinals are done once.

I assumed this was OK
* The output for half of the diagonals is in "reverse" order (i.e. the output includes `PLHD` instead of `DHLP`)

If this isn't ok, then +3 bytes
* This is a "link" in Jelly, which is Jelly's version of a function. This takes takes input via ARGV and outputs to STDIN rather than "returning" a value. The `ȧ“”` in the Footer suppresses Jelly implicitly outputting the return value for the link
* This takes input as a matrix of characters. This seems to be allowed by

> Example input (taken as an array of characters, multiline string, or other reasonable format)

---

## How it works

```
KṄḲ - Helper link. Takes a string S on the left
K   - Join S by spaces
 Ṅ  - Print S
  Ḳ - Split S on spaces

ZUÇƊƬŒDÇ€ - Main link. Takes a matrix M of characters
   Ɗ      - Group the previous 3 links into a monad f(M):
Z         -   Transpose
 U        -   Reverse
  Ç       -   Call the helper link
    Ƭ     - Yield [f(M), f(f(M)), f(f(f(M))), f(f(f(f(M))) = M]
            This outputs and returns all rotations of M
     ŒD   - Get the diagonals of each
       Ç€ - Call the helper link on each diagonal

```

# Answer
> 1 votes
# JavaScript (Node.js), 135 bytes

```
f=(s,n=8)=>n?[s.flatMap(t=>t.join``||[]),...f([...Array(L=(s+0).length)].map((_,y,p)=>p.map((_,x)=>(s[y+x-L>>1]||0)[(x-y)/2])),n-1)]:[]

```

Try it online!

Slow. Complexity O(n^256) Proof that the rotation work Fast run

---
Tags: code-golf, string, grid, word-search
---


title: Minimum depth of a ragged list

text:
# Question
Title: Minimum depth of a ragged list
As input you will be given a ragged list of positive integers containing at least one integer at some level. For example:

```
[[],[[1,2,[3]]],[]]

```

You should output the depth of the least deep integer. For example if the input is just a list of integers, then the every integer is 1 level deep so the answer is 1. There may be a tie for the crown of least deep but it doesn't matter since we only need to output the depth not the least deep integer itself.

This is so answers will be scored in bytes with fewer bytes being the goal.

## Test cases

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

```

# Answer
# Python 2, 35 bytes

```
f=lambda a:min(a)<[]or-~f(sum(a,a))
```

Attempt This Online!

#### Old Python 2, 36 bytes

```
f=lambda a:min(a)<[]or-~f(sum(a,[]))
```

Attempt This Online!

## Python, 45 bytes

```
f=lambda a:int in map(type,a)or-~f(sum(a,[]))
```

Attempt This Online!

#### Old Python, 46 bytes

```
f=lambda a:int in map(type,a)or 1+f(sum(a,[]))
```

Attempt This Online!

Outputs True for 1. Does a bfs for integers.

### Details:

The bfs, or breadth first search, is implemented as follows: If there is an int at level 1 return 1. If not there are only lists; we can sum (concatenate) them; this eliminates depth 1 nodes, combines all former depth 2 nodes into the new depth 1 tier and pulls each level below up one tier. We can now recursively repeat until we find the first integer.

Shortcuts in Python 2:

Python 2 but not Python 3 has a total ordering on all objects, in particular, every list is greater than every integer. The type check can therefore be cheaply done using min.

And one dirty trick:

The `sum` function is meant for numbers. If you apply it to lists you explicitly have to set the starting value from `0` to `[]`. But, technically, any list will do, so to save a byte we use `a` itself instead. While this is rather dirty one can check that it leaves the `min` unchanged.
> 7 votes

# Answer
# Jelly, 4 bytes

```
ŒJẈṂ

```

Try It Online!

-1 byte thanks to Razetime

```
ŒJẈṂ    Main Link
ŒJ      Get the multidimensional index of each scalar value
  Ẉ     Length of each coordinate = depth of each value
   Ṃ    Minimum

```
> 6 votes

# Answer
# , ~~66~~ ~~60~~ 57 bytes

```
f=function(l)"if"(all(Map(is.list,l)),1+f(unlist(l,F)),1)

```

Try it online!

-3 bytes thanks to pajonk.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 16 bytes

```
Min[1+#0/@-1^#]&

```

Try it online!

Abuses the fact that `f/@a = a` for any atomic `a`.
> 2 votes

# Answer
# JavaScript, 35 bytes

```
f=x=>x.at?Math.min(...x.map(f))+1:0

```

`x.at` is a method (truthy) if `x` is an Array (requires a newish browser) and is `undefined` (falsy) if `x` is a Number. The rest is straightforward.

```
f=x=>x.at?Math.min(...x.map(f))+1:0
testcases =
[[1], [[[[1]]],[]], [[[[1]]],[1]], [[[6],1,2,3,[4,5]]], [[],[[1,2,[3]]],[]]]
console.log(testcases.map(f))
```
> 2 votes

# Answer
# Vyxal, 6 bytes

```
⁽LÞZfg

```

Try it Online!

Can’t be bothered trying to add an explanation on mobile, feel free to edit one in.
> 2 votes

# Answer
# Vyxal, ~~16~~ ~~14~~ 13 bytes

```
≬ƛƛ;⁼;A⁽ÞfŀL›

```

Try it Online!

Feels too long. Vyxal parsing isn't janky at all why would you even think that?

## Explained

```
≬ƛƛ;⁼;A⁽ÞfŀL›
≬......⁽..ŀ   # call function ≬ on the input until the result of function ⁽ is falsey
≬             # a function that: (this is the predicate for ŀ)
 ƛƛ;⁼;        #   checks whether each item is a list - an empty map over a list equals itself
      A       #   and returns whether all items are truthy under that
              # ----------------------------------------------------
              # N.B. The ≬ modifier (next 3 elements as a lambda) is used here because of the way map lambdas are parsed:
              # Rather than treating them as their own structure type internally,
              # they are converted to a lambda structure
              # followed immediately by a token representing the `M` (map) element.
              # This means that map lambdas are considered to be 2 elements
              # ‡ doesn't work because it doesn't catch the extra `M`
              # token generated while parsing.
              # ------------------------------------------------------
        ⁽Þf   # a function that flattens its argument by 1 depth
           L› # the length of the list collected by ŀ + 1

```
> 1 votes

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

```
{⌊/(⍵∊⎕d)/+\1 ¯1 0['[]'⍳⍵]}

```

Try it on APLgolf!
> 1 votes

# Answer
# 05AB1E, 11 bytes

```
d[¼D1å#€`}¾

```

Try it online or verify all test cases.

**Explanation:**

```
d       # Transform all integers to 1s in the (implicit) input (with >=0 check)
 [      # Loop indefinitely:
  ¼     #  Increase the counter variable (implicitly starts at 0)
  D     #  Duplicate the current list
   1å   #  Check if it contains a 1
     #  #  If it does: stop the infinite loop
   €`   #  Flatten the list one level down
 }¾     # After the loop, push the counter variable
        # (after which it is output implicitly as result)

```
> 1 votes

# Answer
# Retina 0.8.2, 32 bytes

```
\d+
$'¶
1A`
+`[^][¶]|\[]

O`
\G]

```

Try it online! Link includes test cases. Explanation:

```
\d+
$'¶
1A`

```

Get all the suffixes of the integers.

```
+`[^][¶]|\[]

```

Delete everything except unbalanced `]`s.

```
O`
\G]

```

Output the smallest depth.
> 1 votes

# Answer
# Julia 1.0, ~~36~~ 30 bytes

```
!l::Int=0
!l=1+min(Inf,.!l...)

```

Try it online!
> 1 votes

# Answer
# Ruby, 43 bytes

```
g=->l{l.any?{|x|x*0==0}?1:1+g[l.flatten 1]}

```

Try it online!
> 1 votes

# Answer
# Brachylog, 8 bytes

```
;.≜∋ⁱ⁾İ∧

```

Try it online!

Cannot be golfed to `∋ⁱ↖.İ∧≜`, as failing to pre-label the output variable causes it to hang--perhaps because it gets stuck exploring the elements (digits) of the integers themselves ad infinitum?
> 1 votes

# Answer
# Whython, 26 bytes

```
f=lambda l:1+f(sum(l,l))?1

```

Idea taken from loopy walt's Python 2 answer, which you should upvote.

Attempt This Online!

### Explanation

```
f=lambda l:1+f(sum(l,l))?1
f=                          # Define f as
  lambda l:                 # a function of one argument, l, a list:
               sum(l  )     #  Add (concatenate) each element of l
                    ,l      #  to l
                            #  If all elements of l are lists, this succeeds,
                            #  essentially flattening l by one level and concatenating
                            #  that to the original l
             f(        )    #  Call f recursively on that list
           1+               #  and add 1 to the result
                            #  If there are any integers in l, sum raises an exception
                        ?1  #  Catch that exception and return 1

```
> 1 votes

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

```
{0∊≡¨⍵:1⋄1+∇⊃,/⍵}

```

Try it on APLgolf!

A dfn submission which takes a ragged array on the right.
> 0 votes

# Answer
# Charcoal, 32 bytes

```
≔¹ηＷ⬤θ⁼κ⁺υκ«≦⊕ηＦθＦκ⊞υλ≔υθ≔⟦⟧υ»Ｉη

```

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

```
≔¹η

```

Start off with a depth of `1`.

```
Ｗ⬤θ⁼κ⁺υκ«

```

While all of the elements of the input are arrays, then:

```
≦⊕η

```

Increment the depth.

```
ＦθＦκ⊞υλ≔υθ≔⟦⟧υ

```

Flatten the array by one level. (This is only four bytes in trunk Charcoal but unfortunately that's not available on TIO.)

```
»Ｉη

```

Output the final depth.
> 0 votes

# Answer
# Python3, 57 bytes:

```
f=lambda x:min(isinstance(i,int)or 1+f(i)for i in x if i)

```

Try it online!
> 0 votes

# Answer
# Factor \+ `math.unicode`, 68 bytes

```
[ 1 swap [ dup [ real? ] ∃ ] [ [ 1 + ] dip flatten1 ] until drop ]

```

Flatten the input by one depth until a number is an element at the surface, keeping track of the number of iterations. This is shorter than the recursive solutions I tried, especially because Factor has no terse way of handling the minimum value of a sequence when it can be empty. (And because recursion is verbose in Factor.)

Since `flatten1` postdates build 1525, the one TIO uses, here's a screenshot of running the above code in Factor's REPL:
> 0 votes

# Answer
# Perl 5 List::Util, 43 bytes

```
$_=min map/\d/?$d:9e9+($d+=/,/?0:92-ord),@F

```

Try it online!

Runs through the input as a list of chars. Increases depth `$d` for each `[`, decreases for each `]` since `92-ord` becomes 92 - 91 = +1 for `[` and 92 - 93 = -1 for `]`. Nothing changes for `,` and yield current depths for which the minimum is printed for digits. To run all tests `$d` needs to be reset between each: Try all test cases online! A more sane algorithm would be this one, but 11 bytes longer.
> 0 votes

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


title: Dizzy integer enumeration

text:
# Question
Title: Dizzy integer enumeration
Your challenge today is to output a given term of a sequence enumerating all of the integers. The sequence is as follows: If we have a 0-indexed function generating the sequence `f(n)` and `ceil(x)` is the ceiling function, then `f(0) = 0`; `abs(f(n)) = ceil(n/2)`; `sign(f(n))` is positive when `n` and `ceil(n/2)` are either both even or both odd.

To help understand this sequence, the first few terms are as follows: `0 1 -1 -2 2 3 -3 -4 4 5 -5 -6 6 7 -7...`

Your task is to write a program to that takes an integer `n` and outputs the `n`th term of the sequence. Input may be 0 or 1-indexed only.

Test cases (0-indexed):

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

```

This is , fewest bytes wins!

# Answer
# SOGL V0.12, ~~8~~ 6 bytes

```
I».»⌡±

```

Try it Here! or try the first couple numbers (changed a bit so it'd work)
0-indexed.

Explanation:

```
I       increment the input
 »      floor divide by 2
  .     push the original input
   »    floor divide by 2
    ⌡   that many times
     ±    negate

```

Or simpler:

```
(input + 1) // 2 negated input // 2 times
        I     »     ±      .     »    ⌡

```
> 9 votes

# Answer
# Python 2, 26 24 bytes

```
lambda x:-~x/2/(1-(x&2))

```

Try it online!
> 10 votes

# Answer
# JavaScript (ES6), 18 bytes

1-indexed.

```
n=>n/(++n&2||-2)|0

```

### Demo

```
let f =

n=>n/(++n&2||-2)|0

for(n = 1; n < 20; n++) {
  console.log(n + ' --> ' + f(n))
}
```
> 5 votes

# Answer
# Jelly, 6 bytes

```
HµĊN⁸¡

```

Try it online!

Uses dzaima's algorithm.

-1 thanks to Jonathan Allan.
> 4 votes

# Answer
# C, 25 bytes

```
f(n){return~n/2*~-(n&2);}

```
> 4 votes

# Answer
# Haskell, 26 bytes

```
f x=div(x+1)2*(-1)^div x 2

```

Try it online!

The other Haskell answers seem to be overcomplicating things… ^^
> 4 votes

# Answer
# Pyke, 6 bytes

```
heQeV_

```

Try it here!

Uses dzaima's approach... ~~Beats~~ Ties Jelly!

# Explanation

```
h      - Increment the input, which is implicit at the beginning.
 e     - Floor halve.
  Q    - Push the input.
   e   - Floor halve.
    V_ - Apply repeatedly (V), ^ times, using negation (_).
       - Output implicitly.

```

The hex-encoded bytes equivalent would be: `68 65 51 65 56 5F`.
> 3 votes

# Answer
# 05AB1E, 6 bytes

```
;DîsF(

```

Try it online!

Uses dzaima's algorithm.
> 3 votes

# Answer
# Haskell, ~~25~~ ~~43~~ 42 bytes

```
((do a<-[0..];[[-a,a],[a,-a]]!!mod a 2)!!)

```

Try it online! 1-indexed.

*Edit:* The previous version had the signs in a wrong order, thanks to @Potato44 for pointing out. Fixed for 18 bytes ...

*Edit 2:* Thanks to BMO for -1 byte!
> 3 votes

# Answer
# Mathematica, 24 bytes

```
(s=⌈#/2⌉)(-1)^(#+s)&

```

-14 bytes from @Misha Lavrov
> 3 votes

# Answer
# Python 2, 21 bytes

```
lambda x:-x/2*~-(x&2)

```

Try it online!
> 3 votes

# Answer
# Java 8, 15 bytes

```
n->~n/2*~-(n&2)

```

EDIT: Is Java really the shortest of the non-golfing languages?! o.Ô

**Explanation:**

Try it here.

I'll use the table below as reference of what's happening.

1. `~n` is equal to `-n-1`.
2. Since integer division in Java automatically floors on positive integers and ceils on negative integers, `~n/2` will result in the sequence `0,-1,-1,-2,-2,-3,-3,-4,-4,-5,-5,...`
3. `n&2` will result in either `0` or `2`, in the sequence `0,0,2,2,0,0,2,2,0,0,2,...`
4. `~-x` is equal to `(x-1)`, so `~-(n&2)` (`((n&2)-1)`) results in the sequence `-1,-1,1,1,-1,-1,1,1,-1,-1,1,...`
5. Multiplying the two sequences of `~n/2` and `~-(n&2)` gives is the correct sequence asked in the challenge: `0,1,-1,-2,2,3,-3,-4,4,5,-5,...`

Overview table:

```
n       ~n      ~n/2    n&2     ~-(n&2)     ~n/2*~-(n&2)
0       -1      0       0       -1          0
1       -2      -1      0       -1          1
2       -3      -1      2       1           -1
3       -4      -2      2       1           -2
4       -5      -2      0       -1          2
5       -6      -3      0       -1          3
6       -7      -3      2       1           -3
7       -8      -4      2       1           -4
8       -9      -4      0       -1          4
9       -10     -5      0       -1          5
10      -11     -5      2       1           -5

```
> 3 votes

# Answer
# Python 3, 29 bytes

```
lambda n:-~n//2*(-1)**(n%4>1)

```

Try it online!
> 2 votes

# Answer
# Pyth, 9 bytes

```
_F/hQ2/Q2

```

**Try it here!**

Uses dzaima's approach.
> 2 votes

# Answer
## Batch, 29 bytes

```
@cmd/cset/a"%1/2^(%1<<30>>30)

```
> 2 votes

# Answer
## Haskell, 36 bytes

```
g x=x: -x:g(-x-signum x)
((0:g 1)!!)

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), 18 bytes

```
f=
n=>n/2^(n<<30>>30)
```

```
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0
```

0-indexed.
> 2 votes

# Answer
## Javascript, 17 bytes

```
n=>~n/2*~-(n&2)^0

```

```
f=
n=>~n/2*~-(n&2)^0
```

```
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0
```

This one is 0 indexed. It's entirely bitwise trickery.
> 2 votes

# Answer
# dc, 16 bytes

```
1+d2~+2%2*1-r2/*

```

I am sure there's a way to make 0..1 to -1..1 in dc shorter, but no ideas for now.

Try it online!
> 2 votes

# Answer
# Cubically, 23 bytes

(1-indexed)

```
FDF'$:7+8/0_0*0-8*7/0%6

```

Try it online!

The main difficulty when writing code in Cubically are:

* There is only 1 write-able variable, and
* Get constants is hard.

So, this solution calculate

```
((((n+1)/2)%2)*2-1)*n/2

```

where `/` denotes integer division. That only need 1 temporary variable, and constants 1 and 2.

Explanation:

```
FDF'$:7+8/0_0*0-8*7/0%6
FDF'                      Set face value of face 0 to 2, and value of memory index 8 (cube is unsolved) to 1 (true = unsolved)
    $                     Read input
     :7                                 input
       +8                                + 1
         /0                        (        ) /2
           _0                     (             ) %2
             *0                  (                  ) *2
               -8                                        -1
                 *7             (                          ) *n
                   /0                                          /2
                     %6   Print

```
> 2 votes

# Answer
# TI-Basic (TI-84 Plus CE), 20 bytes

```
‾int(‾Ans/2)(1-2remainder(int(Ans/2),2

```

A full program that is called like `5:prgmNAME`.

TI-Basic is a tokenized lanugage, all tokens used here are one byte, except for `remainder(` which is two.  represents the regative token, which is typed with the `(-)` key.

Examples:

```
0:prgmNAME
 => 0
1:prgmNAME
 => 1
2:prgmNAME
 => -1
#etc

```

Explanation:

```
‾int(‾Ans/2)(1-2remainder(int(Ans/2),2
‾int(‾Ans/2)                           # -int(-X) is ciel(X), so ciel(Ans/2)
                          int(Ans/2)   # int(X) is floor(X), so floor(Ans/2)
                remainder(int(Ans/2),2 # 1 if floor(Ans/2) is odd else 0
            (1-2remainder(int(Ans/2),2 # -1 if floor(Ans/2) is odd, else 1
_int(_Ans/2)(1-2remainder(int(Ans/2),2 # -ciel(Ans/2) if floor(Ans/2) is odd, else ciel(Ans/2)

```

Same formula as a Y-var function:

```
Y1= ‾int(‾X/2)(1-2remainder(int(X/2),2

```
> 2 votes

# Answer
# Brain-Flak, ~~86~~ ~~74~~ ~~72~~ 70 bytes

```
{({}[()]<({}<>([({})]{(<{}([{}]())>)}{}())<>)>)}{}<>{}{<>([{}])(<>)}<>

```

Try it online!

## Explanation

There are two parts to this code. The first part

```
({}[()]<({}<>([({})]{(<{}([{}]())>)}{}())<>)>)}{}

```

does the brawn of the computation. It determines `ceil(n/2)` and whether or not to negate the output.

To explain how it works I will first explain how one would calculate `ceil(n/2)`. This could be done with the following code

```
{({}[()]<({}([{}]()))>)}{}

```

This counts down from **n** each time it performs a not (`([{}]())`) on a counter and adds the counter to a result. Since the counter is zero half the time we only increment every other run starting with the first one.

Now I want to also compute the sign of our results. To do this we start another counter. This counter only changes state if the first counter is off. That way we get the desired pattern. We put these two counters on the off stack to ease with moving them around when the time comes.

Now once we have finished that computation our stack looks like this

```
          parity(n)
ceil(n/2) sign

```

So we need to do some work to get the intended result this second part does it.

```
<>{}{<>([{}])(<>)}<>

```
> 2 votes

# Answer
# Perl 5, 32 + 1 (`-p`) = 33 bytes

```
$_='-'x(($_+++($b=0|$_/2))%2).$b

```

Try it online!
> 1 votes

# Answer
# Proton, 23 bytes

```
n=>-~n//2//(-1)**(n//2)

```

Try it online!

Port of Halvard's solution.

# Proton, 23 bytes

```
n=>-~n//2*(-1)**(n%4>1)

```

Try it online!

Port of Leaky's solution.

A bit more Protonic, 24 bytes:

```
n=>-~n//2*(**)(-1,n%4>1)

```
> 1 votes

# Answer
# QBIC, ~~27~~ 26 bytes

```
g=(:+1)'\2`~(a-g)%2|?-g\?g

```

## Explanation

```
g=          set worker var 'g' to
(:+1)           our index (plus one for the ceil() bit)
'\2`            integer divided by 2 (the int div needs a code literal: '..`
~(a-g)%2    IF index - temp result is odd (index 2 minus result 1 = 1)
|?-g        THEN PRINT g negated
\?g         ELSE PRINT g

```
> 1 votes

# Answer
# Clojure 122 bytes

Verbose, even when golfed. I'm going for the sympathy vote here... :-)

Golfed:

```
(defn d[n](let[x(int(Math/ceil(/ n 2)))y(cond(or(and(even? n)(even? x))(and(odd? n)(odd? x)))(Math/abs x):else(- 0 x))]y))

```

Ungolfed:

```
(defn dizzy-integer [n]
  (let [x   (int (Math/ceil (/ n 2)))
        y   (cond
                (or (and (even? n) (even? x))
                    (and (odd? n)  (odd? x))) (Math/abs x)
                :else (- 0 x)) ]
    y))

```
> 1 votes

# Answer
# Excel VBA 32-Bit, <sub>~~39~~</sub> 37 Bytes

Anonymous VBE immediate window function that takes input from cell `A1` and outputs to the VBE immediate window

```
?[Sign((-1)^Int(A1/2))*Int((A1+1)/2)]

```

Restricted to 32-Bit as `A^B`is not valid in 64-Bit (`A ^B` is as close as can be achieved)
> 1 votes

# Answer
# Julia 0.6, 16 bytes

It's just the java solution except I need `÷` for integer division.

```
n->~n÷2*~-(n&2)

```

Try it online!
> 1 votes

# Answer
# Husk, 9 bytes

```
!m?I_%2İZ

```

Try it online!

1-indexed.

## Explanation

```
!m?I_%2İZ
       İZ List of all integers (builtin) [0,1,-1,2,-2,...]
 m        map to the following function
  ?  %2   if the number is even,
    _     negate it.
   I      otherwise return it
!         find element at input index

```

# Alternate solution, 9 bytes

```
!⌊½¹¡_⌊½→

```

Try it online!

Uses the same equation as the SOGL answer.
> 1 votes

# Answer
# Japt, 8 bytes

```
z°U&2ªJÑ

```

Try it
> 1 votes

# Answer
# Factor, 28 bytes

```
[ dup 1 + 2/ -1 rot 2/ ^ * ]

```

Try it online!

## Explanation

\\$\large f(n)=\left\lfloor\frac{n+1}{2}\right\rfloor\times-1^\left\lfloor\frac{n}{2}\right\rfloor\\$

```
         ! 6
dup      ! 6 6
1        ! 6 6 1
+        ! 6 7
2/       ! 6 3
-1       ! 6 3 -1
rot      ! 3 -1 6
2/       ! 3 -1 3
^        ! 3 -1
*        ! -3

```
> 0 votes

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