Sorting with a deque

Question

You're given an array of positive integers. Your job is to sort them using an initially empty deque (double-ended queue) by the following procedure:

• Take a number from the front of the array, and push it into one of the two ends of the deque. Repeat this until the array is empty.

Determine if it is possible that the deque is sorted from left to right in the end.

You may assume that the array is not empty. The input numbers are not necessarily distinct.

For output, you can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Truthy:

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

Falsy:

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

• Bubbler: Related
• xnor: Related: Antsy Permutations, which I think is this restricted to permutations

Answer 1

K (ngn/k), 17 bytes

{&/(x=|\x)|x=&\x}

Every element must be the minimal (or the maximal) element of its prefix.

Try it online!

APL(Dyalog Unicode), ^{(削除) (削除ここまで)} (削除) 13 (削除ここまで) 10 bytes ^SBCS

A direct translation of the ngn/k solution. -3 bytes thanks to @att.

⊢∧.∊⌈⍀, ̈⌊⍀

Try it on APLgolf! (10 bytes)

(⊢=⌈⍀)∧.∨⊢=⌊⍀

Try it on APLgolf! (13 bytes)

Uiua, (削除) 14 (削除ここまで) 13 bytes

Probably can be improved as I'm not so familiar with Uiua.

/↧↥=⟜\↧:=⟜\↥.

Try it on Uiua pad! (13 bytes)

/↧↥⊃(=⟜\↧)=⟜\↥

Try it on Uiua pad! (14 bytes)

• att: apl -3: ⊢∧.∊⌈⍀,¨⌊⍀
• ovs: uiua -1: /↧↥∩=⊃⟜\↧⟜\↥, and -2 with a slightly different approach: /↧↥∩=∩⟜\↥¯.

Answer 2

Python, 45 bytes

f=lambda l:min(l)<l.pop()<max(l)or l and f(l)

Attempt This Online!

Returns flipped truth values: Falsey (empty list) for sortable and True for not sortable. Consumes the input list.

Answer 3

Jelly, (削除) 7 (削除ここまで) 6 bytes

ṢƤtƑ"ḋ

A monadic Link that accepts a list of positive integers and yields 0 (falsey) if sortable or a positive integer (truthy) if not.

Try it online!

How?

Check that each sorted prefix has its original rightmost element at one end.

ṢƤtƑ"ḋ - Link: list of positive integers, A
 Ƥ - for each prefix:
Ṣ - sort
 " - zip with E in A applying f(SortedPrefix, E):
 Ƒ - is invariant under?:
 t - trim any {E} from both sides of {SortedPrefix}
 ḋ - dot-product with {A}

Answer 4

R, 30 bytes

\(x,`!`=cummin)any(x-!x&x+!-x)

Attempt This Online!

Port of @Unrelated String's first Jelly answer.

Outputs swapped TRUE/FALSE.

Slightly ungolfed:

\(x)any(x-cummin(x)&(-x)-cummin(-x))

Answer 5

Vyxal, 9 bytes

ɖ∵?ɖ∴ZΠ$ḟ

Try it Online! Port of Unrelated String's Jelly answer, and a bit of a mess. I tried writing my own answer, but it was a byte longer.

 $ḟ # Is every element of the input
 ZΠ # Either
ɖ∵ # A cumulative minimum
 ɖ∴ # Or a cumulative maximum
 ? # Of the input?

Answer 6

Nekomata + -e, 6 bytes

pƆt≤t≥

Attempt This Online!

This swaps truthy and falsy.

pƆt≤t≥
p Find a prefix of the input
 Ɔ Split it into the last element and the rest
 t≤ Check that the last is less than at least one element of the rest
 t≥ Check that the last is greater than at least one element of the rest

Answer 7

Jelly, 8 bytes

«\ż»\Œpi

Try it online!

Feels a bit silly, but beats a couple better ideas I've had.

 Œp Generate every list built by choosing from, at each position,
 ż either
