---
# System prepended metadata

title: Homework 01
tags: [homework]

---

---
tags: homework
---

# Homework 01

###### tags: `Recursion`

### Week 01

* Release: 12:10 PM, 2020.03.09, Tue.
* Due: <b>12:10 PM</b>, <font color="blue"><b>2020.03.16</b></font>, Tue.
* Extend: 12:10 PM, 2020.04.06, Tue.
> Your score would be <font color="red"><b>decreased</b></font> 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** <font color=blue>sequence</font> of characters.
* `*`: Matches any <font color=blue>sequence</font> 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 <font color="red"><b>MUST</b></font> 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 <font color="red"><b>no</b></font> 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 <font color="blue"><b>state-transition</b></font> 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.
