Sunday, December 30, 2012

How to Setup JavaFX Project with Gradle

?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
apply plugin: "java"
apply plugin: "eclipse"
 
version = "0.1.0"
 
sourceCompatibility = 1.7
targetCompatibility = 1.7
 
defaultTasks = ["clean", "jar"]
 
def javafxLib = "jfxrt.jar"
 
def getJavaFXPath(def javafxLib) {
    def javaHome = System.env["JAVA_HOME"]
    if (javaHome == null) {
        throw new RuntimeException("JAVA_HOME environment variable must be set")
    }
    def javafxrt = "jre" + File.separator + "lib" + File.separator + javafxLib
    return new File(javaHome, javafxrt).absolutePath
}
 
dependencies {
    compile files(getJavaFXPath(javafxLib))
}
 
jar {
    // When creating a fat JAR, make sure we exclude javafx runtime
    // from the fat JAR
    dependsOn configurations.runtime
    from {
        configurations.runtime.findAll { !it.name.contains(javafxLib) }.collect {
            it.isDirectory() ? it : zipTree(it)
        }
    }
    from sourceSets.main.allJava
 
    // There's no need to explicitly specify the -classpath or -cp
    // since the classpath information is already stored in the MANIFEST.MF
    manifest {
        attributes "Main-Class": "javafxapp.JavaFXApp"
        attributes "Class-Path": getJavaFXPath(javafxLib)
    }
}
Now we can easily execute the generated JAR by calling 
java -jar <jar_file.jar>
Posted by at No comments:
Labels: , ,

Saturday, December 29, 2012

How to Create Fully-Occupied-Space Controls in JavaFX

A simple example to create fully-occupied-space buttons in JavaFX.
?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package javafxapp;
 
import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.scene.Node;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.control.ButtonBuilder;
import javafx.scene.layout.AnchorPane;
import javafx.scene.layout.AnchorPaneBuilder;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.Priority;
import javafx.scene.layout.VBox;
import javafx.scene.layout.VBoxBuilder;
import javafx.stage.Stage;
 
public class JavaFXApp extends Application {
    @Override
    public void start(Stage primaryStage) throws Exception {
        primaryStage.setTitle("JavaFX App");
         
        BorderPane root = new BorderPane();
         
        root.setLeft(createNode("Left"));
        root.setRight(createNode("Right"));
        root.setCenter(createNode("Center"));
        root.setTop(createNode("Top"));
        root.setBottom(createNode("Bottom"));
         
        Scene scene = new Scene(root);
         
        primaryStage.setScene(scene);
        primaryStage.show();
    }
     
    private Node createNode(String text) {
        VBox vbox = VBoxBuilder.create()
            .spacing(5)
            .padding(new Insets(10, 10, 10, 10))
            .build();
 
        Button btn = ButtonBuilder.create()
            .text(text)
            .build();
         
        AnchorPane anchoredPane = AnchorPaneBuilder.create()
            .children(btn)
            .style("-fx-border-style: solid;"
                + "-fx-border-width: 1;"
                + "-fx-border-color: black")
                .build();
         
        AnchorPane.setBottomAnchor(btn, 5.0);
        AnchorPane.setRightAnchor(btn, 5.0);
        AnchorPane.setTopAnchor(btn, 5.0);
        AnchorPane.setLeftAnchor(btn, 5.0);
         
        VBox.setVgrow(anchoredPane, Priority.ALWAYS);
        vbox.getChildren().addAll(anchoredPane);
         
        return vbox;
    }
     
    public static void main(String[] args) {
        launch(args);
    }
}
Posted by at No comments:
Labels: ,

Thursday, December 27, 2012

Getting Started with Gradle Multiproject

Project structure: 
.
├── api
│   └── src
│       └── main
│           └── java
│               └── api
│                   └── API.java
├── build.gradle
├── cli
│   └── src
│       └── main
│           └── java
│               └── cli
│                   └── CLI.java
├── core
│   └── src
│       └── main
│           └── java
│               └── core
│                   └── Core.java
├── gui
│   └── src
│       └── main
│           └── java
│               └── gui
│                   └── GUI.java
└── settings.gradle
In this project, core depends on api, cli depends on core, and gui depends on core.

