Exploring the paths between two points of a grid

Many results in combinatorics can be generated counting all the different ways to make something in the real world. As an example, consider the lines connecting points in a grid or lattice:

o-------o   .   .
        |
.   .   o---o   .
            |
.   .   .   |   .
            |
.   .   .   o---o
                |
.   .   .   .   o

This figure can be associated to many objects in the real world, like a walk through the streets of a city or multiple movements of a chess rook. The number of different paths like this in a grid of NxN points using only two directions to move and not crossing the main diagonal of the grid is equal to the Catalan number N, and these paths are also known as Dyck paths. Interestingly, including the moves crossing the main diagonal generates exactly the numbers of the famous Pascal's triangle, that is, the Binomial coeficients.

OK, but, what happens if we use a chess queen instead?

Thinking in that question I wrote a program to print these paths, and I generalized it to optionally include moves surpassing the main diagonal of the grid and to optionally include diagonal paths. I published the result in LatticePath and it prints the paths in ASCII:

> java -jar LatticePath.jar --pass --diag 5
...
o---o---o
        |
        o---o
            |
            o
            |
            o
            |
            o---o

o---o---o
        |
        o
         '.
           'o---o
                |
                o
                |
                o

o---o---o
        |
        o
         '.
           'o
             '.
               'o
                |
                o
...
> java -jar LatticePath.jar --pass --diag --count 5
1	1	1	1	1
1	3	5	7	9
1	5	13	25	41
1	7	25	63	129
1	9	41	129	321

After writing the first version of the program I realized that including diagonal moves generates different kinds of numbers: The number of paths not surpassing the main diagonal of the grid is called Schröder number, and the number of paths surpassing the main diagonal of the grid is called Delannoy number. How many connections from only a few simple rules! Thanks also to the OEIS site for being so useful for knowing the name of any sequence of numbers.

I hope you enjoy the program LatticePath and the minimalistic style in which it is programmed!

Repeating strings with a separator in Java

The problem of joining strings with a separator is a very common one in programming, but is surprising the number of solutions that different programmers find to that simple task.
Recently I had to repeat a given string ("?" for example) a given number of times but adding a separator between each string ("," for example). I searched for that code in other places of the project and I found many ways, including these:

if (n > 0) {
 for (int i = 1; i < n; i++) {
  buf.append("?,");
 }
 buf.append("?");
}

if (n > 0) {
 for (int i = 0; i < n; i++) {
  buf.append("?,");
 }
 buf.setLength(buf.length() - 1);
}

for (int i = 0; i < n; i++) {
 buf.append("?");
 if (i < n - 1) {
  buf.append(",");
 }
}

boolean first = true;
for (int i = 0; i < n; i++) {
 if (first) {
  first = false;
 } else {
  buf.append(",");
 }
 buf.append("?");
}

To stop this madness, I decided to create a method for reducing all those variations to simpler and less error-prone calls:

/**
 * Appends a string to a buffer a specified number of times,
 * optionally inserting another string as a separator.
 *
 * @param sb The buffer that will have the string appended, if null a new one is created.
 * @param str The string to append.
 * @param n The number of times that the string will be appended.
 * @param sep An optional separator appended between two strings.
 *
 * @return The specified buffer with the string appended or a new one if it was null.
 */
public static StringBuilder repeatAppend(StringBuilder sb, String str, int n, String sep) {
  if (sb == null) {
    sb = new StringBuilder();
  }
  if (n > 0) {
    sb.append(str);
    if (sep != null) {
      for (int i = 1; i < n; i++) {
        sb.append(sep).append(str);
      }
    } else {
      for (int i = 1; i < n; i++) {
        sb.append(str);
      }
    }
  }
  return sb;
}

Be free to use it in your project and happy coding!

Update: Apache Commons StringUtils.repeat(str, sep, n) and Java Collections.nCopies(n, str) with String.join(sep, collection) are alternatives to this method, but our method allows adding to an existing StringBuilder and the others need to create it and destroy it for that. Added return sb; to allow an inline use.

Java class for faster searching of substrings in HashMap

Creating objects in Java requires the allocation of system memory, which is a very complex operation, so many algorithms will be faster when it is avoided. This Substring class allows you to search a portion of a String in a HashMap (one with String keys) without having to create any object. Every time the String.substring method is called, a new object is allocated for the substring (only the internal array is shared), so the solution is searching in the HashMap without using a real String as the key, which can be 2 times faster:

...
Substring substr = new Substring();
for (...) { //lots of repetitions
    String str = ...; int start = ...; int end = ...;
    //obj = hmap.get(str.substring(start, end)); //before
    obj = hmap.get(substr.setSubstring(str, start, end));
    if (obj != null) { ... }
}

Because the Java memory management is so efficient, the use of this class will only be faster if your program needs to search for thousands of substrings and you reuse the same Substring object. A similar idea could also be applied to search for the uppercase version of a String in a HashMap without creating new objects (when calling to String.toUpperCase a new object is created if a lowercase character is found). This one is left as an exercise for the reader. Enjoy!

Mark IV Special Coffee Maker API implementation

In his book "UML for Java Programmers", Robert C. Martin (from Object Mentor) explains an object oriented software design problem: Writing an implementation of the software for the fictional Mark IV Special Coffee Maker. The solution must use the low-level API of the hardware that controls the different parts of the machine, which is provided as the CoffeeMakerAPI Java interface. Robert also published the complete Mark IV Special Coffee Maker chapter for us.

