ThueMorse.java

/*************************************************************************
 *  Compilation:  javac ThueMorse.java
 *  Execution:    java ThueMorse N
 *  Dependencies: StdDraw.java
 *  
 *  Plot the N-by-N Thue-Morse weave. The Thue-Morse sequence is 
 *  defined as follows:
 *  
 *      Start with 0, and repeatedly flip all the bits and concatenate
 *      it onto the original string.
 *
 *  Extend the idea in two dimensions. Plot a black square for 1.
 *
 *  % java ThueMorse 16
 *
 *  % java ThueMorse 128
 *
 *************************************************************************/

import java.awt.Color;

public class ThueMorse { 

    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);     // plot N-by-N grid of cells
        int SIZE = 768;
        double size = 1.0 * SIZE / N;           // size of each cell

       /******************************************************************
        * build up Thue-Morse sequence
        ******************************************************************/
        String thue   = "0";
        String morse  = "1";
        String t, m;

        for (int i = 1; i < N; i *= 2) {
            t = thue;
            m = morse;
            thue  += m;
            morse += t;
        }

       /******************************************************************
        * Draw it in turtle graphics
        ******************************************************************/
        StdDraw.create(SIZE, SIZE);
        StdDraw.setScale(0, 0, N, N);
        StdDraw.setColor(Color.black);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                if (thue.charAt(i) != thue.charAt(j))  {
                    StdDraw.go(i + 0.5, j + 0.5);
                    StdDraw.spot(1, 1);
                }
        }
        StdDraw.show();
    }

}