Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If you've read the book Contact by Carl Sagan, this challenge may seem familiar to you.


Given an input of a set of mathematical equations consisting of a number, an unknown operator, another number, and a result, deduce which operators represent addition, subtraction, multiplication, or division.

Each input equation will always consist of

  • a non-negative integer
  • one of the letters A, B, C, or D
  • another non-negative integer
  • the character =
  • a final non-negative integer

concatenated together. For example, a possible input is 1A2=3, from which you can deduce that A represents addition. Each of the integers will satisfy 0 ≤ x ≤ 1,000.

However, it's not always as simple as that. It is possible for there to be ambiguity between:

  • 5A0=5: addition/subtraction
  • 1A1=1: multiplication/division
  • 0A5=0: multiplication/division
  • 2A2=4: addition/multiplication
  • 4A2=2: subtraction/division
  • 0A0=0: addition/subtraction/multiplication

and so on. The challenge is to use this ability to narrow down choices, combined with process of elimination, to figure out what operator each letter represents. (There will always be at least one input equation, and it will always be possible to unambiguously, uniquely match each letter used in the input with a single operator.)

For example, let's say the input is the following equations:

  • 0A0=0: this narrows A down to addition, subtraction, or multiplication (can't divide by 0).
  • 10B0=10: B has to be either addition or subtraction.
  • 5C5=10: C is obviously addition, which makes B subtraction, which makes A multiplication.

Therefore, the output for these input equations should match A with *, B with -, and C with +.

Input may be given as either a single whitespace-/comma-delimited string or an array of strings, each representing one equation. Output may be either a single string ("A*B-C+"), an array (["A*", "B-", "C+"]), or a dictionary / dict-like 2D array ({"A": "*", ...} or [["A", "*"], ...]).

You may assume that a number will never be divided by another number it isn't divisible by (so, you don't need to worry about whether division should be floating point or truncated).

Since this is , the shortest code in bytes wins.

Test cases:

In                       Out
-------------------------------
0A0=0 10B0=10 5C5=10     A*B-C+
100D100=10000            D*
4A2=2 4B2=2 0A0=0        A-B/
15A0=15 4B2=2 2C2=0      A+B/C-
1A1=1 0A0=0              A*
0A0=0 2A2=4 5B0=5 2B2=4  A*B+
2A2=4 0C0=0 5B0=5 5A0=5  A+B-C*
0A1000=0 4A2=2           A/
share|improve this question
1  
Are we doing (truncated) integer division? – Martin Ender Jan 21 at 22:16
    
@MartinBüttner You can assume that there will never be division by a number that doesn't result in an integer. (Edited into question.) – Doorknob Jan 21 at 22:18
    
Can we output as a dictionary? – lirtosiast Jan 21 at 22:26
    
@ThomasKwa Sure, a dictionary is also acceptable output. – Doorknob Jan 21 at 22:30
    
Most of the examples are inconsistent with "it will always be possible to unambiguously, uniquely identify which letter stands for which operator", although they are consistent with "it will always be possible to unambiguously identify which operator is represented by each letter used in the input". – Peter Taylor Jan 21 at 22:58
up vote 9 down vote accepted

MATL, 53 bytes

