Jared Martin

After posting two separate blogs for PWC 055 and seeing how awkward the explanations were, I'll try a new tack: Both submissions will be elaborated in one blog post. The elaborations will not be explanations. I'll focus more on the "idea" part and let any programming details come out in the comments, if at all.

PWC Task #1, Diff-K

jaredor submission for Task #1

Input

For input I decided that all the numbers in the array would be command line arguments. That meant that 'k' would have to be a command line option. There was some validation that the stated requirements were met.

One input requirement "given an array @N of positive integers (sorted)" seemed to say that the input array should be sorted. The algorithm I chose worked without any sorting requirement on input, so this was not checked.

Case 1: k > 0

Basically, take your input values and then create another array that is the input array with an element-wise subtraction by k. Take the intersection of these two arrays. Any elements in the intersection are the A[j] in the desired relation, A[i] - A[j] = k. By construction, we also know we have A[i] in the input array as well. Some bookkeeping is needed to track the indices, but it's not too bad.

Case 2: k = 0

This is where the i != j requirement comes into play. This case basically lists off all the groups of non-unique elements in pair-wise fashion.

PWC Task #2, Path Sum

jaredor submission for Task #2

This is about the nicest binary tree exercise for people, like myself, who never had a formal comp sci class which forced them to write one from scratch. The tree doesn't have to be balanced, nor does it have to be sorted.

Input

This took the most time to get right. The entire binary tree comes in as a list of values. The "missing nodes" have to have a "null value". I was very liberal and just made anything non-numeric a null value. Then getting the parent node indexing right was a pain, but relatively easy. Once that is figured out, loading the values into a binary tree structure was straightforward and there was just one check needed to validate the input as representing a binary tree. Because of the problem to be solved, it didn't matter if the branches were "left" or "right" but I kept that distinction alive.

Tree Walking

A classic binary tree walking subroutine. Because the walk will go down different paths from the same node, we have to send copies of the path array into each of the recursive calls. Generating the path sums was just the act of calling this tree walker at the top node.

Output

The user can supply target sums to check for in the tree. If the key is pressed, a summary of all the sums and paths is generated. Quit the user input cycle by typing 'Q' to quit.