Memory is Expensive

Question

You are a robot. You are stranded in a small cage with weird humans wearing weird suits looking at you. Your solar panel is malfunctioning, and your energy is running out. On the wall there is a riddle, and if you answer correctly the humans will grant you access to an energy source (yay!). However your RAM unit is leaking power, and the more you use it, the more energy will be lost.

For each byte you access, you spend 1 energy unit (a bit costs 1/8 energy).

The program that uses the least energy wins.

Arrays cost the sum of all their variables. Strings and other non-fixed-length variables/arrays are prohibited, as your bot will be unable to calculate how much energy it spent. (Recursion is prohibited too!)

The riddle is weird, it changes after a while, so your bot must not hardcode the answer.

The riddle is a mathematical challenge:

We shall input you with 3 variables, and they are free, but you shall not change them.

For these 3 inputs, a, b and c, thou shalt calculate an integer p equivalent to floor(pi * 10^(c-1)), then you shall calculate x = a!/b!. Then you shall add to x the integer p. If and only if c is greater than x, you shall yell Pi!!!!

a, b and c are integers smaller than the number 13.

Example: for a = 5, b = 4, and c = 3, calculate 5!/4! + 314. as x = 5, and c = 3, don't yell Pi!!!!

Once finished calculating, your bot should output the answer. The input can be either in form of calling a function or the user typing a number when prompted.

If 2 bots have the same energy spending, the shortest code wins.

Also, the energy cost is for the worst case (that's why I said a, b and c are smaller than 13). (Extra clarification: the language overheads don't count, unless you abuse them to store data.)

Answer 1

AVR (274 bytes, 0 energy points)

With all those fancy high-level languages you're never really sure how much RAM you're accessing. The only way to be sure is to nuke it from orbit go down to the bytes. Fortunately I just happen to be teaching myself assembler at the moment.

This submission is a subroutine that uses the AVR-GCC calling convention. Fortunately it so happens that both the return value and the arguments fit in registers. The return value will be at most 12! + floor(pi * 10^11) = 0x49 41 e6 f2 4e (five bytes) and each of the arguments is at most 12 (one byte each). Each size is rounded up to the nearest multiple of two, so we get a total size of 6 + 2 + 2 + 2 = 12 bytes. Starting at R25, the return value fits in R20-R24, and the arguments live in R18, R16, and R14.

Note that as per the rules ("... but you shall not change [the inputs].") I don't write to R18, R16, or R14. I also don't explicitly use the stack or access anything other than the registers, meaning only two bytes are ever read from RAM during the whole program: RET reads the return address from the stack. However, the rules state "language overheads don't count," so the total score is zero.

The only other oddity is that I don't have a printf function, so in order to "yell" I bit-bang a generic parallel interface on port D. (That's digital pins 0-6 if you run this on an Arduino UNO, with pin 7 being the clock.)

Here is the code itself. All the jumps are relative, so you can plop this anywhere in your program and have it work.

4e e4 56 ef 69 e5 75 e2 89 e4 90 e0 
22 24 23 94 33 24 44 24 55 24 77 24 
60 2e 63 94 20 17 10 f4 22 24 12 c0 
26 15 80 f0 56 9c 50 2c 46 9c 40 2c 
51 0c 36 9c 30 2c 41 0c 57 1c 26 9c 
20 2c 31 0c 47 1c 57 1c 63 94 ee cf 
57 14 01 f5 47 14 f1 f4 37 14 e1 f4 
2e 14 d0 f4 10 e5 1b b9 10 68 1b b9 
19 e6 1b b9 10 68 1b b9 11 e2 1b b9 
10 68 1b b9 1f 77 1b b9 10 68 1b b9 
1f 77 1b b9 10 68 1b b9 1f 77 1b b9 
10 68 1b b9 00 00 7b b8 1c e0 61 2e 
6e 18 c9 f1 13 e3 81 9f 80 2d 91 2d 
71 9f 70 2d 81 0d 97 1d 61 9f 60 2d 
71 0d 87 1d 97 1d 51 9f 50 2d 61 0d 
77 1d 87 1d 97 1d 41 9f 40 2d 51 0d 
67 1d 77 1d 87 1d 97 1d 45 0f 56 1f 
67 1f 78 1f 89 1f 97 1d 46 0f 57 1f 
68 1f 79 1f 87 1d 97 1d 48 0f 59 1f 
67 1d 77 1d 87 1d 97 1d 45 2f 56 2f 
67 2f 78 2f 89 2f 99 27 86 95 77 95 
67 95 57 95 47 95 6a 94 39 f6 42 0d 
53 1d 64 1d 75 1d 87 1d 08 95

