Collatz Graph: Code U session2

BinaryTreeNode.java

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by marcus on 4/12/15.
 */
public class BinaryTreeNode {

    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;
    String payload;

    public BinaryTreeNode(String payload) {
        this.payload = payload;
    }

    public BinaryTreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryTreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public String getPayload() {
        return payload;
    }

    public void setPayload(String payload) {
        this.payload = payload;
    }

    public boolean isLeaf() {
        return leftChild == null && rightChild == null;
    }

    public static void flattenTree(List<String> list, BinaryTreeNode node) {

        if(node.isLeaf()) {
            return;
        }

        if(node.getRightChild() != null) {
            list.add(node.getRightChild().getPayload());
            flattenTree(list, node.getRightChild());
        }

        if(node.getLeftChild() != null) {
            list.add(node.getLeftChild().getPayload());
            flattenTree(list, node.getLeftChild());
        }

    }

    /**
     * Recursively builds a tree based on a scanner object.
     * @param node
     *      The root node of the tree
     * @param scanner
     *      The scanner containing the objects
     */
    public static void buildFromScanner(BinaryTreeNode node, Scanner scanner) {
            if(scanner.hasNext()) {
                node.setLeftChild(new BinaryTreeNode(scanner.next()));
                buildFromScanner(node.getLeftChild(), scanner);
            }

            if(scanner.hasNext()) {
                node.setRightChild(new BinaryTreeNode(scanner.next())); {
                    buildFromScanner(node.getRightChild(), scanner);
                }
            }
    }

    /**
     * Builds a BinaryTreeNode object based on the name of a text file.
     * @param fileName
     *      The name of the test file
     * @return
     *      The BinaryTreeNode object
     */
    public static BinaryTreeNode buildTreeFromFile(String fileName) {
        try {
            Scanner scan = new Scanner(new File(fileName));
            if(scan.hasNext()) {
                BinaryTreeNode rootNode = new BinaryTreeNode(scan.next());
                buildFromScanner(rootNode, scan);
                return rootNode;
            } else {
                return null;
            }
        } catch (IOException ex) {
            System.out.println("Please provide a valid test file.");
            return null;
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode node = buildTreeFromFile("test.txt");

        List<String> payloadList = new ArrayList<String>();
        long startTime, endTime;
        startTime = System.nanoTime();
        payloadList.add(node.getPayload());
        flattenTree(payloadList, node);

        for(String s : payloadList) {
            System.out.println(s);
        }
        endTime = System.nanoTime();
        System.out.println("Finished in " + (endTime - startTime) + " nsec");
    }
}

CollatzGraph.java

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Created by marcus on 4/13/15.
 */

public class CollatzGraph {

    HashMap<Integer, Integer> graph;
    int maxInteger = 1;
    int minInteger = -1;

    public CollatzGraph() {
        graph = new HashMap<Integer, Integer>();
    }

    public HashMap<Integer, Integer> getGraph() {
        return graph;
    }

    public int getNumNodes() {
        return graph.size();
    }

    public int getMaxInteger() {
        return maxInteger;
    }

    public int getMinInteger() {

        int counter = 1;
        while (true) {
            if(graph.containsKey(counter)) {
                counter++;
            } else {
                break;
            }
        }
        minInteger = counter;
        return minInteger;
    }

    // Start with loopCount from Session 1. Every time it generates
    // a new member of the sequence, add a node for the integer to the
    // graph (unless a node for that integer is already present).
    // If such a node is already present, loopCount should not have to
    // generate the rest of the sequence. However, it still must return
    // the length of the sequence starting from x.
    // NOTE: loopCount is no longer static.  You will need to use one
    // or more instance variables to store information (the current
    // graph, for example) between calls.
    int loopCount(int x) {
        // STUDENTS: FILL IN CODE HERE!
        if(graph.containsKey(x)) {
            return graph.get(x);
        }
        int b = 0;
        if (x % 2 == 0) {
            b =  1 + loopCount(x >> 1);
        } else {
            b  = 1 + loopCount((3 * x) + 1);
        }

        graph.put(x, b);
        maxInteger = Math.max(x, maxInteger);
        return b;
    }


