help to optimize code of password decryption

Question

Hello All,

Below is my code:

https://code.sololearn.com/cQmkYpgs96Dz

It is not optimized, and need your view on the same. Logic and input is explained in code comment.

Thanks a lot for your input in advance...!

Answer 1

I misread, but shouldn’t it be the same? Just assign a variable to the last digit index you find, then decrement to the left each time you find a zero and replace?

Answer 2

You seems also assuming getting only valid input, and so my own attempt doesn't handle related exceptions nor dynamic memory allocation exception (few probabilities to happen as I only allocate -- and deallocate -- one char array for the result and length of a password is not supposed to be great ^^)...

On the other hand, my code (try to) handle special cases of original password containing '*' and/or '0' (in doubt) and could be reduced more or less if that wasn't a constraint ;P

When you will have done your attempt and if the challenge is really over, feel free to ask for my code: comparing other ways to your own could be often a good source of learning ;)

Answer 3

This can be done in linear time.
You don’t need to create another substring, or find 0s or anything. Just loop through each character and swap/replace/insert whenever necessary.

Answer 4

In wich context did you get time out?

Because your code run fine for me in sololearn playground context... so I guess you get time out either when SL servers have too many charge (less ressources for your code) or more probably when trying to pass a bunch of tests in the context of code challenge (not necessarly at sololearn): If so, it's cheating to request for optimizing your code ^^

Anyway, the requirement description in your code lacks of information: you didn't handle special cases such as original (decrypted) password contains '*' and/or '0' (you seems assuming it only could be composed of any letters and any digits but not zero).

One tip to optimize your code: you use a lot of substr() and string concatenation, wich is less efficient than use a char array and decrypt in quite one pass after counting digits, zeros, stars ('*'), and computing the decrypted password length...

My own attempt with lot of comments is ready, but you must try by yourself before, and swear you're not trying to cheat ;P

Answer 5

visph , you guessed it right...it's for challenge on different platform and I came to know by appearing for challenge so no option to cheat now as it's over...

Sole purpose of this post is to learn from problem statement and not cheating.

Your assumption of original pasword constrains is fine as of now..

And yes, I don't need well written code as my query response... Thanks for the pointers you gave to improve code and will surely try it own my own... Thank you so much..

Answer 6

visph yeah sure... Will post my updated code but may be tomorrow...

Answer 7

In real world, you should handle possible exceptions (this could be "real" exception thrown by the dynamic char array allocation) and check for input validity (wich could cause unexpected behavior among wich "real" exceptions thrown), at least for the less simple case of original password containing '*' and/or '0' wich I handled ;)

[ edit ]
But sure, often in code challenges that's not needed, unless it's explicitly mentionned you must handle invalid inputs ^^

Answer 8

visph
except this isn’t real world ;)
and there is no invalid input for this problem, introducing your own exceptions doesn’t make your program any more robust than it already is.

Answer 9

Bobby Fischer yes: that's why I doesn't handle exceptions in my code (as I mentionned before) ;)

I was just informing OP ^^ (and edited my last answer to mention that's often not the case in code challenges while you posting...)

Answer 10

Ketan Lalcheta wrote "wich 0 to replace with initial digits?"

You can determine that... I do it in my code (tip: count of digits must equals twice the count of zero to replace and replace digits are all at start of input ;))

Answer 11

The time measurement is not accurate as it could vary depending on server charge ^^ (you should measure time to run at least thousand of execution to get a few more accurate comparison ;))

The input 45XX000 is not valid in my point of view: the first not digit char is at index 2, so there should be only 2 zero to replace next ^^

Anyway my code is probably less efficient as yours due to handling special cases... but if you want to check it (and in particular how I handle special cases), here it is:

https://code.sololearn.com/cvaT1OYKtfT8/?ref=app

Answer 12

Ketan Lalcheta
you don’t need to reverse things if you start from the left.
also, try to do it with constant space instead of creating another string.

Answer 13

Ketan Lalcheta
No. Like I said, loop from left to right.
- Find the index of last consecutive digits.
- Assign the index to a variable z.
- Keep looping until you find the first 0, replace with s[z].
- Decrement z so it now points to the previous number.
- Keep looping again until you find another 0, replace, and repeat.

The point of having constant space is because it is ... constant. Constant means O(1). The length of your decrypted password will of course depend on your input, which means O(N). In very tight space constraint, if you have a really long password to decrypt, this would matter.
Besides, it is a good practice. If you can save space, why not.

Answer 14

Bobby Fischer okay... I got first part..

But wondering what you want me to do about space constraints...
I am creating new string... Do I need to update same string or what ?

Answer 15

Ketan Lalcheta
Exactly. You update your input as you iterate through each character.

Answer 16

Hey, I've done some (random) tests, and I discover some things:

1) the inaccuracy of time measure (try testing first your second "improved" version and then the original (earlier) one... you will be surprised ^^)

2) the focus on (micro-)optimizing code, while it seems that the boltleneck is not in efficiency but in logical: unless digits are not allowed at start of decrypted password, your original algorithm run an infinite loop if there's at least 2 digits at start of original password (ie: decrypted "15aPpLe" => encrypted "5100Pa*Lp*e"), wich I guess is what happened in your code challenge (generating random password with some have at least 2 digits at start)...
This can be solved by changing the else statement in the isdigit loop:
else
{
break; //c = s[1];
}

3) your second "improved" attempt fail for quite all random generated string ^^ (I don't have investigate to find why, as it seems that all attempts to micro-optimizations are useless).

My last code (with random generated tests and improved chrono -- but useless, as execution time difference is not so great, and probably your first attempt should have not timed out with the fix above):

https://code.sololearn.com/ceiYrtrdxp8J/#cpp

It test 5 times first the most basic of my attempts (decryptPassword_0 -- next are micro optimizations wich seems unmeasurable: often less than 1 micro second), then 5 times your original fixed attempt... Count is easily modifiable (in main function at bottom of code, variable "m") as well as functions tested (functions pointers "decrypt_1" and "decrypt_2" variables, also at start of main function ;))

Answer 17

Bobby Fischer , I thought to loop through each character but in first case only I got challenge so changed approach.

If first character while looping is digit ,then it should go to the place where first digit is available. So, we are gonna have find function and apparently doing substring ..

Am I missing something here , then plz enlighten me

Answer 18

I don’t understand your question. Shouldn’t the newest found digit be placed in the beginning?
You can just write s = s[i] + s, then assign s[i] to zero, then increment i.

Answer 19

Bobby Fischer , the logic you mentioned is to encrypt password... We have encrypted password as input. So, digit should go to the place where star is there to get the original password

Answer 20

Bobby Fischer , wow...... I regret why I don't think to start from end to loop over when I got confused... A fab way....

Code performance improved from 21 mili seconds to 5 or 4 mili seconds EVEN ON A STRING OF SIZE LEES THAN 12 CHARACTER... No find , no substring... Fabulous method.

Updated same code which I initially posted with question.

visph , not handling * and 0 as input...

* Can be predicted by checking whether earlier characters are fulfilling condition of lower and upper characters...

But 0 cannot be handled... Max you can check 0 count in string matching with digits at start of encrypted string password... But if it is not matching , then which 0 to replace with initial digits?

For example:

45XX000 may be determined as XX054 or XX504 or XX540

So, not handling input string case of * and 0