title: Is it a tower permutation?

text:
# Question
Title: Is it a tower permutation?
A tower is made out of layers, each one being one unit shorter than the one below it. Every layer is completely on top of the previous layer. For example, here is a tower along with it's height map:

```
  #
 ##
 ###
 ####
#####
14532

```

Because the lengths of the layers are the integers from 1 to n, and because the layers are completely on top of each other, the height map will always be a permutation of the integers from `1` to `n`. (Can you see why? Comment below)

The converse is not true. Some permutations are not the height map of a tower, meaning they are not *tower permutations*. For example, `[2,1,3,5,4]` is not the height map of any tower, meaning that it's not a tower permutation. However, `[1,4,5,3,2]` is a tower permutation, as you can see from the previous ascii drawing.

Just to be clear, the following is **not** a tower:

```
   #
   ##
  ###
# ###
#####
21354

```

Because each layer has to be continuous. This is instead a castle :P

Your task is to take a permutation of the integers 1 to n (inclusive) and decide if it's a tower permutation, as per usual and rules. You can assume that `n>0`

# Test cases (all permutations up to n=4)

```
[1] -> True
[1, 2] -> True
[2, 1] -> True
[1, 2, 3] -> True
[1, 3, 2] -> True
[2, 1, 3] -> False
[2, 3, 1] -> True
[3, 1, 2] -> False
[3, 2, 1] -> True
[1, 2, 3, 4] -> True
[1, 2, 4, 3] -> True
[1, 3, 2, 4] -> False
[1, 3, 4, 2] -> True
[1, 4, 2, 3] -> False
[1, 4, 3, 2] -> True
[2, 1, 3, 4] -> False
[2, 1, 4, 3] -> False
[2, 3, 1, 4] -> False
[2, 3, 4, 1] -> True
[2, 4, 1, 3] -> False
[2, 4, 3, 1] -> True
[3, 1, 2, 4] -> False
[3, 1, 4, 2] -> False
[3, 2, 1, 4] -> False
[3, 2, 4, 1] -> False
[3, 4, 1, 2] -> False
[3, 4, 2, 1] -> True
[4, 1, 2, 3] -> False
[4, 1, 3, 2] -> False
[4, 2, 1, 3] -> False
[4, 2, 3, 1] -> False
[4, 3, 1, 2] -> False
[4, 3, 2, 1] -> True

```

# Answer
# Python, 46 bytes

```
f=lambda l:len(l)<3or min(l[:3])<l[1]*f(l[1:])

```

Try it online!

Uses the characterization

> A tower permutation is one where no element is smaller than both its neighbors.

---

## Python 2, 36 bytes

```
lambda l:'-1, 1'in`map(cmp,l[1:],l)`

```

Try it online!

Really crams in the Python 2 nostalgia: `cmp`, backticks, `map` producing a list.

The idea is to use `cmp` to compare consecutive elements to detect an decrease (`-1`) followed by an increase `(+1)`. This is identified by the string representation containing the substring `-1, 1`, so that tower permutations give `False` and others give `True`.

---

## Python 3 error code, 32 bytes

```
def f(a,*l):(a,)>l<l[1:]or f(*l)

```

Try it online!

A nifty short solution by loopy walt. Takes inputs splatted and outputs by erroring or not erroring, with successful termination indicating *not* a tower permutation.
> 14 votes

# Answer
# Jelly, ~~5~~ 4 bytes

```
>ƝṢƑ
```

Attempt This Online!

Explanation:

```
(implicit input)                     [1, 4, 5, 3, 2]
 Ɲ      for each neighouring pair:   [(1, 4), (4, 5), (5, 3), (3, 2)]
>       is left greater than right?  [0, 0, 1, 1]
   ṠƑ   is it the same after sorting?
(implicit output)

```

This tests if the list is increasing and then decreasing again.
> 10 votes

# Answer
# , 33 bytes

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

```
function(v)is.unsorted(diff(v)<0)

```

Try it online!

Outputs flipped `TRUE`/`FALSE`.
> 6 votes

# Answer
# Julia 1.0, ~~26~~ 23 bytes

```
!v=issorted(diff(v).<0)

```

Try it online!
> 6 votes

# Answer
# Shue, 100 99 bytes

```
=L
=R
,1,R=<,R
1<={
1{={1
,{=<,
L{=L
L1,=L>
>1=}
}1=1}
},=,>
>R=R
LR
,1,1=e
e1=e
1e=e
e,=e
,e=e
LeR

```

Try it online!

Takes input as comma-separated list of unary numbers, with a trailing comma.

# Explanation

```
=L       - Implicit left edge
=R       - Implicit right edge
,1,R=<,R - Spawn a left triangle on the right, if last element is 1. Remove the last element
1<={     - Triangle decrements element, turns into left curly triangle
1{={1    - Curly triangle passes trough ones
,{=<,    - Curly triangle turns into a sharp triangle (to decrement next element)
L{=L     - After reaching the left edge, curly triangle dissapears
L1,=L>   - Same stuff but in the other direction
>1=}     - --||--
}1=1}    - --||--
},=,>    - --||--
>R=R     - --||--
LR       - If everything has been reduced, output true
,1,1=e   - Or if there is a one not located near the edges, create an error
e1=e     - Errors propagate
1e=e     - --||--
e,=e     - --||--
,e=e     - --||--
LeR      - Final error state

```

Try it online!

# Python 3 algorithmic equivalent

```
def f(arr):
 if arr==[]:return True
 if 1 in arr[1:-1]:return False
 if arr[0]==1:return f([e-1 for e in arr[1:]])
 if arr[-1]==1:return f([e-1 for e in arr[:-1]])

```

Try it online!
> 5 votes

# Answer
# Haskell + hgl, ~~16~~ ~~13~~ 9 bytes

```
mnI<pa lt

```

Returns `True` when it is a tower permutation and `False` when it is not.

The following also works for the same score:

```
mnI<pa cp

```

## Explanation

We want to look for an element which is smaller than both of it's neighbors.

To do this we start with `pa lt`. `pa` takes a function and applies it to all consecutive neighbors, `lt` returns `True` if the first argument is less than the second and `False` otherwise.

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

```

If we started with a tower permutation this result is some number of `T`s follower by some number of `B`s. If it was not there is a `[B,T]` sub-sequence. This means that we just have to check if the result is monotonically increasing. If it is then it was a tower permutation, if it is not then it wasn't. `mnI` is the function to check if a list is monotonically increasing.

## Reflection

While working on this I found a bug and some documentation errors. None of this actually effects the answer, but I've fixed them.
> 4 votes

# Answer
# Brachylog, ~~8~~ 6 bytes

```
sṪ⌋∈₁Ṫ

```

Outputs false for a tower permutation, true for a non-tower permutation. Try it online!

### Explanation

Uses the "does it have a local minimum" test from xnor's answer.

```
s       For some consecutive sublist of the input
 Ṫ      which has three elements,
  ⌋     its minimum
   ∈₁   occurs at index 1 (i.e. the middle element)
     Ṫ  in that sublist

```
> 4 votes

# Answer
# , 19 14 12 bytes

```
-:]/:2>/\0&,

```

Try it online!

-5 after realizing from pxeger's answer that I could use sort by instead of group by

another -2 stealing pxeger's idea to use `>` instead of `*@|`

The key insight is that the deltas of successive elements in a tower permutation have at most one "peak":

* `/:` Sort by...
* `2>\0&,` Is left greater than right (pairs of 2
* `-:` Does that equal the original input?
> 3 votes

# Answer
# Python, 49 bytes

```
lambda x:sorted(a:=[*map(int.__gt__,x,x[1:])])==a
```

Attempt This Online!

Port of my Jelly answer. (Writing this is what inspired the -1 byte golf there)
> 2 votes

# Answer
# Java (JDK), 76 bytes

```
h->{int d=1,i=1;for(;i<h.length-1;)d&=h[i-1]>h[i]&h[i]<h[++i]?0:1;return d;}

```

Try it online!

Returns `1` if it's a tower, `0` if it's a castle.
> 2 votes

# Answer
# Husk, 5 bytes

```
V<Ẋ-…

```

Try it online!

Outputs zero for towers, non-zero for non-towers.

```
    …   # Fill gaps with numeric ranges
  Ẋ-    # Pairwise differences
V       # Index of first element that is
 <      # less than the next one
        # (or zero if not found)

```
> 2 votes

# Answer
# Ruby, 35 bytes

```
f=->l{l==l.sort||l.pop<l[-1]&&f[l]}

```

Try it online!
> 2 votes

# Answer
# Quipu, ~~64~~ ~~58~~ 46 bytes

```
3&2&1&4&\/0&
[][]  []  ??
4&3&
[]==
--::
2&
>>

```

Takes input from stdin, one number per line. Outputs by throwing an error for tower permutations and exiting silently for non-tower permutations. Attempt This Online!

### Explanation

Programs in Quipu consist of *threads*, which are two-character-wide columns. This program has six threads, numbered 0 through 5:

```
"0  1  2  3  4  5"

3& 2& 1& 4& \/ 0&
[] []    []    ??
4& 3&
[] ==
-- ::
2&
>>

