Use this GitHub Classroom link to get started: classroom.github.com/a/HpCYL2es.

In a Number Tree puzzle, you must enter the numbers from 1 to N once each (for a puzzle with N circles), such that each non-leaf of the tree contains the sum of the numbers that it is connected to from above. The root and usually at least one other circle have numbers given to you, as shown in the example above.

For clarification:

• In the case where some circles have given numbers, those numbers do count toward the use of each number once.
• The root node need not have a value between 1 and N.
• In the description above, "above" refers to the diagram. Notice that in the diagram, the leaves are "up" and the root node is "down".

Complete the NumberTree class described below:

int size() const

Return the number of nodes in the tree.

int height() const

Return the height of the tree.

void load(const string& str)

Initialize a NumberTree from a string.

• The string will contain one line for each node.
• Each line is terminated by a semi-colon.
• The semi-colon after the last line is optional.
• The first token in each line is the name of the node.
• Remaining tokens identify the node's children.
• If a node's "name" is a number, than that node's value is fixed (e.g., node "4" above).
• A non-numerical node must begin with a character. (In other words, "1st" isn't a valid node name.)
• You may assume the input lists child nodes before the parent.
• Raise an invalid_argument exception if the input is not valid (doesn't parse, nodes are out of order, node repeated, number is out of range, orphan node, etc.)

Sample Input:

A
B
C
D
4 A B
E D 4
F 4 B
G B C
19 E F G
    

bool verify(const string& str) const;

Verify that the content of str represents a valid solution to the problem. The input str describes the values to be placed in the empty nodes. Verify that those values satisfy the puzzle. Specifically:

• Each node's value is equal to the values of its children.
• Each value between 1 to N is used exactly once. (Remember, this restriction does not apply to the root, but does apply to nodes whose values were fixed by the problem definition.)

The input str will consist of a sequence of node names and values separated by semi-colons. For example a 1; b 2; c 3;

Raise an invalid_argument exception if the input is not valid (doesn't parse, unknown node referenced, node is missing a value, value is out of range, etc.)

Important: Notice that this method is const. That means this method can't modify the NumberTree, only query it. Specifically, you need to store the solution values in a data structure that's local to the method. The benefit of this method being const is that you can now verify multiple solutions without having to "reset" the object.

unordered_map<string, int> solve() const;

Find a solution to the puzzle and return a map of node names to values. Return an empty map if no solution exists. You may find this function helpful: www.cplusplus.com/reference/algorithm/next_permutation/. Notice that this is a const function: It may not modify the NumberTree object.

Extra credit: Find a non-brute-force solution. In other words, find a solution that is more clever than just trying assignments of values to nodes until it find one that works.

Submission and grading

• Please fill out this survey (optional): rit.az1.qualtrics.com/jfe/form/SV_cvvgAFEhvcwX0gd
• Submit the written problems in class.
• Make sure all relevant code (including unit tests) is checked in to GitHub by the due date.
• Unless you indicate otherwise, I will assume that the code to be graded is on the master branch.
• You are expected to fix and re-submit buggy code. Because your code will eventually be correct, your grade will be based primarily on timeliness.

(Problem suggested by Zack Butler and Ivona Bezakova at the Rochester Institute of Technology.)

Updated Thursday, 17 October 2019, 7:31 PM