C++ Program to decompress a compressed string
-
That's not what I was expecting. I wanted to see if you guys see anything wrong with the code. I was expecting you to read the code and tell me if there's anything wrong with it. Nothing else.
-
I read that. If you don't like my post, ask a mod to remove it.
-
I read that. If you don't like my post, ask a mod to remove it.
I am trying to explain that we cannot help you if you do not provide the details of your problem. You said that some of the answers produced by your program are wrong: so you need to tell us what data was input to the program, what results were produced, and why that is wrong. As I said before you cannot expect us to guess what your problem is.
-
I am trying to explain that we cannot help you if you do not provide the details of your problem. You said that some of the answers produced by your program are wrong: so you need to tell us what data was input to the program, what results were produced, and why that is wrong. As I said before you cannot expect us to guess what your problem is.
I don't have access to the test cases that fail. I'm sorry, but if you can't help otherwise, I'm going to have to let this one go.
-
I don't have access to the test cases that fail. I'm sorry, but if you can't help otherwise, I'm going to have to let this one go.
-
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
How do you handle 'a1[b2[c]]d' ? Do you get 'abccd' or 'bccd' or 'bcc' ? The compression scheme is essentially recursive, it is a bad idea to handle it with 2 pieces of code.
Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein
-
How do you handle 'a1[b2[c]]d' ? Do you get 'abccd' or 'bccd' or 'bcc' ? The compression scheme is essentially recursive, it is a bad idea to handle it with 2 pieces of code.
Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein
The program returns 'abccd'.
-
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
Hi, I can make the following inference by reading this rule of your challenge.
antoniu200 wrote:
Memory limit: 64 MB (global) / 8 MB(local)
In Microsoft Windows the default stack size is 1MB but on the Linux operating system the default stack size is 8MB so I can infer that your challenge will most likely be tested on a Linux box and will be tested for [stack overflow](https://en.wikipedia.org/wiki/Stack\_overflow). Looks like your code will fail the 64MB memory condition first. You should be able to easily test this by simply fuzzing the program input: 999[a999[c]]999[x999[y]] On a second glance I don't see where you are validating the input string to follow this rule:
antoniu200 wrote:
the string S will contain only lowercase letters of the English alphabet
Looks like you need to validate that your input is alphanumeric. Actually... now that I've read your code a third time I believe you will fail each and every rule in the Restrictions and clarifications section on very large inputs. Best Wishes, -David Delaune
-
Hi, I can make the following inference by reading this rule of your challenge.
antoniu200 wrote:
Memory limit: 64 MB (global) / 8 MB(local)
In Microsoft Windows the default stack size is 1MB but on the Linux operating system the default stack size is 8MB so I can infer that your challenge will most likely be tested on a Linux box and will be tested for [stack overflow](https://en.wikipedia.org/wiki/Stack\_overflow). Looks like your code will fail the 64MB memory condition first. You should be able to easily test this by simply fuzzing the program input: 999[a999[c]]999[x999[y]] On a second glance I don't see where you are validating the input string to follow this rule:
antoniu200 wrote:
the string S will contain only lowercase letters of the English alphabet
Looks like you need to validate that your input is alphanumeric. Actually... now that I've read your code a third time I believe you will fail each and every rule in the Restrictions and clarifications section on very large inputs. Best Wishes, -David Delaune
Looks like you didn't really understand the Restrictions. - (3 ≤ the length of the string S ≤ 1000) is for the input string, meaning no input string will have a length greater than 1000 characters; - decompressed string length ≤ 100,000 means the given input string will not convert into something longer than 100,000 characters; - the string S will contain only lowercase letters of the English alphabet means the given string will not contain any character other than alphanumeric characters. Also, care at this line: The program reads from the keyboard a correctly compressed string S of characters, which basically implies that the given string is correct.
-
Looks like you didn't really understand the Restrictions. - (3 ≤ the length of the string S ≤ 1000) is for the input string, meaning no input string will have a length greater than 1000 characters; - decompressed string length ≤ 100,000 means the given input string will not convert into something longer than 100,000 characters; - the string S will contain only lowercase letters of the English alphabet means the given string will not contain any character other than alphanumeric characters. Also, care at this line: The program reads from the keyboard a correctly compressed string S of characters, which basically implies that the given string is correct.
Ok, 1.) If you were my student I would fail you for not validating your input. 2.) If I were interviewing you for a job I would reject you for not validating your input. Once again your code will fail each and every line in the Restrictions and clarifications section. Good Luck figuring out why you are failing your tests, -David Delaune
-
Ok, 1.) If you were my student I would fail you for not validating your input. 2.) If I were interviewing you for a job I would reject you for not validating your input. Once again your code will fail each and every line in the Restrictions and clarifications section. Good Luck figuring out why you are failing your tests, -David Delaune
I like how people here show others they make mistakes, which is completely acceptable, but the people pointing can't put up with others showing them their mistakes. If you'd be interviewing me, I'd have a ton more other problems done by now and be older by at least 7 years than what I currently am, which as you can probably tell now, I'm not. This isn't an interview prep what I'm doing, it's just simple learning. But how lucky that most people need a push to learn and then consider that everyone else needs a push to learn. If you'd be my teacher, I'd probably be in faculty or University, which I'm 3-4 years away from. So, maybe try and relax. If you have anything that would teach me something useful regarding my question, go ahead and say it. Otherwise, if you don't like me or my question, just don't bother to reply and get me and others angry and frustrated just because you are. If you were my teacher, by me telling you this, I'd get an E right now, am I right? Because I didn't obey orders. I'm not here to be told what to do, I was here to learn. Not anymore. Thanks for teaching me that this forum sucks for learning. If you want to be a good teacher, maybe keep an open mind.
-
I like how people here show others they make mistakes, which is completely acceptable, but the people pointing can't put up with others showing them their mistakes. If you'd be interviewing me, I'd have a ton more other problems done by now and be older by at least 7 years than what I currently am, which as you can probably tell now, I'm not. This isn't an interview prep what I'm doing, it's just simple learning. But how lucky that most people need a push to learn and then consider that everyone else needs a push to learn. If you'd be my teacher, I'd probably be in faculty or University, which I'm 3-4 years away from. So, maybe try and relax. If you have anything that would teach me something useful regarding my question, go ahead and say it. Otherwise, if you don't like me or my question, just don't bother to reply and get me and others angry and frustrated just because you are. If you were my teacher, by me telling you this, I'd get an E right now, am I right? Because I didn't obey orders. I'm not here to be told what to do, I was here to learn. Not anymore. Thanks for teaching me that this forum sucks for learning. If you want to be a good teacher, maybe keep an open mind.
Hi, It appears that you are having some sort of mental breakdown. Just relax and take a fresh look at the challenge. :)
antoniu200 wrote:
Time limit: 0.6 secondsMemory limit: 64 MB (global) / 8 MB(local)
I compiled your code on an ARM based Linux box and restricted the process to 64MB. I verified that your code will exceed 64MB of memory... in fact I was able to get it to consume over 1GB by passing very large input strings. Your code will also consume greater than 600 milliseconds on very large input. I tested both of these conditions. You can avoid all of these failures simply by validating the input string. Best Wishes, -David Delaune
-
Hi, It appears that you are having some sort of mental breakdown. Just relax and take a fresh look at the challenge. :)
antoniu200 wrote:
Time limit: 0.6 secondsMemory limit: 64 MB (global) / 8 MB(local)
I compiled your code on an ARM based Linux box and restricted the process to 64MB. I verified that your code will exceed 64MB of memory... in fact I was able to get it to consume over 1GB by passing very large input strings. Your code will also consume greater than 600 milliseconds on very large input. I tested both of these conditions. You can avoid all of these failures simply by validating the input string. Best Wishes, -David Delaune
I did, sorry for that. However, what you told me is not a good way of convincing people you know more. All you did, in my view, is show me that you can dictate people what to do. 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. Also, the Judge gives my sourceWrond Answer, notTLE,Memory LEorRuntime Error. I just tested this code on Leetcode (after I converted it to aClass Solution) and I got it accepted, so there might be some issue with the Online Judge over at PbInfo, where I discovered this requirement and tested my code. -
I did, sorry for that. However, what you told me is not a good way of convincing people you know more. All you did, in my view, is show me that you can dictate people what to do. 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. Also, the Judge gives my sourceWrond Answer, notTLE,Memory LEorRuntime Error. I just tested this code on Leetcode (after I converted it to aClass Solution) and I got it accepted, so there might be some issue with the Online Judge over at PbInfo, where I discovered this requirement and tested my code.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
-
That's not what I was expecting. I wanted to see if you guys see anything wrong with the code. I was expecting you to read the code and tell me if there's anything wrong with it. Nothing else.
antoniu200 wrote:
I was expecting you to read the code and tell me if there's anything wrong with it.
Does it compile with no errors? If so, then there is nothing wrong with it. Short of that, only you can determine if it produces the correct result.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
-
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