Recovering Source Code Puzzle

A little math puzzle this week.

On an old computer system, I have a program, and part of of this program is a function called FooBar. The softcopy of the source code is missing, but I do have a hardcopy printout (shown below). Unfortunately, this printout has been damaged by water and the three important constants have been obscured.

I do, however, have a compiled version of the function and a test frame that allows me to input the three parameters: x,y,z and display the output of the function. I know that, for the language on this system, all variables are Natural Numbers of arbitrary length (that is, they are integers greater than, or equal to, zero).

The function is pretty simple, it takes three parameters, multiplies each with a distinct constant and outputs the sum of the these products. Your task is to recover the three constants A,B,C with the smallest number of calls to the function.

Three Variables, three unknowns

This does not seem that hard a problem !?!? We have three unknowns, so all we need is three (distinct) sets of input/output and we can solve the simultaneous equations. In fact, if we want to be be math lazy, since we can control the inputs, we can do something as simple as this to devine the constants:


print FooBar(1,0,0);     //returns A
print FooBar(0,1,0);     //returns B
print FooBar(0,0,1);     //returns C

But this is inefficient. We can actually do it with

just two calls

to the function. Huh? how is this possible? What Black Magic is this that allows you to determine three unknowns with just two answers? The secret is that we can leverage information gained from the first call of the function to adjust the parameters we call it with for the second time.

How can we do this with just two calls to the function?

Solution

Need some hints? Click the buttons below.

It would help you to learn what the maximum length of the answer could be.

What would FooBar(1,1,1); tell you? How many digits does this have?

The crucial fact to this puzzle is that all numbers are natural numbers. If you know the maximum number of digits that any of the constants could have you can use this as the radix for inputs to the second call. For example, if the maximum size any of the constants can be is d, then you could call the function with:

print FooBar (d*d, d, 1);

Each parameter is the radix position: x × d² , y × d¹ , z × d⁰, and you can see that the any digit cannot overflow into the next.

The answer will be, in base-d, the digits of the output. You can find out what the maximum size that any of the constants could be by calling FooBar(1,1,1);

If you wanted to be math lazy, and not convert between bases, you could stay in decimal by using log₁₀, and the ceiling function to find the max number of digits.

As an example, let's pretend that A=17, B=63, C=255

Calling r=FooBar(1,1,1) gives the result 335. We can can see that if we set d=1,000 (which is 10^ceil(log(r))), we can make the second call as FooBar(1000*1000,1000,1).

The result will come back as: 17063255, which can be parsed as A=017, B=063, C=255. Bingo!

Interestingly, with arbitrary length variables, there is no theoretical limit to the number of parameters we can determine with just two calls!