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:
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())
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.
Last edited by Hippo on Wed Jan 11, 2017 11:48 am, edited 1 time in total.
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.
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.
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?
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:
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?
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?
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).
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.
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.
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.
.
.