Finally On An Arithmetical Pursuit

| 0 Comments

Arithmetical Pursuit

We have thus far figured many of the mathematical properties of the game of arithmetical pursuit[1][2][3]; that there is no target that cannot be hit given a fortuitous deal of the cards, that there are something of the order of \(210,000,000,000,000\) possible results of admissible formulae and that, if randomly chosen, they are approximately governed by a power law distribution, being one in which the probability of observing a value of \(x\) is more or less proportional to \(x^{-\alpha}\) for some \(\alpha\) greater than one.
You will no doubt recall that the goal of the game is to utilise addition, subtraction, multiplication and division to arithmetically manipulate one or more of six randomly chosen integers to land as closely as possible to a randomly chosen target between one and one thousand, admitting no fractions, with those integers being decided by a deal of six cards, the pips equalling their face values, the Jacks twenty five, the Queens fifty and the Kings one hundred, and the target being decided by the roll of three twenty sided dice having the digits zero to nine writ upon them twice apiece with a roll of three zeros representing one thousand.

The last question that my fellow students and I should like answered is that of how likely it might be that we should be able to hit the target.

An Exhaustive Search

To figure whether we can hit some particular target with some particular deal of the cards we may simply run through every possible formula that we might make from them until, if ever, we hit that target.

Recall that we used reverse Polish notation, in which arithmetical operators appear after the numbers upon which they operator rather than between them, to enumerate all possible arrangements of numbers, represented by \(x\) symbols, and operators, represented by \(o\) symbols, that tidily resolve to a single number with student.rpnSubsets by noting that any such arrangement must have one fewer operator than it has numbers and that, when reading from left to right, its count of numbers must always exceed its count of operators, as illustrated by deck 1.

Deck 1: Enumerating RPN Subsets

We then developed schemes to enumerate every manner in which the allowed numbers and operators might be placed in these arrangements based on the observation that we could use the remainders of successive divisions to associate integers with unique arrangements of those numbers and operators.
For the operators, we simply took the remainder of division by four to identify the first operator, then subtracted the result from the integer and repeated the process to find the remaining operators, as shown in deck 2.

Deck 2: Enumerating Operator Arrangements

For the numbers, we noted that the divisions should be by progressively smaller numbers to account for those that had already been selected. With this we were able to generate a sequence of indices identifying a shuffle of the deck in much the same fashion that we contrived to randomly shuffle it with student.shuffle6, swapping each in turn with one of those not already shuffled, as demonstrated by deck 3.

Deck 3: Enumerating Card Permutations

Here, the function p calculates the permutation, being the number of ways in which we can choose \(r\) from \(n\) objects. Note that, unlike student.shuffle6, it is essential that the deck be returned to its original order after each step, which we manage by performing the swaps in reverse order.

Armed with these schemes it is a simple matter to exhaustively search through the ways in which we might substitute the \(x\) symbols with the dealt cards and the \(o\) symbols with operators, as is done by student.rpnSearch in listing 1 using our student.rpnFill function to perform the substitutions and our student.rpnCalc function to evaluate the resulting formulae.

Listing 1: student.rpnSearch
student.rpnSearch = function(target, subset, numbers, symbols) {
 function p(n, r) {
  var i = n-r+1;
  r = 1;
  while(i<=n) r *= i++;
  return r;
 }
 var xn = (subset.length+1)/2;
 var on = xn-1;
 var xp = p(numbers.length, xn);
 var op = Math.pow(symbols.length, on);
 var perm = new Array(xn);
 var ops = new Array(on);
 var xi, x, i, j, c, oi, o, f, n;

 numbers = numbers.slice(0);

 for(xi=0;xi<xp;++xi) {
  x = xi;
  for(i=0;i<xn;++i) {
   j = x%(numbers.length-i);
   x = (x-j)/(numbers.length-i);
   perm[i] = i+j;
  }

  for(i=0;i<xn;++i) {
   c = numbers[perm[i]];
   numbers[perm[i]] = numbers[i];
   numbers[i] = c;
  }

  for(oi=0;oi<op;++oi) {
   o = oi;
   for(i=0;i<on;++i) {
    j = o%symbols.length;
    o = (o-j)/symbols.length;
    ops[i] = symbols[j];
   }

   f = student.rpnFill(subset, numbers, ops);
   n = student.rpnCalc(f);
   if(n===target) return f;
  }

  for(i=xn-1;i>=0;--i) {
   c = numbers[perm[i]];
   numbers[perm[i]] = numbers[i];
   numbers[i] = c;
  }
 }
 return [];
};

Unfortunately, doing so can be a rather time consuming business, as is occasionally shown by deck 4; most especially when it proves impossible to hit the target!

Deck 4: An Exhaustive Search

We shall most certainly not have sufficient time to test every one of the
\[ ^{52}C_6 = \frac{52!}{6! \times (52-6)!} = 20,358,520 \]
possible combinations of cards, being the number of ways in which we can select six from fifty two cards when the order is of no concern, for each of the one thousand possible targets.

