hacker.org

Posted: **Tue Jan 10, 2017 2:47 pm**

a.goth wrote:
Hippo wrote: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!

So you are ok on sequences where for k-th sorted number there is in the input sequence at most one higher number after it (except when the number was local minima).

Better ... there could be only one higher number after the max position of the number and the first smaller number.

(efbgdac is fine e->b(g), f->b(g), b->a(c), g->d(), d->a(),a->a(c), c->c())

Let me bound the probabilty later ...

Posted: **Tue Jan 10, 2017 2:47 pm**

OK ... another aproach ... there are 16! permutations, your algorithm does 29 comparisons. So it distinguish at most 2^29 of 16! of them so I hope success probability is less than 2^29/16!<1/38971.

Posted: **Tue Jan 10, 2017 9:44 pm**

Hippo wrote:OK ... another aproach ... there are 16! permutations, your algorithm does 29 comparisons. So it distinguish at most 2^29 of 16! of them so I hope success probability is less than 2^29/16!<1/38971.

If I have not miscounted, the probability of success is 49,926,400 / 20,922,789,888,000 = 2.38622e-6. Not very promising.

Posted: **Thu Jan 12, 2017 1:12 am**

Honestly, I think that when an answer has been rejected as wrong once, it should be rejected always.
A correct solution should be a solution that always produces a correct result, not just very rarely.

Posted: **Thu Jan 12, 2017 7:23 pm**

AMindForeverVoyaging wrote:Honestly, I think that when an answer has been rejected as wrong once, it should be rejected always.
A correct solution should be a solution that always produces a correct result, not just very rarely.

It depends. I agree, if it was sheer coincidence that the solution was accepted and therefore is not repeatable by others. Otherwise, if the probability of success is sufficiently large, I would call it a creative and ingenious solution. And is not that what hacking is all about? Being creative and ingenious?

Posted: **Thu Jan 12, 2017 8:56 pm**

I was able to reduce the number of cycles, but not the instructions:

Code: Select all

1@0@¬@@@@@@@ ,,x?$<x1+00>vx2^dxdv00<^?$p04gP100>1^?$p!

Does no one have any better idea?

Posted: **Fri Jan 13, 2017 8:01 pm**

a.goth wrote:I was able to reduce the number of cycles, but not the instructions:
Code: Select all
1@0@¬@@@@@@@ ,,x?$<x1+00>vx2^dxdv00<^?$p04gP100>1^?$p!
Does no one have any better idea?

I had

Code: Select all

¬@0@@@@@ ,,x?$g1vpP1^?$p!

As an reversion alternative using 00 for gP instead of removing unwanted 0 from the top of the stack.
But it didn't help with the total code length.

I have no new ideas ...

Posted: **Sat Jun 17, 2017 9:26 am**

This challenge drives me nuts!

Although the description of SuperHack suggests differently, the array bounds of the code array are never checked and it is virtually unlimited. Equipped with this knowledge, I was able to write the following program, whose code size is 52:

Code: Select all

!/?x-1v1px:1g0x\s1=:*44x+\
â€\1v18gP,?\1+s=/%0s\1,0w1/

The special character at the lower left stands for the non-printing character NUL. But due to the cycle limit, it only works for positive numbers less than or equal to 864. Can the program be improved somehow? Does it pave the way for a new idea?

Posted: **Sun Jun 18, 2017 11:36 am**

a.goth wrote:This challenge drives me nuts!
Code: Select all
!/?x-1v1px:1g0x\s1=:*44x+\
â€\1v18gP,?\1+s=/%0s\1,0w1/

Code: Select all

!/?x-1v1px:1g0x\s1/s?=w\
â€\1v18gP,?\1+s=/%s\01,0/

Could be improvement of the starting loop (for 0 limited imput sequence). Oh no, I have missed you need the count for output.

Posted: **Sun Jun 18, 2017 12:02 pm**