settings.gradle

?
1
include ":api", ":core", ":gui", ":cli"
build.gradle
?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def distDir = "dist"
 
defaultTasks = ["clean", "jar", "dist"]
 
subprojects {
    apply plugin: "java"
    apply plugin: "eclipse"
    sourceCompatibility = 1.7
    targetCompatibility = 1.7
    version = "0.1.0"
}
 
project(":core") {
    dependencies {
        compile project(":api")
    }
}
 
project(":gui") {
    dependencies {
        compile project(":core")
    }
}
 
project(":cli") {
    dependencies {
        compile project(":core")
    }
}
 
task clean << {
    delete distDir
}
 
task dist << {
    def d = mkdir(distDir)
    subprojects.each { subproject ->
        subproject.tasks.jar.each { archiveTask ->
            copy {
                from archiveTask.archivePath
                into d
            }
        }
    }
}
The build.gradle shown above has a dist task that will pull all the generated jars into dist directory.
Posted by at 1 comment:
Labels: ,

How to Include Source Files into JAR in Gradle

Project structure: 
├── build.gradle
└── src
    └── main
        └── java
            └── test
                └── Test.java
build.gradle
?
1
2
3
4
5
6
7
apply plugin: "java"
 
defaultTasks = ["clean", "jar"]
 
jar {
    from sourceSets.main.allJava
}
Posted by at No comments:
Labels: ,

Monday, December 17, 2012

How to Solve Cutting Rod Problem

This solution uses memoization.
?
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
29
30
31
32
33
34
35
#!/usr/bin/env python
 
def find_max(list_tuples):
    if len(list_tuples) == 0:
        return None
    maximum = list_tuples[0]
    for i in xrange(1, len(list_tuples)):
        if maximum[0] < list_tuples[i][0]:
            maximum = list_tuples[i]
    return maximum
 
memo = {}
def cutting_rod(prices, ncuts):
    if ncuts == 0:
        return (0, [])
    if ncuts in memo:
        return memo[ncuts]
    tmp = []
    for i in xrange(0, ncuts):
        r = cutting_rod(prices, ncuts-i-1)
        new_list = list(r[1])
        new_list.append(i)
        value = prices[i] + r[0]
        tmp.append((value, new_list))
    result = find_max(tmp)
    memo[ncuts] = result
    return result
 
if __name__ == '__main__':
    p = [2, 5, 6, 7]
    r = cutting_rod(p, len(p))
    print "Prices:", p
    print "Optimal value:", r[0]
    print "Indices:", r[1]
    print "Cuts:", [p[x] for x in r[1]]
Output: 
Prices: [2, 5, 6, 7]
Optimal value: 10
Indices: [1, 1]
Cuts: [5, 5]
Posted by at No comments:
Labels: ,

Thursday, December 13, 2012

How to Solve Producer Consumer Problem in Java

Change the preJava5 flag to true if you are running Java 4 and below. Change preJava5 flag to true if you are running Java 5 and above.
?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import java.util.LinkedList;
import java.util.Random;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;
 
public class ProducerConsumer {
    public static final int MAX_SIZE = 5;
    public static final int SLEEP_TIME = 5 * 100;
     
    public static class PreJava5 {
        public static class Consumer {
            private Random random = new Random();
             
