Out of the box, Spring provides various techniques to define your beans and their dependencies - XML files, Java annotations and since version 4.0, even using groovy scripts. Furthermore, you can control the creation of the beans using FactoryBean and bean post-processors. Still, there are times when it would be very convenient to create an instance of some random class and have its dependencies satisfied at runtime without Spring knowing anything about that class a priori.

If you are willing to accept a few limitations - only bean dependencies, not simple scalar properties, and only those annotated with @javax.inject.Inject, then the following code creates a dependency injector that you can use to dynamically “bind” random objects.

The dependency injector itself should be a spring bean and available to your code that wants to inject something else. In addition, you need to have an instance of AutowiredAnnotationBeanPostProcessor. This bean is automatically included if you have the annotation-config directive in your Spring context file:

	<context:annotation-config />

You can now use the dependency injector to bind dependencies at runtime as follows:

	public class MyObject {
		@Inject SomeOtherObject other; // SomeOtherObject is spring managed

        ...
    }


	...
    MyObject withDependencies = dependencyInjector.bind(new MyObject());

Groovy has some classes with very interesting names - ConfigSlurper, XmlSlurper and JsonSlurper. I wonder if the engineer who wrote this class had a 7-Eleven slurpee addiction!

I can imagine ConfigSlurper (and its cousins) making a slurping noise as it executes (slurps?), complete with a louder noise as it ends - similar to an annoying kid sucking at the last bit of drink from an empty cup filled with ice. One has to wonder about the wisdom behind calling a class Slurper in a professional software library. But perhaps such concerns are not valid when dealing with a language called Groovy. The software world has a penchant for coming up with interesting names. Apart from culinary and beverage related names such as Java, Beans, Cocoa and Guava topped with Sugar and eliciting a Yum response, we also have reptilian and warrior names like Python, Boa and Ninja. Indeed a simple perusal of Github leads to encounters with Pigshell, Nightmare and Phantom. Not to be left behind, the hardware world is re-calibrating from sophisticated names like Centrino and Ivy Bridge to Raspberry Pi and Beaglebone.

In object oriented design, coming up with a good name is a hard problem. In fact, most of the arguments in OO design are related to naming objects. As a professor once said, there are just two problems in Computer Science:

1. Naming objects
2. Cache invalidation and
3. Off by one errors.

Having had my share of endless arguments over class names, I decided to investigate open source software to see what words appear in class names. I wrote up a program to download the source jars for the latest version of all Java libraries available via Maven Central. An hour later I had 60,000 odd jars downloaded on my hard-drive and ready to analyze. Mining Maven central programmatically is interesting enough to deserve an article of its own. Stay tuned for that. I wrote a simple program to then read the jars and parse all class names into its constituent pieces. I owe the parsing of the names to a clever bit of regex that I found on Stackoverflow. Its only fitting that the answer was by a user named poly-gene-lubricants!

Here are some findings from parsing the names:

1. It looks like we software engineers are an ego-centric bunch. While I found 2,487 references to “My” in classnames, I only found 4 references to “Your.”
2. The most common word was … Type! A whopping 107,246 times. But that is from a total of 6,906,643 words.
3. We seem to be doing a good job of separating interfaces from implementation as evidenced by the close runner up - Impl - with 102,786 references.
4. We like our fruits - Fruit (18), Apple (133), Berry (36), Banana (12), Peach (2), Mango (35) and Grape (23). And we have some die-hard screaming fans of APPLE (23).
5. We do not like our vegetables. Perhaps those who’s mothers fail to impress upon them the importance of eating vegetables end up as engineers? The first lady may want to take note! Broccoli (0), Spinach (0), Squash (5). Who are these wierdo squash lovers?
6. But we do like meat! Meatball (1), Meat (2), Chicken (58), Beef (2). I shudder to use the Chicken library.
7. Oh and we like cheese with that (36).
8. Some of us secretly wish we were in the Restaurant business: Cook (19), Waiter (84), Server (17,166), Host (4,772) and Janitor (30). I found no reference to Hostess, proof positive that we do have a gender problem in tech!
9. If we started a zoo, we’d find: Pandas (1), Monkeys (20), Tigers (83), Dogs (132), Cats (351), Snakes (95), Donkeys (5), Zebras (26), Horses (28), Cows (68), Elephants (19), Giraffes (10) and Lions (21).
10. Is there a lot of workplace violence associated with software development? There really ought to be more - Punch (39), Beat (49), Box (4,993), Poke (6) and Kick (20).
11. Among unusual names, I found:
    1. Valorizer - since nerdy engineer and valor never appear in the same sentence together.
    2. Dateless - a reference to the bespectacled geek in the office.
    3. Datefind - the geek’s attempt to cure the above stated malady.
    4. Autodate - When the geek resorts to chatting with an IM bot.
    5. Ntpdate - What a geek does to schedule the one accidental date he lands.
    6. Undated - The result of the one accidental date.
    7. Unblack - pseudonym for Michael Jackson?
    8. Pockuito - A delectable Polish sausage recommended with Prosciutto.
    9. Sweetener - A class used to make you sign the employment agreement.
    10. Cobbled - A general reference to the way most software is put together. Shame! only one guy was willing to admit it.
    11. Monotonous - Denotes a class with a lot of copy-n-paste!
    12. Seniority - Hooray! We don’t have an age problem in IT. Oh wait! There was only one reference to it.
    13. Switcheroo - Evidence we didn’t pay attention during English class.
    14. Duplciate - More evidence we didn’t pay attention during English class.
    15. Boogaloo - A disruptive software solution to the Ghostbusters.
    16. Anonymizing - What the author of Boogaloo did.
    17. Absolutechildren - Remnant of someone’s militaristic upbringing.
    18. Delinquency - Unfortunately not of the juvenile (0) type.
    19. Greenish - a sophisticated word in the male vocabulary for Teal.

