Code Challenge: basic arithmic operations using only incrementation operator

Question

Challenge

Write a function that takes 2 integer operands left and right (both >= 0) and evaluates one of the following basic arithmic operations:

• addition
• multiplication
• exponentation

The challenge is you are prohibited from using any built-in operator, except for an incrementation (++ or +1). The entropy is all results that are in bounds of the maximum value of an integer.

Provided Classes

public enum Operation
{
    Addition,
    Multiplication,
    Exponentation
}

public static class Expression
{
    public static int Evaluate(int left, int right, Operation operation)
    {
        throw new NotImplementedException(); // .. this should be implemented
    }
}

Unit Tests

[TestClass]
public class Fixtures
{
    [TestMethod]
    public void Fixture()
    {
        Assert.AreEqual(5, Expression.Evaluate(2, 3, Operation.Addition));
        Assert.AreEqual(6, Expression.Evaluate(2, 3, Operation.Multiplication));
        Assert.AreEqual(8, Expression.Evaluate(2, 3, Operation.Exponentation));
    }
}

My Solution

I have decided to use the hyperoperation (Wikipedia Link). The only arithmic operator used is in the first branch (if (n == 0) -> b + 1).

$$ H_n(a,b) = a[n]b = \begin{cases} b + 1 & \text{if } n = 0 \\ a & \text{if } n = 1 \text{ and } b = 0 \\ 0 & \text{if } n = 2 \text{ and } b = 0 \\ 1 & \text{if } n \ge 3 \text{ and } b = 0 \\ H_{n-1}(a, H_n(a, b - 1)) & \text{otherwise} \end{cases}$$

And my implementation of Evaluate:

public static class Expression
{
    public static int Evaluate(int left, int right, Operation operation)
    {
        return Hyper(left, (int)operation + 1, right);
    }

    static int Hyper(int a, int n, int b)
    {
        // https://en.wikipedia.org/wiki/Hyperoperation
        // a = left operand   (a >= 0)
        // n = hyper operator (n >= 0)
        // b = right operand  (b >= 0)

        if (a < 0) throw new ArgumentOutOfRangeException(nameof(a));
        if (b < 0) throw new ArgumentOutOfRangeException(nameof(b));
        if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
        if (n == 0) return b + 1;
        if (b == 0) return n == 1 ? a : n == 2 ? 0 : 1;

        return Hyper(a, n - 1, Hyper(a, n, b - 1));
    }
}

Questions

• Are there any overlooked flaws in my solution?
• Could this be optimized for performance?
• Are there perhaps better alternatives, and why would they be better?
• Any general review of my code, style, conventions are invited.

Answer 1

public enum Operation
{
    Addition,
    Multiplication,
    Exponentation
}

If you gave these explicit values:

  public enum Operation
  {
    Addition = 1,
    Multiplication = 2,
    Exponentation = 3
  }

... you could avoid the + 1 for the operation:

  return Hyper(left, (int)operation, right);

---

Because Hyper(...) is private, and you are supposed to know how to use it, there is no need for checking the input values in there. It is safe to leave it to Evaluate(...) to do that:

public static int Evaluate(int left, int right, Operation operation)
{
  if (left < 0) throw new ArgumentOutOfRangeException(nameof(left));
  if (right < 0) throw new ArgumentOutOfRangeException(nameof(right));
  if (!Enum.IsDefined(typeof(Operation), operation)) throw new ArgumentOutOfRangeException(nameof(operation));

  return Hyper(left, (int)operation, right);
}

it is safe because:

  if (n == 0) return b + 1;
  if (b == 0) return n == 1 ? a : n == 2 ? 0 : 1;

will catch zeros for n and b while a never changes so no arguments will never be lesser than zero - as you can only decrement by one.

---

Personally I would change the order of b and n to be the same as for Evaluate(...):

static int Hyper(int a, int b, int n) {...}

---

All in all in my writing it would look like:

  public enum Operation
  {
    Addition = 1,
    Multiplication = 2,
    Exponentation = 3
  }

  public static class Expression
  {
    public static int Evaluate(int left, int right, Operation operation)
    {
      if (left < 0) throw new ArgumentOutOfRangeException(nameof(left));
      if (right < 0) throw new ArgumentOutOfRangeException(nameof(right));
      if (!Enum.IsDefined(typeof(Operation), operation)) throw new ArgumentOutOfRangeException(nameof(operation));

      return Hyper(left, right, (int)operation);
    }

    static int Hyper(int a, int b, int n)
    {
      if (n == 0) return b + 1;
      if (b == 0) return n == 1 ? a : n == 2 ? 0 : 1;

      return Hyper(a, Hyper(a, b - 1, n), n - 1);
    }
  }

---

More edge/test cases?

---

BtW Hyper() stack overflows relatively quickly: for instance for a == 8 and b == 5 for Exponentation.

An alternative algorithm could be the below "semi-recurs-iterative":

It has a recursive depth of max 3:

public static int HyperIter(int a, int b, int n)
{
  if (n == 1)
  {
    while (b > 0)
    {
      a++;
      b--;
    }

    return a;
  }
  else
  {
    int res = n - 1;
    res--;
    while (b > 0)
    {
      res = HyperIter(res, a, n - 1);
      b--;
    }

    return res;
  }
}

I'm though not sure if it completely satisfies the criteria of only using + 1, because it uses a local variable (res) and -- - but the original also uses - 1 in the recursive calls, so...?

Answer 2

That is an elegant implementation using the hyperoperation. The disadvantage is that a branch on the “level” is needed in each recursive step.

I would implement the addition, multiplication and exponentiation as separate functions. That makes the level parameter obsolete. It is more code but (in my opinion) much clearer:

public static int Evaluate(int left, int right, Operation operation)
{
    if (left < 0) throw new ArgumentOutOfRangeException(nameof(left));
    if (right < 0) throw new ArgumentOutOfRangeException(nameof(right));

    switch (operation)
    {
        case Operation.Addition:
            return Add(left, right);
        case Operation.Multiplication:
            return Mult(left, right);
        case Operation.Exponentation:
            return Power(left, right);
        default:
            throw new ArgumentOutOfRangeException(nameof(operation));
    }
}

static int Add(int a, int b) {
    // a + 0 = a
    if (b == 0) { return a; }

    // a + b = (a + 1) + (b - 1)
    return Add(a + 1, b - 1);
}

static int Mult(int a, int b) {
    // a * 0 = 0
    if (b == 0) { return 0; }

    // a * b = a * (b - 1) + a
    return Add(Mult(a, b - 1), a);
}

static int Power(int a, int b) {
    // a^0 = 1
    if (b == 0) { return 1; }

    // a^b = a^(b-1) * a
    return Mult(Power(a, b - 1), a);
}

It is also considerably faster than the original implementation. My results (tested with Mono on a 1.2 GHz Intel Core m5 MacBook) for computing

Expression.Evaluate(7, 6, Operation.Exponentation)

• Original code: 9.5 seconds
• Above code: 0.05 seconds