# What's the maximum possible score in this mathy solitaire puzzle?

Consider a deck of 52 cards in four mathy suits --two red: "adds" ($+$) and "subs" ($-$); and two black: "muls" ($\times$) and "divs" ($\div$)-- and thirteen numerical values --"A" (1), 2, 3, 4, 5, 6, 7, 8, 9, 10, "J" (11), "Q" (12), "K" (13).

A solitaire game on this deck arranges the cards into four stacks of thirteen cards each, according to two familiar rules:

• Cards in a stack must alternate color
• (Reading from the bottom of the stack) The cards must decrease in numerical value, although "K" is allowed to be placed on top of "A". Values within a stack must be consecutive.

For example, this is (part of) a valid stack of cards:

$$[bottom] \;\; [5-] \;\; [4\times] \;\; [3+] \;\; [2\div] \;\; [A+] \;\; [K\times] \;\; [Q-] \;\; [J\times] \;\; [10+] \;\; [9\div] \;\; \cdots \;\; [top]$$

Run-of-the-mill stuff, no? Well, consider that we assign a score to every stack of cards:

• With an initial value of zero, (and again reading from the bottom) we apply the arithmetic operation represented by each card in turn. (That is, you can think of each card as Reverse Polish Notation instructions.)
• Division rounds toward zero (so that every computation step yields an integer)

Edit. I changed the example to make more explicit use of rounding in the middle of a stack store computation, and to remove possibly-deceptive patterns in the suits.

The example partial stack would have a score of $-124$:

$$(0) [5-] \rightarrow -5$$ $$(-5) [4\times] \rightarrow -20$$ $$(-20)[3+] \rightarrow -17$$ $$(-17)[2\div]\rightarrow -8.5 \rightarrow -8$$ $$(-8)[A+] \rightarrow -7$$ $$(-7) [K\times] \rightarrow -91$$ $$(-91) [Q-] \rightarrow -103$$ $$(-103) [J\times] \rightarrow -1133$$ $$(-1133) [10+] \rightarrow -1123$$ $$(-1123) [9\div] \rightarrow -124.777\dots \rightarrow -124$$

Finally, we compute the game score:

• The game score is the absolute value of the sum of the stack scores (NOT the sum of the absolute values).

Question: What's the largest possible game score?

A fairly naive computer search gave me a value of $915,382$. I'll accept an answer that proves this (or whatever better number) is optimal. (Proof can come in the form of a comprehensive computer search algorithm, though I'd prefer something "logical".)

UPDATE. I conducted a new and (I believe) comprehensive computer search, and have confirmed the $915,382$ maximum. (Perhaps-unsurprisingly, maximal arrangements --for the most part-- put "$+$" and "$\times$" cards into two stacks, and "$-$" and "$\div$" into the remaining stacks. There can be some fiddling with black bottom cards, since they all provide the same result when their "operation" is performed on zero.) @FelixCQ's observation that stack-starting values come in pairs of opposite color was the key to constructing a manageable search strategy, so I'm inclined to accept his answer. However, I'll leave the question open for a while longer in case anyone wants to put forth an analysis that doesn't involve checking 5.67 billion individual cases.

-
It looks like this problem asks for a full-tableau Canfield layout. –  Joe Z. Feb 27 '13 at 22:17

Let us assume that all 52 card must be used (in the context of Solitaire, one could imagine being stuck at some point, and then count the current score as the total score, but let us only consider cases with all cards being used).

Since cards must be consecutive, and since stacks are 13 cards long, the same value can only appear once per stack. Since there are only four stack, each value must appear exactly once per stack.

We therefore have four stacks (which we may call $+$, $-$, $\times$ and $\div$, based on the color of the Ace in the stack, for example).

As it has been pointed out, the stacks need not start with the same value; however, the first values of each stack are not all that independent:

• Say the $+$ stack starts with value $k$, then it ends with value $(k \mod 13) + 1$ with same color.
• This means that one of both card with value $k$ and opposite color is missing a predecessor, so it must start another stack. And of course the same can be said of the two other stacks.

