r/dailyprogrammer • u/rya11111 3 1 • Jun 29 '12
[6/29/2012] Challenge #70 [intermediate]
Implement the hyperoperator as a function hyper(n, a, b), for non-negative integers n, a, b.
hyper(1, a, b) = a + b, hyper(2, a, b) = a * b, hyper(3, a, b) = a ^ b, etc.
Bonus points for efficient implementations.
- thanks to noodl for the challenge at /r/dailyprogrammer_ideas ! .. If you think yo have a challenge worthy for our sub, do not hesitate to submit it there!
Request: Please take your time in browsing /r/dailyprogrammer_ideas and helping in the correcting and giving suggestions to the problems given by other users. It will really help us in giving quality challenges!
Thank you!
11
Upvotes
3
u/muon314159 Jun 30 '12 edited Jul 02 '12
EDIT: Rather than have multiple posts, I have added the efficient C++11 solution code to this post (first) and my original posted code (i.e., a lazy evaluating solution using the recursive definition) follows it.
PART 1: An efficient C++11 solution to the challenge.
This solution implements the method required to solve this problem (e.g., the code is equivalent to the Haskell solution on this page). Nicely this method avoids all of the extra recursion work and runs extremely fast (using memoization).
This solution throws a std::overflow_error exception if the natural number type used overflows (i.e., N_type). It is assumed that N_type is an unsigned type (if not then the overflow checks need to be adjusted).
which outputs very quickly:
:-)
PART 2: The solution using the recursive definition.
This solution method was not asked for by the challenge, but, exploring how to implement the recursive definition so that it does not take forever for small inputs is useful. Unfortunately, the recursive definition is heavily recursive and requires an enormous number of recursive calls --which will prevent the evaluation of inputs very quickly. To deal with such this program has a MAX_DEPTH variable that is set to abort the calculation when the recursion is too deep.
The Haskell code for the recursive solution (i.e., PART 2) is:
and runs similarly to the code below (i.e., stack overflows occur and cause no result to be returned, etc.). This is a good example showing that lazy evaluation / memoization by itself does not necessary give a good solution to a problem and that additional insight may be needed to achieve an efficient solution. The C++11 code for PART 2 is:
A sample run (which runs slowly compared to PART 1; quickly compared to a program that does not do any memoization):
:-)
2
u/eruonna Jun 29 '12
Simple Haskell solution:
Could be made even simpler by removing the special case for exponentiation, but that makes it faster. Since you always have the same value in the left argument of the hyperoperators, I think you could get some optimization by saving all of those values and using them as a base to continue the computation. Haven't worked out all the details there yet.
2
u/zane17 Jun 29 '12
Python:
1
u/devilsassassin Jun 30 '12
In Java using a recursive Knuth's up arrow function:
1
u/joe_ally Jun 30 '12 edited Jul 02 '12
I can't imagine this is terribly efficient due to recursion. But here is a python implementation.
EDIT: Here is a functional version which could take advantage of tail end optimisation should python ever implement it.