|
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 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 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
|
|
|
|
|
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
|
|
|
|
|
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.
|
|
|
|
|
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)
|
|
|
|
|
Let's assume you have a 1 MByte memory, divided into 8 equal sized sectors. Then your address (or register) range occupies 1048576 addresses (or registers). Instead, you could have a state variable that occupies 1 register that selects the current sector. Then you only need 1 + 262144 registers to access the entire memory (of course, it's more inefficient because every once in a while you need an extra write in order to switch sector). My question is, does this technique have a conventional name?
|
|
|
|
|
Memory management, often specifically called bank switching: Memory management unit - Wikipedia[^]
I used to use it in a Z80 clone called the HD64180 which included a MMU to expand the 16 bit address space of the Z80 processor (i.e 64Kbyte) to 1Meg by dividing the processor address space into three banks and assigning them to different areas in the 1MB space. So your ROM was in Bank0, say, and that where the core software was (interrupts, threading, bank control, important stuff you needed all the time), Bank1 was your "user code", and Bank2 was your RAM - and you swapped the banks in and out as needed. Took a bit of work to get it straight in your head (it wasn't the most obvious implementation or an MMU) but it worked pretty well in practice as long as you paid attention.
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Yup, The C=ommodore Plus 4 and C=16/116 also used Bank switching to get the full 16 bit address space accessible for BASIC while keeping the OS in the ROM(s). I've heard the C=64 already had the same technology in hardware, but Basic 2 didn't support it. Therefore only the memory area unused for the OS was available for BASIC programs.
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)
|
|
|
|
|
Memory paging most often used in Virtual Memory systems.
In vino veritas
|
|
|
|
|
What if I was to turn that sector selector into a uint32_t so that I can move the "window" freely (even across sector boundaries), does this have a different name? The reason I ask is that I want to name my registers appropriately. Today they are named SLIDING_WINDOW_BUFFER_position, SLIDING_WINDOW_BUFFER_start and SLIDING_WINDOW_BUFFER_endExcl but I have a feeling this is called something else.
|
|
|
|
|
This is starting to sound like the ancient x86 segmented memory. 20 bit addresses (1MB) were made up of a 16 bit segment (shifted left 4) added to a 16 bit offset. The 8086 for example had 4 segment registers IIRC, CS (code), DS (data), SS (stack) and ES (extra).
Cheers,
Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
From what I can work out you are still building a Virtual Memory system what you are calling the sector selector is the page index and the memory window size itself is the page size.
Memory segmentation - Wikipedia[^]
Quote: Segmentation with paging
Instead of an actual memory location the segment information includes the address of a page table for the segment.
If that is the case you are building a page table for a Virtual Memory Implementation
Page table - Wikipedia[^]
The Virtual space can be bigger, 1:1 or smaller than the real memory space.
Even on Flash Memory we still call them pages and a group of pages become a block.
That also holds for the old superVGA (VESA) standard where you have blocks being made up of pages of a set granularity
Although in both those cases we do call the selector a "bank selector" or a "block selector" as opposed to a "page index"
Sliding Window tends to be used as a term on transmission protocols
Realistically we understand what you are doing and it's only a name.
In vino veritas
modified 13-Aug-19 12:02pm.
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
