Follow

Okay folks, this should be simple, but maybe not.

The goal is to write a function that takes a positive integer and returns a list of its prime factors. So if you did 12 you should get the list [2, 2, 3]

As neither 1 nor zero are prime, as a result should return an empty list.

This is taken from a , so if you have not done this one I encourage you to do so. If you are not into then solve it however you like.

@Absinthe Easy to solve yes, but rather difficult to solve efficiently!

@freemo @Absinthe An even deeper rabbit hole with TDD: "You want to test your factorization? Well, you need a primality test... But wait! Who's gonna test your primality test? Well, you need a prime number generator... But wait!..."
No monkeys, no coconuts, no bottles, no fun...

@namark

Thats solvable (goes into NP stuff but I wont invoke this here)...

Think of it like this creating prime numbers is a much easier task than checking if a number is prime. Its the whole reason cryptography works, we can generate large primes for our keys but getting those primes out after the fact is computationally difficult.

So a TDD would be a simple matter of generating a set of primes (easy) then multiply them together to get the value under test. Then send that value off to be tested and verify if the results agree with the original list of primes you generated.

Reversing the process makes all the difference in the world when testing stuff like this.

@Absinthe

@freemo

Checking for primality is not that hard either, the factorization is hard and is the reason cryptography works (certain schemes).

That said, even if it's an easier task computationally, it's not necessarily easier to implement, especially efficiently, especially for large numbers.

Sure, skip the primality test, if your genrerator does not rely on it, but who's going to test the generator?
Maybe a trivial primality test that does not need a test itself? (oh no already violating TDD) Use it to test the generator, which you can then use to test a more sophisticated primality test that you can then use to test the generator for even bigger numbers? This is a very trollish kata for TDD, and an example of a problem where you're better off relying on theory to prove correctness, an maybe only testing some components not the problem/solution as a whole.

@Absinthe

@namark

Yea sorry I misspoke, I should have said factorization. Sieves would make it easy to chec if something is prime.

@Absinthe

@freemo @namark one of the fun things about TDD is how it can organically create an algorithm that you might not do just by sitting down and hacking at it.

@namark @freemo actually, what would be interesting would be to just sit down and knock it out. Then do it again walking the steps of TDD and compare the results.

@Absinthe

I think people would have a tendency to repeat the way they did it the first time the second time, its hard to forget a solution you just did.. still I do think TDD thinking changes to some extend the design process. Sometimes for the better sometimes for the worse maybe.

@namark

@freemo @namark @Lossberg

When I say TDD, I mean it is the way of design and development. (maybe even a way of life :D )

This means following the 3 laws:

1. You are not allowed to write any production code unless it is to make a failing unit test pass.

2. You are not allowed to write any more of a unit test than is sufficient to fail; and compilation failures are failures.

3. You are not allowed to write any more production code than is sufficient to pass the one failing unit test.

Using a Red-Green-Refactor work flow. Write just enough of a unit test for the simplest unit test. Then see that test fail(Red). Then write the SIMPLEST solution in the code to make it pass. (Green) Then refactor to remove complexity and simplify. Lather, rinse, repeat.

@Absinthe

I'm familiar with TDD and even had to practice it at a few workplaces in that manner. IMO when taken to that extreme, as some people do, I think it is more harmful than good, usually. But i can see at times it being beneficial in other ways.

@namark @Lossberg

@freemo @namark @Lossberg The factorization problem/kata is one that I particularly enjoy, because when I am done, and I look at the 6 lines of python that it generates... I always shake my head and say "I would not have written that no matter how long I sat there, or how many times I tried." Humor me, and let's see if you see similar things....

@freemo @namark @Lossberg see if you see it generate an algorithm different from what you might have done not doing it that way.

@Absinthe

I've actually done this problem many times before, so I'm not the best person to compare with... its one of my favorite class of problems to do since it can go so deep (sieves and such)

@namark @Lossberg

@freemo @namark @Lossberg I realize you enjoy different types of problems, and different types of solutions. So maybe even the suggestion of this is something you may find no interest in. I can accept that. I would encourage everyone, even you to give it a try (at that absolutely ridiculous level of pragmatically following the 3 laws and using the R-G-R workflow) Maybe you will get something out of it, maybe you won't.

