I have no opinion in this matter as I don’t know what “puzzle” means.

From my perspective the algorithm is clearly described by example. The solving of the kata includes finding out a more formal description which then is straight forwardly implemented. Also, looking at the various solutions, I think an algorithm description would narrow it down. My solution was a recursive one (which in combination with generators isn’t something everybody is familiar with). But other solution are using different approaches (and thus different algorithms) to achieve the same results.

It’s like with sorting. By looking at the result (the sorted lists) you cannot find out which algorithm has been used. But I wouldn’t call that a puzzle either.

If, however, puzzle means that you have to find the algorithm, then I’m fine with giving this kata the puzzle tag.

Oh, well, it's the same algorithm as for my solution for the simpler version (so you probably can compare there?), but I replaced the creation of substrings by passing the limits in the original string instead. Makes it less concise and less readable but probably a little faster. But the complexity should be O(log(n)) in both cases. (I might be wrong about the formula, but its definitely the same for both versions.)

I propose to change this kata so that we aren't given a pre-produced string but instead a string-ish object which counts how many accesses to its characters are made and makes up characters on the fly following a certain algorithm. And if the amount of the accesses is too large, it should throw an exception. This way it would not use the brittle timeout-mechanism to ensure the correctness of the algorithm.

I clicked on attempt again and again in the end when I had no more ideas. And finaly it accepted my version. I guess my approach is sound algorithmically (feel free to have a look at my solution and correct me), but the test suite is also reported to have issues with timing out for O(1) algorithms :-/

Weird. The description doesn't explain the format of toll_map and I also don't find it intuitive.

I'm pretty sure I have the optimal algorithm, and now I even optimized the code, although the description says that's not what it is about. And still I get timeouts in Python.

It's frustrating to have it this way. Someone should reduce the limits of the test cases to make sense for Python.

Thanks for adding more TCs.

As I wrote earlier: »I could also add a 16×16 example ;-) But I think if the 4×4 is not enough to get the idea, then larger examples will not really make it any clearer.« I still think this, but of course more TCs don't hurt at all.

I know what you mean. I felt the same when I first tried to implement this and when I succeeded I felt like an algorithm god. Which I'm not ;-)

The solution as I did it turns the typical case of going from coarse to fine and finer (recursively) upside down and goes from finer to coarse and coarser with each recursive step. Maybe this hint helps.

It's a little like counting the topmost bits of an int first instead of the bottom bits. And in fact, turning an int around can also be lead to a solution of this kata.

But if you finally get the trick, then this kata isn't too hard. In fact, then it is rather simple. So it's like a threshold kata.

I'm trying to say that in this case there is a good reason why the solution in the standard library (os module) is a recursive one. Of course this is far from a mathematical proof for this approach being the best, but it is a hint. The recursion solves a lot of special cases very elegantly which would be hard to address in an iterative way. For example, I haven't seen an elegant iterative solution which omits investigating the leftmost path parts.

And, btw, tail-recursion is relevant if you have very deep recursions (to avoid the stack overflow) or if you intend to pass very large data structures (to avoid copying performance loss). In this case, however, you will have a depth in the dozens or less, and creation of directories typically isn't done very often. With such numbers, readability and compactnes (if leading to obvious correctness) always beats performance, IMHO.

The simple iterative solutions I know (also the ones given here) all have drawbacks (like raising errors in case you have paths with unreadable parts in the beginning (what no test case checks) or being uselessly complex in case you had extremly long paths, maybe on very slow file systems like sshfs over a very slow line). As I said elsewhere in this thread, there's a reason the offcial library solution (the mkdirs() in the os module) is implemented recursively. To catch all the problems would be much more complex in an iterative solution. So people tend to ignore them, and if the test cases here do not check for them, people feel they've got a good solution. But ignoring unfound errors ist nothing more than an illusion.

If you disagree and like to go on with the discussion, you can point out to me a concrete iterative solution here and I will tell you concretely what aspects on it I don't like.

Done. I could also add a 16×16 example ;-) But I think if the 4×4 is not enough to get the idea, then larger examples will not really make it any clearer.

Why the special case handling of len = 0 and len = 1? The third case encompasses them.

Oops. Sorry, right. Fixed that. I thought that publishing the kata would check that automatically, but on second thought I understand that it doesn't.