text:
Implement hyperexponentiation/tetration without the use of '^'
The Challenge
Implement tetration (aka Power Tower or Hyperexponentiation) with the least amount of characters.
The Conditions

Don't use the 'power' operator or its equivalents (such as pow(x,y), x^y, x**y, etc.)
Input given as: x y (separated by a space)
x is exponentiated by itself y times.
Your method must be able to compute at least 4 3 (4 exponentiated by itself 3 times)

The Scoring

Lowest score wins: (# of characters)
Bonus deduction if you do not use the multiplication operator (-5 points).
No Speed/Memory requirements. Take as long as you want.

Examples
x, 0 -> 1

2, 2 -> 2^2 = 4

2, 4 -> 2^(2^(2^2)) = 65536

4, 3 -> 4^(4^4) = 4^256 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Open to suggestions/alterations/questions

One 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-style for(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 of 4***3 elements will overflow RAM.

Also worth adding a test for the edge case x 0 => 1. My original solution didn't handle that case.

Thanks, added that as well.  I also added that speed is not a requirement.

The 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.

@userunknown It seemed to help out other people. Peter Taylor, for example. It was just another incentive, for fun.

What does "at least 4 3" mean exactly? My C solution computes 4 3 nicely, but is inaccurate for many smaller numbers (which are not powers of 2).

@ugoren you need to be able to compute numbers lower than that accurately.

Basically this without exponentiation.

@EngineerToast I posted this golf 4 years before the one you linked...

@MrZander HA! Good point. I failed to note either timestamp. My apologies.

The 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?

@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.

The 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.

@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.

This is being flagged as unclear, but no user has stated why yet.  Our standards for this sort of thing have changed since this question was posted and it would be closed as unclear today.  The problem for me is that what counts as "exponentiation", "pow" or "multiplication" are not objectively described, now we require a much more rigid description of this sort of thing.

This post is two weeks shy of being a decade old now (wow).  It seems quite clear to me, but I don't have any clue what the new standards are and don't contribute here anymore.  That being said, I'll gladly accept someone's edit if anyone would like to keep this alive.

J, score is 7 (12 chars - 5 points for avoiding multiplication)
+/@$/@$~/@$~
usage:
   4 +/@$/@$~/@$~ 3
1.34078e154
t=.+/@$/@$~/@$~  NB. define a function
   4 t 3
1.34078e154
   2 t 2
4

Just few nested folds:

Using multiplication it would be */@$~/@$~
Using power it would be ^/@$~ where $~ creates array, / is a fold function.

Nicely done. (pad)

@Gareth Thanks, but was does pad mean here? Sorry, English is not my mother tongue.

My message was too short so I needed to pad it out. :-)

Could you get pentation just by providing one more @$~ in the conjunction?

@Jonah You'd need the /, but yes. you're just folding as many times as needed over the nested folding function.

Haskell, 87 85 - 5 == 80 82
import Data.List
t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)

Uses neither of exponentiation, multiplication or addition (!), just list operations. Demonstration:
Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3

...ahm... you didn't say anything about performance or memory, did you? But given enough billions of years and some petabytes of RAM, this would still yield the correct result (genericLength can use a bigInt to count the length of the list).

I trust you will have an answer for me by 3012? ;)

I'll need some help from Moore's law, but that given I might.

GolfScript, 15 18 chars
~])*1\+{[]+*{*}*}*

Yes, one of the *s is a multiplication operator (exercise: which one?) so I don't qualify for the 5 char bonus.  Still, it's just barely shorter than Peter's solution.
This earlier 15-char version is otherwise the same, but produces no output when the second argument is 0.  Thanks to r.e.s. for spotting the bug.
~])*{[]+*{*}*}*

This produces fatal errors, e.g. with "2 3" ~])*{[]+*{*}*}*.

@r.e.s., it produces the correct answer for me.

@r.e.s.: It assumes that there's nothing else on the stack but the input. If you want to provide the input in-line like in your example, first use ; to remove the actual input string that the interpreter puts on the stack at start-up. Or just prepend a [ to the code: both ;"2 3" ~])*{[]+*{*}*}* and "2 3" [~])*{[]+*{*}*}* work fine for me.

(+1) Thanks! Those variations work and solve a mystery for me. The tutorial says "You don't have to pipe input in, but if you don't, it will not prompt for input, instead it will assume there is no input."  So I've been using just ruby golfscript.rb my_script.gs on the command line, without knowing that it causes something ("", apparently) to be on the stack before the script is run -- which sometimes works, sometimes not. (Also, with echo 2 3 | ruby golfscript.rb my_script.gs, your program does work as-given.)

ideone.com/547LG

Unfortunately, this script leaves an empty stack (instead of the required output 1) when the second input number is 0; i.e., x 0 --> empty.

@r.e.s.: Thanks for spotting that.  Looks like I need to spend three extra chars to fix it. :(

J, 16 19 12 characters
*/@$~/1,~$~/

or as a verb (17 characters):
h=:[:*/@$~/1,~$~/

usage:
   h 2 4
65536

or taking input from keyboard (24 27 20 characters):
*/@$~/1,~$~/".1!:1]1

with thanks to FUZxxl for pointing out my stupidity. :-)
Explanation:
J is read from right to left, so using 2 4:
/ is used to insert the verb $~ between each pair of items in the list. $~ takes the left item and shapes it $ using the right item (the ~ reverses the arguments) - so this would be equivalent to 4 $ 2 which gives you a list of 2s which is four items long 2 2 2 2.
Now we append 1 to the list 1,~ and then do the same thing again; / insert a verb */@$~ between each pair of items in the list. This verb starts in the same way $~ but this time it / inserts a * between each item of the newly generated list. The @ just makes sure that the */@$~ works as one verb instead of two. This gives 2 multiplied by itself enough times to be equivalent to 2^4.
J's vocabulary page - I find solving problems with J fun just because of the different way it sometimes does things.
Adding one further iteration to remove the * operator has 2 problems

It comes out at 17 characters (+/@$~/,@$~/1,~$~/) which, even with the -5 bonus, is too long
It runs out of memory if the number gets too large so doesn't meet the requirement of being able to calculate 4 3

Could you provide an explanation?  This looks interesting.

@MrZander I've edited my answer to add an explanation.

Not sure if I have a better understanding or more confusion, but thanks haha.

The explanation implies that the whole thing is doing exponentiation rather than tetration. Which of us is missing something?

@PeterTaylor I suspect my explanation is not very clear. If it was doing tetration I would have just used ^/]$[ which creates the list 2 2 2 2 and sticks the exponentiation operator between them. What this is doing is going a step further and doing the exponentiation by repeated multiplication.

Unfortunately, this script does not produce the correct output (1) when the second input number is 0; e.g., 1 0 --> domain error ...

@r.e.s. Hmmm...I'm not sure how I'll meet that criterion... - in my defence, the case x 0 = 1 wasn't actually in the question when I posted my answer.

@r.e.s. Ok, found a fix at a cost of 3 characters.

In what way is ]$[ different from $ or ~$?

@FUZxxl That's a very good point. Can't see the wood for the trees sometimes. :-)