    // This method sets the initial state of the graph and any other
    // instance variables of the class.
    // HINT: This is a good place to create an initial node for the integer 1.
    // If you do this, then your termination check will be a lot simpler!
    void initialize() {
        // STUDENTS: FILL IN CODE HERE!
        graph.put(1, 1);
    }

    // Using loopCount, fill in the function maxLoop so that it returns
    // the maximum sequence length for any sequence that starts with a
    // number greater than or equal to x and less than y.
    int maxLoop(int x, int y) {
        // STUDENTS: FILL IN CODE HERE!
        int maxCount = loopCount(x);

        for(int i = x + 1; i <= y; i++) {
            int t = loopCount(i);
            maxCount = Math.max(maxCount, t);
        }

        return maxCount;
    }

    int oldLoopCount(int x) {
        // STUDENTS: FILL IN CODE HERE!
        if (x == 1) {
            return 1;
        } else if (x % 2 == 0) {
            return 1 + oldLoopCount(x >> 1);
        } else {
            return 1 + oldLoopCount((3 * x) + 1);
        }
    }

    int oldMaxLoop(int x, int y) {
        // STUDENTS: FILL IN CODE HERE!
        int maxCount = oldLoopCount(x);

        for(int i = x + 1; i <= y; i++) {
            int t = oldLoopCount(i);
            maxCount = Math.max(maxCount, t);
        }

        return maxCount;
    }

    public static void testCollatz(CollatzGraph graph, int n) {
        long starTime, endTime;
        starTime = System.nanoTime();
        int result = graph.maxLoop(1, n);
        endTime = System.nanoTime();
        System.out.println("Collatz with " + n + " elements: " + (endTime - starTime) + " nsec with result " + result);
    }

    public static void printMap(Map mp) {
        Iterator it = mp.entrySet().iterator();

        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            System.out.println(pair.getKey() + " = " + pair.getValue());
        }
    }

    public static void testOldCollatz(CollatzGraph graph, int n) {
        long starTime, endTime;
        starTime = System.nanoTime();
        int result = graph.oldMaxLoop(1, n);
        endTime = System.nanoTime();
        System.out.println("Collatz with " + n + " elements: " + (endTime - starTime) + " nsec with result " + result);
    }

    public static void main(String[] args) {
        CollatzGraph graph = new CollatzGraph();
        graph.initialize();
        System.out.println("Starting tests...");

        testCollatz(graph, 100000);
        testCollatz(graph, 100000);
        testCollatz(graph, 100000);
        testCollatz(graph, 100000);
        testOldCollatz(graph, 100000);
        testOldCollatz(graph, 100000);
        testOldCollatz(graph, 100000);
        testOldCollatz(graph, 100000);


        // STUDENTS: maxloop and loopcount have constructed a graph that
        // contains the collatz sequence for every integer from 2 to 1000
        // as well as for every integer contained in those sequences. Think
        // of a question about the graph and write a query that answers it.
        // Some interesting (IMO) questions that come to mind are:
        //   (1) how many nodes are in the graph?  How fast is it growing?
        //   (2) what is the largest integer in the graph?
        //   (3) what is the smallest integer that is not in the graph?
        System.out.println("the graph contain " + graph.getNumNodes() + " nodes");
        System.out.println("The maximum integer is: " + graph.getMaxInteger());
        System.out.println("The minimum integer that is not in the graph is: " + graph.getMinInteger());
//        printMap(graph.getGraph());
    }
}

FilterList.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by marcus on 4/7/15.
 */
public class FilterList {
    // Write a function named "evens" that takes as input a
    // list of Integer (almost but not quite int) and returns
    // a new list of ints containing only the even elements
    // of the input.
    public static List<Integer> evens(List<Integer> input) {
        // Here are some reminders:
        //
        // You can find input's length using input.size().
        //
        // You can find the remainder of a division using %. For instance,
        // 2 == 11%3 and 1 == 25 % 4.
        //
        // You can declare a new list named "clown" of length n with the
        // syntax:
        //
        // List<Integer> clown = new ArrayList<Integer>(10);
        // STUDENTS, WRITE CODE HERE.
        List<Integer> evens = new ArrayList<Integer>();
        for(Integer i : input) {
            if (i % 2 == 0) {
                evens.add(i);
            }
        }
        return evens;
    }

