can't be changed

It might be a good idea to include the zero-length input in the sample test cases. Using C, this will likely crash before you have a chance to look much at input and be a pain to debug. If it's a sample test, then solvers can see what the issue is.

I am an engineer and still found the units painful. Keeping everything in meters, seconds, and kg would be preferable. Along these lines, computing the force on the bike (rather than direct accel) would probably make this easier to grok. Once one gets the force, converting to accel given the mass is easy.

And +1 to the comment about setting the absolute value of acceleration. Conversely, it isn't necessary to take the absolute value of v when computing the drag, because it gets squared anyway.

The kata description could stand to be more, well, descriptive. While part of this kata is understanding the puzzle of what the pattern is, it can at least state that clearly.

Fixed misspelling - "Cooley-Turkey" -> "Cooley-Tukey"

@dvbuntu,

First of all, thanks for trying out my Kata.

With regards to the FFT algorithm(s) required to pass this Kata, the description states that any FFT algorithm that passes all tests and doesn't time out is acceptable. FYI even the reference solution only passes the Kata about 50% of the time so if you've implemented your radix-2 FFT correctly, you might be able to submit after a few more attempts.

That being said, it is not the intention of this Kata for you to pad the input with zeroes to the next power of two although you could do that if the results returned still fall within the 1e-6 relative error range. To give you an idea of the approach expected, the reference solution uses a mixed-radix Cooley-Tukey (thanks for correcting me ;) algorithm by means of prime factorization so it should have a speed advantage over your implementation for most odd inputs (provided said number is not prime). I'll leave you to figure out how to implement such a mixed-radix approach (no, you can't find the exact equations on Wikipedia; I had to derive them myself when I authored this Kata) ;)

As for the name of the algorithm, I just checked and it appears that you're correct, not sure how I got that wrong in the first place :p

Cheers,
@donaldsebleung

P.S. If you're feeling ambitious, you could also try to incorporate other FFT algorithms to specifically deal with prime-length input but I personally couldn't be bothered to investigate it myself :p

I believe I've implemented the radix-2 FFT as described, but I noticed the test case time-outs I was getting was all for odd-length inputs. As the kata description only mentions that these must be solved with some other FFT method, I found it odd that they were in the test cases. Is the intention to pad with zeros to the next power of two? If so, that should be stated. Although, I believe that introduces error (it may still be acceptable in certain applications).

Also, I believe the name is "Tukey", not "Turkey".

I was running into a similar problem and talked to donaldsebleung about it (easy enough to comment on one of his Fortran solutions). His method, however, was to first create a static-length string, and then build from that. It seems Fortran has some ability to autosize strings, but only if it's built of existing strings and you concatenate. Writing directly into such strings I haven't fully sorted out yet. Often, I'm frustrated by Kata that are challenging mainly because of arbitrary string formatting output rather than programming or mathematical difficulty.

I was having trouble making a dynamic string work with the write function. It's like if you have some string already created, Fortran can figure out how big to make your new string, but this feature isn't built into write. It makes me wonder if there's a way to do a trial write to get the necessary size, allocate, and then do the real write. Thanks!

Maybe allocating a dynamic string like "str"?

Do you know of a more general way of allocating the string, tmp, here? I was trying different things but found myself circling back to essentially what you did.

I like uppercase style...:-)

Good kata, especially walking the learner through solving it the "slow" way to see the pure solution. But for the Fortran version, can the skeleton code start lowercased? Fortran90 can handle cases just fine, no need to have it be F77 style all uppercase.