3 ms·
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 sol
by slazaro 2y ago
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?
- dumbfounder 2y agoThink 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.
- genewitch 2y agoOr it's 10000?
- SamBam 2y agoThat'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.
- genewitch 2y agoi 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.
- somenameforme 2y agoIf 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.
- fc417fc802 2y ago10^4 permutations. Which you then permute again except the second time you're overlapping them to search for the shortest possible sequence.