---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [sysprog2020]

---

# 2020q3 Homework1 (quiz1)

###### tags: `sysprog2020`

* [add entry](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#add-entry)
    * [AA1](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#AA1)
    * [AA2](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#AA2)
* [swap pair](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#swap_pair)
    * [BB1](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#BB1)
    * [BB2](https://hackmd.io/vdkBR0toQ_WIBYo0JtXpcw?both#BB2)

# node structure
```c
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```
```graphviz
digraph {
    label="node_t";
    node[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">value</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>next</td>
        </tr>
    </table>
    >];
    node1, node2
    node1:next->node2:value
    {rank=same; node1 node2}
}
```

# add entry

### Target : Append a new element to list
```c
void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    AA1;
    while (*indirect)
        indirect = &(*indirect)->next;
    AA2;
}
```

### analysis

Create a new element

```graphviz
digraph B {
    node[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">value</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>next</td>
        </tr>
    </table>
    >];
    n_0,n_1,n_2,n_new
    n_0:next->n_1:value
    n_1:next->n_2:value
    {rank=same; n_0 n_1, n_2, n_new}
}
```

find last element

```graphviz
digraph B {
    node[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">value</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>next</td>
        </tr>
    </table>
    >];
    n_0,n_1,n_2,n_new
    n_0:next->n_1:value
    n_1:next->n_2:value
    n_headpp[fontsize=12,shape=rect,label="indirect (node_t**)"]
    n_headp[fontsize=12,shape=rect,label="*indirect (node_t*)"]
    n_headpp->n_headp
    n_headp->n_0:value[label="start"]
    n_headp->n_0:next[label="after loop 0"]
    n_headp->n_1:next[label="after loop 1"]
    n_headp->n_2:next[label="after loop 2, *indirect==null"]
    {rank=same; n_0 n_1, n_2, n_new}
}
```
### AA1
AA1 is not easy, I found answer by looking options
```c
assert(new_node); // check memory is allocated
```

### AA2
Since original code has create a new node and loop through list to find last node, AA2 should be insert the new node.
```c
*indirect = new_node;
```


# swap_pair

### Target : swap every two node

```c
node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        node_t *tmp = *node;
        BB2;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}
```

### breakdown

```c
node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; // initialize
         *node && (*node)->next; // check there are two nodes to swap
         BB1) { // next
```         

#### before:

```graphviz
digraph{
    n_first[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">first</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*second</td>
        </tr>
    </table>
    >]
    n_second[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">second</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*third</td>
        </tr>
    </table>
    >]
    n_third[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">third</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*next</td>
        </tr>
    </table>
    >]
    n_node[shape=rect,fontsize=12,label="*node"];
    n_node->n_first:value;
    n_first:next->n_second:value;
    n_second:next->n_third:value;
    {rank=same;n_node n_first n_second, n_third}
}
```

```c
        node_t *tmp = *node; // cache the first node
        BB2;
        tmp->next = (*node)->next;/* ∵ the next of fisrt node shouble be
                                   * the next of seconde node
                                   * ∴ (*node) is a pointer to seconde node
                                   */
        (*node)->next = tmp; // assign pointer to first node to second.next
```

#### after:
```graphviz
digraph{
    n_first[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">first</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*third</td>
        </tr>
    </table>
    >]
    n_second[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">second</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*first</td>
        </tr>
    </table>
    >]
    n_third[shape=none label=<
    <table border="0" cellspacing="0">
        <tr>
            <td port="value" border="1">third</td>
            <td port="next" border="1" bgcolor='#AAAAAA'>*next</td>
        </tr>
    </table>
    >]
    n_first:next->n_third:value;
    n_second:next->n_first:value;
    n_node[shape=rect,fontsize=12,label="*node"];
    n_node->n_second:value;
    {rank=same;n_node n_first n_second, n_third}
}
```

### BB2
The missing part should be changing \*node (node_t\*) from 'pointer to first node' to 'pointer to second node'
```c
*node=(*node)->next
```

### BB1
And it need to go through next pair, which is set \*node (node_t\*) to 'pointer to third node', and \*node is a 'pointer to second node' after above operation.
```c
node=&(*node)->next->next
```

```c
    }
    return head;
}
```

### without return

simply change type of head from node_t* to node_t**


```c
void swap_pair(node_t **head)
{
    for (node_t **node = head;
         *node && (*node)->next;
         node=&(*node)->next->next) {
         
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}
```

### test

<iframe width="800px" height="800px" src="https://godbolt.org/e#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAM1QDsCBlZAQwBtMQBGAFlICsupVs1qhkAUgBMAISnTSAZ0ztkBPHUqZa6AMKpWAVwC2tLgHZSW9ABk8tTADljAI0zEQ3ABykADqgWE6rR6hibmvv6BdLb2Tkau7l6KypiqQQwEzMQEIcamnBZKKmp0GVkEMY4ubh7eCpnZuWEFig0VdlXxNV4AlIqoBsTIHADkUgDMdsiGWADU4uM69fioAHQIC9jiAAwAgju7BACePphYVLP1xAaqswD6d7QYmPNmsnuzn7N2BLMAbmwDJgFu9dl9LgRrrcHk85gAqewADwIIIO4jMABFZrDMHcUeNQQccXjZnCFAB3Zg%2BO4%2BZh4YgQYm/OEITDMdA9NFvA7gmjEWaM54kuEI57zcZYqQANlZ7JBpJx80kUulAtFWB6AFpNkj8dJsc8FhjpRB1ZgtTrMMjteNsLqeq9QeDwUzSQQjD5xVizaiPs7PmavWqcRbbbrfWD/bN3T4bXarb8jcHnqH48iI1Hkxq47qgzGM190ca/Z9iJgCINaLNZegI0W0XsDn9UHh0JdKdTafTJIKsMKWWyOVynV8%2BQLXSLFUma/LA9LVaaQzmE/KcUaTWbU7rl8iHeiR/6JzGgz6CTyo3OJVnzTu9ef/THb0HFynbwX/S/s5bkXmPe/XsW%2ByYk2LZtj4xA/Kw9S9riBBwsQnLciWszkggeDsBACH7vezrgT8VAQFIkhSAArD44gkbIkgkegpCkeRJHGiROi0ERpBkMQcYAoYmDsbenJnsh4LEEanHfneyH1o2wF7D8sxGHStAQIhB4Gn2vy0CR%2B6cJI4wkaQ2IGKwrA%2BJC9aCZGnyurQ3DabpvBKlKmnmap1njHZ4zjAZ0o2S5OHWcRbw6eMkjecqtDucBFkukKGmcB5nBhU5gXGtFXzWdsHnbEltDxVFhLIRO/JJhSVI0nSDI%2BdsAmqXh9BQQQmE1Q2lmzMVV6lZ2FVNXWyGdeV3aEcqWFpZ8dUEA1PUWUWIx9KwIAjCRIykKYIzbMtqALTochyJcAxDC8EycMtBALetPR9AA1iAJHZfNIzcMtq3raQm0jMtCggNlp1rbNpBwLAMCICgqAeuhbjkJQaBg%2Bw7jAJw2yhVQ6EEG4n0QM4Z3Lc4dhZEcC3HaQ0NGFoBAAPK0Kw%2BO/aQWAKaI7BY7T9KpGofyYJ9NNWqkBio0zPzKEzrB4M4xB43oWAEydEFGFLfQ0PQTBsBwPD8IIwiiCgO0yEIIufZAfSoKZQSc5qZPjB9KRpBoEBWE0%2BSWNolRxAkgh%2BAEJTBPoeRu5EnvO9U7iJUUrPpG09uCCH1u0GU2QB10QetOUEfB208eu5wfQKPtwxcHNC1LStTNvYinhSpqUrcLMwDIMgswI6skgCrghAkEq4yJbMegw247eZ132vSCdWMXaQ123UIC2PaQstSuMqxmB3BTbJ5Uor2Y2zeM9G0LR9X2kD953/UDEBIAMBA%2BLzkMQNDPjg4nZyt4nCuMCwjOq%2BSYs%2BHLk%2BLU9xcLSOihQgCBZil3LpXautd67bEbsPX6o8aw1GUr/aestxhSkblKTwnhJAAE4pRzwIfg0K29Xq70UPvQ%2Bs0ro3TugtC2RcaZvXgedfOIxJD/2YRQ6ho92bEACBobgQA%3D"></iframe>

# reverse

### Target : reverse link all node
```c
node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next; // cache next
        CCC; // link head to cursor and re assign cursor
        head = next; // process next
    }
    return cursor;
}
```

### CCC
```c
head->next = cursor;
cursor = head;
```

### without return
```c
void reverse(node_t **headp)
{
    node_t **cursor = headp;
    node_t *head = *headp;
    *cursor=NULL;

    while (head) {
        node_t *next = head->next; // cache next
        head->next = *cursor;
        *cursor = head;
        head = next; // process next
    }
}
```

# Fisher–Yates shuffle

The algorithm it self is not hard,
but it turns out pretty tricky to do with linked list.

```c
void FisherYatesShuffle(node_t **head)
{
    int n = 0;
    for (node_t *c = *head; c; ++n, c = c->next)
        ;
    for (int i = n; i > 1; --i, head = &(*head)->next) {
        node_t **target = head;
        for (int s = rand() % i; s; --s, target = &(*target)->next)
            ;
        swapNodes(head, target);
    }
}
```

The swap node is much more complex than I thought, it take about 2 hours to do this, it is easier to think step by step in paper.

```c
void swapNodes(node_t **head, node_t **target)
{
    if (head == target)
        return;
```

swap pointer to node(next pointer of previous node)

```c
    node_t *k = *head;
    *head = *target;
    *target = k;
```

swap next pointer of node

```c
    k = (*target)->next;
    (*target)->next = (*head)->next;
    (*head)->next = k;
}
```
