[ECE361] Lab 01 - Socket Programming

So basically, today was a day I started programming in Java seriously.

I tried programming in Java but it was so different from C and C++ or any other languages I know that I just forgot about it.
I find the language very wordy for what it does (like how I need to first write the main function inside class function while "void"-ing the main!!!) Since I was always told not to use void main() in C, it just appeared awkward to me at first.

Anyways, without much difficulties, my partner and I were able to finish the lab within 2 hours where 1 hour was allocated for the TA in teaching us the language.

Then in the next 20 minutes, we were able to complete the optional "thread" lab.

The purpose of the lab was to create us a client-server architecture on the same machine.
Then after this step, we were to create a chatting program where there were no real distinctions between the client and the server except the server was listening to establish connection at first.

The IDE we used was eclipse.
With the functionality of auto-completion of words, programming in Java was so easy. (Ctrl + Space)
Moreover, eclipse has helped me add libraries whenever I tried to use a built-in function like InputStreamReader.

However, there is a question I need answering to:
Q: What does the class WriteThreadClass implements Runnable mean?

Download: (University of Toronto (U of T) ECE361 Lab 1)
lab01.zip

[Project Euler] Problem 16 in C

Problem: Project Euler Problem 16

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2¹⁰⁰⁰?

About the Problem
This problem just involves dealing with large numbers without losing precision.

Solving the Problem
This problem was not particularly hard since we have dealt with large numbers before (such as adding) like in  Problem 13.

I have just created a function where it takes two strings of numbers and multiply them to output/return a value   by reference.
void multiplyTwoNumbers(char *prod, char *num1, char *num2, int numDigits);

prod represents the result of multiplication between num1 and num2.
numDigits represent the number of digits I want to see.

Code:

#include <stdio.h>
#include <stdlib.h>

#define NUM_DIGITS 1000
#define EXPONENT 1000

int main()
{
    char *prod = (char*)malloc(sizeof(char)*NUM_DIGITS+1);
    int i;
    for (i = 0; i < NUM_DIGITS; i++)
        prod[i] = '0';
    prod[NUM_DIGITS] = '\0';

    prod[0] = '1';

    for (i = 0; i < EXPONENT; i++){
        multiplyTwoNumbers(prod, prod, "2", NUM_DIGITS);
    }

    int sum = 0;
    for (i = 0; i < NUM_DIGITS; i++){
        sum += (prod[i] - '0');
    }

    free(prod);
    printf("%d\n", sum);
    return 0;
}

void multiplyTwoNumbers(char *prod, char *num1, char *num2, int numDigits){
    int i = 0, temp;
    int m, carry = 0;

    while (i < numDigits){
        temp = carry + (num1[i] - '0') * (num2[0] - '0');
        m = temp % 10;
        carry = (int) temp / 10;
        prod[i] = m + '0';
        i++;
    }

}

Challenges Faced (Logic behind Code)
Unlike the code found in my Problem 13 solution, I have reversed the order of the numbers. This means ones digit is in char[0], tens digit is in char[1]. So, instead of writing a hundred twenty(120), the code would write (021).
I have done this because I would not need to know the length of the number in order to perform a multiplication of 2. Therefore, the code would not go through the same array twice, improving the performance.

Lastly, the only the sum of digits, which has associative property, was needed, so the ordering did not matter.

Next Step
N/A

Questions
N/A

__________________________________________________________________
Best Execution Time: 0.016s
Answer:

1366

[Project Euler] Problem 15 in C

Problem: Project Euler Problem 15

Starting in the top left corner of a 22 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 2020 grid?

About the Problem
This is a problem where it asks us to create Pascal's Triangle (Please click on the link for more details) and add them all together to converge at one point.
So, I have created a Pascal's Triangle into one array of integers and added them all up to arrive at my answer.

Solving the Problem
Since I am only looking for the 20th level of the Pascal's Triangle, I could have used binomial theorem to arrive at 20th level of the Pascal's Triangle.
However, I have refrained myself from solving the problem in using binomial theorem because it felt slower to me since I need to calculate factorials of numbers up to 20. If I were to use this method for numbers over 100, I would need a much larger data (more than uint64 datatype probably) for accurately calculating the factorials.
Therefore, I had to choose with conventional way of constructing a Pascal's Triangle: series of additions.

There were two things I kept in mind while coding:
1) Minimal memory
        As a challenge to myself, instead of creating two dimensional array to store all the pascal's triangle values, I have limited myself into using only one array to sequentially go through each level of the triangle. In reality, the cost of writing the complex code outweighs the cost of memory but this is just for fun and practice :)

2) Modularity
        In case, I need to use Pascal's triangle in the future, I have tried to write the code in a clear manner as possible.      

