# Crossing Sequences

Given a list of positive integers A, call it an increasing sequence if each element is greater than or equal to the previous one; and call it a decreasing sequence if each element is less than or equal to the previous one.

Some increasing sequences:

[1,2,4,7]
[3,4,4,5]
[2,2,2]
[]


Some decreasing sequences:

[7,4,2,1]
[5,4,4,3]
[2,2,2]
[]


A crossing sequence is a list that can be decomposed into two disjoint subsequences, one an increasing sequence and the other a decreasing sequence.

For example, the list:

[3,5,2,4,1]


is a crossing sequence, since it can be decomposed into:

[3,    4  ]
[  5,2,  1]


where [3,4] is the increasing subsequence and [5,2,1] is the decreasing subsequence. We'll call such a pair of (increasing,decreasing) subsequences a decomposition of the crossing sequence.

The list:

[4,5,2,1,3]


is not a crossing sequence; there is no way to decompose it into an increasing and decreasing subsequence.

Your task is to write a program/function taking as input a list of positive integers; and if it is a crossing sequence, return the two lists in one of its decompositions; or some consistent "falsey" value if the list is not a crossing sequence.

This is ; shortest program/function in each language is the winner.

## Rules:

• Input is flexible.
• The usual loopholes are forbidden.
• If there are multiple valid ways to decompose the input, you may output one or all of them.
• Output formatting for the decomposition is flexible; but it must be unambiguous regarding the distinction between the two subsequences.
• You may use any consistent output value to indicate that the input is not a crossing sequence; so long as it is unambiguous compared to the output for any crossing sequence. You should specify the falsey value in your answer.

## Test Cases:

Using False to indicate non-crossing sequences:

[3, 5, 2, 4, 1] => [3, 4], [5, 2, 1]
[3, 5, 2, 4, 4, 1, 1] => [3, 4, 4], [5, 2, 1, 1]

[7, 9, 8, 8, 6, 11] => [7, 8, 8, 11], [9, 6]
[7, 9, 8, 8, 6, 11] => [7, 9, 11], [8, 8, 6] # also valid
[7, 9, 8, 8, 6, 11] => [7, 8, 11], [9, 8, 6] # also valid

[7, 8, 9, 10, 20, 30] => [7, 8, 9, 20, 30], 
[7, 8, 9, 10, 20, 30] => [8, 9, 10, 20, 30],  # this is also valid

[5, 5, 5] => [5, 5, 5], []

[4, 5, 2, 1, 3] => False
[3, 4, 3, 4, 5, 2, 4] => False

• Possible duplicate. Only two differences I see is that the other challenge should be run in polynomial time in the length of the input, and allows for a truthy value instead of the two subsequences (returning the subsequences themselves will receive a 20% bonus though). Still sounds like a dupe to me, but I won't hammer it. Aug 13, 2019 at 6:42
• @KevinCruijssen time restriction is probably enough on its own not to make this a dupe. Aug 13, 2019 at 9:46
• @NickKennedy Possibly yeah, which is why I refrained from hammering it. :) Aug 13, 2019 at 9:50
• Suggested test case: [3, 5, 2, 4, 4, 1, 1]. The current test cases let you get away with >= / <, when it should really be >= / <=. Aug 13, 2019 at 11:06
• @Arnauld : Yes, it can be any value ("falsey" is just to say: it is false that the input is a crossing sequence). Aug 13, 2019 at 17:19

# Brachylog, 17 bytes

;Ṣzpᵐz{ℕˢ}ᵐ≤₁ʰ≥₁ᵗ


Try it online!

There's probably considerable room to golf this.

• You've already answered this challenge before here, where you did it in 16 bytes. ;) Aug 13, 2019 at 6:42
• I couldn't shake the feeling that there was something similar I'd done, but for some reason my mind decided it had to have been this instead Aug 13, 2019 at 6:50

# 05AB1E, 1514 13 bytes

2.Œ.ΔćRšεü@}W


Explanation:

2.Œ                    # all partitions of the input in 2 subsequences
.Δ                  # find the first partition such that the following gives 1
ćRš               # reverse the first subsequence
ε  }           # map each subsequence to
ü@            # pairwise greater-than
W          # minimum (1 if all 1s, 0 otherwise)


# Jelly, 12 bytes

ŒPżṚ\$ṢNÞƭ€ƑƇ


Try it online!

# JavaScript (ES6),  110 105  104 bytes

Returns either [[decreasing], [increasing]] or $$\1\$$ if there's no solution.

f=(a,n,b=[[],[]])=>a.some((v,i)=>[...x=b[i=n>>i&1]].pop()*(x.push(v),i-=!i)>v*i)?n>>a.length||f(a,-~n):b


Try it online!

## How?

We try all values of a bitmask $$\n\$$ between $$\0\$$ and $$\2^L\$$, where $$\L\$$ is the length of the input array.

At each iteration, we split the original array into two subsequences $$\b\$$ (decreasing) and $$\b\$$ (increasing), using each bit $$\i\$$ of $$\n\$$ to know where each value goes.

When a new value is added to a subsequence, we simultaneously make sure that it's not invalid by comparing it with the last value, popped from a copy of the subsequence. The direction of the inequality is always the same, but the operands are multiplied by either $$\1\$$ (if $$\i=1\$$) or $$\-1\$$ (if $$\i=0\$$):

[...x = b[i = n >> i & 1]].pop() * (x.push(v), i -= !i) > v * i


We stop and return $$\b\$$ as soon as all values are passing, i.e. some() is falsy.

(([],[])#)
(d,i)#(a:b)=(#b)=<<[(d++[a],i)|all(a<=)d]++[(d,i++[a])|all(a>=)i]
p#_=[p]


Returns a list of all valid (decreasing,increasing) pairs or the empty list if there's no such pair.

Try it online!

# Python 3, 109 107 bytes

def f(l,i=[],d=[]):
if l:s,*r=l;i and s<i[-1]or f(r,i+[s],d);d and s>d[-1]or f(r,i,d+[s])
else:print(i,d)


Try it online!

The function prints all possible decompositions to the standard output. If there are no possible decompositions, nothing is printed.

Thanks to @Sriotchilism O'Zaic for improvement suggestions.

• Welcome to the site. I suggest doing s<i[-1] rather than i[-1]>s  and similar with d[-1]<s , both save a byte. Aug 23, 2019 at 1:39
• Thanks for the suggestion. I've updated the answer. Is there any copy-pastable template here for publishing answers?
– Joel
Aug 23, 2019 at 1:54
• I'm not sure what you mean? TIO has a template that you seem to already be using. Aug 23, 2019 at 1:55
• I only generated a link on TIO and added the link to my post. I did not use any template there. Where is it?
– Joel
Aug 23, 2019 at 1:57
• @Joel - At the top of the TIO page there's an icon that looks like some chain links. Click that, and then you get a page of options. One of them is 'Code Golf Submission'. That will put into your copy buffer the formatted stuff you want! Welcome also, and nice solution! Aug 23, 2019 at 2:10

# Python 2, 147 bytes

def f(a):
for i in range(2**len(a)):
x=[];y=[]
for c in a:[x,y][i&1]+=[c];i/=2
if x==sorted(x)and y[::-1]==sorted(y[::-1]):return x,y
return 0


Try it online!