Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Golfing cryptosums

by ysth (Canon)
on Aug 09, 2009 at 19:27 UTC ( #787193=note: print w/ replies, xml ) Need Help??


in reply to Golfing cryptosums

For extra credit, eliminate puzzles with multiple solutions?


Comment on Re: Golfing cryptosums
Re^2: Golfing cryptosums
by Anonymous Monk on Aug 10, 2009 at 04:00 UTC

    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.

      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.

        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.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://787193]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (8)
As of 2014-04-23 21:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (555 votes), past polls