Inspiration
I wanted to do a small hack at Waterloo's March 2016 TerribleHack, but alas! I was a judge! I had to do something fun and small! Because I had so little time, I decided to make a program that would need ridiculously huge amounts of time to sort a three-element list.
What it does
It sorts numbers really really quickly eventually.
How I built it
I uses a recursive function that generates all permutations of the list, sorts them lexicographically, then generates all permutations of each of those lists, sorts them lexicographically, and so on, and so on, until the bottom layer is reached, which is when the first element in this very, very long list is returned. How many layers are there? n^n^n^n, where n is the number of elements.
Challenges I ran into
Getting it to be slow enough. Also sometimes my computer crashed when I ran it (whoops!).
Accomplishments that I'm proud of
Making quite possibly the slowest sorting function ever! To sort an N-element list takes about factorial(factorial(....(factorial(N))...)^2 operations, where there are N^^^4 operations. For N=2, N^^^4 is about 10^19730. I haven't done the math, but I think 10^19730 nested factorial functions gives you a pretty big number. Still finite though - this algorithm will sort a two-element list eventually!
What I learned
I learned about the limitations of C++ templates - the compiler WILL crash if you accidentally create an infinite tower of templated functions (duh), even if you're guaranteed that only a finite number of templated functions will need to be defined for any input. To be fair, it's a very _ large _ finite number, but still.
Log in or sign up for Devpost to join the conversation.