I believe I have achieved these.
Code:

#include <stdio.h>
#include <stdlib.h>


    #define LEVEL 20
    int createPascalTriangle(int *pTriangle, int level);
    int increasePascalTriangleOneLevel(int *pTriangle);

    int main()
    {
        int *pTriangle = (int*)malloc(sizeof(int)*(LEVEL+1));
        int i;

        for (i = 0; i < LEVEL+1; i++)
            pTriangle[i] = 0;

        createPascalTriangle(pTriangle, LEVEL);

        long long int sum = 0;

        for(i = 0; i < LEVEL+1; i++)
            sum += (long long int) pTriangle[i] * pTriangle[i];

        free(pTriangle);
        printf("%lld\n", sum);

        return 0;
    }

    int createPascalTriangle(int *pTriangle, int level){
        if (level <= 0)
            return 0;
        pTriangle[0] = 1;
        pTriangle[1] = 1;
        int i;
        for ( i = 2; i <= level; i++)
            increasePascalTriangleOneLevel(pTriangle);

        return 1;
    }

    int increasePascalTriangleOneLevel(int *pTriangle){
        int i = 1, c;
        int temp[2] = {0};

        temp[0] = pTriangle[0];
        while (pTriangle[i] != 0){
            temp[i % 2] = pTriangle[i];
            pTriangle[i] = temp[i % 2 ? 0 : 1] + pTriangle[i];
            i++;
        }
        pTriangle[i] = 1;

        return 1;
    }

Challenges Faced (Logic behind Code)
The biggest challenge was figuring out a general pattern for adding the numbers using only one array.
So, the function that was hardest for me to write was increasePascalTriangleOneLevel(). The purpose of the function was to take an array of integers and add adjacent elements to place it in its respectable positions of the array. I found this particular hard because I needed to store its original elements without creating another array with the same size.

Naturally, in our mind, we would think
pTriangle[1] = pTriangle[0] + pTriangle[1]
pTriangle[2] = pTriangle[1] + pTriangle[2]
...
pTriangle[n] = pTriangle[n-1] + pTriangle[n+1]

However, this is exactly the problem I was discussing about.
Here is the picture to show the problem

Iteration 0	1	3	3	1	0
Iteration 1	1	4	3	1	0
Iteration 2	1	4	7	1	0
Iteration 3	1	4	7	8	0
Iteration 4	1	4	7	8	1

You can see from iteration 2, due to lack of storing the original elements, it has given us completely wrong answers.

To prevent this from happening again, I needed to find a generalized way of adding for next level of Pascal's Triangle. Here it is:
temp[0] = pTriangle[0];  //exception of pattern at the start
temp[1] = pTriangle[1];
pTriangle[1] = temp[0] + pTriangle[1];
temp[0] = pTriangle[2];
pTriangle[2] = temp[1] + pTriangle[2];
temp[1] = pTriangle[3];
pTriangle[3] = temp[0] + pTriangle[3];
...
temp[n % 2] = pTriangle[n];
pTriangle[n] = temp[opposite value of n % 2] + pTriangle[n];
Note: opposite value of n % 2 means when n % 2 = 0, the result would be 1 or when n % 2 = 1, the result would be 0.

Therefore, putting all this together, I arrived at increasePascalTriangleOneLevel(); function without a problem!

By using this method, creating a 20 level pascal's triangle only resulted in 0.007s!
However, I was reminded that we have yet to add all the elements of the Pascal's Triangle to arrive at a true answer. This was easy.
All we needed to do was square each element and add them all together.

Another problem I came along, I needed to ask on stackoverflow.
I had forgotten initialize the last element of the array 0 so the code traversed outside the array giving me a hard time.
I will probably never make the same mistake again since it bothered the heck out of me all day!

Next Step
N/A

Questions
N/A

__________________________________________________________________
Best Execution Time: 0.007s
Answer:

137846528820

[Project Euler] Problem 14 in C

Problem: Project Euler Problem 14

The following iterative sequence is defined for the set of positive integers:

n  n/2 (n is even)
n  3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13  40  20  10  5  16  8  4  2  1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. 

Which starting number, under one million, produces the longest chain? 

NOTE: Once the chain starts the terms are allowed to go above one million.

About the Problem
The problem asks us to find the number which produces the longest chain.
From reading upon Collatz conjecture, no matter what the starting positive number is, the final result will always be 1.
This astonished me because despite the function based up on conditional statements, the function converges onto one point.

Solving the Problem
I remember solving a similar problem on uVa.
So, I had to dig through project after project related to uVa to find the code I want.
I finally found what I want and all I needed to do was tweak the main() function to make it work.

