[NetHack] How to build NetHack 3.7 with Qt on macOS

Listed libraries are key requirements

You might need another libraries to finish the build

Install Xcode from App Store or gcc from MacPorts 

Make sure the executables are added to $PATH

$ whereis gcc

/usr/bin/gcc

$ whereis clang

/usr/bin/clang exists 

Download the source code from github

$ git clone git@github.com:NetHack/NetHack.git

$ cd NetHack

$ git checkout NetHack-3.7

Download lua submodule

$ git submodule init

$ git submodule update --recursive

Download qt5 from MacPorts

Qt5 will be installed in /opt/local/libexec/qt5

Make sure the path exists

$ sudo port install qt5 

Generate Makefile

$ sh sys/unix/setup.sh sys/unix/hints/macOS.370

Edit <NetHack source root>/Makefile with familiar editor

uncomment #WANT_WIN_QT=1 

uncomment #WANT_DEFAULT=Qt

uncomment #QTDIR=/opt/local/libexec/qt5

$ make

This should work

Wait until the build finishes

$ make install

My experience is the final product lies in /Users/<user>/nethackdir

Kindly tell me if you find it in another place, thanks in advance

Finding Most Frequent Duplicates Mode(s) in Binary Search Tree (BST) in C

描述

不同於傳統二元搜尋樹，節點的值可以重複，所以左子樹的值小於等於根的值，右子樹的值大於等於根的值，在樹上找到重複頻率最高的節點(們)並回傳

範例

輸入：空樹
輸出：{}

輸入：單節點

    0
   / \

輸出：{0}

輸入：不同節點各出現一次

    0
     \
      1

輸出：{0,1}

輸入：某節點出現二次

    1
     \
     (2)
     /
   (2)

輸出：{2}

輸入：某些節點出現二次

    (3)
   /   \
 (1)    5
 / \   / \
0   2 4   6
   / \
 (1) (3)

輸出：{1,3}

想法

要先知道哪些/個節點出現頻率最高，必須先走訪節點們比一次。取得最高頻率後，找出節點出現頻率等於最高頻率的個數，用這個動態分配回傳陣列的記憶體，再走訪一次把出現頻率最高的節點(們)加入陣列。

情境是記憶體有限，想一次走訪用雜湊表紀錄節點值和頻率，除了發生衝突(conflict)會算錯頻率，記憶體因為表太大爆掉，變成不得不用時間換空間。

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void get_modes(struct TreeNode *root, double *last, int *freq, int max, int *modes, int *i)
{
    int val = root->val;
    
    if (root->left)
        get_modes(root->left, last, freq, max, modes, i);

    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
    {
        modes[*i] = *last;
        (*i)++;
    }
    
    if (root->right)
        get_modes(root->right, last, freq, max, modes, i);
}

void get_num_of_modes(struct TreeNode *root, double *last, int *freq, int max, int *returnSize)
{
    int val = root->val;
    
    if (root->left)
        get_num_of_modes(root->left, last, freq, max, returnSize);
    
    if (*last != val)
    {        
        *freq = 1;        
        *last = val;
    }
    else
        (*freq)++;
    
    if (*freq == max)
        (*returnSize)++;


    if (root->right)
        get_num_of_modes(root->right, last, freq, max, returnSize);
}

