Two Wrongs Sometimes Make a Right

The Problem

Suppose every letter below represents a distinct positive integer, non of which are zero. What is a possible value for each letter?

  W R O N G
+ W R O N G
-----------
  R I G H T

Solution Method

Since there are a limited number of solutions to this problem, we will take the naive approach and test every possible combination. Given a permutation of the digits 1-9 perm, assign each digit a letter as follows:

W = perm[0]
R = perm[1]
O = perm[2]
N = perm[3]
G = perm[4]
I = perm[5]
H = perm[6]
T = perm[7]

We then create 2 lists; one for [W,R,O,N,G] and one for [R,I,G,H,T]. For the example permutation of [1,2,3,4,5,6,7,8,9], these lists would be [1,2,3,4,5] and [2,6,5,7,8] respectively. Notice the digit 9 is unused. Adding the ninth digit and ignoring it makes computing permutations easier and still covers all cases. To test if the lists satisfies the equation, we convert each list of numbers into a single number [1,2,3] => 123 and then test if twice the wrong number is equal to the right number.

Solution in J

Table of all permutations

tap=: i.@! A. i.

This function computes a table of all permutations of the list [0, 1, .., N-1]. For example, for the input tap 3, the output would be the matrix:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

Test function

two_wrongs =: (((2&*) @: (10&#.)@:(5&{.)) = ((10&#.) @: (1 5 4 6 7 &{))) "1

This function is split into 3 main parts.

1. WRONG List

(2&*) @: (10&#.) @: (5&{.)
  1. 5&{. takes the first 5 elements of the list. i.e. [W,R,O,N,G]
  2. 10&#. converts the list into a number. For example [1,2,3] => 123
  3. 2&* multiplies the number by 2. (wrong+wrong)

2. RIGHT List

(10&#.) @: (1 5 4 6 7 &{)
  1. 1 5 4 6 7 &{ creates a list for the indices of [W,R,O,N,G]
  2. 10&#. converts the list into a number (see above)

3. Compare

((WRONG List) = (RIGHT List))

To to the final comparison, we use a monadic fork. In this case, our function will take the list as an input, apply it to each of the monadic right and wrong verbs. And finally use the dyadic = operator to compare each list.

Putting it all Together

8 {."1 ( two_wrongs # ] ) 1 + (tap 9)

First we create our permutation table with tap 9. Since the tap function generates permutations of the list [0,1,..,N-1] we must add one to each element of the list in order to permute on [1,2,..,9]. Next we filter the list using our test function with the code (two_wrongs # ]). Finally, since we only use the first 8 items of each list, we remove the last item from each list using 8{."1.

Result

We run the program to get the following output:

1 2 7 3 4 5 6 8
1 2 8 6 7 5 3 4
1 2 9 3 8 5 7 6
2 5 7 3 4 1 6 8
2 5 8 6 7 1 3 4
2 5 9 3 8 1 7 6
3 7 8 4 6 5 9 2

We can run the following code on this matrix result, to produce a better looking output

,./ ((< & ((5&{.,:5&{.)) ,: (<&(1 5 4 6 7 &{)))) "1 [ result

Output:

+---------+---------+---------+---------+---------+---------+---------+
|1 2 7 3 4|1 2 8 6 7|1 2 9 3 8|2 5 7 3 4|2 5 8 6 7|2 5 9 3 8|3 7 8 4 6|
|1 2 7 3 4|1 2 8 6 7|1 2 9 3 8|2 5 7 3 4|2 5 8 6 7|2 5 9 3 8|3 7 8 4 6|
+---------+---------+---------+---------+---------+---------+---------+
|2 5 4 6 8|2 5 7 3 4|2 5 8 7 6|5 1 4 6 8|5 1 7 3 4|5 1 8 7 6|7 5 6 9 2|
+---------+---------+---------+---------+---------+---------+---------+

There are 7 distinct solutions to the problem. Each of which is listed above.

The full source code is available here.