4
\$\begingroup\$

Pseudo-Quantum Bogosort

Quantum Bogosort is as follows:

  1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.

  2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)

  3. All remaining universes contain lists which are sorted.

Source

Given that we cannot destroy the universe, the next best thing is to destroy a thread!

The challenge is as follows: Make a new thread/branch for each possible permutation of a list and if the list is not sorted, destroy the thread/branch (or just dont output it)

Rules

Input is a list of length 4 or less

Output should be the randomized list for each thread or branch that successfully sorted it. Destroying/exiting the thread or branch is optional, but funny.

If there is a repeated number, output list duplicates.

This is standard code-golf

Test cases:

[1,4,2,9] -> [1,2,4,9]
[3,1,1,9] -> [1,1,3,9] and [1,1,3,9]
[3,1,1,3] -> [1,1,3,3] [1,1,3,3] [1,1,3,3] [1,1,3,3]

\$\endgroup\$
17
  • 3
    \$\begingroup\$ why am I like this \$\endgroup\$
    – pacman256
    Sep 6, 2023 at 15:00
  • 4
    \$\begingroup\$ This is a funny idea but it seems like an unobservable requirement :o \$\endgroup\$ Sep 6, 2023 at 15:07
  • 3
    \$\begingroup\$ @Pacmanboss256 - from your response below my Husk answer, I still can't tell whether you're insisting on the unobservable requirement to use 'branches' (whatever they are) or parallel threading (whatever that is). \$\endgroup\$ Sep 6, 2023 at 16:14
  • 3
    \$\begingroup\$ That doesn't change the fact that "Make a new thread/branch..." is an unobservable requirement \$\endgroup\$
    – Luis Mendo
    Sep 6, 2023 at 19:24
  • 5
    \$\begingroup\$ @ATaco Is it? How can that be observed? Note that by "observe" we mean when the program is treated as a black box \$\endgroup\$
    – Luis Mendo
    Sep 6, 2023 at 23:16

6 Answers 6

2
\$\begingroup\$

Husk, 5 bytes

fS=OP

Try it online!

Quite closely follows the description.

    P  # Make a list with an element for each possible permutation of the input list
f      # Destroy (or just don't output) any element that doesn't satisfy: 
 S=O   #   it's sorted
\$\endgroup\$
6
  • \$\begingroup\$ It looks like there's no threading here: the f seems to just be a "filter". I'll ask OP whether this is ok, as it seems like this would be a nice challenge without all the threading stuff. \$\endgroup\$
    – MTN
    Sep 6, 2023 at 15:55
  • 3
    \$\begingroup\$ @MTN - f is indeed filter. I have no idea whether this is implemented by the Husk interpreter by threading or otherwise, and I have no way to find out. The output would be identical either way. \$\endgroup\$ Sep 6, 2023 at 15:57
  • \$\begingroup\$ Yeah, it doesn't look like it uses threading (github.com/barbuz/Husk/blob/master/Builtins.hs#L412). Anyway, let's wait for clarification from OP. \$\endgroup\$
    – MTN
    Sep 6, 2023 at 16:01
  • 3
    \$\begingroup\$ @MTN that is only an implementation of Husk though. That is a part of the reason unobservable requirements are considered bad. The other is that they basically prescribe the answer, which is pretty dull. \$\endgroup\$ Sep 6, 2023 at 16:27
  • 3
    \$\begingroup\$ @JonathanAllan I agree - I would prefer it if the threading thing was dropped. \$\endgroup\$
    – MTN
    Sep 6, 2023 at 17:10
2
\$\begingroup\$

Python, 77 bytes

lambda l:[x for x in permutations(l)if[*x]==sorted(x)]
from itertools import*

Attempt This Online!

\$\endgroup\$
4
  • \$\begingroup\$ Is destroying the threads unreasonable because I'm fine with removing that part \$\endgroup\$
    – pacman256
    Sep 6, 2023 at 15:07
  • \$\begingroup\$ @Pacmanboss256 yeah, it probably is unreasonable. \$\endgroup\$
    – MTN
    Sep 6, 2023 at 15:08
  • 1
    \$\begingroup\$ The second version seems wrong: there should be 4 outputs for an input of [3,3,1,1]. \$\endgroup\$ Sep 6, 2023 at 15:54
  • 1
    \$\begingroup\$ @DominicvanEssen fixed, thanks \$\endgroup\$
    – MTN
    Sep 6, 2023 at 15:57
