C++ Program to decompress a compressed string
-
Hello! So, I've encountered this problem, on the site I usually work on, that requires me to 'decompress' a 'compressed' string. The code I came up with gives 4 Correct Answers and 6 Wrong Answers. The problem goes like this:
Consider the pattern `n[string]`, which is equivalent to the succession `(string) ... (string)` (`(string)` repeated `n` times). Starting with this model, any string can be compressed. For example: - `1[a]` is equivalent to `a` - `2[ab]` is equivalent to `abab` - `2[a2[b]]` is equivalent to `abbabb` - `3[b2[ca]]` is equivalent to `bcacabcacabcaca` Requirement Given a compressed string of characters, display its decompression. Input data The program reads from the keyboard a correctly compressed string `S` of characters. Output data The program will display a string of characters that will represent the decompression of the string `S`. Restrictions and clarifications - `3 ≤ the length of the string S ≤ 1000` - `decompressed string length ≤ 100,000` - `the string S will contain only lowercase letters of the English alphabet` - `Time limit: 0.6 seconds` - `Memory limit: 64 MB (global) / 8 MB(local)` Example ###Input 1 `3[a1[b2[c]]]` ###Output 1 `abccabccabcc` ###Input 2 `3[a2[c]]2[x3[y]]` ###Output 2 `accaccaccxyyyxyyy`
My code: ``` include include include string input; int createNumber(int &pos) { int number = 0; while (isdigit(input[pos])) number = number * 10 + input[pos] - '0', input.erase(input.begin() + pos); return number; } string insideParanthesis(int &pos) { if (input.length()) { input.erase(input.begin() + pos); string toRepeat = ""; while (input[pos] != ']') { while (isalpha(input[pos]) && pos < input.length()) pos++, toRepeat += input[pos - 1]; if (isdigit(input[pos])) { int timesExpr = createNumber(pos); int posStart = pos; timesExpr--; string expr = insideParanthesis(pos); if (timesExpr < 0) { input.erase(input.begin() + posStart, input.begin() + pos); continue; } while (timesExpr--) input.insert(pos, expr), toRepeat += expr, pos += expr.length(); toRepeat += expr; } } input
The only advice I can give so far is that you should consider all kinds of test cases that you can think of, determine the expected result, and see if your code provides these results. The key is to think of all corner cases, such as unmatched brackets, opening brackets without a leading number, nested brackets, etc.. I'm not even sure how the first two should be dealt with - do you know?
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
antoniu200 wrote:
I did, sorry for that.
No problem, lets just move forward.
antoniu200 wrote:
As for the restrictions, the output of a string similar to
999[a999[c]]999[x999[y]]would go over the said 100,000 characters limit of the output, basically meaning that such test cases aren't given.I would be very surprised if your code is not being tested for invalid input. In fact the memory restrictions directly imply that your code is being tested for invalid input.
antoniu200 wrote:
I just tested this code on Leetcode (after I converted it to a
Class Solution) and I got it accepted,Yes, your code appears to actually work even though the architecture is unusual. I gave it some very complex input and it appeared to pass them all. However I cannot guarantee this... because I only spent a few minutes fuzzing it. Are you developing on Windows or Linux? Best Wishes, -David Delaune
I'm developing on Windows. But the code is evaluated on a Linux Ubuntu machine.
-
I'm developing on Windows. But the code is evaluated on a Linux Ubuntu machine.
antoniu200 wrote:
But the code is evaluated on a Linux Ubuntu machine.
Yes, I told you this in my first reply. The 8MB local stack size strongly infers a Linux based operating system.
antoniu200 wrote:
I'm developing on Windows.
Ok, I was asking because you can use [setrlimit](https://linux.die.net/man/2/setrlimit) on Linux to catch when your process exceeds 64MB of memory usage. You can also use it to limit your program to 0.6 seconds. On Windows you could use [SetProcessWorkingSetSizeEx](https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-setprocessworkingsetsizeex) but you would need to do alot more work... such as attaching to a job object with the [CreateJobObject function](https://docs.microsoft.com/en-us/windows/win32/procthread/job-objects). It's too much work to do this programmatically. You would be better off using [perfmon](https://blogs.msdn.microsoft.com/securitytools/2009/11/03/how-to-use-perfmon-in-windows-7/) on Windows to detect if your program will exceed 64MB memory usage. You will probably lose your mind again... but I am fairly certain that your code is failing these Restrictions and clarifications test rules. ;P Best Wishes, -David Delaune
-
antoniu200 wrote:
But the code is evaluated on a Linux Ubuntu machine.
Yes, I told you this in my first reply. The 8MB local stack size strongly infers a Linux based operating system.
antoniu200 wrote:
I'm developing on Windows.
Ok, I was asking because you can use [setrlimit](https://linux.die.net/man/2/setrlimit) on Linux to catch when your process exceeds 64MB of memory usage. You can also use it to limit your program to 0.6 seconds. On Windows you could use [SetProcessWorkingSetSizeEx](https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-setprocessworkingsetsizeex) but you would need to do alot more work... such as attaching to a job object with the [CreateJobObject function](https://docs.microsoft.com/en-us/windows/win32/procthread/job-objects). It's too much work to do this programmatically. You would be better off using [perfmon](https://blogs.msdn.microsoft.com/securitytools/2009/11/03/how-to-use-perfmon-in-windows-7/) on Windows to detect if your program will exceed 64MB memory usage. You will probably lose your mind again... but I am fairly certain that your code is failing these Restrictions and clarifications test rules. ;P Best Wishes, -David Delaune
I'm fairly sure you just don't get it. The resulting string can be as big as 100'000 characters long, as stated by the Restrictions. Now, how much memory does that use? 100'000 * 8 / 8 / 1024 = 97.6 KB. If I'm in any way seeing this wrong and Wrong Answer should be Caught Fatal Signal 11, please explain as thorough as you can, because I just don't see why would it go over the 100 KB mark, for tests that are meant not to result in a string longer than 100'000 characters.
-
I'm fairly sure you just don't get it. The resulting string can be as big as 100'000 characters long, as stated by the Restrictions. Now, how much memory does that use? 100'000 * 8 / 8 / 1024 = 97.6 KB. If I'm in any way seeing this wrong and Wrong Answer should be Caught Fatal Signal 11, please explain as thorough as you can, because I just don't see why would it go over the 100 KB mark, for tests that are meant not to result in a string longer than 100'000 characters.
Well, I can easily make your program utilize over 1GB of memory simply by passing a large input string.
antoniu200 wrote:
The resulting string can be as big as 100'000 characters long, as stated by the Restrictions. Now, how much memory does that use? 100'000 * 8 / 8 / 1024 = 97.6 KB.
I agree. In fact that's exactly how you could detect whether or not you should process the user input. As you are parsing the input I would recommend multiplying to see if the resulting string would surpass 64MB.
antoniu200 wrote:
If I'm in any way seeing this wrong and Wrong Answer should be Caught Fatal Signal 11
Ok, well maybe something is wrong with your parser. But I've tested your code against quite a few test vectors: 10[b12[ca]] 3[a]2[bc] 3[a2[c]] 2[abc]3[cd]ef 3[a3[b]1[ab]] 3[b2[ca]] Your code seems to be passing all of the tests I can throw at it. This is why I think you must be failing one of the test restrictions. Best Wishes, -David Delaune
-
Well, I can easily make your program utilize over 1GB of memory simply by passing a large input string.
antoniu200 wrote:
The resulting string can be as big as 100'000 characters long, as stated by the Restrictions. Now, how much memory does that use? 100'000 * 8 / 8 / 1024 = 97.6 KB.
I agree. In fact that's exactly how you could detect whether or not you should process the user input. As you are parsing the input I would recommend multiplying to see if the resulting string would surpass 64MB.
antoniu200 wrote:
If I'm in any way seeing this wrong and Wrong Answer should be Caught Fatal Signal 11
Ok, well maybe something is wrong with your parser. But I've tested your code against quite a few test vectors: 10[b12[ca]] 3[a]2[bc] 3[a2[c]] 2[abc]3[cd]ef 3[a3[b]1[ab]] 3[b2[ca]] Your code seems to be passing all of the tests I can throw at it. This is why I think you must be failing one of the test restrictions. Best Wishes, -David Delaune
There's a couple of things I can think of: 1) there's no end-of-line char output. The specs don't say that it should, but that might be causing a fail. 2) the program, as given, only processes one input line per run. Again, the specs as given, do not say you need to process multiple lines of input, but again, that might be the cause of fail.