Solve this simple problem with TDD

A few days ago I tried to solve the next problem with TDD and found it really hard.
I could not reach the solution through a series of small incremental test cases.
This is the problem:

flatten an array of arbitrarily nested arrays of integers into a flat array of integers.
e.g. [[1,2,[3]],4] -> [1,2,3,4].

of course without using language implementation like flatten in ruby

Can someone try to TDD this problem and comment here her/his experience?

Clarification

The process that I follow.
1- Write a set of tests (input--->expected-output)
2- Pick the simplest test case to solve. (RED)(Write a failing spec)
3- Write the most naive code change that solves the current set of tests. (GREEN)
4- Check if DRY is needed (Refactor)
5- Go back to 2

My expectation is that at some point I reach the solution for the general case but following these rules I'm not able to reach the solution.
At some point there is no naive change to solve the tests and I need to rewrite the whole solution.
I found two solutions to this problem but none of them was following this process.
https://gist.github.com/delbetu/ff67be230f83542ac1924e766b591803

Update

I found a solution for this problem check this out https://dev.to/delbetu/a-tdd-example-e4o

Comments

[Ross]

The process that I follow.
1- Write a set of tests (input--->expected-output)
2- Pick the simplest test case to solve. (RED)(Write a failing spec)
3- Write the most naive code change that solves the current set of tests. (GREEN)
4- Check if DRY is needed (Refactor)
5- Go back to 2

Firstly, TDD is not writing a set of tests. It's writing a test that fails then writing functionality.

So (like I said earlier), you write a RED test:

Input: []
Expected Output: []

You then write the simplest code to solve this problem and GREEN the test above

fun flatten(input)
   return input

Then your next test case

Input: [1]
Expected Output: [1]

and it passes, so next

Input: [1,2]
Expected Output: [1,2]

Next

Input: [[1,2]] -> [1,2]
Expected Output: [1,2]

This one does RED. So we write the code to GREEN it

//May be wrong - just throwing pseudocode out there
fun flatten(input)
  output = []
  for (int i=0; i<input.length; i++)
    if input[i] is array
      output.addAll(input[i])
    else
      output.add(input[i])

[1,[2,3]] -> [1,2,3]
[[1,2],[3,4]] -> [1,2,3,4]

Both start off green

[[1,2,[3,4,5]],6,7] -> [1,2,3,4,5,6,7]

RED, so expand implementation

//May be wrong - just throwing pseudocode out there
fun flatten(input)
  output = []
  for (int i=0; i<input.length; i++)
    if input[i] is array
      output.addAll(flatten(input[i]))
    else
      output.add(input[i])

GREEN.

[[1,2,3,[4,5,6]], [7,8,[8,10,11]]] -> [1,2,3,4,5,6,7,8,9,10,11]

Starts off green.

At some point there is no naive change to solve the tests and I need to rewrite the whole solution.

There's not always a naive change but in this case I'm not sure where the non naive code change happens. You need to add a loop pretty early but that's the easy way forward.

[M Bellucci]

You raise a good point when saying that starting with a list of tests is not TDD.
To clarify those tests are not run all together from the beginning.
When I start coding all of them are commented out and during the TDD cycle I just decide which of them uncomment.
Starting with a list of tests is done by J.B.Rainsberger
on his course introduction to TDD

In the other hand maybe restricting to an initial list of test is not a good way to lead to a solution.
I tried writing the test that makes more sense for the current tdd-cycle and then I reached a solution (updated this in the description).

your solution seems to be a valid one I didn't try it.
Thanks for taking the time to read and solve this problem.

[michelemauro]

Well, a few tests that come to mind are:

[3] -> [3]
[[3]] -> [3]
[1, [2, 3]] -> [1, 2, 3]

I'm writing them in Java, give me time to reach an interesting level and I'll share it for discussion.

The problem smells a lot like recursion: it's a great exercise in writing only the necessary code, as J.B. Rainsberger preaches in this video at 2:48:

Do watch it all, because it's great.

[michelemauro]

Well Jon, this is more a proof than an implementation. While technically correct, this approach will however fail if you have an infinite (i.e. unknown in advance) array, or a stream.
What you call "responsibilities" I call "the different cases when inspecting next element". My first solution didn't yield a lazy solution like I wanted, however; I should try again and see if the same subdivision that you envision emerges from that approach or not.

The length and depth of your answer, however, begs a question: what really is a test? is the goal of TDD to prove a piece of code "correct", or just that "it works"?

You do prove that your approach is "correct" (for finite length arrays); but is this a "unit test"? Would you call this TDD?

[Ross]

I don't see a problem, you want small incremental test cases. What's the simplest case and expand it as nauseam:

Simplest case:
[] -> []

An input:
[1] -> [1]

Multiple Inputs:
[1,2] -> [1,2]

Simple nested array:
[[1,2]] -> [1,2]

Nested array and single entry:
[1,[2,3]] -> [1,2,3]