j61tthYX'+-*/'X{Y@!"t'ABCD'!XKX{@YXU?K@Y}hwxKGm1L3$).

Uses current version (10.1.0)

Try it online!

Explanation

This tests all possible permutations of the four operators in a loop until one permutation makes all equations true.

To test if equations are true, a regex is applied to replace the four letters by the operators (in the order dictated by the current permutation), and the string is converted to numbers (evaluated). This gives an array with as many numbers as equations, in which equations that are true become 1 and equations that are false become 0. If this vector only contains 1 values, we're done.

The solution found assigns operators to the four letters, but not all of them necessarily appear in the input. So a final test is done to discard not used letters (and their matching operators).

j            % input data string
61           % '=' (ASCII)
tth          % duplicate twice and concat: '==' (ASCII)
YX           % regexprep to change '=' into '==' in input string
'+-*/'       % push string
X{           % transform into cell array {'+','-','*','/'}
Y@!          % all permutations, each in a column
"            % "for" loop. Iterate columns (that is, permutations)
  t          %   duplicate data string containing '=='
  'ABCD'!XK  %   create column array ['A';'B';'C';'D'] and copy to clipboard K
  X{         %   transform into column cell array {'A';'B';'C';'D'} 
  @          %   push column cell array with current permutation of operator symbols
  YX         %   regexprep. Replaces 'A',...,'D' with current permutation of operators
  U          %   convert to numbers, i.e. evaluate string
  ?          %   if all numbers are 1 (truthy result): found it! But before breaking...
    K        %     push column array ['A';'B';'C';'D']
    @Y}      %     push column array with current permutation of operator symbols
    h        %     concatenate horizontally into 4x2 char array
    wx       %     delete original input so it won't be displayed
    K        %     push ['A';'B';'C';'D']
    G        %     push input string
    m        %     logical index that tells which of 'A',...,'D' were in input string
    1L3$)    %     apply that index to select rows of the 4x2 char array
    .        %     we can now break "for" loop
             %   implicitly end "if"
             % implicitly end "for"
             % implicitly display stack contents
share|improve this answer

Python, 278 characters

My first answer on code golf...

It is just a function implementing a brute force algorithm, you call it passing as argument the string of equations.

from itertools import *
def f(s):
    l=list("ABCD")
    for p in permutations("+-*/"):
        t=s
        for v,w in zip(l+["="," "],list(p)+["=="," and "]):
            t=t.replace(v, w)
        try:
            o=""
            if eval(t):
                for c,r in zip(l,p):
                    if c in s:
                        o+=c+r
                return o
        except:
            pass
share|improve this answer
    
I'm not sure if it works, but can you replace ["A","B","C","D"] with list("ABCD")? – Adnan Jan 21 at 23:37
    
What @Adnan suggested does indeed work. You can also remove the spaces around = in the definition of l. – Alex A. Jan 21 at 23:40
    
@Adnan and Alex A. thanks, I edited the code. – Bob Jan 21 at 23:48
    
Here's 257 bytes for the same approach, plus an online testing environment. – Alex A. Jan 21 at 23:50
    
Made some changes - repl.it/BfuU. You can cut a lot of bytes more by picking a different output format. This solution only works on python 3 btw (4A2=2 4B3=1). – Nabb Jan 22 at 7:30

JavaScript (ES6), 213 208 bytes

f=(l,s="+-*/",p="",r)=>s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Explanation

Input and output are strings.

Defines a function f which doubles as a recursive function for generating all the permutations of the operators and tests complete permutations with the input equations using eval.

f=(
  l,                          // l = input expression string
  s="+-*/",                   // s = remaining operators
  p="",                       // p = current permutation of operators
  r                           // r is here so it is defined locally
)=>
  s?                          // if there are remaining operators
    [...s].map(o=>            // add each operator o
      r=f(
        l,
        s[g="replace"](o,""), // remove it from the list of remaining operators
        p+o                   // add it to the permutation
      )
        ||r                   // r = the output of any permutation (if it has output)
    )
    &&r                       // return r
  :                           // else if there are no remaining operators
    l.split` `.every(x=>      // for each expression
      (q=x.split`=`)          // q = [ equation, result ]
      [1]==eval(              // if the results is equal to the eval result

        // Replace each letter with the current permutation
        q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])
      )
    )

    // If all results matched, add permutation symbols to present characters and return
    &&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

Test

Test does not use default arguments for browser compatibility.

var solution = f=(l,s,p,r)=>s==null&&(s="+-*/",p="",0)?0:s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")
<input type="text" id="input" value="2A2=4 0C0=0 5B0=5 5A0=5" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.