Arithmetical Pursuit
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 = nr+1; r = 1; while(i<=n) r *= i++; return r; } var xn = (subset.length+1)/2; var on = xn1; 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.lengthi); x = (xj)/(numbers.lengthi); 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 = (oj)/symbols.length; ops[i] = symbols[j]; } f = student.rpnFill(subset, numbers, ops); n = student.rpnCalc(f); if(n===target) return f; } for(i=xn1;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 (526)!} = 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(x1x2); 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 bystudent.rpnHits
in listing 3.Listing 3: student.rpnHitProbability
student.rpnHits = function(hits, subset, numbers, symbols) { function p(n, r) { var i = nr+1; r = 1; while(i<=n) r *= i++; return r; } var xn = (subset.length+1)/2; var on = xn1; 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.lengthi); x = (xj)/(numbers.lengthi); 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 = (oj)/symbols.length; ops[i] = symbols[j]; } f = student.rpnFill(subset, numbers, ops); n = student.rpnCalc2(f); if(n>0 && n<=hits.length) hits[n1] = true; } for(i=xn1;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]
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