Re:Anime fans stumbled upon a mathematical proof
by slazaro on Thursday March 06, 2025 @06:12PM
(#43285989)
Given that you just care about 4 digit codes (so you don't actually care about a generic algorithm that's not super slow in asymptotic time), can't you just solve it with an easy to code bruteforce algorithm? Or is the combinatorial explosion so big that it's actually intractable that way?
[ Parent
| on HN ]
Re:Anime fans stumbled upon a mathematical proof
by dumbfounder on Thursday March 06, 2025 @09:28PM
(#43286964)
Think about this. You need to calculate the number of permutation for 4 digit codes. Then you need to arrange them in every order possible to brute force. So that’s 4!!. That’s a lot: roughly 620000000000000000000000 combos.
Re:Anime fans stumbled upon a mathematical proof
by somenameforme on Thursday March 06, 2025 @10:24PM
(#43287160)
If you're not making some joke that I'm missing it's just 10^4 = 10000, which is a just a fancier way of saying 0000-9999.
Re:Anime fans stumbled upon a mathematical proof
by fc417fc802 on Friday March 07, 2025 @02:36AM
(#43287982)
10^4 permutations. Which you then permute again except the second time you're overlapping them to search for the shortest possible sequence.
Re:Anime fans stumbled upon a mathematical proof
by genewitch on Thursday March 06, 2025 @10:09PM
(#43287114)
Or it's 10000?
Re:Anime fans stumbled upon a mathematical proof
by SamBam on Friday March 07, 2025 @01:36PM
(#43292849)
That's the number of possible codes. Not the number of possible ways you could arrange all 10000 codes to see which ordering contains the most shortcuts.
Re:Anime fans stumbled upon a mathematical proof
by genewitch on Friday March 07, 2025 @05:24PM
(#43295473)
i have a python script running through that right now to find "the shortest" and it's been burning a single core for at least 6 hours. So it looks like you are right and i am wrong ;-)
i assume my pc on a single core can do ~1billion permutations per second, this will take 19,647 millennia. AFK.
what do you think the chances are, if i let this run, that it would find a shorter solution than 625 keypresses? the naive De Bruijn algorithm popped that out in like 2 seconds.