Tuesday, December 30, 2014

LeetCode 59 Spiral Matrix

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].


Solution

Code first:

vector<int> spiralOrder(vector<vector<int> > &matrix) {
    vector<int> result;
    if (matrix.size() < 1) 
        return result;
    int top = 0;
    int button = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while (top <= button && left <= right) {
        for (int x = left; x <= right; x++) { //left to right
            result.push_back(matrix[top][x]);
        }
        top++;

        for (int y = top; y <= button; y++) { //top to button
            result.push_back(matrix[y][right]);
        }
        right--;
        if (button >= top) { // check if the button line haven't been pushed
            for (int x = right; x >= left; x--) {
                result.push_back(matrix[button][x]);
            }
            button--;
        }

        if (right >= left) { //check if the left line haven't been pushed
            for (int y = button; y >= top; y--) {
                result.push_back(matrix[y][left]);
            }
            left++;
        }

    }
    return result;
}

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations. In fact, when I implement this, I debugged almost one hour and than find this.


Written with StackEdit.

LeetCode Rotated Sorted Array Problems

There are 4 problems about rotated sorted array, the sorted array is like [0 , 1, 2, 3, 4, 5], and the rotated sorted array is separating the sorted array to two parts and exchange the position of them. So one rotated array of above is [3, 4, 5, 0, 1, 2]. The fist two problems is Search in Rotated Sorted Array and Search in Rotated Sorted Array II. The difference is the first one's array have no duplicate and the second one may have duplicated elements. The method to solve the two question is the same. Here is the code for first question:

