Jeux du Sort

[Hippo]

Hmm, I cannot find my original solution.
My current bublesort like solution looks following way (6110 cycles):

Code: Select all

0,,@2@@@@@@@@@@ xv2vx2^d1-1^d1+v2v1+x^?$1[,21^?$g1vpP22^?$1vp!                    

(Too long for Kolmogorov KOTH challenge)

For Time KOTH challenge threading and algorithms inspired by comparator circuits were required.

[a.goth]

Hmm, I cannot find my original solution.
My current bublesort like solution looks following way (6110 cycles):

Code: Select all

0,,@2@@@@@@@@@@ xv2vx2^d1-1^d1+v2v1+x^?$1[,21^?$g1vpP22^?$1vp!

(Too long for Kolmogorov KOTH challenge)

I am currently working on challenge 'Tiny Sort' and since I could not beat your code size with my own approaches (so far), I analyzed and slightly shortened your SuperHack program:

Code: Select all

0,,2@@@@@@@@@@@ xv2vx2^d1-1^d1+v2v1+x^?$?,21^?$g1vpP22^?$?p!

A brilliant one-liner, by the way! Do you have an even shorter solution by now?

[Hippo]

A brilliant one-liner, by the way! Do you have an even shorter solution by now?

Actually not, I was not working on it for a while.

P.S.: Surely I would look on your improvement.

Oh, I have reread my code to understand it and found that I removed nonzero from the top inefficiently ? would be better. Then I have read your improvement ... and it was easy to understand as it was exactly what I got. ... except my starting @2@ rather to yours 2@@. My version allows more loops to be run (of course it was calced to be sufficient according to given parameters).

OK how it works ... it uses comparator to reorder top two stack elements to have minimum on top.
It inserts element on top of the stack and uses comparator to leave minimum on top comparing with all elements on the stack. When all elements were compared new insert is allowed.

Insert of zero immediately outputs top element (with comma) what invokes cycle comparing all elements with the top. When just one element remains, it is output.

Of course it is time inefficient ... meaning a lot of loop cycles is used as just minimum is detected losing all other comparison results. ... for K nonzeros followed by K-1 zeros it requires (1+2+...+(K-1)) cycles to output minimum and ((K-2)+(K-3)+...+2+1) cycles to output minima of remaining subsets.

Would it be possible to nest loops in such an order that input till first zero would be read first and loop using comparators would run afterwards? In that case much more zeros would be read, but
K+((K-1)+(K-2)+...+2+1) loops would suffice ...
For the size of code it has small influence, as one @ multiplies bound for loops by golden ratio and probably it is enough to cover this difference.

So the rearranged loop code must be at most the same size to improve the length of the whole code.

Here is the comparison of the ideas ... I have not tested it yet ... whether it actually works.

Code: Select all

0,,@2@@@@@@@@@@ xv2vx2^d1-1^d1+v2v1+x^?$1[,21^?$g1vpP22^?$1vp!                    
0,@2@@@@@@@@@ ,1v1^?$+xv2vx2^d1-1^d1+v2v1+x^?$?p01gP2x^?$?p!                    

Yes, it works, but needs 23 more chars to reduce to got to teebee's bound.
Comparator

Code: Select all

x2^d1-1^d1+v

takes a lot of space itself.
But surely there must be some bigger trick than improving this idea.

[a.goth]

I again analyzed and shortened your SuperHack program:

Code: Select all

0,2@@@@@@@@@@ ,1v1^?$+xv2vx2^dxdv2v1+x^?$?p01gP22^?$?p!

Happy holidays!

[Hippo]

I again analyzed and shortened your SuperHack program:

Code: Select all

0,2@@@@@@@@@@ ,1v1^?$+xv2vx2^dxdv2v1+x^?$?p01gP22^?$?p!

Happy holidays!

I am confused by your comparator

Code: Select all

x2^dxdv

Does 0/0 work on PHP version? I am a bit late to wish happy XMAS, but at least I am at time to wish happy new year.

Wow, really, PHP version complains, but the solution is accepted .
x/0 gives result 0 with "warning" ... good to know.

BTW: Frustrating is that teebee and tails went further during first day the challenge appeared.

[AMindForeverVoyaging]

BTW: Frustrating is that teebee and tails went further during first day the challenge appeared.

Not sure what you mean with that. This challenge (Jeux du Sort) appeared at the end of 2008 apparently, and teebee and tails solved it several days later.

Ah, perhaps you mean "Tiny Sort"?

[Hippo]

BTW: Frustrating is that teebee and tails went further during first day the challenge appeared.

Not sure what you mean with that. This challenge (Jeux du Sort) appeared at the end of 2008 apparently, and teebee and tails solved it several days later.

Ah, perhaps you mean "Tiny Sort"?

Sure

[a.goth]

It really bothers me that even for the simpler exercise of printing the integers in reverse order, I already need 25 instructions. Heck, how can you sort the sequence of numbers with only 12 additional or 37 instructions?

Currently, it is only exploited that the list contains exactly 16 positive numbers. Could one also take advantage of the fact that the length of the list is a power of 2, the list does not contain duplicates, or only a single list is tested? Something else?

[Hippo]

It really bothers me that even for the simpler exercise of printing the integers in reverse order, I already need 25 instructions. Heck, how can you sort the sequence of numbers with only 12 additional or 37 instructions?

Currently, it is only exploited that the list contains exactly 16 positive numbers. Could one also take advantage of the fact that the length of the list is a power of 2, the list does not contain duplicates, or only a single list is tested? Something else?

Do you mean

Code: Select all

@0@@@@@@ ,x?$+p09gP1^?$p!

?
Yes the comma separation prolongs the code a lot.

[edit]
address 8->9 forum post typo corrected (pointed out in next post)
[/edit]

[a.goth]

Do you mean

Code: Select all

@0@@@@@@ ,x?$+p08gP1^?$p!

?

Yes, almost exactly the same source code, however, yours separates the integers mistakenly by a space:

Code: Select all

0@@@@@@@ ,x?$[p09gP1^?$p!

Could it be done with fewer instructions?

[a.goth]

I am now down to 54 instructions:

Code: Select all

0@2@¬@@@@@@@ ,1v1^?$+xv2vx2^dxdv2v1+x^?$?p04gP22^?$?p!

I wish you all a Happy New Year!

[Hippo]

I am now down to 54 instructions:

Code: Select all

0@2@¬@@@@@@@ ,1v1^?$+xv2vx2^dxdv2v1+x^?$?p04gP22^?$?p!

I wish you all a Happy New Year!

Nice the comma for read which neednot be interpreted could be used to double call depth rather to get next Fibonacci depth ... what is sufficient enough here.

[a.goth]

Since the SuperHack program is checked with only one test case, I now believe that the solution is an algorithm that does not always sort correctly. Like the one here, although its probability of success is vanishingly small at 35,357,670 / 20,922,789,888,000 = 1.68991e-6 (if the test cases are chosen randomly). What do you think about it? Do you agree?

[Hippo]

Since the SuperHack program is checked with only one test case, I now believe that the solution is an algorithm that does not always sort correctly. Like the one here, although its probability of success is vanishingly small at 35,357,670 / 20,922,789,888,000 = 1.68991e-6 (if the test cases are chosen randomly). What do you think about it? Do you agree?

I don't think you could wait till such small probability happens. ... I am still waiting for something like 1/13000 and it takes years .

[a.goth]

I don't think you could wait till such small probability happens. ... I am still waiting for something like 1/13000 and it takes years .

Of course, that was just an example. The idea is to find an algorithm whose probability of success, for the applied test cases, is sufficiently large. Currently I am experimenting with the following SuperHack program:

Code: Select all

0,@@@@@@@ x2^dxdv,x?$[p01gP1^?$p!

Happy hacking!