Project Euler

Hi all, it's been a while since I've updated, since I've been quite busy. Anyway, I found out about Project Euler through Lifehacker, and it's really challenging and fun. Taken from Project Euler's About page:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

It's quite good for de-stressing and taking your mind off certain things. So far, I've managed to solve questions 1, 2, 4, 5, 6 and 9. I'm using Java to solve them, and you're definitely free to use whatever you like. Let's take a look at the problems and solutions:

Project Euler Question 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

public class Question1 {
    public static void main(String[] args) {
        int belowNum = 1000;
        int total = 0;
  
        for (int i = 0; i < 1000; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
                total += i;
            }
        }
  
        System.out.println(total);
    }
}

Project Euler Question 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Solution:

public class Question2 {
    public static void main(String[] args) {
        int one = 1;
        int two = 2;
        int temp = 0;
        int total = 0;  
  
        while (two < 4000000) {
               if (two % 2 == 0)
                    total += two;
      
            temp = one + two;
            one = two;
            two = temp;              
        }
  
        System.out.println(total);
  
    }

}

Project Euler Question 4:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

public class Question4 {
    public static void main(String[] args) {
        int sum = 0;
        int result = 0;
  
        for (int i = 100; i <= 999; i++) {
            for (int j = 100; j <= 999; j++) {
                sum = i * j;
          
                if (isPalindrome(sum) && sum > result) {
                    result = sum;
                }
            }
        }
  
        System.out.println(result);
  
    }

    static boolean isPalindrome(int s) {
        String sum = Integer.toString(s);
        StringBuffer reverseString = new StringBuffer(sum);
        reverseString.reverse();
        String temp = reverseString.toString();
  
        if (sum.equals(temp)) {
            return true;
        }
        else {
            return false;
        }
    }
}

Project Euler Question 5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

public class Question5 {
    public static void main(String[] args) {
  
        // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
        // Elminating some numbers, example: 14 = 7 x 2, we can thus eliminate
        // both 7 and 2. We'll be left with:
        // 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
        // Something tell me I can eliminate 12 and 15 too, but I can't
        // really describe why, so we'll just leave it at that.
        // Start at 20 since. For a number to be divisible by 20, it has to be a multiple of
        // 20. Thus, we can increment by 20;
  
        int start = 20;
        boolean found = false;
  
        while (true && !found) {
            found = true; //assume it's found
      
            for (int i = 11; i <= 20; i++) {
                if (start % i != 0) {
                    found = false;
                    break;
                }
            }
      
            if (found) {
                System.out.println(start);
            }
      
            start += 20;
      
        }  
  
          
    }
}

Project Euler Question 6:

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution:

public class Question6 {
    public static void main(String[] args) {
        int sumOfSquare = 0;
        int sum = 0;
  
        for (int i = 1; i <= 100; i++) {
            sum += i;      
            sumOfSquare += (i*i);
        }
  
        System.out.println((sum*sum)-sumOfSquare);
    }
}

Project Euler Question 9:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

Solution:

public class Question9 {  
    public static void main(String[] args) {
  
        // a^2 + b^2 = c^2
        // a + b + c = 1000
        // Therefore, c = 1000 - a - b
        // a^2 + b^2 = (1000 - a - b)^2
        // Simplifying:
        // b = (500000 - 1000a) / (1000 - a)
        // Therefore, we got to find a values of a and b that satisfy the above.
        // Since total is 1000, a and b must also be less than 1000. Also (1000 - a),
        // Meaning, if a is 1000, there will be a divide-by-zero. Secondly,
        // 500000 - 1000a, thus I assume that a cannot exceed 500.
  
        int b = 0;
        int c = 0;
  
        for (int a = 1; a < 500; a++) {
            b = (500000 - 1000*a) / (1000 - a);
            c = 1000 - a - b;
                              
            if (a*a + b*b == c*c) {
                System.out.println("a: " + a);
                System.out.println("b: " + b);
                System.out.println("c: " + c);
                int product = a*b*c;
                System.out.println("Product: " + product);
                break;
            }
        } 
    }
}

