Author Archives: stern

Sled Dogs in Vermont

I brought the snow skates up to Vermont last week, and nobody recognized them at all. Typically some old-timers will remember them from the 1990s, but I guess Sled Dogs never penetrated the Vermont market even when they were still being sold. Virtually everybody assumed I was descending the mountain in ski boots, and they remained impressed even after I explained that the reality was somewhat less insane than that.

We got about 18 inches of snow one night, giving me the opportunity to re-learn just how worthless these things are in deep powder.

SledDogs as I spin down the mountain at Bromley, Vermont

SledDogs as I spin down the mountain at Bromley, Vermont

In related news, the company that currently owns the rights to the sled dog name and design has given up on their plan to re-enter the U.S. market this season.

“Sled Dogs snowskates will sadly not be available this season. We thought it would, but due to quality issues with our production, we have to postpone the re-launch to next season. We are not happy about this and understand that our customers are the same. However we can not sell products that do not have the quality that is up to our standards. We will re-launch the webpage when we have products of right quality in stock in our warehouse. We do not know now when this will be but most likely it will be for next season.”

A perfect solution to 24s

In several recent posts, I have discussed a method for perfect solution to the game of 24s. Here, I summarize some of those results and link to the Mathematica notebook I used to find them, and a comprehensive list of solutions for those who would like to skip the math and get right to the answer.

To recap, there are 715 possible hands in a game of 24s. 566 of those hands can be solved with arithmetics alone, 595 if we add roots, powers, and logs, and 619 if we add Mod.

I generally play with Log and Power and Root allowed, but not Mod. I find that the hands that are solvable only with Log, Power, and Root, generally are solvable by humans. See for example

{1,1,8,9} -> 8 Root[9,1+1]
{1,2,9,9} -> (9-1) Root[9,2]
{2, 2, 2, 6} -> 2^(2+Log[2,6]) or (2*Root[6,2])^2
{2,2,9,9} -> 2(Root[9,2]+9)
{3,7,8,10} -> 7 Root[8,3] +10
{3,4,9,10} -> 4+Log[3,9]*10
{7, 8, 9, 9} -> 8 Root[9,9-7], and
{8, 8, 9, 10} -> 8 Root[9,10-8].

A bright high school student should be able to find any of those. However, Mod introduces solutions that would probably never be played by an unaided human being. For example,

{5, 6, 7, 10} -> 6*Mod[7^10,5], and

{5,7,7,8} -> 8*Mod[7^7,5].

There is no other solution in these two cases.

Anyway, I’ve provided a comprehensive list of solutions linked as RTF and PDF documents, and the Mathematica notebook that I used to solve the problem in the first place.

All 24s in PDF.

Again, but as an RTF file.

And, most importantly, the Mathematica notebook.

Let me know if you do anything interesting with this.

Solving 24s, part iii: mod

I have shown how to comprehensively solve a game of 24s that allows just arithmetic, and how to expand that to allow powers, roots, and logarithms. Now we’re going to add the modulo (Mod) function.

If you’ve followed the methodology in parts i and ii, this is pretty simple stuff.

