Game combo press model (substring search)

Question

I'm trying to make a model for checking combo presses in a game. Given a list of Button (enum) presses, it returns the list of possible combos completed. I tried using a suffix tree, but I'm not sure if this is the best solution. It's also my first time writing a suffix tree, and I don't know if this is the correct usage.

Also, could someone help me analyze the runtime of registering combos and searching combos? I think registering combos is O(n), but what about searching for combos?

Button enum:

public enum Button {
 Left, Right, Down, Up, A, B, X, Y;
}

Registering combos and for searching for the completed combos:

public class SuffixTree {
 private class SuffixTreeNode {
 Map<Button, SuffixTreeNode> children = new HashMap<Button, SuffixTreeNode>();
 List<Button> indices = new ArrayList<Button>();
 public void insert(List<Button> lob) {
 if (lob != null && lob.size() > 0) {
 indices.add(lob.get(0));
 Button value = lob.get(0);
 SuffixTreeNode child = null;
 if (children.containsKey(value)) {
 child = children.get(value);
 } else {
 child = new SuffixTreeNode();
 children.put(value, child);
 }
 List<Button> remainder = lob.subList(1, lob.size());
 child.insert(remainder);
 }
 }
 public List<Button> search(List<Button> lob, List<Button> parents) {
 if (lob == null || lob.isEmpty()) {
 return parents;
 } else {
 Button first = lob.get(0);
 if (children.containsKey(first)) {
 parents.add(first);
 List<Button> remainder = lob.subList(1, lob.size());
 return children.get(first).search(remainder, parents);
 }
 }
 return null;
 }
 }
 SuffixTreeNode root = new SuffixTreeNode();
 public void registerCombos(List<List<Button>> combos) {
 for (List<Button> combo : combos) {
 root.insert(combo);
 }
 }
 public List<List<Button>> search(List<Button> buttonPresses) {
 List<List<Button>> res = new ArrayList<List<Button>>();
 int len = buttonPresses.size();
 for (int i = 0; i < len; i++) {
 List<Button> partial = root.search(buttonPresses.subList(i, len), new ArrayList<Button>());
 if (partial != null && !partial.isEmpty()) {
 res.add(partial);
 }
 }
 return res;
 }
}

Answer 1

Bug

Since you never mark your suffix tree nodes as end nodes, your search will find combos that don't exist. For example, if ABXY is a registered combo, and you search for AB, it will return both A and AB as combos. You should have a boolean per node telling you whether the node is the end of a combo or not.

Efficiency

You appear to search for all sublists that end with the end of the original list. For example, if the original search list were ABXY,you would search for these sublists: ABXY BXY XY Y.

Given this behavior, you could greatly improve your suffix tree by storing the combos in reverse order. Then, when you want to search for a given list and all of its sublists, you search the suffix tree once in reverse order. For example, given ABXY, you search the suffix tree for YXBA and return up to four combos that match (Y YX YXB YXBA). This would reduce your search from \$O(n^2)\$ to \$O(n)\$.

How to mark end nodes

This is in response to the comment. Given a tree with combos A B X Y ABXY, the tree would look like this:

 Root
 / | | \ 
 A* B* X* Y*
 B
 X
 Y*

In the tree above, the end nodes are marked with a *. So if you searched for combo AB, it would go down the left branch from the root but it would not find a combo because the node B on the left branch does not have a *.

Why searching in reverse order is more efficient

Suppose you are given combos A B X Y ABXY. If you reversed each combo and added to a tree, your tree would look like:

 Root
 / | | \ 
 A* B* X* Y*
 X
 B
 A*

Now suppose you were given ABXY as your search list, meaning you actually want to search for the four sublists ABXY BXY XY Y. You could do this in one search by searching for YXBA and returning a positive match every time you find an end node. So in the tree above, you would follow the rightmost path four levels, passing by the lists Y YX YXB YXBA. Since Y and A are marked as end nodes, you would return Y and YXBA as matches. After reversing, these would correspond to Y and ABXY as matches. Notice that you only have to traverse the tree once instead of 4 times.

• fluffychaos: Thanks for pointing out the bug! I'm confused about marking the nodes as end of combos. Where exactly would I mark the nodes? Let's say I have the combos "A," "B," "X," "Y," and "ABXY." Since each of ABXY is a combo by itself, each of the ABXY nodes would be marked true. Thus, A AB ABX and ABXY would all be returned as combos. Would I need to make a wrapper just to mark whether these are truly combos?
• JS1: @fluffychaos See my latest edit.
• fluffychaos: Thank you! Makes sense now :) Do you mind explaining the efficiency gain again? Right now I changed my implementation so that the tree is in reverse order, and I'm also searching in reverse order (e.g. for ABXY, start by searching for YXBA, then YXB, then YX, then Y). How is this more efficient that searching for ABXY, BXY, XY, and Y?
• JS1: @fluffychaos See my latest edit again.
• fluffychaos: I think I understand now. Just to confirm, you're saying that I don't need to use subList() to go through ABXY, BXY, XY, and Y, is that correct? I simply iterate through ABXY, checking if the current button is contained in the children. If it is, add it to the result if it's the end of a combo and keep iterating. If not, break and return results immediately. Is this correct?

Answer 2

Sometimes order matters

 indices.add(lob.get(0));
 Button value = lob.get(0);

This would seem more sensible as

 Button value = lob.get(0);
 indices.add(value);

Then you don't repeat the same (rather efficient) operation twice. It's quite possible that the compiler would do this for you, but why rely on that?

Some operations obviate others

 SuffixTreeNode child = null;
 if (children.containsKey(value)) {
 child = children.get(value);
 } else {
 child = new SuffixTreeNode();
 children.put(value, child);
 }

This could be

 SuffixTreeNode child = children.get(value);
 if (child == null) {
 child = new SuffixTreeNode();
 children.put(value, child);
 }

You don't have to do a containsKey before doing a get, as get will do the same check for you. So just do the get and check the result before using it.

No need for an else after a return

 if (lob == null || lob.isEmpty()) {
 return parents;
 } else {

You don't need the else here since you return in the then case. So the code only runs if the condition is not true.

Getting rid of the else gets rid of a level of indent too. That can help readability sometimes, particularly in convoluted methods.

Complexity analysis

What's \$n\$? You say that you think that registerCombos is \$\mathcal{O}(n)\,ドル but what is \$n\$? Is it the number of combos that you are currently registering? The length of the combos? All registered combos? That method is linear in the total number of button presses in all the combos added. So that's \$n\$. The reason why it's linear in the number of button presses is that the insert method consumes one button press for each recursive call.

The search method is \$\mathcal{O}(n^2)\$ because it calls root.search once for each button press and that search calls itself button press times in the worst case.