# 教學紀錄

## 其他筆記本

[Genereal.io Algorithm](https://hackmd.io/@St418/r1qurZvS3/edit)

## 2023/05/21

### HackMD簡介
* MarkDown
* **BOLD**
* `code`
* MarkUp
* HTML Hyper Text MarkUp Language

* Code

print('Hello World!')

### Memory Layout

https://blog.gtwang.org/programming/memory-layout-of-c-program/


#### static

#### dynamic stack
10
記憶體位址由宣告順序先後遞減(從高記憶體位址往低記憶體位址成長)
a - 2 -> 10
m - 1 -> 9
n - 0 -> 8

#### dynamic heap
vector

Point start {x, y} # stack

queue - reference(q) # stack
- allocator # heap

push stack -> heap
emplace heap

#### & reference operator

#### auto: known at compile time

deallocate delete

life span

### Tree

Time Complexity `O(log(n))`

Small `10 ^ 6`


### cin-cout vs scanf-printf

Address -> Value

#include <stdio.h>

int a, m, n;

// format string
scanf("%d%d%d", &a, &m, &n);

// 11 22 33
printf("%d %d %d\n", a, m, n);

// 249ff1c 249ff18 249ff14
printf("%x %x %x\n", &a, &m, &n);

Buffer 緩衝

System call - I/O

#include <iostream>

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int a, m, n;

// input stream
cin >> a >> m >> n;

// output stream -> to buffer
cout << a << m << n;

// end line
cout << endl;

// clear buffer -> system call
cout << '\n' << flush;

## 2023/06/05

[待補]

- 關鍵字：
### introsort(C++<algorithm>sort())

先進行快速排序(Quicksort)

遞迴深度超過一定深度後轉堆積排序(Heapsort)（深度：排序元素數量的對數值）

與quicksort.heapsort同為比較排序演算法

時間複雜度平均與最壞均為Ｏ(n log n)

### timsort(python sort)

先把整個資料分成小區塊，分別把小區塊的資料以Insertion Sort排序，然後再把這些區塊以Merge Sort的合併階段作法(merge function)來合併起來．

### hash

通過雜湊函式/演算法，將要檢索的項與用來檢索的索引（稱為雜湊，或者雜湊值）關聯起來，生成一種便於搜尋的資料結構（稱為雜湊表）

### kraskal's (MST)

權重最小的生成數

尋找方式：

將圖中所有邊依照權重由小到大排序

依序選取邊加回圖上，若形成環則不加

重複步驟直到圖上所有點皆有連線

所形成的圖形即稱為最小生成樹

### method of using Kraskal's to make a maze
It based on a namesake algorithm for finding a Minimal Spanning Tree (MST) over a graph.

Steps:

1.Create a set of all walls in the grid.

2.Randomly select a wall from the grid.

If that wall connects two disjoint trees, join the trees.

Otherwise, remove that wall from the set.

3.Repeat step 2 until there are no more walls left in the set.

code:

from random import shuffle
from argparse import ArgumentParser
import numpy as np
import matplotlib.pylab as plt

def generate(x, y):
    with plt.ion():
        grid = np.ones((y, x), dtype=np.uint8)

        forest = [(i, j) for i in range(1, y - 1, 2)
                  for j in range(1, x - 1, 2)]

        for tree in forest:
            grid[tree] = 0

        plt.imshow(grid, 'gray_r')

        edges = [(i, j) for i in range(2, y - 1, 2) for j in range(1, x - 1, 2)] + \
                [(i, j) for i in range(1, y - 1, 2)
                 for j in range(2, x - 1, 2)]

        shuffle(edges)

        parent = dict(zip(forest, forest))
        # {tree: tree for tree in forest}

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        count = len(forest)
        
        # unpack
        for u, v in edges:
            if u % 2:
                x = u, v - 1
                y = u, v + 1
            else:
                x = u - 1, v
                y = u + 1, v

            x = find(x)
            y = find(y)
            if x != y:
                parent[x] = y
                grid[u, v] = 0
                count -= 1

            plt.clf()
            plt.imshow(grid, 'gray_r')
            plt.pause(0.001)

            if count == 0:
                break

    return grid

parser = ArgumentParser()
parser.add_argument('-x', type=int, help='width', default=5)
parser.add_argument('-y', type=int, help='height', default=5)
args = parser.parse_args()

maze = generate(**vars(args))
plt.imshow(maze, 'gray_r')
plt.show()

# functional programming
# object-oriented programming

- 參考資料：
pip install mazelib
Github
https://github.com/john-science/mazelib/tree/main

## 2023/06/12

[待補]

- 關鍵字：迷宮製作
### numpy
用於科學運算，支援高階大規模的多維陣列與矩陣運算
### matplotlib
資料視覺化
### pytorch
python機器學習庫

## 2023/06/19

### python library

### itertools

Official website
https://docs.python.org/3/library/itertools.html

### argparse

Official website
https://docs.python.org/3/library/argparse.html

## 2023/07/31

Heuristic

Hamiltonain path (NP-Hard)

## 2023/09/04

## 2023/09/11

rens_pump_lns()
lns: Large Neighborhood Search
rins_pump_lns()