As a kid, one of my favorite summer games by the poolside was working out cryptosums. So in a bored moment recently I decided to write my own cryptosum generator. I was curious to know just how few characters one really needed to generate such puzzles, so I tried my hand at a little golf:

# 288 characters (excluding trailing \n)
sub l{length$_[0]};sub p{$x=int rand($n=10**$d);$y=int rand($n);$z=$x+
+$y;@a=();for(0..9){while(defined $a[$n=rand(10)]){};$a[$n]=chr(65+$_)
+;}$n=2+l$z;$"='';print map{eval"y/0-9/@a/";$_}(' 'x($n- l$x),"$x
+ ",' 'x($n-2- l$y),"$y
",'-'x$n,"
  $z
");}$d=shift||4;$q=shift||1;p$d for(1..$q);

[download]

I'm not much of a golfer (either on the green or in code), but I find I learn a lot by watching others play the game. Would you help me lower the score on this? I'm not very good at decoding dense obfuscated code and my bit math is atrocious, so I would be grateful if you would also explain the tricks you used to get rid of characters.

For those interested in golfing, the above cryptosum generator has the following specification:

The program should run under 5.8.8 (I have an old machine) and have two parameters on the command line: max_digits_in_addends number_of_puzzles_to_generate. Thus perl Cryptosum.pm 5 4 would print out four puzzles each with no more than 5 digits in the addends. (the result may have more digits). And would look like this:

   BGBHD
+  ACGIJ
--------
  EHJECB

   JAECD
+  BFIEF
--------
  CAGCGF

  GJBEJ
+ HGJIF
-------
  IBFCA

   BJAGH
+  DCBFB
--------
  BFACGI

[download]

For each sum printed:

#Sum looks like this:
    ABC
+  DDDD
-------
  AEABB

[download]

Best, beth

Replies are listed 'Best First'.
Re: Golfing cryptosums (218=>176=>167)
by BrowserUk (Patriarch) on Aug 09, 2009 at 13:23 UTC

    A first pass to check the output complies with the rules? 

    @c='A'..'Z';map{$x.=splice@c,rand@c,1}1..10;($d,$s)=@ARGV;$n=$d+2;sub 
+p{$t="%${n}s\n";printf" $t+$t ".'-'x$n."\n $t\n",@_}sub x{eval"tr[0-9
+][$x]"for@_}map{@a=map{int rand 10**$d}1..2;$a[@a]=$a[0]+$a[1];x(@a);
+p@a}1..$s

    [download]

    Updates:

    176

    $x=join'',sort{.5<=>rand}A..Z;$s=pop;$n=2+pop;$t="%${n}s\n";map{@a=map
+{int rand".1e$n"}1,1;$a[@a]+=$a[0]+$a[1];eval"tr[0-9][$x]"for@a;print
+f" $t+$t ".'-'x$n."\n $t\n",@a}1..$s

    [download]

    167

    $x=join'',sort{.5<=>rand}A..Z;$s=pop;$n=1+pop;$t="%${n}s\n";map{$a[2]+
+=$_ for@a=map{int rand".1e$n"}1,1;eval"y/0-9/$x/"for@a;printf" $t+$t 
+".'-'x$n."\n $t\n",@a}1..$s

    [download]

    165

    $x=join'',sort{.5<=>rand}A..Z;$s=pop;$£=1+pop;$t="%$£s\n";map{$a[2]+=$
+_ for@a=map{int rand".1e$£"}1,1;eval"y/0-9/$x/"for@a;printf" $t+$t ".
+'-'x$£."\n $t\n",@a}1..$s

    [download]
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]

      Looks right to me!

      Best, beth

[reply]
        $;=1+shift;$t="%$;s
";@x=sort{.5-rand}A..Z;map{printf" $t+$t-$t $t
",grep 1+s/\d/$x[$&]/g,@a=map(0|rand".1e$;",0,1),'-'x$;,$a[0]+$a[1]}1.
+.pop

        [download]

        BrowserUK's solution, only improved a little. Few quick tricks:

        • plain enter used instead of \n
        • s///e used instead of eval"y///" - it is almost always shorter
        • int ... can be shorter: 0|... or 0^...
[reply]
[d/l]
[select]
Re: Golfing cryptosums
by ysth (Canon) on Aug 09, 2009 at 19:27 UTC
[reply]

      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%

      [download]

      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.

[reply]
[d/l]

        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.

[reply]

Back to Meditations