OK let you see the KOTH time version

Of course some details are hidden in the distance

.

(The horizontal blue in the center is waiting not to improve the KOTH limit)

Posted: **Mon Jun 26, 2017 4:49 pm**

Wow, this is a monster of a SuperHack program! Thank you very much, Hippo, for sharing the image with us and I knew why I have not tackled the challenge yet. I would not have the proper tools to write such a giant SuperHack program.

I only see that you have used all 32 possible threads. That is, your SuperHack program executes no more than 32 * 267 = 8,544 instructions to sort and print the list of 64 integers. May I know how many comparisons are made and do the different colours in the image have a certain meaning?

Posted: **Mon Jun 26, 2017 6:17 pm**

a.goth wrote: I only see that you have used all 32 possible threads. That is, your SuperHack program executes no more than 32 * 267 = 8,544 instructions to sort and print the list of 64 integers. May I know how many comparisons are made and do the different colours in the image have a certain meaning?

The colors just denote the execution time (and are repeated) to help debugging sync problems. I do think this is coloring done by about 10 test cases (so some instructions may remain uncolored even when they are needed). The code starts with 2 NOP instructions

. It's mergesort cuircuit as I have described somewhere else. ... So it does 32 + 32 + 16 + 32 + 16 + 24 + 32 + 16 + 24 + 28 + 32 + 16 + 24 + 28 + 30 + 32 + 16 + 24 + 28 + 30 + 31 comparisons. = 32*21-5*16-4*8-3*4-2*2-1*1=543 (depth 21).

P.S.: I cannot share the fast string reversal as it would reveal too much. But it's picture is marvelous
(and I even have not the fastest known solution).

Posted: **Fri Jun 30, 2017 2:52 pm**

Hippo wrote:The code starts with 2 NOP instructions . It's mergesort cuircuit as I have described somewhere else. ... So it does 32 + 32 + 16 + 32 + 16 + 24 + 32 + 16 + 24 + 28 + 32 + 16 + 24 + 28 + 30 + 32 + 16 + 24 + 28 + 30 + 31 comparisons. = 32*21-5*16-4*8-3*4-2*2-1*1=543 (depth 21).

You have described your approach to solving the challenge in this thread and you must use Batcher's odd-even mergesort, right? I also planned to use this algorithm, but I absolutely do not know how to achieve a fast implementation.

Amazingly enough, the minimal number of comparisons needed to sort n elements is known only for 1 ≤ n ≤ 15.

Posted: **Fri Jun 30, 2017 3:27 pm**

Hippo wrote:P.S.: I cannot share the fast string reversal as it would reveal too much. But it's picture is marvelous (and I even have not the fastest known solution).

No worries! This is the one of the three remaining SuperHack challenges that I consider to be solvable, although I have no clue yet. I am looking forward to the smashing solution, which was already very much applauded by adum in this post.

I think that just 14 SuperHack challenges are far too few. I love this esolang.

Posted: **Sun Jul 02, 2017 10:41 am**

a.goth wrote: You have described your approach to solving the challenge in this thread and you must use Batcher's odd-even mergesort, right? I also planned to use this algorithm, but I absolutely do not know how to achieve a fast implementation.

Amazingly enough, the minimal number of comparisons needed to sort n elements is known only for 1 â‰¤ n â‰¤ 15.

Yes, and as I have written first unfinished tries of me lead to about 300 cycles and making comparators faster and sync them quickly was another challenge

.

BTW: number of comparisons is not important ... the depth of the circuit is important.

hacker.org

Jeux du Sort

Re: Tiny Sort

Re: Tiny Sort

Re: Tiny Sort

On hacking

Tiny Sort

Re: Tiny Sort

Tiny Sort

Re: Tiny Sort

Jeux du Sort Vite

Re: Jeux du Sort Vite

Re: Jeux du Sort Vite

Fast String Reversal

Re: Jeux du Sort Vite