title: Java program to identify patterns in numbers
body: <p>I am looking to create a program that would identify certain patterns in numbers. I am not sure if this needs an algorithm or just carefully thought out programming. I am not looking for someone to provide source code, just some thought provoking ideas to start me in the right direction.</p>
  
  <p>Numbers will be fixed length of 6 digits from 000000 to 999999. I guess each number would be stored as part of an array. I would then like to test the number against a pattern. </p>
  
  <p>For example lets say the 3 patterns I am using are </p>
  
  <pre><code>A A A A A A - would match such examples as 111111 , 222222, 333333 etc where 
  A B A B A B - would match such examples as 121212 , 454545, 919191 etc
  A (A+1) (A+2) B (B+1) (B+2) - would match such examples as 123345, 789123, 456234
  </code></pre>
  
  <p>I guess the part that I am stuck on is how to allocate each part of the integer array to a value such as A or B</p>
  
  <p>My initial thoughts would be just to allocate each part as an individual letter. So if the array consisted of 1 3 5 4 6 8, then I would create a map like </p>
  
  <pre><code>A=1
  B=3
  C=5
  D=4
  E=6
  F=8
  </code></pre>
  
  <p>Then some how take the first pattern, </p>
  
  <pre><code>AAAAAA
  </code></pre>
  
  <p>and test with something like if (AAAAAA = ABCDEF) then we have matched AAAAAAA</p>
  
  <p>if not then try (ABABAB = ABCDEF) etc through all my patterns</p>
  
  <p>In this scenario there is no reason why the value assigned to C cant be the same as the value assigned to F like in the number 234874.</p>
  
  <p>I am not sure if this will even make sense to anyone but I guess I can refine my question based on feedback.</p>
  
  <p>In summary, I am looking for ideas on how to have a program accept a 6 digit number and return back to us which pattern it matched.</p>
  
  <p>SOLUTION</p>
  
  <p>After the comments given put me on a good track below is what i created as a final solution. </p>
  
  <pre><code>package com.doyleisgod.number.pattern.finder;
  
  import java.io.File;
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.Map;
  import javax.xml.parsers.DocumentBuilder;
  import javax.xml.parsers.DocumentBuilderFactory;
  import org.w3c.dom.Document;
  import org.w3c.dom.Element;
  import org.w3c.dom.Node;
  import org.w3c.dom.NodeList;
  
  
  public class FindPattern {
  private final int[] numberArray; //Array that we will match patterns against.
  private final Document patternTree = buildPatternTree(); //patternTree containing all the patterns
  private final Map&lt;String, Integer&gt; patternisedNumberMap; //Map used to allocate ints in the array to a letter for pattern analysis
  private int depth = 0; //current depth of the pattern tree
  
  // take the int array passed to the constructor and store it in out numberArray variable then build the patternised map
  public FindPattern (int[] numberArray){
      this.numberArray = numberArray;
      this.patternisedNumberMap = createPatternisedNumberMap();
  }
  
  //builds a map allocating numbers to letters. map is built from left to right of array and only if the number does not exist in the map does it get added
  //with the next available letter. This enforces that the number assigned to A can never be the same as the number assigned to B etc
  private Map&lt;String, Integer&gt; createPatternisedNumberMap() {
      Map&lt;String, Integer&gt; numberPatternMap = new HashMap&lt;String, Integer&gt;();
  
      ArrayList&lt;String&gt; patternisedListAllocations = new ArrayList&lt;String&gt;();
      patternisedListAllocations.add("A");
      patternisedListAllocations.add("B");
      patternisedListAllocations.add("C");
      patternisedListAllocations.add("D");
      Iterator&lt;String&gt; patternisedKeyIterator = patternisedListAllocations.iterator();
  
      for (int i = 0; i&lt;numberArray.length; i++){
          if (!numberPatternMap.containsValue(numberArray[i])) {
              numberPatternMap.put(patternisedKeyIterator.next(), numberArray[i]);
          } 
      }
      return numberPatternMap;
  }
  
  //Loads an xml file containing all the patterns.
  private Document buildPatternTree(){
      Document document = null;
      try {
      File patternsXML = new File("c:\\Users\\echrdoy\\Desktop\\ALGO.xml");
      DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
      DocumentBuilder db = dbf.newDocumentBuilder();
      document = db.parse(patternsXML);
  
      } catch (Exception e){
          e.printStackTrace();
          System.out.println("Error building tree pattern");
      }
      return document;
  }
  
  //gets the rootnode of the xml pattern list then called the dfsnodesearch method to analyse the pattern against the int array. If a pattern is found a
  //patternfound exception is thorwn. if the dfsNodeSearch method returns without the exception thrown then the int array didn't match any pattern
  public void patternFinder() {
      Node rootnode= patternTree.getFirstChild();
      try {
          dfsNodeSearch(rootnode);
          System.out.println("Pattern not found");
      } catch (PatternFoundException p) {
          System.out.println(p.getPattern());
      }
  }
  
  //takes a node of the xml. the node is checked to see if it matches a pattern (this would only be true if we reached the lowest depth so must have 
  //matched a pattern. if no pattern then analyse the node for an expression. if expression is found then test for a match. the int from the array to be tested
  //will be based on the current depth of the pattern tree. as each depth represent an int such as depth 0 (i.e root) represent position 0 in the int array
  //depth 1 represents position 1 in the int array etc. 
  private void dfsNodeSearch (Node node) throws PatternFoundException {
      if (node instanceof Element){
          Element nodeElement = (Element) node;
          String nodeName = nodeElement.getNodeName();
  
          //As this method calls its self for each child node in the pattern tree we need a mechanism to break out when we finally reach the bottom
          // of the tree and identify a pattern. For this reason we throw pattern found exception allowing the process to stop and no further patterns.
          // to be checked.
          if (nodeName.equalsIgnoreCase("pattern")){
              throw new PatternFoundException(nodeElement.getTextContent());
          } else {
              String logic = nodeElement.getAttribute("LOGIC");
              String difference = nodeElement.getAttribute("DIFFERENCE");
  
              if (!logic.equalsIgnoreCase("")&amp;&amp;!difference.equalsIgnoreCase("")){
                  if (matchPattern(nodeName, logic, difference)){
                      if (node.hasChildNodes()){
                          depth++;
                          NodeList childnodes = node.getChildNodes();
                          for (int i = 0; i&lt;childnodes.getLength(); i++){
                              dfsNodeSearch(childnodes.item(i));
                          }
                          depth--;
                      }
                  } 
              }
          }
  
  
      }
  }
  
  //for each node at a current depth a test will be performed against the pattern, logic and difference to identify if we have a match. 
  private boolean matchPattern(String pattern, String logic, String difference) {
      boolean matched = false;
      int patternValue = patternisedNumberMap.get(pattern);
  
      if (logic.equalsIgnoreCase("+")){
          patternValue += Integer.parseInt(difference);
      } else if (logic.equalsIgnoreCase("-")){
          patternValue -= Integer.parseInt(difference);
      }
  
      if(patternValue == numberArray[depth]){
          matched=true;
      }
  
      return matched;
  }
  
  
  }
  </code></pre>
  
  <p>the xml list of patterns looks like this</p>
  
  <pre><code>&lt;?xml version="1.0"?&gt;
  &lt;A LOGIC="=" DIFFERENCE="0"&gt;
      &lt;A LOGIC="=" DIFFERENCE="0"&gt;
          &lt;A LOGIC="=" DIFFERENCE="0"&gt;
              &lt;A LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(A)(A)(A)&lt;/pattern&gt;
              &lt;/A&gt;
              &lt;B LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(A)(B)(A)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/A&gt;
          &lt;B LOGIC="=" DIFFERENCE="0"&gt;
              &lt;A LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(A)(B)(A)&lt;/pattern&gt;
              &lt;/A&gt;
              &lt;B LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(A)(B)(B)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/B&gt;
      &lt;/A&gt;
      &lt;A LOGIC="+" DIFFERENCE="2"&gt;
          &lt;A LOGIC="+" DIFFERENCE="4"&gt;
              &lt;A LOGIC="+" DIFFERENCE="6"&gt;
                  &lt;pattern&gt;(A)(A+2)(A+4)(A+6)&lt;/pattern&gt;
              &lt;/A&gt;
         &lt;/A&gt;
      &lt;/A&gt;
      &lt;B LOGIC="=" DIFFERENCE="0"&gt;
          &lt;A LOGIC="+" DIFFERENCE="1"&gt;
              &lt;B LOGIC="+" DIFFERENCE="1"&gt;
                  &lt;pattern&gt;(A)(B)(A+1)(B+1)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/A&gt;
          &lt;A LOGIC="=" DIFFERENCE="0"&gt;
              &lt;A LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(B)(A)(A)&lt;/pattern&gt;
              &lt;/A&gt;
              &lt;B LOGIC="+" DIFFERENCE="1"&gt;
                  &lt;pattern&gt;(A)(B)(A)(B+1)&lt;/pattern&gt;
              &lt;/B&gt;
              &lt;B LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(B)(A)(B)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/A&gt;
          &lt;B LOGIC="=" DIFFERENCE="0"&gt;
              &lt;A LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(B)(B)(A)&lt;/pattern&gt;
              &lt;/A&gt;
              &lt;B LOGIC="=" DIFFERENCE="0"&gt;
                  &lt;pattern&gt;(A)(B)(B)(B)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/B&gt;
          &lt;A LOGIC="-" DIFFERENCE="1"&gt;
              &lt;B LOGIC="-" DIFFERENCE="1"&gt;
                  &lt;pattern&gt;(A)(B)(A-1)(B-1)&lt;/pattern&gt;
              &lt;/B&gt;
          &lt;/A&gt;
      &lt;/B&gt;
      &lt;A LOGIC="+" DIFFERENCE="1"&gt;
          &lt;A LOGIC="+" DIFFERENCE="2"&gt;
              &lt;A LOGIC="+" DIFFERENCE="3"&gt;
                  &lt;pattern&gt;(A)(A+1)(A+2)(A+3)&lt;/pattern&gt;
              &lt;/A&gt;
          &lt;/A&gt;
      &lt;/A&gt;
      &lt;A LOGIC="-" DIFFERENCE="1"&gt;
          &lt;A LOGIC="-" DIFFERENCE="2"&gt;
              &lt;A LOGIC="-" DIFFERENCE="3"&gt;
                  &lt;pattern&gt;(A)(A-1)(A-2)(A-3)&lt;/pattern&gt;
              &lt;/A&gt;
          &lt;/A&gt;
      &lt;/A&gt;
  &lt;/A&gt;
  </code></pre>
  
  <p>and my pattern found exception class looks like this </p>
  
  <pre><code>package com.doyleisgod.number.pattern.finder;
  
  public class PatternFoundException extends Exception {
  private static final long serialVersionUID = 1L;
  private final String pattern;
  
  public PatternFoundException(String pattern) {
      this.pattern = pattern;
  }
  
  public String getPattern() {
      return pattern;
  }
  
  }
  </code></pre>
  
  <p>Not sure if any of this will help anyone with a similar problem or if anyone has any comments on how this is working would be great to hear them.  </p>