Programming Puzzle 28 - Alphabet Math?

[Tom Cone Jr]

Puzzle 28 - Alphabet Math

Write an xbasic script that will solve this puzzle. Display your answer in a message box on screen.

In the following math problem substitute numeric digits for the letters.
Find the three numbers that these words represent.
You may assume that none of the numbers begin with a zero. However, the number assigned to
a letter must be the same everywhere that letter appears.

    SEND
  + MORE
  -------
   MONEY

There are numerous valid solutions to this, but only one where MONEY = 10,652.

What are the values of SEND and MORE that make MONEY = 10,652 ?




Credit for this puzzle: EasyCalculations.com

[Keith Hubert]

Hi Tom,

These puzzles beat me to do in Xbasic. I do it the hard way, pen and paper!!!

How about

 CROSS
+ROADS
DANGER

The only clue is S=3 and there are no Zeros.

[Lenny Forziati]

Here's a brute-force approach, which surely someone can improve upon. It finds all possible solutions, and is NOT fast - running in the background while I was doing other work, it took over 20 minutes on my system to identify 155 solutions.

'  SEND
'+ MORE
'------
' MONEY
'Assume that none of the numbers begin with a zero
'    therefore neither M nor S may be zero

'Variables to store results
dim SENDValue			as n
dim MOREValue			as n
dim MONEYValue			as n

'start by creating a simple formula by multiplying the digits by their place value
' SEND becomes 1000S + 100E + 10N + D
' MORE becomes 1000M + 100O + 10R + E
' MONEY becomes 10000M + 1000O + 100N + 10E + Y
dim SENDFormula			as c = "1000*S + 100*E + 10*N + D"
dim MOREFormula			as c = "1000*M + 100*O + 10*R + E"
dim MONEYFormula		as c = "10000*M + 1000*O + 100*N + 10*E + Y"

'A simplified formula can also be assembled...
' assemble SEND + MORE = MONEY
'    1000S + 100E + 10N + D + 1000M + 100O + 10R + E = 10000M + 1000O + 100N + 10E + Y
' then regroup
'    1000S + 91E + D + 10R = 9000M + 900O + 90N + Y
dim AssembledFormula	as c = "1000*S + 91*E + D + 10*R = 9000*M + 900*O + 90*N + Y"

'variables for tracking the values of the individual digits
dim D					as n
dim E					as n
dim M					as n
dim N					as n
dim O					as n
dim R					as n
dim S					as n
dim Y					as n

dim Solution			as c = ""
dim NumSolutionsFound	        as n = 0
dim ProfessorsTarget	        as n = 10652	'the problem asks specifically about 10652
dim ProfessorsTargetSol	as c = ""		'will be populated with text to solve the specific case asked about
dim Timer				as Util::Timer	'see how long it takes to run this, just for curiosity

'quick-and-dirty (SLOW-and-dirty) brute-force approach to just try every combination that satisfies the formula above
'  simply try digits 0-9 for each individual digit (except M and S, which can only be 1-9)
'  no attempt is made to ensure that the values of each dgit are unique, since that was not specified in the problem
for D = 0 to 9
	for E = 0 to 9
		for M = 1 to 9 'M cannot be zero
			for N = 0 to 9
				for O = 0 to 9
					for R = 0 to 9
						for S = 1 to 9 'S cannot be zero
							for Y = 0 to 9
								ui_yield() 'keeps the A5 UI responsive while this long-running script is doing its thing

								'if eval(AssembledFormula) 'An eval here makes the code a bit neater, but also runs slower, so use the formula directly for better performance
								if (1000*S + 91*E + D + 10*R) = (9000*M + 900*O + 90*N + Y)
									'test was true, solution found
									NumSolutionsFound = NumSolutionsFound + 1
									statusbar.Set_Text("Found " + NumSolutionsFound + " solutions so far...")

									SENDValue	= eval(SENDFormula)
									MOREValue	= eval(MOREFormula)
									MONEYValue	= eval(MONEYFormula)
									Solution = Solution + "SEND: " + ltrim(str(SENDValue)) + crlf() + \
														"MORE: " + ltrim(str(MOREValue)) + crlf() + \
														"MONEY: " + ltrim(str(MONEYValue)) + crlf() + "------" + crlf()
									if MONEYValue = ProfessorsTarget
										'The professor asked specifically about this value
										ProfessorsTargetSol = "When MONEY is " + ProfessorsTarget + ", SEND is " + SENDValue + " and MORE is " + MOREValue
									end if
								end if

							next Y
						next S
					next R
				next O
			next N
		next M
	next E
next D
Timer.Stop() 'stop the timer

Solution = "Found " + NumSolutionsFound + " solutions in " + Timer.ElapsedSeconds + " seconds" + \
			crlf() + "*****************" + "The professor asked specifically about " + ProfessorsTarget + \
			crlf() + chr(9) + ProfessorsTargetSol + \
			crlf() + "*****************" + Solution
showvar(Solution,"Found " + NumSolutionsFound + " Solutions")

[Tom Cone Jr]

Lenny,

Very nice! I've shown your xbasic script to the "professor" and he's curious whether your solution assures that values assigned to specific letters in a word are not used by different letters elsewhere. i.e. a value assigned to the letter "E" may not be used by the letter "M", or any other letter of the alphabet in the three words. Otherwise, you'd be changing the alphabetic representation of the puzzle, which the professor says is a no-no. I attempted to persuade him that this limitation was not explicitly stated in the puzzle, but he is adamant. Perhaps this is because he missed his nap this afternoon! But in his cranky condition he insists that this limitation should be inferred from the puzzle as presented.

