friday code challenge

Hierarchical data structuring.md

Challenge:

Convert a flat representation of a hierarchical data into a nested tree structure.

Assumptions:

• The dataset is already sorted
• The dataset should be in the form of an RDBMS resultset, however that is represented in your target language
• Multiple "top-level" nodes may exist, defined as having an empty parentId

Expectations:

• Result is an array of the top level nodes, with child nodes nested below them.
• Use the key children to assign an array of child nodes to the parent.
• A node that does not have any children should not have the children key.

Examples:

dataset:

id	parentId	nodeText
1	null	File
2	1	New
3	2	File
4	2	Folder
5	null	Edit
6	5	Copy
7	5	Cut
8	5	Paste
9	null	Help
10	9	About

Expected result:

[
  {
     nodeText : "File"
    ,children : [
      {
         nodeText : "New"
        ,children : [
           { nodeText: "File" }
          ,{ nodeText: "Folder" }
        ]
      }
    ]
  }
  ,{
     nodeText : "Edit"
    ,children : [
       {nodeText: "Copy"}
      ,{nodeText: "Cut"}
      ,{nodeText: "Paste"}
    ]
  }
  ,{
     nodeText : "Help"
    ,children : [
      { nodeText: "About" }
    ]
  }
]

Judging

• Correctness of the result. The solution must address the problem as specified.
• Readability. This is not code golf - conciseness is good, but readable/understandable/maintainable is the goal.
• Bonus: sharing test cases in the comments on the gist are appreciated by everyone!

Rules

• Original work only
• Submissions should be licensed under a permissive license (MIT/BSD/Apache 2.0/etc.)
• You can use any language
• This is for fun and learning. There are no prizes except pride, knowledge and maybe karma.
• Submit answers in the comments as Gist/PasteBin/Online REPL, not in slack.
• If you need to clarify something about the problem or rules, do it in the comments on the gist, or at least copy the clarification there for posterity

Results.md

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.

Overview

I have observed three basic approaches to solving this problem:

• Procedural
• OOP
• 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.

Results

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 children key.

@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!

SampleTestData_CFML.cfm

<cfscript>
  
  TestData = querynew("id,parentId,nodeText");
  queryAddRow(TestData,{id:1,nodeText:"File" });
  queryAddRow(TestData,{id:2,nodeText:"New",parentId:1});
  queryAddRow(TestData,{id:3,nodeText:"File",parentId:2});
  queryAddRow(TestData,{id:4,nodeText:"Folder",parentId:2});
  queryAddRow(TestData,{id:5,nodeText:"Edit"});
  queryAddRow(TestData,{id:6,nodeText:"Copy",parentId:5});
  queryAddRow(TestData,{id:7,nodeText:"Cut",parentId:5});
  queryAddRow(TestData,{id:8,nodeText:"Paste",parentId:5});
  queryAddRow(TestData,{id:9,nodeText:"Help"});
  queryAddRow(TestData,{id:10,nodeText:"About",parentId:9});

</cfscript>

SampleTestData_JavaScript.js

  TestData = [
     {id:1,   nodeText:"File"     }
    ,{id:2,   nodeText:"New",     parentId:1}
    ,{id:3,   nodeText:"File",    parentId:2}
    ,{id:4,   nodeText:"Folder",  parentId:2}
    ,{id:5,   nodeText:"Edit"     }
    ,{id:6,   nodeText:"Copy",    parentId:5}
    ,{id:7,   nodeText:"Cut",     parentId:5}
    ,{id:8,   nodeText:"Paste",   parentId:5}
    ,{id:9,   nodeText:"Help"     }
    ,{id:10,  nodeText:"About",   parentId:9}
];

Do we post answers here? https://github.com/CraicOverflow89/FridayPuzzle/blob/master/26082016.cfm

Here is a basic solution: http://trycf.com/gist/cc80f7cbc14edef841deac04161446ff/lucee5?theme=monokai

Here's my solution:
http://trycf.com/gist/a0cef853e0f3528c9552e091c957c12a/lucee5?theme=monokai
https://gist.github.com/elpete/a0cef853e0f3528c9552e091c957c12a

Solution is here: https://github.com/mjhagen/SSCCE/blob/master/friday-puzzle/20160826/app/puzzle.cfc
Tests are here: https://github.com/mjhagen/SSCCE/tree/master/friday-puzzle
( and on trycf: http://trycf.com/gist/521ce8e41fdff8d4058b0798c32af931/lucee5?theme=monokai )

Solution: http://trycf.com/gist/bfbb242302885d43fecce779260c3ea6/acf2016?theme=monokai

Finally got around to solving my own puzzle.

Lucee 5:
http://trycf.com/gist/dc3a6ef7e0e80fdf178c09fa4274c9fc/lucee5?theme=monokai