Homework 02 - HackMD

--- tags: homework --- # Homework 02 ###### tags: `structure` ### Week 02 * Release: 12:10 PM, 2020.03.30, Tue. * Due: 12:10 PM, 2020.04.07, Tue. * Extend: 12:10 PM, 2020.04.28, 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 --- ## 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.  ![](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:  $$ \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  --- 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 MUST 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$.  #### 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  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 MUST implement the file **diceheaven.c** is defined above, no "main" function on it. * REMEMBER to calculate each dice's total points, assign 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. ---