# 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. – Kevin Cruijssen Aug 13 '19 at 6:42
• @KevinCruijssen time restriction is probably enough on its own not to make this a dupe. – Nick Kennedy Aug 13 '19 at 9:46
• @NickKennedy Possibly yeah, which is why I refrained from hammering it. :) – Kevin Cruijssen Aug 13 '19 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 >= / <=. – Grimmy Aug 13 '19 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). – Chas Brown Aug 13 '19 at 17:19

# 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. – Ad Hoc Garf Hunter Aug 23 '19 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 '19 at 1:54
• I'm not sure what you mean? TIO has a template that you seem to already be using. – Ad Hoc Garf Hunter Aug 23 '19 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 '19 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! – Chas Brown Aug 23 '19 at 2:10

# 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. ;) – Kevin Cruijssen Aug 13 '19 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 – Unrelated String Aug 13 '19 at 6:50

# 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!