So stacks' starting values go by two, with opposite colors.

The corrected number of cases to check is now $$13^2 \cdot 2^{25} \approx 5,67\cdot10^{9}.$$

This should still be manageable by a computer program, although it might take some time. :)

-
Unfortunately, the stacks don't have to start with the same value at all - the fact that stacks loop around from A to K means that each stack is essentially an independent cycle; once we've come up with an assignment to all the stacks that 'works' (uses each suit once for each rank), that stack can be cycled into any of 13 positions. I think this gives a value of $13^3=2197$ times your answer, or between $2^{38}$ and $2^{39}$ possibilities - within the realm of computation, but definitely challenging. –  Steven Stadnicki Oct 13 '11 at 16:16
After the edit I'm still not seeing the dependence that you suggest here. Here's the way I'm thinking about it: (a) start with four stacks A-through-K (hearts/diamonds/spades/clubs). (b) arbitrarily swap hearts with diamonds and spades with clubs at each position (this gives the $2^{13}\cdot 2^{13}$ factor). (c) Exchange every 'even' heart (2, 4, 6, ...) with its corresponding spade and every even diamond with its corresponding club. At this point we have four piles that meet the alternating-color conditions and run A-K. (d) rotate each pile independently (giving us a $13^4$ factor). –  Steven Stadnicki Oct 13 '11 at 18:28
Ahhh, wait, I see my error - after the swap, the top and bottom cards will be the same color, so there's no arbitrary rotation available. Sorry! –  Steven Stadnicki Oct 13 '11 at 21:00
In the edit, I don't think I understand your bullet-pointed notions ("cards that go after [...] are the same as the cards that go before"). However, I agree that "stacks['] starting values go by two, with opposite colors". Are the numerics quite correct? 13 positions for "$A+$" in its stack; likewise for "$A-$"; 2 ways to choose which of those stacks has a starting value matching that of the "$A\times$" stack. With aces handled, there remain 24 generic red cards needing suits (in 2^12 ways); likewise for black. So, "only" $13^2 \cdot 2^{25}$ arrangements, right? –  Blue Oct 13 '11 at 22:09
@DayLateDon: Indeed, I agree with your computation of the numerics. I have also edited out poorly expressed arguments. –  FelixCQ Oct 14 '11 at 8:40

I think with rounding towards 0 you can get $93,405,311,997$, rather larger than yours, with $$[2-] \; [1\div] \; [13-] \; [12\div] \; \cdots \;[4-] \; [3\div] \; [2+] \; [1\times] \;[13+] \; [12\times] \; \cdots \; [4+] \; [3\times]$$

I found this pattern by thinking that you want to try to neutralise the effects of the negatives and divisions before getting onto the serious business of building up your result. You also want subtraction before division to make the negative number halfway as small as possible, and addition before multiplication to get the final result as big as possible. Your constraint on the cards being in numerical order means that there are 13 patterns of this kind to check, and this seems to be the largest. I may have missed something including what you mean by stack scores.

-
If the game consisted in a single stack, I would agree with your solution (although it is still not clear to me whether card descending values must be consecutive or not, so you might be able to do better without this constraint). However, the instructions specify that four decks of 13 cards need to be constructed, and that the final value is the sum of the absolute values of each stack. –  FelixCQ Oct 13 '11 at 13:12
As @FelixCQ points out, I'm looking for a four-stack solution. (And the card values must be consecutive (which yours are); I'm amending the question to reflect this requirement.) –  Blue Oct 13 '11 at 15:31
Your strategy of maximizing with $+$ and $\times$ while minimizing with $-$ and $\div$ was part of what fed my own search, with the "adds" and "muls" filling two stacks and the "subs" and "divs" filling the remaining two stacks. This makes a lot of sense to me, but I haven't ruled-out the possibility that a clever tweak could boost the score by even a point. –  Blue Oct 13 '11 at 17:01