Code Challenge: basic arithmic operations using only incrementation operator 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 &amp; \text{if } n = 0 \\
                           a &amp; \text{if } n = 1 \text{ and } b = 0 \\
                           0 &amp; \text{if } n = 2 \text{ and } b = 0 \\
                           1 &amp; \text{if } n \ge 3 \text{ and } b = 0 \\
   H_{n-1}(a, H_n(a, b - 1)) &amp; \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 &gt;= 0)
        // n = hyper operator (n &gt;= 0)
        // b = right operand  (b &gt;= 0)

        if (a &lt; 0) throw new ArgumentOutOfRangeException(nameof(a));
        if (b &lt; 0) throw new ArgumentOutOfRangeException(nameof(b));
        if (n &lt; 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.
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 &lt; 0) throw new ArgumentOutOfRangeException(nameof(left));
  if (right &lt; 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 &lt; 0) throw new ArgumentOutOfRangeException(nameof(left));
      if (right &lt; 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 &gt; 0)
    {
      a++;
      b--;
    }

    return a;
  }
  else
  {
    int res = n - 1;
    res--;
    while (b &gt; 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...?