# HW01 參考答案

## 1.1 My String Library

此題可參考 [glibc 的官方實作](https://sourceware.org/git/?p=glibc.git;a=tree;f=string;h=c3bbd3e7962e69e3c3b44c8f42e0c3b16cb59957;hb=refs/heads/master)，值得一提的是他們將每個函式實作放在單獨的檔案中。

:::spoiler 同學的滿分解答 (Credit: 41247032S 吳Ｏ廷)

#include "mystring.h"


char *mystrchr(const char *s, int c){
    char *ptr=NULL;
    for(unsigned int i=0;i<strlen(s);i++){
        if(s[i] == c){
            ptr = (char*)&s[i];
            break;
        }
    }
    return ptr;
}
char *mystrrchr(const char *s, int c){
    char *ptr=NULL;
    for(int i=strlen(s)-1; i>=0; i--){
        if(s[i] == c){
            ptr = (char*)&s[i];
            break;
        }
    }
    return ptr;
}
size_t mystrspn(const char *s, const char *accept){
    size_t i;
    for (i = 0; s[i]; i++) {
        bool found = false;
        for (size_t j = 0; accept[j]; j++) {
            if (s[i] == accept[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            break;
        }
    }
    return i;
}
size_t mystrcspn(const char *s, const char *reject){
    size_t i;
    for (i = 0; s[i]; i++) {
        bool found = false;
        for (size_t j = 0; reject[j]; j++) {
            if (s[i] == reject[j]) {
                found = true;
                break;
            }
        }
        if (found) {
            break;
        }
    }
    return i;
}
char *mystrpbrk(const char *s, const char *accept){
    for (size_t i = 0; s[i]; i++) {
        for (size_t j = 0; accept[j]; j++) {
            if (s[i] == accept[j]) {
                return (char*)&s[i];
            }
        }
    }
    return NULL;
}
char *mystrstr(const char *haystack , const char *needle){
    if (!*needle) {
        return (char *)haystack;
    }
    for (size_t i = 0; haystack[i]; i++) {
        if (haystack[i] == needle[0]) {
            size_t j;
            for (j = 0; needle[j]; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (!needle[j]) {
                return (char *)&haystack[i];
            }
        }
    }
    return NULL;
}
char *mystrtok(char *str, const char *delim){
    static char *p = 0;
    if(str) p = str;
    else if(!p) return 0;
    str = p + strspn(p, delim);
    p = str + strcspn(str, delim);
    if(p == str) return p = 0;
    p = *p ? *p = 0, p + 1 : 0;
    return str;
}

:::

## 1.2 String Calculator

其中包含測試用的 `hw0102.c` 以及範例 `cal.c`、`cal.h`，給大家看 AC code 的其中一種實作方法：

> Murmur: 可以參考 calculate 的邏輯設計、如何將不同工作拆分成模組，以及動態記憶體管理的方式。特別在輸入檢查 `is_invalid()` 可以看一遍

https://drive.google.com/file/d/18G9VQqN8R94KyeIEiFugm82ljgNeUAyX/view?usp=sharing

> `cal.c` example code from Darrin Lin (41247022S)

## 1.3 Chain Rule

助教提供的 `hw0103.c`[由此去](https://drive.google.com/drive/folders/1WLExo1vfjnTvF8a_xVIXEOVPyR7aJVoL?usp=drive_link) 是助教的解法，在這邊另外提供其他同學的解法:

Credit: 41247027S 陳Ｏ羽
:::spoiler mychain.c

#include<stdint.h>
#include<stdlib.h>
#include<stdio.h>

typedef struct _sPoly{
    uint32_t size;
    uint32_t *pPowers;
    int32_t *pCoefficients;
} sPoly;

void copy(sPoly *x,const sPoly*y){
    (*x).size = (*y).size;
    (*x).pPowers = calloc((*y).size,sizeof(uint32_t));
    (*x).pCoefficients = calloc((*y).size,sizeof(int32_t));
    for(int i=0;i<y->size;i++){
        ((*x).pPowers[i]) = ((*y).pPowers[i]);
        ((*x).pCoefficients[i]) = ((*y).pCoefficients[i]);
    }
}
void move(sPoly *f,int32_t position){
    for(int i=position;i<(*f).size;i++){
        *((*f).pPowers+i) = *((*f).pPowers+i+1);
        *((*f).pCoefficients+i) = *((*f).pCoefficients+i+1);
    }
}

void sort(sPoly *f){
    for(int i=0;i<(*f).size;i++){
        for(int j=i+1;j<(*f).size;j++){
            if(*((*f).pPowers+i)<*((*f).pPowers+j)){
                int tmp = *((*f).pPowers+i);
                *((*f).pPowers+i) = *((*f).pPowers+j);
                *((*f).pPowers+j) = tmp;
                tmp = *((*f).pCoefficients+i);
                *((*f).pCoefficients+i) = *((*f).pCoefficients+j);
                *((*f).pCoefficients+j) = tmp;
            }
        }
    }
}

void arrange(sPoly *f){
    for(int i=0;i<(*f).size;i++){
        for(int j=i+1;j<(*f).size;j++){
            if(((*f).pPowers[i])==((*f).pPowers[j])){
                ((*f).pCoefficients[i])+=((*f).pCoefficients[j]);
                move(f,j);
                ((*f).size)--;
            }
        }
    }
    sort(f);
    for(int i=0;i<(*f).size;i++){
        if(((*f).pCoefficients[i])==0){
            move(f,i);
            ((*f).size)--;
        }
    }
    (*f).pCoefficients = realloc((*f).pCoefficients,((*f).size)*sizeof(int32_t));
    (*f).pPowers = realloc((*f).pPowers,((*f).size)*sizeof(uint32_t));
}

void multi(sPoly *x,const sPoly *y){
    sPoly tmp;
    tmp.size = (*x).size;
    tmp.pCoefficients=calloc(tmp.size,sizeof(int32_t));
    tmp.pPowers=calloc(tmp.size,sizeof(uint32_t));
    for(int i=0;i<tmp.size;i++)
        *(tmp.pPowers+i) = -1;
    for(int i=0;i<tmp.size;i++)
        *(tmp.pCoefficients+i) = 0;
    int used = 0;
    for(int i=0;i<(*x).size;i++){
        for(int j=0;j<y->size;j++){
            int power = (*x).pPowers[i] + (*y).pPowers[j],coefficents = (*x).pCoefficients[i] * (*y).pCoefficients[j],find = 0;
            for(int k=0;k<tmp.size;k++){
                if(*(tmp.pPowers+k) == power){
                    *(tmp.pCoefficients+k) += coefficents;
                    find = 1;
                    break;
                }
            }
            if(find == 0){
                
                if(used<tmp.size){
                    tmp.pCoefficients[used] = coefficents;
                    tmp.pPowers[used] = power;
                    used++;
                }
                else{
                    tmp.size++;
                    tmp.pCoefficients=realloc(tmp.pCoefficients,tmp.size*sizeof(int32_t));
                    tmp.pPowers=realloc(tmp.pPowers,tmp.size*sizeof(uint32_t));
                    tmp.pCoefficients[used] = coefficents;
                    tmp.pPowers[used] = power;
                    used++;
                }
            }
        }
    }
    arrange(&tmp);
    copy(x,&tmp);
}




int32_t chain_rule( sPoly *pResult , const sPoly *pFy, const sPoly *pFx ){
    if(pFy==NULL||pFx==NULL||pFx->pPowers==NULL||pFx->pCoefficients==NULL||pFy->pPowers==NULL||pFy->pCoefficients==NULL)
    	return -1;
    sPoly Fx,Fy;
    copy(&Fx,pFx);
    copy(&Fy,pFy);
    arrange(&Fy);
    arrange(&Fx);
    for(int i=0;i<Fy.size;i++){
        Fy.pCoefficients[i] = Fy.pCoefficients[i]*Fy.pPowers[i];
        if(Fy.pPowers[i]==0){
            move(&Fy,i);
            Fy.size--;
        }
        else
            Fy.pPowers[i]--;
    }
    arrange(&Fy);
    sPoly *tmp;
    tmp = calloc(Fy.size,sizeof(sPoly));
    sPoly tmp2;
    for(int i=0;i<Fy.size;i++){
        if(Fy.pPowers[i]==0){
            (*(tmp+i)).size = 1;
            (*(tmp+i)).pCoefficients = calloc(1,sizeof(int32_t));
            (*(tmp+i)).pPowers = calloc(1,sizeof(uint32_t));
            (*(tmp+i)).pCoefficients[0] = Fy.pCoefficients[i];
            (*(tmp+i)).pPowers[0] = 0;
        }
        else{
            for(int j=0;j<Fy.pPowers[i];j++){
                if(j==0)
                    copy(tmp+i,pFx);
                else
                    multi(tmp+i,pFx);
            }
            for(int j=0;j<(*(tmp+i)).size;j++){
                (*(tmp+i)).pCoefficients[j] *= Fy.pCoefficients[i];
            }
        }
    }
    tmp2.size = tmp[0].size;
    tmp2.pPowers = calloc(tmp2.size,sizeof(uint32_t));
    tmp2.pCoefficients = calloc(tmp2.size,sizeof(uint32_t));
    for(int i=0;i<tmp2.size;i++)
        tmp2.pPowers[i] = -1;
    for(int i=0;i<tmp2.size;i++)
        tmp2.pCoefficients[i] = 0;
    int used = 0;
    for(int i=0;i<Fy.size;i++){
        for(int j=0;j<(tmp[i]).size;j++){
            int find = 0;
            for(int k=0;k<tmp2.size;k++){
                if((tmp[i]).pPowers[j] == tmp2.pPowers[k]){
                    find = 1;
                    tmp2.pCoefficients[k]+=(tmp[i]).pCoefficients[j];
                    break;
                }
            }
            if(find == 0){
                
                if(used<tmp2.size){
                    tmp2.pCoefficients[used] = (tmp[i]).pCoefficients[j];
                    tmp2.pPowers[used] = (tmp[i]).pPowers[j];
                    used++;
                }
                else{
                    tmp2.size++;
                    tmp2.pPowers = realloc(tmp2.pPowers,tmp2.size*sizeof(uint32_t));
                    tmp2.pCoefficients = realloc(tmp2.pCoefficients,tmp2.size*sizeof(uint32_t));
                    tmp2.pCoefficients[used] = (tmp[i]).pCoefficients[j];
                    tmp2.pPowers[used] = (tmp[i]).pPowers[j];
                    used++;
                }
            }
        }
    }
    arrange(&tmp2);
    copy(pResult,&tmp2);
    for(int i=0;i<Fx.size;i++){
        Fx.pCoefficients[i] = Fx.pCoefficients[i]*Fx.pPowers[i];
        if(Fx.pPowers[i]==0){
            move(&Fx,i);
            Fx.size--;
        }
        else
            Fx.pPowers[i]--;
    }
    multi(pResult,&Fx);
    arrange(pResult);
    return 0;
}

:::

:::spoiler mychain.h

#include<stdint.h>



typedef struct _sPoly{
    uint32_t size;
    uint32_t *pPowers;
    int32_t *pCoefficients;
} sPoly;
int32_t chain_rule( sPoly *pResult , const sPoly *pFy, const sPoly *pFx );

:::

## 1.4 Maze

:::spoiler mymaze.h

#pragma once

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>


typedef struct _sRoom{
    uint32_t cost;
    uint8_t doors; // 8 bits: aabbccdd
    // aa: the up door number 0-3
    // bb: the right door number 0-3
    // cc: the down number 0-3
    // dd: the left door number 0-3
} sRoom;

typedef struct _sPoint {
    uint32_t row;
    uint32_t col;
} sPoint;

typedef struct _sPath {
    uint32_t length; // Path length.
    uint32_t cost; // Cost
    sPoint *pPath; // An array of all points in order.
} sPath;

typedef enum Direction{
    UP = 0,
    RIGHT = 1,
    DOWN = 2,
    LEFT = 3
}Direction;

typedef struct _sMaze_info {
    const sRoom *pMaze;
    sPath *cur_min_path;
    sPath *pMinPath;
    uint32_t row;
    uint32_t col;
    bool *found;
    bool has_path;
} sMaze_info;

// The start point is pMaze[0][0] and the exit point is pMaze[row -1][col -1]
// If there is no path , return 0; otherwise , return 1;
int32_t find_min_path(const sRoom *pMaze, const uint8_t row, const uint8_t col, sPath *pMinPath);
static void dfs_find_path(const sPoint src_pos);
static void add_room_to_path(const sPoint pos);
static void remove_room_from_path();
static bool is_arrive_maze_end(const sPoint pos);
static void update_min_path();
static bool can_move(const sPoint src_pos, const sPoint dest_pos, const Direction next_direction);
static bool has_path(const sRoom *src_room, const sRoom *dest_room, const Direction next_direction);
static int get_index(const sPoint pos);
static sRoom* get_room(const sPoint pos);
static uint8_t get_door(const sRoom *room, const Direction direction);
static sPoint get_dest_pos(const sPoint src_pos, const Direction next_direction);
static sMaze_info* create_maze_info(const sRoom *pMaze, const uint8_t row, const uint8_t col);
static void delete_maze_info(sMaze_info *maze_info);
static sPath* create_pMinPath(const uint16_t size);
static void free_pMinPath(sPath *pMinPath);
static void copy_pMinPath(const sPath *src, sPath *dest);

:::

:::spoiler mymaze.c

#include "mymaze.h"

static sMaze_info *maze_info;

int32_t find_min_path(const sRoom *pMaze, const uint8_t row, const uint8_t col, sPath *pMinPath) {
    bool has_path = false;

    if (pMaze == NULL || pMinPath == NULL || row == 0 || col == 0) {
        return -1;
    }

    maze_info = create_maze_info(pMaze, row, col);
    
    dfs_find_path((sPoint){0, 0});
    has_path = maze_info->has_path;
    if (has_path) {
        copy_pMinPath(maze_info->pMinPath, pMinPath);
    }
   
    delete_maze_info(maze_info);

    return has_path ? 1 : 0;
}

static void dfs_find_path(const sPoint src_pos) {
    
    if (is_arrive_maze_end(src_pos)) {
        add_room_to_path((sPoint){maze_info->row - 1, maze_info->col - 1});
        update_min_path();
        remove_room_from_path();
        maze_info->has_path = true;
        return;
    }

    add_room_to_path(src_pos);
    
    for (int direction = 0; direction < 4; direction++) {   
        const sPoint dest_pos = get_dest_pos(src_pos, direction);
        if (can_move(src_pos, dest_pos, direction)) {
            dfs_find_path(dest_pos);
        }
    }
    remove_room_from_path();
}

static void add_room_to_path(const sPoint pos) {
    maze_info->found[get_index(pos)] = true;
    maze_info->cur_min_path->pPath[maze_info->cur_min_path->length] = pos;
    maze_info->cur_min_path->cost += get_room(pos)->cost;
    maze_info->cur_min_path->length++;
}

static void remove_room_from_path() {
    maze_info->cur_min_path->length--;
    const sPoint pos = maze_info->cur_min_path->pPath[maze_info->cur_min_path->length];

    maze_info->cur_min_path->cost -= get_room(pos)->cost;
    maze_info->found[get_index(pos)] = false;
    maze_info->cur_min_path->pPath[maze_info->cur_min_path->length] = (sPoint){0, 0};
}

static bool is_arrive_maze_end(const sPoint pos) {
    return pos.row == maze_info->row - 1 && pos.col == maze_info->col - 1;
}

static void update_min_path() {
    if (maze_info->cur_min_path->cost >= maze_info->pMinPath->cost) {
        return;
    }
    
    memcpy(maze_info->pMinPath->pPath,  maze_info->cur_min_path->pPath, maze_info->row * maze_info->col * sizeof(sPoint));
    maze_info->pMinPath->cost = maze_info->cur_min_path->cost;
    maze_info->pMinPath->length = maze_info->cur_min_path->length;
}

static bool can_move(const sPoint src_pos, const sPoint dest_pos, const Direction direction) {
    if (dest_pos.row < 0 || maze_info->row <= dest_pos.row || dest_pos.col < 0 || maze_info->col <= dest_pos.col)  {
        return false;
    }
    if (maze_info->found[get_index(dest_pos)]) {
        return false;
    }
    
    const sRoom *src_room = get_room(src_pos);
    const sRoom *dest_room = get_room(dest_pos);
    if (!has_path(src_room, dest_room, direction)) {
        return false;
    }

    return true;
}

static bool has_path(const sRoom *src_room, const sRoom *dest_room, const Direction direction) {
    if (direction == UP && get_door(src_room, UP) == get_door(dest_room, DOWN)) {
        return true;
    }
    if (direction == RIGHT && get_door(src_room, RIGHT) == get_door(dest_room, LEFT)) {
        return true;
    }
    if (direction == DOWN && get_door(src_room, DOWN) == get_door(dest_room, UP)) {
        return true;
    }
    if (direction == LEFT && get_door(src_room, LEFT) == get_door(dest_room, RIGHT)) {
        return true;
    }

    return false;
}


static int get_index(const sPoint pos) {
    return pos.row * maze_info->col + pos.col;
}

static sRoom* get_room(const sPoint pos) {
    return (sRoom *)(maze_info->pMaze + get_index(pos));
}

static uint8_t get_door(const sRoom *room, const Direction direction) {
    if (direction == UP) {
        return (room->doors & 0b11000000) >> 6;
    }
    if (direction == RIGHT) {
        return (room->doors & 0b00110000) >> 4;
    }
    if (direction == DOWN) {
        return (room->doors & 0b00001100) >> 2;
    }
    if (direction == LEFT) {
        return (room->doors & 0b00000011) >> 0;
    }
    return -1;
}

static sPoint get_dest_pos(const sPoint src_pos, const Direction direction) {
    // UP, RIGHT, DOWN, LEFT
    const int row_dir[4] = {-1, 0, 1, 0};
    const int col_dir[4] = {0, 1, 0, -1};

    return (sPoint){src_pos.row + row_dir[direction], src_pos.col + col_dir[direction]};
}



static sMaze_info* create_maze_info(const sRoom *pMaze, const uint8_t row, const uint8_t col) {
    sMaze_info *maze_info;

    maze_info = calloc(1, sizeof(sMaze_info));
    if (maze_info == NULL) {
        return NULL;
    }

    maze_info->pMaze = pMaze;
    maze_info->row = row;
    maze_info->col = col;
    maze_info->has_path = false;

    maze_info->found = calloc(row * col, sizeof(bool));
    if (maze_info->found == NULL) {
        free(maze_info);
        return NULL;
    }

    maze_info->cur_min_path = create_pMinPath((uint16_t)row * (uint16_t)col);
    maze_info->pMinPath = create_pMinPath((uint16_t)row * (uint16_t)col);
    maze_info->pMinPath->cost = UINT32_MAX;
    if (maze_info->cur_min_path == NULL) {
        free(maze_info->found);
        free(maze_info);
        return NULL;
    }
    
    return maze_info;
}

static void delete_maze_info(sMaze_info *maze_info) {
    if (maze_info == NULL) {
        return;
    }
    if (maze_info->found != NULL) {
        free(maze_info->found);
    }
    free_pMinPath(maze_info->cur_min_path);
    free_pMinPath(maze_info->pMinPath);
    free(maze_info);
}

static sPath* create_pMinPath(const uint16_t size) {
    sPath *pMinPath;

    pMinPath = (sPath *)calloc(1, sizeof(sPath));
    if (pMinPath == NULL) {
        return NULL;
    }

    pMinPath->length = 0;
    pMinPath->cost = 0;
    pMinPath->pPath = calloc(size, sizeof(sPoint));
    if (pMinPath->pPath == NULL) {
        free(pMinPath);
        return NULL;
    }
    return pMinPath;
}

static void free_pMinPath(sPath *pMinPath) {
    if (pMinPath == NULL) {
        return;
    }
    if (pMinPath->pPath != NULL) {
        free(pMinPath->pPath);
    }
    free(pMinPath);
}

static void copy_pMinPath(const sPath *src, sPath *dest) {
    dest->length = src->length;
    dest->cost = src->cost;
    dest->pPath = calloc(src->length, sizeof(sPoint));
    memcpy(dest->pPath, src->pPath, src->length * sizeof(sPoint));
}

:::

## 1.5 Taiko Music Generator
:::spoiler taiko.c

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#include "taiko.h"

#define BUFFER_SIZE 1000

#define INIT_BPM_TAG "BPM:"
#define OFFSET_TAG "OFFSET:"

#define COURSE_TAG "COURSE:"
#define START_TAG "#START"
#define MEASURE_TAG "#MEASURE "
#define BPM_CHANGE "#BPMCHANGE "
#define END_TAG "#END"
#define MEASURE_SLICE_TAG ','
#define CHART_HEADER_CFG_TAG ":"
#define CHART_CFG_TAG "#"

#define COURSE_SYMBOL_EDIT "Edit"
#define COURSE_SYMBOL_EDIT_NUM "4"
#define COURSE_SYMBOL_ONI "Oni"
#define COURSE_SYMBOL_ONI_NUM "3"
#define COURSE_SYMBOL_HARD "Hard"
#define COURSE_SYMBOL_HARD_NUM "2"
#define COURSE_SYMBOL_NORMAL "Normal"
#define COURSE_SYMBOL_NORMAL_NUM "1"
#define COURSE_SYMBOL_EASY "Easy"
#define COURSE_SYMBOL_EASY_NUM "0"

// utility function define
size_t io_read(char***);
bool set_chart(Chart *, const float, char**, const uint64_t, const uint64_t);
uint8_t is_chart_content(const char*);
Measure add_measure(const char*, const float, const uint64_t, const uint64_t);
bool is_exist_taiko_note(const char*);

bool ReadtjaFile(Taiko **src)
{
    // temp variable
    float offset = 0.0;
    float init_bpm = 0.0;
    uint64_t course = 0;

    // Read tja text file from stdin io
    char **text = NULL;
    size_t line = io_read(&text);
    
    *src = (Taiko*)calloc(1, sizeof(Taiko));

    (*src)->offset = 0;
    for (int i = 0; i < 5; i++)
    {
        ((*src)->chart)[i] = NULL;
    }
    
    // Process tja text file
    for (int i = 0; i < line; i++)
    {
        if (strstr(text[i], OFFSET_TAG) != NULL) // get offset
        {
            if (sscanf(text[i], OFFSET_TAG"%f", &offset) != 1)
            {
                fprintf(stderr, "offset error when getting\n");
                return false;
            }
            else
            {
                (*src)->offset = offset;
            }
        }
        else if (strstr(text[i], INIT_BPM_TAG) != NULL) // get bpm
        {
            if (sscanf(text[i], INIT_BPM_TAG"%f", &init_bpm) != 1)
            {   
                fprintf(stderr, "bpm error when getting\n");
                return false;
            }
        }
        else if (strstr(text[i], COURSE_TAG) != NULL) // get course and start to set Taiko->chart
        {
            if (strstr(text[i], COURSE_SYMBOL_EDIT) != NULL || strstr(text[i], COURSE_SYMBOL_EDIT_NUM) != NULL)
            {
                course = EDIT;
            }
            else if (strstr(text[i], COURSE_SYMBOL_ONI) != NULL || strstr(text[i], COURSE_SYMBOL_ONI_NUM) != NULL)
            {
                course = ONI;
            }
            else if (strstr(text[i], COURSE_SYMBOL_HARD) != NULL || strstr(text[i], COURSE_SYMBOL_HARD_NUM) != NULL)
            {
                course = HARD;
            }
            else if (strstr(text[i], COURSE_SYMBOL_NORMAL) != NULL || strstr(text[i], COURSE_SYMBOL_NORMAL_NUM) != NULL)
            {
                course = NORMAL;
            }
            else if (strstr(text[i], COURSE_SYMBOL_EASY) != NULL || strstr(text[i], COURSE_SYMBOL_EASY_NUM) != NULL)
            {
                course = EASY;
            }
            else
            {
                fprintf(stderr, "course value invalid\n");
                return false;
            }

            for (int j = i; i < line; j++)
            {
                if (strstr(text[j], END_TAG) != NULL)
                {
                    ((*src)->chart)[course] = (Chart*)calloc(1, sizeof(Chart));
                    if ( !set_chart((*src)->chart[course], init_bpm, text, i, j) )
                    {
                        return false;
                    }
                    ((*src)->chart)[course]->course = course;
                    break;
                }
            }
        }
    }

    return true;
}

void WritejsonFile(const Taiko *src)
{
    puts("{");
    puts("\t\"data\": [");
    for (int i = 4; i >= 0; i--)
    {
        if(src->chart[i] == NULL) continue;
        puts("\t\t{");
        printf("\t\t\t\"course\": %d,\n", src->chart[i]->course);
        puts("\t\t\t\"chart\": [");
        
        float music_time = -(src->offset);
        bool flag = false;

        for (int j = 0; j < src->chart[i]->measure_size; j++)
        {
            const char *measure = src->chart[i]->measure[j].chart_content;
            const uint64_t bpm = src->chart[i]->measure[j].bpm;
            const uint64_t beat = src->chart[i]->measure[j].beat;
            const uint64_t note = src->chart[i]->measure[j].note;
            
            const float duration = (60.0 / (float)bpm) *  ((float)beat / (float)strlen(measure)) * (4.0 / (float)note);
            
            for (int m = 0; m < strlen(measure); m++)
            {
                TaikoNote n = measure[m] - '0';            
                if (n >= DON && n <= BIGKA)
                {
                    if(flag) printf(",\n");
                    printf("\t\t\t\t[%d, %f]", n, music_time);
                    flag = true;
                }

                music_time += duration;
            }
        }
        flag = false;
        puts("\n\t\t\t]");
        printf("\t\t}");
        if(i <= 0)
        {
            printf("\n");
        }
        else
        {
            printf(",\n");
        }
        
    }
    puts("\t]");
    puts("}");
}

size_t io_read(char*** src)
{
    size_t size = 0;
    char *buffer = (char*)calloc(BUFFER_SIZE, sizeof(char*));
    while (scanf("%[^\n]%*c", buffer) != EOF)
    {
        *src = (char**)realloc(*src, (size + 1) * sizeof(char**));
        for (size_t i = 0; i < strlen(buffer); i++) 
        {
            if (buffer[i] == '\n' || buffer[i] == '\r') 
            {
                buffer[i] = 0;
            }
        }
        (*src)[size] = (char*)calloc(strlen(buffer)+1, sizeof(char*));        
        strncpy((*src)[size], buffer, strlen(buffer));
        memset(buffer, 0, BUFFER_SIZE);
        size++;
    }
    return size;
}

bool set_chart(Chart *chart, const float init_bpm, char **text, const uint64_t start, const uint64_t end)
{
    // set measure
    chart->measure = (Measure*)calloc(1, sizeof(Measure));
    chart->measure_size = 0;

    uint64_t beat = 4;
    uint64_t note = 4;
    float bpm = init_bpm;

    char *tmp_chart_content = (char*)calloc(1, sizeof(char));
    
    for (int i = start; i < end; i++)
    {
        uint8_t flag = is_chart_content(text[i]);

        // get now measure
        if (strstr(text[i], MEASURE_TAG) != NULL)
        {
            if (sscanf(text[i], MEASURE_TAG"%d/%d", &beat, &note) != 2)
            {
                fprintf(stderr, "measure error when getting\n");
                return false;
            }
        }
        else if (strstr(text[i], BPM_CHANGE) != NULL)
        {
            if (sscanf(text[i], BPM_CHANGE"%f", &bpm) != 1)
            {
                fprintf(stderr, "bpm_change error when getting\n");
                return false;
            }
        }
        else if (flag > 0)
        {
            if (flag == 1)
            {
                text[i][strlen(text[i]) - 1] = 0;
            }
            
            tmp_chart_content = (char *)realloc(tmp_chart_content, sizeof(char) * ((strlen(text[i]) + strlen(tmp_chart_content) + 1)));
            tmp_chart_content[strlen(text[i]) + strlen(tmp_chart_content)] = 0;
            strncat(tmp_chart_content, text[i], strlen(text[i]));

            if (flag == 1)
            {
                chart->measure = (Measure*)realloc(chart->measure, (chart->measure_size + 1) * sizeof(Measure));
                (chart->measure)[chart->measure_size] = add_measure(tmp_chart_content, bpm, beat, note);
                chart->measure_size++;
                memset(tmp_chart_content, 0, strlen(tmp_chart_content) * sizeof(char));
            }
        }
    }
    return true;
}


uint64_t lcm(uint64_t a, uint64_t b) 
{
    uint64_t tempA = a, tempB = b;

    while (a != b) 
    {
        if (a < b) 
        {
            a += tempA;
        } else 
        {
            b += tempB;
        }
    }

    return a;
}

Measure add_measure(const char *chart_content, const float bpm, const uint64_t beat, const uint64_t note)
{
    Measure tmp_m;
    tmp_m.beat = beat;
    tmp_m.bpm = bpm;
    tmp_m.note = note;
    size_t len_chart_content = strlen(chart_content);

    if(len_chart_content < beat)
    {
        uint64_t temp_beat = 0;
        if(len_chart_content == 0)
        {
            tmp_m.chart_content = (char*)calloc(beat + 1, sizeof(char));
            temp_beat = beat;
        } 
        else
        {
            temp_beat = lcm(len_chart_content, beat);
            tmp_m.chart_content = (char*)calloc(temp_beat + 1, sizeof(char));
        } 

        for (int i = 0; i < temp_beat; i++)
        {
            if(len_chart_content == 0)
            {
                tmp_m.chart_content[i] = BLANK + '0';
            }
            else if(i % (temp_beat/len_chart_content) == 0)
            {
                tmp_m.chart_content[i] = chart_content[i/(temp_beat/len_chart_content)];
            }
            else
            {
                tmp_m.chart_content[i] = BLANK + '0';
            }
        }
    }
    else
    {
        tmp_m.chart_content = (char*)calloc(len_chart_content + 1, sizeof(char));
        strncpy(tmp_m.chart_content, chart_content, len_chart_content);
    }
    
    return tmp_m;
}

uint8_t is_chart_content(const char *str)
{
    size_t str_len = strlen(str);

    if (strstr(str, CHART_CFG_TAG) != NULL || strstr(str,CHART_HEADER_CFG_TAG) != NULL)
    {
        return 0;
    }
    if (str[str_len - 1] == MEASURE_SLICE_TAG)
    {
        return 1;
    }
    else if(str[str_len - 1] >= '0' && str[str_len - 2] <= '9')
    {
        return 2;
    }
    return 0;
}

:::

:::spoiler taiko.h

#pragma once

#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

typedef enum _Course {
    EASY = 0,
    NORMAL,
    HARD,
    ONI,
    EDIT
} Course;

typedef enum _TaikoNote { 
    BLANK = 0,
    DON,
    KA,
    BIGDON,
    BIGKA,
    DRUMROLL,
    BIGDRUMROLL,
    BALLOON,
    END,
    POTATO
} TaikoNote;

typedef struct _Measure
{
    char *chart_content;
    float bpm;
    uint64_t beat;
    uint64_t note;
} Measure;

typedef struct _Chart
{
    Course course;
    Measure *measure;
    uint64_t measure_size;
} Chart;

typedef struct _Taiko
{
    Chart *chart[5];
    float offset;
} Taiko;

bool ReadtjaFile(Taiko **);
void WritejsonFile(const Taiko *);

:::

::: spoiler hw0105.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "taiko.h"

int main() 
{
    Taiko *src = NULL;
    if ( !ReadtjaFile(&src) ) return 0;
    WritejsonFile(src);
    return 0;
}

:::

## 1.6 Bonus: _BitInt(N)
1. $2^{\lceil log_2(N / 8) \rceil}$ (size 只會是 1, 2, 4, 8, 16 byte 喔，單純回答 $N / 8$ 是錯的)
2. 會導致 overflow 僅保留後 N 位 (僅回答 overflow 或是 warning 不夠完整，我會算錯)
3. Yes
4. unsigned _BitInt
5. Error