void get_max_freq(struct TreeNode *root, double *last, int *freq, int *max)
{
    int val = root->val;
    
    if (root->left)
        get_max_freq(root->left, last, freq, max);
    
    if (*last != val)
    {
        *freq = 1;
        *last = val;
    }
    else
        (*freq)++;

    if (*freq > *max)
        *max = *freq;
    
    if (root->right)
        get_max_freq(root->right, last, freq, max);
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findMode(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    
    int *modes = NULL;
    double last = -2147483649; // Out of int range to avoid 0 case
    int freq = 0;
    int max = 0;
    int i = 0;
    
    if (root == NULL)
        return NULL;
    
    get_max_freq(root, &last, &freq, &max);
    
    freq = 0;
    last = -2147483649;
    get_num_of_modes(root, &last, &freq, max, returnSize);

    freq = 0;
    last = -2147483649;
    modes = (int *)malloc(sizeof(int) * (*returnSize));
    get_modes(root, &last, &freq, max, modes, &i);
    
    return modes;
}

Validating Binary Search Tree (BST) in C

描述

驗證二元搜尋樹是否有效，有效的二元搜尋樹必須符合下列原則

• 左子樹的值小於根的值
• 右子樹的值大於根的值
• 左右子樹也是二元搜尋樹

範例

• 有效

無節點

單節點

    0
   / \

左右子樹

    2
   / \
  1   3

• 無效
有相同的值

    1
     \
     (1)

右子樹節點的值小於根的值

    10
   / \
  5   15
     / \
   (6)  20

左子樹節點的值大於根的值

    3
     \
     30
    /
   10
     \
     15
       \
      (45)

原理

用中序走訪(inorder traversal)二元搜尋樹取得節點的值會升冪排列，一旦走訪節點的值小於等於前面節點的值，就不是有效二元搜尋樹

實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool validate(struct TreeNode* root, double *last)
{   
    if (root->left)
        if (validate(root->left, last) == false)
            return false;
    
    // Check ascending order
    if (root->val > *last)
        *last = root->val;
    else
        return false;
    
    if (root->right)
        if (validate(root->right, last) == false)
            return false;
    
    // Subtree is valid
    return true;
}

bool isValidBST(struct TreeNode* root){  
    double last = -2147483649; // integer type minimum is -2147483648, last should be able to store integer minimum
    
    if (root == NULL)
        return true;

    return validate(root, &last);
}

Remove nth node from end of a linked list in C in Linear Time

描述

刪除從串列尾巴往回數第n個節點，n一定有效，回傳輸出串列的head

範例

輸入：1->2->3->4->5, n = 2 輸出：1->2->3->5
輸入：1, n = 1 輸出：NULL
輸入：1->2, n = 2 輸出

想法

用兩個距離n+1的串列指標，一個走訪在前，一個跟在後，走訪在前的指標碰到串列尾節點時，後面的指標在欲刪除節點的前一個。前述的想法適用於3個以上的節點，所以0到2個節點用特殊狀況處理。

實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    int x = 0;
    struct ListNode *rear = NULL;
    struct ListNode *ahead = NULL;

    // Empty linked list
    if (!head)
        return head;
    
    // Linked list with one node, n must be 1
    if (!head->next)
        return NULL;
    
    // Linked list with two nodes, n is either 1 or 2
    if (!head->next->next)
    {
        if (n == 1)
        {
            head->next = NULL;
            return head;
        }

        return head->next;
    }
    
    ahead = head;
    for (x = 0; x < n; x++)
        ahead = ahead->next;   
        
    // head is to be removed
    if (!ahead)
        return head->next;
    
    rear = head;    
    while (ahead->next)
    {
        ahead = ahead->next;
        rear = rear->next;
    }
    
    rear->next = rear->next->next;
    return head;
}

Check if Parentheses is Valid in C

規則

• 括弧只有'('、'['與'{'三種
• 括弧必須成對
• 括弧順序必須正確

範例

有效

• "()"
• "{}[]()"
• "[{}]"

無效

• "([{]})"
• "(]"
• "([])("
• "([])}"

原理

• 遞迴：有效的成對括弧內必含有有效括弧
• 堆疊：有效的成對括弧順序是close先進open後出
• 不符合以上原則都是無效括弧

實作

// MODE 0 for recursive, 1 for iterative
#define MODE 1

struct stack {
    char items[65535];
    int top;
};

void push(struct stack *s, char c)
{
    s->items[s->top] = c;
    s->top++;
}

char pop(struct stack *s)
{
    s->top--;
    return s->items[s->top];
}

bool open(char c)
{
    return c == '(' || c== '[' || c == '{';
}

