.. (לתיקייה המכילה) | ||
Did you update the homework after it was published ? | |
Yes (Last update was on 6.6.2017) - update: - Corrected example for nextString. - Clarified regarding Sent. - Capital letters at the beginning of labels in isStart and nextString. - Clarified that sentInDic receives the length of the dictionary (referred to as dictLen) in stack |
The code runs very slow on the test cases. Is this ok? | |
The code can take a long time to run. If your code completes the provided test case in under a minute then that is fine. You may be generating strings and for each one checking if it is both a valid X-mistake prefix and a valid sentence. Be advised that in most implementations checking if the current string is a valid sentence can take much less time than checking if it is a valid X-mistake prefix (when considering test cases similar to the one which we provided). Therefore, you should first check if the current string is a valid sentence and only if it is you should proceed to check if it is a valid X-mistake prefix (this can greatly reduce the time your code runs in). Additionally, it is VERY important that once you find the first string of a certain length which matches all the criteria, then you need to stop testing strings of that length. For example, if you tried different strings of length 4 and you found the first lexicographical string which matches all the criteria, then you need to instantly start checking strings of length 5 and not 4 (otherwise in certain tests your code may run a very long time). |
Can you further describe how to know which string needs to come next in the sub-routine nextString? For example, which string needs to come after "AB*space*"? | |
We will analyze the case of "AB*space*" under the conditions that our alphabet is A,B,...,I and the delimiter is a *space*. To get an intuition of which string needs to come after the current string, start by numbering the letters: A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8. Since we defined the delimiter to be consecutive to the last letter in the alphabet, we will mark: *space* = 9. Translate the original string into a number according to the numbering above: "AB*space*" = 019. To find which string follows "AB*space*", increment your number and translate it back to a string: 019 ---> 020 = "ACA". Therefore, "ACA" is the consecutive string of "AB*space*". Ultimately, upon reaching the string "*space**space**space*", the consecutive string will be "AAA" (999 becomes 000). Note that we specifically chose the alphabet A-I so that the incrementation will be in base 10. |
Does a sentence have to contain the delimiter to be considered valid? | |
No. If it does not contain the delimiter then it simply is a 1 word sentence and you should check if that word appears in the dictionary. |
Can you explain the order in which parameters are passed in isStart? | |
The parameters are passed *inline* with length being in the lower address. For example, if we placed a call (jsr) to isStart at address 1000, then the memory would look like this: 1000: opcode of (jsr r5, isStart) 1002: additional word for passing isStart via addressing mode 6-7 1004: length (value, for example: 5) 1006: str (address, for example: 2000) |
How does isStart return its output? | |
The subroutine isStart returns its output through the stack. Therefore, the caller to the subroutine must allocate a word on the stack before calling isStart and that is where the output needs to be written. |
How can we split the sentence into words given a certain delimiter? | |
To ensure that there is only a single way to split a given sentence into words when given a certain delimiter, we define that in addition to having words separated by the delimiter, there can be *no* instances of the delimiter in a word in the division of the sentence. For example, given the sentence: "AB*space**space*C" then the following division into a sentence is ILLEGAL: word1="AB*space*", word2="C" but the following is legal: word1="AB", word2="C". |