Double dequer sort

Question

In this challenge Bubbler describes sorting a list by inserting its elements left to right into a double ended queue or "deque".

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.

That challenge asks if it is possible to sort a given array using this procedure. That is it possible to choose a pattern of fronts and backs which yields a sorted deque at the end.

In this challenge we ask whether it is possible to do sort a list by following this procedure twice. That is:

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.

Then take a number from the front of that deque and push it into one of the two ends of a new deque. Repeat this until the first deque is empty.

For example the list [4,5,6,1,2,3] cannot be sorted using one pass of this procedure. However with one pass we can get the list [3,2,1,4,5,6] which can be sorted with another pass.

Not all lists can be sorted in two passes however. For example [5,3,4,1,2] requires a minimum of 3 passes to sort.

Task

Given an array of positive integers determine if it can be sorted in two passes of the procedure. Output one of two distinct consistent values depending on whether the input is possible or impossible to sort in two passes.

This is code-golf. The goal is to minimize the size of your source code as measured in bytes.

Test cases

Possible

[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]
[1,3,2]
[3,4,5,1,2,3]

Impossible

[5,3,4,1,2]
[7,5,6,3,4,1,2]
[7,8,9,3,4,5,1,2,3]

• Bubbler: Imaginary bonus points for answers that solve this in linear time in terms of input length.
• Jonah: This is an excellent challenge title
• Jonah: @Bubbler May I assume you know the linear time solution is possible?
• Bubbler: @Jonah Yes, I'm pretty sure I've got such an algorithm. Though you need an actual deque or many variables to achieve that, so it's probably not suited for golf in many languages.

Answer 1

Nekomata + -e, 14 bytes

o2ドルŋ{Jĭajd↔,}=

Attempt This Online!

o2ドルŋ{Jĭajd↔,}=
o Sort the input
 $ Push the input again
 2ŋ{ } Apply the following function twice:
 J Nondeterministically partition the input
 e.g. [4,3,5,2,6,1] may become [[4,3],[5],[2],[6],[1]]
 ĭ Uninterleave
 e.g. [[4,3],[5],[2],[6],[1]] -> [[4,3],[2],[1]], [[5],[6]]
 aj Concatenate both parts
 e.g. [[4,3],[2],[1]], [[5],[6]] -> [4,3,2,1],[5,6]
 d↔ Reverse the first part
 e.g. [4,3,2,1],[5,6] -> [1,2,3,4],[5,6]
 , Join the two parts
 e.g. [1,2,3,4],[5,6] -> [1,2,3,4,5,6]
 = Check equality (comparing to the sorted input)

Answer 2

JavaScript (Node.js), 78 bytes

f=(x,g=i=4)=>x.reverse().map((c,i)=>c<Math.max(...x)?++g:x[i]=0)|i?f(x,--i):!g

Try it online!

-2 bytes from Neil(may extra -1(削除) or -2 (削除ここまで)if weaker output format)

Polynomial time

• Samuel Jahnke: how do you even begin to write something like this? please comment if you have time, I want to learn and improve
• l4m2: @SamuelJahnke What?
• Samuel Jahnke: how did you learn to code like this? what is your process?
• Neil: I got your polynomial answer down to 79 bytes with inverted output: f=(x,i=4)=>x.reverse().map(g=(c,i)=>c<Math.max(...x)?++g:x[i]=0)&&i?f(x,i-1):!g

Answer 3

05AB1E, 20 bytes

".œειćRíì ̃"D...D{QJ.Và

Port of @alephalpha's Nekomata answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

".œειćRíì ̃" # Push this string
 D # Duplicate it
 ...D{Q # Push string "D{Q"
 J # Join the stack together: ".œειćRíì ̃.œειćRíì ̃D{Q"
 .V # Evaluate and execute as 05AB1E code (see below)
 à # Check if any is truthy by taking the flattened maximum
 # (which is output implicitly as result)
.œ # Get all partitions of the (implicit) input-list
 ε # Map over each partition:
 ι # Uninterleave it into two parts
 ć # Head extracted
 R # Reverse the list of parts
 í # And also reverse each inner part itself
 ì # Prepend it back to the other part
 ̃ # Flatten all of it to a single list
 .œειćRíì ̃ # Do the same for each of those inner lists
 D # Duplicate each of those inner-most lists
 { # Sort the copy
 Q # Check if the two are equal (aka it was already sorted)

Answer 4

Elisp 226 bytes

(defun d(i r)(let((o(list(pop i))))(while(and i o)(let((n(pop i)))(if(<= n(car o))(setq o(cons n o))(if(>= n(car(last o)))(setq o(append o(list n)))(if r(progn(setq o(cons n o))(if(not i)(setq o(d o nil))))(setq o nil))))))o))

Try it online!

ungolfed:

(defun double-dequer-sort (input recursive)
 (let ((output (list (pop input))))
(while (and input output)
 (let ((next (pop input)))
 (if (<= next (car output))
 (setq output (cons next output))
 (if (>= next (car (last output)))
 (setq output (append output (list next)))
 (if recursive
 (progn
 ;; no idea whether to add to end or beginning here
 (setq output (cons next output))
 (if (not input)
 (setq output (double-dequer-sort output nil))
 )
 )
 (setq output nil)
 )
 )
 )
 )
 )
output
)
 )

Answer 5

Charcoal, 26 bytes

F3«≔⮌θθFLθ¿=§θκ⌈θ§≔θκ0»¬⌈θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for double dequer, nothing if not. Explanation: Assumes the correctness of @l4m2's polynomial time algorithm.

F3«

Repeat thrice.

≔⮌θθ

Reverse the array.

FLθ

Loop over its indices.

¿=§θκ⌈θ

If this element is the maximum of those remaining, then...

§≔θκ0

... replace it with 0.

»¬⌈θ

If the array only contains 0s then the original array was double dequer.

Unfortunately MapCommand only updates the array at the end of the map, otherwise you could write something like this for 20 bytes:

F3«≔⮌θθUMθ∧−κ⌈θ껬⌈θ

29 bytes to support all integers:

F3«≔⮌θθF⮌Eθλ¿=§θκ⌊θ≔Φθ−μκ軬θ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for double dequer, nothing if not. Explanation: Assumes the correctness of @l4m2's polynomial time algorithm.

F3«

Repeat thrice.

≔⮌θθF⮌Eθλ

Reverse the array and then loop over its indices in reverse. (This is because I want to be able to remove elements as I go.)

¿=§θκ⌊θ

If this element is the minimum of those remaining, then...

≔Φθ−μκθ

... remove that element.

»¬θ

If the array is now empty then the original input was double dequer.