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]

Related: Antsy Permutations, which I think is this restricted to permutations — xnor
– xnor, Commented Jul 15, 2024 at 20:48

akamayu · Accepted Answer · 2024-07-16 00:31:57Z

11

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)

edited Jul 16, 2024 at 0:31

answered Jul 15, 2024 at 8:39

akamayu

1,1553 silver badges8 bronze badges

1

\$\begingroup\$ apl -3: ⊢∧.∊⌈⍀,¨⌊⍀ \$\endgroup\$

att
– att

2024-07-15 18:01:53 +00:00
Commented Jul 15, 2024 at 18:01
1

\$\begingroup\$ uiua -1: /↧↥∩=⊃⟜\↧⟜\↥, and -2 with a slightly different approach: /↧↥∩=∩⟜\↥¯. \$\endgroup\$

ovs
– ovs

2024-07-18 15:41:53 +00:00
Commented Jul 18, 2024 at 15:41

Add a comment |

Albert.Lang · Accepted Answer · 2024-07-15 23:53:38Z

9

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.

edited Jul 15, 2024 at 23:53

answered Jul 15, 2024 at 2:18

Albert.Lang

6,0347 silver badges29 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2024-07-15 02:30:23Z

8

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}

edited Jul 15, 2024 at 2:30

answered Jul 15, 2024 at 1:55

Jonathan Allan

115k8 gold badges68 silver badges293 bronze badges

Add a comment |

pajonk · Accepted Answer · 2024-07-15 06:26:26Z

8

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))

answered Jul 15, 2024 at 6:26

pajonk

19.4k5 gold badges29 silver badges78 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2024-07-15 00:51:48Z

7

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?

answered Jul 15, 2024 at 0:51

emanresu A

46.2k5 gold badges111 silver badges257 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2024-07-15 02:08:07Z

7

Nekomata + `-e`, 6 bytes

pƆᵗ≤ᵗ≥

Attempt This Online!

This swaps truthy and falsy.

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

answered Jul 15, 2024 at 2:08

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

Add a comment |

Unrelated String · Accepted Answer · 2024-07-15 01:02:56Z

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?

Wheat Wizard · Accepted Answer · 2024-07-15 19:07:15Z

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.

Bubbler · Accepted Answer · 2024-07-16 04:20:10Z

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

Kevin Cruijssen · Accepted Answer · 2024-07-15 07:53:22Z

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)

Dominic van Essen · Accepted Answer · 2024-07-15 15:44:37Z

4

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)

answered Jul 15, 2024 at 15:44

Dominic van Essen

37.2k2 gold badges24 silver badges61 bronze badges

1

\$\begingroup\$ I'm always blown away by how simultaneously expressive and compact this language is, it's really something awesome. :D \$\endgroup\$

Conor O'Brien
– Conor O'Brien

2024-07-16 01:40:42 +00:00
Commented Jul 16, 2024 at 1:40
1

\$\begingroup\$ @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! \$\endgroup\$

Dominic van Essen
– Dominic van Essen

2024-07-16 08:39:43 +00:00
Commented Jul 16, 2024 at 8:39

Add a comment |

Arnauld · Accepted Answer · 2024-07-16 08:52:10Z

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()

Neil · Accepted Answer · 2024-07-15 07:46:24Z

Charcoal, 16 bytes

⬤θ№⟦⌊…θ⊕κ⌈…θ⊕κ⟧ι

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
  №                 Contains
               ι    Current element
                    Implicitly print

l4m2 · Accepted Answer · 2024-07-15 01:21:16Z

2

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

edited Jul 15, 2024 at 1:21

answered Jul 15, 2024 at 1:02

l4m2

32.4k2 gold badges26 silver badges115 bronze badges

Add a comment |

bigyihsuan · Accepted Answer · 2024-07-15 14:00:06Z

2

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.

answered Jul 15, 2024 at 14:00

bigyihsuan

11.4k1 gold badge30 silver badges70 bronze badges

Add a comment |

Jonah · Accepted Answer · 2024-07-26 05:04:23Z

1

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.

edited Jul 26, 2024 at 5:04

answered Jul 26, 2024 at 1:48

Jonah

34.1k4 gold badges41 silver badges95 bronze badges

1

\$\begingroup\$ -1: */@:+.&(=>./\)- or */ .+.&(=>./\)- \$\endgroup\$

Bubbler
– Bubbler

2024-07-26 03:53:38 +00:00
Commented Jul 26, 2024 at 3:53
\$\begingroup\$ Also I think it's OK to use + instead of +. since any nonzero is truthy. \$\endgroup\$

Bubbler
– Bubbler

2024-07-26 04:02:36 +00:00
Commented Jul 26, 2024 at 4:02
\$\begingroup\$ 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. \$\endgroup\$

Jonah
– Jonah

2024-07-26 05:05:57 +00:00
Commented Jul 26, 2024 at 5:05

Add a comment |

Stack Exchange Network

Sorting with a deque

Test cases

16 Answers 16

K (ngn/k), 17 bytes

APL(Dyalog Unicode), 13 10 bytes ^SBCS

Uiua, 14 13 bytes

Python, 45 bytes

Jelly, 7 6 bytes

How?

R, 30 bytes

Vyxal, 9 bytes

Nekomata + `-e`, 6 bytes

Jelly, 8 bytes

Jelly, 8 bytes

Haskell + hgl, 23 bytes

Explanation

Alternative algorithm, 34 bytes

Explanation

Reflection

K (ngn/k), 13 bytes

05AB1E, 11 10 bytes

Nibbles, 13 nibbles (6.5 bytes)

JavaScript (ES6), 39 bytes

Commented

Charcoal, 16 bytes

JavaScript (Node.js), 41 bytes

JavaScript (Node.js), 64 bytes

Go, 119 bytes

J, 16 14 bytes

Your Answer

Linked

Hot Network Questions

Sorting with a deque

Test cases

16 Answers 16

K (ngn/k), 17 bytes

APL(Dyalog Unicode), 13 10 bytes SBCS

Uiua, 14 13 bytes

Python, 45 bytes

Jelly, 7 6 bytes

How?

R, 30 bytes

Vyxal, 9 bytes

Nekomata + -e, 6 bytes

Jelly, 8 bytes

Jelly, 8 bytes

Haskell + hgl, 23 bytes

Explanation

Alternative algorithm, 34 bytes

Explanation

Reflection

K (ngn/k), 13 bytes

05AB1E, 11 10 bytes

Nibbles, 13 nibbles (6.5 bytes)

JavaScript (ES6), 39 bytes

Commented

Charcoal, 16 bytes

JavaScript (Node.js), 41 bytes

JavaScript (Node.js), 64 bytes

Go, 119 bytes

J, 16 14 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

APL(Dyalog Unicode), 13 10 bytes ^SBCS

Nekomata + `-e`, 6 bytes