|
|
It works ! Kindly thank you all of you ! Without you I would not succedded !
modified 22-Aug-19 6:16am.
|
|
|
|
|
After referring to the SO link you helpfully provided, I finally understand what this macro is intended for.
The solution is simple: don't use this macro! It is intended for an extremely specific purpose with specific classes/structs, and it must be used with very specific arguments. If you don't know how to use it correctly, the preprocessor will generate garbagage code, and the compiler unintellegible errors!
The purpose is some low level memory address juggling which makes a whole lot of assumptions on behalf of the parameters being passed, without giving the compiler any information about what is going on. This is highly explosive stuff! Obviously you have no idea what parameters to pass and how to use it, probably not even what to use it for. Please don't do that and stop before anyone gets hurt.
The only thing that's worse than using #define macros in C++ is using other peoples #define macros without being 200% sure what it does and how it's supposed to be used. If you need to ask what it does or why it doesn't work, then just drop it. Instead, just tell us what goal you intend to achieve, so we can advise you on proper C++ ways of solving your problem.
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)
|
|
|
|
|
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 <iostream>
include <string>
include <cctype>
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.erase(input.begin() + pos);
return toRepeat;
}
return "";
}
int main() {
ios_base::sync_with_stdio(false);
getline(cin, input);
for (int i = 0; i < input.length(); i++) {
if (isdigit(input[i])) {
int timesExpr = createNumber(i);
int iStart = i;
timesExpr--;
string expr = insideParanthesis(i);
if (timesExpr < 0 && input.length()) {
input.erase(input.begin() + iStart, input.begin() + i);
continue;
}
else if (!(input.length()))
return 0;
while (timesExpr--)
input.insert(i, expr);
}
}
for (int i = 0; i < input.length(); i++) {
if (input[i] == '[' || input[i] == ']')
continue;
else
cout << input[i];
}
}
I'd like to add that I've seen sumbitted sources on C++ with the same runtime as my source, but with 10 test cases correct out of 10.
If someone has any advice that could help me get those test cases right, I'd be thankful.
modified 19-Aug-19 5:03am.
|
|
|
|
|
antoniu200 wrote: If someone has any advice You could start by explaining exactly what you mean by "wrong answers".
|
|
|
|
|
Well, I don't have any other detalis to give about that wrong answer. If I knew the input and output, I could solve the issue myself. But I don't. So, I'm stuck.
|
|
|
|
|
Sorry, but you cannot expect anyone here to guess.
|
|
|
|
|
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 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.
|
|
|
|
|
antoniu200 wrote: I don't have access to the test cases that fail. Well neither do we, since we have no idea where they come from.
|
|
|
|
|
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
|
|
|
|
|
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
modified 18-Aug-19 5:57am.
|
|
|
|
|
The program returns 'abccd'.
|
|
|
|
|
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.
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.
|
|
|
|
|
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.
|
|
|
|
|
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 seconds Memory 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 source Wrond Answer , not TLE , Memory LE or Runtime Error .
I just tested this code on Leetcode (after I converted it to a Class 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
|
|
|
|
|
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 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 but you would need to do alot more work... such as attaching to a job object with the CreateJobObject function. It's too much work to do this programmatically. You would be better off using perfmon 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.
Best Wishes,
-David Delaune
|
|
|
|
|