2
\$\begingroup\$

Nekomata, 3 4 bytes

Edit: +1 byte to fix (unobservable) mechanism-of-action, thanks to alephalpha.

↕:o=

Attempt This Online!

Nekomata seems well-suited for this.
Default behaviour is to output all successful forks.

↕      # non-deterministically choose a permutation of the input list
 :     # duplicate it
  o=   # keep one duplicate if it's equal to the other, sorted 
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Sorry, I think it should be ↕:o=. Nekomata is stack-based. ↕= finds a permutation that is equal to the input list, and o sorts it. Pseudo-quantum bogosort is an unobservable requirement though. \$\endgroup\$
    – alephalpha
    Sep 8, 2023 at 3:31
  • 1
    \$\begingroup\$ @alephalpha - Ah! Thanks for the explanation! Indeed, the unobservability made it difficult for me to be sure that the code was really doing what I wanted, of course. Perhaps this can serve as a genuine example of why unobservable requirements are a bad thing... \$\endgroup\$ Sep 8, 2023 at 6:01
  • \$\begingroup\$ @alephalpha - I've linked your comment: please don't delete it! \$\endgroup\$ Sep 8, 2023 at 6:07
1
\$\begingroup\$

Factor + math.combinatorics, 49 bytes

[ <permutations> [ dup sort = ] parallel-filter ]

Attempt This Online!

parallel-filter is a version of filter that spawns cooperative threads to handle each iteration.

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

Charcoal, 40 bytes

⊞υ⟦⟧Fθ≔ΣEυE⁻Eθνκ⁺κ⟦μ⟧υFυUMι§θκEΦυ⁼ι⌊υ⭆¹ι

Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ⟦⟧Fθ≔ΣEυE⁻Eθνκ⁺κ⟦μ⟧υ

Generate all of the permutations of the indices of the input. This is taken from my answer to Count N-Rich Permutations of an Integer Sequence. I use the indices because they're unique and it makes it easier to generate the permutations.

FυUMι§θκ

Map each index to the actual value from the input list.

EΦυ⁼ι⌊υ⭆¹ι

Pretty print those that equal the minimum i.e. sorted value.

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

Python 3.8+, 75 bytes

lambda a:filter(min(p:=[*permutations(a)]).__eq__,p)
from itertools import*

An unnamed function that accepts a tuple and returns a generator.

Try it online!

How?

a is the input tuple. p is initialised to a list of all permutations of a. A condition of being equal to the minimal permutation is then used to create a filter object.


Also, non-conforming but interesting at 62 bytes:

lambda a:8**sum(a.count(v)**7-1for v in{*a})%66%26*[sorted(a)]

Try it online!

The number of repeats of the sorted list needs to be \$\prod_{m \in \text{multiplicities}} m!\$, e.g. [5,4,5,5] has multiplicities [3,1] and \$3!1!=6\$.

But that's going to cost a lot of bytes. However, since the input has a length of at most four there are only twelve cases to handle by multiplicity, so I thought a hash might be golfier, so I had a play and came up with:

multiplicities **7-1 sum 8**sum%66%26 == required length
[] [] 0 1
[1] [0] 0 1
[2] [127] 127 2
[3] [2187] 2187 6
[4] [16383] 16383 24
[1,1] [0,0] 0 1
[1,2] [0,127] 127 2
[1,3] [0,2187] 2187 6
[2,2] [127,127] 254 4
[1,1,1] [0,0,0] 0 1
[1,1,2] [0,0,127] 127 2
[1,1,1,1] [0,0,0,0] 0 1

...it's certainly shorter than this, more logical, shortcut for lists of length at most four (71):

lambda a:(sum((c:=a.count(v))*~-c*-~(c>3)for v in{*a})or 1)*[sorted(a)]
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.