How to Create a Binary Search Tree from a Sorted Array

import java.util.LinkedList;

public class BST {
    static class Node {
        private int value;
        private Node leftChild;
        private Node rightChild;
        
        public Node(int value) {
            this.value = value;
        }
    }
    
    static enum ChildType {
        LEFT, RIGHT, ROOT
    }
    
    private Node root;
    
    public BST(int[] sortedArray) {
        int lo = 0;
        int hi = sortedArray.length;
        int mid = (lo + hi) / 2;
        root = new Node(sortedArray[mid]);
        build(root, ChildType.ROOT, sortedArray, lo, hi);
    }
    
    private void build(Node node, ChildType type, int[] array, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = (lo + hi) / 2;
        Node n = node;
        if (type == ChildType.LEFT) {
            node.leftChild = new Node(array[mid]);
            n = node.leftChild;
        } else if (type == ChildType.RIGHT) {
            node.rightChild = new Node(array[mid]);
            n = node.rightChild;
        }
        build(n, ChildType.LEFT, array, lo, mid);
        build(n, ChildType.RIGHT, array, mid+1, hi);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            Node n = nodes.removeFirst();
            if (n.leftChild != null) {
                sb.append(n.leftChild.value + " -- left --> " + n.value + " \n");
                nodes.add(n.leftChild);
            }
            if (n.rightChild != null) {
                sb.append(n.rightChild.value + " -- right --> " + n.value + " \n");
                nodes.add(n.rightChild);
            }
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        int[] sortedArray = new int[7];
        for (int i = 0; i < sortedArray.length; i++) {
            sortedArray[i] = i;
        }
        BST bst = new BST(sortedArray);
        System.out.println(bst);
    }
}

How to Implement tail -f in Java

package jtail;

import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;

public class JTail {
    private static final long SLEEP_TIME = 500L;
    