And by pragmatically, I mean your first test would look like:

def test_factor_zero_return_empty():
assert factor(0) == []

----

and the first code that makes it pass is:

def factor(num):
return []

-------

That is the level or pragmatism I am speaking of.

@Absinthe

But yea prime sieve is probably the best solution I could give ya personally.. is that what you used?

@namark @Lossberg

@freemo @namark @Lossberg a prime sieve would be more complex than the whole solution.

@freemo @namark @Lossberg It is a pragmatic solution based on a "process" where the process is more important than the solution. Think of it like Algebra.

Big numbers, small numbers... it is all a matter of time.

@Absinthe

Well, from our brief discussion with @freemo we arrived at needing a prime number generator to write the test for factorization, which itself would require at least a trivial primality test, which will have to be written without a unit test. How was your approach different? Did you generate a certain amount of prime numbers by hand and deemed that acceptable?

@freemo @Lossberg

@namark @freemo @Lossberg

Those are the types of assumtions one arrives at when not using TDD :)

@freemo @namark @Lossberg

@freemo, I assumed that you would consider this as uninteresting as problems that require brute force. I am disappointed that you are not willing to give it a shot. But i didn't really expect you to find much interest in it in the first place.

@Absinthe

Its not that I'm not willing. I've done the problem before, and am a bit busy as usual lately.

@namark @Lossberg

@freemo @namark @Lossberg No matter. Not all problems are for everyone. Do the ones you like, ignore the ones you don't.

@Absinthe

Even if that's the case, the question was what is the proper TDD approach? Generating prime numbers for the test by hand? Or factorizing a couple of numbers by hand?

Thinking about it, wouldn't that make copying the hand calculated results into the implementation the best way to comply with rule 3? That's what I would arrive at with that approach, and nothing necessarily wrong with that. In one of my recent toy projects, I needed a factorization, and I just included a short list of primes, that I used as "only/all primes", knowing that the number to factorize would be small enough (and even if it wasn't that wouldn't affect the final result much). Totally sufficient for some use cases, but I see no way to move on from that point to anything more complete or sophisticated with the strict TDD approach, for the prime number problems specifically, which I think is an odd choice for a TDD kata.

@freemo @Lossberg

Here is a link to REPL.it Where it has been done via TDD 

@namark @freemo @Lossberg

Short of walking you through it, here is one instance where it was walked through. You can see the the unit tests that were used, unfortunately, there is not a really good way to see each of the coding steps and refactorings. I think I will have to do a Git solution that does a commit on each phase-step.

There are a couple commented solutions that are further ideas I wanted to keep.

repl.it/@reasintper/One-Kata-a

Here is a link to REPL.it Where it has been done via TDD 

@Absinthe

I wonder how did you come up with the 5993 test? I find it hard to verify, though I'm a particularly lazy person. Is there some sort of a trick?

Here is what I would have came up with given that sequence of test and the rules of TDD presented (not at all what I would come up with just trying to tackle the problem)
ix.io/2bgk/py
with the list of primes there growing with each new unit test . I think it's much simpler and also runs much faster. By any objective metric, with those TDD rules in mind, this is a superior solution, and I believe you would not be able to beat it without introducing a prime number generator or a primality test, or both, with one or the other not being tested.

@freemo @Lossberg

Here is a link to REPL.it Where it has been done via TDD 

@namark @freemo @Lossberg

I think we are in agreement. Maybe it is not as cool as I believe, I am used to my wife rolling her eyes when I get excited about stuff like this... :)

@namark @freemo @Lossberg

I am not saying that you shouldn't solve the problem that way. That is as legitimate solution as any. And as a solution that comes from just diving in and doing it that is what I would expect. But it is not what I would expect from doing the TDD technique.

@namark @Absinthe @freemo I think that there is a limit here. It will always be a human in the end of the link designing some test and we are all prone to mistakes. You cannot test everything after all ;)

@Lossberg @namark @freemo good reason to have tests reviewed as well as code. Maybe a reviewer can find a case you haven't done to test some aspect of the specification.

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.