Another fun kata:
Given an array of arbitrarily nested objects, return a flat array with all the objects marked as “good”.
The definition above is quite generic, so I’ll provide examples to show exactly what I mean.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
We want the IDs of the good ones.
You might have noticed not all objects are “good”. Number 2 for example is not good. So the result in this case should be:
The only thing to notice here is that you know it’s not good because
it’s not marked as such. In other words, when some object is “bad”,
good: false nor
bad: true that tells you that.
So how do we solve this challenge?
Since there’s an arbitrary nesting depth, we can once again leverage the power and simplicity of recursion.
I’ve created the function
goodOnes(items) that takes the input and
returns what we expect. I’m also using Ramda.js, just because I wanted a clean functional solution and I didn’t want to mess around
Here it is:
1 2 3 4 5 6 7 8 9 10 11 12
As a side note, you don’t really have to use Ramda.js.
Array.prototype.reduce does the same, although in a less elegant way.
What this function does is basically just collecting values. The
starting point is an empty array, you can see that as the second
argument in the first line.
theGoodOne is another function (a closure,
to be specific) that is implicitly taking two arguments:
accumulator, the empty array) and
item (the current item in the loop).
If the item is good, we return a new array with the item’s ID. Otherwise, we return the accumulator. However, if the item happens to have some children, we start over doing the same thing (i.e. looping over its children), also keeping track of the accumulator we already have this time. It might be still empty, but we don’t care yet. We just return it at the very end.
Now, you might have noticed a bug: what happens if the item is good, but also has children? … Yes, that item will be discarded! I did it on purpose by the way. When I made this function, the original array of items never had any good item with children. Only good items, or items with children. The algorithm is reflecting this, so it’s technically not a bug.
If you’re curious about what’s the original intent behind this function, it is to collect values from an infinitely nestable architecture of UI components. There are text components, number components, datepickers etc… those are all part of a category called fields. There are also wrappers, that could be for example a fieldset or a grid. Wrappers can contain fields, but also other wrappers.
So what if you have such data structure with so many components and all you need is just an array of fields? Simple, just reduce recursively on it! ;)
More in general, you can use the recursive reduce whenever you have a nested data structure (such as an array of arrays) and you want to get something out of it.
Solution in Clojure
1 2 3 4 5 6 7 8 9
Demo & Download
Everything is on GitHub if you want to fiddle around – just follow the instructions to get the demos up and running on your computer.