# Alex is sometimes right

This challenge is to lift the spirits of our mod Alex A., who is usually wrong.

Suppose you have a friend named Alex who needs help with basic logic and math, specifically mathematical equivalence.

He gives you a list of equations of the form [variable] = [variable] where a [variable] is always a single uppercase letter A to Z (not a lowercase letter, not a number, nor anything else). There's one equation per line in the list except for a single line that only says therefore.

All the equations above the therefore are premises, facts that are assumed to be true. All the equations below the therefore are unverified propositions, facts that Alex is attempting to infer from the premises, and they may or may not be true.

For example, in this equation list the single conclusionary proposition A = C happens to be true:

A = B
B = C
therefore
A = C


It's your job to tell Alex if all of his propositions logically follow from the given premises. That is, you need to tell Alex if he is wrong or right in his conclusions.

Write a program/function that takes in a string of a list of equations as described and prints/returns

Alex is right


if all the conclusions follow logically from the premises, and otherwise outputs

Alex is wrong


if any conclusion does not logically follow from the premises.

The shortest code in bytes wins.

Be sure to watch out for these cases:

• Variable always equals themselves. e.g.

B = A
therefore
A = A
X = X


results in Alex is right.

• Variables with unknown relationships cannot be assumed to be equal. e.g.

P = Q
therefore
E = R


results in Alex is wrong.

• When there are no equations after the therefore then the conclusions are vacuously true. e.g.

D = C
therefore

and

therefore

both result in Alex is right.

• When there are no equations before the therefore then only self-equality can be inferred. e.g.

therefore
R = R


results in Alex is right, but

therefore
R = W


results in Alex is wrong.

## More Examples

Alex is wrong cases: (separated by empty lines)

A = B
C = D
therefore
A = C

A = L
E = X
A = I
S = W
R = O
N = G
therefore
G = N
L = I
R = O
S = A
X = X
X = E

D = K
D = Q
L = P
O = L
M = O
therefore
K = L

A = B
therefore
B = C

Z = A
S = S
therefore
A = Z
A = A
S = A
A = S
Z = A
Z = A

K = L
K = X
therefore
X = P
L = X
L = P

therefore
A = B
B = C
A = C

therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
T = I
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z

A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = O
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
A = Z

therefore
C = D
T = Y
A = Z

P = Q
therefore
E = R

therefore
R = W

Alex is right cases:

H = J
therefore
J = H

K = L
K = X
therefore
L = X

C = B
B = A
therefore
A = B

K = L
K = X
K = P
therefore
L = X
L = P
X = P

A = Y
Y = Q
Q = O
therefore
O = Y
O = A

C = C
therefore
C = C

A = B
B = A
therefore
A = B
B = A

A = B
B = C
C = D
therefore
A = A
A = B
A = C
A = D
B = A
B = B
B = C
B = D
C = A
C = B
C = C
C = D
D = A
D = B
D = C
D = D

therefore
A = A
B = B
C = C
D = D
E = E
F = F
G = G
H = H
I = I
J = J
K = K
L = L
M = M
N = N
O = O
P = P
Q = Q
R = R
S = S
T = T
U = U
V = V
W = W
X = X
Y = Y
Z = Z

D = I
F = H
J = M
therefore
M = J
D = I
H = F

A = B
B = C
C = D
D = E
E = F
F = G
G = H
H = I
I = J
J = K
K = L
L = M
M = N
N = O
O = P
P = Q
Q = R
R = S
S = T
T = U
U = V
V = W
W = X
X = Y
Y = Z
therefore
Z = A
F = R
G = I
W = L

A = B
B = C
therefore
A = C

B = A
therefore
A = A
X = X

P = P
C = G
M = C
therefore

D = C
therefore

therefore

therefore
R = R
• PHP, 13 bytes Alex is wrong Verifies all test cases. – Dennis Oct 22 '15 at 18:48
• Hey, sometimes is better than never. ¯\_(ツ)_/¯ – Alex A. Oct 22 '15 at 20:00
• alex-is-wrong – Optimizer Oct 22 '15 at 20:06
• therefore\nTABS < SPACES --> Alex is right – Doorknob Oct 22 '15 at 20:51
• Love to see a solution in prolog. – azz Oct 24 '15 at 10:53

# CJam, 49

"Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?


Inspired from histocrat's Ruby solution. Try it online
3 bytes obliterated thanks to jimmy23013 :)

Explanation:

For each premise, the program replaces the first variable with the 2nd variable in the rest of the text. It then checks if there's any conclusion with different variables.

"Alex is "    first push the part we know
qN%           read the input and split into lines
S             push a space (initial no-op replacement string, see below)
{…}h          do-while
f{…}        for each line and the replacement string
)         take out the last character
er        replace the remaining character(s) with that character
(           afterwards, take out the first line
_el         duplicate and convert to lowercase
-           remove all the resulting characters from the line
this removes all lowercase letters and non-letters
"X = Y" becomes "XY" (new replacement string)
and "therefore" becomes "" (ending the loop)
this is the loop condition and is left on the stack every time
;             after the loop, pop the empty string (from "therefore")
{…},          filter the remaining (conclusion) lines using the condition block
)           take out the last character
#           find its index in the remaining string
this is 0 (false) iff the first character is the same as the last
afterwards, we have an array of lines with non-equal variables
"wrong"       push "wrong"
"right"       push "right"
?             choose "wrong" if the array was not empty, else choose "right"


Old version, 85

"Alex is "26,:A;{:i{{_A=_@-}g}%$~}:F;0q"= "-'t/Nf%~\{A\Ft:A;}/1>{F=}%-"right""wrong"?  This uses a union-find algorithm. Try it online • "Alex is "qN%S{f{)er}(_el-}h;{)#},"wrong""right"?. – jimmy23013 Oct 23 '15 at 16:01 • I just read that last line as ‘This uses a unicorn-find algorithm’ … waitwot? xD – Jan Oct 23 '15 at 20:26 • Alex is * wrong * right * ? – Charlie Oct 28 '15 at 20:44 # Ruby, 80 76 + 2 = 78 With command-line flags p0, run gsub$1,$2%p=$[/e/]while~/(.) = (?!\1)(.)/
$_="Alex is #{p ?:wrong: :right}"  Explanation: This uses pure string manipulation. p0 reads the full input as a single string into the variable $_. Then, we repeatedly match that string against the regular expression /(.) = (?!\1)(.)/, which finds all strings of the form "X = Y" where X and Y aren't the same letter, and assigns X to $1 and Y to$2. When such a match is found, gsub$1,$2 replaces all instances of X with Y in the string. We also check whether this match occurred before or after the "therefore" with

$[/e/]  If it occurred after, it's an unjustified claim and Alex is wrong. We track whether any such occurrences have happened using p=. The use of p as a tracking variable prevents things from breaking if the loop never hits even once, since p will return nil if it's never been assigned to. As of this post, the CJam solution is longer. A proud, if no doubt fleeting moment. Edit: Yup, quickly dethroned. Also, to finish the explanation, with the p flag the final value of $_ is output at the end of execution, so the last line is the output.

• The sweetest moments are those before one's solution is slaughtered by an esolang. – Alex A. Oct 22 '15 at 20:54
• The abuse of String#format to get both the gsub call and assignment into one expression is a pretty neat idea, +1! – Ventero Oct 23 '15 at 2:43

# CJam, 83756867 64 bytes

Thanks to Dennis for saving 1 byte.