@Gareth, I can't understand how come that ^/4$3 runs out of memory, but your solution doesn't

@ArtemIce My solution will turn 4 3 into a list of 256 4s and then multiply them. Adding an extra iteration to get rid of the * and use + instead will generate a list of 4s so long that it won't fit into memory.

@Gareth oh, I should be using ^/4$~3 instead! Now I've come up with an answer http://codegolf.stackexchange.com/a/6992/4878

GolfScript (24 chars - 5 = 19 points)
~\1{1{0{+}?}?}{@\+@*}:?~

is insanely slow.
(or 20 chars)
~\1{1{*}?}{@\+@*}:?~

is much faster.

Since GolfScript is a Ruby program, we can test on ideone :) http://ideone.com/GTIfP.  I've also emailed ideone suggesting they add support for GolfScript.

@mellamokb, it'll be nice if they do add it, but I'm not too optimistic because their stated policy is to add languages which are supported by their distro.

I read that too... but since they support Ruby, and GolfScript is just a Ruby program, it should be easy :) Just create a bash script that passes in the parameters.

+1 http://ideone.com/eW2F3 :)

Python, 70
This uses nested eval calls, eventually producing a string "a*a*a*a...*a" which gets evaluated.  Almost half of the score is wasted on getting the arguments... though I've noticed that a few other solutions don't bother with that.
a,b=map(int,raw_input().split())
exec"eval('*'.join('a'*"*b+'1'+'))'*b

If we assume the arguments are comma sepearated, you could use input() or use eval(raw_input()) Cheers

@st0le, please read the question

Nice one.  The second line can be golfed even more:  exec"eval('a*'*"*b+'1'+"+'1')"*b

@flornquake good catch! thanks!