Naturally for this problem, I had used a recursive function to count the number of iterations the code had to take in order to reach 1 and I had used brute force method to solve this problem, which has greatly hindered the performance (reaching almost 1.2 seconds!)

You'll know what I mean when you view my code.
Code:

#include <stdio.h>
#include <stdlib.h>

unsigned long int countIterations(unsigned long int number){
    if (number == 1) return 1;
    if (number % 2 == 0){
        return 1 + countIterations(number / 2);
    } else {
        return 1 + countIterations(number * 3 + 1);
    }
}

int main()
{
    unsigned long int maxIter = 0, maxNum;
    unsigned long int i, n;
    for (i = 1; i < 1000000; i++){
        if (maxIter < (n = countIterations(i))){
            maxIter = n;
            maxNum = i;
        }
    }

    printf("%lu\n", maxNum);

    return 0;
}

Challenges Faced/ Lessons Learned
It was definitely like uVa problems revisited and I learned that keeping good documentation of all the codes you have created is a good idea, considering it took me nearly 10 minutes to find the small piece of code.
It would have been easier for me to just write the code from scratch!

Next Step

• To increase the performance of the code, I can use the optimization process called memoization. This method is possible because there is only one flow of the series. I mean if we see the same integer we have calculated before during the series, if we store the number of steps taken before, we can easily just add to the number of steps taken up until the familiar integer is shown.

Questions
N/A

__________________________________________________________________
Best Execution Time: 1.169s
Answer:

837799

[Project Euler] Problem 13 in C

Problem: Project Euler Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

About the Problem
The problem asks us to find the first ten digits of a sum of large numbers.
For a moment, I thought the question was too easy to be #13 of Project Euler but I was wrong since I was solving in C.
Since it seems project euler likes to deal with large numbers, I decided to just create a user-friendly function for adding string consisting of only numbers together for future uses.

Solving the Problem
After I have solved the problem, I quickly looked through the answer forum that is only accessible to the ones who have solved the problem. I was flabbergasted by BigInteger library that was available to a lot of languages except for C!
They had literally used only one line to solve the problem which made me a sad panda.

Anyways, I have solved this problem by first assigning the numbers to an array of strings.
Then I have added the strings altogether by adding the strings two at a time.
When I mean adding the strings together, I mean traversing through the string to add digit by digit by first transforming the digit character to an integer to use the + operator.

At first, I was thinking of adding ten large strings at a time because this way, I do not have to worry about two carrys since the maximum value we can get from adding 10 ones digit is 9 * 10 = 90 (where 9 is the carry and 0 is the sum).

However, I became lazy and decided to just add two strings at a time.

Therefore, I have created a function, addTwoNumbers, where it takes two strings of numbers and return the addition result. Although there are limitations of this function as I have quickly put them together, such as fixed length of addition result and requirement that num1 is longer in length than num2, the function works as intended.

After devising this function, the answer was easy to get.
All I needed to do was call this function in a loop to traverse through the entire array of strings I have parsed in the beginning of the program.

Without further ado, here is the code
Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int parseFileIntoStringArray(char *str, char delimiter);
const char* addTwoNumbers(char *num1, char *num2);

char s[100][51] = {'\0'};

int main()
{
    FILE *fp;
    char *sum = (char*)malloc(sizeof(char)*55);
    int k;
    for (k = 0 ; k < 55 ; k++){
        sum[k] = '0';
    }
    sum[54] = '\0';

    char filename[] = "C:\\Problem.txt";
    parseFileIntoStringArray(filename, '\n');
    //strcpy(sum, addTwoNumbers(s[0], s[1]));
    //printf("length of sum: %d\n", strlen(sum));
    int i;

    for (i = 0; i < 100; i++){
        strcpy(sum, addTwoNumbers(sum, s[i]));
    }
    printf("%s\n", sum);

    return 0;
}

const char* addTwoNumbers(char *num1, char *num2){
    char sum[55];
    int k;
    for (k = 0 ; k < 55 ; k++){
        sum[k] = '0';
    }
    sum[54] = '\0';

    int i = strlen(num1) - 2, j = strlen(num2) - 1;
    int carry = 0, digitSum, counter = 54;
    const int offset = '0';

    for (i;i>=0;i--,j--,counter--){
        digitSum = carry + num1[i] - '0';
        if (j >= 0)
            digitSum += num2[j]-'0';
        carry = digitSum / 10;
        digitSum %= 10;
        sum[counter] = digitSum + '0';
    }

    return sum;
}

int parseFileIntoStringArray(char *str, char delimiter){
    FILE *fp;
    char c;
    int i = 0, j = 0;

    fp = fopen(str, "r");
    if (fp == NULL)
        return 0;

    while ((c = fgetc(fp)) != EOF){
        if (c == delimiter){
            i++;
            j = 0;
            continue;
        }
        s[i][j++] = (char) c;
    }

    fclose(fp);
    return 1;
}