            public void consume(LinkedList<Integer> queue) {
                while (true) {
                    try {
                        synchronized (queue) {
                            if (queue.isEmpty()) {
                                System.out.println("Queue is empty");
                                queue.wait();
                            } else {
                                System.out.println("Consuming something, size="
                                    + queue.size());
                                queue.removeFirst();
                                queue.notifyAll();
                            }
                        }
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
         
        public static class Producer {
            private Random random = new Random();
             
            public void produce(LinkedList<Integer> queue) {
                while (true) {
                    try {
                        synchronized (queue) {
                            if (queue.size() == MAX_SIZE) {
                                System.out.println("Queue is full");
                                queue.wait();
                            } else {
                                System.out.println("Producing something, size="
                                    + queue.size());
                                queue.addLast(0);
                                queue.notifyAll();
                            }
                        }
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
    }
     
    public static class Java5AndAbove {
        public static class Consumer {
            private Random random = new Random();
             
            public void consume(BlockingQueue<Integer> queue) {
                while (true) {
                    try {
                        System.out.println("Consuming something, size="
                            + queue.size());
                        // will block if the queue is empty
                        queue.take();
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
         
        public static class Producer {
            private Random random = new Random();
             
            public void produce(BlockingQueue<Integer> queue) {
                while (true) {
                    try {
                        System.out.println("Producing something, size="
                            + queue.size());
                        // will block if the queue is full
                        queue.put(0);
                        // to simulate performing some busy tasks
                        Thread.sleep(random.nextInt(SLEEP_TIME));
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }
            }
        }
    }
     
    public static void main(String[] args) {
        boolean preJava5 = false;
         
        if (preJava5) {
            final LinkedList<Integer> queue = new LinkedList<>();
            final PreJava5.Producer producer = new PreJava5.Producer();
            final PreJava5.Consumer consumer = new PreJava5.Consumer();
            Thread t1 = new Thread(new Runnable() {
                @Override
                public void run() {
                    producer.produce(queue);
                }
            });
            Thread t2 = new Thread(new Runnable() {
                @Override
                public void run() {
                    consumer.consume(queue);
                }
            });
            t1.start();
            t2.start();
        } else {
            final BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(MAX_SIZE);
            final Java5AndAbove.Producer producer = new Java5AndAbove.Producer();
            final Java5AndAbove.Consumer consumer = new Java5AndAbove.Consumer();
             
            ExecutorService es1 = Executors.newSingleThreadExecutor();
            ExecutorService es2 = Executors.newSingleThreadExecutor();
             
            es1.execute(new Runnable() {
                @Override
                public void run() {
                    producer.produce(queue);
                }
            });
             
            es2.execute(new Runnable() {
                @Override
                public void run() {
                    consumer.consume(queue);
                }
            });
        }
    }
}
Posted by at No comments:
Labels:

Tuesday, December 11, 2012

How to Implement Matrix Multiplication

?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Matrix {
    private static int[][] multiply(int[][] a, int[][] b) {
        if (a[0].length != b.length) {
            throw new IllegalArgumentException(
                "A(" + a.length + "x" + a[0].length + ") did not match " +
                "B(" + b.length + "x" + b[0].length + ")");
        }
         
        int[][] c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[0].length; k++) {
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }
     
    private static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] < 10) {
                    System.out.print(" ");
                }
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
     
    public static void main(String[] args) {
        int[][] a = new int[2][3];
        int value = 1;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value++;
            }
        }
        System.out.println("Matrix A:");
        print(a);
         
        int[][] b = new int[3][2];
        value = 1;
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                b[i][j] = value++;
            }
        }
        System.out.println("Matrix B:");
        print(b);
         
         
        int[][] c = multiply(a, b);
        System.out.println("Matrix C:");
        print(c);
    }
}
Posted by at No comments:
Labels: ,

Wednesday, December 5, 2012

How to Create a Binary Search Tree from a Sorted Array

?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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);
    }
}
Posted by at No comments:
Labels: ,

Monday, December 3, 2012

How to Implement tail -f in Java

?
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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]));
    }
}
Posted by at No comments:
Labels:

Sunday, December 2, 2012

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.

    ?
    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
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    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);
            }
        }
    }
    Posted by at No comments:
    Labels: ,

    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
    ?
    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
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    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));
        }
    }
    Posted by at No comments:
    Labels: ,
    Subscribe to: Posts (Atom)