Scala:110
type B=BigInt
def r(a:B,b:B,f:(B,B)=>B):B=if(b>1)f(a,r(a,b-1,f))else a
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))
ungolfed:
type B=BigInt
def recursive (a:B, b:B, f:(B,B)=>B): B =
if (b>1) f (a, recursive (a, b-1, f))
else a
recursive (2, 3, recursive (_, _, recursive (_, _, (_ + _))))
explanation:
type B=BigInt
def p (a:B, b:B):B = a+b
def m (a:B, b:B):B = if (b>1) p (a, m (a, b-1)) else a
def h (a:B, b:B):B = if (b>1) m (a, h (a, b-1)) else a
def t (a:B, b:B):B = if (b>1) h (a, t (a, b-1)) else a
plus, mul, high(:=pow), tetration all work in the same manner.
The common pattern can be extracted as recursive method, which takes two BigInts and a basic function:
def r (a:B, b:B, f:(B,B)=>B):B =
if (b>1) f(a, r(a, b-1, f)) else a
r (4, 3, r (_,_, r(_,_, (_+_))))
The underlines are placeholder for something which gets called in this sequence, for example the addition plus(a,b)=(a+b); therefore (+) is a function which takes two arguments and adds them (a+b).
unfortunately, I get issues with the stack size. It works for small values for 4 (for example: 2) or if I reduce the depth for one step:
def h(a:B,b:B)=r(a,b,r(_,_,(_*_))) // size -7, penalty + 5
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))
The original code is 112 characters and would score, if valid, 107. Maybe I find out how to increase the stack.
The expanded algorithm can be transformed to tailrecursive calls:
type B=BigInt
def p(a:B,b:B):B=a+b
import annotation._
@tailrec
def m(a:B,b:B,c:B=0):B=if(b>0)m(a,b-1,p(a,c))else c
@tailrec
def h(a:B,b:B,c:B=1):B=if(b>0)h(a,b-1,m(a,c))else c
@tailrec
def t(a:B,b:B,c:B=1):B=if(b>0)t(a,b-1,h(a,c))else c
The tailrecursive call is longer than the original method, but didn't raise a stackoverflow in the long version - however it doesn't yield a result in reasonable time. t(2,4) is fine, but t(3,3) already was stopped by me after 5 min. However, it is very elegant, isn't it?
// 124 = 119-5 bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,r(_,_,0,(_+_))))
And now the same as above: use stinky multiplication (we even profit while rejecting the bonus of 5, because we save 7 characters: win=4 chars:)
// 115 without bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,(_*_)))
invocation:
timed ("t(4,3)")(t(4,3))
t(4,3): 1
scala> t(4,3)
res89: B = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
runtime: 1ms.
4One alteration which I think is fairly important is to replace "* operator" with "multiplication operator". In GolfScript
*
is multiplication in some contexts, but it's also the simple looping operator:{block}N*
is equivalent to C-stylefor(i=0;i<N;i++){block}
. The tricky edge case is string/array multiplication ('a'3*
gives'aaa'
), but that's unlikely to be an issue given that an array of4***3
elements will overflow RAM. – Peter Taylor – 2012-04-19T08:38:41.453@PeterTaylor Thanks, updated. – MrZander – 2012-04-19T21:12:26.413
3Also worth adding a test for the edge case
x 0
=> 1. My original solution didn't handle that case. – Peter Taylor – 2012-04-19T21:20:37.137Thanks, added that as well. I also added that speed is not a requirement. – MrZander – 2012-04-19T21:21:53.517
3The penalty for using multiplication is way too low. (:=bonus for not using it). I made a solution which didn't used it, and had to replace it to avoid stack overflows, and gained a 7 char win for a 5 char bonus loss. – user unknown – 2012-04-20T03:32:11.233
@userunknown It seemed to help out other people. Peter Taylor, for example. It was just another incentive, for fun. – MrZander – 2012-04-20T05:20:46.883
1What does "at least
4 3
" mean exactly? My C solution computes4 3
nicely, but is inaccurate for many smaller numbers (which are not powers of 2). – ugoren – 2012-04-20T12:16:05.7471@ugoren you need to be able to compute numbers lower than that accurately. – MrZander – 2012-04-20T17:20:15.027
1
Basically this without exponentiation.
– Engineer Toast – 2017-09-19T12:20:21.9202@EngineerToast I posted this golf 4 years before the one you linked... – MrZander – 2017-09-19T23:13:40.183
@MrZander HA! Good point. I failed to note either timestamp. My apologies. – Engineer Toast – 2017-09-20T12:03:02.127
2The conditions and scoring are kind of strange. You don't allow the use of power operations? Or you do allow them, but they are a +10 point bonus? – Simply Beautiful Art – 2017-12-04T23:58:20.447
1@SimplyBeautifulArt The scoring was meant as a deterrent, this is a code golf. Meaning, if you used a power operator, it would be worth 10 points towards your golf score, of which you want to be low. But yeah, I can see how it's unclear. This was posted a long time ago haha. I'll update it. – MrZander – 2017-12-05T00:03:04.353
1The strange thing is that it's kinda hard for me to implement exponentiation in less than 10 bytes in Ruby, so it was actually worth the 10 point price. – Simply Beautiful Art – 2017-12-05T00:03:58.370
1@SimplyBeautifulArt The original goal of the question was to not use the power operator, so I have made that the "rule". Thanks for pointing it out. – MrZander – 2017-12-05T00:06:14.143