Challenges Faced/ Lessons Learned
It has been a long time since I have dealt with C strings or in fact, any strings! So, I had to review on some of the concepts behind string pointers and char array for proper string manipulation.

Here are couple of things that have hindered me from arriving at the answer earlier!

• Returning string from a function and assigning it to another variable
• Initializing values for a string after declaration
• Assigning to a variable from an input file line by line at a time

Although I knew why the code was not working, I spent most of my time trying to find shortcuts in achieving the same results.

Next Step

• Improve addTwoNumbers for more flexibility, such as non-fixed sized string addition, returning value by reference
• Allow addition of 10 big integers at a time

Questions
I still have some questions left risen from solving this problem:

• How can I easily initialize values for a string after declaring an array of characters? (Right now, I have a loop traversing through the array to assign a value to each element at a time)
• Is there a safe, stable way of assigning line by line from an input file to a variable?

__________________________________________________________________
Best Execution Time: 0.010s
Answer:

5537376230

[Project Euler] Problem 12 in C

Problem: Project Euler Problem 12

So, this problem asked us to find the first triangular number that has over 500 divisors.
When I was solving this, I totally forgot about the triangular part so I tried to find the first instance of number that had over 500 divisors. (It was 14414400)

When I ran that code, it took almost 2 minutes to arrive at an answer! Other than that, the answer was wrong too! (duh..)

After carefully reading the problem again, I fixed "n++" to "n += i++" to only check for triangular numbers.
The problem was solved using Trial Division method.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    long int n = 0;
    long int i = 1;
    while (findNumberOfDivisors(n) < 500){
        n += i++; //Used n++ when I understood the problem wrong.
    }
    printf("%ld\n", n);

    return 0;
}

int findNumberOfDivisors(long n){
    int number = 2;
    int squareRoot = (int) sqrt(n);
    long int i;
    for (i = 2; i <= squareRoot; i++){
        if (n % i == 0){
            number += 2;
        }
    }

    if (squareRoot * squareRoot == n)
        number--;

    return number;
}

Best Execution Time: 0.205s
Answer:

76576500

[Project Euler] Problem 11 in C

Problem: Project Euler Problem 11

This problem was very similar to problem 8 of Project Euler.
I used the same concept proposed in optimizing the code (click this)

Optimizations
Skipping product upon seeing certain "low" digit values.
        Upon inspection of product of randomly chosen 4 numbers, which in my case was (78*78*96*83) resulting in a product of 48477312, we can arrive at a conclusion of ignoring any product containing numbers less than or equal to 49.
        This is because the highest possible product with only 3 digits is 99 * 99 * 99 = 970299. So, simply dividing 48477312/970299 = 49.96... So, even in the best case scenario with the number 49, we cannot exceed the arbitrarily found product. Therefore, we don't even need to compute for products with number less than or equal to 49.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int arr[20][20]=
    {
{ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
{52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
{24, 47, 32, 60, 99,  3, 45,  2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
{67, 26, 20, 68,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
{24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
{16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
{86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
{ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
{20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48},
    };
    int i, j, k, tmp;
    //1 = left-down, 2 = down, 3 = right-down, 4 = right
    long long int prod1, prod2, prod3, prod4, greatestProd = 0;
    for (i = 0; i < 20; i++){
        for (j = 0; j < 20; j++){
            prod1 = 1, prod2 = 1, prod3 = 1, prod4 = 1;
            for (k = 0; k < 4; k++){
                //left-down
                tmp = arr[i+k][j-k];
                if (tmp >= 50 && j >= 3 && i <= 16)
                    prod1 *= tmp;
                else
                    prod1 = 0;

                //down
                tmp = arr[i+k][j];
                if (tmp >= 50 && i <= 16)
                    prod2 *= tmp;
                else
                    prod2 = 0;

                //right-down
                tmp = arr[i+k][j+k];
                if (tmp >= 50 && i <= 16 && j <= 16)
                    prod3 *= tmp;
                else
                    prod3 = 0;

                //right
                tmp = arr[i][j+k];
                if (tmp >= 50 && j <= 16)
                    prod4 *= tmp;
                else
                    prod4 = 0;
            }

            if (prod1 > greatestProd)
                greatestProd = prod1;
            if (prod2 > greatestProd)
                greatestProd = prod2;
            if (prod3 > greatestProd)
                greatestProd = prod3;
            if (prod4 > greatestProd)
                greatestProd = prod4;
        }
    }
    printf("%lld\n", greatestProd);

    return 0;
}

Best Execution Time: 0.006s
Answer:

70600674