    public static void main(String[] args) {
        List<Integer> test1 = new ArrayList<Integer>(Arrays.asList(8, 6, 7, 5, 3, 0, 9));
        List<Integer> ans = evens(test1);
        // Expected output: 8, 6, 0
        for (Integer n : ans) {
            System.out.print(Integer.valueOf(n) + ", ");
        }
        System.out.println();

        List<Integer> test2 = new ArrayList<Integer>(Arrays.asList(2, 7, 18, 28, 18, 28, 45, 90, 45));
        ans = evens(test2);
        // Expected output: 2, 18, 28, 18, 28, 90
        for (Integer n : ans) {
            System.out.print(n + ", ");
        }
        System.out.println();

        // STUDENTS: ADD YOUR TEST CASES HERE.
    }
}

RotatedList.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * Created by marcus on 4/7/15.
 */
public class RotatedList {

    public static boolean isRotation(List<Integer> list1, List<Integer> list2) {

        // STUDENT: PROVIDE IMPLEMENTATION
        if(list1.size() != list2.size()) {
            return false;
        }

        if(list1.size() == 0) {
            return false;
        }

        int startPointList2 = list2.indexOf(list1.get(0));
        ListIterator<Integer> iteratorList1 = list1.listIterator();
        ListIterator<Integer> iteratorList2 = list2.listIterator(startPointList2);

        while (iteratorList1.hasNext()) {
            if(!iteratorList2.hasNext()) {
                iteratorList2 = list2.listIterator(0);
            }

            int i1 = iteratorList1.next();
            int i2 = iteratorList2.next();

//            System.out.println("i1: " + i1 + " -- i2: " +i2);
            if(i1 != i2) {
                return false;
            }
        }

        return true;
    }

    public static class Test_IsRotation {
        // Test framework for isRotation()
        // Instead of calling isRotation directly, call expectFailure or expectSuccess
        // with the desired input arguments.  Call init() to start collecting results
        // data for a series of tests, and call report() to print a short report on the
        // outcomes so far.
        private static int failCount;
        private static int successCount;

        public static void init() {
            failCount = 0;
            successCount = 0;
        }

        public static void expectFalse(List<Integer> a, List<Integer> b) {
            // STUDENT: PROVIDE IMPLEMENTATION
            if(!isRotation(a, b)) {
                failCount++;
            }
        }

        public static void expectTrue(List<Integer> a, List<Integer> b) {
            // STUDENT: PROVIDE IMPLEMENTATION
            if(isRotation(a, b)) {
                successCount++;
            }
        }

        public static void testLargeList(int n, boolean expectTrue) {
            List<Integer> list1;
            List<Integer> list2;

            Integer[] a1 = new Integer[n];
            Integer[] a2 = new Integer[n];
            for (int i = 0; i < n; ++i) {
                a1[i] = 0;
                a2[i] = 0;
            }
            // (STUDENT: WHY THIS CASE?)
            a1[0] = 1;
            a1[99] = 2;
            a1[499] = 3;
            a1[999] = 4;
            if(expectTrue) {
                a2[n/2] = 1;
                a2[n/2 + 99] = 2;
                a2[n/2 + 499] = 3;
                a2[n/2 + 999] = 4;
            } else {
                a2[n/3] = 1;
                a2[n/3 + 99] = 2;
                a2[n/2 + 499] = 3;
                a2[n/4 + 999] = 4;
            }

            list1 = new LinkedList<Integer>(Arrays.asList(a1));
            list2 = new LinkedList<Integer>(Arrays.asList(a2));
            long start_time, end_time;
            start_time = System.nanoTime();
            if(expectTrue) {
                Test_IsRotation.expectTrue(list1, list2);
            } else {
                Test_IsRotation.expectFalse(list1, list2);
            }

            end_time = System.nanoTime();
            System.out.println(n + " elements: " + (end_time - start_time) + " nsec");
        }

