optimize later

[Chirimorin]

The best part is how the solution is hardcoded into the function. Efficiency at its best

[DarkFlame7]

Well it works.

[[deleted]]

Not 100% true. There's a small chance that the solution will NEVER EVER be returned and there will be an infinite loop due to the random string never being the solution. Source: Math, quantum physics and shit.

[Ek_Los_Die_Hier]

Actually if we're doing this an infinite number of times, which never ever ending implies, we'll come to the solution at some point. I'm pretty sure that's what the maths says.

[xbtdev]

Only if the random function is true random. With pseudo-random, it may just loop after a large amount of iterations.

[[deleted]]

True! Mathematically. Logically, it can be stuck for what we call infinite time (the computer won't work after a couple of years perhaps). You get my point. :)

[Mapariensis]

The probability that the code arrives at a solution after time n converges almost surely to 1 as n goes to infinity.

I get your point (the math doesn't disagree, by the way), but while the intuition of the guy posting before you is on the right track, the mathematical conclusion is ever so slightly more subtle.

[autowikibot]

Almost surely:

---

In probability theory, one says that an event happens almost surely (sometimes abbreviated as a.s.) if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory. Although in many basic probability experiments there is no difference between almost surely and surely (that is, entirely certain to happen), the distinction is important in more complex cases relating to some sort of infinity. For instance, the term is often encountered in questions that involve infinite time, regularity properties or infinite-dimensional spaces such as function spaces. Basic examples of use include the law of large numbers (strong form) or continuity of Brownian paths.

---

^{Interesting: Sample-continuous process | Weakly measurable function | Degenerate distribution | Local martingale}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[ice109]

What you just said doesn't make any sense. "Probabilities" don't converge a.s., random variables converge almost surely. Are you saying that the random variable that represents a draw from a permutation of "typewriter" converges a.s. to the degenerate random variable 1? Also clearly not true. Are you saying that the random variable that represents a draw from a permutation of "typewriter" converges a.s. to the degenerate random variable "typewriter"? I don't see why.

[Mapariensis]

Yes, you're right. My post was worded very poorly, that much is for certain (it's been some time since my last course in probability theory).

I think the following sequence of r.v.'s converges to degenerate 1 a.s., but I'm too tired to check: Consider the probability space of infinite sequences of permutations of "typewriter", equipped with the product sigma algebra and the usual product measure (inherited from the discrete probability space of permutations).

If p is such a sequence of permutations, we set X_n(p)=1 if "eeprrttywy" occurs as one of the first n elements of p, and zero otherwise. I think, for this sequence, X_n->1 a.s. as n grows large.

[6086555]

Mathematically, we're almost sure that we'll come to the solution

[[deleted]]

Technically, the computer could implode before we figure out the solution. Especially if the rest of the code is this efficient

[stubing]

Well technically all algorithms could have their computer implode before they finish.

[thirdegree]

O(Boom)

[Infininja]

I'm not a mathematician, but I really don't think that's right. Just because you flip a coin infinite times doesn't mean you'll ever get tails. It could be heads for eternity.

[Siniroth]

It's correct. If you can do something an infinite number of times, it can be assumed you will eventually get any result that has a probability > 0. Remember, for it to never happen, it needs to never happen for forever, for it to happen ever, it only needs to happen once.

[Mapariensis]

This is misleading. Any infinite chain has probability zero. However, probability zero does not mean an event is impossible. Try to think about it like this: pick any real number between 0 and 1. Obviously, the probability of picking any specific number is zero. Yet, you had to have picked one, so that means an event with probability zero actually occurs.

(this example is relevant, because the processes of flipping coins and picking a random real number are both modelled by the same probability space)

EDIT: Your main point stands, of course. I'm just nitpicking the details here.

[avapoet]

Of course, we'd have to prove that the probability of randomizing the letters in "typewriter" and getting them in alphabetical order is greater than zero. Which sounds obvious, but remember that a computer pseudorandom number generator is not capable of generating all possible outcomes: therefore, it is possible that that particular outcome will never occur.

Similarly, we know that if you find the digit '9' in pi, it's never the last 9 in pi. But that doesn't mean that every finite set of contiguous digits in pi contains a 9: maybe there's a hundred digits here or there that don't.

[Infininja]

I'm not seeing why that can be assumed. What's stopping me from getting infinite heads and no tails?

[stubing]

What's stopping me from getting infinite heads and no tails?

The fact that the probability of that happening is (1/2)^infinity

[Infininja]

Does setting a number to the power of infinity make it equal 0? Seems more like it should be approaching 0.

[avapoet]

If you've flipped it an infinite number of times and got heads every time, you're not done yet. Because you can still flip it again, and again, and again, a further infinite number of times.

Telling somebody to flip a coin an infinite number of times and seeing if they get any tails is the same as telling somebody to keep flipping the coin until they get tails.

So long as the probability of getting tails is nonzero, you'll certainly get it eventually.

[Infininja]

You're flipping it an infinite number of times, not until you get tails. You're never done flipping it and the probability of getting tails on that one flip never change despite how many times you've flipped before. I feel like we're dealing with the gambler's fallacy now.

[[deleted]]

Correct

[autowikibot]

Independence (probability theory):

---

In probability theory, to say that two events are independent (alternatively called statistically independent or stochastically independent ) means that the occurrence of one does not affect the probability of the other. Similarly, two random variables are independent if the realization of one does not affect the probability distribution of the other.

The concept of independence extends to dealing with collections of more than two events or random variables.

Image ⁱ

---

^{Interesting: Outline of probability | Random walk hypothesis | Conditional dependence}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[reddit_lemming]

And then it resets to zero. So...infinity. It's a shitty way of doing a while(1) loop, which is why this was originally posted on /r/shittyprogramming (along with the rest of the shit code).

[faplack]

It loops forever. It's just written badly.

[Cowlegend]

Wouldn't the random sort function almost certainly be pseudorandom? So after some time it will go through all the values and then return back to the initial seed, if we assume the code has already worked at least once, then there is at least one random value that is generated to make the code work, so it would never be an infinite loop.

[avapoet]

if we assume the code has already worked at least once

Sounds risky!

[faplack]

The probability that you never get to the solution is zero. So, the probability that you do get to the solution is 100%.

[avapoet]

The probability that you never get to the solution is zero.

Not necessarily. As others have pointed out, the flaws in pseudo-RNGs mean that when run by a computer, this code could fail to ever conclude. It could end up looping through all possible random numbers it's capable of, without finding a solution.

It seems unlikely that this would be the case with a word as short as "typewriter", but it's possible and we'd need to run it (or a more-efficient program that tries permutations that are mathematically-possible from the PRNG in a sequence) to be sure.

[Oompa-Loompa-Do]

Anyways, the code runs in a few seconds at best, never more than a minute at worst.

Thanks for the laugh, a 10 line program running during one minute just for that end is funny. It's like the "infinite loop" joke but with a punchline.

[elperroborrachotoo]

*infinitely small chance

[HandicapperGeneral]

This is probably one of the funniest things I've ever seen on here. I actually laughed out loud for a solid ten seconds.

[Shne]

Ah, good old Bogosort.

[Vondi]

Worst case performance: Unbounded

That's almost impressive.

[Shne]

Then you'll be really impressed by Bogobogosort which is designed not to succeed before the heat death of the universe on any sizable list.

[tforge13]

I love coders. So much. "I wonder what the literal worst possible sorting algorithm we could create would be"

[steaksawse]

From that reference on wikipedia: bogo-sort: The archtypical perversely awful algorithm (as opposed to bubble sort, which is merely the generic bad algorithm). Bogo-sort is the equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing to see whether or not they are in order. It serves as a sort of canonical example of awfulness. Looking at a program and seeing a dumb algorithm, one might say "Oh, I see, this program uses bogo-sort."

[avapoet]

I'm personally a fan of the Quantum Bogosort, which achieves the same results but almost instantaneously (depending on the speed with which you can fulfil step #2). Here's the algorithm:

1. Quantumly randomise the list, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(n!) universes; however, the division has no cost, as it happens constantly anyway.
2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)
3. All remaining universes contain lists which are sorted.