Br**nfuck, 128-5=123 bytes
+<<+<<,<,[>[>+>>+<<<-]>[<+>-]>[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>[<<+>>-]+<[-]<<<<-]>>>.

Input is in the form of characters with code points of the numbers desired as inputs. Output is the same.
An explanation is coming when I have the time below. Do I get bonus points for not using exponentiation, multiplication, OR even addition?
Cell 3 (0-indexed) is the running total x.
This calculates the nth tetration of a.

+<<+<<,<,                                       Initialize tape with [n, a, 0, 1, 0, 1]
[                                               While n:
  >[>+>>+<<<-]>[<+>-]                             Copy a 3 cells to right: [n, a, 0, x, a, 1]
  >[                                              While x:
    >[>>+>+<<<-]>>>[<<<+>>>-]                       Copy a 2 cells to right: [n, a, 0, x, a, 1, a, 0]
    <<[>[>+>+<<-]>>[<<+>>-]<<<-]                    Cell 7 = prod(cell 5, cell 6)
    >[-]>[<<+>>-]<<<<-]                             Move this value to cell 5. End while.
  >>[<<+>>-]+<[-]<<<<-]                           Update x to result of exponentiation. End while.
>>>.                                            Print the result!

This works (tested) for x 0, 0 x, x 1, 1 x, x 2, 2 3, and 2 4. I tried 3 3, but it ran for several hours without finishing (in my Java implementation—probably not optimal) (EDIT: in @Timwi's EsotericIDE [It's great! Y'all should try it] as well. No luck.). In theory, this works up to the cell size of the specific implementation.

"Br**nfuck" Yes "brain" is a very offensive word xD. sorry I needed to

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.

Ruby 66 59 characters
def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end

Unfortunately, this script does not produce the correct output (1) when the second input number is 0; rather, e(x,0) returns the value of x.

@r.e.s. you are right. I fixed the code. Thanks!

Python, 161 - 5 (no * operator) = 156
r=xrange
def m(x,y):
 i=0
 for n in r(y):i+=x
 return i
def e(x,y):
 i=1
 for n in r(1,y+1):i=m(i,x)
 return i
def t(x,y):
 i=1
 for n in r(y):i=e(x,i)
 return i

invoke:
t(2, 4)

Is multiplication by iterated addition really fast enough to evaluate 4***3?!

@PeterTaylor yes? it completes in less than a second for me

Wow. The equivalent GolfScript version takes aaaaaaages.

As in, I've left it running overnight and it still hasn't finished.

@PeterTaylor: Have you tried 3***3? I interrupted my Scala program after a few minutes.

Since efficiency is not a criterion, you can reduce the score to 147-5=142 (this doesn't display properly in a comment, but you should get the idea): r=range def f(k,x,y):  i=0  if k==1:   for n in r(y):i+=x  if k==2:   i+=1   for n in r(y):i=f(1,i,x)  if k==3:   i+=1   for n in r(y):i=f(2,x,i)  return i. Invoke: f(3,x,y). (In some browsers, you can view the comment with properly displayed code by using View Source. Or, in Chrome, right-click and Inspect Element.)

Six years later, you can also save some bytes by replacing your m function with m=lambda x,y:sum(x for _ in r(y))

Perl, 61 chars
here's a bizarre one
sub t
{
  ($x,$y,$z)=@_;
  $y>1&&t($x,$y-1,eval$x."*$x"x($z-1||1))||$z
}

usage:
print t(2,4,1)

an incorrect one too

Mathematica, 40 33
This doesn't quite conform to the rules but it is not in contention for the shortest code anyway, and I hope that it will be of interest to someone.
m@f_:=Fold[f,1,#2~Table~{#}]&;

m[m@Sum]

This builds a "tetration" function when it is run, but the arguments must be given in reverse order.  Example:
m[m@Sum][3, 4]

1340780792994259709957402499820584612747936582059239337772356144372176
  4030073546976801874298166903427690031858186486050853753882811946569946
  433649006084096

Would you explain the code? Or display results on symbols rather than numbers? I notice that Fold[g, 1, #2~Table~{#}] &[3, 4] will produce g[g[g[1, 4], 4], 4] for instance.

@David m[Times] produces Fold[Times, 1, Table[#2, {#1}]] &, which is a power function:  m[Times][5, x] ---> x^5; the same method is used for this new power function to produce a tetration function.  Logically one could start with Plus but that fails almost immediately.

To eliminate Times, try this: t[h_, n_] := Sum[h, {i, n}].  Then run m[m@t][3, 4].

@David, yes, that should work, but not for Code-Golf. ;-)  (BTW you could write Sum[h, n].)

Look at the scoring rules. You save 9 points by not using Times.  The total score is still not better than yours but getting closer.

The question says -5 points, but with that I'm down to 33.  Thanks, @David!

I get the following error message with your 33 char code: Table::iterb: Iterator {Underscript[\[Sum], 4]1} does not have appropriate bounds. >>

@David please ping me in Mathematica Chat when you read this.

Haskell:  58  51 chars, with or without multiplication.
i f x 1=x;i f x n=f$i f x$n-1
t=i(\o n->i(o n)n)(+)4

Ungolfed:
bump op n a = iterate (op n) n !! (fromIntegral $ a-1)
tetrate = iterate bump (+) !! 3

Shorter definition comes from inlining “bump”, and defining a custom version of “iterate”.  Unfortunately the result is impossibly inefficient, but starting with (*) instead of (+) gives decent speed.  In ghci:
Prelude> let i f x 1=x;i f x n=f$i f x$n-1
(0.00 secs, 1564024 bytes)
Prelude> let t=i(\o n->i(o n)n)(*)3
(0.00 secs, 1076200 bytes)
Prelude> t 4 3
13407807929942597099574024998205846127479365820592393377723561443721764030073546
976801874298166903427690031858186486050853753882811946569946433649006084096
(0.01 secs, 1081720 bytes)

Rockstar, 233 bytes
Rockstar is a quite new computer programming language, designed for creating programs that are also song lyrics. Rockstar is heavily influenced by the lyrical conventions of 1980s hard rock and power ballads.
The solution takes two inputs, one per each line (string manipulation is very limited). It uses multiplication operator, so no bonus to apply for :/
P takes A,B
N is 1
C is 1
While C is as low as B
Let N be N of A
Build C up

Give back N

T takes E,F
If F is empty
Give back 1
Else
Knock F down
Let G be T taking E,F
Give back P taking E,G

Listen to X
Listen to Y
Say T taking X,Y

Ungolfed, here's a more lyric version (comments are in parentheses, which are standard comments in Rockstar). Variable names may take up more words, and all words count ('my power' is different from 'the power' and from 'Power')
Power takes the force and the cross          (function def, two parameters: 'the force', 'the cross')
  Build my arm up                            ('my arm' := 1) (literally: 'my arm'++, but my arm was initialized with 0)
  Build my faith up                          ('my faith' := 1)
  While my faith is as weak as the cross     (While loop, condition: 'my faith' <= 'the cross')
    Let my arm be the force of my arm        ('my arm' := 'the force' * 'my arm' )
    Build my faith up                        ('my faith' ++ )
                                             (empty line to terminate While block)
  Give back my arm                           (return 'my arm')
                                             (empty line to terminate function block)
Tower takes the force and the enemy          (function def, two parameters: 'the force', 'the enemy')
  If the enemy is nowhere                    (If, condition: 'the enemy' == 0) (literally: 'the enemy' == NULL, but NULL is considered 0 in arithmetics)
    Build Victory up                         (Victory := 1, this is a bit diffeerent from the golfed version)
    Give back Victory                        (return Victory)
  Else                                       (else)
    Knock the enemy down                     ('the enemy' -- )
    Let the defense be Tower taking the force and the enemy ('the defense' := Tower ('the force', 'the enemy'))
    Give back Power taking the force and the defense        (return Power ('the force', 'the defense'))
                                             (empty line to terminate If block)
                                             (empty line to terminate Function block)
Listen to us                                 (input: 'us')
Listen to your enemy                         (input: 'your enemy')
Scream Tower taking us and your enemy        (output: Tower('us', 'your enemy'))

JavaScript (Node.js), 41 bytes
Have some BigInts
a=>g=b=>b--?(P=n=>n--?a*P(n):1n)(g(b)):1n

Try it online!

Jelly, 9 bytes - 5 (no multiplication) = 4
xxxS¥/¥@/

Try it online!
Jelly, 6 bytes - 5 (no multiplication, but cheats by using the list product atom) = 1
xxP¥@/

Try it online!

Python, 112 chars
The numbers should be the 1st and 2nd argument: python this.py 4 3
** operator not used.
* used. It's quite trivial to implement, exactly like **, but costs more than 5 chars.
import sys
p=lambda y:y and x*p(y-1)or 1
t=lambda y:y>1 and p(t(y-1))or x
x,y=map(long,sys.argv[1:])
print t(y)

How do I use the code to compute 4 3? And, just of curiosity: Have you tried to implement * that way, and to compute 4 3 then?

@userunknown, Input is by parameters. I added an explanation to the answer. I didn't try to add the * implementation, I believe the recursion depth would be too large for 4 3.

C, 117 105 99 chars
EDIT: Merged the two functions p and r into one, saving some chars.
Of 99 chars, 52 do the actual calculation (including variable definitions). The other 47 are for handling input and output.
BUG: Badly handles powers of 0 (e.g. 0 2). Should find a minimum cost fix. This isn't a bug, I forgot that 0 2 is undefined.
Successfully handles 4 3, and even gives an exact result. However, can be inaccurate for some smaller numbers.
Prints the number with a trailing .000000.
x,y,z;
double R(){return--y?!z?y=R(),R(z=1):x*R():x;}
main(){
    scanf("%d%d",&x,&y);
    printf("%f\n",R());
}

Looks like 118 chars to me: http://ideone.com/9D5SU

Testing this with 4 3 is only accurate to about 18 places,  double doesn't have nearly enough precision to support an exact representation.

@Sir_Lagsalot, double has more than enough precision for 4^256. It only has one significant digit.

Ah good point, I wasn't thinking in binary. Does it actually print out the exact value for you? It gets truncated after the first 18 or so decimal digits on my machine, but I'm willing to accept that's system specific.

@Sir_Lagsalot: See the ideone link I provided.  It prints out the whole number.

@Sir_Lagsalot, I tested gcc/Linux, it prints it all. Maybe the format string %lf isn't handled the same way on your system.

VBA, 90 Chars
*Perhaps the no multiplication bonus is not good enough. I think the no multiplication answer is much more interesting, but this is code golf, so it's not the best. Here's an answer without *, and a better (shorter, and better scoring) answer with it:
90 chars, no power operators, uses multiplication = 90
Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:b=b*x:Next:f=b:Next:MsgBox f
End Sub

116 chars, no power operators, no multiplication bonus (-5) = 111
Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:For i=1 To x:a=a+b:Next:b=a:a=0:Next:f=b:Next:MsgBox f
End Sub

NOTE: VBA has issues printing the number when the result is very large (i.e. 4, 3), but it does calculate correctly, so if, for example, you wanted to USE that number, you would be good to go. Also, even BIGGER numbers overflow (i.e. 3, 4).

Factor, 187 characters
USING: eval io kernel locals math prettyprint sequences ;
IN: g
:: c ( y x o! -- v )
o 0 = [ x y * ] [ o 1 - o!
y x <repetition> 1 [ o c ] reduce ] if ;
contents eval( -- x y ) swap 2 c .

Before golf:
USING: eval io kernel locals math prettyprint sequences ;
IN: script

! Calculate by opcode:
!   0 => x * y, multiplication
!   1 => x ^ y, exponentiation
!   2 => x ^^ y, tetration
:: calculate ( y x opcode! -- value )
    opcode 0 = [
        x y *
    ] [
        ! Decrement the opcode. Tetration is repeated exponentiation,
        ! and exponentiation is repeated multiplication.
        opcode 1 - opcode!

        ! Do right-associative reduction. The pattern is
        !   seq reverse 1 [ swap ^ ] reduce
        ! but a repetition equals its own reverse, and 'calculate'
        ! already swaps its inputs.
        y x <repetition> 1 [ opcode calculate ] reduce
    ] if ;

contents eval( -- x y )         ! Read input.
swap 2 calculate .              ! Calculate tetration. Print result.

I did not remove the multiplication operator *. If I did so, then I would need to add some logic expressing that the sum of an empty sequence is 0, not 1. This extra logic would cost more than the -5 bonus.

Rule breaker, 124 + 10 = 134 characters
USING: eval kernel math.functions prettyprint sequences ;
contents eval( -- x y ) swap <repetition> 1 [ swap ^ ] reduce .

This program has a lower score, but the exponentiation operator ^ breaks the rules. The rules say "(# of characters) + (10 * (# of 'power' operators))", so I applied the +10 penalty. However, the rules also say "Don't use the 'power' operator", so any program taking this penalty does break the rules. Therefore, this program of 134 characters is not a correct answer, and I must present my longer program of 187 characters as my answer.

Ruby, 47 46 45
t=->x,n{r=x;2.upto(n){r=([x]*r).inject :*};r}

Haskell 110 - 5 = 105
Tetration Peano Style. This is the most insanely slow solution possible, just a warning, but also avoids even addition.
data N=Z|S N
a&+Z=a
a&+S b=S$a&+b
_&*Z=Z
a&*S b=a&+(a&*b)
_&^Z=S Z
a&^S b=a&*(a&^b)
_&>Z=S Z
a&>S b=a&^(a&>b)

This relies on you having the patience to type out Peano numbers (and won't show the answer,
If you actually want to run it, add these few lines (90 chars):
f 0=Z
f a=S$f$a-1
t Z=0
t(S a)=1+t a
main=interact$show.f.(\[x,y]->x&>y).map(f.read).words

Lua: 133 chars, multiplication-less
a,b=io.read():match"(%d+) (%d+)"a,b,ba=a+0,b+0,a for i=1,b-1 do o=1 for i=1,a do o=o+o for i=1,ba-b do o=o+o end end a=o end print(o)

I was originally going to use string repetition hacks to do fake multiplication, but it likes to fail on large values. I could possibly use dynamic compilation and loadstring to make it smaller, but it's getting late here... I need sleep.
Entering "4 3" into stdin outputs:
1.3407807929943e+154

Perl 6, 32 bytes
->\a,\b{(1,{[*] a xx$_}...*)[b]}

Try it online!
(1, { [*] a xx $_ } ... *) is a lazy sequence that generates the power tower, each element being the a list which consists of the first input parameter a replicated (xx) a number of times equal to the previous element ($_), that list then being reduced with multiplication ([*]).  From that sequence we simply pluck out the b-th element.

Lambda calculus, 10-5
(using Church encoding and De Bruijn indeces)
λλ(1λ13)λ1
Explanation
Without De Bruijn indeces: λa,b.(b λc.ca)λc.c:
λa,b.                                                 define the anonymous function f(a,b)=
     (b                                                apply the following function b times
        λc.                                                    the anonymous function g(c)=
           ca)                 apply c to a because of church encoding this is equal to a^c
              λc.c                              the identity function, 1 in church encoding

If you define exp_a(x)=a^x this program defines a↑↑b=exp_a^b(1) where ^b denotes function itteration.
I'm not sure if this is allowed because ca is technically equivalent to a^c how ever it is not a real built-in and only a side effect of the way integers are encoded in lambda calculus.

Hm, is there an interpreter so that I can try this? If there's no implementation of a language, then you can't use it to solve challenges here. Languages are based on their implementations here.

Python - 151 bytes
Python 3.0:
r=range
def exp(a,b):
 if b=0:
  a=1
else:
 r1=a
 for i in r(1,b):
  s=s*a

def tet(a,b):
 r1=0
  if b=0:
   a=1
else:
 r1=a
 for i in range(1,b):
 r1=exp(a, result)

Here's how the new new version works.
1: Exponentiation is initialized (multiplies a by a b times), as well as tetration (in terms of our exp function).
2: a is stored in result of the tetration function.
3: Then we exponentiate a to result (as tetration does), and store that in result
4: Repeat step 3 b times.
Feel free to tell me I suck. (With huge credits to the commenters and Googology Wiki)

Welcome to Code Golf! This looks like the start of a good answer, but there are a few obvious things that can be golfed (like the whitespace and variable names). You may want to check out Tips for Golfing in Python. Also, if you indent your code by four spaces here, it'll format it as code.

Thanks for the advice! I'm going to format it now.

I fixed a lot of issues, but I don't think this is optimal yet.

Welcome @StackMeter, I suggest you take a look at this post: https://codegolf.stackexchange.com/questions/54/tips-for-golfing-in-python
A lot of good golfing tips

Removed the spaces and dropped about 20 bytes; thanks!

Thank you for bothering to upvote me twice - I appreciate it!

It's not clear what the I/O method is, and it doesn't seem like your byte count matches the code. Consider using Try it Online.

Wolfram Language (Mathematica), 29 bytes
(27 characters)
aNest[Nest[a#&,1,#]&,1,#]&

Try it online!
Input curried as f[x][y].

Without *: 35 bytes (33 characters)
aa+#&~n~0~n~1~n~1
n=Nest~Curry~3

Try it online!

Javascript: 116 chars
function t(i){y=i.split(' ');a=y[0];b=y[1];return+b&&p(a,t(a+' '+(b-1)))||1}function p(a,b){return+b&&a*p(a,b-1)||1}

t('4 3') Outputs:
1.3407807929942597e+154

Python (111) (113) no *
r=lambda x,y:(x for _ in range(y));t=lambda x,y:reduce(lambda y,x:reduce(lambda x,y:sum(r(x,y)),r(x,y)),r(x,y),1)

6***3 - 36k digits))
Upd: Have to add initial value, to fit t(X,0)=1

Impressive, how long did the 36k take?

9.375 seconds including print.

Common Lisp, 85 chars
(lambda(b c)(let((r b)u)(dotimes(c c r)(setf u 1 r(dotimes(c b u)(setf u(* u r)))))))

I tried doing the multiplications through repeated addition, but it was way more than 5 characters.  Same thing with macrolets, the declarations were not worth the gains.
Another solution, inspired by boothby's python solution.  It's 1 character less than the above solution.
(lambda(a b)(eval`(*,@(loop for x below b nconc(loop for x below a nconc`(,a,a))))))

Python 3 – 68
(including the 10-point penalty for the power operator)
a,b=input().split()
r=1
exec("r=%s**r;"%a*int(b))
print(r)

Haskell: 88-5 chars without multiplication, 59 chars with multiplication
Without multiplication:
h x y=foldr(\x y->foldl(\x y->foldl(+)0(replicate x y))1(replicate y x))1(replicate y x)

There are probably ways that I could golf that down a little.
With multiplication:
h x y=foldr(\x y->foldl(*)1(replicate y x))1(replicate y x)

And finally, the ungolfed program:
mult x y = foldl (+) 0 (replicate x y)
expo x y = foldl (mult) 1 (replicate y x)
h x y = foldr (expo) 1 (replicate y x)

This is probably the simplest way to do this problem, which is defining multiplication as repeated addition, exponentiation as repeated multiplication, and tetration as repeated exponentiation.

Racket 58 (no *)
(define(t x y)(if(= y 0)1(for/product([i(t x(- y 1))])x)))

for/product is walking a fine line on the "no multiplication" rule, haha.

Ruby, 43 39 points
->a,b{c=1;eval"c=eval('a*'*~-c+?a);"*b}

Try it online
Ruby, also 43 39 points
t=->a,b{b<1?1:eval("a*"*~-t[a,b-1]+?a)}

Try it online

The following are no longer valid(?)
Ruby, 26 + (1 power operation)*10 points
t=->a,b{b<1?1:a**t[a,b-1]}

Try it online
Ruby, 28 + (1 power operation)*10 points
->a,b{c=1;b.times{c=a**c};c}

Try it online

Yabasic, 71 bytes
A function that takes input a and b as a space delimited string.
Input""a,b
d=a^(b>0)
For i=2To b
c=a
For j=2To d
c=c*a
Next
d=c
Next
?d

Try it online!

R, 71 - 5 = 66 bytes
function(x,y,b=x){for(i in 2:y)b=cumprod(z<-rep(x,b))[sum(z|1)];cat(b)}

Try it online!
-5 for avoiding *, which was harder than I expected. It explodes really fast and won't work (unless it had more memory) but it satisfies all necessary criteria.

PHP, 139 125 bytes
function f($x,$y){return gmp_strval($y?(function($x,$y){for($a=1;$i<$y;$i++)$a=gmp_mul($x,$a);return$a;})($x,f($x,$y-1)):1);}

Uses GMP library for the arbitrary-length math.  It does compute the result instantly and able to solve 2***5 as well.
The longer (198 bytes - 5 = 193) version that does not multiply:
function f($x,$y){return gmp_strval($y?(function($x,$y,$a=1){for(;$i<$y;$i++)$a=(function($x,$y){$a=0;for(;$i<gmp_intval($y);$i++)$a=gmp_add($x,$a);return$a;})($x,$a);return$a;})($x,f($x,$y-1)):1);}

Output Tests:
2, 0 -> 1
Exec time 0.00009513 seconds
2, 2 -> 4
Exec time 0.00006819 seconds
2, 4 -> 65536
Exec time 0.00002694 seconds
4, 3 -> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
Exec time 0.00011992 seconds

If you were curious the result of 2***5, here it is:
2, 5 -> [encoded data, 19729 characters]
Exec time 0.11125493 seconds

APL(NARS), chars 46, bytes 92
{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}

test:
  h←{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}
  3 h 0
1
  2 h 2
4
  2 h 4
65536
  4 h 3
1.340780793E154

without the use of pow=* in APL where ⍵>0;
but i use multiplication ×...

APL (Dyalog Classic), 23 bytes
f←{⍵=0:1⋄⊃⌽{×/⍵⍴⍺}\⍵⍴⍺}

Try it online!

JavaScript, 85 bytes
function(s){for(s=s.split(" "),a=b=s[0],i=0;++i<s[1];)for(j=a,a=b;--j;)a*=b;return a}

JavaScript (ES6), 83 bytes
r=f=>(i,n,j=i)=>--n?j:r(f)(i,n,f(i,j));s=>r(r((a,b)=>a*b),(s=s.split(" "))[0],s[1])

APL (Dyalog Unicode), 14 12 bytes (SBCS)
f←(×/⍴⍨)/1,⍨⍴⍨

Try it online!
Without multiplication, 19 17 - 5 = 12
f←((+/⍴⍨)/⍴⍨)/1,⍨⍴⍨

Try it online!
This is practically the same thing as above, but much, much slower. This time, since we can't have multiplication either, there's (+/⍴⍨).
With exponentiation operator (*), 4 bytes
*/⍴⍨

Try it online!

Whispers v3, \$39 - 5 = 34\$ bytes
> Input
> Input
>> 1↑↑2
>> Output 3

This uses the tetration builtin

Perl 5 -Mbigint -pa, 51 46 bytes
for$i(0..<>){$_=1;for$b(1..$e){$_*="@F"}$e=$_}

Try it online!

[Wolfram Language (Mathematica)], 114 bytes
Obviously nowhere near shortest, but points for supporting all hyperoperations, and no *?
h[n_,a_,b_]:=Which[n==0,b+1,b!=0,h[n-1,a,h[n,a,b-1]],n==1,a,n==2,0,True,1]
h[4,##&@@FromDigits/@StringSplit@#]&@"3 2"

(yields 3^3 = 27).

67 bytes. The private-use character is \[Piecewise].

Javascript (ES6), 24 + 10  bytes:
h=(a,n)=>n?a**h(a,--n):1
Without **, 50 bytes:
e=(n,p)=>p?e(n,--p)*n:1;h=(a,n)=>n?e(a,h(a,--n)):1
Without *, 77 - 5 bytes:
m=(n,p)=>p?n+m(n,--p):0;e=(n,p)=>p?m(e(n,--p),n):1;h=(a,n)=>n?e(a,h(a,--n)):1
There's got to be a better way to do this than create recursive helpers, but until then...
h is the main function, the others are recursive helpers.

These only compute the exponent, you need to go one level deeper.  Compare your results with the test cases provided in the question.

In Python 3:
pow = 1
for i in range(n):
   pow=pow**a

where a is the base and n is the height

Welcome to Code Golf! Nice first answer.

"Don't use the 'power' operator or its equivalents (such as pow(x,y), x^y, x**y, etc.)". Your answer uses it and is therefore invalid.

TI-Basic, 27 - 5 = 22 bytes
Prompt X,Y
1
For(I,1,Y
prod(seq(X,J,1,Ans
End
Ans

There's no multiplication operator, but there is prod(. Takes two separate inputs. Output is stored in Ans and is displayed.


text:
Solve the 14-Pegs puzzle
Introduction
A common puzzle involves a triangular board with 15 holes for tees/pegs as shown in the image below:

Starting with all the pegs in the board except for a hole at the top, the point of the puzzle is to jump pegs over one another like checkers in such a way to leave exactly one peg left.  The only valid move is to jump one peg over an adjacent peg in any direction into an empty hole.  The peg that was jumped is then removed from the board.  Play finishes when there remain no valid moves.
Spec
Your job is to write a program that can find a complete solution to the peg puzzle, i.e., one that leaves exactly one peg left.  There are multiple possible solutions, so your program just needs to print one.

Your program will receive no input.  You are not allowed to read data from any outside source.
Print out the list of 13 moves that gives a result of 1 peg remaining using this format:

Peg 1 jumps Peg 3 to Hole 6.

The holes/pegs are numbered from top to bottom, left to right, so that the top peg/hole is 1, numbering until the bottom-right is 15.
Your program must find the solution at runtime.  Printing out a solution directly by any means other than solving it in the program is an automatic disqualification.
Bonus: receive 10 bonus points if you can output multiple unique solutions (can just print separated by blank lines).
Bonus: receive 5 bonus points if the number 15 appears nowhere in your source code.

Scoring
This is code-golf, so the shortest solution (by byte count) that prints out a correct answer will be the winner.  Bonus points are subtracted from your total byte count.  Please provide a sample output of running your program as well as a link to ideone or some similar site if possible demonstrating the execution of your program.

How do you mingle bonus points with the objective winning criterion, which we can only assume to be character count since this has a code-golf tag?

Added clarification "Bonus points are subtracted from your total byte count.", does that make sense?

second bonus is too easy to obtain, 15=0xff=(1<4)-1=~(-1<<4)=...

Some of your representations are >= 5 characters longer than 15 itself ;)

Ruby, score 240 238 234 = 249 - 10 - 5
s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

A plain ruby implementation which prints all possible solutions to this puzzle (takes less than a minute on my computer). The first lines of output can be seen here:
Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

And the online example can be found here.

I'm curious how many total solutions there are?

@mellamokb It says there are 29760 solutions.

29760 solutions? When I first found out about this game, it took me forever to find one.

That is odd. There are 2^14 (16384) board states and probably not all of them are reachable. I would've bet there were less solutions than states.

@kaoD there is certainly more than 1 way to reach most of those states

@ardnew I'm aware, it was just a 'feeling'.

@kaoD: A solution is actually a sequence of 13 moves (13 successive states from the original board state), of which there are technically (2^15)^13 unique possibilities, and of which a very large majority are incorrect under the rules.  There are also actually 2^15 (32768) possible board states because there are 15 holes that could be either filled or empty (of which a handful are irrelevant since the board starts with a hole)

Python, 324 chars, score = 319
f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

The peg state is kept as a bitmask.  M contains a list of peg states and the instructions to get to that state.
I could make it print out all of the solutions as well (there are 29760 of them), but it would cost more than 10 characters to do it.
I can't post it on ideone as it takes about 90 seconds to run.
Output:
Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

You only have to print out a minimum of 2 solutions in order to receive the 10-point bonus.

C, 386 chars, score = 371
int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

Prints out all 29760 solutions, in well under a second.
This version assumes (among other things) that the compiler will permit the implicit declaration of printf(). About six more characters could be saved by making use of implicit-int, but that feature was technically removed from C99.
Also, four more bytes can be saved by replacing the capital letters in the two strings with the corresponding control characters. I didn't do that here because compilers aren't required to permit such strings, and it makes already-dense source code completely illegible.
For clarity, here's the same algorithm without the more obfuscatory size-optimizations:
#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

f, o, and t are the list of legal jumps initialized in the first loop. r and i form the history that the program uses to backtrack and explore all possible games.
I'm sure this can be improved!

There's a one-char saving in the initialisation replacing >>1 by /2.

Using / instead of >> would need parens around the addition.

Ah, misread the parens because they're different in the ungolfed one.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
How many mesas begin with a given string?
Let's call a non-empty list of strings a mesa if the following conditions hold:

Each listed string is non-empty and uses only characters that occur in the first string.
Each successive string is exactly one character longer than the preceding string.
No string in the list is a subsequence of any other string in the list.

The term "mesa" is from visualizing like this (where the xs are to be various characters):
    xx..x
    xx..xx
    xx..xxx
    .
    .
    .
    xx..xxx..x

NB: It's a mathematical fact that only finitely many mesas begin with a given string. Note the distinction between subsequence vs.  substring; e.g., 'anna' is a subsequence (but not a substring) of 'banana'.
Challenge:

Write the shortest program that takes an arbitrary non-empty alphanumeric input string and outputs the number of mesas that begin with that string.

Input (stdin):

Any non-empty alphanumeric string.

Output (stdout):

The number of mesas that begin with the input string.

Scoring:

The winner is the program with the least number of bytes.

Example mesas
Only one mesa starts with a:
a

Only one mesa starts with aa:
aa

Many mesas start with ab:
ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa

How is the uniqueness of a mesa determined?  For instance, I could have ab, bbb as a mesa just by stopping at the second term.  Is that valid?  Or do they always have to be made as long as possible?  Also, if there are multiple possible rearrangements of the nth term (such as baa, aba, aab), do they all count as separate mesas as well (providing of course they all follow the rules)?

@mellamokb -- They're different mesas if they differ in any way at all. E.g., ab, ab/baa, ab/bbb, ab/bbb/bbaa, ab/bbb/bbaa/baaaa, ab/bbb/bbaa/baaaa/aaaaaa are different mesas.

@mellamokb -- You bring up other good questions; e.g., how many maximum-length mesas start with a given string, and what is that maximum length. Other versions of these questions would fix an alphabet of given size (alphabet size would be the input), and would consider all mesas (redefined without condition #1) that use only letters from the given alphabet -- again there are only finitely many.

GolfScript (106 103 chars)
n-..&1/:Z;]]0,\{.@+\{['']:E+.-2=,)E\{{`{+}+Z/}%}*{:x`{\1,+\{1$(@={\}*;}/0=!}+1$?!{.);[x]+\}*}/;}%.}do;,

Somewhere in the heart, of course, is some code from Is string X a subsequence of string Y?

Ruby, 142 characters
m=->l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

This algorithm is constructive, i.e. it builds all possible mesas for the input string and counts them. It makes the program really, really slow - but hey, it is codegolf.
Example runs:
> a
1
> aa
1
> ab
43

I was hoping that all mesas beginning with some of the nontrivial binary strings of length 3 (e.g. aab) are of feasible length, but I'm not sure -- your program has been running about an hour for that example. NB: There won't be feasible output for any input involving more than two distinct letters; e.g., some of the mesas that begin with abc have length greater than the 7000th Ackermann number.

I've built an optimized version in C#, and after I generated 300,000 entries with aab I still was seeing the first 10 or so terms being all identical.  So I think it might not be feasible for anything larger than two characters.  At least, not without some intelligence and heuristic calculations.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Reverse Engineer Polling Statistics
Introduction
Given a set of percentages of choices in a poll, calculate the minimum number of voters there must be in the poll to generate those statistics.
Example: What is your favorite pet?

Dog: 44.4%
Cat: 44.4%
Mouse: 11.1%

Output: 9 (minimum possible # of voters)
Specs
Here are the requirements for your program/function:

You are given an array of percentage values as input (on stdin, as function argument, etc.)
Each percentage value is a number rounded to one decimal place (e.g., 44.4 44.4 11.1).
Calculate the minimum possible number of voters in the poll whose results would yield those exact percentages when rounded to one decimal place (on stdout, or function return value).
Bonus: -15 characters if you can solve in a "non-trivial" way (i.e., doesn't involve iterating through every possible # of voters until you find the first one that works)

Example
>./pollreverse 44.4 44.4 11.1
9
>./pollreverse 26.7 53.3 20.0
15
>./pollreverse 48.4 13.7 21.6 6.5 9.8
153
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6
2000
>./pollreverse 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7
667
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7
2000
>./pollreverse 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8
401

Scoring
This is code-golf, so shortest possible characters wins.  Any bonuses are further subtracted from the total character count.

shouldn't sum of all votes be 100%? it's not in last four testcases

@Gajet: No it does not always equal 100%.  Every time there is a rounding down, you lose up to 0.5% from the total, and every time there is a rounding up, you add up to 0.5% to the total.  The last four test cases were purposely constructed to optimally exploit this phenomenon.  In the first test case that results in 2000, each of the first 9 entries represents 1 vote (and are all rounded up 0.5%), whereas the last one represents 1991 votes (and is rounded down ~0.5%).  If you calculate those percentages manually and round to 1 decimal place, you will see they are all correct.

I am struggling with the non-trivial answer in VBA (trying since so far, there have been none), but I'm working on it!

I rescind. [tag:VBA] doesn't like to mod with non-integers, and the code to correct is getting too long. I can create a working, non-trivial function for SIMPLE percentages, at least. :-)

Very similar: Find the smallest number of participants with resulting percentages

APL (Dyalog Classic), 48 43 bytes
-5 bytes by Adám
+/0(⊢+{(⌈/⍷⊢)⍺-⍵÷+/⍵})⍣{z≡⍎3⍕⍺÷+/⍺}⍨z←.01×⎕

Full program taking input from stdin.
Try it online! Link is to dfn version.
Ungolfed
normalize ← ⊢ ÷ +/
find_max ← {⍵⍷⍨⌈/⍵}
round ← {⍎3⍕⍵}
increase ← {find_max ⍺ - normalize ⍵}
vote_totals ← {z←⍺ ⋄ ⍺ (⊢+increase)⍣{z ≡ round normalize ⍺} ⍵}
h ← {+/ (.01×⍵) vote_totals 0}

Try it online!

normalize divides (÷) all elements of its right argument (⊢) by its sum (+/).
round(y) rounds y to 3 decimal places by formatting (⍕) and then evaluating (⍎) each element of y.
find_max(y) returns an array with 1 where max(y) is found and 0 elsewhere.
increase(x,y) takes x (the goal percentages) and y (the array of current vote totals) and calculates where to add 1 in y to bring the percentages closer to x.
vote_totals(x,y) takes x (the goal percentages) and y (the starting vote totals) and executes f repeatedly, adding votes until the percentages round to x.

The syntax f ⍣ g means to execute f repeatedly until g(y,f(y)) is true. In this case we ignore f(y).

h(x) sets y to 0 (equivalent to an array of 0s due to vectorization), executes g, and sums the final vote totals.

Python, 154
def p(x):
 n=[1]*len(x);d=2;r=lambda z:round(1000.*z/d)/10
 while 1:
    if(map(r,n),sum(n))==(x,d):return d
    d+=1
    for i in range(len(x)):n[i]+=r(n[i])<x[i]

It works for the last example now.
Example runs:
>>> p([44.4, 44.4, 11.1])
9
>>> p([26.7, 53.3, 20.0])
15
>>> p([48.4, 13.7, 21.6, 6.5, 9.8])
153
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 99.6])
2000
>>> p([0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 98.7])
667
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 98.7])
2000
>>> p([0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 97.8])
401

I think something may be wrong in your last example; perhaps you meant 99.1 as the last value

I think it's right but it's quite confusing. 1/2000 = 0.05% (0.1% rounded) and 1991/2000 = 99.55% (99.6% rounded). So if there are ten options in a poll and nine of them get voted for once while the last gets 1991 votes, then it would give those percentages.

You're right. Great solution, BTW.

I think you can save 3 more chars by following this tip: http://codegolf.stackexchange.com/a/58/3527

Thanks, w0lf. I've updated it now to include tabs. Tabs show up as four spaces if anyone's wondering.

Python, 154
def r(l):
 v=0
 while 1:
  v+=1;o=[round(y*v/100)for y in l];s=sum(o)
  if s:
    if all(a==b for a,b in zip(l,[round(y*1000/s)/10for y in o])):return s

+1 Looks good! http://ideone.com/k2Mgb. I tried to find a pathological case to break it and I couldn't.

I can't generate on ideone due to time-limit exceeding, but what result do you get for [0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,99.6]?

hmm... half an hour and the program is still running. I think its probably safe to say that's a breaker. however, I dont see how that can be a valid answer because it totals 100.5% and not 100%

1/2000 = 0.05% (0.1% rounded) and 1991/2000 = 99.55% (99.6% rounded). So it does actually total 100%, but the rounding makes it really confusing.

J, 57 characters
t=:".>'1'8!:0|:100*%/~i.1001
{.I.*/"1(t{~i.#t)e."1~1!:1[1

Used the trivial method. It takes input from the keyboard. t creates a lookup table and the second line looks for the input within the table. I can provide an expanded explanation of the code if anyone's interested.
I had looked into using the percentage to create a fraction then get the lowest form of the fraction to figure out the number, but I couldn't figure out a way to make it work with the rounding of the results.

Hmm, this fails for the new test case. I'll have to look for a fix.

VBA - 541
This has got some glaring errors, but it was my attempt to find a non-trivial/looping-until-I-get-the-right-number solution. I have not fully golfed it, though I don't think there's much to add in that regard. However, I've spent too much time on this, and it hurts my head now. Not to mention, the rules are probably very broken and apply more or less to these examples only.
This does very well for a lot of simple tests I ran, (i.e. even totals, 2 or 3 inputs) but it fails for some of the tests presented by the challenge. However, I found that if you increase the decimal precision of the input (outside the scope of the challenge), the accuracy improves.
Much of the work involves finding the gcd for the set of numbers provided, and I sort of got that through Function g(), though it is for sure incomplete and likely a source of at least some of the errors in my outputs.
Input is a space-delimited string of values.
Const q=10^10
Sub a(s)
e=Split(s)
m=1
f=UBound(e)
For i=0 To f
t=1/(e(i)/100)
m=m*t
n=IIf(n>t Or i=0,t,n)
x=IIf(x<t Or i=0,t,x)
Next
h=g(n,x)
i=(n*x)/(h)
If Int(i)=Round(Int(i*q)/q) Then
r=i
ElseIf (n+x)=(n*x) Then
r=(1/(n*x))/h/m
ElseIf x=Int(x) Then
r=x*(f+1)
Else
z=((n+x)+(n*x)+m)*h
y=m/(((m*h)/(f+1))+n)
r=IIf(y>z,z,y)
End If
Debug.Print Round(r)
End Sub
Function g(a,b)
x=Round(Int(a*q)/q,3)
y=Round(Int(b*q)/q,3)
If a Then
If b Then
If x>y Then
g=g(a-b,b)
ElseIf y>x Then
g=g(a,b-a)
Else
g=a
End If
End If
Else
g=b
End If
End Function

Testcases (input ==> expected/returned):
Passed:

"95 5" ==> 20/20
"90 10" ==> 10/10
"46.7 53.3" ==> 15/15
"4.7 30.9 40.4 23.8" ==> 42/42
"44.4 44.4 11.1" ==> 9/9
"26.7 53.3 20.0" ==> 15/15
"48.4 13.7 21.6 6.5 9.8" ==> 153/153
"0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.05 99.55" ==> 2000/2000
"0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 0.15 98.65" ==> 2000/2000
"0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 0.149925 98.65067" ==> 667/667

Failed:

"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 99.6" ==> 2000/1000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 98.7" ==> 2000/5000
"0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 98.7" ==> 667/1000
"0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 0.14 98.65" ==> 667/10000
"0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 97.8" ==> 401/500
"0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 0.24 97.75" ==> 401/235
"0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 0.249377 97.75561" ==> 401/14010

you can loose 6 bytes by converting Debug.Print  to Debug.?

C# (.NET Core), 286 bytes
double M(string[]a){var p=a.Select(double.Parse).ToList();var n=p.Select(x=>1d).ToList();var c=2;for(;;){Func<double,double>f=x=>Math.Round(x*1000/c,(MidpointRounding)1)/10;if(n.Select(f).Zip(p,(x,y)=>x==y).All(z=>z)&&c==n.Sum())return c;c++;n=n.Zip(p,(x,y)=>x+(f(x)<y?1:0)).ToList();}}

Try it online!
Saved lots of bytes thanks to Peter Taylor and Embodiment of Ignorance

How could I modify this to test it on ideone.com?

I think you're missing a } at the end.

@Gareth I tried to execute it on ideone.com, but I think it's using a .NET framework version earlier than 4.0, because it does not recognize the Linq Zip method.

@grc Thanks for pointing that out. Updated.

I've got it running on ideone.com: http://ideone.com/GofZ4.  Even for the simple test case 44.4 44.4 11.1 it errors out because it takes too long (6+ seconds).  Is that expected?  Edit: works just fine in LINQPad, maybe mono just isn't well optimized for LINQ.

@mellamokb thanks for testing the code. I don't know why it takes so long in ideone. I ran it in Visual Studio and there were no strange delays.

I'm not familiar with C#. Is while(1>0) necessary? Does while(1) not work?

@Gaffi: No, C# has strict typing (like Java) so it must be a boolean.  Since 1>0 is shorter than true, it is preferred.

Why is the argument called args? That's 6 characters straight down the pan. You can also save 2 chars by moving ++c into the while guard, and 1 by changing the first if guard to s>0. And I'm not sure whether you're counting any unnecessary whitespace, but you seem to be.

@PeterTaylor Thank you for all your great suggestions. I've updated my code and saved 7 characters. Leaving args in there was a really silly mistake.

@PeterTaylor the while(++c>0) is an ingenious trick, but unfortunately it won't compile unless I add another return statement, after the while loop. That's because the compiler knows it's never going to get out of while(1>0) unless there's a return in the while, but with the ++c>0 condition it does not have that guarantee at compile time.

Looks like this solution also goes into an infinite loop for some of my new test cases.  See the update to the question for the new test cases.  Here's a LINQPad-ready test case runner: http://pastebin.com/811wZtFG

@mellamokb You are right; I'll check why this happens and then fix the code

I have fixed the code.

I know this is really old, but can't you change the while(1>0) to for(;;)? Also, I'm pretty sure the code is only 300 bytes, without linebreaks. You can also use (MidpointRounding)1 instead of MidpointRounding.AwayFromZero

@EmbodimentofIgnorance Right, thanks! This is in fact a submission so old that now I realized I missed some basic golfing tricks, like cutting whitespace. Fixed now.

Python 3, 140 139 137 bytes
f=lambda l,m=1,i=0,c=0,x=0:round(x*100,1)-l[i]and(x<1and f(l,m,i,c,x+1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

Try it online!
Gives the right answer for the first two test cases, and runs into Python's recursion limits for the others. This is not very surprising, since every check is made on a new recursion level. It's short, though...
(An explanation of the used variables can be found in the TIO link)
f=lambda l,m=1,i=0,c=0,x=1:round(x*100,1)-l[i]and(x and f(l,m,i,c,x-1/m)or f(l,m+1))or l[i+1:]and f(l,m,i+1,c+x)or c+x-1and f(l,m+1)or m

should work for 136 bytes, but doesn't due to float precision.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/