Tree game validator

by ishanpm

HTML

<textarea id="text" style="width:500px; height:300px;"></textarea>
<div></div>
<button onclick="validate1()">Validate</button>
<!-- legalMoves doesn't work yet
<div></div>
<button onclick="listMoves1()">Legal moves</button>
<label><input id="allow0" type="checkbox" checked>()</label>
<label><input id="allow1" type="checkbox" checked>&lt;></label>
<label><input id="allow2" type="checkbox" checked>[]</label>
<label><input id="allow3" type="checkbox">{}</label>
<label><input id="allow4" type="checkbox">/\</label> -->
<p id="output" style="font-family:monospace;"></p>
<p id="desc">
TREE(k) game validator (see <a href="https://cp4space.wordpress.com/2012/12/19/fast-growing-2/">https://cp4space.wordpress.com/2012/12/19/fast-growing-2/</a>)<br><br>
Each line may contain one tree, consisting of matched pairs of these brackets: () &lt;> [] {} /\<br>
Other characters and lines with none of these characters are ignored.<br>
A tree must have a single root node, i.e. the first and last bracket must match.<br>
The first tree can only have one node, the second can have at most 2, the third at most 3, and so on.<br>
A tree "contains" another tree if it can be transformed into the other using these actions:<br>
- Reorder the children of any node: [(){}] ->  [{}()]<br>
- Delete a node and all of its children: [(){}] -> [{}]<br>
- Delete a node and all but one of its children: [(){}] -> ()<br>
No tree can "contain" an earlier tree (but containing a later tree is fine).<br>
Click "Validate" to make sure a game follows the rules.<br>
</p>

JavaScript

var startBrackets = '(<[{/';
var endBrackets   = ')>]}\\';

// Ridiculously naive tree matching algorithm
// Checks if `match` can be homeomorphically embedded into `tree`
function containsTree(tree,match) {
  if (match == null) return true;
  if (tree == null) return false;
  
  // Check if this node matches
  if (tree.color == match.color) {
    // Check if children match children
    if (match.s.length == 0) {
      // All children matched
      return true;
    }
    
    // Try to match the first child
    var matchCopy = {color:match.color, s:match.s.filter((e,i)=>i!=0)}
    
    for (var i=0; i<tree.s.length; i++) {
      if (containsTree(tree.s[i], match.s[0])) {
        var treeCopy = {color:tree.color, s:tree.s.filter((e,k)=>k!=i)}
        if (containsTree(treeCopy, matchCopy)) return true
      }
    }
  }
  
  // Check if children match
  for (s of tree.s) {
    if (containsTree(s, match)) return true
  }
  
  return false;
}

// Convert matched bracket representation of a tree to an actual tree
function treeify(str) {
  
  var root = null;
  var stack = [];
  var last = null; // Last item of stack
  
  for (c of str) {
    var color = startBrackets.indexOf(c);
    if (color > -1) {
      // Add node
      var node = {color:color,s:[]};
      if (!last) {
        if (!root) {
          root = node;
        } else {
          throw "Too many root nodes"
        }
      }
      if (last) {
        last.s.push(node)
      }
      stack.push(node);
      last = node;
    } else {
      color = endBrackets.indexOf(c);
      if (color > -1) {
        // Close node
        if (!last) throw "Tried to close past root node"
        if (color !== last.color) throw "Incorrect closing bracket"
        stack.pop();
        if (stack.length > 0) {
          last = stack[stack.length-1];
        } else {
          last = null;
        }
      } else {
        // Invalid character, ignore it
      }
    }
  }
  
  if (stack.length != 0) throw "Unclosed node"
  
 ...