Background
I’ve been working on a AI project today and came across this problem.
Given input data structured like so:
[‘A’, [‘B’, (‘D’, 3), (‘E’, 5)], [‘C’, [‘F’, [‘I’,(‘K’,0), (‘L’, 7)],(‘J’,5)], [‘G’, (‘M’,7), (‘N’,8)], (‘H’,4)]]
I need to parse and build tree which has an arbitrary branching factor, and values only at the leaves.
(As for why: Later, I’ll be running Minimax and some other algorithms on this tree, in order to algorithmically determine the best possible game move. More on that in another post.)
This seemed like a good problem to solve recursively. And to avoid a soul-sucking debug session, I decided my goal was to solve it as succinctly as possible.
Here’s what I came up with. Why I’m posting: This seems like it would be a very common AI/Data-Structures problem, but my first few searches on the subject came up with nada. Nothing even closely related to the problem I’m solving. So doing my part to fix that now.
Working Code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ @author Tony Poerio | |
| @email tony@tonypoer.io | |
| tree_parser.py –> parse a nested data string into a tree. | |
| Only leaf nodes have values. | |
| I'm intending to running minimax algorithms on these trees for a competitive game AI | |
| Data should be in the following format: | |
| ['A', ['B', ('D', 3), ('E', 5)], ['C', ['F', ['I',('K',0), ('L', 7)],('J',5)], ['G', ('M',7), ('N',8)], ('H',4)]] | |
| Note that Leaves must be **tuples** | |
| Usage: python tree_parser.py [filename] | |
| File should have data in the format shown above. | |
| """ | |
| from ast import literal_eval | |
| import sys | |
| ########################## | |
| ###### PARSE DATA ######## | |
| ########################## | |
| def parse_data_as_list(fname): | |
| with open(fname, "r") as f: | |
| data_as_string = f.read() | |
| print data_as_string | |
| data_list = literal_eval(data_as_string) | |
| return data_list | |
| class GameNode: | |
| def __init__(self, name, value=0, parent=None): | |
| self.Name = name # a char | |
| self.value = value # an int | |
| self.parent = parent # a node reference | |
| self.children = [] # a list of nodes | |
| def addChild(self, childNode): | |
| self.children.append(childNode) | |
| class GameTree: | |
| def __init__(self): | |
| self.root = None | |
| def build_tree(self, data_list): | |
| """ | |
| :param data_list: Take data in list format | |
| :return: Parse a tree from it | |
| """ | |
| self.root = GameNode(data_list.pop(0)) | |
| for elem in data_list: | |
| self.parse_subtree(elem, self.root) | |
| def parse_subtree(self, data_list, parent): | |
| # base case | |
| if type(data_list) is tuple: | |
| # make connections | |
| leaf_node = GameNode(data_list[0]) | |
| leaf_node.parent = parent | |
| parent.addChild(leaf_node) | |
| # if we're at a leaf, set the value | |
| if len(data_list) == 2: | |
| leaf_node.value = data_list[1] | |
| return | |
| # recursive case | |
| tree_node = GameNode(data_list.pop(0)) | |
| # make connections | |
| tree_node.parent = parent | |
| parent.addChild(tree_node) | |
| for elem in data_list: | |
| self.parse_subtree(elem, tree_node) | |
| # return from entire method if base case and recursive case both done running | |
| return | |
| ########################## | |
| #### MAIN ENTRY POINT #### | |
| ########################## | |
| def main(): | |
| filename = sys.argv[1] | |
| print "hello world! " + filename | |
| data_list = parse_data_as_list(filename) | |
| data_tree = GameTree() | |
| data_tree.build_tree(data_list) | |
| if __name__ == "__main__": | |
| main() |
Signing Out
Side note. I’m actually not sure what this tree (with weights only at the leaves) would be called technically. It reminds me of the tree made during Huffman Encoding, but it’s not quite a match for that since we aren’t summing the values in all parent nodes. If you know the technical name, let me know, so I can update.
tonypoer.io 