First, to our set of simplified function definitions, I add
mod[x_Integer?(# > 0 &), y_Integer?(-16 <= # <= 16 && # != 0 &)] := Mod[x, y]; mod[x__] := Indeterminate;

Then, our rule definition step looks like
rules = generateRules[{Times, Plus, Subtract, divide, power, root, log, mod}, 4];

We're up to 512 rules here, once redundant patterns are eliminated. The complexity increases exponentially with the number of operators allowed.

The good news is that Mod makes lots of hands solvable that wouldn't be otherwise. See, for example,

{3, 5, 5, 10} -> 5*5-Mod[10,3]
{5, 6, 7, 10} -> 6*Mod[7^10,5]
{5, 7, 7, 8} -> Mod[7^7,5]*8, and
{6, 7, 7, 9} -> 6*Mod[7*7,9]

In fact, allowing Mod as an operator increases the total number of solvable hands all the way to 619 out of 715.

The unsolvable hands that remain are
{{1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 1, 3}, {1, 1, 1, 4}, {1, 1, 1, 6}, {1, 1, 1, 7}, {1, 1, 1, 9}, {1, 1, 1, 10}, {1, 1, 2, 2}, {1, 1, 2, 3}, {1, 1, 5, 9}, {1, 1, 5, 10}, {1, 1, 6, 7}, {1, 1, 6, 10}, {1, 1, 7, 7}, {1, 1, 7, 8}, {1, 1, 7, 9}, {1, 1, 8, 10}, {1, 1, 9, 9}, {1, 1, 9, 10}, {1, 1, 10, 10}, {1, 2, 2, 2}, {1, 2, 9, 10}, {1, 2, 10, 10}, {1, 4, 9, 9}, {1, 5, 7, 7}, {1, 6, 6, 7}, {1, 6, 7, 7}, {1, 6, 7, 8}, {1, 6, 10, 10}, {1, 7, 7, 7}, {1, 7, 7, 8}, {1, 7, 10, 10}, {1, 8, 9, 9}, {1, 8, 9, 10}, {1, 8, 10, 10}, {1, 9, 9, 9}, {1, 9, 9, 10}, {1, 9, 10, 10}, {1, 10, 10, 10}, {2, 2, 2, 2}, {2, 2, 7, 9}, {2, 6, 7, 7}, {2, 7, 7, 7}, {2, 7, 7, 9}, {2, 7, 9, 9}, {2, 9, 9, 9}, {2, 9, 9, 10}, {2, 10, 10, 10}, {3, 3, 10, 10}, {3, 5, 7, 7}, {3, 10, 10, 10}, {4, 4, 9, 9}, {4, 7, 7, 9}, {4, 7, 7, 10}, {4, 9, 9, 9}, {5, 5, 5, 7}, {5, 5, 5, 8}, {5, 5, 5, 10}, {5, 5, 6, 10}, {5, 5, 7, 9}, {5, 7, 7, 7}, {5, 7, 9, 9}, {5, 8, 10, 10}, {5, 9, 9, 9}, {5, 10, 10, 10}, {6, 6, 6, 7}, {6, 6, 7, 7}, {6, 6, 7, 8}, {6, 7, 7, 7}, {6, 7, 7, 8}, {6, 9, 10, 10}, {7, 7, 7, 7}, {7, 7, 7, 8}, {7, 7, 7, 9}, {7, 7, 7, 10}, {7, 7, 8, 8}, {7, 7, 8, 9}, {7, 7, 9, 9}, {7, 8, 8, 8}, {7, 9, 9, 9}, {7, 9, 9, 10}, {7, 9, 10, 10}, {7, 10, 10, 10}, {8, 8, 8, 8}, {8, 8, 9, 9}, {8, 8, 10, 10}, {8, 9, 9, 9}, {8, 9, 9, 10}, {8, 9, 10, 10}, {8, 10, 10, 10}, {9, 9, 9, 9}, {9, 9, 9, 10}, {9, 9, 10, 10}, {9, 10, 10, 10}, {10, 10, 10, 10}}

Solving 24s, part ii: powers, roots, and logarithms

In my last post on this topic, I showed that 566 of 715 possible hands in the game of 24s could be solved with simple arithmetic. However in practice people don’t play with just those operators. In my experience, a normal game always includes powers, roots, and logarithms. The solution method used for arithmetics works just fine when expanded for these additional functions, though I chose to make some small modifications for the sake of efficiency.

First, I redefine the functions to remove some cases that are quite unlikely to produce 24s, and which would increase memory needs and processing time significantly if left in place. See the following, for example:


Off[General::"spell1"]; Off[General::"spell"];
power[x_?(# > 0 &), y_?(-16 <= # <= 16 &)] := x^y; power[x__] := Indeterminate; root[x_Integer?(# > 0 &), y_Integer?(-16 <= # <= 16 && # != 0 &)] := Power[x, (y)^-1]; root[x__] := Indeterminate; divide[x_, y_] /; y != 0 := Divide[x, y]; divide[x_, 0] := Indeterminate; log[x_?(# > 0 &), y_?(# > 0 &)] := Log[x, y];
log[x__] := Indeterminate;

We can then generate rules as in the arithmetic case but with

rules = generateRules[{Times, Plus, Subtract, divide, power, root, log}, 4];

and run legitCombos as before. The result? 595 hands are solvable, as opposed to the 566 we had before. hands that can be solved now, that couldn’t be solved before, include

{1,1,8,9} -> 8 Root[9,1+1] and trivial variations
{1,2,9,9} -> (9-1) Root[9,2] and trivial variations
{2, 2, 2, 6} -> 2^(2+Log[2,6]) or (2*Root[6,2])^2 and trivial variations
{2,2,9,9} -> 2(Root[9,2]+9) and trivial variations
{3,7,8,10} -> 7 Root[8,3] +10 and trivial variations
{3,4,9,10} -> 4+Log[3,9]*10 and trivial variations
{7, 8, 9, 9} -> 8 Root[9,9-7] and trivial variations, and
{8, 8, 9, 10} -> 8 Root[9,10-8] and trivial variations.

The hands that remain unsolvable are

{{1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 1, 3}, {1, 1, 1, 4}, {1, 1, 1, 6}, {1, 1, 1, 7}, {1, 1, 1, 9}, {1, 1, 1, 10}, {1, 1, 2, 2}, {1, 1, 2, 3}, {1, 1, 5, 9}, {1, 1, 5, 10}, {1, 1, 6, 7}, {1, 1, 6, 10}, {1, 1, 7, 7}, {1, 1, 7, 8}, {1, 1, 7, 9}, {1, 1, 8, 10}, {1, 1, 9, 9}, {1, 1, 9, 10}, {1, 1, 10, 10}, {1, 2, 2, 2}, {1, 2, 9, 10}, {1, 2, 10, 10}, {1, 4, 9, 9}, {1, 5, 7, 7}, {1, 6, 6, 7}, {1, 6, 7, 7}, {1, 6, 7, 8}, {1, 6, 10, 10}, {1, 7, 7, 7}, {1, 7, 7, 8}, {1, 7, 10, 10}, {1, 8, 9, 9}, {1, 8, 9, 10}, {1, 8, 10, 10}, {1, 9, 9, 9}, {1, 9, 9, 10}, {1, 9, 10, 10}, {1, 10, 10, 10}, {2, 2, 2, 2}, {2, 2, 7, 9}, {2, 6, 7, 7}, {2, 7, 7, 7}, {2, 7, 7, 9}, {2, 7, 8, 10}, {2, 7, 9, 9}, {2, 9, 9, 9}, {2, 9, 9, 10}, {2, 10, 10, 10}, {3, 3, 4, 10}, {3, 3, 10, 10}, {3, 4, 6, 7}, {3, 5, 5, 10}, {3, 5, 7, 7}, {3, 5, 8, 10}, {3, 10, 10, 10}, {4, 4, 5, 9}, {4, 4, 6, 6}, {4, 4, 6, 7}, {4, 4, 9, 9}, {4, 4, 9, 10}, {4, 7, 7, 9}, {4, 7, 7, 10}, {4, 9, 9, 9}, {4, 9, 10, 10}, {4, 10, 10, 10}, {5, 5, 5, 7}, {5, 5, 5, 8}, {5, 5, 5, 10}, {5, 5, 6, 9}, {5, 5, 6, 10}, {5, 5, 7, 9}, {5, 6, 7, 10}, {5, 7, 7, 7}, {5, 7, 7, 8}, {5, 7, 9, 9}, {5, 8, 9, 9}, {5, 8, 10, 10}, {5, 9, 9, 9}, {5, 9, 9, 10}, {5, 10, 10, 10}, {6, 6, 6, 7}, {6, 6, 7, 7}, {6, 6, 7, 8}, {6, 6, 10, 10}, {6, 7, 7, 7}, {6, 7, 7, 8}, {6, 7, 7, 9}, {6, 7, 8, 8}, {6, 8, 10, 10}, {6, 9, 9, 9}, {6, 9, 10, 10}, {7, 7, 7, 7}, {7, 7, 7, 8}, {7, 7, 7, 9}, {7, 7, 7, 10}, {7, 7, 8, 8}, {7, 7, 8, 9}, {7, 7, 8, 10}, {7, 7, 9, 9}, {7, 7, 10, 10}, {7, 8, 8, 8}, {7, 9, 9, 9}, {7, 9, 9, 10}, {7, 9, 10, 10}, {7, 10, 10, 10}, {8, 8, 8, 8}, {8, 8, 8, 9}, {8, 8, 9, 9}, {8, 8, 10, 10}, {8, 9, 9, 9}, {8, 9, 9, 10}, {8, 9, 10, 10}, {8, 10, 10, 10}, {9, 9, 9, 9}, {9, 9, 9, 10}, {9, 9, 10, 10}, {9, 10, 10, 10}, {10, 10, 10, 10}}.

Next chapter, we add Mod[].

Solving 24s, part i: Algebraic programming, arithmetic allowed

If the game of 24s is played with binary operators only, there is a finite number of different possible ways to combine the cards. Given a modern computer, it is perfectly solvable. The basic technique that I use is called algebraic programming, and amounts to combining every possible combination of four cards and every one of the permitted operators in every possible way, then selecting the combinations that equal 24.

This can be done in any programming language, but it’s natural in Mathematica, which natively supports the set operations on which this method relies.

First, some observations:

1. We have four cards, each of which can be any number from 1 to 10. We therefore have 10*10*10*10 (10,000) possible hands, if order matters.

2. If order doesn’t matter, such that {1,2,3,4} is the same as {4,3,2,1}, there are only 715 possible combinations

In[]:= Length[Union[Sort /@ Tuples[Range[10], 4]]]
Out[]= 715

Now we develop our combinations. This can be made easier using Andrzej Kozlowski’s “ReplaceAllList” function from The Mathematica Journal 9:2 © 2004.

ReplaceAllList[expr_, rules_] :=
Module[{i},
Join[ReplaceList[expr, rules],
If[AtomQ[expr], {},
Join @@ Table[
ReplacePart[expr, #, i] & /@
ReplaceAllList[expr[[i]], rules], {i, Length[expr]}]]]]

We have a choice — make our function set commutative, so that {3,2} is processed as both 3-2 and 2-3, or make our card set comprehensive, so that both arrangements are passed through the function. I elected the latter, but the former should work equally well.

Start by finding all the ways of associating four elements.

ClearAll[f]; SetAttributes[f, {Flat, OneIdentity}]; rawFunctions =
Union[FixedPoint[Union[Flatten[ReplaceAllList[#, f[a_, b_] -> g[a, b]]]] &,
f[a, b, c, d]] /. f -> g];

Off[General::"spell1"]; Off[General::"spell"];
divide[x_, y_] /; y != 0 := Divide[x, y]; divide[x_, 0] := Indeterminate;

Then we remove all duplicates and expressions that involve the application of g to three elements.

uniqueFunctions =
DeleteCases[rawFunctions, _?(Not[FreeQ[#, g[x__ /; Length[{x}] >= 3]]] &),
1];

Finally we replace g by Subscript[A, 2],Subscript[A, 1],Subscript[A, 0], in this order, and swap in the numbers from a hand of cards

functionsWNumbers[hands_List] :=
Map[(i = 0;
MapAll[If[# === g, # /. g -> Subscript[A, Mod[++i, 3]], #] &,
uniqueFunctions, Heads -> True] /. {a -> #[[1]], b -> #[[2]],
c -> #[[3]], d -> #[[4]]}) &, hands]

The following step generates every possible combination of operators. For four binary functions and four cards, we have a maximum of three functions per hand and only 64 possible combinations.

generateRules[binaryFunctions_List, numCards_Integer] :=
Module[{raw, refined, numFuncs},
numFuncs = Length[binaryFunctions];
raw = Map[Thread,
Map[RuleDelayed[Array[Subscript[A, # - 1] &, {numFuncs}], #] &,
Distribute[Array[binaryFunctions &, {numFuncs}], List]]];

(* since an actual hand never involves more than three binary operations,
we remove the rules involving unnecessary As.*)

refined = Union[DeleteCases[raw,Apply[Alternatives,
Map[HoldPattern[#] &,
Table[Subscript[A, i] :> _, {i, numCards - 1, numFuncs - 1}]]],
Infinity]];
refined]

Now we map our selected functions over the generic rules from the previous step.

generateHands[functions_List, rules_List] :=
Table[Union[# /. rules] & /@ functions[[i]], {i, 1, Length[functions]}]

When we get our answers, {1,1,2,2} is treated as distinct from {2,2,1,1}. Let’s fix that. The following assumes the cardSet is a single list of four integers {1,1,2,3}, and that the possibilitySet is a list of {{ordered four cards},{solutions}} like
{{6,6,6,6},{((6+6)+6)+6,(6+(6+6))+6,(6+6)+(6+6),6+((6+6)+6),6+(6+(6+6)),6 6-(6+6),(6 6-6)-6}}

solutionsForSet[cardSet_List, possibilitySet_List] :=
Module[{allVarieties, matches},
allVarieties = Permutations[cardSet];
matches = Select[possibilitySet, MemberQ[allVarieties, #[[1]]] &];
Flatten[matches[[All, 2]], 1]]

So, what do we find? Running every possible hand of cards through our 64 possible rules, and seeing which come out equal to 24, we find 566 of the 715 possible hands (about 79% of all possible cases) are solvable with arithmetic alone.

The unsolvable hands are {{1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 1, 3}, {1, 1, 1, 4}, {1, 1, 1, 5}, {1, 1, 1, 6}, {1, 1, 1, 7}, {1, 1, 1, 9}, {1, 1, 1, 10}, {1, 1, 2, 2}, {1, 1, 2, 3}, {1, 1, 2, 4}, {1, 1, 2, 5}, {1, 1, 3, 3}, {1, 1, 5, 9}, {1, 1, 5, 10}, {1, 1, 6, 7}, {1, 1, 6, 10}, {1, 1, 7, 7}, {1, 1, 7, 8}, {1, 1, 7, 9}, {1, 1, 8, 9}, {1, 1, 8, 10}, {1, 1, 9, 9}, {1, 1, 9, 10}, {1, 1, 10, 10}, {1, 2, 2, 2}, {1, 2, 2, 3}, {1, 2, 9, 9}, {1, 2, 9, 10}, {1, 2, 10, 10}, {1, 3, 5, 5}, {1, 4, 7, 10}, {1, 4, 8, 10}, {1, 4, 9, 9}, {1, 5, 5, 7}, {1, 5, 5, 8}, {1, 5, 7, 7}, {1, 6, 6, 7}, {1, 6, 7, 7}, {1, 6, 7, 8}, {1, 6, 10, 10}, {1, 7, 7, 7}, {1, 7, 7, 8}, {1, 7, 10, 10}, {1, 8, 9, 9}, {1, 8, 9, 10}, {1, 8, 10, 10}, {1, 9, 9, 9}, {1, 9, 9, 10}, {1, 9, 10, 10}, {1, 10, 10, 10}, {2, 2, 2, 2}, {2, 2, 2, 6}, {2, 2, 7, 9}, {2, 2, 9, 9}, {2, 3, 3, 4}, {2, 5, 5, 5}, {2, 5, 5, 6}, {2, 5, 9, 9}, {2, 6, 7, 7}, {2, 7, 7, 7}, {2, 7, 7, 9}, {2, 7, 8, 10}, {2, 7, 9, 9}, {2, 9, 9, 9}, {2, 9, 9, 10}, {2, 10, 10, 10}, {3, 3, 4, 10}, {3, 3, 5, 8}, {3, 3, 7, 10}, {3, 3, 10, 10}, {3, 4, 6, 7}, {3, 4, 8, 8}, {3, 4, 9, 10}, {3, 5, 5, 5}, {3, 5, 5, 10}, {3, 5, 7, 7}, {3, 5, 8, 10}, {3, 7, 8, 10}, {3, 10, 10, 10}, {4, 4, 5, 9}, {4, 4, 6, 6}, {4, 4, 6, 7}, {4, 4, 9, 9}, {4, 4, 9, 10}, {4, 7, 7, 9}, {4, 7, 7, 10}, {4, 9, 9, 9}, {4, 9, 10, 10}, {4, 10, 10, 10}, {5, 5, 5, 7}, {5, 5, 5, 8}, {5, 5, 5, 10}, {5, 5, 6, 9}, {5, 5,
6, 10}, {5, 5, 7, 9}, {5, 6, 7, 10}, {5, 7, 7, 7}, {5, 7, 7, 8}, {5, 7, 9, 9}, {5, 8, 9, 9}, {5, 8, 9, 10}, {5, 8, 10, 10}, {5, 9, 9, 9}, {5, 9, 9, 10}, {5, 10, 10, 10}, {6, 6, 6, 7}, {6, 6, 7, 7}, {6, 6, 7, 8}, {6, 6, 9, 9}, {6, 6, 10, 10}, {6, 7, 7, 7}, {6, 7, 7, 8}, {6, 7, 7, 9}, {6, 7, 8, 8}, {6, 7, 9, 10}, {6, 8, 10, 10}, {6, 9, 9, 9}, {6, 9, 10, 10}, {7, 7, 7, 7}, {7, 7, 7, 8}, {7, 7, 7, 9}, {7, 7, 7, 10}, {7, 7, 8, 8}, {7, 7, 8, 9}, {7, 7, 8, 10}, {7, 7, 9, 9}, {7, 7, 10, 10}, {7, 8, 8, 8}, {7, 8, 9, 9}, {7, 9, 9, 9}, {7, 9, 9, 10}, {7, 9, 10, 10}, {7, 10, 10, 10}, {8, 8, 8, 8}, {8, 8, 8, 9}, {8, 8, 9, 9}, {8, 8, 9, 10}, {8, 8, 10, 10}, {8, 9, 9, 9}, {8, 9, 9, 10}, {8, 9, 10, 10}, {8, 10, 10, 10}, {9, 9, 9, 9}, {9, 9, 9, 10}, {9, 9, 10, 10}, {9, 10, 10, 10}, {10, 10, 10, 10}}

These same methods can be used with larger number of functions too, as I will show in coming posts.