Programming Puzzles

8/20/18

Programming puzzles are great ways to exercise your critical reasoning and problem solving skills, practice algorithmic thinking, and learn syntactic and semantic features of a particular programming language. Here are a few to get started with.

Programming Puzzles

1. Swap two numbers without using a third variable

We've seen a solution to this puzzle when we looked at the boolean operator xor. The went as follows:

void swap(int &x, int &y)
{
  x ^= y;
  y ^= x;
  x ^= y;
}

Try solving it without using xor.

Hint:

Think about how to do something similar using some arithmetic operators.

A solution

#include <iostream>
using namespace std;

// The difference method
void swap(int &x, int &y)
{
  if(x != y)
  {
    x = x - y;
    y = y + x;
    x = y - x;
  }
}

int main()
{
  int a = 5;
  int b = 10;
  swap(a, b);
  cout << "a = " << a << endl << "b = " << b << endl;
  return 0;
}

2. Print a semicolon without using a semicolon anywhere in the program

Print a semicolon ; in C++, without using a semicolon ; anywhere in the source code.

Hint 1:

What's the ascii value of the semicolon?

Hint 2:

Consider the C++ preprocessor directives.

Hint 3:

In what context can you find C++ statements that don't require ending in a semicolon?

A solution

#include <cstdio>
#include <iostream>
#define SEMICOLON 59

int main()
{
  while(!printf("%c\n", SEMICOLON)){}
  // if(printf("%c\n", SEMICOLON)){}
  int x = SEMICOLON;
  if(std::cout << static_cast<char>(x) << std::endl)
  {
  }
}

3. Add two numbers without using the addition operator

Given two ints, return the sum without using the + operator.

Hint 1:

Try using a different arithmetic operator.

Hint 2:

Use repeated increment or decrement operators `++` and `--`.

A solution

#include <iostream>
using namespace std;

int sum(int x, int y)
{
  return x - (-y);
}

int main()
{
  int a = 5;
  int b = 10;
  cout << a << " + " << b << " = " << sum(a, b) << endl;
  return 0;
}

4. Find whether a number is even or odd without using a conditional statement

Given an int, print odd if it is odd and even if it is even.

Hint 1:

Use modulus operator `%` to test for evenness and oddness.

Hint 2:

Exploit the way that boolean expressions are short-circuited in C/C++.

Hint 3:

A different strategy might rely on indexing to a string array, using result of our modulo operation.

A solution

#include<iostream>
#include<string>
using namespace std;

void OddEven(int x)
{
  string array[] = {"even", "odd"};
  cout << array[x % 2] << endl;

  /* Alternatively something that exploits short-circuiting in boolean expressions:
   * ((x & 1) && printf("odd") || printf("even");
   * */
}

int main()
{
  int a = 50;
  int b = 55;

  cout << a << " is ";
  OddEven(a);
  cout << b << " is ";
  OddEven(b);

  return 0;
}