4
\$\begingroup\$

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.
\$\endgroup\$

closed as unclear what you're asking by Blue, Rɪᴋᴇʀ, NoOneIsHere, acrolith, DJMcMayhem Aug 30 '16 at 17:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ What is the 16 bits? 16 bits of function definition in machine language? 16 bits of memory storage, but the function can be as large as necessary? What is this function supposed to do? Stop when it has been run one million times? Display a message when it has been run one million times? Is this function being randomly called by another program and you have to track, or is this function being run one million times in a row at the same time? Can you describe in pseudo-code how this function works/is used in this process? \$\endgroup\$ – mellamokb Aug 24 '11 at 17:35
  • 2
    \$\begingroup\$ Superbly underspecified. \$\endgroup\$ – Thomas Eding Aug 24 '11 at 19:44
  • 1
    \$\begingroup\$ I understand: store the number of invocations (or whatever you like) in 16 bits. But should be clarified. \$\endgroup\$ – user unknown Aug 25 '11 at 4:53
  • 1
    \$\begingroup\$ Bearing in mind that a standard PRNG, which all the approachs so far are using, probably has at least 48 bits of internal state, that approach fails point 3. \$\endgroup\$ – Peter Taylor Aug 25 '11 at 6:10
  • 2
    \$\begingroup\$ See 2.: You have to compose a function, and count, how often it is called. You're composing a function, and count another functions invocations (which isn't composed - it's just a name). \$\endgroup\$ – user unknown Aug 25 '11 at 13:56

13 Answers 13

8
\$\begingroup\$

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!)

\$\endgroup\$
  • \$\begingroup\$ This suffers from overflow if called too much, as numbits(counter) <= 16. Add a guard against incrementing counter if counter is greater than some number (say counter > 62500). \$\endgroup\$ – Thomas Eding Aug 26 '11 at 0:33
  • \$\begingroup\$ @trinithis: Thanks, I missed that! \$\endgroup\$ – Briguy37 Aug 26 '11 at 19:06
2
\$\begingroup\$

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
}
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for finding a different rule to break. (You're breaking rule 2 as specified, because you're executing the function 1m times rather than finding out when it's been called 1m times). \$\endgroup\$ – Peter Taylor Aug 25 '11 at 8:25
  • \$\begingroup\$ @Garet: You could make the function private and then turn the while loop into a public controller function that runs the function 16 times, increments the counter, and then returns if the function has run about 1 million times. You could even make it know when the function has run exactly 1 million times if you synchronized the controller method. Admittedly, then the function can never have a single run, which doesn't break any rules, but it doesn't feel right either :) \$\endgroup\$ – Briguy37 Aug 25 '11 at 13:34
  • \$\begingroup\$ Sorry Gareth...that's twice now I've typed your name wrong...doh! \$\endgroup\$ – Briguy37 Aug 26 '11 at 19:11
2
\$\begingroup\$

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();
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ If you've got an additional variable x, aren't you breaking the 'only 16 bits' rule? \$\endgroup\$ – Gareth Aug 25 '11 at 8:08
  • 1
    \$\begingroup\$ @Gareth, observe the text It is, of course, cheating. It is mathematically impossible to solve this problem without breaking that rule; therefore the purpose of the puzzle must be to find inventive ways of breaking it. \$\endgroup\$ – Peter Taylor Aug 25 '11 at 8:22
  • \$\begingroup\$ Fair point, I missed that bit. \$\endgroup\$ – Gareth Aug 25 '11 at 9:00
1
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ hi will never reach 4000 (this requires 12 bits and lo's 250 requires 8: 8+12=20) \$\endgroup\$ – ratchet freak Aug 24 '11 at 19:21
  • \$\begingroup\$ ohh.. i should not code after drinking.. :P \$\endgroup\$ – Kapil Ratnani Aug 24 '11 at 19:29
  • 3
    \$\begingroup\$ In fact, keeping two 8-bit numbers and incrementing the high-bit one every time the low-bit one overflows is exactly the same as keeping one 16-bit number. \$\endgroup\$ – Clueless Aug 24 '11 at 20:49
0
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Protip: f.x No need for globals here. \$\endgroup\$ – seequ Jun 4 '14 at 18:00
0
\$\begingroup\$

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");
}
\$\endgroup\$
0
\$\begingroup\$

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]++;
        }
    }

}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.