10
\$\begingroup\$

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], [10]
[7, 8, 9, 10, 20, 30] => [8, 9, 10, 20, 30], [7] # this is also valid

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

[4, 5, 2, 1, 3] => False
[3, 4, 3, 4, 5, 2, 4] => False
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Aug 13 at 6:42
  • \$\begingroup\$ @KevinCruijssen time restriction is probably enough on its own not to make this a dupe. \$\endgroup\$ – Nick Kennedy Aug 13 at 9:46
  • 1
    \$\begingroup\$ @NickKennedy Possibly yeah, which is why I refrained from hammering it. :) \$\endgroup\$ – Kevin Cruijssen Aug 13 at 9:50
  • 2
    \$\begingroup\$ Suggested test case: [3, 5, 2, 4, 4, 1, 1]. The current test cases let you get away with >= / <, when it should really be >= / <=. \$\endgroup\$ – Grimy Aug 13 at 11:06
  • 1
    \$\begingroup\$ @Arnauld : Yes, it can be any value ("falsey" is just to say: it is false that the input is a crossing sequence). \$\endgroup\$ – Chas Brown Aug 13 at 17:19
1
\$\begingroup\$

Jelly, 12 bytes

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

Try it online!

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

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[0]\$ (decreasing) and \$b[1]\$ (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.

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

Haskell, 84 bytes

(([],[])#)
(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!

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic Aug 23 at 1:39
  • \$\begingroup\$ Thanks for the suggestion. I've updated the answer. Is there any copy-pastable template here for publishing answers? \$\endgroup\$ – Joel Aug 23 at 1:54
  • \$\begingroup\$ I'm not sure what you mean? TIO has a template that you seem to already be using. \$\endgroup\$ – Sriotchilism O'Zaic Aug 23 at 1:55
  • \$\begingroup\$ I only generated a link on TIO and added the link to my post. I did not use any template there. Where is it? \$\endgroup\$ – Joel Aug 23 at 1:57
  • 1
    \$\begingroup\$ @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! \$\endgroup\$ – Chas Brown Aug 23 at 2:10
0
\$\begingroup\$

Brachylog, 17 bytes

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

Try it online!

There's probably considerable room to golf this.

\$\endgroup\$
  • 2
    \$\begingroup\$ You've already answered this challenge before here, where you did it in 16 bytes. ;) \$\endgroup\$ – Kevin Cruijssen Aug 13 at 6:42
  • \$\begingroup\$ 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 \$\endgroup\$ – Unrelated String Aug 13 at 6:50
0
\$\begingroup\$

05AB1E, 15 14 13 bytes

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

Try it online or validate all test cases.

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

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!

\$\endgroup\$

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.