Homework 01 - HackMD

--- tags: homework --- # Homework 01 ###### tags: `Recursion` ### Week 01 * Release: 12:10 PM, 2020.03.09, Tue. * Due: 12:10 PM, 2020.03.16, Tue. * Extend: 12:10 PM, 2020.04.06, Tue. > Your score would be decreased by 20% every week. --- ## TA information > Contact with TAs if having any problems. * 莊博傑 Po-Chieh Chuang / 40747019s@gapps.ntnu.edu.tw * 林育辰 Yu-Chen Lin / 40771131h@gapps.ntnu.edu.tw --- ## Fibonacci String (35%) > [name=Bogay] ### Description Do you know [Fibonacci number](https://en.wikipedia.org/wiki/Fibonacci_number)? which commonly denoted $F_n$, and its value is defined as $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0, F_1 = 1$. Today, in this problem. We are discussing a similar sequence, called Fibonacci string. Given 2 string $s_0, s_1$，we can create $s_n$ by concatenating $s_{n-1}$ and $s_{n-2}$ $\forall n \ge 2$. ### Input first line contains a positive integer $n$, and the second line contains $s_0, s_1$, sperated by a space. #### Limits - $N \le 10$ - $\|s_0\|, \|s_1\| \le 10$ - $s_0, s_1$ only contains numbers and letters. ### Output print $s_n$ in a line. #### Subtasks | | Limits | Score | |:--------- |:---------------------- | -----:| | #0 | $\|s_0\|, \|s_1\| = 1$ | $70$ | | #1 | no other limits | $30$ | | **Total** | | $100$ | ### Sample Input 0 ``` 0 peko peko ``` ### Sample Output 0 ``` peko ``` ### Sample Input 1 ``` 2 shaaa aaark ``` ### Sample Output 1 ``` aaarkshaaa ``` ### Hint ### Problem-solving Ideas Implement a function `fib_str(i)` (the name is not so important, you can call it whatever you like) to print the i-th fibbonacci string. And what you should do inside the function is to print (i-1)-th one and (i-2)-th string. --- ## Hello Regex and Glob (HRG) (35%) > [name=Yu-Chen Lin] ### Description Undoubtedly, Prof. Wang is good at teaching, so you are here, passed Computer Programming I, at level II, right? Your TA, Yu-Chen Lin (abbr. = Y.C. Lin) is researching regex and glob recently. Now, Y.C. Lin develops a new string matching rule, so-called **Hello Regex and Glob** (abbr. = HRG), I will introduce HRG below. Certainly, you know C standard string library supports some string matching functions, like **strcmp**, **strtok**, etc. However, sometimes we want a string matching function to use **patterns** instead of exact words. Then HRG combines the advantages of regex and glob symbol. This is why I want to develop HRG. (:P) In HRG, you must learn **three** symbols: * `?`: Matches any **single** character. * `+`: Matches any **non-empty** sequence of characters. * `*`: Matches any sequence of characters. For example, given a pattern `app?e`: * **apcs** doesn't match the pattern. * **applepen** doesn't match the pattern. * **apple** matches the pattern. * **appe** does **not** match the pattern. For example, given a pattern `app*e`: * **appcse** does match the pattern. * **applepenapple** does match the pattern. * **apple** matches the pattern. * **appe** does **match** the pattern. Finally, use `+` instead of `*` in **app*e** (that is `app+e`), which would pass all examples **except** the last (`appe`). Now, given an input string in the first line, and an integer $1 \leq t \leq 15$ in the second line, which represents how many patterns strings following. You should print the pattern string that matches in separate lines sequentially. Note that it is possible for an input string to: 1. match non of the pattern. 2. match more than 1 pattern. 3. contain more than 1 different symbol. For example, `app*+`, or `a*p?kk+`, `a***p??kk+?*`. ### Input * Line $1$: input string. * Line $2$: integer $t$. * Line $3\text{~}(1+t)$: pattern string each line. #### Limits For your convenience, there are some limits: 1. all test strings are composed of English **lowercase** alphabets and `*` `+` `?` symbols only. 2. string is less than $64$ bytes. 3. $1 \leq t \leq 15$. 4. **no** empty string. ### Output As the pattern matches the input string, print the pattern string. Therefore, only $t$ lines of strings would be printed **at most**. Undoubtedly, the output MUST end with a **newline** character. #### Subtasks | | Limits | Score | | --------- |:--------------- | -----:| | #1 |Pattern string doesn't contain any symbol, and $t \leq 5$. | $25$ | | #2 |Pattern string contains `?` symbol only, and $t \leq 5$. | $35$ | | #3 |Pattern string contains **one** symbol only, and $t \geq 5$. | $20$ | | #4 | Following the "limits" block conditions only.| $20$| | **Total** | | $100$ | ### Sample Input 0 ``` apple 9 apple a*e a***e appl+e appl*e ????? ?????e ?+?*?e a?p?e* ``` ### Sample Output 0 ``` apple a*e a***e appl*e ????? ?+?*?e a?p?e* ``` ### Sample Input 1 ``` hellotandteacher 13 h*r h+r he+t*h?? hello*he****+ hello*he*?**+ hello*ta* hello*teacher* hello*atm * + *? ?+ ++ ``` ### Sample Output 1 ``` h*r h+r he+t*h?? hello*he****+ hello*ta* hello*teacher* * + *? ?+ ++ ``` ### Sample Input 2 ``` nobodyloveme 2 everybodyloveme *hateme ``` ### Sample Output 2 > There is no output. ``` ``` ### Hint * The problem refers to the [Homework 1](https://drive.google.com/file/d/1fOsejqaCJ9WXTNGocXR6ev0Qhnefgwc6/view) of Prof. Chi in the Computer Programming II course. Yeah, Prof. Chi and Wang is our Computer Programming teacher in NTNU CSIE, they are both good at teaching, therefore, if you interest also can refer to the Prof. Chi course [website](https://sites.google.com/gapps.ntnu.edu.tw/neokent/teaching/2021spring-computer-programming-ii?authuser=0). * You can use some tricks like **recursion** to simulate a state-transition to match the pattern. * [Finite-state machine](https://en.wikipedia.org/wiki/Finite-state_machine) Wikipedia ### Problem-solving Ideas > [name=Yu-Chen Lin] * You should prepare a function with four-parameter, which is `input_string`, `pattern`, `index_to_input_string`, `index_to_pattern`. Then recursion the function **base on the last two-parameters**. * There are some situation for `*`: 1. Empty character 2. Any character sequence 3. It can be treated as `?` > It's important to recursion for the situation above by the two indexes **represent the current position**. * Why the `TLE` I receive? 1. `**` can be simplify to `*` 2. `+*` equal to `?*` 3. You should attend to the **priority order** for each condition. * Believe those ideas **enough** to help you to solve this problem, right? --- ## Letter Segments Reversion (30%) > [name=Bogay] ### Description Given a string $S$ only contains letters and digits, if we split it by digits, then we can observer some letter segments in it. For example, if $S$ is `"AbcE12qerP"`, we can find there are 2 letter segments, `"AbcE"` and `"qerP"`. We can reverse any number of letter segments to create a new string, in above example, `"EcbA12qerP"` is a possible result. Write a program to all possible strings we can create from $S$ in lexicographic order. Note that $S$ is also a possible result. ### Input String $S$. #### Limits - $\|S\| < 30$ - number of letter segments < $10$. - $S$ only contains letters and digits. ### Output Every possible string we can create from $S$ in lexicographic order line-by-line. #### Subtasks | | Limits | Score | | --------- |:--------------- | -----:| | #0 | only 1 segment | $70$ | | #1 | no other limits | $30$ | | **Total** | | $100$ | ### Sample Input 0 ``` oAO ``` ### Sample Output 0 ``` OAo oAO ``` ### Sample Input 1 ``` miko35miko35 ``` ### Sample Output 1 ``` miko35miko35 miko35okim35 okim35miko35 okim35okim35 ``` ### Sample Input 2 ``` AAAAA ``` ### Sample Output 2 ``` AAAAA ``` ### Hint - All uppercase letter is less than lowercase letter. e.g., `'A'` < `'B'` < `'a'` < `'b'`. ### Problem-solving Ideas 1. Build segments of digits and letters. Beware of that you know which of the original one and reversed one is larger. 3. Implement a function to recursively print segments. For each segment, if it is digit segement, you can directly print it, else decide which one should print, original one or reversed one? Print larger one, process next segment, print less one, process next segment, until reach the end.