News for hackers. Stuff that matters.
Re:Is this the simplest (and most surprising) sorting algori... by GistNoesis on Tuesday October 05, 2021 @10:00AM (#28759601)
I remember asking the question on a stack-overflow site in 2015.

https://cs.stackexchange.com/questions/45348/why-does-this-s...

And it was answered successfully by pointing the same invariant they point in the paper.

I remember finding this program through via automatic program search, so the algorithm and the question of why it works as probably been discovered many times.

If only we had something that would allow to surface information from the vast amount of data available...

Re:Is this the simplest (and most surprising) sorting algori... by somenewaccount1 on Tuesday October 05, 2021 @11:03AM (#28760437)
Yes, but you asked a computer science question with computer code instead of "pseudo code and arguments of correctness.", as Rafael kindly reminded you. :)
Re:Is this the simplest (and most surprising) sorting algori... by civilized on Tuesday October 05, 2021 @11:07AM (#28760476)
That comment was a bit of an eye-roller. The post is perfectly clear as it stands.
Re:Is this the simplest (and most surprising) sorting algori... by liversage on Tuesday October 05, 2021 @12:09PM (#28761369)
The original question contained a sizeable chunk of what looks like C#. It was then edited and made much clearer perhaps in a response to the comment.
Re:Is this the simplest (and most surprising) sorting algori... by svat on Tuesday October 05, 2021 @01:07PM (#28762242)
Re:Is this the simplest (and most surprising) sorting algori... by aasasd on Tuesday October 05, 2021 @12:08PM (#28761361)
More like, GistNoesis used 0-based arrays and the paper uses 1-based arrays. “Arguments of correctness” sounds like Rafael basically told GistNoesis to answer themselves, which is of course a widely spread attitude on SE.
Re:Is this the simplest (and most surprising) sorting algori... by aasasd on Tuesday October 05, 2021 @04:14PM (#28764981)
Wait a minute! What the hell is ‘automatic program search’? Is it like with Malbolge where the first working programs had to be written through brute-force search?
Re:Is this the simplest (and most surprising) sorting algori... by GistNoesis on Wednesday October 06, 2021 @06:11AM (#28771213)
You define some test-unit cases, input-output pair.

You define some elementary blocks like in scratch (Blockly). And you try to randomly assemble the blocks so that they respect the type constraints. And you score your program based on the number of test case it got right.

For this simple problem, naive random search was all that was needed. (less than 100k programs evaluations)

But for more advanced cases you could use something like Genetic Programming with Koza's Automatically Defined Functions where you build an intermediate library of useful blocks.

Now one would use deep learning and produce source code directly with some tool like Copilot and run it until it passes all tests. Or if you want to get your hands dirty, you can re-implement the old school methods and use a neural network to make the pick decisions instead of a random pick.

Once you have programs that pass all test cases, you can try to prove correctness (that's more something like HOL-Light would do) and whether or not they are equivalent (and equivalent to a formal specification) and optimize them further by transforming the program.

Re:Is this the simplest (and most surprising) sorting algori... by aasasd on Wednesday October 06, 2021 @09:27AM (#28772892)
Interesting, thanks!
Re:Is this the simplest (and most surprising) sorting algori... by gnramires on Tuesday October 05, 2021 @11:07AM (#28760474)
I think we should start recognizing more alternate information sources, such as blogs and stack exchange (i.e. attribute scientific credit and recognition to those posts).

Of course traditional scientific publishing has its place (including the care for methodology and source citation)... but many people will search directly those websites instead, so clearly it's an important emerging source of information and discovery.

Re:Is this the simplest (and most surprising) sorting algori... by jvanderbot on Tuesday October 05, 2021 @10:25AM (#28759912)
Write it down or it didn't happen. More directly, write down the result separate from the method or it won't be discovered by the right audience.
Re:Is this the simplest (and most surprising) sorting algori... by Cryptonic on Tuesday October 05, 2021 @10:05AM (#28759655)
Maybe there gotta be a paper or it does not exist xD