Re: Golfing cryptosums

[ysth]

For extra credit, eliminate puzzles with multiple solutions?

[Anonymous Monk]

Yeah, it isn't (IMO) a letter-sum puzzle (aka crypto-sum) if the solution isn't unique.

If I require the leading digits to be non-zero, then adding two N-digit numbers gives us the following odds:

Digits  Unique  Equations  Odds
  1          2       81    2.47%
  2         76     8100    0.94%
  3      5,112     81e4    0.63%
  4  1,222,504     81e6    1.51%

There is only a single solution to each of "a + b = ac" and "a + b = bc" so those are the only two 1-digit letter-sum puzzles (where you can replace abc with any three unique letters) -- note that I consider a+b different from b+a for several reasons. (There are 32 solutions to "a + b = c" and 30 solutions to "a + b = cd" and no solutions to "a + b = ba", to give a few examples of unacceptable puzzles.)

Of the 8100 (90*90) 2-digit + 2-digit sums that can be selected at random, only 76 result in a unique pattern of repeated digits such that transforming it into a letter-sum puzzle will give you one with a unique solution. So randomly selecting two 2-digit numbers only has a 0.94% chance of producing an acceptable letter-sum puzzle.

So the vast majority of 4-or-fewer-digit puzzles are unacceptable and would not be published in any of the places where I have seen letter-sum puzzles published.

I'm pretty sure that the odds steadily increase with the number of digits from this point on. And I haven't taken the time to run / optimize the code to precisely calculate those odds (nor to write the code to check whether a single puzzle has duplicate solutions which would then allow me to use random sampling to estimate the odds for larger numbers of digits).

Those are much more interesting challenges to me than golfing something that mostly produces invalid letter-sum puzzles. So thanks for that diversion.

[ELISHEVA]

To each his own.

Your analysis helps me realize that even as a kid, I was always more interested in the relationship between things than in the one and only solution to things. To me it hardly matters whether there are 0, 1, or many solutions to a problem. In the case of cryptosums, I'm fascinated by the fact that the mere arrangement and repetition of symbols provides enough information to deduce (a) whether or not a mapping between those symbols and the set of digits exists and (b) whether or not that mapping is unique.

How did you come up with those figures? According to this article, determining whether or not a solution even exists for a particular puzzle is NP-complete (if we allow for bases other than 10). Other than limiting the problem space to 10! possible mappings, how does limiting the problem to base 10 help one determine the potential number of puzzles with solutions, let alone the number of puzzles with unique solutions? Can you determine the number of problems without knowing exactly which particular puzzles will have solutions? Or did you use brute force to count the number of solutions for each puzzle?

Best, beth

Update: clarified question.

[Anonymous Monk]

Instead of constructing an equation at random and then converting it into a puzzle, one can also just construct a random puzzle (but don't let yourself use more than 10 different letters). Here are your odds of success with that route:

Digits       Number of puzzles
  1                     31,200 with unique solutions
                        37,102 with no solutions
                       406,250 with 4..32 solutions
                       474,551 total puzzles

  2                 10,795,200 with unique solutions
                 1,990,652,352 with no solutions
                 6,339,278,400 with 3..476 solutions
                 8,340,725,952 total puzzles

  3             33,433,717,226 with unique solutions
             6,746,392,175,276 with no solutions
           139,816,773,439,850 with 2..1200 solutions
           146,596,599,332,352 total puzzles


  4      1,974,825,396,897,600 with unique solutions
       240,014,957,704,387,2?? with no solutions
     1,147,855,057,502,310,0?? with 2..3840 solutions
     1,389,844,840,603,594,8?? total puzzles

     2,576,581,829,865,418,742 total random letter choices
     1,186,736,989,261,824,0?? with over 10 different letters

Digs   Uniq     None     Dupl    Max
  1    6.57%    7.82%   85.61%    32
  2    0.13%   23.87%   76.00%   476
  3    0.02%    4.60%   95.38%  1200
  4    0.14%   17.27%   82.59%  3840

And I suspect the odds just get worse after this. (And note that the numbers have gotten too complicated for both Perl and me toward the end there so don't use these for life-and-death calculations.)