There are 2,760 class names that are greater than 50 characters in length. Among the largest are:

• “Has This Type Pattern Tried To Sneak In Some Generic Or Parameterized Type Pattern matching Stuff Anywhere Visitor” (from Apache ServiceMix aspectJ 1.8.0)
• “Web Get Number Of Parent Process Instances With Active User And Activity Instance Expected End Date” (from Bonita Server 5.10.2)

I would have loved to be a fly on the wall when these names were being discussed!

The raw class component names data is available as a CSV file.

Statutory Disclaimer: This post is simply an exercise in algorithm development. It is not a warrant to attempt to cheat while playing Wordament. Any attempt to cheat the game will get you booted. The booting will be well deserved and this blog takes no responsibility for it.

Game Time

Wordament is a very popular word puzzle that is available on all the mobile app stores. The object of the game is to identify as many words as possible from a 4x4 grid of letters. Words are formed by sliding your finger on the letters. You can form words by moving in any direction as long as you don’t repeat the letters. You get points for your words - longer words earn more points and there are special bonuses for uncommon words and words that contain letter sequences that are specifically called out.

A first time casual player will be simultaneously astounded at the number of words identified by the winners of any given round and embarrassed by their own dismal performance. In fact, the winners are jaw-droppingly fast. Have a look at this video of a face-off (or is that word-off?):

Some of us speed-challenged folks, especially the geeks at heart may consider instead the challenge of algorithmically finding all the words. The problem is relatively straightforward and with adequate setup may even make a great interview question. If you do use this as an interview question, I would strongly suggest letting the candidate program on a computer with an IDE/language of their choice and not on a whiteboard.

Word Bank

First we need a database of valid words. Here are a couple of sources to get such a list of words:

• SIL English Wordlist
• SCOWL dictionary

At a high-level, our task will be to navigate the grid adding letters to a sequence and testing if what we have is a valid word. Our challenge is to:

1. Ensure that we navigate all permutations of the letters.
2. Not visit any letter more than once.
3. Determine if the sequence of letters we have is a valid word.

The last step is straightforward. We can simply load the entire list of valid words into a HashMap and check to see if the word we’ve assembled is valid. However, for our purpose, we are going to eschew the HashMap based approach and instead construct a tree of valid words such that we can more efficiently figure out if a word is valid or not. From a practical computational standpoint, this extra optimization is not going to make a material difference. However, the optimization does have academic value.

From Word Bank to Word Tree

We will construct our word tree by creating nodes that have two properties:

1. A letter value.
2. An index of up to 26 child nodes, one per letter that can follow the current node.
3. A flag that indicates if the path from the root to the current node represents a valid word.

We use two classes to construct the nodes, a NodeLoader and the Node itself. The code for these classes is shown below:

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
public class NodeLoader {

	
	public static Node init() throws IOException {
        // LineIterator and FileUtils are from apache commons io.

		LineIterator iterator = FileUtils.lineIterator(new File("src/main/resources/dict.txt"));
		
		Node root = new Node();
		root.setWord(false);
		
		while (iterator.hasNext()) {
			String line = iterator.next().toLowerCase().trim();
			createNodes(line, root, 0).setWord(true);
		}
		
		return root;
	}
	

	private static Node createNodes(String line, Node current, int index) {
		if (index != line.length()) {
			Node next = current.createOrGet(line.charAt(index));
			return createNodes(line, next, index+1);
		} else {
			return current;
		}
	}
}

Notice that root node does not represent a letter. In fact, the Nodes don’t explicitly represent a letter. The letter representation is implicit from their position in the parent. For example, the sequence from the root node of the first child node, its second child node and its third child node represent the letter sequence ‘abc’.

