Day 4: Secure Container
by Simon Berger
Links:
It’s days like these I truly wonder whether it’s even worth writing anything. I don’t feel like I really have anything to say today.
One thing I can talk about though, is how my approach could be improved (and why I didn’t bother). The current approach parses the input to get the start and end points and then checks every number in the closed range for correctness.
The check itself is done by iterating over each character (in the number’s base 10 string representation) and comparing it to the previous character. If it’s less, the check immediately returns false, a special “has repeating” flag is set to true if they’re equal, and if it’s bigger, it just moves on.
The same is true for the second part, but an additional “streak counter” is introduced to make sure that a character is repeated exactly two times.
This is a really poor approach (at least when it comes to performance), but before I get into why that is and how it could be improved, let me defend my honour and explain why I didn’t bother.
The reason being, that we “only” have to check at most 1’000’000 passwords (actually less, because the passwords are exactly 6 digits long).
So even though the implementation is where is the amount and is the length of the passwords, is hardly anything.
So TL;DR: Rust lets me get away with it.
Regarding how we could improve it, let’s start with a simple one. Instead of iterating over characters, we could iterate over the digits directly using the “mathematical approach” (i.e. repeating , until ). This way we avoid having to convert the number to a string before iterating over its characters.
The method described above will produce the digits in reverse order. We can work with that though, all we have to do is change the rule from “strictly non-decreasing” to “strictly non-increasing”.
But probably the biggest problem is that it will check “obviously” invalid passwords. Say we’re at the (valid) password 123499, the next password to be checked is 123500, which is invalid because it contains digits in decreasing order. The same holds true for all following passwords up to 123555. That’s over 150 easily identifiable invalid cases and the amount of “skippable” passwords increases the higher we go. To circumvent this we can design an iterator that yields all possible increasing digit sequences starting from a given password. We could already introduce the repetition rule here, but let’s keep it simple for now. In a second step we then filter out all invalid sequences based on the repeating digit rules (which depend on whether you want to solve the first or second part). Now all that’s left is to count the amount of items in the resulting iterator.
I was curious so I calculated how many invalid password this approach skips and it turns out it’s over 99% for 6 digits! Sad thing is, I probably spent more time finding that out than solving the puzzle. But hey, such is life, isn’t it.
If you’re really curious, starting with 2 digits 45% of all numbers are skipped. 78% for 3, 92% for 4, and it just keeps on rising from there.
I could probably waste spend a lot more time coming up with various more efficient approaches, but at the end of the day it doesn’t really matter, does it?
So, before I say something awfully wrong, let me stop for the day. See you tomorrow!
Overview
Previous day Next day