Coursera - Computer Science: Programming With A Purpose
Week 3: Arrays - Thue-Morse Weave
Write a program ThueMorse.java that takes an integer command-line argument n and prints an n-by-n pattern like the ones below. Include two space characters between each + and - character.
~/Desktop/arrays> java ThueMorse 4
+ - - +
- + + -
- + + -
+ - - +
~/Desktop/arrays> java ThueMorse 8
+ - - + - + + -
- + + - + - - +
- + + - + - - +
+ - - + - + + -
- + + - + - - +
+ - - + - + + -
+ - - + - + + -
- + + - + - - +
~/Desktop/arrays> java ThueMorse 16
+ - - + - + + - - + + - + - - +
- + + - + - - + + - - + - + + -
- + + - + - - + + - - + - + + -
+ - - + - + + - - + + - + - - +
- + + - + - - + + - - + - + + -
+ - - + - + + - - + + - + - - +
+ - - + - + + - - + + - + - - +
- + + - + - - + + - - + - + + -
- + + - + - - + + - - + - + + -
+ - - + - + + - - + + - + - - +
+ - - + - + + - - + + - + - - +
- + + - + - - + + - - + - + + -
+ - - + - + + - - + + - + - - +
- + + - + - - + + - - + - + + -
- + + - + - - + + - - + - + + -
+ - - + - + + - - + + - + - - +
The Thue-Morse sequence is an infinite sequence of 0s and 1s that is constructed by starting with 0 and successively appending the bitwise negation (interchange 0s and 1s) of the existing sequence. Here are the first few steps of this construction:
0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
To visualize the Thue–Morse sequence, create an n-by-n pattern by printing a + (plus sign) in row i and column j if bits i and j in the sequence are equal, and a - (minus sign) if they are different.
Note: you may assume that n is a positive integer (but it need not be a power of 2).
The Thue–Morse sequence has many fascinating properties and arises in graphic design and in music composition.
Note: the above description is copied from Coursera and converted to markdown for convenience
Solution:
public class ThueMorse {
public static void main(String[] args) {
final int n = Integer.parseInt(args[0]);
// construct sequence
final int[] sequence = new int[n];
for (int i = 1; i < sequence.length; i = i * 2) {
for (int j = 0; j < i; j++) {
// skip if n is not a power of 2
if (i + j >= n) {
continue;
}
if (sequence[j] == 0) {
sequence[i + j] = 1;
} else {
sequence[i + j] = 0;
}
}
}
// output
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (sequence[i] == sequence[j]) {
System.out.print("+ ");
} else {
System.out.print("- ");
}
}
System.out.println();
}
}
}
Link To: Java Source Code