«\ the cumulative minima
 »\ or the cumulative maxima.
 i Is the input in this list?

Jelly, 8 bytes

n×ばつ»\o=

Try it online!

n Is each element not equal to
 «\ the smallest element so far?
 ×ばつ Multiply those comparisons pairwise with
 »\ the cumulative maxima,
 o then replace zeroes with corresponding elements of the input. 
 = Is this result equal to the input?

Answer 8

Haskell + hgl, 23 bytes

no uq<f'[gj,mx,mn]<<pxn

Attempt This Online!

Explanation

For each prefix determine the maximum, minimum and last elements. If any of these results in 3 unique values then fail otherwise pass.

• pxn all non-empty prefixes
• f' apply all functions in a list ...
• gj last
• mx maximum
• mn minimum
• no none is ...
• uq unique

If the result is unique it means that there is an element which has both a greater and smaller element before it, and thus that element cannot be inserted into the deque.

Alternative algorithm, 34 bytes

f x=fo$(zW ma.*eq=#=x.*flz x)mN ma

Attempt This Online!

Explanation

We check that every element of the input is either a cumulative minimum or a cumulative maximum.

• Take the cumulative minimum and maximum of the input.
• Zip each with the original list to determine the equal elements.
• Zip the two results together with or.
• Check that every element in the result is true.

Reflection

This seems pretty poor overall. The second submission is very long but can be improved in a lot of ways. I don't see any sensible way to shorten the first submission.

Part of why the alterntive is so much longer is it seems to be that the algorithm uses a lot of references to the input. (The most expanded version references the input 4 times!) This makes the glue pretty costly.

• lz ma and lz mN for cumulative maximum and minimum could have pre-composed variants.
• zW ma, zW mN, and zW eq could all also have shortcuts. Generally zW could have more shortcuts.
• I implemented jzW to zip and concat lists. I chose to generalize this to any monad, however we can see in the above that it would have been useful to have generalized to a monoid. I'll leave the existing version, but I should make a version which zips and then uses a monoid action to combine the values.

Answer 9

K (ngn/k), 13 bytes

&/|/=/&\'\-:\

Try it online!

Returns a positive integer for truthy and 0 for falsy.

I don't think I've seen any other code with such high slash ratio :)

&/|/=/&\'\-:\ Input: x = a vector of positive integers
 -:\ negate and collect until convergence;
 gives [x, -x] since x is nonempty and positive
 &\'\ "minimum scan each" until convergence;
 if x is all-equal, becomes [[x, -x]];
 otherwise [[x, -x], [cummin of x, cummin of -x]]
 note that cummin of -x is -(cummax of x)
 =/ reduce by elementwise equality;
 [x, -x] or [x == cummin of x, x == cummax of x]
 |/ reduce by max;
 x or (x[i] == (cummin of x)[i] or (cummax of x)[i] for each i)
&/ reduce by min

Answer 10

05AB1E, (削除) 11 (削除ここまで) 10 bytes

ηε{DyθÚÊ}P

-1 byte porting @JonathanAllan's Jelly answer

Outputs 1 if sortable; 0 if not.

Try it online or verify all test cases or see a step-by-step output.

Original approach:

δ.SÅlεÙg}3å

Outputs 0 if sortable; 1 if not.

Try it online or verify all test cases or see a step-by-step output.

Explanation:

η # Get all prefixes of the (implicit) input-list
 ε # Map over each prefix `y`:
 { # Sort it
 D # Duplicate this sorted prefix
 y # Push the current prefix `y` again
 θ # Pop and keep its last item
 Ú # Trim all leading/trailing occurrences of this value from the
 # sorted copy
 Ê # Check that the two lists are NOT the same
 }P # After the map: product to check all were truthy
 # (after which this is output implicitly as result)