Alright. That's about it. The cool thing about Project Euler is that for some of them, after solving the questions you get access to a PDF file that gives you ideas and MUCH more elegant solutions than what I've done. Also, you get to see the forums for that particular question, and some of the solutions are really, really elegant. It's just too bad that my understanding of Mathematics has yet to reach that level, but it's always good to have a goal =)! On another note, for those of you who are interested, but have no programming background, you may want to try out Small Basic (link to Lifehacker.com, again). Personally, I'd suggest starting out with Java, but well, it's always good to have choices!

Analyzing Problems *Properly*

I'm writing this as a summary of lessons learnt (through the hard way) since I started studying this year. Some of you might have figured out by now, I'm currently taking CS1102 (Data Structures & Algorithms). It's a pretty good module, and I really enjoy it. However, when it really mattered, I always seem to screw up. I had my Practical Examination yesterday, which consisted of 2 parts, one worth 30%, and the other worth 70%.

For the 30% part, we had the following (something similar, can't remember the exact thing):

Character Sequence:
AXXAIOUAAXXUOIAXAXIOUAAXXAIOU

Test Cases:

1. AXXAIOU


2. AIOUAAX


3. AAXXUOI


4. AXAIOUA


5. AAAXXXX

I can't remember the exact scenario, but basically the input consisted of the above character sequence, and the test cases. The test cases will always be in groups of 7 chracters. You are supposed to output the position of the sequence if found, which in the above case, you should output:

0, 22
3
7
14
Not found

Moreover, the question wants you to be able to query in less than O(n) time.

Explanation: AXXAIOU is found at position 0 and 22. AIOUAAX is found at position 3. AAXXUOI is found at position 7. AXAIOUA is found at position 14. Finally, AAAXXXX is not found in the sequence.

A	X	X	A	I	O	U	A	A	X	X	U	O	I	A	X	A	X	I	O	U	A	A	X	X	A	I	O	U
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28

Analysis: Based on the given example, I deduced that overlapping cases can occur, and that each sequence can occur more than once. So what did I do wrongly? I did not read the question thoroughly enough to know that only the query (test cases) needs to be less than O(n) time. I thought the entire program should not take O(n) time. So I proceeded to implement some methods using String, and still ended up with O(n) time. The truth is, since the character sequence portion does not have to be less than O(n) time, I can simply store it into a hash table as follows:

AXXAIOU
XXAIOUA
XAIOUAA

And so on. That is, I can simply substring(i, 7) as I iterate through the character sequence, and put it into a Hashtable, all the way till I hit length of sequence - 7, which would give me the last substring of:

AXXAIOU

Once everything is inserted into the Hashtable, querying/retrieving it is O(1) time. I have no idea why did I not read the question properly. Sigh. I'll probably still pass, but not get the full marks.

Next, we have the 70% part, which I came SO CLOSE to finishing it, I just UNDER-analyzed it. Basically, suppose you have the following:

    7
   / \
  5   4
 /   / \
6   1   3

You are then supposed to calculate the largest number based on the following:

n1 + (n2 - (n3 + (n4 - (n5 + n6)))...

Meaning, using the above example, there are 3 paths:

7 + (5 - 6) = 6
7 + (4 - 1) = 10
7 + (4 - 3) = 8

Thus, the longest path is 10 in this case. The input you are given is:

7 2 3
5 1 0
6 0 0
4 1 1
1 0 0
3 0 0

Which means, to the left of 7, there are 2 nodes, and to the right of 7, there are 3 nodes. To the left of 5, there is one node, and none to the right. 6 has no child nodes. 4 has one child each on the left and right. Both 1 and 3 have no child nodes. Basically, the first digit of each line is the actual node value, given in pre-order. The second digit means the number of left child nodes, and the third digit means the number of right child nodes. Thus, you have to build the tree out, and then find the longest path.

Analysis: Basically, this problem can be broken up into 2 parts, building the tree, and then finding the longest path. I was able to build the tree relatively quickly. What I did was to have something like the following:

void buildTree(ArrayList<TempNode> nodes) {
    root = buildTree(nodes, 0);
}
Node buildTree(ArrayList<TempNode> nodes, int curr) {
    Node temp = null;

    if (curr < nodes.size()) {

        temp = new Node(nodes.get(curr));
        if (nodes.get(curr).left != 0)
            temp.left = buildTree(nodes, curr+1);
        if (nodes.get(curr).right != 0)
            temp.right = buildTree(nodes, curr+1+nodes.get(curr).right);
        return node;
    }
}
class TempNode {
    protected int value, left, right;
    TempNode(int value, int left, int right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

What I did was to store each line of input into a TempNode object, and all of that is then stored into an ArrayList. The tree is then built recursively, and if you study the input (since it's pre-order), you will realise that the node to the right of the current node is always the position of the current pointer + the number of left nodes of the current node + 1. Take note that the above code might be missing a things because I don't exactly remember everything, but the general concept is that. Thus, I was able to build out the tree. Now comes the longest path part. I made use of a concept similar to finding the height of the tree, which is as follows:

int findHeightOfTree(Node node) {
    if (node == null)
        return 0;
    else {
        return 1 + Math.max(findHeightOfTree(node.left), findHeightOfTree(node.right));
}

What the code does is that, starting at the node you specify (the root node in this case), it will traverse left and right and return the maximum value at that point in time. Thus, if I were to change the code to the following:

int findMaxValue(Node node) {
    if (node == null)
        return 0;
    else {
        return node.value + Math.max(findMaxValue(node.left), findMaxValue(node.right));
}

I would be able to find the maximum value, PROVIDED all the values are added together. Meaning that the above tree would give:

7 + (5 + 6) = 18
7 + (4 + 1) = 12
7 + (4 + 3) = 14

Which is very similar to what the question wants. So I thought, now I just need to add in a boolean to alternate + and -. And the code became:

int findMaxValue(Node node, boolean plus) {
    if (node == null)
        return 0;
    else {
        if (plus)
            return node.value + Math.max(findMaxValue(node.left, !plus), findMaxValue(node.right, !plus));
        else
            return node.value - Math.max(findMaxValue(node.left, !plus), findMaxValue(node.right, !plus));
}

Sadly, it did not work as expected, and I had 30 minutes before the end of the practical. I finally figured out at the 29th minute what were the mistakes, but before I could magically try to code it in 1 min, I had to press some key wrongly in Vim that resulted in it being unable to respond to me (I'm quite new to Vim, and I still don't know what I pressed). Thus, I was REALLY close, but not close enough. Here is what I realised, but could not put into code:

Firstly, I had to return the maximum value at the node itself, which means I should have the following instead:

int findMaxValue(Node node, boolean plus) {
    if (node == null)
        return 0;
    else {
        if (plus)
            return Math.max(node.value + findMaxValue(node.left, !plus), node.value + findMaxValue(node.right, !plus));
        else
            return Math.max(node.value - findMaxValue(node.left, !plus), node.value - findMaxValue(node.right, !plus));
}

I managed to do this part, thankfully. Of course, the output was still wrong. So what did I missed out (which I realised LITERALLY at the last minute)? Look at the following:

    7
   / \
  5   4
 /   / \
6   1   3

Look at Node 5. I was doing a comparison between 5-6, and 5-0 (since 5 has no left child, the code will return 0). Of course, the code will return 5-0 as the maximum value, which is 5. That is what I missed out. I neglected the MINUS case, whereby if a node has either no right or left child, there should be no comparison taking place. For the case of plus, it is ok, because 5+6 is still more than 5+0. Alas, it was too late, and I could not complete what I SHOULD HAVE completed. Sadly =(. I haven't tried actually compiling or writing the whole thing out, but the final correct code should have been something like:

int findMaxValue(Node node, boolean plus) {
    if (node == null)
        return 0;
    else {
        if (plus)
            return Math.max(node.value + findMaxValue(node.left, !plus), node.value + findMaxValue(node.right, !plus));
        else
            if (node.left == null && node.right == null) {
                if (node.left == null) {
                    return node.value - findMaxValue(node.right);
                }
                else {
                    return node.value - findMaxValue(node.left);
                }
            }
            else {
                return Math.max(node.value - findMaxValue(node.left, !plus), node.value - findMaxValue(node.right, !plus));
            }
}

There you have it. I under-analyzed the problem, and neglected one case, and could not get the correct output. Sigh. To be honest, I'm still not quite over it, but I've learnt my lesson, and I think that is important in itself. I just don't understand, why, for 29 minutes, I thought of every possible scenario I could have gone wrong, but this. This simple case, of not taking care of a possible empty child node. Why =(?

Lesson Learnt: Analyze your problems properly. Use a highlighter if necessary. Sometimes luck REALLY isn't on your side. Sigh.

Building A Binary Tree (From Post/Pre-Order & In-Order Traversal)

As most of you know, it is possible to build a Binary Tree from either its post-order/pre-order traversal and its in-order traversal. For example, given the following:

Pre-Order: 1 2 4 5 8 9 3 6 0 7
In-Order: 4 2 8 5 9 1 6 0 3 7

You can re-construct the Binary Tree and get the following:

       1
   /       \
  2         3
 / \       / \
4   5     6   7
   / \     \
  8   9     0

Basically, the pre-order traversal will give you the order in which the nodes should be added, and the in-order traversal will give you the position. For example, using the pre-order example, we have "1". Since it's pre-order, which means that it's traversed in the order Root-Left-Right, "1" would be the root node since it appears first. Thus, we create "1" accordingly. Take note of the position of "1" in the in-order traversal. Next, we have "2" (pre-order), which means it's the next node to be created/inserted. Looking at the in-order traversal, we see that "2" is to the left of "1", and thus, "2" would be the left node of "1". We now look at "3" (pre-order), and see that it is to the right of "1" in in-order, and thus add "3" to the left of "1" accordingly.

We now look at "4" (pre-order), and see that it is to the left of "2" (in-order). Next up, is "5", which is to the right of "2". This goes on until the whole tree is created. I figured that since it is quite easy to figure out once you get the concept, why not put it into code? It can be seen that this can be coded recursively, and so I went ahead and implemented it in Java. However, I ran into some problems with the base case, and after doing some search online, I found http://www.dotnetjunkies.com/WebLog/debasish/archive/2006/05/31/139364.aspx, which gave me the solution to the base case I want. Ok, enough talking, and here's the code:

/*
 * Author: Soh Yuan Chin
 * Explanation:
 * Create a tree from its preorder/postorder and inorder
 * The first line of input will have 0 or 1. 0 = preorder. 1 = postorder.
 * Second line of input determines number of nodes.
 * Third line of input contains the pre/post order.
 * Fourth line of input contains the in order.
 *
 * Example Input:
 * 0
 * 10
 * 1 2 4 5 8 9 3 6 0 7
 * 4 2 8 5 9 1 6 0 3 7
 *
 */

import java.util.*;

public class BuildBinaryTree {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BinaryTree bt = new BinaryTree();

        int type = sc.nextInt();
        int numOfNodes = sc.nextInt();
        int[] preOrPost = new int[numOfNodes];
        int[] inOrder = new int[numOfNodes];

        for (int i = 0; i < numOfNodes; i++) {
            preOrPost[i] = sc.nextInt();
        }

        for (int i = 0; i < numOfNodes; i++) {
            inOrder[i] = sc.nextInt();
        }

        bt.buildTree(preOrPost, inOrder, type);
        bt.preOrder();
        bt.inOrder();
        bt.postOrder();
    }

}

class TreeNode {
    protected int number;
    protected TreeNode left;
    protected TreeNode right;

    TreeNode(int number) {
        this.number = number;
    }
}

class BinaryTree {

    private TreeNode root;
    private int size;

    BinaryTree() {
        root = null;
        size = 0;
    }

    // Building Tree    
    public void buildTree(int[] preOrPost, int[] inOrder, int type) {
        if (type == 0)
            root = buildPreOrderTree(preOrPost, inOrder, 0, 0, preOrPost.length);
        else if (type == 1) {
            // reverse the array. exchange the first and last.
            for (int left=0, right=preOrPost.length-1; left < right; left++, right--) {
                int temp = preOrPost[left];
                preOrPost[left] = preOrPost[right];
                preOrPost[right] = temp;
            }

            root = buildPostOrderTree(preOrPost, inOrder, 0, 0, preOrPost.length);
        }

    }

    private TreeNode buildPostOrderTree(int[] preOrPost, int[] inOrder, int curr, int start, int end) {
        TreeNode currNode = null;

        if (end-start == 1) {
            currNode = new TreeNode(inOrder[start]);
        }
        else {
            int k = 0;
            for (int i = start; i < end; i++) {
                if (preOrPost[curr] == inOrder[i]) {
                    k = i;
                    break;
                }
            }

            if (k > 0) {
                currNode = new TreeNode(inOrder[k]);
                currNode.right = buildPostOrderTree(preOrPost, inOrder, curr+1, k+1, end);
                currNode.left = buildPostOrderTree(preOrPost, inOrder, curr+(k-start), start, k);
            }
        }

        return currNode;
    }


    private TreeNode buildPreOrderTree(int[] preOrPost, int[] inOrder, int curr, int start, int end) {
        TreeNode currNode = null;

        if (end-start == 1) {
            currNode = new TreeNode(inOrder[start]);
        }
        else {
            int k = 0;
            for (int i = start; i < end; i++) {
                if (preOrPost[curr] == inOrder[i]) {
                    k = i;
                    break;
                }
            }

            if (k > 0) {
                currNode = new TreeNode(inOrder[k]);
                currNode.left = buildPreOrderTree(preOrPost, inOrder, curr+1, start, k);
                currNode.right = buildPreOrderTree(preOrPost, inOrder, curr+1+(k-start), k+1, end);
            }
        }

        return currNode;
    }

    // Traverse
    public void preOrder() {
        System.out.print("Pre-Order: ");
        preOrder(root);
        System.out.println();
    }

    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.number + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public void postOrder() {
        System.out.print("Post-Order: ");
        postOrder(root);
        System.out.println();
    }

    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.number + " ");
        }
    }

    public void inOrder() {
        System.out.print("In-Order: ");
        inOrder(root);
        System.out.println();
    }

    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.number + " ");
            inOrder(node.right);
        }
    }

    public void levelOrder() {
        System.out.print("Level-Order: ");
        levelOrder(root);
        System.out.println();
    }

    private void levelOrder(TreeNode node) {
        if (node != null) {
            Queue<TreeNode> tempQ = new LinkedList<TreeNode>();
            tempQ.offer(node);        
            TreeNode temp = null;

            while (!tempQ.isEmpty()) {
                temp = tempQ.poll();
                System.out.print(temp.number + " ");

                if (temp.left != null)
                    tempQ.offer(temp.left);
                if (temp.right != null)
                    tempQ.offer(temp.right);
            }
        }
    }
}

Take note that the above code is able to do both pre-order/post-order and in-order building of tree. Also, you should get an output of printing out the different traversals of the newly-built tree. You can enable level-order traversal by adding the method call to main(), the levelOrder() method has already been implemented. Lastly, I implemented post-order building of tree by reversing the array of elements first. If you do not want to do that, simply modify the values of curr, start, and end accordingly.

Below are 2 test cases you can try using. Simply save them as a text file, example "test.txt", and use input redirection "java BuildBinaryTree < test.txt".

Post-Order Test Case:

1
10
4 8 9 5 2 0 6 7 3 1
4 2 8 5 9 1 6 0 3 7

Pre-Order Test Case:

0
10
1 2 4 5 8 9 3 6 0 7
4 2 8 5 9 1 6 0 3 7

I hope this has been useful for some of you =)!