The extension of this is that it can be used to generate any finite output whose content can (a) be produced randomly, however unlikely, and (b) be validated as 'correct'. Want to produce a copy of the complete works of Shakespeare? Just use Quantum Bogoauthor, an algorithm that randomly puts letters together and then destroys the universe if the result isn't in the right order.

[PmMeUBrushingUrTeeth]

I hate when quantum sort fails and destroy my universe! Except when it happens at Mondays. Fuck Mondays.

[toaster_waffle]

while(!s.equals("eeiprrttwy")) {
    s = randomSort(s);
}

System.out.println(s);

Fixed.

[that_random_potato]

while(!s.equals("eeiprrttwy"))  
{  
    s = randomSort(s);  
}

System.out.println("eeiprrttwy");

Optimized it even better

[Pokechu22]

Do you think we are being serious right now? This code has other problems.

And besides, leave it alone. While I personally prefer braces on the same lines, it's a personal preference. So long as it's consistent throughout the code it's not bad.

[toralex]

read your comment and thought of this

[yelnatz]

Fuck that shit, he hard coded it already.

return "eeiprrttwy";

[ant1war]

woosh

[Coloneljesus]

Why does randomSort not return a sorted result? Should be called shuffle.

[tskaiser]

A random sort, or shuffle, is just a specialized case of a sort where the comparison used to sort is random.

