Problem 621. Cryptomath: Addition

Created by Doug Hull

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ W A I T\n + A L L\n ---------\n G I F T S]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>equals:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 9 6 0 8\n + 6 7 7\n ---------\n 1 0 2 8 5]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given strings a,b,c find where a + b = c; No left hand zeros. All solutions are believed to be unique.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Beware, the test machine might time out your entry!</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If you want some easier problems that build up to this one,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/641-make-a-random-non-repeating-vector\"><w:r><w:t>random permutations of integers</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/640-do-a-binary-comparison-on-a-vector\"><w:r><w:t>binary comparisons</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/639-string-substitution-sub-problem-to-cryptomath\"><w:r><w:t>string substitution</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/642-convert-a-vector-into-a-number\"><w:r><w:t>convert list of numbers to a scalar</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Why are the above building blocks to solving this problem? Well, let's think about the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://c2.com/xp/DoTheSimplestThingThatCouldPossiblyWork.html\"><w:r><w:t>simplest thing that could possibly work.</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If we</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Made random mapping of the ten or less characters to the ten digits</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Converted the characters to a vector of numbers</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Converted the vector of numbers to a scalar</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Checked the scalars in the summation</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Tried again if it did not work</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Eventually, we would find the correct answer. Worst case scenario, we have a one in 10! (1/3,600,000) chance of stumbling upon the answer. For the eight character case, it is 8! (1/40,320). I like those odds enough that it is worth trying.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/648-cumulative-probability-of-finding-an-unlikely-combination\"><w:r><w:t>supplemental problem</w:t></w:r></w:hyperlink><w:r><w:t> finds out which technique, methodical or random is better.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

<pre> W A I T
 + A L L
 ---------
 G I F T S</pre>equals:<pre> 9 6 0 8
 + 6 7 7
 ---------
 1 0 2 8 5</pre>Given strings a,b,c find where a + b = c; No left hand zeros. All solutions are believed to be unique.Beware, the test machine might time out your entry!If you want some easier problems that build up to this one,<ul><li><a href="http://www.mathworks.com/matlabcentral/cody/problems/641-make-a-random-non-repeating-vector">random permutations of integers</a></li><li><a href="http://www.mathworks.com/matlabcentral/cody/problems/640-do-a-binary-comparison-on-a-vector">binary comparisons</a></li><li><a href="http://www.mathworks.com/matlabcentral/cody/problems/639-string-substitution-sub-problem-to-cryptomath">string substitution</a></li><li><a href="http://www.mathworks.com/matlabcentral/cody/problems/642-convert-a-vector-into-a-number">convert list of numbers to a scalar</a></li></ul>Why are the above building blocks to solving this problem? Well, let's think about the <a href="http://c2.com/xp/DoTheSimplestThingThatCouldPossiblyWork.html">simplest thing that could possibly work.</a>If we<ul><li>Made random mapping of the ten or less characters to the ten digits</li><li>Converted the characters to a vector of numbers</li><li>Converted the vector of numbers to a scalar</li><li>Checked the scalars in the summation</li><li>Tried again if it did not work</li></ul>Eventually, we would find the correct answer. Worst case scenario, we have a one in 10! (1/3,600,000) chance of stumbling upon the answer. For the eight character case, it is 8! (1/40,320). I like those odds enough that it is worth trying.A <a href="http://www.mathworks.com/matlabcentral/cody/problems/648-cumulative-probability-of-finding-an-unlikely-combination">supplemental problem</a> finds out which technique, methodical or random is better.

Solve

Solution Stats

275 Solutions
24 Solvers

Last Solution submitted on Dec 31, 2020

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

K E on 17 May 2012

The problem is to find the number-to-string matching that results in a + b = 3, right?

Suresh Deoda on 17 Oct 2012

Test case needs to be changed,thre can be more than 1 solution to the problem.
e.g. in question for example,[afgilstw = 74062195] is also one correct solution.

Doug Hull on 18 Oct 2012

Suresh, Which test case? Please be more explicit. These were all taken from a list of known problems, so I need more info to understand if one is flawed.

Suresh Deoda on 19 Oct 2012

I am saying in general there can be more than one solution e.g. the one in the question, Wait+All = GIFTS , for that[afgilstw = 74062195] is also valid solution. i.e.[ 5769 +722 = 6491]

Doug Hull on 22 Oct 2012

Note in the instructions: "No left hand zeros"

Jean-Marie Sainthillier on 2 Sep 2013

Difficult to solve in time.

Informaton on 28 Aug 2017

I saw the note regarding "No left hand zeros", but did not put it together until later that it's really a hint regarding the sum; the 'G' in gifts cannot be mapped to a 0. It's clear now, but initially I thought the remark was referring to 'ALL' not having a blank character to the left (e.g. '\ ALL') that would be 0 when mapped to digits (e.g. 0677).

Rafael S.T. Vieira on 16 Jun 2020

No leading zeros or repeating numbers. Be careful.
% 4956 911 05867
% 9707 766 10473
% wait all gifts

Rafael S.T. Vieira on 16 Jun 2020

The problem with randomness is that we can't be sure about the time one experiment will take. Sometimes my solution founds the mapping in less than one second, but, in others, it can take 25 seconds: blowing the time limit.

Problem Recent Solvers24

Problem Tags

ml101

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 621. Cryptomath: Addition

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers24

Suggested Problems

More from this Author52

Problem Tags

Community Treasure Hunt

Problem 621. Cryptomath: Addition

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers24

Suggested Problems

More from this Author52

Problem Tags

Community Treasure Hunt

Players