Two nested arrays:
[[1,2],[3,4]] -> [1,2,3,4]

Two level nested array and single elements:
[[1,2,[3,4,5]],6,7] -> [1,2,3,4,5,6,7]

Two, two level nested arrays:
[[1,2,3,[4,5,6]], [7,8,[8,10,11]]] -> [1,2,3,4,5,6,7,8,9,10,11]

At which point you can continue to create test cases for different combinations or even better, I would advise Theory or Property testing to generate arbitrary numbers of entries, depths and values. Any non conformity found via these methods become hard coded test cases of their own.

[M Bellucci]

I think that I'm not expressing my problem correctly.
Just wrote a clarification in the description.

[michelemauro]

While reading and writing the other comments, something felt missing... then it dawned on me!

@delbetu , are we answering to your question?

I assumed that your question was "I had a hard time coming up with the tests for this problem". And approached the thing writing some tests. That led me to a suboptimal solution (but I can improve it, I have tests now!)

I think @jonsullivandev thought your question meant "I had a hard time solving this problem" and gave you a correct solution, proving it beyond every (well, almost) conceivable test.

Which one was it, @delbetu ?

(not that I mind the interesting discussion that came out of this...)

[M Bellucci]

"I had a hard time coming up with the tests for this problem" --> this is partially correct.
I was able to get a set of test cases.
I wasn't able to reach a solution through the application of micro cycles (red-green-refactor) based on those tests.

The point is "Does TDD work?"

[michelemauro]

There is only one answer, of course: "It depends".

It depends on what you mean for "work".

TDD has a proven track of "working" in helping produce software that exibits less bugs, that it is closer to the specification encoded by the tests (that may or may not be the desidered one, but that's another story), and that is easier to debug. And that, at least locally, is better designed.

Things get much more blurred when you have:

• non-functional specification that may not be testable without costly or impossible setup (i.e. it's difficoult to write a test for "must not exceed 50% CPU on the target hardware"). These situations require prototyping or something else.
• correctness requirements that must be upholded in every concievable, and a few unconcievable, cases; Jon's approach covers exactly that (or at least part of it). These situations require formal methods.
• a situation when "fiddling" is required (as Uncle Bob puts it); that is where a human estetic acceptance is required (you can't test for "it looks good") or when interacting with an external, poorly specified interface. These situations require experimentation.
• to accomodate for unexpected or unforseen (at the moment of writing) architectural requirements (will the same code work for 100x the traffic? will you design the same if it is called 10k times per second instead of 10?). These situation require a wider vision and a cost/risk evaluation.
• probably other situations that I can't think of right now.

So, TDD "works"... in every context where it works (sorry). That however covers quite a lot of possible programming problems. There undoubtedly are contexts in which TDD is not a perfect fit or does not work at all, and other tecniques must supplement or substitute it.

[michelemauro]

Well, Jon Sullivan's answer is quite... interesting. And it's quite, but not completely, different from the path that I took.

In this repository: bitbucket.org/michelemauro/flatten... (sorry, it's Java; I don't do Ruby) you'll find:

• in the master branch, each commit adds a test
• in the "mim" branch, each test is merged and solved.

I tried a "the simplest thing that can possibily work" approach, but came out with a really unsatisfying solution because:

• it's an eager approach: I would prefer a lazy one (one that does not pre-allocate the whole result before returning it) but it didn't seem like "the simplest thing" while writing it.
• the third test passes without intervention: this makes me think that I wrote too much code the first time. I'll need to work on that.

All in all, my implementation seems very similar to what Jon describes, with the caveat that I don't separate the two responsibilities. I also don't think that the best solution (a recursive, lazy one that can work with infinite collections) can work with this approach, because it requires unpacking a whole sub-array before returning the next element, and that loses the lazyness.

So, this simple question is becoming a really interesting little problem, almost worth a kata. There is a lot to be pondered on.

[M Bellucci]

Thanks for sharing this!
I faced the same issue, at some early point in the TDD cycles I got stuck and couldn't pass the test without writing the solution that was in my mind.
Anyway, testing first helped me to think about the problem and came out with a solution.
Share my my solution

So it seems that the hard part of TDD is finding The simplest thing that can possibly work

[M Bellucci]

Thanks Jon for taking the time for thinking of such a detailed solution, but the core of my question is TDD.
I wonder if this problem can be solved in a series of micro red-green-refactor cycles (30 seconds)
I don't want a solution I want you to try it and heard about your thoughts.
I'm questioning the usage of TDD not the problem.

[M Bellucci]

Ok, as soon as I have some free time I'll try to follow your tests and tell you back what was my experience.
thank you!

[M Bellucci]

Reading again all of your answer so you are describing an algorithm which possibly solves the problem and you identify two sub problem that can be tested individually,

This is a valid technique for solving a problem but is totally the opposite of tdd

Because in tdd you don’t know the solution in advance, as you resolve every micro test with the minimum amount of code to satisfy the test you discover the algorithm.
So you don’t know the algorithm in advance.