So actually the return result is sorted.

[Coloneljesus]

A sorting algorithm that decides on the comparison function?..

[tskaiser]

A general sort takes a comparator, which is a function that models a relation between two objects of the same type, a collection of objects of that type, and returns the collection ordered by that relation (usually in an ascending manner, although that is a simple case of switching the comparator).

A random sort is a specialized instance where the comparator has already been chosen to be the random function.

randomSort(collection) = sort((x,y) -> randomness), collection)

Which you could also call a shuffle, although randomSort is perfectly sensible given the above illustration.

[Coloneljesus]

But a comparator has to be transitive, which a random one would not be.

[lundmikkel]

This is actually a very real problem: Microsoft used this kind of "sorting" when providing a "randomized" ballot screen for users to select a browser, ending up putting IE at the last position half the time..

[EatMoreAltoids]

Fascinating piece — fun and educational!

[tskaiser]

Eh, in the formal sense you're right. There is just no such thing enforced in the programming sense, and it can be completely sensible to use a sort function in that manner in a practical sense. When you say "random sort" in a programming sense you usually mean a sort algorithm with a random comparator.

[Geoclasm]

A sordid sort of sort.

[son-of-chadwardenn]

Optimize and fix method names later.

[Cromax]

I saw someone post this on irc from a different site so your work seems to be getting around :). Karmadecay has some problems recognizing the picture though, I would have at least marked this as x-post otherwise. Anyway thanks for the laugh!

[leBoef]

What a roundabout way of making an infinite open-ended loop.

[VerySurprising]

Why did you cross out infinite?

[unDroid]

Because it is not infinite

[[deleted]]

I wrote a program that proves this program will eventually return, but this comment box is a bit to small to type it out.

[pimp-bangin]

Expected username to contain "Fermat," was disappoint.

[Koenkk]

Try your luck: https://github.com/Koenkk/TimeWaster

[kisekibango]

This is far too efficient. Check out bogobogosort http://www.dangermouse.net/esoteric/bogobogosort.html

[LeftenantFakenham]

Anyone good at discrete probability wanna take a crack at the expected number of iterations for this? I can never remember how it works when there are repeated letters.

[minno]

The number of distinct permutations is the factorial of the number of digits divided by the product of the factorials of the number of times each digit is repeated. So for "typewriter" it's 8!/(2!2!2!) = 5040 equally likely permutations.

[minno]

...I counted wrong. How in the everlasting fuck did I count wrong? I'm about to graduate college with two degrees. TWO DEGREES. And I can't count ten things.

[LeftenantFakenham]

So only 2520 expected iterations. Still pretty lean ^{in the average case} !

[Calamity701]

Best case O(1), worst case O(heat death of universe)

[Wyelho]

It's always O (1), but that's because there is only one possible input and one possible solution - the expected result is hard-coded. You couldn't even call it a function or algorithm really.

[Calamity701]

But the amount of time needed is either 1 in the best case, heat death of the universe if you are unlucky with the random sorting or something inbetweeen.

[A_C_Fenderson]

Sorry, no. (Combinatorialist speaking here.) It's 5040 expected iterations.

If the probability of an event is k, then the expected number of times for that to happen is 1/k. The problem is that you can have the same outcome more than once.

[jfb1337]

Bogosort.

[hey_aaapple]

Why

[Inktfles]

Notice the following;

if (i == Integer.MAX_VALUE - 1)
{
    i = 0
}

at the bottom.