20
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Related (inputs for this question are tower permutations) \$\endgroup\$
    – AnttiP
    Feb 21 at 16:42
  • 2
    \$\begingroup\$ This is closely related to Antsy Permutations -- a tower permutation is one whose inverse permutation, read backwards as a list, is antsy. \$\endgroup\$
    – xnor
    Feb 21 at 17:09
  • \$\begingroup\$ I think these would also be called the "unimodal" permutations. \$\endgroup\$ Feb 23 at 0:52

27 Answers 27

14
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Apologies, my "golf" was a mirage. Which unfortunately leaves just the +2 for the recursive f. \$\endgroup\$
    – loopy walt
    Feb 21 at 18:18
  • 4
    \$\begingroup\$ Python3, 32 bytes. Takes the splatted input and signals by exit code: tio.run/… (hope I didn't mess up this time): \$\endgroup\$
    – loopy walt
    Feb 21 at 18:52
10
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

Julia 1.0, 26 23 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 35 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ This wouldn't work with n>9, would it? \$\endgroup\$
    – bazzilic
    Feb 22 at 7:01
  • \$\begingroup\$ @bazzilic Why? It's an integer array, not a digit array. \$\endgroup\$ Feb 22 at 7:16
  • \$\begingroup\$ Ah, ok, my bad. I thought it was a string array with digits. \$\endgroup\$
    – bazzilic
    Feb 22 at 7:20
  • \$\begingroup\$ @bazzilic I added a few test cases to show that it works with n > 9. \$\endgroup\$ Feb 22 at 8:04
  • \$\begingroup\$ It would, however, not work with n greater than 2^31 - 1. ;^) \$\endgroup\$ Feb 23 at 1:58
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Isn't this overkill? Wouldn't it be shorter to test if a[i] < a[i-1] & a[i] < a[i+1]? \$\endgroup\$ Feb 21 at 22:56
  • \$\begingroup\$ @OlivierGrégoire It has to be increasing from a[0] up to a[i] and then decrease all the way to a[n-1]. How does your test verify that? And how do you find i? And make sure it's the only peak? And handle just increasing or decreasing from a[0] to a[n-1]? \$\endgroup\$
    – Noodle9
    Feb 21 at 23:00
  • \$\begingroup\$ You're still thinking recursion while I'm not: I'm thinking plain iteration, which you already partly do. Just take a for(int i = 1; i < n-1; i++) if ((a[i] < a[i-1]) & (a[i] < a[i+1])) return 0; return 1; I don't know enough of C to adapt your golfed code without segfault. The condition checks that there are no valley, basically. \$\endgroup\$ Feb 21 at 23:10
  • \$\begingroup\$ @OlivierGrégoire Yes, figured it out - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 21 at 23:14
  • \$\begingroup\$ np! :) I was missing the n=r; to provide you with a working example. \$\endgroup\$ Feb 21 at 23:19
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 37 bytes

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

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 7 bytes

2lvƒ>ÞṠ

Try it Online! or Run all the test cases

-2 bytes thanks to Aaroneous Miller

\$\endgroup\$
1
1
\$\begingroup\$

Dyalog APL: 10 bytes

Nothing really to say here, regular solution.

(⍳∘≢≡⍋)2>/
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Apr 22 at 22:32
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 47 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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'

\$\endgroup\$
0
0
\$\begingroup\$

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 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
\$\endgroup\$
1
  • \$\begingroup\$ You can simply take out the two backslashes for -2 bytes: Try It On Desmos!. \$\endgroup\$
    – Aiden Chow
    Mar 2 at 7:54
0
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ your TIO link goes to the list of 05AB1E commands... \$\endgroup\$
    – Steffan
    Apr 19 at 18:55
  • \$\begingroup\$ @Steffan Whoops.. Thanks for noticing. Should be fixed now. \$\endgroup\$ Apr 19 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.