Is it a tower permutation?

Question

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 code-golf and decision-problem 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 1

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.

Answer 2

Jelly, ⁵ 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.

Answer 3

Julia 1.0, 26 23 bytes

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

Try it online!

Answer 4

R, 33 bytes

Or R>=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.

Answer 5

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!

Answer 6

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

Answer 7

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 Ts follower by some number of Bs. 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.

Answer 8

J, ^{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?

Answer 9

Ruby, 35 bytes

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

Try it online!

Answer 10

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.

Answer 11

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)

Answer 12

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)

Answer 13

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.

Answer 14

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]

Answer 15

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.

Answer 16

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

Answer 17

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 1s where both neighbouring runs of 1s 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.

Answer 18

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

Answer 19

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.

Answer 20

Perl 5, 47 bytes

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

Try it online!

Answer 21

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!

Answer 22

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'

Answer 23

JavaScript (Node.js), 37 bytes

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

Attempt This Online!

Answer 24

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)

Answer 25

Vyxal, 9 7 bytes

2lvƒ>ÞṠ

Try it Online! or Run all the test cases

-2 bytes thanks to Aaroneous Miller

Answer 26

Dyalog APL: 10 bytes

Nothing really to say here, regular solution.

(⍳∘≢≡⍋)2>/

Answer 27

Uiua, 10 bytes

/↧↘⊗1.≡/<◫2

      ≡  ◫2 # for each adjacent pair of elements,
       /<   # check if the pair is increasing
   ⊗1       # find the first decreasing pair
  ↘  .      # and drop everything before it
/↧          # are all remaining pairs decreasing?

try it online!

bonus 11-byte solution:

/↧≡(≠1⊗/↧.)◫3

Answer 28

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 1s and -1s. If l is a tower permutation, all the -1s will come before the 1s.

M then takes the result of D and gets its pairwise differences. For a tower permutation, this will be a list of 0s 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 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

Answer 29

Setanta, 74 bytes

gniomh(l){le i idir(1,fad@l-1)ma l[i]<l[i-1]&l[i]<l[i+1] toradh 0toradh 1}

Try on try-setanta.ie

Answer 30

Pyt, 8 bytes

₋ĐÅ/ĐŞ=Π

Try it online!

Port of Kevin Cruijssen's 05AB1E answer