Jeux du Sort

[a.goth]

Okay, as an exercise, I have tried to find the fastest possible SuperHack programs for the first powers of two. That is, to sort and print a list of one, two, or four integers, from lowest to highest separated by commas:

Code: Select all

,p!

(1 Thread, 0 Comparisons, 3 Cycles)

Code: Select all

&\,,x2^dxdvpp
 \====}02gP!

(2 Threads, 1 Comparison, 12 Cycles)

Code: Select all

,                              !
                               p
                               p
                               |
                               \:1vpp!
                                ^
                                2
                      !         x
                      p         <
                      p         1     !
                      v         0     p
                      1         |     p
                      :^2x<10v1:/     |
                  !pp=/        ^      \:1vpp!
                               2       ^
                               x       2
                               <       x
                               0       <
                               0       1
                               v       0
                               1       v
                     %&\},,1^1^:       1
                       ,       \=00<x2^:       /=pp!
                       ,               \=01<x2^:
                       1                       1
                       ^                       v
                       1                       p
pPPPxxg00p<11=\        ^                       p
              :^2x<01v1:\                      !
              1         |
              v         1
              1         0
              1         <
              <         x
              p         2
              0         ^
              0        /:1v11<p00gxxPPPp
              g        |
              x        1
              x        1
              P        <
              P        p
              P        0
              p        0
                       g
                       x
                       x
                       P
                       P
                       P
                       p

(2 Threads, 5 Comparisons, 33 Cycles)

Are these the fastest possible SuperHack programs? It is getting way too complicated for me much too early.

[Hippo]

Sorting one number is optimal, sorting 2 can be done faster.

Code: Select all

4,,&\&\}1gP         
pv]=:\1             
    |][             
    ]*p             
    *p!             
    p               

Looks much better ... and I am still not sure it's optimal.
Hmm I got a lot of solutions on 9 ticks.
I was trying hard to print in parallel and stop on 8th tick, but always one branch needs one tick more.

Code: Select all

4,,&\}1g&\P      
    &    ! 
pp*1/   
    :]v

Sorting of 4 cannot be optimal as you use 1^ rather to x, but again x2^ is subptimal.
... and you ignore equality case at all.

[a.goth]

Holy shit, this is crazy! Thank you, Hippo, for showing me how to interweave threads and I must say I like this esolang more and more.

I also need at least nine cycles and it seems to be the minimum. Let us try to get it as small as possible. My current best code size is 36:

Code: Select all

3,&\&\&\\
  p,s}s/|
/=]:]1vp|
p=]/ \gP!

By the way, has anyone ever wondered why the challenge has a French title? Does it have any meaning?

[Hippo]

I got this:

Code: Select all

4,,&\}1\ 
    &  g
pp*1/  P
    :]v!

But in the equaity case it needs nops outside the code.

Code: Select all

3,&\&\==\
 /p, }  &
 \]:]1vp/
  \/ \gP!

is a variant of your solution.

And finally there is 8 tick solution working except the equality case:

Code: Select all

3,&\&\}1g&&P
   , \&\=&&p
   &   |    
   :]1v!    
   |        
   |        
   &        
   p        

[a.goth]

I knew it was possible in eight cycles:

Code: Select all

4,&\&\}1g&P
   , \=&\&p
   &    !
   \1*p
  /:]v
  \/

A neat trick to create additional threads just to delay execution of instructions within a cycle. Is this the fastest and smallest possible?

[Hippo]

I knew it was possible in eight cycles:

Code: Select all

4,&\&\}1g&P
   , \=&\&p
   &    !
p*1/
 ==:]v
  =/

A neat trick to create additional threads just to delay execution of instructions within a cycle. Is this the fastest and smallest possible?

I like it ... it differs very slightly from my first attempts ... (of course staying on 1st read position of you helped a lot). There are just small cosmetic deviations possible.

(Now I see, I have edited out from the first post the 9tick version printing by other threads than thread branching (to v). ... and I let * trick version instead ... and both tricks were needed)

[a.goth]

Oh no, I have missed you need the count for output.

In fact, it is possible without explicitly counting the integers and can therefore be shrunk to code size 44:

Code: Select all

 !/?v3px:1g0\s11/?w0^\
␀,\11gPs\1+x/%0s\,x11/

Now it even works for positive numbers less than or equal to 962. However, still far from teebee's solution.

[a.goth]

Recently, I tried solving challenge 'Tiny Sort' based on the Lehmer RNG with parameters n = 17, g ∈ {±3, ±5, ±6, ±7}, and the seed not being a multiple of 17. (The probability that a randomly chosen number is a multiple of 17 is only 1/17 ≈ 6%.) With that said, the random number generator pseudo-randomly runs through the numbers from 1 to 16 exactly once before starting over:

    ,x35*,@@@@@@@ 1v,x?$0<g*89+1^1^d*-x00>^px?s!1-1v00gP$

It did not work out and is not small enough either, but it was worth a try. Happy hacking!