So as per my previous article - "Friday code puzzle" - here's my answer to the current puzzle.
I knocked the first version of this out over a beer whilst waiting for my flight to Galway, last night. Then scrapped that as being crap, and rewrote whilst in transit. And then... erm... back-filled my unit tests y/day evening. I feel guilty about not doing proper TDD, but... so be it. It's got test coverage now.
Just on TDD for a second. It was wrong of me not to do the testing first, and whilst I was just about to manufacture an excuse as to why not ("I didn't have PHPUnit installed on this machine", "I couldn't be arsed making a whole project out of it", "um [something about being offline on the flight]"), it was all bullshit laziness. I had to write tests to prove that my function would work outside of the immediate quiz requirements: the easiest way to do this is with unit tests and clear expectations etc. These tests were of limited benefit to me, given I already had the code written, and had already been through the trial-and-error process of getting the thing working correctly. The thing is, in a professional environment the tests aren't for you necessarily. They're for the next person who comes along to maintain your code. Or to troubleshoot your code when an edge-case crops up. It should not be down to the next person to write the tests for your code. That's lazy-arse, ego-centric shit. Do your job properly. I have encountered a coupla devs recently who think they're too good for tests, and refuse to do them properly. I don't want to work with people like that as they're all "me me me me".
But anyway... some code.
Well first a recap. Here's the "official" description from Jesse. But in summary:
We have this data set:
id,parentId,nodeText
1,,File
2,1,New
3,2,File
4,2,Folder
5,,Edit
6,5,Copy
7,5,Cut
8,5,Paste
9,,Help
10,9,About
This reflects hierarchical data (I would not represent a hierarchy that way, but that's a different story for another time), and we want to convert it to a hierarchical representation, eg:
[
{
nodeText : "File"
,children : [
{
nodeText : "New"
,children : [
{ nodeText: "File" }
,{ nodeText: "Folder" }
]
}
]
}
,{
nodeText : "Edit"
,children : [
{nodeText: "Copy"}
,{nodeText: "Cut"}
,{nodeText: "Paste"}
]
}
,{
nodeText : "Help"
,children : [
{ nodeText: "About" }
]
}
]
There are a few "rules of engagement" at that link I mentioned, but that's the gist of it.
I decided I had better write some PHP code for a change, so knocked something together hastily. Initially I thought I might need to write some recursive monster to generate the hierarchy, but instead realised I did not need to do that, I just needed to track each "parent" node as I encountered it, and then append children to it as appropriate. Note that the data is sorted, so each record could be a parent of a subsequent node, and it will never be the case one will encounter a node before already having processed its parent. So all I needed to do is iterate over the data from top to bottom. Once. Nothing more tricky than that. Then by the time I had finished, the first parent would represent the entire tree. That was easy enough but then I had to convert it to JSON. Note the above representation is not JSON, but it's close enough, so that's what I decided to run with. As it turns out this was pretty easy to achieve in PHP as it has the ability to provide a custom serialiser for a class, and given I'd used a mix of associative and indexed arrays to build the data structure, it was simply a matter of returning the first parent node's children. Done.
Enough chatter, here's the code...
Update:
I have updated this from the first version I posted. This is slightly simpler, and also works even if the data is not pre-sorted. Thanks to Mingo for encouraging me to look into this.<?php
namespace puzzle;
class Tree implements \JsonSerializable {
private $parents = [];
function __construct() {
$tree = [
"children" => []
];
$this->parents[0] = $tree;
}
static function loadFromCsv($filePath) {
$dataFile = fopen($filePath, "r");
$tree = new Tree();
while(list($id, $parent, $nodeText) = fgetcsv($dataFile)) {
$tree->addNode($nodeText, $id, $parent);
}
return $tree;
}
private function addNode($nodeText, $id, $parent) {
$parent = $parent === "" ? 0 : $parent;
$this->parents[$id]["nodeText"] = $nodeText;
$this->parents[$parent]["children"][] = &$this->parents[$id];
}
function jsonSerialize() {
return $this->parents[0]["children"];
}
}
The only other thing to note here is that the requirements indicated the data "should be in the form of an RDBMS resultset", but I could not be arsed horsing around with DB data for this, so I'm just reading a CSV file instead.
I also wrote the tests, as I said:
<?php
namespace test\puzzle;
use puzzle\Tree;
/** @coversDefaultClass \puzzle\Tree */
class TreeTest extends \PHPUnit_Framework_TestCase {
private $testDir;
function setup() {
$this->testDir = realpath(__DIR__ . "/testfiles");
}
/**
* @covers ::loadFromCsv
* @covers ::__construct
* @covers ::addNode
* @covers ::jsonSerialize
* @dataProvider provideCasesForLoadFromCsvTests
*/
function testLoadFromCsv($baseFile){
$files = $this->getFilesFromBase($baseFile);
$result = Tree::loadFromCsv($files["src"]);
$resultAsJson = json_encode($result);
$resultAsArray = json_decode($resultAsJson);
$expectedJson = file_get_contents($files["expectation"]);
$expectedAsArray = json_decode($expectedJson);
$this->assertEquals($expectedAsArray, $resultAsArray);
}
private function getFilesFromBase($base){
return [
"src" => sprintf("%s/%s/data.csv", $this->testDir, $base),
"expectation" => sprintf("%s/%s/expected.json", $this->testDir, $base)
];
}
function provideCasesForLoadFromCsvTests(){
return [
"puzzle requirements" => ["testSet" => "puzzle"],
"one element" => ["testSet" => "one"],
"deep" => ["testSet" => "deep"],
"flat" => ["testSet" => "flat"],
"not ordered" => ["testSet" => "notOrdered"]
];
}
}
There's no real surprise of discussion point there, beside highlighting the test cases I decided upon:
- the puzzle requirements;
- a single element;
- a deep structure;
- a flat structure.
I think those covered all the bases for a Friday Puzzle. An example of the data and expectation are thus (this is the "deep" example):
1,,Tahi
2,1,Rua
3,2,Toru
4,3,Wha
5,4,Rima
6,5,Ono
7,6,Whitu
8,7,Waru
9,8,Iwa
10,9,Tekau
[
{
"nodeText": "Tahi",
"children": [
{
"nodeText": "Rua",
"children": [
{
"nodeText": "Toru",
"children": [
{
"nodeText": "Wha",
"children": [
{
"nodeText": "Rima",
"children": [
{
"nodeText": "Ono",
"children": [
{
"nodeText": "Whitu",
"children": [
{
"nodeText": "Waru",
"children": [
{
"nodeText": "Iwa",
"children": [
{
"nodeText": "Tekau"
}
]
}
]
}
]
}
]
}
]
}
]
}
]
}
]
}
]
}
]
All the rest are on GitHub.
I ran the code coverage report on the tests, and they're all green:
Give it a blast. Reminder: the puzzle details are in this gist.
Righto.
--
Adam