bool worker(struct stack *t, char *s)
{
    char s0 = s[0];
    char top = '\0';
    
    if (s0 == '\0')
    {
        // No pair for open
        if (t->top != 0)
            return false;
        
        return true;
    }
    
    if (open(s0))
    {
        push(t, s0);   
        return worker(t, s + 1);
    }
    
    // No pair for close
    if (t->top == 0)
        return false;
    
    top = t->items[t->top - 1];
    
    if (s0 == ')' && top != '(')
        return false;
    
    if (s0 == ']' && top != '[')
        return false;

    if (s0 == '}' && top != '{')
        return false;

    pop(t);
    return worker(t, s + 1);
}

bool isValid(char * s){
    struct stack t = {0};

#if MODE == 0
    return worker(&t, s);
#else
    int i = 0;
    char c = '\0';
    char top = '\0';

    for (i = 0; s[i] != '\0'; i++)
    {
        c = s[i];
        
        if (open(c))
        {
            push(&t, c);
            continue;
        }
        
        // No pair for close
        if (t.top == 0)
            return false;
        
        top = t.items[t.top - 1];
        if (c == ')' && top != '(')
            return false;
        
        if (c == ']' && top != '[')
            return false;
        
        if (c == '}' && top != '{')
            return false;

        pop(&t);
    }
    
    // Check no pair for open
    return t.top == 0;
#endif
}

Finding Length of Longest Substring without Repeating Characters in C in Linear Time

出處

原理

走訪字串中每個字元，若當前被掃瞄字元沒有被走訪過則暫存到陣列中，目前長度加1，否則判斷當前被掃瞄字元是否在不重複字元的子字串中，若不在則目前長度加1，否則檢查最大長度與目前長度，若目前長度大於最大長度就將最大長度設定為目前長度，並且移動不重複字元子字串的起始點到重複字元的下一個字元，例如輸入為"dxdy"，遇到第二個d而且d已經在不重複字元子字串"dx"中，則不重複字元子字串起始點從d移動到x，例如輸入為"pwwkew"，遇到第二個w而且w已經在不重複自原子字串"pw"中，則不重複自原子字串起始點從p移動到第二個w，最後重設目前長度，長度應為新的不重複字元子字串起始點算到當前被掃瞄字元，走訪完所有字元後的目前長度再跟最大長度比較決定最大長度。

實作

#define NUM_CHAR 256

int hash(char x)
{
    return x % NUM_CHAR;
}

int length_of_longest_substring(char * str)
{
    char visited[NUM_CHAR] = {0};
    char temp[NUM_CHAR] = {0};
    char * current_scanned = NULL;
    char * nrcs_start = NULL;  // nrcs: non-repeating character substring
    int key = 0;
    int cur_length = 0;
    int max_length = 0;
    
    current_scanned = s;
    nrcs_start = str;
    while (*current_scanned != '\0')
    {        
        key = hash(*current_scanned);
        if (visited[key] != *current_scanned)
        {
            visited[key] = *current_scanned;
            cur_length++;
            goto end;
        }
        
        strncpy(temp, nrcs_start, cur_length);
        if (!strchr(temp, *current_scanned))
        {
            cur_length++;
            memset(temp, 0, NUM_CHAR);
            goto end;
        }
        
        memset(temp, 0, NUM_CHAR);
        
        if (cur_length > max_length)
            max_length = cur_length;

        while (*nrcs_start != *current_scanned)
            nrcs_start++;
        nrcs_start++;
        
        cur_length = current_scanned - nrcs_start + 1;

end:
        current_scanned++;
    }

    if (cur_length > max_length)
        max_length = cur_length;
    
    return max_length;
}

The Clean Code Talks - Don't Look For Things! 整理

重點整理：

