Division!

Michael Cain says:

Hmmm…

Background: Many years ago, while I was getting an MS in operations research, I took a class where the prof assigned, once per week or so, a combinatorial sort of problem. The intent was that students would spend a couple of hours finding the “trick” to transform the problem into one that could be solved manually. I found it was quicker in terms of student-time to write little programs to run through all possible solutions, or at least all possible interesting solutions. When the homework was handed back, the prof would make… comments. The comment he often made about my solution was, “And Mr. Cain, of course, used brute force on the computer [1] to get an answer.” To which my response was generally, “Yes, but I was clever about the brute force. Not only can my piece of code solve the problem we were given, but it can (a) tell you if there are multiple solutions, and (b) is fast enough to be used to solve similar non-toy problems.” Sometimeswith the prof’s response of, “Yes. Mr. Cain, the chalkboard is yours, to talk about clever use of brute force for a few minutes.” The division problems are well-suited to clever use of brute force.

Side note: Absent any constraints, any problem of this form has a “trivial” solution with all letters having the value zero, exploiting the fact that 0/0 is undefined, hence any damned thing you would like it to be.

Having said all that… in setting up conditions that a solution must satisfy, the most obvious in this case is

LAA * LLATT + LDDTR == LTRNNUI

This involves only eight of the variables. Running through the 100 million possible combinations of eight variables (following Mr. Schilling’s advice to assume nothing, but ignoring the all-zero solution because it’s boring) and testing against that condition takes some time (in Perl, on my Mac, with no serious effort to optimize the code, 19 minutes of processor time). Unsurprisingly, there are multiple possibilities.

However, if we’re clever about the order in which we examine possible solutions, that condition also gives us

(A * T + R – I) mod 10 == 0

that can be used to eliminate a lot of the possibilities earlier in the search, reducing the search time to about 2 minutes, and identifying exactly the same 50 partial solutions.

If we start working our way through other simple constraints in the larger problem, we immediately find that

(R + N) mod 10 == I and
(T + N) mod 10 == U

can be incorporated using only the eight variables previously used and reduce the search time to about 1.2 seconds. More interestingly, at this point we find that there are no non-trivial results that satisfy the constraints.

My code is specific to the problem given. Generalizing it to handle any such division problem is left as a straightforward exercise for the student.

[1] Most students avoided even attempting brute-force solutions because we were provided with limited pseudo-funds to buy resources on the university’s computers. Over the course of time at two different universities, I was a living demonstration that there’s almost always a way to get computer time for free. God, I love having fast personal computers instead of having to steal computing resources.Report