7
2
This question is similar to Write a word equation solver by David Frank but different in three important ways: (1) David asked for just the first solution found, and I am asking for all the solutions. (2) I am asking to output the time required to solve the puzzle. And (3), it is a completely different undertaking to write a program designed to be fast compared with one designed to be short. A brute force method is probably best for code golf, but will not beat my ?amazing? time of 0.15 seconds. -I say "amazing" only to encourage other to try it out. I'm sure mine won't be the fastest.
(I'm going to copy a lot of the text from that question.)
Introduction
Consider the following example:
CODE
+ GOLF
——————
GREAT
This is an equation where each letter represents a decimal digit and the words represent natural numbers (similar letters represent similar digits and different letters represent different digits). The task is to match each letter with its digit value so that the equation is correct. One of the four solutions for the equation above is:
9265
+ 1278
——————
10543
Your task
Your task is to write a program or function to find ALL of the answers to such a word equation. Your program should output all the answers and the time it took to find them in seconds.
Input
The input will be something like this, two words added together to make a third word.
Example:
- CODE+GOLF=GREAT
- AA+BB=CC
Spaces are omitted and only letters between capital A and Z will be used (no special or small letters). This string can be read from the standard input, from a file, or as a function parameter.
Output
The output should look something like this. To take luck out of the competition, your program must list all the solutions.
time = XX.XXX seconds
(1) 9265+1278=10543
(2) 9275+1268=10543
(3) 9428+1437=10865
(4) 9438+1427=10865
Rules
- Similar letters represent similar digits and different letters represent different digits
- To make things easier, you can assume that numbers can or don't start with a leading zero, it's up to you. The four answers I got for the sample problem assume numbers do not start with leading zeros.
- You can use any language and the standard library of the chosen language (no external libs)
- You cannot connect to any resources on the internet (why would you anyways?)
- So the goal here is speed, but of coarse that depends on what computer you use. In order to account for the different speed of different computers, you could run my example on your computer and then report how many times faster or slower yours is than my sample answer.
- Please explain how your code works.
Example in JavaScript
JeffSB
Posted 2014-07-22T10:18:40.403
Reputation: 357
3For fairness, submissions to fastest-code challenges should all be tested on the same machine - which usually means your machine. Are you prepared to install all of those submissions on your own machine? Alternatively, another option might be to have everyone run your own solution and their own, the score being the ratio between the two. – Martin Ender – 2014-07-22T10:23:20.600
Also I think your example problem may be too small to accurately measure the timing for well-optimised solutions. You might want to provide a larger test case as the benchmark. – Martin Ender – 2014-07-22T10:24:27.773
The same question with a different winning criterion is a duplicate. (Even if the original question has a really stupid winning criterion).
– Peter Taylor – 2014-07-22T10:24:33.000@PeterTaylor I don't see how you read that into the answers of that meta question. What they say (and what the usual consensus is) is that it depends on whether answers from one challenge are competitive and valid solutions to the other. Seeing that the other one is code golf, I suspect that no solution will be optimised for efficiency (most of them will probably brute-force it). Hence, I'd say the difference in winning criterion is quite significant. – Martin Ender – 2014-07-22T10:27:14.097
@MartinBüttner, it's the plain meaning of the most voted answer, as further explained in Tyzoid's comment on his answer. – Peter Taylor – 2014-07-22T10:29:58.220
1@PeterTaylor Right, I didn't see his comment. I personally think (and I've seen answers along those lines on meta, too - and the comment with 3 upvotes is one of them) that we should take into account whether any submission from the original challenge would be competitive against new submissions which tackle the new challenge in a way according to the new winning criterion. If three optimised answers to this are posted, who would copy over a golfed brute force solution? I'm pretty sure to win this one, you do have to solve it in a novel way. – Martin Ender – 2014-07-22T10:34:52.333
3(Furthermore, copying a golfed submission into a fastest-code challenge comes very close to justifying a delete-vote for "This does not provide an answer to the question.") – Martin Ender – 2014-07-22T10:36:21.033
Hello Martin and Peter. I am very new to this. I can say that the answers for the code-golf question seemed to take many seconds or even minutes to run, and they did not find all the solutions. They just found one. The method I used in my example is pretty unique - I think. But then again my code golf answers are typically 5-10 times longer than the shortest ones. As for judging the speed of an algorithm, I would agree that it's approximate. – JeffSB – 2014-07-22T10:41:11.050
@MartinBüttner, even taking that view, I think this is one of the clearest cases: the scoring system on the other question is so badly exploitable that there's very little stopping an answer from scoring well on both that and speed. – Peter Taylor – 2014-07-22T10:42:10.610
2@PeterTaylor That's a fair point, although in that case I'd rather view the old one a duplicate of this one, as this here is definitely the more interesting challenge (answers to which can be submitted to the other one by encoding it in a whitespace string). One more thing about Tyzoid's opinion: there is a reasonable chance that his strong opinion and the upvotes were correlated to the fact that the two winning criteria in question were much more similar than code-golf vs fastest-code. – Martin Ender – 2014-07-22T10:45:09.823
Also, for comparison sake, my answer can be run on anyone's computer because it's JavaScript on a web page -not that this completely solves the problem. (I'll add a link to it.) – JeffSB – 2014-07-22T10:54:31.183
Can multiple letters have the same digit? or are there only a maximum of 10 different letters per equation. – Οurous – 2014-07-22T11:06:11.763
The "O" in GOLF and the "O" in CODE have the same value. This is what David meant by "Similar letters represent similar digits and different letters represent different digits." Also two different letters can not have the same value. – JeffSB – 2014-07-22T11:10:49.547
I adjusted rule number 5 to try to standardize the speed of different computers. You can answer in seconds if you want to be general/approximate, or you can answer as a factor of the sample answer if you want to be more precise. – JeffSB – 2014-07-22T11:14:33.253
Why not use most elegant solution? This is determine by popularity, also is applicable to each language. – Adam Speight – 2014-07-22T11:17:09.723
@JeffSB If I had ABCDEFGHIJK, only 10 of 11 letters would be able to be assigned digits. Would K have one of the previously assigned digits, or can there only be 10 letters? – Οurous – 2014-07-22T11:18:19.697
Adam, I'm fine with most votes. It's about the fun of it. – JeffSB – 2014-07-22T11:26:31.977
Ourous, You can only have ten different letters, but letters can be repeated. CODE+GOLF=GREAT has 13 letters, but only 10 unique letters - so it works. – JeffSB – 2014-07-22T11:28:04.137
@AdamSpeight Because why turn something into a popularity contest if you don't have to? (@JeffSB, please, please, stick to fastest code.) – Martin Ender – 2014-07-22T11:30:23.550
Okay, fastest code it is. – JeffSB – 2014-07-22T11:30:54.313
I inserted the 2nd paragraph to address the duplicate issue. – JeffSB – 2014-07-22T17:38:20.457