18
\$\begingroup\$

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
\$\endgroup\$
9
  • \$\begingroup\$ Related challenge. \$\endgroup\$ Dec 17, 2023 at 22:00
  • \$\begingroup\$ How is 99,4,8,16 bitonic? which for is less than both 99 and 8? \$\endgroup\$ Dec 18, 2023 at 12:42
  • \$\begingroup\$ @AmirrezaRiahi It goes down from 99 to 4, then up from 4 over 8 to 16. Two monotonic sequences form one bitonic sequence. \$\endgroup\$
    – Philippos
    Dec 18, 2023 at 13:25
  • 1
    \$\begingroup\$ In research papers, such sequences or functions are usually called unimodal \$\endgroup\$
    – Stef
    Dec 18, 2023 at 20:33
  • \$\begingroup\$ Are there any guarantees about the length of the input? \$\endgroup\$
    – chunes
    Dec 19, 2023 at 0:33

24 Answers 24

5
\$\begingroup\$

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

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)
\$\endgroup\$
2
  • \$\begingroup\$ Golfing languages are just unbeatable. I swear, Jelly is so often under 10 bytes \$\endgroup\$
    – Hakaishin
    Dec 19, 2023 at 16:20
  • 1
    \$\begingroup\$ @Hakaishin Please don't let golfing languages dissuade you, just try to make code as short as you can in the language of your choice and have some fun with it. (We generally don't give the green tick here anymore, because of the vast language differences). \$\endgroup\$ Dec 19, 2023 at 17:31
4
\$\begingroup\$

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.

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

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

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.

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

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!

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

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.

bitonic

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

Perl 5 -p, 43 bytes

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

Try it online!

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ +/ -> 1⊥ and you can remove the parens \$\endgroup\$
    – att
    Dec 19, 2023 at 2:17
3
\$\begingroup\$

Julia 1.0, 29 bytes

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

Try it online!

based on multiple other answers

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

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

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

APL+WIN, 15 bytes

Prompts for input.

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

Try it online! Thanks to Dyalog Classic

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

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.

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

Japt, 6 bytes

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

äÎòÎÊÍ

Try it

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

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

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

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

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

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.

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

Charcoal, 23 bytes

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

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

≔EΦθκ›ι§θκθ

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.

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

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!

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

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

\$\endgroup\$
3
  • \$\begingroup\$ Do you have an explanation and a link how to test it? \$\endgroup\$
    – Philippos
    Dec 18, 2023 at 15:16
  • \$\begingroup\$ the explenation is that in each sequence increase and after decrease or viceversa there is one and only one element that has in one side the increase and other side the decrease or viceversa \$\endgroup\$
    – Rosario
    Dec 18, 2023 at 16:35
  • 1
    \$\begingroup\$ You can drop the ~ and replace the second equals with not equals \$\endgroup\$
    – Tbw
    Dec 21, 2023 at 0:51
1
\$\begingroup\$

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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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