I am not here to give another solution for the problem. Instead, I wrote the CoffeeMakerGUI application, that contains a CoffeeMakerAPI implementation that lets you to manually test your solution by using a simulated Coffee Maker machine:

To compile it using a Java compiler, you need the CoffeeMakerAPI Java interface (given in the mentioned chapter) and also the following interface:

   public interface CoffeeMakerImpl {
      void createComponents(CoffeeMakerAPI api);
      void pollComponents();
   }

You can run the application without parameters, and a help message will be printed, but to test your solution you have to connect it with CoffeeMakerGUI, and to do it you must pass as the first argument of the program a class implementing the above CoffeeMakerImpl interface and having a default constructor. So the command to run it could be, for example:
java CoffeeMakerGUI MyCoffeeMakerImpl

The program will instance that passed class and will call to createComponents passing a reference of the CoffeeMakerAPI implementation. Then, it will call to the pollComponents periodically to "wake up" your implementation.

Thanks to Uncle Bob for publishing that interesting problem and solution!

Simple Java Swing JSON formatter

Most of web developers that are using AJAX to retrieve data from the server will be using the JSON lightweight format (instead of XML) to encode the data. To help them with this, the web development consoles in all web browsers are capable to show a hierarchical view of received JSON data, and this is usually fine, but when the size of the data grows or its hierarchy becomes complicated, you need to copy the data out to study it. More specifically, I usually need to compare the differences in the responses of different calls to the server.

The problem here is that JSON data is generally encoded in a very long string without line breaks, so you must format the JSON first. Many online JSON formatters exist, but I just needed a simple non-remote tool to format large JSON strings, leaving each element in its own line and ordering the properties of the objects, so I wrote a little Java Swing program, JsonFormatter.java, helped by the json-simple Java toolkit. To use this program you need to download the json-simple JAR file in order to compile and run the program (see below), and do Ctrl+V/Ctrl+A/Ctrl+C to process the JSON text, along with a text editor capable of doing diff comparisons, like Vim. Use it!

To compile this program using the javac compiler, after putting the json-simple JAR file in the same directory (for example the 1.1.1 version), type: javac -cp json-simple-1.1.1.jar JsonFormatter.java

Then you could build a JAR file to run it easily, just typing: jar cfm json-formatter.jar MANIF-ADD.MF JsonFormatter*.class, where the MANIF-ADD.MF is a text file with the following two lines (ensuring that last line ends with a return):
Main-Class: JsonFormatter
Class-Path: json-simple-1.1.1.jar

After that, you only need the two JAR files, and to run it, if the double click doesn't work, you can type: java -jar json-formatter.jar

How to run your JUnit 4 tests using the old JUnit 3 GUI runners

Although the usual way for running JUnit tests is inside an IDE like Eclipse or NetBeans, both with an integrated debugger that directly points you to the place where the error is located when a test fails, sometimes can be better a lightweight tool for running your tests.

The popular JUnit testing framework, in its version 3, came with Java-based GUI runners which allowed developers to see the test results in a graphical window instead of having them printed in the text console, so it was nice to run them even without having an IDE.

Instead, the next version of the framework, JUnit 4, didn't come with any GUI runners (for unknown reasons for me, perhaps because the features and API are in constant change or to encourage developers to use IDEs for debugging), so developers not using an IDE now must see the results of their tests in the text console, having to read the large exception's trace output when an error appears, hidding also any other debugging messages added by the developer to catch the bug.

In the first releases of the JUnit 4 series, the JUnit team developed a backwards compatibility feature for allowing the JUnit 4 tests to be run with a JUnit 3 runner, so certain older applications having such a runner could run JUnit 4 test classes just adding to them the following method (changing the SimpleTest.class to the file name in which the code is pasted):

public static junit.framework.Test suite() {
    return new junit.framework.JUnit4TestAdapter(SimpleTest.class);
}

For achieving this the JUnit 4 framework provides some code under the old junit.framework package (although the new version uses the new org.junit package to allow coexistence), so the code showed before can be compiled with the JUnit 4 framework and also be able to run in a JUnit 3 runner needing to call the suite() method.

Recently, however, it seems that support for this hack has been reduced as more applications are ported to the new framework version, so you cannot find the JavaDoc documentation of this package in the latest JavaDoc JUnit 4 API link from JUnit main page, but only in the outdated previous version of the JUnit 4 API. Also, if you download the last JUnit 3 version from the old JUnit hosting site at SourceForge, the old GUI runners seem not to run properly, perhaps because of the problem of having both junit.framework versions of the package.

After many days searching around this, I discovered that the people from JUnit 4 Extensions have been maintaining the isolated GUI runners of JUnit 3, so they can coexists with the JUnit 4 packages without problem. By adding their prebuilt junit-ui-runners-3.8.2.jar file to your CLASSPATH environment variable you will be able to run any individual JUnit 4 modified test class in the old Swing GUI runner of JUnit 3 introducing the following command (changing the SimpleTest name to the name of the class test that you want to run):

java junit.swingui.TestRunner SimpleTest

Keep in mind that this is a temporary solution, because JUnit 4 will not support this for a long time (although having a simple standalone GUI runner for JUnit 4 would be much better). Until then, when all those suite() methods will be removed, we can keep using this alternative. Happy testing!