Count the number of times a function runs

Question

This is a teaser a friend of mine sent. It seems straightforward, but I can't seem to get my head around it, probably due to my lack of sleep.

1. You have 16 bits available.
2. Compose a function, and find a way to know when the function has run approximately one million times.
3. You MAY NOT use any additional memory space other than the 16 bits given.
4. Recursion may be used for efficiency, but, again, you MAY NOT use memory definition inside the recursion frames: only the 16 bits.

Answer 1

One-million in binary is equal to 11110100001001000000 (20 bits). Thus, we cannot implement a simple counter for this.

Instead, the max number we can represent with 16 bits is 1111111111111111 = 65,535. Since the answer requires that we only need to approximate 1 million function runs, we could add one to the counter approximately once every 16 function runs, and know that the function has run about 1 million times when the counter reaches 1000000/16 = 62500.

Below is the pseudocode of a potential solution, assuming that counter is a positive integer stored in 16 bits. Also, this assumes that calls such as random(1,16) do not count towards memory as long as they are not stored in a variable. Last, the random(x,y) function should give a random integer between x and y inclusive.

counter = 0;

function amIAttaBoutaMillionYet(){
    if(random(1,16)==16 && counter<62501){
        counter++;
    }
    if(counter==62500){
        return true;
    }
    return false;
}

UPDATE

Fixed function so that it won't show true after about 2 million+, 3 million+, etc. function runs. (thanks trinithis!)

Answer 2

Beaten to it by Briguy37. :-(

Just call the function code 16 times for each tick of the counter.

def function()
{
    do stuff here...
}
while(loop<65535)
{
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    function()
    loop+=1
}

Answer 3

You could make it so that for every external call of function A, A is called another 999,999 times internally. Therefore, you are guaranteed that that last internal call is the millionth call.

var internal = false;
function A() {
    if (internal)
        return;

    internal = true;

    A();
    A();
    // ...999999 times...
    A();
    A(); // This last call is guaranteed to be the millionth call

    internal = false;
}

A();

Answer 4

The obvious approach is self-modifying code. Something along the lines of (and bearing in mind that I scarcely ever touch C, consider this to be pseudocode and don't try compiling it)

uint16 counter = 0;

void fun() {
    byte x = 0;
    if (x == 15) counter++;
    (*fun)=(x+1)&15;
    if (counter == 62500 && x == 0) sprint("Jackpot!");
}

It is, of course, cheating, but so is every possible approach, because the problem taken literally violates basic principles of information theory. And there may be a small offset needed when overwriting the initial value of x: depends on your processor and compiler. (No, I'm not going to dig out my notes on ARM assembler just for this).

Answer 5

Primary answer:

Does not use crazy macro expansion. Uses recursion and two 8 bit variables. The code works by recursing enough such that the first call to foo generates enough calls where the function is called approximately 1 million times.

//unsigned long count = 0;
//unsigned long numTimesTrue = 0;

#define SET_HIGH(x) (x |= (unsigned char)(1 << 7))
#define MASK_HIGH(x) (x & (unsigned char)~(1 << 7))
#define TEST_HIGH(x) (x & (unsigned char)(1 << 7))

int foo (unsigned char n = 0) {
    static unsigned char i;
    //++count;
    if (n == 0) {
        SET_HIGH(n);
    }
    if (MASK_HIGH(i) >= 20) {
        return 0;
    }
    for (i = n; MASK_HIGH(i) < 20; ++i) {
        n = i;
        foo(MASK_HIGH(i) + 1);
        i = n;
    }
    //if (TEST_HIGH(i) != 0) ++numTimesTrue;
    return TEST_HIGH(i) != 0;
}

int main () {
    int r1 = foo(); // 1, count == 1048576
    int r2 = foo(); // 0, count == 1048577
    int r3 = foo(); // 0, count == 1048578
    //assert(numTimesTrue == 1);
    return 0;
}

Secondary answer:

This returns true only once and only when the function has been run approximately 1 million times. I'm talking liberty in the usage of the word approximate in that the integers are unbounded. (1 is approximately 1,000,000 with respect to 100!!!!!! (you have to figure out which are factorials and which are exclamation points).)

int foo () {
    static int hasRun = 0;
    if (!hasRun) {
        hasRun = 1;
    }
    return !hasRun;
}

Answer 6

Python

Likely also bending the rules:

x = 0 
def f():
    global x
    if x < 20:
        x = x + 1
        f()
        f()
        x = x - 1

Arguably could do with just 5 bits, and would probably be shorter in C. Stretches rule (3) perhaps a bit.

Answer 7

C

it's actually 6 bit. (Does rand() == 12679 count...?)

void func(void)
{
    static struct { 
        unsigned short int count : 6; 
    } S = {42};
    if (rand() == 12679)
        S.count--;
    if (!S.count)
        puts("1 MILLION REACHED");
}

Answer 8

C

This answer changes the name of the process, and more precisely uses the first character of the name as an additional 8-bits counter.

#include <stdio.h>

int main(int argc, char* argv[])
{
unsigned short cpt=0;

argv[0][0]=0;
while(argv[0][0]!=20)
    {
    cpt++;

    /* the function printf is called 1.0000.000 times */
    printf("ok\n");

    if (cpt==50000)
        {
        cpt=0;
        argv[0][0]++;
        }
    }

}

Answer 9

Well, similar to Briguy37. I divided the 16 bits to two 8 bits vars. low byte is incremented on every call and reset when it reaches 250. On reset of low byte increment hi. When hi reaches 4000 (1000000/250 = 4000), we have 1 million calls

    byte hi=0
    byte lo=0

    function oneMillionCallFunction()
        lo++
        if lo==250 then
            hi++
            lo=0
        if hi==4000 then
            return true
        return false

Answer 10

to implement Briguy's solution in D

import std.random;
bool foo(){
    static ushort count = 0;//16 bits
    if(uniform(0,16)==0)count++;//increment once in approx every 16 calls
    if(count==62500)return true;//we're close enough
    return false;
}

Answer 11

This scala-code contains the test, to see how much we are away:

val r = util.Random 

def resetAndTest () {

var x = 0 : Short

def mioFun (n: Int) = {
  if (r.nextInt (30518) < 1000) 
    x = (x + 1).toShort 
  if (x < 0) { 
    println ("n calls " + n )  
    true } 
  else false
} 

(1 to 1010000).find (mioFun) 

}

typical results:

scala> (1 to 10).foreach (_ => resetAndTest)
n calls 1001214
n calls 1000340
n calls  993883
n calls 1005774
n calls 1001670
n calls  997401
n calls 1009786
n calls  992853
n calls 1002313
n calls 1002992

Answer 12

I just had a strange idea - but it works. This python version works without any counter. The one-millionth call returns 1 any other the value 0.

def fun(): 
    global f
    try:
      f
    except NameError:
      def fun_int():
        yield 0
        yield 0
        ...
        yield 0
        yield 1
        while 1:
          yield 0
      f = fun_int()
    return f.__next__()

print(fun())
print(fun())
...
print(fun())
print(fun())

Unfortunately the generator reference f takes some bits - so please use a python implementation which does it in 16 bits or less.

Answer 13

Since Peter Taylor points out that using a PRNG may violate the 16-bit limit, what about using the system time? Would that also violate the limit?

In PHP:

$counter = 0;
function maybeOneMillion() {
  global $counter;
  $time = gettimeofday();
  if ($time['usec'] % 100 == 0) {
    $counter++;
    if ($counter == 10000) return true;
  }
  return false;
}