• 用細緻的方式回到基本去討論依賴注入(Dependency Injection)
• 測試系統時需要實例化物件，實例化物件時常放了很多測試替身(Test-double)進去，讓測試更困難
• 類別的靜態變數有時牽涉到單例(Singleton)設計模式，要一起實例化，讓測試更麻煩
• 實例化很困難意味著難以測試
• 超文本文件類別為例，文件只在乎客戶端產生的文件，不需要瞭解客戶端如何產生文件
• 車類別為例，車只在乎產生的引擎，不需要了解引擎怎麼產生

服務定位器模式(Service Locator pattern)的問題：

• 違反得墨忒耳定律(Law of Demeter a.k.a. LoD，簡單說即只拿直接需要的物件)
• 將服務定位器傳給要實例化的物件，看建構子參數不夠，還得追建構子程式碼才知道相依的物件，這會隱藏物件間真正的相依性
• 以房子類別為例，實例化房子卻傳入整個家的狀態，追建構子才知只要門、窗與屋頂
• 給房子還要給整個家的物件，導致物件重用性變差
• 解決方式是不透過定位器，明確將門、窗與屋頂作為參數傳給房子
• 此舉能讓獨立測試變得容易
• 服務定位器把查詢與建立物件的功能混淆
• 還需要額外的介面、覆寫或仿造服務定位器的設定方法(setter)
• 以致一旦依賴服務定位器，也需要依賴其他跟服務定位器有關的東西
• 服務定位器有很多別名，本質上都是只需要部分物件但給了全世界

得墨忒耳定律：

• 以結帳為例，一般來說只會拿錢(直接需要的物件)給店員(請求物件的物件)，不會整個錢包(全域狀態)給店員
• 只請求直接需要的物件
• a.getX().getY()亦即間接取得物件即違反得墨忒耳定律
• 好萊塢法則(Hollywood principle, that is "Don't call us, we'll call you")

破解依賴注入的迷思

• 子物件新增一個參數，則父物件要一路傳遞參數直到給子物件
• 事實上父物件並不負責建構子物件，父物件並不知道子物件怎麼建構的，所以也沒有傳遞參數的問題
• 房子類別為例，房子並不知道門有門把，房子只需要建構好的門物件
• 工廠模式(Factory pattern)負責將物件組合起來，與業務邏輯分開
• 同一個生命週期的類別們只要同一個工廠組合就夠，並不用一個類別一間工廠，所以不會導致類別倍數增生
• 注入的物件生命週期應該大於等於被注入的物件，如果有生命週期較短的物件，應該調整架構，將短生命週期的物件分群

偏執狂程式設計(Paranoid programming/coding)

• 到處是空指標檢查讓測試變得困難
• 測試房子的油漆功能不需要門，傳入門的空指標，但門的空指標檢查讓測試無法繼續
• 與其到處用先決條件檢查，不如用許多測試確保程式能跑
• 如果物件是給外部使用的應用程式介面(API)，加入先決條件檢查是合理的
• 但若給內部使用，一堆先決條件檢查表示對程式的穩定性沒有信心
• 產品程式碼不應該傳空指標給物件，應該用空集合代替，若希望傳入的集合做事就實作方法，不然就給無操作(NOP a.k.a. NOOP)
• 測試程式碼可以傳空指標給物件，目的在表明此物件與測試無關
• 產品程式碼不應該在工廠類別外的類別呼叫new運算元，即業務與建構邏輯混淆
• 測試程式碼為了實例化小部分的程式做測試可以呼叫new運算元

總結

• 絕大部分的情況應該避免呼叫new運算元實例化物件，除了最基底的類別或物件圖的葉類別，其餘有與其他類別互動的類別，應該請求物件
• 將業務類別與建構類別分開，測試會變得容易，因為可以將業務邏輯與建構邏輯分別獨立測試
• 若將業務與建構邏輯混淆，測試建構邏輯時還不得不跑業務邏輯做的事

Q&A

• 問：是否建議不需要假(dummy)物件？
• 答：否，當測試的時候，無關的物件可以傳空物件進行無操作(NOP)，空物件是假物件更強的表現形式