The Node is a simple class of mostly boilerplate code (please Oracle, if you are listening, at least add Lombok style @Getter/@Setter annotations to Java 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
public class Node {

    private boolean word;

    private Node[] branches = new Node[26];


    public boolean isWord() {
        return word;
    }


    public void setWord(boolean word) {
        this.word = word;
    }


    public Node getNode(char c) {
        int i = c - 'a';
        return branches[i];
    }


    public Node createOrGet(char c) {
        Node n = getNode(c);
        if (n == null) {
            n = new Node();
            branches[c - 'a'] = n;
        }

        return n;
    }
}

“Wording” it together

Armed with our word-tree, we can now write the grid input and traverse logic. For reading in the input, we will require the user to type in four lines of letters with each line containing 4 letters. We can then parse the letters and put them into a two-dimensional array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        	Node root = NodeLoader.init();
        Scanner scanner = new Scanner(System.in);
        char grid[][] = new char[4][4];
        String parts[] = new String[4];

        parts[0] = scanner.nextLine();
        parts[1] = scanner.nextLine();
        parts[2] = scanner.nextLine();
        parts[3] = scanner.nextLine();

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                grid[i][j] = parts[i].charAt(j);
            }
        }

With the grid initialized we now have to traverse the grid. Our grid traversal must consider every location in the grid as a starting point. As we traverse the grid and identify valid words, we add it to a set (thus eliminating duplicates). Once the words have all been identified, we can sort them by length and print them. At a high level, assuming a “traverse” method, the code required is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
       for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                traverse(grid, new boolean[4][4], i, j, root, "");
            }
        }

        List<String> temp = new ArrayList<String>(wordsFound);
        Collections.sort(temp, new Comparator<String>() {

            public int compare(String o1, String o2) {
                return o2.length() - o1.length();
            }
        });
        for (String word : temp) {
            System.out.println(word);
        }

The variable wordsFound is simple HashSet. The only thing left to flush out is the traverse routine. Grid traversal is easily written as a recursive routine. Our job is to consider the current location, add the letter to the sequence by grabbing the appropriate child node of the current node (indexed by the letter) and seeing if the node represents a complete word. If it does, we add it to our list of valid words and then try to traverse by moving in each of the 8 different directions we can head in (left, right, up, down, diagonally to the top-right, top-left, bottom-right and bottom-left).

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
/**
     * @param grid The grid of letters representing the game.
     * @param visited A grid of indicators telling us which letters have already been visited.
     * @param i Our current location in the grid. x-axis
     * @param j Our current location in the grid. y-axis
     * @param node The node we have just visited.
     * @param current The currently formulated word.
     */
    private static void traverse(char[][] grid, boolean[][] visited, int i, int j, Node node, String current) {
        char c = grid[i][j];
        String newStr = current + Character.toString(c);
        Node next = node.getNode(c);

        if (next != null) {
            visited[i][j] = true;
            if (next.isWord() && newStr.length() > 2) {
                wordsFound.add(newStr);
            }

            if (j < 3 && !visited[i][j + 1]) {
                traverse(grid, visited, i, j + 1, next, newStr);
            }
            if (i < 3 && !visited[i + 1][j]) {
                traverse(grid, visited, i + 1, j, next, newStr);
            }
            if (j > 0 && !visited[i][j - 1]) {
                traverse(grid, visited, i, j - 1, next, newStr);
            }
            if (i > 0 && !visited[i - 1][j]) {
                traverse(grid, visited, i - 1, j, next, newStr);
            }
            if (i < 3 && j < 3 && !visited[i + 1][j + 1]) {
                traverse(grid, visited, i + 1, j + 1, next, newStr);
            }
            if (i < 3 && j > 0 && !visited[i + 1][j - 1]) {
                traverse(grid, visited, i + 1, j - 1, next, newStr);
            }
            if (i > 0 && j > 0 && !visited[i - 1][j - 1]) {
                traverse(grid, visited, i - 1, j - 1, next, newStr);
            }
            if (i > 0 && j < 3 && !visited[i - 1][j + 1]) {
                traverse(grid, visited, i - 1, j + 1, next, newStr);
            }
            visited[i][j] = false;
        }

    }

Here is a sample run. The letters entered are:

abcd
efgh
ijkl
mnop

This gives us the following words:

• knife
• plonk
• glop
• mink
• jink
• fink
• fab
• ink
• fin
• lop

The complete code is available at Github. The code comes with a plea to use it to further academic interest in such puzzle solvers and not to get cheap thrills from cheating in the real game.

DSLs allow a programmer to tailor-make keywords and syntax to express a higher abstract representation of a problem domain. Recognizing the power of DSLs, most modern JVM languages have taken to support them. Scala, Groovy and the up-and-coming Ceylon all support writing DSLs.