A Faster RPN Calculator

We can reduce the number of formulae that we need to test by noting that the order of the arguments for addition and multiplication is irrelevant and consequently we can give up on a particular calculation if ever it happens that their first argument is smaller than their second, confident that we shall presently enumerate a formula in which the arguments are reversed.
Furthermore, for division such an order of the arguments must necessarily yield a fraction and consequently be inadmissible in the game.
Finally, there is no need for negative numbers in the formulae since we can always switch their sign whilst swapping addition for subtraction, and vice versa, further along the formula.
Consequently, we can abort the calculation with a NaN whenever the second argument of an arithmetical operator exceeds the first, as is done in student.rpnCalc2 in listing 2.

Listing 2: student.rpnCalc2
student.rpnCalc2 = function(f) {
 var stack = [];
 var n = f.length;
 var i, arg, x1, x2;

 for(i=0;i<n;++i) {
  arg = f[i];
  if(ak.nativeType(arg)===ak.STRING_T) {
   x2 = stack.pop();
   x1 = stack.pop();
   if(x1<x2) return ak.NaN;

   switch(arg) {
    case '+': stack.push(x1+x2);
              break;
    case '-': stack.push(x1-x2);
              break;
    case '*': stack.push(x1*x2);
              break;
    case '/': if(x1%x2!==0) return ak.NaN;
              stack.push(x1/x2);
              break;
    default:  return ak.NaN;
   }
  }
  else stack.push(arg);
 }
 return stack.length===1 ? stack[0] : ak.NaN;
};

Deck 5 demonstrates student.rpnSearch2 which is identical to student.rpnSearch in every way, but for its evaluating formulae with student.rpnCalc2 rather than with student.rpnCalc.

Deck 5: A Faster Exhaustive Search

Whilst this is most assuredly faster, it is still not remotely fast enough that we might use this scheme to test the outcome of every possible game. We might, however, employ it in a slightly different manner.

An Alternative Scheme

Rather than test whether we might be successful in hitting a particular target with a particular deal of the cards, we can instead search for every target than can be hit with them. Noting that each target has an equal chance of one in one thousand of being set, we might use this to calculate the likelihood that any given deal of the cards might yield a hit. To do this we need only keep track of those targets that have already been hit, as illustrated by student.rpnHits in listing 3.

Listing 3: student.rpnHitProbability
student.rpnHits = function(hits, subset, numbers, symbols) {
 function p(n, r) {
  var i = n-r+1;
  r = 1;
  while(i<=n) r *= i++;
  return r;
 }
 var xn = (subset.length+1)/2;
 var on = xn-1;
 var xp = p(numbers.length, xn);
 var op = Math.pow(symbols.length, on);
 var perm = new Array(xn);
 var ops = new Array(on);
 var xi, x, i, j, c, oi, o, f, n;

 for(xi=0;xi<xp;++xi) {
  x = xi;
  for(i=0;i<xn;++i) {
   j = x%(numbers.length-i);
   x = (x-j)/(numbers.length-i);
   perm[i] = i+j;
  }

  for(i=0;i<xn;++i) {
   c = numbers[perm[i]];
   numbers[perm[i]] = numbers[i];
   numbers[i] = c;
  }

  for(oi=0;oi<op;++oi) {
   o = oi;
   for(i=0;i<on;++i) {
    j = o%symbols.length;
    o = (o-j)/symbols.length;
    ops[i] = symbols[j];
   }

   f = student.rpnFill(subset, numbers, ops);
   n = student.rpnCalc2(f);
   if(n>0 && n<=hits.length) hits[n-1] = true;
  }

  for(i=xn-1;i>=0;--i) {
   c = numbers[perm[i]];
   numbers[perm[i]] = numbers[i];
   numbers[i] = c;
  }
 }
};

Here we are using the hits array to record which of the targets have already been hit so that we do not erroneously double count successful outcomes of the game. In this fashion, deck 6 runs through all of the formulae subsets for a random deal of the cards, updating the probability of a hit after every formula therein has been tested.

Deck 6: The Probability That A Deal Is A Hit

Whilst this is still far too time consuming to allow for testing every possible deal of the cards, running the deck some several times shows that it is usually the case that most every target can be hit, which I must say came as something of a surprise to my fellow students and I, given just how frequently it happens that we fail to hit the target!
Yet more surprising was our discovery that there are particularly fortuitous deals of the cards with which any target may be hit. For example, one such deal is
\[ 3, 6, 9, 10, 50, 100 \]
which you may confirm with deck 6 by setting deck to [3, 6, 9, 10, 50, 100] rather than a random shuffle.

And with that we have reached the conclusion of our arithmetical pursuit!
\(\Box\)

References

[1] On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

[2] Further On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

[3] Further Still On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

Based upon an article I wrote for ACCU's Overload magazine.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+