    public static void open(File file) {
        RandomAccessFile raf = null;
        long lastFilePointer = 0;
        try {
            raf = new RandomAccessFile(file, "r");
            while (true) {
                if (raf.length() == lastFilePointer) {
                    // Don't forget to close the previous file handle
                    raf.close();
                    Thread.sleep(SLEEP_TIME);
                    // Wait till the file exists before opening it
                    while (!file.exists()) {}
                    raf = new RandomAccessFile(file, "r");
                    raf.seek(lastFilePointer);
                } else {
                    byte[] bytes = new byte[4096];
                    int bytesRead;
                    while ((bytesRead = raf.read(bytes, 0, bytes.length)) != -1) {
                        System.out.print(new String(bytes, 0, bytesRead));
                    }
                    lastFilePointer = raf.getFilePointer();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (raf != null) {
                try {
                    raf.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }
    
    private static void printUsage() {
        System.out.println("Usage: java -cp <classpath> " +
            JTail.class.getName() + " <file>");
    }
    
    private static boolean validateArgs(String[] args) {
        if (args.length != 1) {
            printUsage();
            return false;
        }
        File file = new File(args[0]);
        if (!file.isFile()) {
            System.err.println("Error: " + file.getAbsolutePath() +
                " does not exist or is not a file");
            return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        if (!validateArgs(args)) {
            System.exit(1);
        }
        JTail.open(new File(args[0]));
    }
}

How to Solve Clock Puzzle

While playing Final Fantasy XIII-2, I came across an interesting puzzle. The puzzle is as follows.

Given n-numbers in a circle that form numbers similar to the ones in a clock. Like a clock, it has two pointers (e.g. the hour and the minute) that move to the left and to the right. Initially both pointers are pointing to the same number and we are allowed to choose any number to begin with. For any number that we pick, the two pointers will move x steps to the left and x steps to the right where x is the value shown in the number that we pick. For each number that we pick, the number will disappear and we cannot pick that number again. The next step is to pick any number that the left or right pointer is pointing to. The win this puzzle, we need to perform n-moves that will eliminate all the numbers in the clock. If both pointers are pointing to the numbers that have disappeared and there are still numbers that have not disappeared, we are lost.

Example:

      2
    3   1 
  3       3
    2   2
      2

We pick 2 (north). Number 2 (north) will disappear. The left pointer will move 2 steps to the left and pointing to 3 (west). The right pointer will move to 2 steps to the right and pointing to 3 (east)

We pick 3 (west). Number 3 (west) will disappear. The left pointer will move 3 steps to the left and pointing to 2 (southeast). The right pointer will move 3 steps to the right pointing to 1 (northeast)

We pick 2 (southeast). Number 2 (southeast) will disappear. The left pointer wil move 2 steps to the left and pointing to 1 (northeast). The right pointer will move 2 steps to the right pointing to 2 (southwest)

We keep picking a number that either a left or right pointer is pointing to and we need to make sure that if there are still some numbers in the clock, both left and right pointers must not point to the numbers that have disappeared. Once all the numbers have disappeared, we have won the puzzle

One possible solution.

 1. Init  --> 2
 2. Left  --> 3
 3. Left  --> 2
 4. Left  --> 1
 5. Right --> 3
 6. Right --> 2
 7. Right --> 3
 8. Left  --> 2

My solution in Java.

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

public class ClockPuzzle {
    private static class Number implements Cloneable {
        private boolean marked;
        private final int value;
        
        public Number(int value) {
            this.value = value;
        }
        
        public Number(int value, boolean marked) {
            this.value = value;
            this.marked = marked;
        }
        
        @Override
        protected Object clone() {
            return new Number(value, marked);
        }
    }
    
    private static enum Direction {
        INIT("Init "),
        LEFT("Left "),
        RIGHT("Right");
        
        private String str;
        
        private Direction(String str) {
            this.str = str;
        }
        
        @Override
        public String toString() {
            return str;
        }
    }
    
    private final Number[] numbers;
    private final int size;
    
    public ClockPuzzle(int... values) {
        numbers = new Number[values.length];
        for (int i = 0; i < values.length; i++) {
            numbers[i] = new Number(values[i]);
        }
        size = values.length;
    }
    
    public void solve(int index) {
        List<String> result = new ArrayList<>();
        Number[] newNumbers = copy(numbers);
        result.add(createResult(Direction.INIT, index, newNumbers[index].value));
        solve(newNumbers, index, result);
    }
    
    private void solve(Number[] numbers, int index, List<String> result) {
        Number e = numbers[index];
        if (e.marked) {
            return;
        }
        e.marked = true;
        if (allMarked(numbers)) {
            printResult(result);
        } else {
            // the left pointer
            int leftIndex = getActualIndex(index-e.value, numbers.length);
            solve(leftIndex, Direction.LEFT, numbers, result);
            
            // the right pointer
            int rightIndex = getActualIndex(index+e.value, numbers.length);
            solve(rightIndex, Direction.RIGHT, numbers, result);
        }
    }
    
    private void solve(int index, Direction direction, Number[] numbers, List<String> result) {
        Number[] newNumbers = copy(numbers);
        List<String> newResult = copy(result);
        newResult.add(createResult(direction, index, newNumbers[index].value));
        solve(newNumbers, index, newResult);
    }
    
    private Number[] copy(Number[] numbers) {
        Number[] newNumbers = new Number[numbers.length];
        for (int i = 0; i < newNumbers.length; i++) {
            newNumbers[i] = (Number) numbers[i].clone();
        }
        return newNumbers;
    }
    
    private String createResult(Direction direction, int index, int value) {
        return direction.toString() + " --> " + value + " (index: " + index + ")";
    }
    private List<String> copy(List<String> list) {
        List<String> newList = new ArrayList<>();
        for (String s : list) {
            newList.add(s);
        }
        return newList;
    }
    
    private void printHeader() {
        for (int i = 0; i < 50; i++) {
            System.out.print("=");
        }
        System.out.println();
    }
    
    private void printResult(List<String> result) {
        printHeader();
        int i = 1;
        for (String r : result) {
            if (i < 10) {
                System.out.println(" " + i++ + " " + r);
            } else {
                System.out.println(i++ + " " + r);
            }
        }
        printHeader();
    }
    
    private boolean allMarked(Number[] numbers) {
        for (Number n : numbers) {
            if (!n.marked) {
                return false;
            }
        }
        return true;
    }
    
    private int getActualIndex(int i, int arraySize) {
        if (i >= arraySize) {
            return i - arraySize;
        }
        if (i < 0) {
            return arraySize + i;
        }
        return i;
    }
    
    public static void main(String[] args) {
        ClockPuzzle clockPuzzle = new ClockPuzzle(2, 1, 3, 2, 2, 2, 3, 3);
        for (int i = 0; i < clockPuzzle.size; i++) {
            clockPuzzle.solve(i);
        }
    }
}

How to Get the Index of an Element in a Circular Buffer

Problem: Get the index of a particular element in a circular buffer, e.g.

Array: 7 8 9 0 1 2 3 4 5 6
search(0) --> index 3
search(6) --> index 9

public class CircularBinarySearch {
    // return -1 if not found
    private static int getIndex(int[] array, int value) {
        int minIdx = findMinIndex(array);
        return binarySearch(array, value, minIdx, array.length-1+minIdx, minIdx);
    }
    
    private static int binarySearch(int[] array, int value, int lo, int hi, int minIdx) {
        if (lo > hi) {
            return -1;
        }
        int mid = (lo + hi) / 2;
        int midIdx = getRealIndex(array.length, mid, minIdx);
        if (array[midIdx] == value) {
            return midIdx;
        } else if (array[midIdx] > value) {
            return binarySearch(array, value, lo, mid-1, minIdx);
        } else if (array[midIdx] < value) {
            return binarySearch(array, value, mid+1, hi, minIdx);
        }
        return -1;
    }
    
    private static int getRealIndex(int arrayLength, int idx, int minIdx) {
        if (idx >= arrayLength) {
            return idx - arrayLength;
        }
        return idx;
    }
    
    private static int findMinIndex(int[] array) {
        int minIdx = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[minIdx]) {
                minIdx = i;
            }
        }
        return minIdx;
    }
    
    public static void main(String[] args) {
        int[] array = new int[10];
        array[0] = 7;
        array[1] = 8;
        array[2] = 9;
        array[3] = 0;
        array[4] = 1;
        array[5] = 2;
        array[6] = 3;
        array[7] = 4;
        array[8] = 5;
        array[9] = 6;
        
        // verify it
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + " --> " + getIndex(array, array[i]));
        }
        System.out.print("120 --> " + getIndex(array, 120));
    }
}

How to Create an Executable Zip File

Python has the ability to execute a zip file that contains Python files. This makes it very handy to create an executable zip file. Here's an example how to do it.

test.py

#!/usr/bin/env python

def say_something(): print "Hello World"
def main(): say_something()

__main__.py

#!/usr/bin/env python

import test

if __name__ == "__main__": test.main()

The __main__.py must be in the root directory of the zip file.

Zip all the Python files so that it looks like below. We don't need to use .zip extension, we can name it anything we want.

test.zip
|-- __main__.py
`-- test.py

To execute it:

python test.zip

and you will see the output as

Hello World

How to Capture StdOut/StdErr in Java

package test;

import java.io.BufferedReader;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PipedInputStream;
import java.io.PipedOutputStream;
import java.io.PrintStream;
import java.io.StringWriter;

public class Main {
    public static interface Function {
        void execute();
    }
    
    public static String capture1(PrintStream ps, Function func)
        throws IOException {
        PipedOutputStream pos = new PipedOutputStream();
        BufferedReader br = new BufferedReader(new InputStreamReader(
            new PipedInputStream(pos)));
        StringWriter sw = new StringWriter();
        String output = null;
        try {
            PrintStream old = ps;
            System.setOut(new PrintStream(pos));

            func.execute();
            System.out.flush();

            pos.close();

            System.setOut(old);

            int charsRead;
            char[] cbuf = new char[4096];
            while ((charsRead = br.read(cbuf, 0, cbuf.length)) != -1) {
                sw.write(cbuf, 0, charsRead);
            }
            output = sw.toString();
        }
        finally {
            br.close();
            sw.close();
        }
        return output;
    }
    
    public static String capture2(PrintStream ps, Function func)
        throws IOException {
        String output = null;
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        try {
            PrintStream old = System.out;
            System.setOut(new PrintStream(baos));

            func.execute();
            System.out.flush();

            System.setOut(old);

            output = baos.toString();
        }
        finally {
            baos.close();
        }
        return output;
    }
    
    public static void main(String[] args) throws Exception {
        String output = capture1(System.out, new Function() {
            @Override
            public void execute() {
                System.out.println("Hello World");
                System.out.println("Bye World");
            }
        });
        System.out.println(output);
        
        
        output = capture2(System.out, new Function() {
            @Override
            public void execute() {
                System.out.println("Hello World");
                System.out.println("Bye World");
            }
        });
        System.out.println(output);
    }
}

How to Parse Java Source Code using Oracle/Sun Java Compiler API

NOTE: using compiler API (com.sun.*) packages can be dangerous since they are supposed to be internal packages.

package test;

public class Foo {
    public String getSomething() {
        return "Hello World";
    }
}

package test;

import javax.tools.JavaCompiler;
import javax.tools.JavaFileObject;
import javax.tools.StandardJavaFileManager;
import javax.tools.ToolProvider;

import com.sun.source.tree.ClassTree;
import com.sun.source.tree.CompilationUnitTree;
import com.sun.source.tree.MethodTree;
import com.sun.source.tree.ReturnTree;
import com.sun.source.tree.StatementTree;
import com.sun.source.tree.Tree;
import com.sun.source.util.JavacTask;
import com.sun.source.util.SimpleTreeVisitor;

public class Test {
    public static void main(String[] args) throws Exception {
        JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();
        StandardJavaFileManager fileManager = compiler.getStandardFileManager(null, null, null);
        Iterable<? extends JavaFileObject> fileObjects = fileManager
            .getJavaFileObjects("test/Foo.java");
        JavacTask javac = (JavacTask) compiler.getTask(null, fileManager, null, null, null,
            fileObjects);
        Iterable<? extends CompilationUnitTree> trees = javac.parse();
        for (CompilationUnitTree tree : trees) {
            tree.accept(new CompilationUnitVisitor(), null);
        }
    }
    
    static class CompilationUnitVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitCompilationUnit(CompilationUnitTree cut, Void p) {
            System.out.println("Package name: " + cut.getPackageName());
            for (Tree t : cut.getTypeDecls()) {
                if (t instanceof ClassTree) {
                    ClassTree ct = (ClassTree) t;
                    ct.accept(new ClassVisitor(), null);
                }
            }
            return super.visitCompilationUnit(cut, p);
        }
    }
    
    static class ClassVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitClass(ClassTree ct, Void p) {
            System.out.println("Class name: " + ct.getSimpleName());
            for (Tree t : ct.getMembers()) {
                MethodTree mt = (MethodTree) t;
                mt.accept(new MethodVisitor(), null);
            }
            return super.visitClass(ct, p);
        }
    }
    
    static class MethodVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitMethod(MethodTree mt, Void p) {
            System.out.println("Method name: " + mt.getName());
            for (StatementTree st : mt.getBody().getStatements()) {
                if (st instanceof ReturnTree) {
                    ReturnTree rt = (ReturnTree) st;
                    rt.accept(new ReturnTreeVisitor(), null);
                }
            }
            return super.visitMethod(mt, p);
        }
    }
    
    static class ReturnTreeVisitor extends SimpleTreeVisitor<Void, Void> {
        @Override
        public Void visitReturn(ReturnTree rt, Void p) {
            System.out.println("Return statement: " + rt.getExpression());
            return super.visitReturn(rt, p);
        }
    }
}