"Alex is "q_elN--N/:$La/~{)-},\{__m*{:&},::^|}5*-"wrong""right"?  Test suite. The test cases are too long for a permalink, so simply copy them in from the question. Note that this is fairly slow - it takes a minute or two in the online interpreter. You can make it much faster by changing 5* to 2* in which case it will finish almost instantly and solve all but one test case. ## Explanation (Slightly outdated.) The idea is to do a sort of "flood fill" of possible equalities and then remove all the equalities we obtained from the conclusion list. It can be shown that we need no more than 5 steps of the flood fill, because those would cover a distance (in the initial graph of inequalities) of 25 = 32 but the maximum distance is 25. "Alex is " e# Push the string. q e# Read the input. _elN- e# Make a copy, convert to lower case, remove linefeeds. This gives us a string e# with all the characters we don't want from the input. - e# Remove them from the input. This leaves two upper-case letters on each line e# and an empty line between premises and conclusions. N/ e# Split into lines. La/ e# Split around the empty line. ~ e# Dump both halves on the stack. {)-}, e# Remove any "A = A"-type equalities from the conclusions. \ e# Swap with the premises. { e# Extend the premises 5 times... _Wf% e# Duplicate the premises and reverse each one, because = is symmetric. | e# Set union with the original premises. __m* e# Make two copies and get an array of every possible pair of premises. {:&}, e# Select those which have at least one character in common. ::^ e# For each such pair, take the mutual set difference, i.e. those characters e# that are in only one of the strings. | e# Set union with the original premises. }5* - e# Remove all the equalities we've obtained from the conclusions. If all e# conclusions were valid, the result will now be a empty array, which is falsy. ! e# Logical not. "wrong""right"? e# Select "wrong" or "right", respectively.  • Constructing the transitive closure, eh? I'm not familiar with CJam, but it seems like the 5th generation of equalities might only be generated in one direction. If they are, you'd need one more iteration to reverse those equalities. – user2357112 Oct 24 '15 at 0:36 • @user2357112 I believe they should be generated in both directions, because the first step adds all reverses of the input (or in the version that's golfed further, I sort all premise and conclusion equalities to begin with). – Martin Ender Oct 24 '15 at 0:42 • When you take the symmetric differences, though, do you get edges in both directions? (Or, in the further-golfed version, do the symmetric differences produce the edges in the needed direction?) – user2357112 Oct 24 '15 at 3:25 • @user2357112 Since I'm processing the entire Cartesian product, I will get each pair of equalities in both orderings, which will result in both orderings of the drawn conclusion (The only reason I need to reverse explicitly, or sort the initial input, is that the original premises are not necessarily generated in this process, so they are not reversed by taking the set differences of the Cartesian product). – Martin Ender Oct 24 '15 at 8:20 ## R, 183 192 bytes I have modified my answer to address a limitation pointed out by user2357112. There is still an extremely small probability of calling Alex out when he is in fact right (which itself does not seem to happen very often if I understand the context of the challenge :-). I hope he won't mind. i=grep("t",z<-scan(,"",,,"\n")) cat("Alex is",if(eval(parse(t=c(paste(LETTERS,"=",1:26),sample(rep(head(z,i-1),1e3)),paste(c(TRUE,sub("=","==",tail(z,-i))),collapse="&")))))"right"else"wrong")  I need to de-golf this a bit: lines = scan(, what = "", sep = "\n") therefore_idx = grep("therefore", lines) setup = paste(LETTERS, "=", 1:26) premises = sample(rep(head(lines, therefore_idx - 1), 1000)) propositions = paste(c(TRUE, sub("=", "==", tail(lines, -therefore_idx))), collapse = "&") things_to_evaluate = c(setup, premises, propositions) boolean_result = eval(parse(text = things_to_evaluate)) cat("Alex is", if (boolean_result) "right" else "wrong")  For example, if the input is A = B B = C therefore A = C B = C  it will first evaluate the setup: A = 1 B = 2 ... Z = 26  then the premises A = B B = C  will be run 1,000 times each in a random order. This is to make sure ("almost sure") that all equalities are propagated. Finally, it will evaluate the propositions: TRUE & A == B & B == C  • If the premises are A = B, B = C, C = A, the values just cycle around forever. 26 rounds of evaluation aren't enough. – user2357112 Oct 23 '15 at 5:22 • My failed logic... Thanks for the example, I'll have to work something else then. – flodel Oct 23 '15 at 11:34 • I think fixed it, or almost...! – flodel Oct 24 '15 at 1:01 # Haskell, 208 bytes import Data.Equivalence.Persistent c l=equate(l!!0)$last l
r=foldr(c)$emptyEquivalence('A','Z') l#r=equiv r(l!!0)$last l
f x|(h,_:t)<-span((<'t').head)$lines x="Alex is "++if all(#r h)t then"right"else"wrong"  I'm offloading the work to the Data.Equivalence.Persistent module, which provides functions for manipulating equivalence classes. All left to do is parsing the input and calling functions which sometimes have too long names for proper golfing. Usage example: *Main> f "A = B\nB = C\ntherefore\nA = C" "Alex is right" *Main> f "A = B\nB = D\ntherefore\nA = C" "Alex is wrong"  # Mathematica, 182 f[s_]:="Alex is "<>If[True===And@@Simplify[#2,#1]&@@(StringSplit[s,"\n"]/.{a___,"therefore",b___}:>StringSplit/@{{a},{b}}/.{x_,_,y_}:>Symbol[x<>"$"]==Symbol[y<>"$"]),"right","wrong"]  Works on string input, as per the challenge. In[]:= f["A = B B = C therefore A = C"] Out[]= Alex is right In[]:= f["D = K D = Q L = P O = L M = O therefore K = L"] Out[]= Alex is wrong  • You can lose 8 bytes by declaring f as a pure function, replacing Simplify[#2,#1] with #2~Simplify~#, and replacing StringSplit[s,"\n"] with #~StringSplit~"<actual newline>". – LegionMammal978 Oct 22 '15 at 21:27 • Good points! Also q=StringSplit; and then s/StringSplit/q/ for another 6 bytes or so saved. But in the end, this is not a good challenge for Mathematica I'm afraid, even though the logic character seemed a perfect fit. – user46060 Oct 22 '15 at 22:39 • Also, a___ and b___ can probably be changed to a__ and b__, and s=Symbol;. – LegionMammal978 Oct 22 '15 at 22:46 • a__ and b__ won't work if premises, propositions or both are empty though – user46060 Oct 22 '15 at 22:50 # Retina, 90 bytes To run, place the following 12 lines of code in 12 separate files (+11 bytes counted for each file beyond the first). <empty> designates an empty file; \n designates a literal newline. Alternately, keep the \ns as they are, put all lines in a single file, and use the -s option. Make sure that all files use literal newlines, not Windows \r\n, and note the space at the end of the last line. s+^(.) = (.)(.*)\1$1 = $2$3$2 )^. .+\n <empty> ^.+|(.) = \1 <empty> ^\n*$
right
^[^r]+
wrong
^
Alex is


How it works

The first replacement matches the first premise in the input, whenever the lhs of the premise occurs later on in the file. It replaces that later occurrence with the rhs of the premise. The + modifier ensures that the replacement is repeated until it doesn't match any more. Thus, if the first premise is A = B, all subsequent As in the file get transmuted into Bs.

The second replacement removes the first premise from the input, since we're done with it now. Then the ) modifier loops back to the first replacement, and repeats until there were no changes in a whole pass through the loop. This happens when all the premises have been substituted and removed, and the input starts with therefore.

The third replacement matches the first line of input (which is therefore) or anything of the form A = A, and deletes it. If all propositions are supported by the premises, all of them will match this form, so what remains should consist solely of newlines. The fourth replacement changes this into right. Otherwise, the fifth replacement changes everything remaining (which doesn't contain r since therefore was deleted) into wrong. Finally, the last replacement adds Alex is  at the beginning.

# Python 2, 264 bytes

There's already a remarkable Python 3 answer by mbomb007. This answer steals flagrantly from that one (in particular the "Alex is wrriognhgt" trick).

And this answer is also significantly longer than that one...

Well, anyway, the idea in this answer is to maintain a dictionary of key-value pairs, where the keys are the 26 capital letter characters, and each key's corresponding value is the set of letters that are equivalent to the key. (If all 26 letters were equivalent, then each key would have a set of 26 letters for its corresponding value.)

def a(s):
d={C:set(C)for C in map(chr,range(65,91))};p,c=s.split('t');c,p=[x.split('\n')for x in[c[9:],p]]
for u in p[:-1]:
g,h=u[::4];y=d[g]|d[h]
for v in y:
for w in y:d[v]|=d[w];d[w]|=d[v]
print'Alex is','wrriognhgt'[all(uin d[u]for u in c if u)::2]


(To save bytes, this answer mixes spaces and tabs, which is legal in Python 2.)

This code is really pretty efficient, because the dictionary is limited to a maximum possible size (26 by 26 as described above) which doesn't depend on the number of lines of input.

Now, as I was golfing this solution, I realized that I could save four bytes by using strings instead of sets for the dictionary values, by replacing

d={C:set(C)for C in map(


with

d={C:C for C in map(


Of course then you also have to replace (NOTE: DON'T DO THIS) the three instances of the set union operation | with string concatenation +, but that doesn't change the code length. The result is that everything should still work just the same, except it won't eliminate duplicates like you do with sets (it'll just keep adding onto the end of the string). Sounds OK--a little less efficient, sure, but 260 bytes instead of 264.

Well, it turns out that the 260-byte version is so inefficient that it caused a MemoryError when I tested it with

A = B
A = B
therefore
B = A


This was surprising to me. Let's investigate the 260-byte "string concatenation" version!

Of course it would start out with the key-value pairs A:A and B:B (plus 24 others that don't matter). We'll write d[A] to mean the dictionary value corresponding to the key A, so at the beginning we'd have d[A] = A. Now, given the premise A = B, it would start by concatenating the values d[A]=A and d[B]=B to get y = AB. Then it'd loop over this string twice: for v in AB: for w in AB:...

So, the first time through the loop, we have v=A and w=A. Applying d[v] += d[w] and d[w] += d[v] results in the following sequence of dictionaries:

{A:A, B:B}      (start)
{A:AA, B:B}     (d[A] += d[A])
{A:AAAA, B:B}     (d[A] += d[A])


Next, with v=A and w=B:

{A:AAAA, B:B}     (start)
{A:AAAAB, B:B}    (d[A] += d[B])
{A:AAAAB, B:BAAAAB}   (d[B] += d[A])


Next, v=B, w=A:

{A:AAAAB, B:BAAAAB}   (start)
{A:AAAAB, B:BAAAABAAAAB}     (d[B] += d[A])
{A:AAAABBAAAABAAAAB, B:BAAAABAAAAB}     (d[A] += d[B])


And v=B, w=B:

{A:AAAABBAAAABAAAAB, B:BAAAABAAAAB}     (start)
{A:AAAABBAAAABAAAAB, B:BAAAABAAAABBAAAABAAAAB}     (d[B] += d[B])
{A:AAAABBAAAABAAAAB, B:BAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB}     (d[B] += d[B])


The above sequence of steps would implement the single premise A = B, with the conclusion that A is equal to every letter in the string AAAABBAAAABAAAAB, while B is equal to every letter in BAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB.

Now, suppose that the next premise is A = B again. You first calculate y = d[A] + d[B] = AAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAABBAAAABAAAAB.

Next, you loop over this string twice: for v in y: for w in y:...

Yeah. Maybe that wouldn't be a very efficient implementation.

• My answer isn't "great" since it's invalid, but it was a noteworthy attempt. Too bad I couldn't get it to work. – mbomb007 Oct 26 '15 at 20:34
• @mbomb007 Huh, I'm sorry to hear that. (I did think you had a cool approach!) Since you objected to the word "great", I have substituted "remarkable". :) – mathmandan Oct 27 '15 at 18:14

# ES6, 128 bytes

Loosely based on the Ruby version.

r=s=>(m=/^[^e]*(.) = (?!\1)(.)/.exec(s))?r(s.replace(RegExp(m,'g'),m)):'Alex is '+(/(.) = (?!\1)/.test(s)?'wrong':'right')


Looks for any non-self-equality before the "therefore" and recurisvely replaces the variable throughout the string each time (this saves bytes over a while loop).

# C, 240 bytes

#define V[v-65]
v;char*r[]={"wrong","right"};i=65;j;g(a){return a V^a?g(a V):a;}main(){char b;for(;i<91;++i)i V=i;while(gets(b)&&*b<99)bV=bV=bV<bV?bV:bV;while(gets(b))j|=g(*b)^g(b);printf("Alex is %s\n",r[!j]);}


This works by combining values into set trees, so any equivalent values lead to the same set root. Ungolfed, with implicit types made explicit.

// Anything before V becomes an index into v, offset by -'A'.
#define V [v-65]
int v;
char* r[] = {"wrong", "right"};
int i=65;
int j;
// Finds a set identifier for a by recursing until some index points to itself.
int g(int a) {
return a V ^ a
? g(a V)
: a;
}
int main() {
char b;
// Initialize all entries to point to themselves.
for(; i < 91; ++i)
i V = i;
// For each premise "A = B", set the entries for A and B to point to the
// smaller of their current values. This exits after reading "therefore"
// as 't' > 99.
while (gets(b) && *b < 99)
bV = bV = bV < bV
? bV
: bV;
// For each conclusion "A = B", OR j with non-zero if the set identifiers
// for A and B are different.
while (gets(b))
j |= g(*b) ^ g(b);
printf("Alex is %s\n", r[!j]);
}


# 180 bytes

This shorter version works for all cases from the OP, but for some other inputs incorrectly claims Alex is wrong. It uses a similar approach, but for each premise simply sets the second entry to the current value of the first entry. When comparing, it looks only at exact values instead of searching up a tree.

v;*V=v-65;char*r[]={"wrong","right"};i;j;main(){char b;for(;i<26;++i)v[i]=i;while(gets(b)&&*b<99)V[b]=V[*b];while(gets(b))j|=V[*b]^V[b];printf("Alex is %s\n",r[!j]);}


An example input for which this fails:

A = B
C = B
therefore
A = C