https://kats.coffee/blog/send-more-money

kats.coffee

  * Home
  * Blog
    iPad Pro 1 Year RetrospectiveBook Classics IBook Classics IntroSt
    Petersburg Board Game SimulatorMovember 2017 Giving Tuesday
    Movember 2017 AnnouncementCafeteria Intervals
  * ICPC Blog
    Generalized Roman NumeralsSign GamesPicky LoungesWarring Clans
    DemoBankrupt Kingdoms DemoWards Demo
  * Demos
    DominionVisa CountriesMeeting BingoMachi KoroSt. PetersburgSpace
    InvadersContiguous Regions Demo
  * Publications
  * Patents
  * PassZero
    PassZeroChrome Extension

send + more = money
July 19, 2021
#javascript#algorithm

A friend nerd-sniped me with this problem:

      send
    + more
    ------
     money

where each letter represents a digit 0-9 and must take on a unique
value.

You can of course try to solve this problem through trial and error
(though there are 10^8 unique possibilities). You can also try a
Sudoku-style logic-based approach. You might, for example,
immediately set m=1. You can try this approach to solve the puzzle
below:

+    {{ letter }} [                    ] [                    ]
x each letter must be assigned to a unique number
x top 2 rows must sum to the bottom row
[?] your solution is correct

If you solved it, well done! There are 2 valid solutions, though one
of them sets m=0, so it's the sort of solution most people wouldn't
immediately find.

Show Solution #1Show Solution #2

I solved this problem on pen and paper, but I wondered how we might
solve this computationally. We can of course try brute force search
(10^8 is not very big for a computer), but is there a smarter way ^1?
Think about it and if you come up with a solution, email me at daniel
[at] kats [dot] coffee. I'll update this tomorrow with the answer I
came up with.

Update & Computational Solution

I got a lot of very smart answers. Many of you realized that if you
use the fact that the numbers must be unique, you will only search
10!/2 solutions in the worst case.

A lot of you also figured out rules to this problem such as n = e +
1, but were unsure how to make a computer learn those kinds of rules.

I implemented 3 different kinds of solutions: one brute-force, one
brute-force that searches only the unique possibilities, and one
using constraint search. In basic AI, for example in Sudoku solvers,
you can express general constraints over variables (relationships
between variables like all variables in a group must take unique
values, or a domain constraint such as (m = 0 or m = 1)). You can
then use those constraints to dramatically speed up your search.

I implemented the most basic type: constraint search with Forward
Checking (FC). The idea here is, if you know some partial assignment
of variables won't work out, you don't need to try different values
for other variables. For example, take a look at the partially-filled
Sudoku puzzle below:

[sudoku-fc-]

We can see that there are no possible values for the highlighted
cell. There's no point in trying to solve the rest of the puzzle, we
know it's not possible.

Here are the methods I implemented, together with their performance
(Python3.9 on an old Macbook Pro).

                            Use m
         Technique           =1         Variable Order              Time (seconds, 5 runs)            Number of Solutions Tried (5 runs)       Theoretical
                            Trick                                                                                                              Worst Case
                              ?
{{ isSmallScreen() ?                                          {{                                 {{ Math.round
row.run_params.solver.split       {{                          row.results.agg.mean_time.toFixed  (row.results.agg.mean_states).toLocaleString
('_').join('-') :                 row.run_params.letter_order (3) }} +- {{                        () }} +- {{ Math.round
row.run_params.solver }}          }}                          row.results.agg.stdev_time.toFixed (row.results.agg.stdev_states).toLocaleString
                                                              (3) }}                             () }}

If you tried to program a solution, you may have noticed that the
order in which you try to set the variables makes a big difference.
You can see this in the table above - random variable orderings
produce huge fluctuations in the number of solutions tried. I also
created a "worst-case" variable ordering that would get the number of
states checked before a solution is found as close to the theoretical
maximum as possible. In that case, the runtime is a lot more stable.

Notice that the Forward Checking technique tries only around 70
solutions before finding the correct answer, so it's extremely
efficient. In terms of constraints, I used the simple fact that for
each column (for example e, o, n), either e + o (mod 10) = n, or e +
o + 1 (mod 10) = n, when you carry the 1 from the previous column.
Mod 10 here means the remainder after dividing by 10. We can get even
better results by adding constraints which prevent the leading digits
from being 0.

However, for a problem of this size, using just the brute_force_uniq
technique together with the m=1 trick, a pretty old laptop can find
the solution in a fraction of a second. The brute_force_uniq solution
is also far simpler to write: under 25 lines of code. In contrast,
the Forward Checking solution was over 100 lines.

[send-more-]

You can find all the code on Github.

^1We can of course manually partially solve it and for example set m=
1 and then only search 10^7 states

about

I'm a researcher, data scientist, and programmer (mostly in Python).
My work focuses on the intersection of machine learning and security.

I like to fiddle with data and make pretty graphs. I'm also a big fan
of stats in board games.

Twitter@boompig
Githubboompig
Google Scholar
Login