Display 100 Hello World Without Using Loops(ajibanda.com)
ajibanda.com
Display 100 Hello World Without Using Loops
http://www.ajibanda.com/2012/05/programmers-interview-101-print-100.html#.T79WN7Bo3tw
41 comments
#include "stdafx.h"
#include <iostream>
using namespace std;
class HelloWorld {
HelloWorld::HelloWorld()
{
int _tmain(int argc, _TCHAR* argv[])
{
#include <iostream>
using namespace std;
class HelloWorld {
public:
HelloWorld();
HelloWorld::HelloWorld()
{
cout << "Hello World\n";
int _tmain(int argc, _TCHAR* argv[])
{
HelloWorld * hi = new HelloWorld[100] ();
return 0;
}Or, the first thing I thought of (didn't even think recursion), was evil-y eval JavaScript:
eval(Array(101).join('console.log("hello world");'));
eval(Array(101).join('console.log("hello world");'));
Here is mine in that really crappy PHP language:
print implode(PHP_EOL, array_fill(1, 100, "Hello World"));
print implode(PHP_EOL, array_fill(1, 100, "Hello World"));
yy 100 p
or
map { print "hello, world\n" } (1..100);
or a goto or maybe even disgusting abuse of try/catch
Depending on how far I wanted to tweak the interviewer's nose. :D
or
map { print "hello, world\n" } (1..100);
or a goto or maybe even disgusting abuse of try/catch
Depending on how far I wanted to tweak the interviewer's nose. :D
Haskell Solution ::
Prelude> take 100 $ cycle "Hello World"
Prelude> take 100 $ cycle "Hello World"
Decent enough explanation of recursion.
Why not take it further and produce a more general solution?
In JavaScript I'd write something like this:
Why not take it further and produce a more general solution?
In JavaScript I'd write something like this:
function recurseBetween(start, end, callback) {
// Create a recursive function
// which checks the limits and calls the supplied callback
var recursiveCallback = function(i) {
// Call the original callback
callback(i);
// If we're at the end, stop
if(i >= end) {
return;
} else {
// Else increment and recurse
recursiveCallback(++i);
}
};
// Start recursing with the start value
recursiveCallback(start);
}
recurseBetween(1, 10, function(i) {
console.log(i);
});
Here's a completely abstracted version, but I'm certain it's less clear to use ;)
In reality, this syntax is too complicated. I would probably introduce some helpers; eg you could pass in a straight integer or a function and it would deal with it. I'd also probably send the arguments as named parameters so the syntax looked like this instead:
function recurseBetween(initial, hasEnded, modify, callback) {
// Overwrite the callback with a recursive version:
var recursiveCallback = function(i) {
// Call the original callback
callback(i);
// If we're at the end, stop
if(hasEnded(i)) {
return;
} else {
// Else increment and recurse
recursiveCallback(modify(i));
}
};
// Start recursing with the start value
recursiveCallback(initial());
}
recurseBetween(function() {
return 1;
}, function(i) {
return i<=10;
}, function(i) {
return i++;
}, function(i) {
console.log(i);
});
recurseBetween(function() {
return 1;
}, function(i) {
return i<=100;
}, function(i) {
return i+=10;
}, function(i) {
console.log(i);
});
In reality, this syntax is too complicated. I would probably introduce some helpers; eg you could pass in a straight integer or a function and it would deal with it. I'd also probably send the arguments as named parameters so the syntax looked like this instead:
recurseBetween({
'start': 1,
'end': 100,
'modify': function(i) {
return i+=10;
},
'callback': function(i) {
console.log(i);
}
});
What you're inventing here is usually called "unfold". I don't know javascript, but here it is in close relative Scheme:
'f' is what to do for each 'seed' value. In this case, it ignores the current value and just prints "Hello world". It's your 'callback'.
'g' maps each 'seed' value to the next 'seed' value. It's your 'modify'.
'seed' is the initial state for the unfold. It's your 'initial'.
-----
There are a couple other caveats to do with this being an expression rather than a statement, but it doesn't really matter right now. There are a million other cool things about unfolds (and folds, and other higher-order functions), but I'm not sure I could conscionably point you in the right direction since they lead to dangerous places.
Speaking of which, here is an unfold in Haskell, where it may (may) be clearer:
(define (unfold p f g seed)
(if (p seed)
'()
(cons (f seed) (unfold p f g (g seed)))))
(unfold (lambda (x) (> x 100))
(lambda (x) (display "Hello world"))
(lambda (x) (+ x 1))
1)
'f' is what to do for each 'seed' value. In this case, it ignores the current value and just prints "Hello world". It's your 'callback'.
'g' maps each 'seed' value to the next 'seed' value. It's your 'modify'.
'seed' is the initial state for the unfold. It's your 'initial'.
-----
There are a couple other caveats to do with this being an expression rather than a statement, but it doesn't really matter right now. There are a million other cool things about unfolds (and folds, and other higher-order functions), but I'm not sure I could conscionably point you in the right direction since they lead to dangerous places.
Speaking of which, here is an unfold in Haskell, where it may (may) be clearer:
unfold p f g seed | p seed = []
| otherwise = x:xs
where
x = f seed
xs = unfold p f g (g seed)
sequence_ $ unfold (>100) (const $ print "Hello world!") (+1) 1
Yeah I've done a bit of haskell at uni, it only struck me later how similar it is(/can be) to JS.
Or go back to C and learn that recursion is not really used like that. If you know the limits beforehand, use "for". If you don't know how deep the processing will go, use recursion.
If you must code a loop without using "for" it means you're doing a homework ;)
If you must code a loop without using "for" it means you're doing a homework ;)
Python version:
exec "print 'Hello world'\n" * 100I think a better Python version would be
print '\n'.join(['Hello world'] * 100)
I wonder why 430gj9j added exec..
print "Hello world\n"*100
He abstracted this loop:
for i in xrange(100):
statement
exec "statement" * 100
Or just
print "Hello, World\n" * 100
that reminds me why I don't like Python. Ad-hoc tools (many) instead of a few general concepts working well together.
Btw at interview time this solution would not be acceptable, because you are using still a built-in language construct for looping.
Btw at interview time this solution would not be acceptable, because you are using still a built-in language construct for looping.
You're right, Python isn't beautifully minimal. But the Scheme version is boring ;)
Rather than asking the interview candidate to use recursion for a problem that shouldn't be solved using recursion (unless in a language where recursion is the idiomatic iteration method), it would be better to ask about a problem that is best solved using recursion rather than printing "Hello world" -- perhaps something from Project Euler (http://projecteuler.net/).
Rather than asking the interview candidate to use recursion for a problem that shouldn't be solved using recursion (unless in a language where recursion is the idiomatic iteration method), it would be better to ask about a problem that is best solved using recursion rather than printing "Hello world" -- perhaps something from Project Euler (http://projecteuler.net/).
On the contrary, wouldn't OP's solution be an example of more generalized implementation of multiplication? I can see that it is similar to (X * 2) where X defines behavior of __mul__.
Yes, there is chance that arbitrary objects can provide different semantics for __mul__. It would be true for any language.
Yes, there is chance that arbitrary objects can provide different semantics for __mul__. It would be true for any language.
Huh? This is a specific case of the * operator, which is overloaded for type string to return a repetition of the string. The only ad-hoc in the example is the print statement, which is gone in 3.2.
How do you know the __mul__ operator overload for string is implemented with iteration?
How do you know the __mul__ operator overload for string is implemented with iteration?
> This is a specific case of the * operator, which is overloaded
It is not operator overloading in the strictest sense, but more of duck typing. In Python (and Ruby), operators are syntactic sugar for method calls on the first operand.
Operator overloading on the contrary suggests a function add(a, b) that reacts differently through polymorphism (i.e according to the types of its arguments).
The distinction is important as overloading and polymorphism simply do not exist in Ruby and Python, only overriding.
It is not operator overloading in the strictest sense, but more of duck typing. In Python (and Ruby), operators are syntactic sugar for method calls on the first operand.
Operator overloading on the contrary suggests a function add(a, b) that reacts differently through polymorphism (i.e according to the types of its arguments).
The distinction is important as overloading and polymorphism simply do not exist in Ruby and Python, only overriding.
My hope in using the phrase "operator overloading" was to bring to mind the familiar concept of operator ad-hoc polymorphism (which I would maintain duck typing is an example of) rather than to misleadingly describe the internals of the Python language. Nonetheless you are quite right on the details.
Well then you don't seem to know python and focus on some red herrings, because it's much more of the latter than the former. The example leverages general concepts such as duck typing and defining __mul__ for a string as doing something thoughtful.
> because you are using still a built-in language construct for looping.
That... makes no sense, the code is not looping anywhere.
And if you could somehow disqualify this bit, then recursion most definitely wouldn't qualify.
That... makes no sense, the code is not looping anywhere.
And if you could somehow disqualify this bit, then recursion most definitely wouldn't qualify.
Or just this:
print ('hello, world\n' * 100)[:-1]Perl version:
perl -e 'print "Hello world\n" x 100;'
perl -e 'print "Hello world\n" x 100;'
Or alternatively, "how not to write a parser".
A great answer to a similar problem here http://stackoverflow.com/a/4583502/456341.
No loop, and no conditional recursion.
The flaw is to use arithmetic on stack function pointer, which is not recommended nor strictly defined.
No loop, and no conditional recursion.
The flaw is to use arithmetic on stack function pointer, which is not recommended nor strictly defined.
100.times {puts "Hello, world"}
I'm just sayin'.
I'm just sayin'.
I'm not sure this will reflect well on Haskell that this is the most natural way I can think to write it. But I can pretty much guarantee replicateM_[0] is the most generalizable idiom in this whole comments section.
-----
[0] http://hackage.haskell.org/packages/archive/base/latest/doc/...
replicateM_ 100 $ print "Hello World!"
-----
[0] http://hackage.haskell.org/packages/archive/base/latest/doc/...
sequence_ $ take 100 $ repeat $ putStrLn "Hello, World"
mapM_ putStrLn $ take 100 $ repeat "Hello, World" [see above]Oh, didn't know about `replicateM_`. Not sure I like it much though, seems... redundant.
It's a pretty common pattern, I think it's worth its own word, at least as much as mapM:
mapM f xs = sequence (map f xs)
replicateM n x = sequence (replicate n x)
[deleted]
These are fun.
In C++, make the compiler do your recursion:
In C++, make the compiler do your recursion:
#include <iostream>
template <int N>
void pr(const std::string &msg)
{
std::cout << msg << std::endl;
pr<N-1>(msg);
}
template <>
void pr<0>(const std::string &msg)
{
}
int main(int argc, char *argv[])
{
pr<100>("Hello World");
return 0;
}
Unrolling loops can be a good thing when optimizing code, but you can't get much worse than tail recursion. It's always a win to eliminate this code pattern. The order of complexity is the same, but your stack will blow up for large N.
I don't know what you're looking for when posing this problem. A simple loop is already the most efficient technique.
loop good tail recursion bad
Of course, this is just a homework quiz, right?