11
\$\begingroup\$

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 . 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]
Improve this question
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Imaginary bonus points for answers that solve this in linear time in terms of input length. \$\endgroup\$ Commented Jul 24, 2024 at 4:44
  • 2
    \$\begingroup\$ This is an excellent challenge title \$\endgroup\$ Commented Jul 26, 2024 at 1:17
  • \$\begingroup\$ @Bubbler May I assume you know the linear time solution is possible? \$\endgroup\$ Commented Jul 26, 2024 at 5:38
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Jul 26, 2024 at 6:08

5 Answers 5

Reset to default
6
\$\begingroup\$

Nekomata + -e, 14 bytes

o$2ᵑ{Jĭᵃjᵈ↔,}=

Attempt This Online!

o$2ᵑ{Jĭᵃjᵈ↔,}=
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]]
       ᵃj           Concatenate both parts
                    e.g. [[4,3],[2],[1]], [[5],[6]] -> [4,3,2,1],[5,6]
         ᵈ↔         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)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ how do you even begin to write something like this? please comment if you have time, I want to learn and improve \$\endgroup\$ Commented Jul 24, 2024 at 13:25
  • \$\begingroup\$ @SamuelJahnke What? \$\endgroup\$ Commented Jul 24, 2024 at 16:51
  • \$\begingroup\$ how did you learn to code like this? what is your process? \$\endgroup\$ Commented Jul 24, 2024 at 23:53
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Commented Jul 25, 2024 at 13:02
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
)
  )
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 26 bytes

Ｆ³«≔⮌θθＦＬθ¿⁼§θκ⌈θ§≔θκ⁰»¬⌈θ

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.

Ｆ³«

Repeat thrice.

≔⮌θθ

Reverse the array.

ＦＬθ

Loop over its indices.

¿⁼§θκ⌈θ

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

§≔θκ⁰

... 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:

Ｆ³«≔⮌θθＵＭθ∧⁻κ⌈θ껬⌈θ

29 bytes to support all integers:

Ｆ³«≔⮌θθＦ⮌Ｅθλ¿⁼§θκ⌊θ≔Φθ⁻μκ軬θ

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.

Ｆ³«

Repeat thrice.

≔⮌θθＦ⮌Ｅθλ

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.