δ # Apply double-vectorized on two times the (implicit) input-list:
 .S # Compare (-1 if a<b; 0 if a==b; 1 if a>b)
 Ål # Pop and leave just the lower triangle of this matrix
 ε # Map over each row of the lower triangle:
 Ù # Uniquify
 g # Pop and push the length
 }3å # After the map: check whether there is a 3 in the list
 # (after which this is output implicitly as result)

Answer 11

Nibbles, 13 nibbles (6.5 bytes)

?`*!`\$[`\@]:

Attempt This Online!

?`*!`\$[`\@]: # full program
?`*!`\$[`\@]:$ # with implicit variable shown
? $ # index of the input array in
 `* # cartesian product of:
 ! : # zip together by concatenating elements:
 `\$[ # scan over input by minimum
 # (=cumulative minumum)
 `\@] # scan over input by maximum
 # (=cumulative maximum)

• Conor O'Brien: I'm always blown away by how simultaneously expressive and compact this language is, it's really something awesome. :D
• Dominic van Essen: @ConorO'Brien ...and it's relatively easy to learn, once one gets one's head around the concept of DeBruijn-indexed variables. There certainly aren't a huge number of built-ins to rememnber. Give it a shot! It'd be great to have some more Nibbles competition!

Answer 12

JavaScript (ES6), 39 bytes

Returns a Boolean value.

a=>a.every(m=v=>(v>a?v:a=v)<m?a==v:m=v)

Try it online!

Commented

a => // a[] = input array, re-used as the lower bound
a.every(m = // m = upper bound, initially NaN'ish
 v => // for each value v in a[]:
 ( v > a ? // if v is greater than the lower bound:
 v // use v directly
 : // else:
 a = v // update the lower bound to v
 ) < m ? // if v is lower than the upper bound:
 a == v // success if the lower bound is equal to v
 // failure otherwise (v is between the 2 bounds)
 : // else:
 m = v // update the upper bound to v (truthy)
) // end of every()

Answer 13

Charcoal, 16 bytes

⬤θNo⟦⌊...θ⊕κ⌈...θ⊕κ⟧ι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the deque can be sorted, nothing if not. Explanation: Port of JonathanAllan's Jelly answer.

 θ Input array
⬤ All elements satisfy
 θ Input array
 ... Truncated to length
 κ Current index
 ⊕ Incremented
 ⌊ Minimum so far
 θ Input array
 ... Truncated to length
 κ Current index
 ⊕ Incremented
 ⌈ Maximum so far
 ⟦ ⟧ Make into list
 No Contains
 ι Current element
 Implicitly print

Answer 14

JavaScript (Node.js), 41 bytes

x=>!x.some(p=q=t=>t<x[0]?p<(p=t):q>(q=t))

Try it online!

Optimized

JavaScript (Node.js), 64 bytes

f=([c,...x],...a)=>c?f(x,c,...a)|f(x,...a,c):!a.some(p=>c>(c=p))

Try it online!

Raw parse of question

Answer 15

Go, 119 bytes

import."slices"
func f(l[]int)bool{for i:=1;i<len(l);i++{if p,e:=l[:i],l[i];e>Min(p)&&e<Max(p){return 0>1}}
return 0<1}

Attempt This Online!

Uses the fact (pointed out by @akamayu) that each element must be either the minimum or the maximum of it and all elements before it.

Answer 16

J, (削除) 16 (削除ここまで) 14 bytes

*/@:+&(=>./\)-

Try it online!

-2 thanks to Bubbler!

Based on akamayu's idea, but applies max-scan to both the input and its negation instead of applying max and min scans, which saves bytes in J vs APL.

• Bubbler: -1: */@:+.&(=>./\)- or */ .+.&(=>./\)-
• Bubbler: Also I think it's OK to use + instead of +. since any nonzero is truthy.
• Jonah: Thanks! I thought the +. over + was more of a codegolf site convention (meaning truthy/falsy return values need to be 1 of 2 distinct values), but since it's your question I'm happy to take advantage of that flexibility.