favoring composition over inheritance and dependency injection

// demo of favoring composition over inheritance and construction with dependency injection

class Movement {

public void move();

};

class Wheel: Movement {};

class Turbine: Movement {};

class Control {

public void control();

};

class Handle: Control {};

class Dashboard: Control {};

class Handlebar: Control {};

class Vehicle {

Movement movement;

Control controll;

Vehicle(Movement m, Control c) {

this.movement = m;

this.control = c;

}

};

class Car: Vehicle {};

class MotorBike: Vehicle {};

class Jet: Vehicle {};

int main () {

Vehicle vehicles[] = {

new Jet (new Turbine(), new Dashboard()), 

new Car (new Wheel(), new Handle()), 

new MotorBike(new Wheel(), new Handlebar())

};

for (v: vehicles) {

v->move();

}

return 0

}

[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;
}