int search(int A[], int n, int target) {
    int lo = 0;
    int hi = n - 1;
    int mid;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (target == A[mid]) {
            return mid;
        }
        if (A[lo] < A[mid]) {// target in left part, when no duplicate, change "<" to "<=".
            if (A[lo] <= target && target <= A[mid]) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        else if (A[lo] > A[mid]) { //target in right part. when no duplicate, change to else here.
            if (A[mid] <= target && target <= A[hi]) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        else { // handle duplicated cases
            lo++;
        }
    }
    return -1;
}

In fact, the code above also could handle the cases contain duplicated elements. When there are duplicated elements, we do know target in which part, so just let "lo" increase by one. If there have no duplicates, the time complexity is O(logn), just like binary search for a sorted array. if there are duplicated cases, the worst time complexity is O(n) for a array like [3, 3, 3, 3, 1, 3, 3].

The other two problem is Find Minimum in Rotated Sorted Array and Find Minimum in Rotated Sorted Array II. These two questions also could use binary search to solve, and just like the above two problems, the difference is whether there are duplicated elements. Here is the code:

int findMin(vector<int> &num) {
    int lo = 0;
    int hi = num.size() - 1;
    int mid = 0;

    while(lo < hi) {
        mid = lo + (hi - lo) / 2;

        if (num[mid] > num[hi]) { //minimum in right side
            lo = mid + 1;
        }
        else if (num[mid] < num[hi]) { //mininum in left side
            hi = mid;
        }
        else { // when num[mid] and num[hi] are same
            hi--;
        }
    }
    return num[lo];
}

Just as first two questions, this could handle the duplicated elements. This part of problems compare middle elements with "hi" elements, we also could compare middle and "lo" elements.

Written with StackEdit.

LeetCode 172 Factorial Trailing Zeroes

Problem

Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in logarithmic time complexity.

This is a newly added problem in LeetCode, just yesterday. As a Chinese, I firstly searched what is "Trailing Zeros". OK, it's just the zeros at the end of a decimal number.
Before a depth thinking, I have known that the number of trailing zeros have a close relationship with the number of "5". So I wrote a small python script to try factorials below 10!. Here is the result:
1  1
2  2
3  6
4  24
5  120
6  720
7  5040
8  40320
9  362880
10 3628800

Looks like the number of trailing zeros is associated with the number of numbers could be divided by 5, so I wrote answer:
int trailingZeroes(int n) { return n / 5; }
While, it's still hard to me to get the right answer just one submit. When the input is 30, the right answer is 7 but my answer is 6. OK, I printed out all the factorials less than 28, something aren't went well after 25:
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000

After multiplied by 25, there increased 2 zeros. 25 is the square of 5, so it multiplied two 5 to 24!, so it added 2 zeros. Same thing, 125 means there are three 5 multiplied to last number, added 3 zeros. Looks like for factorial, the result is,
return n / 5 + n / 25 + n / 125 + n / 625 + n / 3125;

This could pass the test in LeetCode, but if n is too large, this is not a universal result. The best is
int trailingZeroes(int n) {
    int c = 0;
    while (n >= 5) {
        n /= 5;
        c += n;
    }
    return c;
}


By the way, StackEdit is a great!!!
Written with StackEdit.

Thursday, November 6, 2014

The Easiest Way to Upgrade GCC compiler in Windows Eclipse CDT

Because window have no Linux like package management tool for now, when we want to upgrade some development tools, we have to find windows installer or compile by ourselves and set the right thing into PATH.
 Recently, I want to use the <regex> in C++ for G++ in eclipse. This is a C++11 new feature and just successfully implemented in gcc compiler. GCC version 4.8 although it contains <regex>, but the functions haven't implemented.
I've tried window installer from MinGW official site, but looks like it doesn't update PATH for me. Eventually, I find a website that contains a Windows installer could set the right PATH and easy to setup in eclipse.

Step 1

Go to this address, scroll down the page, download gcc-4.9.4-32.exe or gcc-4.9.4-64.exe depending on your system version.


Step 2

Click the downloaded file, wait extracting finish. Then click accept, set the install address to c:\MinGW.
Then click install to install gcc 4.9.1. You can check if the installation is correct by open Command Prompt and type
gcc -v
Then it should tells you the version of your gcc is 4.9.1.


Step 3

If you haven't download eclipse CDT, download it here.
Open Eclipse, Window -> Preference -> C++ -> New C++ Project Wizard -> Preferred Toolchains tab. For every project type under Executable, set Toolchains to MinGW GCC. Click OK to finish



Now, our  eclipse C++ projects could use <regex>!

Sunday, November 2, 2014

Using Python and sklearn Package Build Decision Tree


This is still the homework of Machine Learning class.
The data is come from one of UCI repository. It's a data set about whether consumer want to buy certain types of cars. All the data is discrete so it's appreciate to using a decision tree to classify them. 
I use sklearn package to build tree and use matplotlib to plot statistic graph of results. After the training, the tree being stored using graphviz format. We can using graphviz's client to save the graph as png or other picture formats. 
Looks like that sklearn is the most famous and powerful Machine Learning package in python and not like some other packages, it is still under maintains and adding new functions. Even some very famous internet service are using it(honestly I just know Spotify and Evernote). The document of it is pretty understandable for me and the examples are ample enough. 
My code trained different decision trees with different depth using same data set, and compare the training error and test error. Here is the result document of decision tree in sklearn. 

Here is the code(Python 3.3):

from sklearn import tree
import numpy as np
from matplotlib import pyplot

# read lines in file to data
with  open("car.data.txt", mode='r') as f: 
    data = f.read().splitlines()
    
data_table = []
for line in data:
    data_table.append(line.split(','))  # separate each words by comma
data_table = np.asarray(data_table)  # change the type of data to nparray

X = [row[0:6] for row in data_table]  # first 7 columns are features
Y = [row[-1] for row in data_table]  # the last column is the clacification

# Decision tree classifier could only classify the tree represented by numbers
convert_dict = {'vhigh':3, 'high':2, 'med':1, 'low':0,
                '2':2, '3':3, '4':4, '5more':5,
                'more':5,
                'small':0, 'big':2}
for row_num in range(len(X)):
    for col_num in range(len(X[row_num])):
        X[row_num][col_num] = convert_dict[X[row_num][col_num]]
        
# except 'unacc', all other 
for i in range(len(Y)):
    if Y[i] != 'unacc':
        Y[i] = 1
    else:
        Y[i] = 0
              
# using the first half data to train the tree and the last part to test the tree
X_train = X[:len(X) // 2]
X_test = X[(len(X) // 2):]

Y_train = Y[:(len(Y) // 2)]
Y_test = Y[(len(Y) // 2):]

 
# using 'entropy' as the classification criterion
clf = tree.DecisionTreeClassifier(criterion='entropy')
clf = clf.fit(X_train, Y_train)

# save the tree to graph using graphviz format 
# and we can using graphviz client to see and save the graph to png
with open("hw2_option2_original.dot", 'w') as result_file:
    result_file = tree.export_graphviz(clf, out_file=result_file)
    
# count how many results computed by three fit to the real result
def compute_fit_number(X_train, Y_test, clf):
    Y_pred = clf.predict(X_train)
    fit_num = 0
    for y_t, y_p in zip(Y_test, Y_pred):
        if y_t == y_p:
            fit_num += 1
    return fit_num

# show how testing error and training error varied according to the increase of the depth.
def test_depth(max_depth, X_train, X_test, Y_train, Y_test):
    testing_errors = []
    training_errors = []
    depths = []
    for depth in range(2, max_depth + 1):
        depths.append(depth)
        clf = tree.DecisionTreeClassifier(criterion='entropy', max_depth=depth)
        clf.fit(X_train, Y_train)
        testing_errors.append(compute_fit_number(X_test, Y_test, clf) / len(Y_test))
        training_errors.append(compute_fit_number(X_train, Y_test, clf) / len(Y_train))
        
    pyplot.plot(depths, testing_errors, '-r', label="testing error")
    pyplot.plot(depths, training_errors, '-g', label='training error')
    pyplot.legend()
    pyplot.xlabel('depth')
    pyplot.ylabel('error')
    pyplot.title('error variation with the increase of depth')
    pyplot.show()

# test_depth(20, X_test, X_train, Y_train, Y_test)
    
Y_predict = clf.predict(X_test)
fit_number = 0
for y_t, y_p in zip(Y_test, Y_predict):
    if y_t == y_p:
        fit_number += 1
  
print(clf)
print('testing error is: ', fit_number / len(Y_test))
print("atrribute number", len(X_test[0]))
  
Y_predict = clf.predict(X_train)
fit_number = 0
for y_t, y_p in zip(Y_test, Y_predict):
    if y_t == y_p:
        fit_number += 1
print('training error is: ', fit_number / len(Y_test))


Here is the graph show errors of different trees with different depth of the tree.

errors vs depth of the tree




Thursday, October 30, 2014

Using neurolab in Python to train a multi-layer neural network

Recently, I'm learning machine learning in my university. Our teacher didn't limit us using specific programming language to solve the problem, so I choose to using Python my most familiar one.
Write the code of neural network from scratch is not so easy for me now(teacher, please forgive me), so I searched on the internet to find a easy to use package.
In machine learning area, the most famous and full functioned package is sklearn. I did my regression tree homework using this. But sklearn only have Bernoulli Restricted Boltzmann Machine. I don't know what's this and apparently this neural network aren't fit the requirement of my machine learning homework.
There is a problem on neurolab package. The document of it wasn't easy to understand. Looks like this package was developed by a Russian and his/her English is not as good as me, by the way, I'm a Chinese.
Before I use it, I devoted a lot of time to read the document and examples. This is not because this package has a bad design, but the way to explain how to use it. Anyway, I finally figured it out and finished my homework.

OK, here is the description of homework:

A NN has Input and output as following:
       Input Output
10000000 10000000
01000000 01000000
00100000 00100000
00010000 00010000
00001000 00001000
00000010 00000010
00000001 00000001
Design a one-hidden layer NN with 2, 3, 4 hidden nodes
respectively. Use programming language(matlab, R, etc) to
implement backpropagation algorithm to update the weight.
1). Show the hidden nodes value for different design. (10 points)
2). Compare the sum of squared error for different design. (10
points)
3). Plot the trajectory of sum of squared error for each output
unit for different design. (10 points)
Here is the code, I think I've build commended enough to let others understand my code
import neurolab as nl
import numpy as np  
import pylab as pl

def NN_for_234_hidden_node():
    '''
    Train a neural net work for one hiden layer and 2, 3, 4 hidden nodes, 
    then plot and compare sum of squared error for different design 
    '''
 
    inputs = np.eye(8) # Create the input and target 
    inp = inputs[2] # input used to test the neural network
    inp = inp.reshape(1,8) # transform inp from one row to 8 row 1 column
    inputs = np.delete(inputs , 5, 0) # delete 0000 0100
    print(inputs)
    error = [] 
 # node_number denote the number of nodes in hiden layer.
    for node_number in range(2, 4 + 1):
        # [[0, 1]] * 8 denote that there EIGHT input nodes and the range of each input is from 0 to 1
        # [node_number, 7] denote that the hidden layer contains "node_number" neurons and have 8 out put.
  # transf=[nl.trans.LogSig()] * 2 shows that using Log Signoid function in nodes. 
        net = nl.net.newff([[0, 1]] * 8, [node_number, 8], transf=[nl.trans.LogSig()] * 2)  # @UndefinedVariable
        # net = nl.net.newff([[0, 1]] * 8, [node_number, 8])  # @UndefinedVariable
  # using Resilient Backpropagation to train the network. 
  # This is the best way to train in this example in all provided Backpropagation algorithm
        net.trainf = nl.train.train_rprop  # @UndefinedVariable
        # default transfer function for newff is tan sigmoid 
        
        # net = nl.net.newp([[0, 1]]*8, 2)  # @UndefinedVariable
        
  # train network and generate errors. the default method to generate error is Sum of Squared Error 
        error.append(net.train(inputs, inputs, show=0, epochs = 3000))  # @UndefinedVariable
        print("The input array is: ", inp)
        out = net.sim(inp) # compute output for input "inp"
        print(out)
  
  # this small block of code used to compare network result with expected result.
#         pl.plot(range(8), inp[0])    
#         pl.plot(range(8), out[0])    
#         pl.show()                    
#         print(out)                   
#         print(net.layers[0].np)      
        sigmoid = nl.trans.LogSig();  # @UndefinedVariable
         
  # compute the value of nodes in each hidden layer
        for inputs_idx in range(len(inputs)):
            result = []
            for perce_idx in range(node_number):
                result.append(sigmoid((net.layers[0].np['w'][perce_idx] * inputs[inputs_idx]).sum() 
                                      + (net.layers[0].np['b'][perce_idx])))
            print("For the ", inputs_idx, " The value of each node is: ")
            print(result)
                
    # plot the error of 3 different network
    for i in range(len(error)):
        label_str = str(i + 2) + " nodes"
        # label_str = str(label_str)
        # print(str(label_str))
        pl.plot(range(len(error[i])), error[i], label=label_str)
    pl.legend()
    pl.xlabel("number of iteration")
    pl.ylabel("sum of squared error")
    pl.title("Sum of squared error for NN with different hidden nodes")
    pl.show()

NN_for_234_hidden_node()