I think the whole approach with print5, print25 is the "correct" solution, but if I were interviewing I would give the best score to the person that gave system("/usr/bin/seq 1000"); as the answer.
The idea of building up by having something that prints 5, and then using that to build a print 25, and so on, is good.
That then inspires another question: given a function, foo(), that we wish to call exactly 1000 times, what is the way to do it in the least amount of code given that we are only allowed the following:
1. calling foo().
2. defining new functions, whose bodies consist entirely of calls to previously defined functions or to foo.
3. calling those new functions.
For computing amount of code, let's take it as 1 line per function call, and 1 line per function defined.
So, for example (in pseudocode):
function foo_50
foo
foo
...
foo
foo_50
foo_50
...
foo_50
where there are 50 foo's in foo_50, and 20 calls to foo_50, would be a program of length 71. Breaking it down by powers of two:
function foo_2
foo
foo
function foo_4
foo_2
foo_2
...
function foo_512
foo_256
foo_256
foo_512
foo_256
foo_128
foo_64
foo_32
foo_8
would have length 33.
Is that the best we can do? How about for a general N? How about writing a program that given N writes the optimal program in the above form for N?
Whoops, `baz() and baz()` actually doesn't work, because foo may not return a truthy value (and bar definitely doesn't). One fix, which actually makes it even shorter, is just `baz(), baz()`.
Same goes for `bar(bar(...)) and bar()`; all the `and`s should be commands instead in my solution above. Of course, this is Python-specific.
