---
# System prepended metadata

title: Homework 02
tags: [homework]

---

---
tags: homework
---

# Homework 02

###### tags: `structure`

### Week 02

* Release: 12:10 PM, 2020.03.30, Tue.
* Due: <b>12:10 PM</b>, <font color="blue"><b>2020.04.07</b></font>, Tue.
* Extend: 12:10 PM, 2020.04.28, 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

---

## Dice heaven!! (20%)
> [name=Yu-Chen Lin]

### Description

You have an assignment by TA. Arrange n dice in a row, and then each dice have 1 point top, 4 points front, 2 points right (shown in the left figure below) initially, and Its development drawing is shown in the right figure below.  
<!--
給定 $n$ 個骰子排成一列，一開始都是點數 $1$ 朝上，點數 $4$ 朝前，點數 $2$ 朝右 (如下左圖所示)，另外骰子的展開圖如下右圖所示。
-->

![](https://i.imgur.com/3St4YFY.png)


---

### Total Points

A dice total points are defined as: 

<!--
其中，我們定義一個骰子之總點數計算如下：
-->

$\text{Total Points} = \underbrace{N}_{\text{Front}} \overbrace{E}^{\text{Right}} \underbrace{S}_{\text{Back}} \overbrace{W}^{\text{Left}} \underbrace{U}_{\text{Top}} \overbrace{D}^{\text{Down}}$

For example, a dice its initial status is 4 points on front, 2 points right, 3 points backward, 5 points left, 1 point top, and 6 points downward. Therefore, we calculate its total points as:
<!--
舉例來說，按題目所述之骰子初始狀態，點數 $4$ 朝前、點數 $2$ 朝右、點數 $3$ 朝後、點數 $5$ 朝左、點數 $1$ 朝上和點數 $6$ 朝下，也就是說：
-->

$$
\text{Total Points} = 423516
$$

---


Next, there are $m$ operations, and each operation contains two integer $a$ and $b$.

* $a, \ b \in \mathbb{N}$, swapping the dice position between number $a$ and $b$.
* As $b$ equal to `-1`, the dice number $a$ rotates forward.
* As $b$ equal to `-2`, the dice number $a$ rotates right.
* As $b$ equal to `-3`, sorting the dice between number $a$ to the last ascending by total points.
* As $b$ equal to `-4`, sorting the dice between the first to the number $a$ descending by total points.

Print the total points between number $0$ to $(n-1)$ after the $m$ times operations 

<!--
接下來有 $m$ 次修改操作，每個操作包含兩個整數 $a$, $b$

* 若 $a,\ b$ 都是正整數，交換編號 $a$ 與編號 $b$ 的骰子的位置。
* 若 $b$ 為 `−1`，將編號 $a$ 的骰子向前旋轉。
* 若 $b$ 為 `−2`，將編號 $a$ 的骰子向右旋轉。
* 若 $b$ 為 `-3`，將編號 $a$ 至最後一顆骰子按 $\text{Total Points}$ 由**小到大**排序。
* 若 $b$ 為 `-4`，將編號 $a$ 至第一顆按 $\text{Total Points}$ 由**大到小**排序。

在 $m$ 次操作結束之後，依序輸出編號 $1$ 到編號 $n$ 各骰子的 $\text{Total Points}$。
-->

---

TA provides a header file named **"diceheaven.h"** below.

* **diceheaven.h**
```cpp=
#pragma once

#include <stdbool.h>

//Define the dice structure
struct s_dice{
    int front;
    int right;
    int back;
    int left;
    int top;
    int down;
    int totalPoint;
};

//Optional function
void sortDice(struct s_dice dice[], int n, int from, int to, bool isAscending);
void rotateDice(struct s_dice *dice, char direction[]);
int calculate_totalPoints(struct s_dice dice);

//Main function would call this function.
void solve(struct s_dice dice[], int n, int a, int b);
```

`main.c` is a reference. We would call your function in the main, output the answer. 

---

* **main.c**

```cpp=
#include <stdio.h>
#include <stdbool.h>
#include "diceheaven.h"

int main(){
    //Read variable
    int n = 0 , m = 0;
    scanf("%d %d", &n, &m);

    //Initialize the dice array.
    struct s_dice dice[n];
    for (int i = 0 ; i < n ; i += 1){
        initDice(&dice[i]);
    }

    //Call your function to finish operation
    for (int i = 0 ; i < m ; i += 1){
        int a = 0 , b = 0;
        scanf("%d %d", &a, &b);
        solve(dice, n, a, b);
    }

    //Output answer
    for (int i = 0 ; i < n ; i += 1){
        if (i != 0){
            printf(" ");
        }
        printf("%d", dice[i].totalPoint);
    }
    printf("\n");
}

void initDice(struct s_dice *dice){
    dice->front = 4;
    dice->right = 2;
    dice->back  = 3;
    dice->left = 5;
    dice->top = 1;
    dice->down = 6;
    dice->totalPoint = 423516;
}
```

---

Therefore, you should complete a file named **"diceheaven.c"**, and must complete the **solve** function, others function is optional, could implement your own function and call in the solve function. 

Finally, you <font color="red">MUST</font> implement the file below, then submit it on NOJ.

* **diceheaven.c**
```cpp=
//You can include the header file in need
#include "diceheaven.h"

//Optional function
void sortDice(struct s_dice dice[], int n, int from, int to, bool isAscending){

}

//Optional function
void rotateDice(struct s_dice *dice, char direction[]){

}

//Optional function
int calculate_totalPoints(struct s_dice dice){

}

//Main function would call this function.
void solve(struct s_dice dice[], int n, int a, int b){

}

//DONT contain the main function...
//Or you would get "compiler error".
```

---

### Input

* The 1st line of the input contains two numbers, `n` and `m`. Two consecutive numbers separated with space. 
* The following `m` lines are the operation. Each line contains two integers $a, \ b$. 

<!--
第一行包含兩個正整數 $n, \ m$

接下來 $m$ 行每行有兩個整數，第 $i$ 行的兩個正整數表示第 $i$ 次操作。
-->

#### Limits
* $1 \leq n \leq 20, \ n \in \mathbb{N}$
* $1 \leq m \leq 100, \ m \in \mathbb{N}$
* $a \geq 0, \ a \in \mathbb{N}$
* $b \geq -4, \ b \in \mathbb{N}$

#### Subtasks

|           | Limits | Score |
| --------- |:------ | -----:|
| #0        |  $n = 1, \ -1 \leq b \leq -2$      | $35$ |
| #1        |   $b \geq -2$      | $25$ |
| #2        |   $b \geq -3$      | $20$ |
| #3        |   Following the “limits” block conditions only.      | $20$ |
| **Total** |        | $100$ |

### Output

<!--
在一行輸出 $n$ 個數字以空格分隔，第 $i$ 個數字表示編號 $i$ 的骰子最後朝上的點數。
-->

Print the `n` total points in order, and the consecutive numbers separated with space, ending with a newline character.


### Sample Input 0

```
1 2
0 -2
0 -1
```

### Sample Output 0

```
512634
```

### Sample Input 1

```
3 3
1 -1
2 -2
2 0
```

### Sample Output 1

```
413652 126534 423516
```

### Sample Input 2

```
3 4
1 -1
2 -2
2 0
0 -3
```

### Sample Output 2

```
126534 413652 423516
```

### Sample Input 3

```
3 4
1 -1
2 -2
2 0
2 -4
```

### Sample Output 3

```
423516 413652 126534
```

### Sample Input 4

```
3 4
1 -1
2 -2
0 1
1 -3
```

### Sample Output 4

```
126534 413652 423516
```


### Hint
* You <font color="red">MUST</font> implement the file **diceheaven.c** is defined above, no "main" function on it. 
* REMEMBER to calculate each dice's total points, <font color="red"><b>assign</b></font> the value to the dice. Don't deal with the output.
* The problem modified refer from APCS (Advanced Placement Computer Science)

### Problem-solving Ideas
* Draw a dice on your paper, and then simulate its rotation. 
* Focus on the value and pointer, for example, if the parameter is a Dice pointer structure, you should use `->` to access its value, and this operation can change its value. 
* Additionally, if the parameter isn't a pointer, whatever how you change this you can't change the "original" value.
* Use the bubble sort or insertion sort or each you like, then implement swapping the dice structure. And notice the interval is [0, a] and [a, n-1], you would get the "accepted" result.

---

## Old Maid (20%)

> [name=Bogay]

### Description

Bogay, your Computer Programming TA who has very few friends, wants to play old maid with others. Can you write a program to help him? At least he can play with the computer...

### Input

**Note**: in you submission code, please add `#include "card.h"`, or you will get `CE`

In this problem, I declare a struct `Card` with below definition.

```c=
struct Card
{
  int rank;
  int suit;
};
```

* `rank` is a number in $[1, 13]$
* `suit` is a number in $[1, 5]$, $1 \sim 4$ means hearts, diamonds, clubs and spades. If this card is joker, it will be $5$

You should implement 2 functions.

```c=
void init_cards(struct Card cards[53]);
void draw_card(int idx);
```

* `init_cards` tells you what cards players hold, the first player (no. 0) has `cards[0...13]`, the second one has `cards[14...26]`, and the third one has `cards[27...39]`, fourth one has `cards[40...52]`. Be aware that this function may be called not only once. Each call means a new game start, so players' hand will be reset by given argment, you can also handle other initialization you needs.
* `draw_card` means that, in this round, the `idx`-th card (starts from 0) is taken and insert to the end of the next player's hand. The first call of this function takes a card from player 0 to player 1, and the second call is from 1 to 2, and so on. But note that if any player discards all of his hand, he/she should be skipped. If you receive an invalid `idx`, ignore it.

So, this problem I provide 2 files:

`card.h`:

```c=
struct Card
{
    int rank;
    int suit;
};

void init_cards(struct Card cards[53]);
void draw_card(int idx);
```

and `main.c`:

```c=
#include <stdio.h>
#include <stdlib.h>
#include "card.h"

int main()
{
    char cmd;
    while (scanf("%c", &cmd) != EOF)
    {
        if (cmd == 'i')
        {
            struct Card cards[53];
            for (int i = 0; i < 53; i++)
                scanf("%d %d", &cards[i].suit, &cards[i].rank);
            init_cards(cards);
        }
        else if (cmd == 'd')
        {
            int idx;
            scanf("%d", &idx);
            draw_card(idx);
        }
    }

    return 0;
}
```

you should submit your implementation for `init_cards` and `draw_card`, don't include main function or `Card` definition, etc. or you may get `CE`.

#### Input Format

Each line means a function call in the below format:

```
cmd params
```

`cmd` is a character either be `i` or `d`, means `init_cards` or `draw_card`, respectively.
For command `i`, the `params` will contains 106 integers, each pair means the card suit and rank, e.g., hearts 4 will be $1\ 4$.
For command `d`, `params` will be an integer that denotes `idx`.

#### Limits

* There is always one joker in the cards.

#### Subtasks

|           | Limits                        | Score |
| --------- |:----------------------------- | ----- |
| #0        | no `draw_card` call           | $40$  |
| #1        | `init_cards` called only once | $40$  |
| #2        | no other limits               | $20$  |
| **Total** |                               | $100$ |

### Output

In any moment, if a player has matched pairs so he/she can discard them, you should print the player id and these pairs in the below format:

```
player_id card_1 card_2
```

For single round of output, you should sort them by player id, and then card rank, lastly card suit.
For example, if player 0 has cards $[(1, 1), (2, 1), (2, 13), (3, 13)]$, and player 1 has cards $[(3, 1), (4, 1), (2, 11), (1, 11)]$ (first number in parentheses means suit, second one is rank). You should print these lines.

```
0 (1, 1) (2, 1)
0 (2, 13) (3, 13)
1 (3, 1) (4, 1)
1 (1, 11) (2, 11)
```

### Sample Input 0

```
i 1 11 2 7 4 6 1 12 3 6 3 2 4 10 1 4 4 11 5 0 4 1 3 3 2 10 4 3 2 3 1 6 3 10 2 2 2 11 2 13 3 12 3 1 1 1 1 13 2 8 1 5 2 4 1 2 1 8 4 7 4 5 3 5 2 9 4 12 1 7 4 4 4 13 3 7 4 8 4 9 2 12 2 6 1 9 3 9 1 10 3 4 1 3 2 5 3 8 3 13 2 1 4 2 3 11
```

### Sample Output 0

```
0 (3, 3) (4, 3)
0 (3, 6) (4, 6)
0 (2, 10) (4, 10)
0 (1, 11) (4, 11)
1 (1, 1) (3, 1)
1 (1, 13) (2, 13)
2 (3, 5) (4, 5)
2 (1, 7) (3, 7)
2 (1, 8) (4, 8)
2 (2, 9) (4, 9)
3 (1, 9) (3, 9)
```

### Hint

### Problem-solving Ideas

In this problem, you need to maintain what cards 4 players hold, and card goes from who to whom, etc.

In each `init_cards` call, you should initilialize the state describe above. After that, check each players hand and put pairs that should discard.

In `draw_card` calls, steps are described below:

1. First you need to check where cards goes, e.g., from 0 to 1.
2. If the `idx` is invalid, update player index, and turn to next round.
3. Move player 0's `idx` card to player 1's end of hand.
4. Fill in the gaps of hand by move second half of cards backward.
5. Check player 1's pairs.

But...how to check whether there exists pairs in players' hand? Sorting may first comes to your mind, but is is a little trouble, right?

So I use another way to do this, steps are described below, indentation means a nested loop:

* Iterate rank `r` from 1 to 13.
  1. declare a array `c` to record found cards.
  2. Iterate player's cards.
      * If find a rank of card matches `r`, add it `c`.
  3. Iterate `c` to check pair, and remove matched cards.



---

## Rotating a bit string (20%)

> [name=Yu-Chen Lin & Hung-Lung Wang]

### Description
Write a function $\mathtt{rightrot}(x, n)$ that returns the value of the
integer $x$ rotated to the right by $n$ bit positions.

---

For example:
* Given $x = 23, \ n = 4$

and then
$$
23 = (10111)_2
$$

Now, the $x$ rotated to the right by $4$ bits positions:
$$
15 =(01111)_2
$$

---

Other example:
* Given $x = 279, \ n = 1$

and then
$$
279 = (100010111)_2
$$

Now, the $x$ rotated to the right by $4$ bits positions:
$$
395 =(110001011)_2
$$

---

### Input
Two integers $x$ and $n$ with $n\ge 0$ in a single line.

#### Limits
* $2^{31}-1 \geq x \geq 0, \ x \in \mathbb{N}$
* $5 \times 10^5 \geq n \geq 0, \ n \in \mathbb{N}$

#### Subtasks

|           | Limits | Score |
| --------- |:------ | -----:|
| #0        |   $n = 1$     | $25$ |
| #1        |   Guarantee the n bits from left to right is zero for x after the rotate operation, $n \leq log_{2}{x} + 1$   | $35$ |
| #2        |   $n \leq log_2{x} + 1$     | $25$ |
| #3        |   Following the “limits” block conditions only.      | $15$ |
| **Total** |        | $100$ |

### Output
Print the value `x` after the rotate operation, ending with a newline character.

### Sample Input 0

```
0 1
```


### Sample Output 0

```
0
```

### Sample Input 1

```
16 2
```


### Sample Output 1

```
4
```

### Sample Input 2

```
15 3
```


### Sample Output 2

```
15
```

### Sample Input 3

```
14 1
```


### Sample Output 3

```
7
```

### Sample Input 4

```
168 200
```


### Sample Output 4

```
168
```

### Sample Input 5

```
20210330 1210
```


### Sample Output 5

```
21843224
```

### Sample Input 6

```
20210330 500000
```


### Sample Output 6

```
20210330
```


### Problem-solving Ideas
* There are two blocks in X, one is n bits from LSB to MSB, and another is the others.
* Using the AND operation like `1111`, which can keep the original value. Maybe you could use this operation to keep the last n bits.
* Just use the right shift (>>) operation to shift n bits, and the value you keep left shifts `?` bits. Then use the OR operation on them.
* Notice the n can greater than the X bits.



---

## Inverting a segment of a bit string (20%)

> [name=Bogay & Hung-Lung Wang]

### Description

Write a function $\mathtt{invert}(x, p, n)$ that returns $x$ with the $n$ bits that begin at position $p$ inverted (i.e., $1$ change into $0$ and vice versa), leaving the others unchanged.
Note that the position starts with 0 from the most siginificant bit of $x$.

For example, with $x=10, p=0, n=1$, we can first write down $x$ in binary form.

```
1010
^
```

The mask start at 3^th^ bit, denoted by the arrow above.
From this position, we invert 1 bit, so the result is

```
0010
```

which is `2`, this is the answer.

### Input

Three integers $x$, $p$, and $n$.

#### Limits

* $0 \lt x \lt 2^{31}$
* $0 \le p, n$
* $0 \le p + n \le [\log_2x]$

#### Subtasks

|           | Limits          | Score |
| --------- |:--------------- | -----:|
| #0        | $n=0$           |  $10$ |
| #1        | $p=0$           |  $50$ |
| #2        | no other limits |  $40$ |
| **Total** |                 | $100$ |

### Output

Print the result in decimal format.

### Sample Input 0

```
10 0 1
```

### Sample Output 0

```
2
```

### Sample Input 1

```
2147483647 3 5
```

### Sample Output 1

```
1887436799
```

### Sample Input 2

```
65535 15 1
```

### Sample Output 2

```
65534
```

### Sample Input 2

```
35 3 0
```

### Sample Output 2

```
35
```

### Problem-solving Ideas
In this problem, an important part is how to flip a bit. A convenient way is to xor 1.

So, if the case is $x=10, p=0, n=1$, what you should do is calculate $(1010)_2 \oplus (1000)_2 = (0010)_2$.


---

## Find (20%)

> [name=Bogay]

### Description

[`find`](https://man7.org/linux/man-pages/man1/find.1.html) is a useful command to find files you want.
In this problem, you need to implement its `-iname` test, which accepts a pattern to match the filename (case insensitive).
For example, given a directory like this.
```
.
├── cat
├── rabbit
└── fox
    └── cat
```
If the command is `find . -iname cat`, it will match `./cat` and `./fox/cat` (dont't forget the `./` prefix).
Patterns may contain these [wildcards](https://en.wikipedia.org/wiki/Wildcard_character)

* `?` matches any **single character**
* `*` matches any **sequence** (any number of any characters, just everything).
* `[...]` matches any **single character** between `[` and `]`, e.g., `[abc]` will match a, b or c.

Its difinition is a little different from [HRG](https://noj.tw/problem/123) in last homework, be careful!

Given a struct `File` in below definition.

```c=
struct File
{
  char *name;
  int size;
  struct File **children;
}
```

* `name` is the file's base name. It will be `.` if this file is root.
* `size` means how many files under this directory. If this is a file, `size` will be 0.
* `children` is an array of directory's children's pointers with length of `size`.

You should implement a function `void cmd_find(char *pattern, struct File *root)`, which prints all matched files' full name.

Also, this is the `main.c` content, if you need. I write some function that can help you parse input like the `tree --fromfile .` behavior.

```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "file.h"

#define PATTERN_SIZE 80
#define FULL_FILENAME_SIZE 100005

// create a new file
struct File *new_file()
{
    struct File *new = calloc(1, sizeof(struct File));
    if (!new)
    {
        fputs("Allocation failed!", stderr);
        exit(EXIT_FAILURE);
    }
    return new;
}

void set_filename(struct File *file, const char *name, int name_len)
{
    file->name = malloc(sizeof(char) * (name_len + 1));
    if (!file->name)
    {
        fputs("Allocation for filename failed!", stderr);
        exit(EXIT_FAILURE);
    }
    strncpy(file->name, name, name_len);
    file->name[name_len] = 0;
}

// count length of basename
int get_basename_len(const char *filename)
{
    int r = 0;
    while (*filename && *filename != '/')
        filename++, r++;
    return r;
}

// add a file to root
void add_file(struct File *root, const char *filename)
{
    int basename_len = get_basename_len(filename);
    int next = -1;
    for (int i = 0; i < root->size; i++)
    {
        if (strncmp(root->children[i]->name, filename, basename_len) == 0)
        {
            next = i;
            break;
        }
    }
    if (next == -1)
    {
        root->children = realloc(root->children, sizeof(struct File *) * (root->size + 1));
        if (!root->children)
        {
            fputs("Reallocation failed!", stderr);
            exit(EXIT_FAILURE);
        }
        struct File *temp_file = new_file();
        set_filename(temp_file, filename, basename_len);
        root->children[root->size] = temp_file;
        root->size++;
        next = root->size - 1;
    }
    if (!filename[basename_len])
        return;
    add_file(root->children[next], filename + basename_len + 1);
}

// recursively print file
void print_file(const struct File *root, int level)
{
    const char *INDENTATION = "  ";
    for (int i = 0; i < level; i++)
        printf("%s", INDENTATION);
    puts(root->name);
    for (int i = 0; i < root->size; i++)
        print_file(root->children[i], level + 1);
}

int main()
{
    // setup file root
    struct File *root = new_file();
    char pattern[PATTERN_SIZE];
    char filename[FULL_FILENAME_SIZE];
    fgets(pattern, PATTERN_SIZE, stdin);
    pattern[strlen(pattern) - 1] = 0;
    while (!feof(stdin))
    {
        fgets(filename, FULL_FILENAME_SIZE, stdin);
        filename[strlen(filename) - 1] = 0;
        add_file(root, filename);
    }
    // root->children[0] is "."
    cmd_find(pattern, root->children[0]);
    return 0;
}
```

### Input

Sample inputs follow this format. This is a little different from the input format for judging, but I think it is more readable.

```
pattern
empty line
root
```

The first line is `pattern` we want to match, and `root` is the directory structure in [`tree`](https://en.wikipedia.org/wiki/Tree_(command))'s output format.

#### Limits

* length of `pattern` $\le 16$
* Count of `struct File` you need to search $\le 10^4$
* Sum of all files' name's length $\le 10^5$
* Filenames' only consist of letters and digits.

#### Subtasks

|           | Limits                      | Score |
| --------- |:--------------------------- | -----:|
| #0        | No wildcards. No directory. |  $40$ |
| #1        | No directory.               |  $25$ |
| #2        | No wildcards.               |  $25$ |
| #3        | No other limits.            |  $10$ |
| **Total** |                             | $100$ |

### Output

Print every matched files' full name. Each one occupies one line, in given order.

### Sample Input 0

```
apple

.
├── apple
├── banana
└── grape
```

### Sample Output 0

```
./apple
```

### Sample Input 1

```
apple

.
├── apple
├── AppLe
└── APplE
```

### Sample Output 1

```
./apple
./AppLe
./APplE
```

### Sample Input 2

```
NT?U

.
├── NTU
├── NTNU
└── NTUST
```

### Sample Output 2

```
./NTNU
```

### Sample Input 2

```
NT*U

.
├── NTU
├── NTNU
└── NTUST
```

### Sample Output 2

```
./NTU
./NTNU
```


### Sample Input 3

```
*.py

.
├── m1.py
│   ├── foo.c
│   ├── bar.py
│   └── foo.py
└── m2
    └── bar.py
```

### Sample Output 3

```
./m1.py
./m1/bar.py
./m1/foo.py
./m2/bar.py
```

### Hint

* The code from your solution for [123. HRG](https://noj.tw/problem/123) will be helpful.

### Problem-solving Ideas

In this problem, you need to traversal all files.
The steps look like this:

1. Is `root`'s name match `pattern`? If so, print the full name.
2. Add `root` to prefix.
3. For every file in `root->children`, apply `cmd_find` on it.

So the most hard part I think is to implement the match logic, which is almost done in previous homework.


---