So... getting around to the results.
Took me a while to get around to solving my own puzzle (let alone scoring it), and seeing as I cannot objectively score my own result, I automatically win. Just kidding - I will attempt to provide a decent, and objective, evaluation of all submissions.
I have observed three basic approaches to solving this problem:
- Functional, of which are two flavors: iterative and recursive
As far as target languages, everyone provided a CFML-based solution, most of which used the Lucee5 engine, while one used ACF2016. In addition, @adamcameron provided his solution in both CFML and PHP.
I will not fully analyze each solution here, but provide a quick first-impression. I encourage you to look at the submissions yourself, as I will not be posting code snippets. Anyways, on to the results:
@CraicOverflow89 was the first submission, using a recursive approach. Good as far as readability - iterate over the nodes, and for each node recursively look for children. This solution takes to heart expecting the dataset to be a query object, and as such uses QoQ to find children. QoQ can be useful, but keep in mind it is slow.
@jcberquist also submitted a recursive solution. This is a bit more compact, fairly readable, and being a single function it is easy to drop into a class, or use as a global function. This makes it more easily reusable.
@elpete submitted a recursive solution that incorporated some functional iteration as well as looping statements. This solution makes strides toward reusability by allowing to specify the
nestingKey - in this case being
parentId. However, looking at the output, one of the expections was not met, that is, nodes that do not have children should not have the
@adamcameron is next - posting his answer on his blog: http://blog.adamcameron.me/2016/08/friday-puzzle-my-php-answer.html. This is the first (and only) solution using a fully-OOP approach, also the first to provide tests - bonus points! His was the first solution to hit on my unspoken goal of a non-recursive, single-pass solution. Please read his blog post as he does a really good job explaining the problem and how he came to the solution. Now, I will say that while being perhaps the most elegant solution, it does assume the data is in a CSV formatted file as opposed to an RDBMS resultset, and that reading the CSV file is incorporated into the same class used to represent the tree itself.
@mjhagan followed up shortly thereafter with essentially the same approach, both as a component for testability, and as a single function to execute on trycf.com. I would lean toward classifying his example as functional, as the component seems to be more tailored to embedding the function into the testing environment. I will also point out that by browsing his git repo, I found an example of essentially the same algorithm that will work for unsorted data - excellent!
@jasperdenk rounded out the weekend with a procedural solution that also solved the problem non-recursively and with a single pass. Wrap that up in a function for reusability, and that would
Finally, I provided my solution, which is a functional approach using reduce (the only one to do so, patting myself on the back), and using a stack to track the current branch. While it accomplishes the goal in a single pass with no recursion, it is way overcomplicated as compared to @adamcameron and @mjhagan.
And the winner is:
Based on all the criteria, I have to give this one to @mjhagan. His solution, in my estimation, did the best at meeting all the stated expectations, and with the bonus of adding tests. Congratulations!
Thanks to all who participated, looking forward to next Friday's puzzle!