        private static void report(List<Integer> a, List<Integer> b, boolean got) {
            // Helper routine that may be used by expectFailure and expectSuccess.
            // It should be called only if the unexpected occurs. In other words,
            // if all tests work as expected, then the program will be silent.

            // STUDENT: PROVIDE IMPLEMENTATION
        }

        public static void reportSummary() {
            if (successCount == 0) {
                System.out.println("Summary: all " + failCount +
                        " tests FAILED!");
            } else if (failCount == 0) {
                System.out.println("Summary: all " + successCount +
                        " tests SUCCEEDED!");
            } else {
                System.out.println("Summary: " + successCount +
                        " tests succeeded, " + failCount +
                        " tests failed.");
            }
        }
    }


    public static void main(String[] args) {

        Test_IsRotation.init();

        List<Integer> list1, list2;
        list1 = new LinkedList<Integer>(Arrays.asList(1,2,3,4));
        list2 = new LinkedList<Integer>(Arrays.asList(3, 4, 1, 2));
        Test_IsRotation.expectTrue(list1,list2);
        list1 = new LinkedList<Integer>(Arrays.asList(1,2,3,4));
        list2 = new LinkedList<Integer>(Arrays.asList(3,4,2,1));
        Test_IsRotation.expectFalse(list1,list2);

        // STUDENT: ADD TEST CASES HERE

        // Check performance
        int N = 10000;
        Integer[] a1 = new Integer[N];
        Integer[] a2 = new Integer[N];
        for (int i = 0; i < N; ++i) {
            a1[i] = 0;
            a2[i] = 0;
        }
        // (STUDENT: WHY THIS CASE?)
        a1[0] = 1;
        a2[N/2] = 1;
        list1 = new LinkedList<Integer>(Arrays.asList(a1));
        list2 = new LinkedList<Integer>(Arrays.asList(a2));
        long start_time, end_time;
        start_time = System.nanoTime();
        Test_IsRotation.expectTrue(list1, list2);
        end_time = System.nanoTime();
        System.out.println("10000 elements: " + (end_time - start_time) + " nsec");

        // STUDENT: DESIGN SOME BETTER TESTS FOR EVALUATING PERFORMANCE

        Test_IsRotation.testLargeList(100000, true);
        Test_IsRotation.testLargeList(100000, false);

        Test_IsRotation.test    LargeList(1000000, true);
        Test_IsRotation.testLargeList(1000000, false);

        Test_IsRotation.testLargeList(10000000, true);
        Test_IsRotation.testLargeList(10000000, false);

        Test_IsRotation.reportSummary();
    }
}

SparseMatrix

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by marcus on 4/14/15.
 */
public class SparseMatrix {

    int rows, cols;
    int[][] matrix;

    public SparseMatrix() {

    }

    public void printMatrix() {
        for(int i = 0; i < matrix.length; i++) {
            System.out.print("[");
            for(int j = 0; j < matrix[i].length; j++) {
                System.out.printf("%3d", matrix[i][j]);
            }
            System.out.println(" ]");
        }
    }

    /**
     * I'm assuming that the input from the System.in is comming from a
     * file using the redirection by the terminal
     * @param scanner
     *          Scanner with the input from the console.
     */
    public void initialize(Scanner scanner) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        int maxCol = 0, maxRow = 0;
        int counter = 0;
        while (scanner.hasNextLine()) {
            String[] line = scanner.nextLine().split("");
            for(String s : line) {
                if(Character.isDigit(s.charAt(0))) {
                    int current = Integer.parseInt(s);
                    numbers.add(current);
                    if(counter == 0) {
                        maxRow = Math.max(maxRow, current);
                        counter++;
                    } else if(counter == 1) {
                        maxCol = Math.max(maxCol, current);
                        counter++;
                    } else {
                        counter = 0;
                    }
                }
            }
        }
        rows = maxRow + 1;
        cols = maxCol + 1;

        matrix = new int[rows][cols];
        for(int i = 0; i < numbers.size(); i++) {
            int r = numbers.get(i);
            i++;
            int c = numbers.get(i);
            i++;
            matrix[r][c] = numbers.get(i);
        }
        printMatrix();
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        SparseMatrix m = new SparseMatrix();
        m.initialize(s);
    }
}