Here is the breakdown, including a short header to demonstrate calling the function.

0x0000  1fef      ldi  r17, 0xFF  ; write 1111 1111
0x0002  1ab9      out  0x0a, r17  ; to port D direction register
0x0004  10e0      ldi  r17, 0x00  ; write 0000 0000
0x0006  1bb9      out  0x0b, r17  ; to port D output register
0x0008  25e0      ldi  r18, 0x05  ; set a to 5
0x000a  04e0      ldi  r16, 0x04  ; set b to 4
0x000c  13e0      ldi  r17, 0x03  ;
0x000e  e12e      mov  r14, r17   ; set c to 3 (can't ldi, r14 < r16)
0x0010  0e940a00  call 0x14       ; call our subroutine @ 0x0014
0x0014  4ee4      ldi  r20, 0x4E  ; initialize output
0x0016  56ef      ldi  r21, 0xF6  ; with maximum 'pi integer'
0x0018  69e5      ldi  r22, 0x59  ; Floor[Pi*10^11]
0x001a  75e2      ldi  r23, 0x25  ;  = 314 159 265 358 (12 digits)
0x001c  89e4      ldi  r24, 0x49  ;  = 0x 49 25 59 f6 4e
0x001e  90e0      ldi  r25, 0x00
0x0020  2224      eor  r2, r2     ; initialize x
0x0022  2394      inc  r2         ; to 1
0x0024  3324      eor  r3, r3     ; (eor clears a byte)
0x0026  4424      eor  r4, r4
0x0028  5524      eor  r5, r5
0x002a  7724      eor  r7, r7     ; r7 stays zero (handy)
0x002c  602e      mov  r6, r16    ; count = b
0x002e  6394      inc  r6         ; count++
0x0030  2017      cp   r18, r16   ; if a >= b
0x0032  10f4      brcc .+4        ; go to loop @ 0x0038
0x0034  2224      eor  r2, r2     ; otherwise x is zero
0x0036  12c0      rjmp .+36       ; go to end of loop @ 0x005c
0x0038  2615      cp   r18, r6    ; if a < count
0x003a  80f0      brcs .+32       ; go to end of loop @ 0x005c
0x003c  569c      mul  r5, r6     ; otherwise multiply high byte by count
0x003e  502c      mov  r5, r0     ; copy low byte of result (high byte = 0)
0x0040  469c      mul  r4, r6     ; multiply second byte by count
0x0042  402c      mov  r4, r0
0x0044  510c      add  r5, r1     ; carry 
0x0046  369c      mul  r3, r6     ; multiply third byte
0x0048  302c      mov  r3, r0
0x004a  410c      add  r4, r1
0x004c  571c      adc  r5, r7
0x004e  269c      mul  r2, r6     ; multiply low byte
0x0050  202c      mov  r2, r0
0x0052  310c      add  r3, r1
0x0054  471c      adc  r4, r7
0x0056  571c      adc  r5, r7
0x0058  6394      inc  r6         ; count++
0x005a  eecf      rjmp .-36       ; return to start of loop @ 0x0038
0x005c  5714      cp   r5, r7     ; if any of the high bytes of x
0x005e  01f5      brne .+64       ; are nonzero
0x0060  4714      cp   r4, r7     ; then jump past 'yelling'
0x0062  f1f4      brne .+60       ; @ 0x00a0
0x0064  3714      cp   r3, r7
0x0066  e1f4      brne .+56
0x0068  2e14      cp   r2, r14    ; only the low byte is a comparison 
0x006a  d0f4      brcc .+52       ; since c is only one byte long
0x006c  10e5      ldi  r17, 0x50  ; write 'P' to buffer
0x006e  1bb9      out  0x0b, r17  ; write to PORTD
0x0070  1068      ori  r17, 0x80  ; set clock bit (buffer |= 1000 0000)
0x0072  1bb9      out  0x0b, r17  ; PORTD
0x0074  19e6      ldi  r17, 0x69  ; 'i'
0x0076  1bb9      out  0x0b, r17  ; PORTD
0x0078  1068      ori  r17, 0x80  ; 1000 0000
0x007a  1bb9      out  0x0b, r17  ; PORTD
0x007c  11e2      ldi  r17, 0x21  ; '!'
0x007e  1bb9      out  0x0b, r17  ; PORTD
0x0080  1068      ori  r17, 0x80  ; 1000 0000
0x0082  1bb9      out  0x0b, r17  ; PORTD
0x0084  1f77      andi r17, 0x7F  ; clear clock bit (buffer &= 0111 1111)
0x0086  1bb9      out  0x0b, r17  ; PORTD
0x0088  1068      ori  r17, 0x80  ; 1000 0000
0x008a  1bb9      out  0x0b, r17  ; PORTD
0x008c  1f77      andi r17, 0x7F  ; 0111 1111
0x008e  1bb9      out  0x0b, r17  ; PORTD
0x0090  1068      ori  r17, 0x80  ; 1000 0000
0x0092  1bb9      out  0x0b, r17  ; PORTD
0x0094  1f77      andi r17, 0x7F  ; 0111 1111
0x0096  1bb9      out  0x0b, r17  ; PORTD
0x0098  1068      ori  r17, 0x80  ; 1000 0000
0x009a  1bb9      out  0x0b, r17  ; PORTD
0x009c  0000      nop             ; baud rate is 1/4 processor speed
0x009e  7bb8      out  0x0b, r7   ; PORTD
0x00a0  1ce0      ldi  r17, 0x0C  ; buffer = 12
0x00a2  612e      mov  r6, r17    ; count = buffer (# of places in p)
0x00a4  6e18      sub  r6, r14    ; count -= c (# of /= 10 we need)
0x00a6  c9f1      breq .+114      ; if count == 0 skip loop @ 0x011a
0x00a8  13e3      ldi  r17, 0x33  ; buffer = 51
0x00aa  819f      mul  r24, r17   ; following the same procedure as before
0x00ac  802d      mov  r24, r0    ; we multiply p by 51
0x00ae  912d      mov  r25, r1
0x00b0  719f      mul  r23, r17   ; since we can't divide by 10
0x00b2  702d      mov  r23, r0    ; we divide by 5
0x00b4  810d      add  r24, r1    ; by multiplying by
0x00b6  971d      adc  r25, r7    ; 0b0.00110011001100110011
0x00b8  619f      mul  r22, r17   ; equivalent to multiplying by
0x00ba  602d      mov  r22, r0    ; 0b110011 = 51
0x00bc  710d      add  r23, r1    ; then repeatedly adding to itself
0x00be  871d      adc  r24, r7    ; shifted right by one byte
0x00c0  971d      adc  r25, r7
0x00c2  519f      mul  r21, r17
0x00c4  502d      mov  r21, r0
0x00c6  610d      add  r22, r1
0x00c8  771d      adc  r23, r7
0x00ca  871d      adc  r24, r7
0x00cc  971d      adc  r25, r7
0x00ce  419f      mul  r20, r17
0x00d0  402d      mov  r20, r0
0x00d2  510d      add  r21, r1
0x00d4  671d      adc  r22, r7
0x00d6  771d      adc  r23, r7
0x00d8  871d      adc  r24, r7
0x00da  971d      adc  r25, r7
0x00dc  450f      add  r20, r21   ; add p to itself, shifted one byte
0x00de  561f      adc  r21, r22
0x00e0  671f      adc  r22, r23
0x00e2  781f      adc  r23, r24
0x00e4  891f      adc  r24, r25
0x00e6  971d      adc  r25, r7
0x00e8  460f      add  r20, r22   ; shifted two bytes
0x00ea  571f      adc  r21, r23
0x00ec  681f      adc  r22, r24
0x00ee  791f      adc  r23, r25
0x00f0  871d      adc  r24, r7
0x00f2  971d      adc  r25, r7
0x00f4  480f      add  r20, r24   ; shifted four bytes
0x00f6  591f      adc  r21, r25
0x00f8  671d      adc  r22, r7
0x00fa  771d      adc  r23, r7
0x00fc  871d      adc  r24, r7
0x00fe  971d      adc  r25, r7
0x0100  452f      mov  r20, r21   ; shift right one byte
0x0102  562f      mov  r21, r22
0x0104  672f      mov  r22, r23
0x0106  782f      mov  r23, r24
0x0108  892f      mov  r24, r25
0x010a  9927      eor  r25, r25   ; clear top byte
0x010c  8695      lsr  r24        ; finally divide by two
0x010e  7795      ror  r23        ; by shifting right one bit
0x0110  6795      ror  r22
0x0112  5795      ror  r21
0x0114  4795      ror  r20
0x0116  6a94      dec  r6         ; count--
0x0118  39f6      brne .-114      ; if count != 0, repeat @ 0x00a8
0x011a  420d      add  r20, r2    ; add x to p
0x011c  531d      adc  r21, r3
0x011e  641d      adc  r22, r4
0x0120  751d      adc  r23, r5
0x0122  871d      adc  r24, r7
0x0124  0895      ret             ; return

Note that the since the subroutine directly follows the main routine, the subroutine is actually executed twice. The second RET call then tries to read from an empty stack. I left this behavior in the minimal example, since it's not a problem if you go step-by-step through the AVR simulator, and I wanted to keep the byte count low.

Mathematica (70 bytes, 6 energy points)

Function[{a,b,c},If[c>a!/b!,Print["Pi!!!!"]];a!/b!+Floor[Pi 10^(c-1)]]

• a, b, and c are 'free', and don't count towards the number of accesses.
• The string contains six characters, which count as six bytes.

Answer 2

Javascript (155 bytes, 14+ accesses)

Alright, this isn't the most golfed answer.

Quoting this: "Arrays cost the sum of all their variables"... I have no idea how to interpret this, since an array is simply a set of values all aligned in the memory.

Also, there's no information about how to access functions or anything else.

But here is the code:

function(a,b,c){var m=[1,1,2,6,24,120,720],f=function(n){return m[n]=m[n]?m[n]:n*f(n-1)};return ((f(a)/f(b))+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

For the score (using a=5, b=4, and c=3):

1. Creates an array with the factorial until 7 already there (? accesses)
2. Creates a variable f with a function to access the array (? accesses)
3. Calculates the factorial of a (2 accesses)
4. Calculates the factorial of b (2 accesses)
5. Divides them (2 accesses)
6. Calculates the sum of the number "equivalent to PI" (Math.PI*Math.pow(10,c)>>0) now it is only 3 accesses since it fetches c characters from the string and converts to integer:
   • Gets the value of PI (∞ accesses)
   • Calculates the power of 10 to multiply by Math.PI (∞ accesses + 1)
   • Sums it all together (2 accesses)
   • Rounds it (1 access)
7. Compares with c (2 accesses)
8. Either returns an empty string (0 accesses) or PI!!!! (6 accesses).

Result: To be improved! The battery would die in no time! DO NOT RUN THIS CODE ON YOUR ROBOT OR IT WILL EXPLODE

I assume that the access to the window object is ∞ (infinite) due to the fact that it contains everything, including itself.

Conclusion: I'm missing some crucial information and explanation to calculate the final number of accesses. But shouldn't be too bad, right?

---

Why am I using var? Simple: if it is declared without var, it is effectively accessing the window object which is a ∞ (infinite) number of accesses and the battery wouldn't even last 1 nanosecond. We would have a very fast drain, probably followed by an explosion.

---

Javascript (165 bytes, 31 bytes for the factorial array + 16 accesses):

This one should be easier to calculate

function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(+'3141592653589'.substr(0,c)))<c?'PI!!!':'';}

It has a 31 bytes-long list with all the 13 factorial numbers required.
It was calculated with the following code:

var i=0,m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800],k;for(k in m)i+=Math.ceil(m[k].toString(2).length/8);

This makes it faster (if time is critical) and cleaner both for humans and machines. With a VERY good branch-prediction, the number of accesses could be reduced to 7 accesses.

It works as the code above, except that it doesn't have to calculate the factorial.

---

Javascript (3 bytes, self-destruction)

Yes, the smallest losing entry!

It drains your battery so fast it will explode!

It's simple, just run:

top

And you are set. top is a variable that will access to window.top, which is the same as window, which has recursion EVERYWHERE

---

Javascript (31*2+6+6 bytes (592 bits), 187*2+42+38=494 bits ):

Same thing as before, but a lot easier to calculate the number of accesses:

function(a,b,c){var m=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800];return ((m[a]/m[b])+(''.substr.call(3141592653589,0,c)))<c?'PI!!!':'';}

Empty strings and 0 aren't being calculated. Why? They are NOTHING in the memory. They only have a datatype.

The aray is being accessed twice, so, I'm counting that the entire array must be scattered.

If not, then the number of accesses drops to 22 bytes (146 bits)!!!

That is for the worst case!!!

Answer 3

Both of these are ports of @IsmaelMiguel's answer.

K, 59 bytes, # of accesses is proportional to input size

f:{:[z>(l[x]%(l:*/1+!:)y)+0$z#"3141592653589";"PI!!!!";""]}

The number of accesses would be something like (assuming a, b, and c are free):

a*4+b*4+19

C89, 172 bytes (DON'T LOOK! CAST AWAY!)

int l(int n){int r=1;while(n--)r*=r;return r;}char s[]="PI!!!!";char*f(int a,int b,int c) {char p[]="3141592653589";p[c-1]=0;if(l(a)/l(b)+strtol(p,0,0)>=c)s[0]=0;return s;}

Apparently we're not allowed to use recursion, so this increased by several characters. Darn it.

Again assuming a, b, and c are free, the # of accesses might be something like:

a*4*4+b*4*4+3*4+3*8+15 == a*16+b*16+51

Thanks to @mbomb007 for pointing out I accidentally forgot an exclamation mark in "PI!!!!".

Answer 4

Java (4 Energy points, maybe)

Here's my solution. I am not entirely sure how to score it as I might be invalid.

Calculating p wasn't part of the output so I skipped it (the people holding the bot wouldn't know if it was calculated or not). Also, I'm not sure if this is counts for hardcoding and I don't have enough rep to comment to ask.

public class Bot {
    public void foo(final int a, final int b, final int c) {
        if (b > a) {
            return;
        }
        int x = a - b;
        if (x > 4) {
            return;
        } else if (x == 3 && c < 7) {
            return;
        } else if (x == 2 && c < 3) {
            return;
        } else if (c < 2) {
            return;
        }
        System.out.println("Pi!!!!");
    }
}