Test whether a sequence is bitonic

Question

You know what a monotonic sequence is: each element is bigger than its predecessor (monotonically rising) or as its successor (monotonically falling).

Bitonic means you have two arms of the sequence, one monotonically rising, the other falling.

For example, 1,3,5,7,6,4,2 is bitonic (rising until 7, then falling until the end; 99,4,8,16 is as well (falling until 4, then rising until the end).

The task is to test, whether a sequence is bitonic (without being monotonic), with your code being as short as possible in your language of choice.

Input: A list of positive integer numbers without duplicates in a form that suits your language.

Output: Truthy/falsy

Test data:

True:
1,3,5,7,6,4,2
99,4,8,16
100000,10000,1000,100,10,1,11,111,1111,11111,111111
2,1,3,4,5,6

False:
1,2,3,4,5,6,7
7,6,5,4,3,2,1
1,4,7,6,2,3,5
99,88,66,77,55,44,33,22,11
1,9,2,8,3,7,4,6,5

Answer 1

Haskell + hgl, 10 bytes

eL2<gr<pac

(Doesn't work on ato since ato is slightly out of date)

Explanation

• pac gets the contour of a list, i.e. the comparisons between consecutive elements
• gr group them into sections of equal elements.
• eL2 check if there are exactly two groups

Reflection

A couple of thoughts here

• I think there might be use in having a function which counts the number of groups. Although I don't think it would help this particular answer.
• pWK gets all partitions where each part satisfies a predicate. A version of this could be ay eL2<pWK(lq<pac), which is much longer although there are a bunch of ways to improve this approach.
  • lq<pac determines if a list is monotonic, that is useful. We already have functions for the specific monotonicities, this would be a nice addtion.
  • Versions of a lot of the partitioning functions that are specific to partition into two parts would be useful, since that is the most basic non-trivial type of partition. A version of pWK which is specific to size 2 would change this from ay eL2, checking if there is something of size 2, to ø, checking if the result is null.

Answer 2

Jelly, 6 bytes

IṠITL’

A monadic Link that accepts a list of different integers and yields 0 (falsey) if it is bitonic or a non-zero integer (truthy) if not.

Try it online! Or ee the test-suite.

How?

The count of direction changes must be exactly one, so count them and subtract one to give 0 iff the input is bitonic.

IṠITL’ - Link: list, A       e.g. [5, 4, 3, 6, 7, 2]
I      - forward differences      [ -1,-1, 3, 1,-5]
 Ṡ     - signs                    [ -1,-1, 1, 1,-1]
  I    - forward differences      [   0, 2, 0,-2]
   T   - truthy indices           [      2,    4]
    L  - length                   2
     ’ - decrement                1 (truthy: not bitonic)

Answer 3

R, 31 bytes

\(x,`?`=diff)sum(!!?sign(?x))-1

Attempt This Online!

A function taking a vector of integers and returning falsy for bitonic and truthy for non-bitonic. Takes some inspiration from @JonathanAllan’s Jelly answer.

Answer 4

Jelly, 7 bytes

IṠŒgL=2

Try it online!

Explanation

I       | Increments
 Ṡ      | Signs
  Œg    | Group consecutive equal values
    L=2 | Length is equal to two?

Answer 5

Ruby, 36 bytes

->a,*l{l.chunk{|x|a<=>a=x}.count==2}

Try it online!

Probably the same idea as @JonathanAllan’s Jelly answer.

Answer 6

JavaScript (Node.js), 40 bytes

This is implementation-dependent, as it assumes that the sort() algorithm compares the items by pairs from left to right, at least while \$x\ge0\$ (after which it no longer matters because we already know that the sequence is not bitonic anyway).

Returns \$0\$ or \$1\$.

a=>a.sort(s=(a,b)=>x-=s!=(s=a>b),x=2)|!x

Try it online!

Answer 7

Google Sheets, 80 bytes

=regexmatch(join(,sort((D1:Y1<E1:1)+2*(D1:Y1>E1:1)*(E1:1>0))),"^(1+2+|2+1+)0*$")

Put the number sequence in cells D1:Z1 and the formula in cell A1.

Simple Boolean arithmetic and string matching. Makes just one pass through the array. The sort() does not actually sort anything — its purpose is to enable array processing.

Expects that the last number is in or before column Z. If you need more columns, replace :1 with :Z1 (3 bytes) and insert columns before Y as necessary.

Answer 8

Perl 5 -p, 43 bytes

s/\d+ ?/$&>$'||B/ge;chop;$_=/^(B+1+|1+B+)$/

Try it online!

Answer 9

APL (Dyalog Classic), 13 11 bytes

-2 bytes thanks to att.

1=1⊥2≠/2>/⊢

Try it online!

1=1⊥2≠/2>/⊢­⁡​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌­
       2>/⊢  ⍝ ‎⁡compare successive terms with > (direction of deltas)
    2≠/      ⍝ ‎⁢compare successive terms with ≠ (changes in direction)
  1⊥         ⍝ ‎⁣sum (# of changes in direction)
1=           ⍝ ‎⁤equal to 1
💎

Created with the help of Luminespire.

Answer 10

Julia 1.0, 29 bytes

!L=sum((~=diff)(~L.>0).^2)==1

Try it online!

based on multiple other answers

Answer 11

05AB1E, 6 bytes

ü.SÔg<

Outputs an 05AB1E truthy/falsey value, so 1 if truthy and 0 or a positive integer if falsey.

Try it online or verify all test cases.

Explanation:

ü       # For each overlapping pair of the (implicit) input-list:
 .S     #  Compare them: 1 if a>b; 0 if a==b; -1 if a<b
   Ô    # Connected uniquify this list
    g   # Pop and push the length
     <  # Decrease it by 1
        # (after which the result is output implicitly)

Answer 12

MathGolf, 7 bytes

│mσ│┘Σ┴

Try it online.

Explanation:

│        # Get the forward differences of the (implicit) input-list
 m       # Map over each integer:
  σ      #  Get its sign
   │     # Get the forward differences of this list again
    ┘    # Check for each that they're NOT equal to 0
     Σ   # Sum the amount of non-zero values together
      ┴  # Check whether this is equal to 1
         # (after which this is output implicitly as result)

Answer 13

APL+WIN, 15 bytes

Prompts for input.

1=+/2=|2-/×2-/⎕

Try it online! Thanks to Dyalog Classic

Answer 14

Raku, 29 bytes

($_ Z-.skip)>>.sign.squish==2

Attempt This Online!

Zip-subtract the sequence with itself-skipped, i.e., take the differences and further take the sign of those differences. Lastly "squish" the signs, which squeezes consecutive duplicates into one, i.e., uniq of UNIX; if we have 2 unique signs at the end, sequence is bitonic.

Answer 15

Japt, 6 bytes

Outputs 0 for true or a non-zero integer for false.

äÎòÎÊÍ

Try it

Answer 16

C (clang), 62 bytes

i;f(*l,z){i=*l=*l>l[1];return--z-1?f(l+1,z)+(i%2-*l&&++i):-1;}

Try it online!

Return false if bitonic , true otherwise

Answer 17

Uiua, 14 bytes

=1/+≡/≠◫2≡/>◫2

Gets windows, compares, gets windows, counts changes in comparisons and checks if the number of changes is exactly 1.

Test pad

Answer 18

Retina 0.8.2, 39 bytes

\d+
$*
(?<=(1+)),1\1
;
1

^,+;+$|^;+,+$

Try it online! Link includes test cases. Explanation: Port of @NickKennedy's Jelly answer.

\d+
$*

Convert the integers to unary.

(?<=(1+)),1\1
;

Replace the comma with a semicolon for all ascending pairs. (The lookbehind both allows the "matches" to overlap and being atomic finds the start of the unary value without needing a word boundary.)

1

Delete any remaining 1s.

^,+;+$|^;+,+$

Check whether the sequence is bitonic.

Answer 19

Charcoal, 23 bytes

≔ＥΦθκ›ι§θκθ⁼№θ§θ⁰⌕謧θ⁰

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

≔ＥΦθκ›ι§θκθ

Create a list of 1s and 0s corresponding to whether the overlapping pairs of integers are ascending or descending.

⁼№θ§θ⁰⌕謧θ⁰

Check that the count of occurrences of the first element is also the start of the second run of identical elements; if there is only one run then there is no start of the second run while if there are more than two runs then there are too many of the first element to fit before the second run.

Answer 20

Clojure, 84 bytes

#(=(sort(mapcat set(partition-by +(for[i(map -(rest %)%)](Long/signum i)))))'(-1 1))

Annoyingly partition-all is a long function name, and the static function call Long/signum (which outputs -1, 0 or 1) cannot be directly composed with - using comp.

Try it online!

Answer 21

APL(NARS), 12 chars

1=≢⍸∼2=/2</⎕

This above it seems ok for all test how to use it:

  1=≢⍸∼2=/2</⎕ 
⎕:
  1 9 2 8 3 7 4 6 5
0

test but the char "∼" in Tio is not the same char of the answer.

https://tio.run/##PY09DsIwDIX3nOWh4rT5qUQPgATiDJVQWSrBysIIZQCxcAFOwXlykfCSAFH89Gx/tvvDONse@3G/i@H@XK/C@VEruuWGTlSYLkOULlxf4fY@6a7Si4rdyHoclKCGgYNFA60G1bY0HmLpZZ4e5K9JGBBI@jmKfFU4pZF2Ntyad0D/Mjjm6ZJhXrMuud/k64ky5b73sIQdDEGSRMkWuCXoiTqOcdEH

Answer 22

Desmos, 42 bytes

f(L)=d(d(L))^2.total-1
d(L)=sgn(L[2...]-L)

Try It On Desmos!

Try It On Desmos! - Prettified

Returns 0 if bitonic or a non-zero integer otherwise.

Answer 23

Swift, 143 bytes

Minimal version:

func b(_ a:[Int])->Bool{var c=[Int]();for i in 0..<a.count-1{let s=(a[i+1]-a[i]).signum();if s != 0 && s != c.last{c+=[s]}};return c.count==2}

Verbose version:

func bitonic3(_ array: [Int]) -> Bool {
    let a = array
    var changes: [Int] = []
    var reducedChanges: [Int] = []

    for i in 0 ..< a.count - 1 {
        let sign = (a[i+1] - a[i]).signum()
        if sign != 0 {
            changes.append(sign)
        }
    }

    for i in 0 ..< changes.count {
        let value = changes[i]
        if reducedChanges.last != value {
            reducedChanges.append(value)
        }
    }
    
    if reducedChanges.count != 2 {
        return false
    }

    return true
}

Answer 24

Nekomata + -e, 4 bytes

∆±ĉđ

Attempt This Online!

∆±ĉđ
∆       Delta; differences between consecutive elements
 ±      Sign
  ĉ     Split into chunks of identical elements
   đ    Unpair; check if length is 2