To improve our programming skills and as a part of self-improvement exercise we are supposed to spend sometime every week as a part of Company Policy. Last fortnight my team has put their mind on test with one puzzle (passed on to us by other programming department) and it went quite well for everyone.
It was more about basic math rather than programming and it was good to see everyone refreshing their mind with roots of math/programming. I am sharing this puzzle/question on my blog and want my reader to put their mind and some of their time to crack this and put down their results as comments on this post.
Here we go:
Assume that you have a abstract computer, so forget everything you know about computers, this one only does what I am about to tell you it does.
- You can use as many variables as you need,
- There are no negative numbers,
- All numbers are integers.
- You do not know the size of the integers, they could be infinitely large, so you cannot count on truncating at any point.
- There are NO comparisons allowed, no if statements or anything like that.
- There are only four operations you can do on a variable.
- You can set a variable to 0.
- You can set a variable = another variable.
- You can increment a variable (only by 1), and it is a post increment.
- You can loop. So, if you were to say loop(v1) and v1 = 10, your loop would execute 10 times, but the value in v1 would not change so the first line in the loop can change value of v1 without hanging the number of times you loop.
You need to perform 3 operations:
- Write a function that decrements by 1.
- Write a function that subtracts one variable from another.
- Write a function that divides one variable by another.
(See if you can implement all 3 using at most 4 variables.)Meaning, you are not making function calls now, you are making macros. And at most you can have 4 variables.
The restriction really only applies to divide, the other 2 are easy to do with 4 variables or less. Division on the other hand is dependent on the other 2 functions, so, if subtract requires 3 variables, then divide only has 1 variable left unchanged after a call to subtract.
Basically, just make your function calls to decrement and subtract so you pass your variables in by reference, and you can not declare any new variables in a function, what you pass in is all it gets.
Although one can search through Internet to get the answer to this Question but it would be fun to see how long it takes one to crack it and how much of 3 operations.
Readers if you try this, please write down your scores (Time and no of Operations) as a comment. I am sure I don't need to put on the answer here.
#1 by Roger on January 12, 2009 - 7:01 pm
Quote
I don´t know if i am too stupid or what, but I don´t get it, how can you substract if there are no negative numbers and you can only set a variable to 0 or another variable, loop, and increment it? also what do you mean by a post increment?, i guess you beat me…i´ve been thinking about it for an hour now and i can´t think of anything!
#2 by Craig Francis on January 12, 2009 - 9:56 pm
Quote
My answers… (spoiler alert)
Not sure if this is within the confines of this system, but as a “post increment” was allowed, I’ve combined that with a variable assignment pre the variables increment.
#################################################
1) Decrements by 1 (about 15 minutes)
$a = 3; // Variable 1
$b = 0; // Variable 2
loop ($a) {
$a = $b++;
}
echo $a;
If your interested in testing, I implemented the loop with:
for ($k = 0, $z = $a; $k < $z; $k++)
#################################################
2) Subtracts one variable from another (about 10 minutes)
$a = 5; // Variable 1
$b = 2; // Variable 2
loop ($b) {
$b = 0;
loop ($a) {
$a = $b++;
}
}
echo $a;
And for testing, the loops were:
for ($j = 0, $x = $b; $j < $x; $j++)
for ($k = 0, $z = $a; $k 0), and I’ve spent another hour trying to reduce it down to 4 variables (no luck so far)… but this is what I’ve got at the moment:
$a = 8; // Variable 1
$b = 2; // Variable 2
$c = 0; // Variable 3
$d = 0; // Variable 4
$e = 0; // Variable 5
loop ($a) {
$c++;
loop ($a) {
$e = $a;
loop ($b) {
$d = 0;
loop ($e) {
$e = $d++;
}
}
$d = $c;
}
$a = $e;
}
echo $d;
And for testing, the loops were:
for ($h = 0, $w = $a; $h < $w; $h++) {
for ($i = 0, $x = $a; $i < $x; $i++) {
for ($j = 0, $y = $b; $j < $y; $j++) {
for ($k = 0, $z = $e; $k < $z; $k++) {
#################################################
#3 by Craig Francis on January 12, 2009 - 9:58 pm
Quote
OK, last post was messed up because of the less than sign (should have known)… try this instead…
—
My answers… (spoiler alert)
Not sure if this is within the confines of this system, but as a “post increment” was allowed, I’ve combined that with a variable assignment pre the variables increment.
#######################################
1) Decrements by 1 (about 15 minutes)
$a = 3; // Variable 1
$b = 0; // Variable 2
loop ($a) {
$a = $b++;
}
echo $a;
If your interested in testing, I implemented the loop with:
for ($k = 0, $z = $a; $k [lt] $z; $k++)
#######################################
2) Subtracts one variable from another (about 10 minutes)
$a = 5; // Variable 1
$b = 2; // Variable 2
loop ($b) {
$b = 0;
loop ($a) {
$a = $b++;
}
}
echo $a;
And for testing, the loops were:
for ($j = 0, $x = $b; $j [lt] $x; $j++)
for ($k = 0, $z = $a; $k [lt] $z; $k++)
#######################################
3) divides one variable by another (about an hour).
Took a while to find an alternative to a while($a > 0), and I’ve spent another hour trying to reduce it down to 4 variables (no luck so far)… but this is what I’ve got at the moment:
$a = 8; // Variable 1
$b = 2; // Variable 2
$c = 0; // Variable 3
$d = 0; // Variable 4
$e = 0; // Variable 5
loop ($a) {
$c++;
loop ($a) {
$e = $a;
loop ($b) {
$d = 0;
loop ($e) {
$e = $d++;
}
}
$d = $c;
}
$a = $e;
}
echo $d;
And for testing, the loops were:
for ($h = 0, $w = $a; $h [lt] $w; $h++) {
for ($i = 0, $x = $a; $i [lt] $x; $i++) {
for ($j = 0, $y = $b; $j [lt] $y; $j++) {
for ($k = 0, $z = $e; $k [lt] $z; $k++) {
#######################################
#4 by AntonioCS on January 12, 2009 - 10:14 pm
Quote
Wow! Nobody cared about your little mind teaser…. sad..
#5 by ronen cohen on January 13, 2009 - 2:01 am
Quote
craig: My idea was similar to yours for 1 & 2 but for 3 I did:
a = 10
b = 2
c = 0
loop (a)
{
loop(a)
{
a = subtract(a, b)
c++;
}
}
// outputs 5
print c
#6 by Kurt Zoglmann on January 13, 2009 - 2:35 am
Quote
This was quite the bugger of a problem. I was able to complete the entire thing by myself in 3 hours. I allowed the subtract macro to overwrite the first argument, so it was like saying x = x-y or x -= y. I also assumed that it was okay to say that 5 -10 = 0 since there are no negative numbers. I am tempted to post the answer here just for proof. This was ridiculously hard. I hope you don’t do these kind of problems every week or you probably don’t get much done.
#7 by ronen cohen on January 13, 2009 - 2:47 am
Quote
Sorry, that was wrong:
a = 10
b = 2
c = 0
loop (a)
{
k = b
loop (a)
{
m = 1
loop (k)
{
loop (m)
{
c++
m = 0
}
a = subtract(a, 1)
k = 0
}
}
}
// outputs 5
print c
#8 by Kurt Zoglmann on January 13, 2009 - 2:54 am
Quote
hmm.. i guess i’ll post my answer. i didn’t realize there were some posts already.
this is pseudo code.
//decided to make it more challenging by not allowing post increment
// when v1 is 0 returns 0
macro dec (v1, temp) {
temp = 0
loop(v1) {
v1 = 0
loop(temp) {
inc(v1)
}
inc(temp)
}
}
//equivalent to x = x – y or x-= y
//when y > x in x – y, then x = 0
macro subtract-equal(v1, v2, temp) {
loop(v2) {
dec(v1,temp)
}
}
//equivalent to x = x / y or x /= y
//throws away remainder
//infinite loop when given 0 for v2 and v1 >= 1
//when 0 / 0 it equals 0 instead of error or infinite loop
macro divide-equal(v1, v2, temp, div-temp) {
div-temp = 0
loop(v1) {
subtract-equal(v1,v2,temp)
loop(v1) {
inc(div-temp)
}
dec(v1,temp)
loop(v1) {
dec(div-temp)
}
inc(v1)
}
v1 = div-temp
}
hopefully i didn’t make a mistake. i didn’t test this except by hand.
#9 by Brian Clapper on January 13, 2009 - 7:02 am
Quote
Highly fun. Had everyone in the office going. Thanks!
#10 by Craig Francis on January 13, 2009 - 4:58 pm
Quote
For anyone who is interested in a description with my solution to problem 3, the first loop is just to get it to loop as many times as possible (i.e. I would like to say, keep dividing until $a is zero, but this is good enough)… the second loop is like an if statement, although it will run many times, it will keep doing the same thing, unless of course a is zero (not run at all)… the fourth (note, not third) loop does the minus one, while the third repeats that minus one $b times.
@ronen cohen:
Aww, that’s cheating… not only does it use 5 variables (a, b, c, k and m), it also goes out to a function (no if statements or anything like that) which presumably uses more variables… and you have an “m = 1″, and a “subtract(a, 1)”… where you can only set a variable to 0.
And later on, I don’t understand why you have a c++, when it doesn’t seem to be used… did you copy the right version over?
So, the question remains, can it be done in less than or equal to 4 variables?
@kurt zoglmann:
I’ve already got stuck on your “dec” function (copy below)… as temp = 0, how would the loop(temp) run to increment v1?
I am presuming that the inc() function just increments the value by 1 (e.g. v1++).
macro dec (v1, temp) {
temp = 0
loop(v1) {
v1 = 0
loop(temp) {
inc(v1)
}
inc(temp)
}
}
#11 by Ben on January 13, 2009 - 9:37 pm
Quote
my attempt can be found here: http://regenmytoolkit.blogspot.com/2009/01/computational-mind-teaser.html
I like the DIV with only two loops but I feel like the use of c to reduce the looped increment to a single increment is a hack.
#12 by Kurt Zoglmann on January 16, 2009 - 2:07 am
Quote
@Craig
Remember that “loop”, as defined in the problem statement, allows one to redefine its value without changing the number of iterations. Thus in something like “loop(v1) { v1 = 0}”, it would still loop 5 times if v1 was set to 5 before hitting the loop. My macro of dec works because v1 is always one behind the value of temp.
#13 by Craig Francis on January 17, 2009 - 3:16 pm
Quote
@Ben
Your right about it sounding like a hack, but that does seem to be the only way to get this effect.
I like your examples, but they do use more than the 4 variable target (e.g. in the division, there are 4 variables in that function, but more are used by calling the other functions).
Which is why I removed the use of functions (something that isn’t in the list of allowed constructs), and tried to reduce the number of variables even further (getting it down to 5).
Oh, and as to having only “two” loops in the division… if you look at the code flow, there is actually 5 (2 in main body, 2 from the SUB’s, and 1 from the DEC)… mine on the other hand only uses 4 loops.
#14 by Craig Francis on January 17, 2009 - 3:16 pm
Quote
@Kurt
Yes, if you look at the for loops that I provided, they do just that.
Hence why in my examples I re-use variables within the loop, that have just been used to start the loop (e.g. $e).
Going though the loops:
$a) Starts the main loop, but is then used as a countdown to zero, to limit the number of subtractions (done by the second loop).
$b) The divisor, needs to always be available, so the subtraction can be performed on each loop.
$c) Monitors the number of times that the main loop has been run… as this provides the answer to $d, when the second loop cannot be run any more ($a <= 0).
$d) Is first used to perform the subtraction (the temporary variable), but after its done that, it stores the result for when the main loop finishes… I suspect out of all the variables, this is the one to remove.
$e) I used first to calculate ($b – $a) without changing $a (as the loop runs many times – to create the fake “if” condition), and when its completed, $a is updated with the new value from $e.