```

Threads 3 and 4 hold two consecutive numbers in the list. (Initially, they're both 0.) Execution proceeds as follows:

* Thread 0 takes the value of thread 3 minus the value of thread 4 and tests whether the difference is positive, i.e. whether the numbers are in descending order. If they are, jump to thread 2; otherwise, continue to thread 1.
* Thread 1 tests if thread 2 is still 0. If so, it jumps to thread 3; if not, it exits the program.
* Thread 2, if reached, sets its value to 1.
* Thread 3 sets its value equal to the value of thread 4.
* Thread 4 reads and stores a number from stdin.
* Thread 5 jumps back to thread 0.

The end result is that any descending pair sets thread 2's value to 1, and any subsequent ascending pair ends the program. If this descending-ascending pattern never occurs, the program continues until it runs out of input and errors.
> 2 votes

# Answer
# Behaviour, 52 bytes

```
t=&(i=1\~([a%i>a%(i+1)a%i>a%(i-1)]i+=1i<#a-1)i>#a-2)

```

I don't exactly know the rules regarding recently self-made esolangs, but here goes nothing.

Ungolfed and commented:

```
t = &(
    i=1 // start on the index 1
    // repeat the following sequence until failure
    \~(
      // either the ith member is bigger than the previous or bigger than the next
      [
        a%i > a%(i+1)
        a%i > a%(i-1)
      ]
      // increment index and check if it still is less than n-1
      i += 1
      i < #a-1
    )
    // is a tower if the index stopped incrementing on the last possible index (i.e. passed all the checks)
    i > #a-2
  )

```

Test with:

```
t:{1}
t:{1 2 3}
t:{3 1 2}

```

Bonus (bigger) answer using more obscure features of the language but basicaly the same logic:

```
t=&![#(t=a)<3(#a-2)*&(v=t%(a+1)v>t%a|v<t%(a+2));>&a|b]

```
> 2 votes

# Answer
# Curry, 24 bytes

*Tested to work in both PAKCS and KiCS2*

```
f(_++a:b:c:_)|b<a&&b<c=1

```

Try it online!

Checks if any value is smaller than both of its neighbors using Curry's powerful pattern matches. Returns a `1` if it isn't a tower permutation and nothing otherwise.

TIO has a limited ability to test things like this. Paste the following to smap and run in `PAKCS 2.2.0` for better testing abilities:

```
import Control.SetFunctions

f(_++a:b:c:_)|b<a&&b<c=1

-- Helper to run tests
helper :: [Int] -> Bool
helper a = isEmpty $ set0 $ f a
main =
  [ helper [1,2,3]
  , helper [3,2,1]
  , helper [3,1,2]
  , helper [4, 1, 2, 3]
  ]

```

This test handler will not work in KiCS2 or at least not on the version used by smap. But the function itself does if you want to manually test it.
> 2 votes

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

```
[ 3 clump [ dup infimum second= ] ∃ ]

```

Try it online!

## Explanation

Returns `f` for true and `t` for false.

*"Is there an element that is smaller than both its neighbors?"*

Thanks to @xnor's answer for the characterization. The shortest I could get the 'sorted signs of differences' method was 44 bytes.

```
             ! { 2 1 3 5 4 }
3 clump      ! { { 2 1 3 } { 1 3 5 } { 3 5 4 } }
[ ... ] ∃    !          (is there any element that...)
             ! { 2 1 3 }
dup          ! { 2 1 3 } { 2 1 3 }
infimum      ! { 2 1 3 } 1
second=      ! t

```
> 1 votes

# Answer
# C (gcc), ~~93~~ \\$\cdots\\$ ~~59~~ 54 bytes

```
r;f(a,n)int*a;{for(r=0;n-->2;)r|=*a>*++a&*a<a[1];n=r;}

```

Try it online!

*Saved a whopping 24 bytes thanks to Olivier Grégoire!!!*

Inputs a pointer to an array of a permutation of the integers from \\$1\\$ to \\$n\\$ and \\$n\\$ (because pointers in C carry no length info).
Returns \\$0\\$ if it's a tower permutation or \\$1\\$ otherwise.
> 1 votes

# Answer
# Retina 0.8.2, 17 bytes

```
\d+
$*
(1+),\1,\1

```

Try it online! Link includes test cases. Outputs `0` for a tower permutation, nonzero if not. Explanation: Uses @xnor's observation that each number in a tower permutation is greater than at least one of its neighbours. After unary conversion, the regex simply has to find a run of `1`s where both neighbouring runs of `1`s are at least as long and therefore neither neighbour is lower.

A direct positive test takes a massive 39 bytes:

```
\d+
$*
^(^1+,|1+\1)*((1+),(?!\3))*(1+)$

```

Try it online! Link includes test cases. Explanation: Looks for an ascending sequence followed by a descending sequence.
> 1 votes

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

```
a=>!a.some((x,i)=>x<a[i-1]&&x<a[i+1])
```

Attempt This Online!
> 1 votes

# Answer
# Vyxal, ~~9~~ 7 bytes

```
2lvƒ>ÞṠ

```

Try it Online! or Run all the test cases

*-2 bytes thanks to Aaroneous Miller*
> 1 votes

# Answer
# Dyalog APL: 10 bytes

Nothing really to say here, regular solution.

```
(⍳∘≢≡⍋)2>/

```
> 1 votes

# Answer
# Charcoal, 13 bytes

```
¬№⭆Φθκ›ι§θκ01

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a tower permutation, nothing if not. Explanation: Port of @xnor's Python 2 answer.

```
    θ           Input array
   Φ            Filtered where
     κ          Current index is not zero
  ⭆             Map over remaining elements and join
       ι        Current element
      ›         Is greater than
         θ      Unfiltered array
        §       Indexed by
          κ     Current index
¬№              Does not contain
           01   Literal string `01`
                Implicitly print

```
> 0 votes

# Answer
# Pari/GP, 41 bytes

```
f(a)=#a<3||(a[2]>min(a[1],a[3]))*f(a[^1])

```

Try it online!

A port of @xnor's Python answer.

---

# Pari/GP, 47 bytes

```
a->#a<3||prod(i=2,#a-1,a[i]>min(a[i-1],a[i+1]))

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 5 bytes

```
ü›D{Q

```

Try it online or verify all test cases.

**Explanation:**

```
ü      # For each overlapping pair of the (implicit) input-list:
 ›     #  Check if the first is larger than the second
  D    # Duplicate this list of checks
   {   # Sort the copy
    Q  # Check if the lists are still the same (thus it was sorted)
       # (after which the result is output implicitly)

```
> 0 votes

# Answer
# Perl 5, 47 bytes

```
sub{join('',map$_[-2]>pop?I:D,2..@_)=~/^I*D*$/}

```

Try it online!
> 0 votes

# Answer
# Java (JDK), 71, 63 bytes

```
h->{int b=0,s=1;for(int a:h)s=s*b>s*(b=a)?s>0?-1:0:s;return s;}

```

Try it online!

returns 0 if a castle, non zero (1 or -1) if a tower;

## Explanation

Starts with an expected minimum "slope" (s) of 1, Checks if difference between consecutive values matches the expected "direction" by multiplying them by the slope to normalize direction and ensuring next value is greater. If this check fails while the slope is 1, changes the slope to -1 for the remainder of the comparisons. If this fails while the slope isn't 1, changes to a slope of 0. Otherwise keeps the same slope as last iteration. Slope of 0 means a delta in an unexpected direction and therefore not a tower, also ensures all consecutive direction computations are 0 so computed slope of 0 'sticks'. Returns the slope 's'
> 0 votes

# Answer
# Desmos, ~~41~~ 39 bytes

*-2 bytes thanks to Aiden Chow*

```
D=sign(l-l[2...])
M(l)=1/max(D-D[2...])

```

The function `M` takes a list and returns `undefined` for tower permutations or `0.5` for non-tower permutations.

Try it (golfed)

Try it (prettified)

### Explanation

`D` is a helper quantity? macro? that takes the pairwise differences of a list `l` and gets the sign of each. The result will be a list of `1`s and `-1`s. If `l` is a tower permutation, all the `-1`s will come before the `1`s.

`M` then takes the result of `D` and gets *its* pairwise differences. For a tower permutation, this will be a list of `0`s and possibly a `-2`. For a non-tower permutation, there will be a `2` somewhere. Thus, the max of the second-level differences will be `0` for a tower permutation or `2` for a non-tower permutation. But there are also inputs of length 1 or 2 to be considered; they are too short for to have any second-level differences, which means that `max` returns `undefined`. To merge this result with the `0` from longer lists, we invert it, resulting in `undefined` for any tower permutation and `0.5` otherwise.

---

Alternate 39-byte solution that returns `1` instead of `0.5`:

```
D(l)=sign(l-l[2...])
M(l)=1/D(D(l)).max

```
> 0 votes

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


title: Will this makina program halt?

text:
# Question
Title: Will this makina program halt?
makina is a cell-based esolang composed of automata which move around a grid. These automata follow paths of instructions that direct their movement. Your task is to, given a makina program *using only the below instructions* (so a subset of normal makina) as input, output two distinct values depending on whether or not it is a loop. (If program flow comes to an arrow character that it has already visited then the program is a loop.)

## Instructions

* `^>v<` These instructions (arrows) set the direction of the automaton to the direction they point in.
* `I` This instruction halts automata going up or down, but does nothing to ones going left or right.
* `H` This instruction halts automata going left or right, but does nothing to ones going up or down.
* `O` This instruction does nothing to the automaton, acting like a sort of 4-way intersection.

All other characters (including spaces) halt the automaton, as does exiting the bounds of the program. The automaton starts in the top-left corner going right. You may assume programs are padded by spaces to be rectangular. This is , so shortest answer wins!

## Testcases

## Truthy

```
>>>v
v<<<

```

```
OOOv
H<<<
v

```

```
>>>v
v<I<
H>^
>^

```

```
>>>>v
v <<<

```

## Falsey

```
>>>v
^<<<

```

```
>v
^O<
>^

```

# Answer
> 4 votes
# Python, ~~182~~ 187 bytes

```
def f(s):
    i=j=h=0;d=1;v={0}
    while 1:
        if(t:=(i,j,h,d))in v:return 0
        try:c=s[i][j];0/(c-32)/(c&16 or(c&3^h))
        except:return 1
        if c&16:h=c>>6;d=(c>>4&c&2)-1
        v|={t};i+=h*d;j+=d-h*d
```

Attempt This Online!

Edit: the previous version did return *falsey* if the automaton visited twice a cell with `H` or `I`. Thanks to @tsh for the useful comments on the challenge post.

Brief explanation:

* `i` and `j` are the coordinates of the current cell (`i` is the row index, `j` is the column index);
* `v` is the set of the previously visited cells; if the current cell was already in `v`, it means that the automaton does not halt (hence `return 0`);
* the try block assigns to `c` the symbol in the current cell; it also checks if the coordinates refer to a cell present in the input, if the cell contains a space, or if the automaton halts encountering a `H` or a `I`;
* `h` stores the direction of the movement; if `h` is `0` the automaton is moving horizontally, if `h` is `1` it is moving vertically;
* `d` stores the magnitude of the movement, can be `-1` or `+1`

# Answer
> 2 votes
# JavaScript, 118 bytes

```
s=>[x=-1,y=0,d=4,...s+s].every(_=>d=1+'^<v>'.indexOf(c=s.split`
`[y+=(d-2)%2]?.[x+=(d-3)%2])||d*(c=='O'|c=='IH'[d%2]))

```

This answer disagree with the last 2 testcases.

```
f=

s=>[x=-1,y=0,d=4,...s+s].every(_=>d=1+'^<v>'.indexOf(c=s.split`
`[y+=(d-2)%2]?.[x+=(d-3)%2])||d*(c=='O'|c=='IH'[d%2]))

t= `
>>>v
v<<<

OOOv
H<<<
v

>>>v
^<<<

>v
^O<
>^

>>>v
v<I<
H>^
>^

>>>>v
v <<<

vv<v<X
>OOOOv
vOOOO<
>OOOOv
XO^<^<
`.trim().split(/\n\n+/);
t.forEach(s => {
  console.log(f(s));
});
```

Basic idea: A makina program with \\$n\\$ bytes source code will always terminate in at most \\$2n\\$ steps or it will never terminate.

# Answer
> 2 votes
# Ruby, ~~274~~ 233 bytes

```
->b{b=b.lines.map &:chars;x=y=0;d=[1,0];i={?>=>d,?<=>[-1,0],?^=>[0,-1],?v=>[0,1],?H=>0,?I=>1};loop{a=b[y][x] rescue break;a=~/[><^v]/? (d=i[a];b[y][x]=0): a=~/[IH]/? (break if d[i[a]]!=0): a==?O? 0: a==0? v: break;x,y=x+d[0],y+d[1]}}

```

Try it online! I've only put a couple test cases in the TIO link because the test cases in the question aren't all sorted correctly. (Some marked falsy are actually truthy.)

Takes a string. Errors if the input doesn't terminate, runs without error (returns `nil`) if it does. I'm proud of the golfed case statement and use of inline `rescue`, an arguably useless feature that's only really applicable in an edge case like this. Still trying to figure out how to golf `i` (a direction lookup hash) as well as optimize control flow in the function itself.

Ungolfed code:

```
def simulate_makina program
  program = program.chomp.split(?\n).map(&:chars)
  x, y = 0, 0
  dir = [1, 0]
  dirs = {?> => [1, 0], ?< => [-1, 0], ?^ => [0, -1], ?v => [0, 1], ?H => 0, ?I =>1}

  loop do
    a = program[y][x] rescue break
    case a
    when /[><^v]/
      dir = dirs[a]
      program[y][x] = 0
    when /[IH]/
      break if dir[dirs[a]] != 0
    when ?O
      0 # nop
    when 0
      v # raises a NameError
    else
      break
    end
    x, y = x + dir[0], y + dir[1]
  end
end

```

# Ruby, ~~252~~ 211 bytes

```
->b{x=y=0;d=[1,0];i={?>=>d,?<=>[-1,0],?^=>[0,-1],?v=>[0,1],?H=>0,?I=>1};loop{a=b[y][x] rescue break;a=~/[><^v]/? (d=i[a];b[y][x]=0): a=~/[IH]/? (break if d[i[a]]!=0): a==?O? 0: a==0? v: break;x,y=x+d[0],y+d[1]}}

```

Alternative answer that takes, instead of a string, a 2d array of characters. Again, errors if the input doesn't terminate and returns if it does. Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), 248 bytes

```
def h(i):
 p=P=d=0;D=1;v=[]
 while 1:
  try:p+=d;P+=D;r=i[p][P]
  except:return 1
  if[p,P]in v:return 0
  if'H'==r and D or'I'==r and d or'<>^vHIO'.find(r)<0:return 1
  L=r in'<>^v';v+=[[p,P]]*L
  if L:d=r>']'and' v'.find(r);D=r<'?'and' >'.find(r)

```

Try it online!

Wrong output for fourth falsy case but it seems like the output should in fact be truthy (the automaton hits a space and halts). I am waiting for clarification from the OP on this. Works on all other testcases.

Nothing too complex; just moves around as dictated by the input. The only part of note here is how to check whether to halt at an `H` or `I` location. For `H`, this is done by checking that `D`, which is the horizontal movement variable, is truthy, because it is truthy if it is not zero, and if it is not zero then the automaton is moving from the left or right. If it is zero then it is moving from the top or bottom. Similar for `I` but we check `d` (vertical movement) instead.

+6 bytes to fix bug pointed out by @tsh in comments, which means that the output for the third "falsey" case is now 1. However, it would appear that this is the correct answer.

# Answer
> 1 votes
# Charcoal, 56 bytes

```
ＷＳ⊞υιＰ⪫υ¶Ｗ⊕⌕⪪HIO>^<v¹ＫＫ¿‹ι⁴¿⁼⊖ι﹪φ²⎚Ｍ✳⊗φ«≔ιφ✳⊗φψ»≔ＫＫθ⎚⁼θψ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings and outputs `-` if the program does not halt, nothing if it halts. Explanation:

```
ＷＳ⊞υιＰ⪫υ¶

```

Input the instructions and print them to the canvas without moving the cursor.

```
Ｗ⊕⌕⪪HIO>^<v¹ＫＫ

```

While the character under the cursor is a valid instruction:

```
¿‹ι⁴

```

If this was an intersection-type character, then...

```
¿⁼⊖ι﹪φ²⎚

```

... if this intersection should halt the program then clear the canvas, causing the loop to exit, ...

```
Ｍ✳⊗φ

```

... otherwise move on through the intersection.

```
«≔ιφ✳⊗φψ»

```

Otherwise, update the direction, replace the current character with a null marker and move in the new direction.

```
≔ＫＫθ⎚⁼θψ

```

Output whether the cursor landed on a null marker, indicating an infinite loop.

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


title: Numbers in 2050

text:
# Question
Title: Numbers in 2050
It's 2050, and people have decided to write numbers in a new way. They want less to memorize, and number to be able to be written quicker.
For every place value(ones, tens, hundreds, etc.) the number is written with the number in that place, a hyphen, and the place value name. "zero" and it's place value does not need to be written.
The number 0 and negative numbers do not need to be handled, so don't worry about those.

#### Input:

The input will be a positive integer up to 3 digits.

#### Output:

The output should be a string that looks like something below.

Test cases:

```
56 => five-ten six
11 => ten one
72 => seven-ten two
478 => four-hundred seven-ten eight
754 => seven-hundred five-ten four
750 => seven-hundred five-ten
507 => five-hundred seven

```

This question would not be a dupe because that one has a bit more requirements.
"One" does not need to be printed unless it is in the ones place value.
This is , so normal golfing rules apply.
Shortest answer wins!
Good luck!

###### Imagine if numbers are actually written like this in the future...

# Answer
> 6 votes
# Vyxal `S`, 25 bytes

```
ẏṘ↵Z'h;ƛ∆ċ1∆ċ-';\-jȧ1∆ċ$∨

```

Try it Online!

or try a test suite.

Thank goodness for built-in number to word support

## Explained

```
ẏṘ↵Z'h;ƛ∆ċ1∆ċ-';\-jȧ1∆ċ$∨ # example input → 701
ẏṘ                        # range(len(input) - 1, -1, -1) → [2, 1, 0]
  ↵                       # 10 to the power of each item in that range → [100, 10, 1]
   Z                      # zip that with the digits of the input → [[7, 100], [0, 10], [1, 1]]
    'h;                   # keep only items where the digit of the input isn't 0 → [[7, 100], [1, 1]]
       ƛ                  # to each item in the remaining [digit, power10] list:
        ∆ċ                #   convert both digit and power10 to words → [["seven", "one hundred"], ["one", "one"]]
          1∆ċ-            #   remove any occurances of the word "one" from each → [["seven", " hundred"], ["", ""]]
              ';          #   and remove any empty strings - this makes it so that you have singleton lists for hundreds and tens and an empty list for ones if one is present → [["seven", " hundred"], []]
                \-j       #   join the result of that on "-" → ["seven- hundred", ""]
                   ȧ      #   remove whitespace → ["seven-hundred", ""]
                    1∆ċ$∨ #   get the first truthy item from that and "one" - this works because an empty string means that we want the word "one" → ["seven-hundred", "one"]
                          # The -S joins the result on spaces → "seven-hundred one"

```

# Answer
> 10 votes
# Perl 5 `-p`, 100 bytes

```
$a="{,{one,two,three,four,five,six,seven,eight,nine}";$_=(<"$a-hundred }$a-ten }$a}">)[$_];s/one-//g

```

Try it online!

Readable version:

```
#!perl -pl
$a="{,{one,two,three,four,five,six,seven,eight,nine}";
$_=(<"$a-hundred }$a-ten }$a}">)[$_];
s/one-//g

```

The idea here is simple: instead of trying to generate the number on the fly, generate a list of all 2050 numbers using a glob expression (which is much easier) and then index into that list. If $n is the list of numbers, we construct the glob `{,{$n}-hundred }{,{$n}-ten }{,{$n}}`. The only problem is that this glob expression will generate `one-ten` and `one-hundred`, which we can simply strip at the end with `s/one-//g`.

# Answer
> 5 votes
# Python \+ num2words, ~~162~~ ~~138~~ 137 bytes

```
lambda N:' '.join([((num2words(n)+'-'*(w>''),'')[n=='1'<w]+w)for n,w in zip('%3s'%N,['hundred','ten',''])if'0'<n])
from num2words import*
```

Attempt This Online!

Requires the package `num2words` to be installed, so won't run in the ATO link.

-24 bytes thans to **Jonathan Allan**

-1 byte, replaced `'%03s'%N` with `'%3s'%N`

# Answer
> 4 votes
# Charcoal, 74 bytes

```
⪫Φ⮌Ｅ⮌Ｓ⪫Φ⟦§⪪”↶⌈↶？#λ<∕CＳＧ∨⮌№¤"~^hφ﹪▶U⊕hU⦄w↷” ∧∨⊖ι¬κＩι§⪪”↶↧WaＫπ⁵1✂” ∧Ｉικ⟧λ-ι

```

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

```
     Ｓ                                      Input as a string
    ⮌                                       Reversed
   Ｅ                                        Map over digits
        ⟦                            ⟧      Tuple of
           ”...”                            Compressed digits string
          ⪪                                 Split on spaces
         §                                  Indexed by
                    ι                       Current digit
                   ⊖                        Decremented
                  ∨                         Logical Or
                      κ                     Current power of 10
                     ¬                      Is zero
                 ∧                          Logical And
                        ι                   Current digit
                       Ｉ                    Cast to integer
                           ”...”            Compressed places string
                          ⪪                 Split on spaces
                         §                  Indexed by
                                   ι        Current digit
                                  Ｉ         Cast to integer
                                 ∧          Logical And
                                    κ       Current power of 10
       Φ                                    Filtered where
                                      λ     String is not empty
      ⪫                                     Joined with
                                       -    Literal string `-`
  ⮌                                         Reversed
 Φ                                          Filtered where
                                        ι   String is not empty
⪫                                           Joined with spaces
                                            Implicitly print

```

# Answer
> 4 votes
# C (gcc), ~~193~~ ~~171~~ 169 bytes

* -2 thanks to ceilingcat

Recursively divides the input number, looking up each digit (except for `1` in non-ones position and `0`) and and appending the suffix (except for ones position.)

```
g(v,s,i){v&&g(v/10,s?"hundred":"ten"),(i=v%10)&&printf("%3$.5s%2$s%s "+(i<2&&s)*10,s?:"",!s+"-","one\0 two\0 threefour\0five\0six\0 seveneightnine"+~-i*5);}f(v){g(v,0);}

```

Try it online!

# Answer
> 2 votes
# JavaScript (V8), ~~162~~ ~~153~~ ~~151~~ 148 bytes

-3 bytes thanks to Arnauld.
-6 bytes by merging the handling of 10's and 100's.
-2 bytes thanks to Arnauld, again.
-3 bytes by moving the floor operation, thanks to Shaggy.

```
f=(n,p)=>n>9?f(n/(m=n>99?100:10)|0,m%4?'ten ':'hundred ')+f(n%m):n?--n|!p?'one,two,three,four,five,six,seven,eight,nine'.split`,`[n]+[p&&'-'+p]:p:''

```

Try it online!

Ungolfed

```
f = (n, p) =>
  n > 9 ? // check if we should handle 10's or 100's
    f(
      n / (m = n > 99 ? 100 : 10) | 0, // check what mod to use, then floor divide
      m % 4 ? 'ten ' : 'hundred ' // check what place to use
    ) + f(n % m) :
  n ? // if 9 >= n > 0
    --n | !p ? // if n > 1 or p ('ten' or 'hundred') is not defined we need to find the name of n
      'one,two,three,four,five,six,seven,eight,nine'.split`,`[n] +
      [p && '-' + p] : // add p if we have it
    p : // return p if n = 1
  '' // return '' if n = 0

```

# Answer
> 2 votes
# Factor \+ `math.text.english math.text.utils`, ~~138~~ ~~136~~ 126 bytes

```
[ 1 digit-groups [ 10^ [ number>text ] bi@ "-"glue R/ one[- ]|-one$|zero.*/ ""re-replace ] map-index reverse harvest " "join ]

```

Try it online!

## Explanation

```
Code                     | Data stack                              | Comment
============================================================================================================
                         ! 478
1 digit-groups           ! { 8 7 4 }
           <<inside the map-index quotation now; first iteration>>
                         ! 8 0                                       (digit, index)
10^                      ! 8 1
[ number>text ] bi@      ! "eight" "one"
"-"glue                  ! "eight-one"
R/ one[- ]|-one$|zero.*/ ! "eight-one" R/ one[- ]|-one$|zero.*/      (push a regexp literal on the data stack)
""re-replace             ! "eight"
          <<outside the map-index quotation now>>
map-index                ! { "eight" "seven-ten" "four-hundred" }
reverse                  ! { "four-hundred" "seven-ten" "eight" }
harvest                  ! { "four-hundred" "seven-ten" "eight" }    (remove empty strings)
" "join                  ! "four-hundred seven-ten eight"

```

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

```
o,i,z;main(a,c)char**c;{for(o=strlen(c[1]);z=c[1][i]-49,printf("%s%s%s ",z|o-i==1?"zero\0one\0two\0three\0four\0five\0six\0seven\0eight\0nine"+"059=CHMQW]"[z+1]-48:"",z&&o+~i?"-":"",o-i-2?o-i-3?"":"hundred":"ten"),++i-o;);}

```

Try it online!

Thanks to Mukul Kumar for basis, fixed what I perceived to be incorrect output, and shaved down by switching to C and embracing the sketchiness of golf C.

Updates based on issues found and golf contributed by Arnauld

Thanks to ceilingcat for some more C golf sketchiness.

# Answer
> 2 votes
# Python, ~~198~~ 188 bytes

```
lambda m:" ".join([r[int(i)]for i,r in zip('%3s'%m,[[c+s for c in",one,two,three,four,five,six,seven,eight,nine".split(",")]for s in['-hundred','-ten','']])if"0"<i>" "]).replace("one-","")
```

Attempt This Online!

Inspired by Sisyphus's answer. Generates three lists of the number string for each of the hundreds, tens and ones. Indexes each list by it's respective value in the input, then gets rid of `one-`

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

```
n=>['hundred','ten',''].flatMap(t=>(c=',,two,three,four,five,six,seven,eight,nine'.split`,`[p=(n*=10)/1e3%10|0])?t?c+'-'+t:c:p?t||'one':[]).join` `

```

Try it online!

# Answer
> 2 votes
# Python 3.8, no library, 184 bytes

Late to the party, but here's my answer. jezza\_99 answer using library is unbeatable!

```
n=input()
for i,o in zip([' one two three four five six seven eight nine'.split(' ')[int(d)]for d in n],['-hundred','-ten',''][-len(n):]):
 if i:print((i+o).replace('one-',''),end=' ')

```

Try it online!

---

***Commented code***

```
# input: get number to be rewritten in words
# n will be a string
n = input('Input number n to be translated into words (0 < n < 1000): ')

# list of literal digit
# specify split(' ') to have empty string corresponding to 0
literal_digit = ' one two three four five six seven eight nine'.split(' ')
# we will get
# ['', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']

# list of literal digit corresponding to the input number
# expanded list comprehension [literal_digit[int(d)] for d in n]
literal_number = []
for d in n:
    literal_number.append(literal_digit[int(d)])
# for example '438' -> ['four', 'three', 'eight']

# list of literal orders of magnitude
# we have to consider only the elements according to the length of the number
ord_mag = ['-hundred', '-ten', ''][-len(n):]
# for example '43' -> len = 2 -> start at -2
# we will get only ['-ten', '']

# build the number string translated into words
# loop over the literal number and the corresponding order of magnitude
for i, o in zip(literal_number, ord_mag):

    # check if digit is 0 -> '': don't print
    if i:

        # not 0

        # we must print the literal digit and its order of magnitude
        string = i + o

        # if digit is one
        # we must print only the order of magnitude,
        # otherwise only 'one' if the magnitude is unit
        string = string.replace('one-', '')
        # this can be done because the '-' is defined in the order of magnitude

        # print the string, concatenating the digit on the same line
        print(string, end=' ')

```

# Answer
> 1 votes
# 05AB1E, 53 bytes

```
“0€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“#ISèāR… —¿°¡#sèøʒнa}€á'-ýðý„€µ-K

```

Try it online or verify all test cases.

**Explanation:**

```
“0€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“
               # Push dictionary string "0 one two ... eight nine"
 #             # Split it on spaces
  I            # Push the input-integer
   S           # Convert it to a list of digits
    è          # Index those into the list
ā              # Push a list in the range [1,length] (without popping)
 R             # Reverse it to range [length,1]
  … —¿°¡       # Push dictionary string "  ten hundred"
        #      # Split it on spaces: ["","","ten","hundred"]
         s     # Swap so the [length,1] integer-list is at the top
          è    # 0-based index into the ["","","ten","hundred"]
ø              # Create pairs of the two lists
 ʒ             # Filter, to only keep the pairs where:
  н            #  the first item
   a           #  only contains letters
               #  (this removes ["0","hundred"], ["0","ten"], and ["0",""] pairs)
 }€            # After the filter: map over each remaining pair:
   á           #  Only keep strings consisting solely of letters
               # (this removes the "" from the last pair)
    '-ý       '# Join each inner pair with "-" delimiter
       ðý      # Then join these strings with " " delimiter
         „€µ-  # Push dictionary string "one-"
             K # Remove all those substrings
               # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“0€µ‚•„í†ìˆÈŒšï¿Ÿ¯¥Š“` is `"0 one two three four five six seven eight nine"`; `… —¿°¡` is `" ten hundred"`; and `„€µ-` is `"one-"`.

# Answer
> 1 votes
# Retina 0.8.2, 102 bytes

```
\B
-ten¶
ten(¶..)
hundred$1
A`0
¶

1-

1
one
2
two
3
three
4
four
5
five
6
six
7
seven
8
eight
9
nine

```

Try it online! Link includes test cases. Explanation:

```
\B
-ten¶

```

If there is more than one digit then assume the leading digit is a ten. Also split the digits onto their own line.

```
ten(¶..)
hundred$1

```

If there's a second digit then correct it to a hundred.

```
A`0

```

Delete any lines containing a `0`.

Join the lines together again.

```
1-

```

`10` and `100` should just be ten and hundred.

```
1
one
2
two
3
three
4
four
5
five
6
six
7
seven
8
eight
9
nine

```

Turn the remaining digits into words.

Bonus: Here's a version that works up to `9999` for 116 bytes: Try it online! Link includes test cases. (Sadly the three digit version is 103 bytes.)

# Answer
> 1 votes
# PHP, 195 bytes

```
<?php foreach(str_split(substr("00".fgets(STDIN),-3))as$i=>$c)echo trim($c>0?[0,$i>1?"one":"","two","three","four","five","six","seven","eight","nine"][$c].["-hundred","-ten",""][$i]." ":"","-");

```

Input via STDIN, output via echo

Try it online!

---

De-golf:

```
<?php
    $inp = substr("00".fgets(STDIN),-3);
        // here I take input and append leading zeros, so as the total lengh is 3
        //   (for example, 13 becomes 013)
    $arr = str_split($inp);
        // string to array of chars

    foreach($arr as $index => $digit){
        $num_array = [0, $index > 1 ? "one":"","two","three","four","five","six","seven","eight","nine"]; // here one is hidden unless it's on the last position
        $name_array = ["-hundred","-ten",""];
        $chunk = $num_array[$digit].$name_array[$index]." ";
        $chunk = $digit > 0 ? $chunk : ""; // empty string if it's zero
        $trimmed = trim($chunk, "-"); // to dispose of "-" at the beginning of the string (this could happen if we drop "one" in "one-ten", so just "-ten" left)
        echo $trimmed;
    }
?>

```

---

***Fun note** \- I didn't expect PHP doesn't complain here:*

# Answer
> 1 votes
# Python 2, 209 bytes

```
i=input();t,n="0 one two three four five six seven eight nine".split(),map(int,"00"+`i`)[-3:]
print ("",t[n[0]]+"-hundred ")[n[0]and i>99]+("",(t[n[1]]+"-","")[n[1]<2]+"ten ")[n[1]and i>9]+("",t[n[2]])[n[2]>0]

```

Try it online!

Python 2 because:

1. Accepts integers directly as input
2. \`\` converts integer to string
3. Can directly index the result of map without converting to a list
4. No () required by the print

# Answer
> 1 votes
# Julia, ~~185~~ 158 bytes

```
n+m+s=!(n÷m)*"-$s "*!(n%m)
!n=replace(n<10 ? split(" one two three four five six seven eight nine"," ")[-~n] :
n<100 ? n+10+:ten : n+100+:hundred,"one-"=>"")
```

Attempt This Online!

# Answer
> 1 votes
# C++, 277 bytes

```
#include <iostream>
main(int a,char*c[]){char s[9];int q[]={0,4,7,10,15,19,23,26,31,36,40},n,m,o=strlen(c[1]),i=0;do{m=c[1][i]-48;n=q[m];strcpy_s(s,"zeroonetwothreefourfivesixseveneightnine"+n,q[m+1]-n);std::cout<<((o-i==2)?"ten-":(o-i==3)?"hundred-":"")<<s<<' ';}while(++i<o);}

```

## Ungolfed

```
#include <iostream>

int main(int a, char* c[]) {
    char s[9];
    int q[] = { 0,4,7,10,15,19,23,26,31,36,40 }, n, m, o = strlen(c[1]), i = 0;
    do {
        m = c[1][i] - 48;
        n = q[m];
        strncpy_s(s, 9, "zeroonetwothreefourfivesixseveneightnine" + n, q[m + 1] - n);
        std::cout << ((o - i == 2) ? "ten-" : (o - i == 3) ? "hundred-" : "") << s << ' ';
    } while (++i < o);
}

```

**Input** comes from command-line arguments

**Reason for using C++ over C**

* apparantly some compilers include `string.h` header in `iostream`

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


title: Antsy permutations

text:
# Question
Title: Antsy permutations
## Introduction

Suppose you have a ruler with numbers from **0** to **r-1**. You place an ant between any two of the numbers, and it starts to crawl erratically on the ruler. The ruler is so narrow that the ant cannot walk from one position to another without walking on all the numbers in between. As the ant walks on a number for the first time, you record it, and this gives you a permutation of the **r** numbers. We say that a permutation is *antsy* if it can be generated by an ant in this way. Alternatively, a permutation **p** is antsy if every entry **p\[i\]** except the first is within distance 1 from some previous entry.

## Examples

The length-6 permutation

```
4, 3, 5, 2, 1, 0

```

is antsy, because **3** is within distance 1 of **4**, **5** is within distance 1 of **4**, **2** is within distance 1 from **3**, **1** is within distance 1 from **2**, and **0** is within distance 1 from **1**. The permutation

```
3, 2, 5, 4, 1, 0

```

is not antsy, because **5** is not within distance 1 of either **3** or **2**; the ant would have to pass through **4** to get to **5**.

## The task

Given a permutation of the numbers from **0** to **r-1** for some **1 ≤ r ≤ 100** in any reasonable format, output a truthy value if the permutation is antsy, and a falsy value if not.

## Test cases

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

```

Fun fact: for **r ≥ 1**, there are exactly **2r-1** antsy permutations of length **r**.

# Answer
## Pyth, 7 bytes

```
/y+_QQS

```

Try it online. (Only small test cases are included due to exponential run-time.) Outputs 2 for Truthy, 0 for Falsey.

```
/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

```

In other words,

```
lambda l: subseq(sorted(l), concat(reverse(l), l))

```

where `subseq` outputs whether the elements of the first list appear in order in the second list, not necessarily adjacent. The `subseq` is done in Pyth by taking all subsets of the second list, which keep the order of the elements, and counting the number of occurrences of the first list. This takes exponential time.

Why does this work? For a permutation to be antsy, stepping from 0 to n-1 must consist of going only left, then going only right. This is because the elements greater than the first element must increase left to right, and those less than it must decrease left to right.

```
[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1
 2  ^
    3     ^
          4

```

If we mirror the list by putting a reversed copy to its left, this walk now only goes right.

```
[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |
 0     ^      |
       1      | ^
              | 2  ^
              |    3     ^
              |          4

```

Conversely, any rightward of this mirror list corresponds to a left-then-right walk of the original list. This rightward just is a sorted subsequence of 0 to n-1. In an antsy list, this sorted subsequence is unique, except for an arbitrary choice between the two adjacent copies of the original first element.
> 19 votes

# Answer
## Haskell, 46 bytes

```
(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

```

Checks whether the vector difference of the running maxima and the running minima is \[0,1,2,3...\].

```
l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]
difference =    [0, 1, 2, 3, 4]

```

Zgarb saved 2 bytes with `(%)=scanl1`.
> 12 votes

# Answer
# JavaScript (ES6), 45

```
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

```

I thought it's too simple to need as explanation, but there is a trick, and just in case, here is my first version, pre-golf

```
a => {
  k = []; // I'll put a 1 in this array at position of each value
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

```

Note: in the golfed code `a` is used instead of `k`, as I need no reference to the original array inside the `every` call. So I avoid to pollute the global namespace reusing the parameter

**Test**

```
antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g),
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')
```
> 9 votes

# Answer
## Python 2, 49 bytes

```
f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

```

Checks whether each prefix of the list contains all numbers between its min and max inclusive. It does so by checking if the difference of the max and min is less than its length.

---

**54 bytes:**

```
f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

```

Checks if the last element is either one less than the min of the other elements, or one more than their max. Then, removes the last element and recurses. On a single-element list, outputs True.

This can also be checked via an amusing but longer list comprehension.

```
lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

```

I'd like to use the inequality `min(l)-2<l.pop()<max(l)+2`, but the `pop` needs to happen first. Using a program to output via error code would likely be shorter.
> 6 votes

# Answer
## Mathematica, 42 bytes

```
!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

```

Uses pattern matching to try and find a prefix `a` whose maximum difference from the next element `b` is greater than `1` (and negating the result of `MatchQ`).
> 6 votes

# Answer
# Perl, ~~39~~ ~~38~~ 35 bytes

Includes +1 for `-p`

Give sequence on STDIN:

```
antsy.pl <<< "2 1 3 0"

```

`antsy.pl`:

```
#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++

```
> 6 votes

# Answer
# MATL, 11 bytes

```
&-|R1=a4L)A

```

Try it online! Or verify all test cases.

### Explanation

This computes a matrix of all pairwise absolute differences and keeps the upper triangular part. The result is true iff there is at least a 1 value in all columns except the first.

```
&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results

```
> 4 votes

# Answer
# R, ~~72~~ ~~64~~ 60 bytes

```
v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

```

A permutation is antsy if and only if all its left subpermutations are continuous (i.e. have difference one when sorted).

~~If input is guaranteed to have length more than one, then we can replace `1:sum(1|v)` with `seq(v)`, which saves four bytes.~~

The `seq(v)` in the if condition behaves differently when the input is of length one --- it generates the sequence `1:v` instead of `seq_along(v)`. However, fortunately, the output turns out to be `TRUE` in this case, which is the desired behaviour. The same also happens for zero-length input.

In R, `T` is a preset variable equal to `TRUE` (but R allows you to redefine it). `TRUE` is also deemed to be equal to `1`.

Thanks to @Billywob for some helpful improvements to the original solution.
> 4 votes

# Answer
# Jelly, ~~9~~ ~~8~~ 7 bytes

```
;@UŒPċṢ

```

Try It Online!

A Jelly translation of xnor's answer.

Old solutions:

```
;\Ṣ€IỊȦ
;\Ṣ€IE€P

```

Try it online!

Works very similarly to my Pyth answer below:

```
;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?

```
> 3 votes

# Answer
# 05AB1E, 7 bytes

```
Âìæ¹{¢O

```

Try it online! or as a modified test suite.

**Explanation**

Uses the process described by xnor in his brilliant Pyth answer.
Returns 2 for truthy instances and 0 for falsy.

```
Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)

```
> 3 votes

# Answer
# Brain-Flak ~~302 264~~ 256 Bytes

Thanks to Wheat Wizard for saving 46 bytes

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

```

The top of the stack will be a 1 for truthy and a 0 for falsy.

Truthy: Try it Online!
Falsy: Try it Online!

The idea is to hold the minimum and maximum number that the ant has visited in the off stack. Then compare each number to both of those and update the appropriate one. If the next number is not 1 less than the min or 1 more than the max, break out of the loop and return false.

---

**Brief Explanation:**

```
([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack

```
> 3 votes

# Answer
## CJam (21 20 bytes)

```
{:A,{_)A<$2*)@-#},!}

```

Online test suite

### Dissection

This uses the observation by xnor in his Haskell answer that the difference between the maximum and minimum of the first `n` elements should be `n-1`.

```
{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

```

---

### Alternative approach (also 20 bytes)

```
{_{a+_)f-:z1&,*}*^!}

```

Online test suite

This checks directly that each element after the first is at distance 1 from a previous element. Since the input is a permutation and hence doesn't repeat values, this is a sufficient test. Thanks to Martin for a 1-byte saving.

### Dissection

```
{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}

```
> 3 votes

# Answer
## Perl, 63 bytes

Note that @Gabriel Banamy came up with a shorter (55 bytes) answer. But I think this solution is still interesting, so I'm posting it.

The bytes count includes 62 bytes of code and `-n` flag.

```
s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

```

To run it :

```
perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

```

**Short explanations** : converts each number `k` to the unary representation of `k+1` (that `+1` is needed so the `0`s don't get ignored). Then for each number `k+1` (expressed in unary as `1(1*)`), we look if either `k` (`$1` holds `k`) or `k+2` (which is then `11$1`) are present in the preceding string (referenced by `$-backtick`). If no, then we set `$.` to zero. At then end we print `$.` which will be `1` if we never set it to zero, or zero otherwise.
> 3 votes

# Answer
# Java, ~~100~~ ~~98~~ ~~79~~ 75 bytes

```
a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

```

Formerly:

```
a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

```

Saved 3 bytes by replacing `true` and `false` with `1>0` and `0>1`.

Saved 23 bytes thanks to excellent suggestions from Peter Taylor!

Ungolfed:

```
a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

```

Keep track of the highest and lowest values seen so far as `m` and `n`; only accept a new value if it is `m + 1` or `n - 1` i.e. the next higher or lower value; initialize the high value, `m`, to one less than the first element so that it will "match" the first time around the loop. Note: this is a linear-time, online algorithm. It requires only three words of memory, for the current, highest-so-far, and lowest-so-far values, unlike a lot of the other solutions.

If the next value misses both the high and low ends of the range, the lowest-so-far value is set to `-1` and then the low end can never proceed and reach zero. We then detect an antsy sequence by checking whether the low value, `n`, reached zero.

(Unfortunately this is less efficient because we always have to look at the entire sequence rather than bailing out after the first *wrong* number, but it's hard to argue with a 23-byte savings (!) when other solutions are using O(n^2) and exponential time approaches.)

Usage:

```
import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

```

Note: this can also be written without taking advantage of Java 8 lambdas:

# Java 7, 89 bytes

```
boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

```
> 3 votes

# Answer
# Jelly, 5 bytes

```
Ụ<ƝṢƑ

```

Try it online!

In Is it a tower permutation?, xnor comments

> This is closely related to Antsy Permutations -- a tower permutation is one whose inverse permutation, read backwards as a list, is antsy.

Combining pxeger's answer to that question with  (Grade, which inverts permutations) yields a short Jelly answer to this question.

Instead of reversing the list before inverting the permutation, which would cost another byte, I just check for "anti-towers" by changing `>` to `<`.
> 3 votes

# Answer
# Pyth (fork), 13 bytes

```
!sstMM.+MSM._

```

No Try It Online link for this fork of Pyth. The fork includes the deltas function `.+`, which is not part of the standard Pyth library.

Explanation:

```
           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.

```
> 2 votes

# Answer
# J, 14 bytes

```
/:~-:>./\-<./\

```

This is based on @xnor's method.

## Explanation

```
/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted

```
> 2 votes

# Answer
# Perl, ~~66~~ 54 +1 = 55 bytes

+1 byte for `-n`.

```
s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

```

Explanation:

```
s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

```

Prints 0 if false, 1 if true.

-11 bytes thanks to @Dada
> 2 votes

# Answer
## Brainfuck, 60 bytes

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

```

The permutation is given as bytes with no separators and no terminating newline. Since `\x00` occurs in the input, this is designed for implementations with `EOF = -1`. The output is `\x00` for false and `\x01` for true.

If a permutation of `\x01` up to `chr(r)` is allowed, then we can replace all instances of `,+` with `,` for a score of 57 with an `EOF = 0` implementation.

Try it online (57-byte version): Input can be given as a permutation of any contiguous range of bytes excluding `\x00`, and the output will be `\x00` for false and the minimum of the range for true.

We keep track of the min and max seen so far, and for each character after the first, check whether it is min-1 or max+1 or neither. In the case of neither, move the pointer outside the normal working space so that the local cells become zero.

The memory layout of the normal working space at the beginning of the main loop is

`c a b 0 0`

where `c` is the current character, `a` is min, and `b` is max. (For the 60-byte version, everything is handled with an offset of 1 because of `,+`.)
> 2 votes

# Answer
# Vyxal, 8 bytes

```
⇧2lvƒ<ÞṠ

```

Try it Online!

Like Lynn's Jelly answer, takes my Vyxal answer to Is it a tower permutation?, adds a grade up at the beginning, and changes `>` to `<`.

## How?

```
⇧2lvƒ<ÞṠ
⇧        # Grade up (i.e. sort indices by corresponding values)
 2l      # Get overlapping pairs
   vƒ<   # For each pair, check if the first item is less than the second
      ÞṠ # Is it sorted in ascending order?

```
> 2 votes

# Answer
# Brachylog, 22 bytes

```
:@[fb:{oLtT,Lh:T:efL}a

```

Try it online!

### Explanation

I haven't found a concise way of checking whether a list contains consecutive integers or not. The shortest I found is to generate a range between the first and last element of that list and check that that range is the original list.

```
:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L

```
> 1 votes

# Answer
## Batch, 133 bytes

```
@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

```

Takes input as command-line arguments. Exits with error level 0 for success, 1 for failure.
> 1 votes

# Answer
## Java, 170 bytes

```
boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

```

Array `x` has values from 0 to maximum number in order (Python would be much better here...). The loop goes backwards trying to match the lowest (`x[b]`) or the highest (`x[e]`) number not yet encountered; if it does, that number could be reached in that step.

Test code here.
> 1 votes

# Answer
# 05AB1E, 7 bytes

```
ηε{¥P}P

```

Try it online!
> 1 votes

# Answer
# , 57 bytes

```
function(x,y=x[-1],`!`=cummin){y[]=y+1-!x&y-1+!-x;any(y)}

```

Try it online!

Completely different and somewhat shorter approach to JDL's previous R answer.

Returns `FALSE` for antsy sequences, `TRUE` for not-antsy sequences.
Add two bytes to reverse the output to truthy for antsy sequences: 59 bytes, but save 4 bytes by taking input using `scan`: 55 bytes
> 1 votes

# Answer
# Java 7, ~~170~~ 169 bytes

```
import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

```

**Ungolfed & test code:**

Try it here.

```
import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

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

```

**Output:**

```
true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true

```
> 0 votes

# Answer
# Mathematica, 47 bytes

A little longer than Martin Ender's solution (surprise surprise!). But it's one of my more unreadable efforts, so that's good :D

```
#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

```

Explanation:

```
#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list

```
> 0 votes

# Answer
# \[JavaScript\], 54 bytes

```
e=>e.every((f,m)=>!m||e.some((e,o)=>o<m&&(e-f)**2==1))

```

Try it online!
> 0 votes

---
Tags: code-golf, permutations, decision-problem
---


title: Make me a metasequence

text:
# Question
Title: Make me a metasequence
# Background

For this challenge, a 'metasequence' will be defined as a sequence of numbers where not only the numbers themselves will increase, but also the increment, and the increment will increase by an increasing value, etc.

For instance, the tier 3 metasequence would start as:

`1 2 4 8 15 26 42 64 93 130 176`

because:

```
    1 2 3  4  5  6  7  8   9       >-|
      ↓+↑ = 7                        | Increases by the amount above each time
  1 2 4 7  11 16 22 29 37  46  >-| <-|
                                 | Increases by the amount above each time
1 2 4 8 15 26 42 64 93 130 176 <-|

```

# Challenge

Given a positive integer, output the first twenty terms of the metasequence of that tier.

## Test cases

Input: `3` Output: `[ 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160 ]`

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

Input: `5` Output: `[ 1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664 ]`

Input: `13` Output: `[ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16383, 32752, 65399, 130238, 258096, 507624 ]`

As you may realise, the first \\$t+1\\$ items of each sequence of tier \\$t\\$ are the first \\$t+1\\$ powers of 2...

# Rules

* Standard loopholes apply
* This is , so shortest answer in bytes wins

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

```
20ḶcþŻS

```

Try it online!

```
   cþ       Table of binom(x,y) where:
20Ḷ           x = [0..19]
     Ż        y = [0..n]    e.g.  n=3 → [[1, 1, 1, 1, 1, 1,  …]
                                         [0, 1, 2, 3, 4, 5,  …]
                                         [0, 0, 1, 3, 6, 10, …]
                                         [0, 0, 0, 1, 4, 10, …]]

      S     Columnwise sum.           →  [1, 2, 4, 8, 15, 26, …]

```

This uses @alephalpha’s insight that $$\text{meta-sequence}\_n(i) = \sum\_{k=0}^n \binom ik.$$

# Answer
> 24 votes
# Wolfram Language (Mathematica), 34 bytes

```
0~Range~19~Binomial~i~Sum~{i,0,#}&

```

Try it online!

The tier \\$n\\$ metasequence is the sum of the first \\$n+1\\$ elements of each row of the Pascal triangle.

# Answer
> 19 votes
# Haskell, 34 bytes

```
(iterate(init.scanl(+)1)[1..20]!!)

```

Uses 0-indexed inputs (`f 4` returns tier 5.)

# Haskell, 36 bytes

```
f 1=[1..20]
f n=init$scanl(+)1$f$n-1

```

Try it online! Uses 1-indexed inputs (`f 5` returns tier 5.)

# Explanation

`scanl (+) 1` is a function that takes partial sums of a list, starting from (and prepending) `1`.

> For example: `scanl (+) 1 [20,300,4000]` equals `[1,21,321,4321]`.

It turns out that tier \\$n\\$ is just this function applied \\$ (n-1) \\$ times to the list \\$\[1,2,3,\dots\]\\$.

(Or equivalently: \\$n\\$ times to a list of all ones.)

We use either `init` or `[1..20-n]` to account for the list getting longer by \\$1\\$ every application.

# Answer
> 8 votes
# Brain-Flak, ~~84~~ 82 bytes

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

```

Try it online!

## Annotated

```
<>               Switch to the off stack
((()()()()()){}) Push 10
{({}[((()))])}{} Make twice that many 1s
<>               Switch back
{                While ...
({}[(())]<       Subtract one from the input and push 1
<>               Switch
{                For every x on the stack
({}<>({}))<>     Remove x and add it to a copy of the other TOS
}                End loop
<>{}             Remove 1 element to keep it 20
{({}<>)<>}       Copy everything back to the other stack
>)}<>            End scopes and loops

```

Try it online!

# Answer
> 8 votes
# , 36 bytes

```
rowSums(outer(0:19,0:scan(),choose))

```

Try it online!

Thanks to @Giuseppe for suggesting `outer`.

This is based on the approach @alephalpha described

# Answer
> 6 votes
# dzaima/APL REPL, 14 bytes

```
(+\1,19↑)⍣⎕⍳20

```

Try it online!

```
(+\1,19↑)⍣⎕⍳20
(       )⍣⎕     repeat the function below input times:
 +\               cumulative sum of
   1,             1 prepended to
     19↑          the first 19 items of the previous iteration
           ⍳20  starting with the first 20 integers

```

# Answer
> 6 votes
# Python 2, ~~69~~ ~~58~~ 55 bytes

*Saved bytes thanks to ovs and Jo King; also, it works in Python 3 now as well.*

```
m=lambda t:[1+sum(m(t-1)[:n])for n in range(~t and 20)]

```

Try it online!

### The math

Let \\$a(t,n)\\$ be the \\$n^{th}\\$ term (0-indexed) of the sequence at tier \\$t\\$. A little analysis leads to the following recurrence formula:

$$ a(t,n) = 1+\sum\_{i=0}^{n-1}a(t-1,i) $$

Working backwards, we define \\$a(0,n) = 1\\$ and \\$a(-1,n) = 0\\$ for all \\$n\\$. These definitions will simplify our base case.

### The code

We define a function `m(t)` that returns the first 20 elements of the sequence at tier `t`. If `t` is nonnegative, we use the recursive formula above; if `t` is `-1`, we return an empty list. The empty list works as a base case because the result of each recursive call is sliced (`[:n]`) and then summed. Slicing an empty list gives an empty list, and summing an empty list gives `0`. That's exactly the result we want, since tier \\$-1\\$ should behave like a constant sequence of all \\$0\\$'s.

```
m=lambda t:                     # Define a function m(t):
 [          ]                   # List comprehension
     for n in range(         )  # for each n from 0 up to but not including...
                    ~n and 20   # 0 if n is -1, else 20:
  1+sum(          )             # a(t,n) = 1 + sum of
              [:n]              # the first n elements of
        m(t-1)                  # the previous tier (calculated recursively)

```

# Answer
> 4 votes
# Pari/GP, 36 bytes

```
n->vector(20,i,i<n+2)*matpascal(19)~

```

Try it online!

A port of my Mathematica answer.

---

# Pari/GP, 39 bytes

```
n->Vec(sum(i=1,n+1,(1/x-1)^-i)+O(x^21))

```

Try it online!

---

# Pari/GP, 40 bytes

```
n->Vec((1-(1/x-1)^-n++)/(1-2*x)+O(x^20))

```

Try it online!

---

The generating function of the tier \\$n\\$ metasequence is:

$$\sum\_{i=0}^n\frac{x^i}{(1-x)^{i+1}}=\frac{1-\left(\frac{x}{1-x}\right)^{1+n}}{1-2x}$$

# Answer
> 4 votes
# Perl 6, ~~34~~ 32 bytes

*-2 bytes thanks to Jo King*

```
{(@,{[\+] 1,|.[^19]}...*)[$_+1]}

```

Try it online!

### Explanation

```
{                              }  # Anonymous block
   ,                ...*  # Construct infinite sequence of sequences
  @  # Start with empty array
    {              }  # Compute next element as
     [\+]     # cumulative sum of
          1,  # one followed by
            |.[^19]  # first 19 elements of previous sequence
 (                      )[$_+1]  # Take (n+1)th element

```

# Answer
> 4 votes
# Python 3.8 (pre-release), 62 bytes

```
f=lambda n:[t:=1]+[t:=t+n for n in(n and f(n-1)[:-1]or[0]*19)]

```

Try it online!

---

## Explanation

```
f=lambda n:     # funtion takes a single argument
     [t:=1]     # This evaluates to [1] and assigns 1 to t
                # assignment expressions are a new feature of Python 3.8
       +        # concatenated to
     [  ....  ] # list comprehension

# The list comprehesion works together with the
# assignment expression as a scan function:
[t := t+n for n in it]
# This calculates all partial sums of it
# (plus the initial value of t, which is 1 here)

# The list comprehension iterates
# over the first 19 entries of f(n-1)
# or over a list of zeros for n=0
 for n in (n and f(n-1)[:-1] or [0]*19)

```

# Answer
> 4 votes
## R (63 47 bytes)

```
function(n,k=0:19)2^k*pbeta(.5,pmax(k-n,0),n+1)

```

Online demo. This uses the regularised incomplete beta function, which gives the cumulative distribution function of a binomial, and hence just needs a bit of scaling to give partial sums of rows of Pascal's triangle.

## Octave (66 46 bytes)

```
@(n,k=0:19)2.^k.*betainc(.5,max(k-n,1E-9),n+1)

```

Online demo. Exactly the same concept, but slightly uglier because `betainc`, unlike R's `pbeta`, requires the second and third arguments to be greater than zero.

Many thanks to Giuseppe for helping me to vectorise these, with significant savings.

# Answer
> 3 votes
# , ~~59~~ 49 bytes

```
f=function(n)`if`(n,Reduce(`+`,f(n-1),1,,T),1:20)

```

Try it online!

Recursively `Reduce` with `+`, `init=1` and `accumulation=TRUE` to avoid having to subset. Thanks to Criminally Vulgar for suggesting the recursive approach!

# Answer
> 3 votes
# Wolfram Language (Mathematica), 42 bytes

```
Nest[FoldList[Plus,1,#]&,Range[21-#],#-1]&

```

Try it online!

# Answer
> 3 votes
# Retina, 59 bytes

```
.+
19*$(_,

```

Replace the input with 19 `1`s (in unary). (The 20th value is 0 because it always gets deleted by the first pass through the loop.)

```
"$+"{`
)`

```

Repeat the loop the original input number of times.

```
(.+),_*
_,$1

```

Remove the last element and prefix a `1`.

```
_+(?<=((_)|,)+)
$#2*

```

Calculate the cumulative sum.

```
_+
$.&

```

Convert to decimal.

Try it online!

# Answer
> 3 votes
# JavaScript (Node.js), 58 bytes

```
t=>Array(20).fill(t).map(g=(t,i)=>i--*t?g(t,i)+g(t-1,i):1)

```

Try it online!

It is trivial to write down following recursive formula based on the description in question $$ g(t,i)=\begin{cases} g(t,i-1)+g(t-1,i-1) & \text{if} \quad i\cdot t\>0 \\ 1 & \text{if} \quad i\cdot t=0 \\ \end{cases} $$ And you just need to generate an Array of 20 elements with \\$\[g(t,0)\dots g(t,19)\]\\$

# Answer
> 3 votes
# 05AB1E, ~~11~~ ~~9~~ 8 bytes

```
19ÝIÝδcO

```

1-indexed

-1 byte by porting *@alephalpha*'s Mathematica answer, so make sure to upvote him!!

Try it online or verify all test cases.

**Explanation:**

```
19Ý       # Push a list in the range [0, 19]
   IÝ     # Push a list in the range [0, input-integer]
     δ    # Apply on the two lists double-vectorized (as a table):
      c   #  The binomial coefficient
       O  # And then sum each inner list
          # (after which the resulting list is output implicitly)

```

---

**Old ~~11~~ 9 bytes answer:**

```
20LIF.¥>¨

```

0-indexed

Try it online or verify all test cases.

**Explanation:**

```
20L        # Create a list in the range [1,20]
   IF      # Loop the input amount of times:
     .¥    #  Get the cumulative sum of the current list with 0 prepended automatically
       >   #  Increase each value in this list by 1
        ¨  #  Remove the trailing 21th item from the list
           # (after the loop, the result-list is output implicitly)

```

# Answer
> 3 votes
# Rust, 135 bytes

```
fn t(m:u64)->Vec<u64>{let f=|y|(1..=y).fold(1,|a,n|a*n);(0..20).map(|i| (0..=u64::min(i,m)).fold(0,|a,x|a+f(i)/f(x)/f(i-x))).collect()}

```

used @alephalpha 's idea, like several others. there is no builtin factorial so that takes up at least 36 bytes, (plus dealing with negatives). no builtin choose, another 16 bytes. iterator-\>declared vector type, 20 bytes.. etc etc.

Ungolfed at play.rust-lang.org

# Answer
> 2 votes
# JavaScript (ES6),  ~~68~~  67 bytes

```
f=(n,a=[...f+f])=>n--?f(n,[s=1,...a.map(x=>s-=~--x)]):a.slice(0,20)

```

Try it online!

---

# JavaScript (ES6), 63 bytes

NB: this version works for \\$n\le20\\$.

```
f=(n,a=[...Array(20-n)])=>n--?f(n,[s=1,...a.map(x=>s+=x||1)]):a

```

Try it online!

# Answer
> 2 votes
# Ruby, 74 bytes

`a=->b{c=[1];d=0;b==1?c=(1..20).to_a: 19.times{c<<c[d]+(a[b-1])[d];d+=1};c}`

Ungolfed version:

```
def seq num
    ary = [1]
    index = 0
    if num == 1
        ary = (1..20).to_a
    else
        19.times{ary << ary[index]+seq(num-1)[index]; index+=1}
    end
    return ary
end

```

Quite resource-intensive--the online version can't calculate the 13th metasequence.

Try it online

# Answer
> 2 votes
# Ruby, 49 bytes

```
f=->n{n<1?[1]*20:[o=1]+f[n-1][0,19].map{|x|o+=x}}

```

Recursive definition: Tier 0 is `1,1,1,1...` and each subsequent tier is 1 followed by a sequence whose first differences are the previous tier. Annoyingly this would give me 21 values if I didn't explicitly slice out the first 20; seems like there should be a way to shorten this by avoiding that.

# Answer
> 2 votes
# , 24 bytes

```
<:(1+/\@,])^:[(1+i.20)"_

```

Try it online!

NOTE: Turns out this is a translation of dzaima's APL answer, though I actually didn't notice it before writing this.

## explanation

```
<: (1 +/\@, ])^:[ (1+i.20)"_
<:                           NB. input minus 1 (left input)
                  (1+i.20)"_ NB. 1..20 (right input)
   (         )^:[            NB. apply verb in parens
                             NB. "left input" times
   (1     , ])               NB. prepend 1 to right input
   (  +/\@   )               NB. and take scan sum

```

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 120 bytes

```
n=>{for(long i=-1,h=0,m=0;++i<20;Print(i<1?1:h))for(m=h=0;m<=n;)h+=f(i)/(f(m)*f(i-m++));long f(long a)=>a>1?a*f(a-1):1;}

```

Try it online!

Based off of alephalpha's formula.

# Answer
> 2 votes
# K (oK), 17 bytes

-1 byte thanks to ngn (switching from 0-indexed to 1-indexed)

```
{x(+\1,19#)/20#1}

```

Try it online!

1-indexed

# K (oK), 18 bytes

```
{x(+\1,19#)/1+!20}

```

Try it online!

0-indexed

# Answer
> 2 votes
# Perl 5, 48 bytes

```
$x=1,@A=(1,map$x+=$_,@A[0..18])for 0..$_;$_="@A"

```

TIO

# Answer
> 2 votes
## R (60 59 bytes)

```
function(n)Reduce(function(p,q)2*p-choose(q-1,n),1:19,1,,1)

```

Online demo

Straightforward implementation of the observation

> T(n,k) = 2 T(n-1,k) - binomial(n-1,k). - M. F. Hasler, May 30 2010

from OEIS A008949. The arguments to `Reduce` are the function (obviously), the array over which to map, the starting value, a falsy value (to fold from the left rather than the right), and a truthy value to accumulate the intermediate results in an array.

# Answer
> 1 votes
# Jelly, 10 bytes

```
20RṖ1;ÄƲ⁸¡

```

Try it online!

0-indexed.

# Answer
> 1 votes
# Japt, 15 bytes

0-indexed; replace `h` with `p` for 1-indexed.

```
ÈîXi1 å+}gNh20õ

```

Try it

# Answer
> 1 votes
## CJam (20 bytes)

```
1aK*{1\{1$+}/;]}q~*p

```

Online demo. This is a program which takes input from stdin and prints to stdout; for the same score an anonymous block (function) can be obtained as

```
{1aK*{1\{1$+}/;]}@*}

```

### Dissection

This applies the definition literally:

```
1aK*      e# Start with an array of 20 1s
{         e# Loop:
  1\      e#   Push a 1 before the current list
  {1$+}/  e#   Form partial sums (including that bonus 1)
  ;]      e#   Ditch the last and gather in an array (of length 20)
}
q~*       e# Take input and repeat the loop that many times
p         e# Pretty print

```

# Answer
> 1 votes
# Vyxal `R`, 7 bytes

```
20⁰(ÞR›

```

Try it Online!

0-indexed.

## How?

```
20⁰(ÞR›
20      # Push number 20
  ⁰(    # Loop input times
    ÞR  # Take the cumulative sum of list (20, R flag makes this a [1, 20] range), remove last item, and prepend 0. Short for ¦Ṫ0p
      › # Increment (implicit vectorization)

```

# Vyxal `RM`, 7 bytes

```
19ƛ⁰ʀƈ∑

```

Try it Online!

1-indexed.

## How?

```
19ƛ⁰ʀƈ∑
19      # Push the number 19
  ƛ     # Map, R and M flags make this be a [0, 19] range
   ⁰ʀ   # Inclusive zero range of input
     ƈ  # Binomial coefficient, implicit vectorization
      ∑ # Sum these binomimal coefficients

```

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


title: Get the trends of an array

text:
# Question
Title: Get the trends of an array
For our purposes, a trend is a contiguous subsequence of an array that falls into one of three categories:

* increasing, e.g. `[1,2,3,10,239]`
* decreasing, e.g. `[8,5,0,-3,-50]`
* stable, e.g. `[7,7,7,7]`

Note that `[1,1,2,3]` is not a valid trend. It can be broken up into a stable trend `[1,1]` and an increasing trend `[1,2,3]`. In the event an array has more than one trend, its trends will always overlap by one number.

## Task

Given an array of at least two integers in any reasonable format, output the trends of the array.

## Rules

* You must output the smallest possible number of trends. `[[1,1], [1,2], [2,3]]` is not valid output for `[1,1,2,3]`.
* You must output trends in the order they occur in the input.
* You may output in any format you like as long as we can tell the trends apart.
* This is , so the code with the fewest bytes (in each language) wins.
* Standard loopholes are forbidden.

## Test cases

| Input | Output |
| --- | --- |
| ``` [1,2]<br>[1,2,1]<br>[1,1,2,3]<br>[1,-1,2,-2,3,-3]<br>[0,0,0,4,10,96,54,32,11,0,0,0]<br>[-55,-67,-80,5,5,5,9,9,9,9,14,20,25] ``` | ``` [[1,2]]<br>[[1,2], [2,1]]<br>[[1,1], [1,2,3]]<br>[[1,-1], [-1,2], [2,-2], [-2,3], [3,-3]]<br>[[0,0,0], [0,4,10,96], [96,54,32,11,0], [0,0,0]]<br>[[-55,-67,-80], [-80,5], [5,5,5], [5,9], [9,9,9,9], [9,14,20,25]] ``` |

# Answer
# BQN, 30 bytesSBCS

```
{(⊏˜+`)⌾∾0∾¨=˜⊔+`»≠⟜«×1↓-⟜»}

```

Run online!

| Code | Explanation | Example |
| --- | --- | --- |
| `x` | Argument | `⟨ 1 1 2 4 ⟩` |
| `1↓-⟜»` | Differences of adjacent arguments | `⟨ 0 1 2 ⟩` |
| `×` | Sign of each value | `⟨ 0 1 1 ⟩` |
| `»≠⟜«` | Mark starts of runs of equal adjacent values with a 1,
except the first. | `⟨ 0 1 0 ⟩` |
| `+`` | Cumulative sum | `⟨ 0 1 1 ⟩` |
|  | Group indices by their value | `⟨ ⟨ 0 ⟩ ⟨ 1 2 ⟩ ⟩` |
|  | Self-equal; replace all values by 1's | `⟨ ⟨ 1 ⟩ ⟨ 1 1 ⟩ ⟩` |
| `0∾¨` | Prepend a 0 to each group | `⟨ ⟨ 0 1 ⟩ ⟨ 0 1 1 ⟩ ⟩` |
| `+`⌾∾` | Cumulative sum under flattening the list | `⟨ ⟨ 0 1 ⟩ ⟨ 1 2 3 ⟩ ⟩` |
| `⊏˜` | Index into the argument | `⟨ ⟨ 1 1 ⟩ ⟨ 1 2 4 ⟩ ⟩` |
> 9 votes

# Answer
# , ~~83~~ ~~74~~ 73 bytes

*Edit: -9 bytes thanks to @Giuseppe.*

```
\(x,`?`=diff)Map(\(i,j)x[i:j],c(1,w<-which(!!?sign(?x))+1),c(w,sum(x|1)))
```

Attempt This Online!

Pretty straightforward:

1. Get signs of differences (identify trends).
2. Find starting positions of the trends.
3. Those (shifted by one) are also the ends of the trends.
4. `Map` over trends and extract them using `start:end`.

---

Alternative inspired by Unrelated String's Jelly answer:

### , ~~73~~ 71 bytes

*Edit: -2 bytes thanks to @Giuseppe.*

```
\(x)Map(\(i,j)x[i:j],head(w<-diffinv(rle(sign(diff(x)))$l)+1,-1),w[-1])
```

Attempt This Online!
> 5 votes

# Answer
# Jelly, 10 bytes

```
IṠŒɠ1;ÄrƝị

```

Try it online!

```
 Ṡ            Take the signs of the
I             differences between adjacent elements.
  Œɠ          Count the lengths of consecutive runs of equal signs,
    1;        prepend a 1,
      Ä       take the cumulative sums,
       rƝ     get the inclusive ranges between each pair of adjacent values,
         ị    and index each number in each range back into the input.

```
> 5 votes

# Answer
# Ruby, 60 bytes

```
->a,*w{a.each_cons(2){|x,y|(a!=a=x<=>y)&&w<<[x];w[-1]<<y};w}

```

Try it online!

### How it works

```
->a,*w{

```

Initialize `w` as an empty array, we will store the result there

```
a.each_cons(2)

```

Iterate on all pairs of consecutive elements of `a`

```
{|x,y|(a!=a=x<=>y)

```

Use `a` as a temporary variable to store the result of the last comparison. At the beginning its value will be different from anything else. On every iteration, check if the result of the comparison of the next 2 values is different from the previous result.

```
&&w<<[x]

```

If it's different, put the first of the two value in a new array inside of `w`.

```
;w[-1]<<y

```

Append the second value to the last array (continuation of sequence if the comparison result is the same, new array if it is different.)

```
};w}

```

Return `w` after the last iteration.
> 3 votes

# Answer
# Vyxal, 14 bytes

```
¯±ĠvL0p¦2lvƒṡİ

```

Try it Online!

Port of Unrelated String's Jelly answer.

```
  ĠvL          # Get the lengths of the runs of identical...'
 ±             # Signs
¯              # In the forward differences of the input
     0p¦       # Prepend a zero and get cumulative sums
         lvƒ   # Over runs of length...
        2      # 2
            ṡ  # Inclusive range
             İ # Index those into the original array

```
> 3 votes

# Answer
# Perl 5, 107 bytes

```
sub{my@r;!@r?push@r,$l=[$_]:@$l<2||($_<=>$L)==($L<=>$$l[-2])?push@$l,$_:push@r,$l=[$L,$_]and$L=$_ for@_;@r}

```

Try it online!
> 2 votes

# Answer
# Vyxal, 15 bytes

```
¯±ĠvL1p¦2lvƒṡ‹İ

```

Try it Online!

## How?

```
¯±ĠvL1p¦2lvƒṡ‹İ
¯               # Deltas (consecutive differences) of (implicit) input
 ±              # Sign of each
  Ġ             # Group consecutive identical items
   vL           # Length of each
     1p         # Prepend a one
       ¦        # Cumulative sums
        2lvƒṡ   # For each overlapping pair, get an inclusive range between them
             ‹  # Decrement each
              İ # Index each into the (implicit) input

```
> 2 votes

# Answer
# JavaScript, 84 bytes

-2 bytes from Arnauld, thanks!

```
f=([n,...a],d,s=[g=[]])=>1/n?f(a,D=Math.sign(a[0]-n,g.push(n)),d-D?[...s,g=[n]]:s):s

```

Try it online!

Explained

```
f = (
  [n, ...a],     // n: first item of array, a: remaining items
  d,              // d: previous difference
  s = [g = []]  // s: partial output, g: current group
) =>
  1 / n ?        // if n is a number, recurse, else return s
    f(           // call f() again
      a,         // remaining items
      D = Math.sign(a[0] - n, g.push(n)),  // assign new d to D
      d - D ?    // check if direction changes (sneakily push n to g)
        [...s, g = [n]] :  // if new direction, start a new group
        s,                 // else keep the same
    ) :
    s

```
> 2 votes

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

```
¥.±γ€g.¥üŸè

```

-3 bytes porting *@UnrelatedString*'s Jelly answer.

Try it online or verify all test cases.

**Original 14 bytes answer:**

```
ü2.γ`.S}ε˜ι`θª

```

Try it online or verify all test cases.

**Explanation:**

```
¥           # Get the forward-differences of the (implicit) input-list
 .±         # Get the sign (-1 if <0; 0 if 0; 1 if >0) for each value
   γ        # Split it into equal adjacent values
    €g      # Get the length of each inner list
      .¥    # Undelta with leading 0
        ü   # For each overlapping pair:
         Ÿ  #  Create an inclusive ranged list
          è # (0-based) index those lists into the (implicit) input
            # (after which the resulting list of lists is output implicitly)

ü2          # Split the (implicit) input-list into overlapping pairs
  .γ        # Adjacent group these pairs by:
    `       #  Pop and push both values in the pair to the stack
     .S     #  And compare them (-1 if a<b; 0 if a==b; 1 if a>b)
   }ε       # After the adjacent group-by: map over each list of pairs:
     ˜      #  Flatten the list
      ι     #  Uninterleave it into two parts ([a,b,c,d,e,f] → [[a,c,e],[b,d,f]])
       `    #  Pop and push both lists to the stack
        θ   #  Pop the second list and leave just its last value
         ª  #  Append it to the first list ([a,c,e,f])
            # (after which the resulting list of lists is output implicitly)

```
> 2 votes

# Answer
# TI-Basic, 65 bytes

```
Input A
tanh(99ΔList(ʟA
augment(Ans,{9→B
1→I
For(J,1,N
If ʟB(I)=ʟB(J
End
Disp seq(ʟA(X),X,I,J
J→I
End

```

prints each sublist on a new line

* `ΔList(` is a `diff` function
* `tanh(99X)` is a `sign` function for integers: `tanh(0)=0`, `tanh(99)=1` and `tanh(-99)=-1`
* we add a 9 at the end of `ʟB`, different than any value a diff can take, so that the last sublist is always printed
* `I` stores the index of the start of the current sublist
* if the signs are equal, we cut the `For` loop short with the `End`
* otherwise, the `End` is skipped, so we print the sublist from `I` to `J` and set `I` to `J`
> 2 votes

# Answer
# Haskell, 95 bytes

```
(!)=compare
x#y=show x++' ':y
f(a:x@(b:c:t))|a!b==b!c=a#f x|1>0=a#(b#('|':f x))
f[x,y]=x#(y#"")

```

Try it online!

A bit weird output: a string where *trends* are separated by `|` and elements are space separated.

**Alternatively**
Output a list of lists for *111 bytes*.

```
f l=l?(l!2)
(#)=compare
(a:t@(b:c:r))!x|a#b==b#c=t!(x+1)|1>0=x:t!2
_!x=[x]
l?(h:t)=take h l:drop(h-1)l?t
_?x=[]

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 90 bytes

```
f=(a,s,c=[],[v,...b]=a,x=[...c,v],q=Math.sign(b[0]-v))=>1/v?s-q?[x,...f(a,q)]:f(b,q,x):[c]

```

Try it online!
> 1 votes

# Answer
# Python, 132 bytes

```
c=lambda a,b,*_:(a>b)-(a<b)
f=lambda h,*t,v=3:([[[h]],[]][c(h,*t)==v]+((r:=f(v=c(h,*t),*t))[0].insert(0,h)or r)if t else[[h]])[v>2:]
```

Attempt This Online!

# Python, ~~138~~ 136 bytes

*-2 bytes thanks to @Kevin Cruijssen*

```
t=lambda a,b,*c:(a>b)-(a<b)
def f(x):
    i=j=0
    while-~i<len(x):
        k=t(*x[j:])
        while-~j<len(x)and t(*x[j:])==k:j+=1
        yield x[i:j+1];i=j
```

Attempt This Online!
> 1 votes

# Answer
# Retina, 75 bytes

```
\d+
*
L$`(?<=((_+)))((,(?<2>\2_+))+|(,(?!\1|\6)(_+))+|(,\1)+)\b
$1$&
_+
$.&

```

Try it online! Only supports positive integers due to language limitations. Explanation:

```
\d+
*

```

Convert to unary.

```
(?<=((_+)))

```

For each trend starting just after a value (either the first value or the last value of the previous trend)...

```
((,(?<2>\2_+))+|(,(?!\1|\6)(_+))+|(,\1)+)\b

```

... match either a trend where the value increases each time, a trend where the value decreases each time, or a trend where the value doesn't change, ...

```
L$`
$1$&

```

... and output the matched trend preceded by the initial value.

```
_+
$.&

```

Convert to decimal.
> 1 votes

# Answer
# Julia, 62 bytes

```
!x=(a=1;~ =diff;findall(~[sign.(~x);9].!=0).|>i->x[a:(a=1+i)])

```

Try it online!
> 1 votes

# Answer
# MATLAB, 92 bytes

```
function t(m)
d=[1 find(diff(sign(diff(m))))+1 numel(m)];for i=2:numel(d)
m(d(i-1):d(i)),end

```

Try it online!
> 1 votes

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