Programming puzzles/brainteasers

Smasher

As the title says this thread is for posting whatever programming puzzles or brainteasers you know that you think other people might enjoy. I'm posting one puzzle but feel free to add your own as well as respond to whatever puzzles you like. If you're posting an answer please put it in a labeled spoiler (the label referring to which problem you're answering), both to save space and so people don't accidently see an answer if they don't want to. Since my problem is really a collection of related problems you might want to use a double spoiler there, but I'll leave that to your discretion.


My puzzle:
Suppose you must implement a set of boolean and comparison functions that use integers to store the boolean values. 0 is considered false, 1 is considered true, and any other value is invalid. Let an integer used in this manner be called a boolInt. Assuming the functions are passed valid boolInts, they must return a boolInt that represents the value you would expect from that function given its name. Normally this would be easy, but there is one major impediment: you are unable to "see" the value of any variable. In other words, you cannot use any sort of branch, conditional, or comparison operation. That means no if(), while(), for(), etc. loops or branches, no exceptions, and no doing something like "int a = (arg1 == arg2);" because of the equality comparison. The idea is that for a given function, the same sequence of instructions will be executed every time the function is called no matter what the arguments are. The list of allowed operations is variable creation and assignment, addition and subtraction, multiplication and division, sqrt (square root), and returning a boolInt. You can mix the allowed operations in any way that makes sense.

Other notes:
- You must return a boolInt (ie integer with value 0 and 1), but other variables within each function have no restriction on their value.
- Since boolInts and integers are indeed the same type, you can mix them at will. I make a distinction between the "two" types merely for clarity.
- You may assume Integer underflow and overflow are not a concern. However, you must prevent division by zero (which would cause an exception and thus an alternate flow of execution), and integer truncation behaves as it does in c.
- You can use parenthesis too. You don't technically need them, but they might make answers easier to read.


Boolean functions: Take two boolInts as arguments (except for NOT which takes one) and return a boolInt
AND
OR
NOT
XOR

Comparison functions: Take two integers as arguments (positive, negative, whatever) and return a boolInt
EQ // equal to
NEQ // not equal to
GT // greater than
GTE // greater than or equal to
LT // you get the idea
LTE

A solution for AND (read this if you're stuck or unsure what I'm going for):

int AND(int arg1, int arg2){
return arg1 * arg2;
}

AND is only true if both its arguments are true. If either is false it will be 0 and thus the whole result will be 0. If they're both true 1*1 == 1 and so the function returns true.

NOT:

int NOT(int arg1){
int a = -arg1; // implicit multiplication by -1 is fine
return a + 1;
}

XOR:

int XOR(int arg1, int arg2){
int a = arg1 - arg2;
return a * a;
}

OR:

int OR(int arg1, int arg2){
int a = arg1 + arg2; // 0, 1, or 2 for false/false, (true/false or false/true), true/true respectively
int b = a - 1; // -1, 0, or 1
b = b * arg1;
return a - b;
}
I like that solution a lot, but this one's shorter:
int OR2(int arg1, int arg2){
return (int)sqrt(arg1 + arg2); // sqrt(2) gets truncated to int -> 1
}

You're on your own for the comparison ones.

ecco the dolphin

About to go home, so lacking time to type out full answers, but I believe that I have the basis for solving the comparisons:

boolInt lessThanZero(int a)
{
  // Rely on division rounding - if the denominator is bigger than the numerator, we get zero.
  // If the denominator is smaller than a non-zero numerator, but larger than
  // half the absolute value of the numerator, then we get one.
  // This means if we use a/(a+k), then k should be less than 0.5.
  // However, we are using integral mathematics, so we multiply everything so that k is an integer.
  // The multiplier can't be 2, as then that would mean that k has an effective value of 0.5.  So we use 3.
  return (3 * a) / (3 * a + 1);
}

boolInt greaterThanZero(int a)
{
  return lessThanZero(-a);
}

Will edit this with full answers when I get time at home.

Edit:
EQ:

boolInt EQ(int a, int b)
{
  return AND( NOT(lessThanZero(a - b)), NOT(lessThanZero(b - a)) );
}

NEQ:

boolInt NEQ(int a, int b)
{
  return OR( lessThanZero(a - b), lessThanZero(b - a) );
  // Alternatively: return NOT(EQ(a, b));
}

GT:

boolInt GT(int a, int b)
{
  return lessThanZero(b - a);
}

LT:

boolInt LT(int a, int b)
{
  return lessThanZero(a - b);
}

GTE:

boolInt GTE(int a, int b)
{
  return NOT(LT(a, b));
}

LTE:

boolInt LTE(int a, int b)
{
  return NOT(GT(a, b));
}

Smasher

Nice; that's a better answer than what I had.

Two others puzzles, not mine this time:

In linear time and constant space, determine if a singly-linked list has any loops in it.

Write a c++ program that contains no semicolons and displays "Hello world".

zilo

Smasher wrote: »

Nice; that's a better answer than what I had.

Two others puzzles, not mine this time:

In linear time and constant space, determine if a singly-linked list has any loops in it.

Write a c++ program that contains no semicolons and displays "Hello world".

The first one is a popular interview question. It has a clever solution that doesn't use any c++ arcana, which I like.

For the second:

void main()
{
  while ( printf( "Hello world" ) )
  {
  }
}

Haven't tried to compile it but it should work, although tbh "void main()" is bad juju and it should return an int, but that would require a semicolon.

edit for code tags