5
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ I have tried to fix the quoted TeX block. Please check if it still correct. \$\endgroup\$ – Martin R Aug 10 at 18:14
  • \$\begingroup\$ @MartinR Looks perfect,thanks \$\endgroup\$ – dfhwze Aug 10 at 18:15
5
\$\begingroup\$
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...?

\$\endgroup\$
  • 1
    \$\begingroup\$ You are right, I should only check those args once, at the top level. \$\endgroup\$ – dfhwze Aug 10 at 20:44
  • 1
    \$\begingroup\$ Now you mention it, the decrementaton should be allowed as well. I won't update the question. It would invalidate your answer for a part. And perhaps there is a possibility of using only incrementation.. \$\endgroup\$ – dfhwze Aug 11 at 5:45
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This is a valid solution, well split into sub routines, using the hyper operator. I am surprised the difference in performance is that high. :o \$\endgroup\$ – dfhwze Aug 12 at 15:12
  • \$\begingroup\$ This is essentially the same concept as my suggestion. \$\endgroup\$ – Henrik Hansen Aug 13 at 7:26
  • 1
    \$\begingroup\$ I didn't mean to accuse you of stealing anything :-), my point is just, that the concept of Power calls Mult and Mult calls Add is essentially what I'm doing. Feel free to copy, steal or what ever you like - we are helping each other to improved code here :-) \$\endgroup\$ – Henrik Hansen Aug 13 at 7:56
  • 1
    \$\begingroup\$ BtW: when I run the original code with (7, 6, Exponentation) I get a stackoverflow exception. Are you running it in a thread with an expanded stack size? \$\endgroup\$ – Henrik Hansen Aug 13 at 8:07
  • 2
    \$\begingroup\$ @HenrikHansen: I am using Mono (mono-project.com) on macOS. That might behave differently from C# on Windows. \$\endgroup\$ – Martin R Aug 13 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.