Recently I needed to build a Groovy DSL to facilitate some complex data setup for executing automated scenario tests. The GroovyBuilder mechanism wasn’t to my liking as it seemed too closely tied to object instantiation and the canonical constructor syntax. While researching other options I came across Steven Devijver’s post on creating Groovy DSLs. Steve’s technique works by defining a closure to bootstrap the script execution and redirecting method resolution using delegate modification and prioritization. The idea while intriguing had two aspects that didn’t fit well with my requirement:

1. There wasn’t an easy way to supply the closure to a self-contained “DSL executor.”
2. I would have to provide closure definitions for every top-level method I wanted to have in my DSL.

My ideal solution would involve giving a self-contained DSLExecutor object a script filename and a handler object that had the method definitions for the script. I decided to dig through Spring’s GenericGroovyApplicationContext that provides a DSL for Spring context configuration and the groovy.lang.Script class for inspiration and clues to achieve this. Spring’s Groovy context loader takes advantage of the fact that the groovy.lang.Script class, using an overridden invoke method, attempts to see if the Binding object has a closure definition of the same name as the method that just failed to resolve:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Object invokeMethod(String name, Object args) {
    try {
        return super.invokeMethod(name, args);
    }
    // if the method was not found in the current scope (the script's methods)
    // let's try to see if there's a method closure with the same name in the binding
    catch (MissingMethodException mme) {
        try {
            if (name.equals(mme.getMethod())) {
                Object boundClosure = getProperty(name);
                if (boundClosure != null && boundClosure instanceof Closure) {
                    return ((Closure) boundClosure).call((Object[])args);
                } else {
                    throw mme;
                }
            } else {
                throw mme;
            }
        } catch (MissingPropertyException mpe) {
            throw mme;
        }
    }
}

Combining ideas from Steve’s post, Spring and the groovy.lang.Script implementations, I realized that by supplying the groovy.lang.Script’s metaclass with a methodMissing closure, I can effectively route unmatched methods to any arbitrary object. The result is a simple standalone DSL executor:

The DSLExecutor.execute() method accepts a script filename and a handler object. The script is resolved using Spring’s resource loader (you can therefore prefix the filename with classpath: or other prefixes that Spring supports). The handler object is expected to have methods for your constructs in the DSL. The execute() method returns a map of variables returned by the script.

A simple example of a handler is shown below:

1
2
3
4
5
6
7
class MyHandler {

   def printMe(String name, Closure cl) {
		println "Hello $name"
        cl(name)
   }
}

The above code allows a simple DSL of the form:

1
2
3
printMe "Dude" {
    println it
}

We can extend the handler paradigm by making it hierarchical, wherein the handler delegates processing of some methods to a more specialized handler. For example, if our DSL had a section dealing with users, we may want to be able to write a construct such as:

1
2
3
4
5
6
7
8
9
10
printMe "Dude" {
   println it
}

users {
    tom = create "Tom"
    login tom {
        it.setRememberMe()
    }
}

We may want to segregate the responsibility for all user related methods to a UserHandler class. This is easily achieved within the primary handler by setting the delegate on the closure supplied to the users method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class UserHandler {
   // ... various methods
}

class MyHandler {

   def printMe(String name, Closure cl) {
	println "Hello $name"
        cl(name)
   }

   def users(Closure c) {
       UserHandler handler = new UserHandler()
       c.delegate = handler
       c.resolveStrategy = Closure.DELEGATE_FIRST
       c()
   }
}

We thus have yet-another-DSL construction paradigm using Groovy. I hope other folks find this useful and are able to create some elegant tailor-made DSLs with it.

Spring has a number of utilities that the framework ships with. One of them is a classpath scanner provided by ClassPathScanningCandidateComponentProvider. That is a long name and a mouthful. The class allows you to enable auto-discovery features in your own framework or code. Here is a simple example to demonstrate its use:

The constructor takes a boolean parameter to apply default filters or not. Default filters are based on annotations for @Component, @Repository, @Service and @Controller. Once you have your provider, you give it filters to zero-in on the types you are interested in. Filters implement the TypeFilter interface and Spring helpfully ships with a number of useful ones:

• AnnotationTypeFilter: filters based on annotations on the class.
• AssignableTypeFilter: filters that match based on superclass or interface.
• RegexPatternTypeFilter: matches a fully qualified class name against a regular expression.

Spring also has an AbstractClassTestingTypeFilter that allows you to write your own matcher against class metadata that spring provides for each Class/Interface that it finds.

Once you have your filters defined, you simply give the scanning provider a root package to search within and it returns you a list of BeanDefinition objects for matches. You may incorrectly assume, because of the name BeanDefinition, that this is restricted to beans in a Spring context. Thankfully, it is not, as that would severely restrict the utility value of this class. The BeanDefinition is simply a container of useful information about the class including the Class instance.