Added later ...
I've shown the professor your results, and he congratulates you on solving the puzzle for the case where MONEY = 10652. He still has a bone to pick with you on some of the other "solutions", but as they're not necessary to solve the original puzzle, I've persuaded him to give you full credit. Nice work! Hope you had fun.

[Lenny Forziati]

Lenny,

Very nice! I've shown your xbasic script to the "professor" and he's curious whether your solution assures that values assigned to specific letters in a word are not used by different letters elsewhere. i.e. a value assigned to the letter "E" may not be used by the letter "M", or any other letter of the alphabet in the three words. Otherwise, you'd be changing the alphabetic representation of the puzzle, which the professor says is a no-no. I attempted to persuade him that this limitation was not explicitly stated in the puzzle, but he is adamant. Perhaps this is because he missed his nap this afternoon! But in his cranky condition he insists that this limitation should be inferred from the puzzle as presented.

There's actually a comment in the code specifically explaining that this condition is not checked for since it isn't required, but it is certainly one of the improvements that could be made to what I posted. Depending on the implementation, this checking could also greatly improve the performance of the script (or have almost no impact at all). Others are welcome to use what I provided as a basis to make this improvement and/or any others.

The professor really should be more careful about what he expects to be inferred though. It would be just as reasonable to infer that the script could stop at the first solution as it would be to infer that no two letters could have the same value, IMHO. He should remember that inferring is essentially assuming, and I hope he knows what assume does

[Lenny Forziati]

There's actually a comment in the code specifically explaining that this condition is not checked for since it isn't required, but it is certainly one of the improvements that could be made to what I posted. Depending on the implementation, this checking could also greatly improve the performance of the script (or have almost no impact at all). Others are welcome to use what I provided as a basis to make this improvement and/or any others.

I'll even leave a hint to one such implementation: continue. With it, I can cut the 20+ minutes down to 1.5 minutes and get rid of what the professor considers to be extraneous solutions at the same time.

[Tom Cone Jr]

Lenny,

I've managed to catch up with the professor before his evening lecture and he's unpersuaded. Instead, he says that if there's any ambiguity in the puzzle its the fault of me, your humble servant, and can hardly be his fault. Academics! What are you gonna do with them!

Thanks for planting a few useful clues of your own. Let's see if anyone else will take a crack at this.

[aschone]

So um... can you send more money please?

[Tom Cone Jr]

Andy, very nice! Your solution runs quickly. The professor is impressed that you solved this by working backwards from the clues that were furnished in the puzzle.

good work!

[StephenP]

Here is my solution. I stuck to the very basics of what was asked.

'Date Created: 10-Jun-2012 02:14:16 PM
'Last Updated: 10-Jun-2012 02:47:19 PM
'Created By  : spilon
'Updated By  : spilon
'Puzzle 28 - Alphabet Math
'Write an xbasic script that will solve this puzzle. Display your answer in a message box on screen.
'In the following math problem substitute numeric digits for the letters. 
'Find the three numbers that these words represent. 
'You may assume that none of the numbers begin with a zero. However, the number assigned to
'a letter must be the same everywhere that letter appears.
'
'Code:
'    SEND
'  + MORE
'  -------
'   MONEY
'
'There are numerous valid solutions to this, but only one where MONEY = 10,652.
'What are the values of SEND and MORE that make MONEY = 10,652 ?
'Credit for this puzzle: EasyCalculations.com

'Given: M-O-N-E-Y = 1-0-6-5-2
dim nMONEY as n = 10652
'Given: only one possible solution for previous given (i.e., not asked to prove only one solution)
'Assuming: digits unique for each letter
'Thus: S-E-N-D = ?-5-6-?
dim nSEND as n
'Thus: M-O-R-E = 1-0-?-5
dim nMORE as n

'With unique values for each letter, R = 3, 4, 7, 8 or 9
'Thus: M-O-R-E = 1-0-3-5 or  1-0-4-5 or  1-0-7-5 or  1-0-8-5 or 1-0-9-5

'Challange: look for occurance when nMONEY - nMORE has pattern ?-5-6-?

for nMORE = 1035 to 1095 step 10
	'skip these values, as not part of check
	if .not. inlist(nMORE,1055,1065) then
		if right(left(ut(str(nMONEY - nMORE)),3),2) = "56" then
			'we found our match
			ui_msg_box("Send More Money",chr(9) + "Send" + chr(9) + (nMONEY - nMORE) + crlf() + "+" + chr(9) + "More" + chr(9) + nMore + crlf() + "_____________________________" + chr(9) + crlf() + "=" +  chr(9) + "Money" + chr(9) + nMONEY)
			exit for
		end if
	end if
	'if we are still here, go to next number
next nMORE

[Tom Cone Jr]

Very nice, Stephen!

I woke the "professor" from his Sunday afternoon nap to have a look at your solution. He was impressed with your use of the INLIST() function to exclude values that are disqualified by the puzzle's terms. He had "forgotten" that this function could handle numeric data in the "list". Your use of the function was sweet, however, he thought an explanatory comment on the list items themselves might prove useful six months from now!

The Professor's "eyes crossed" when he tried to decipher line 39 where you say:

right(left(ut(str(nMONEY - nMORE)),3),2) = "56"

Your expression works just fine, but the professor suggests you look to SUBSTR() to simplify the expression.

Congratulations for coming up with a solution that runs so quickly.