Group Therapy: Identify Groups
Ruby, 401 ... 272
f=->s{n=(s.size+1)**0.5
w=n.to_i-1
e=s[0,w].split''
s=s[w,n*n]
m={}
w.times{(1..w).each{|i|m[s[0]+e[i-1]]=s[i]}
s=s[n,n*n]}
s=e.find{|a|e.all?{|b|x=m[a+b]
x==m[b+a]&&x==b}}
e.all?{|a|t=!0
e.all?{|b|x=m[a+b]
t||=x==m[b+a]&&x==s
e.all?{|c|m[m[a+b]+c]==m[a+m[b+c]]}}&&t}&&s}
This is my first ruby program! This defines a lambda function that we can test by doing puts f[gets.chomp]. I return false for my false value. The first half of the function is simply parsing the input into a map, then the second half checks the possibilities.
f=->s{
n=((s.size+1)**0.5).to_i
w=n-1
e=s[0,w].split'' # create an array of elements of the potential group
s=s[w,n*n]
m={} # this map is what defines our operation
w.times{
(1..w).each{ # for each element in the row of the table
|i|m[s[0]+e[i-1]]=s[i] # put the value into the map
}
s=s[n,n*n]
}
s=e.find{|a| # s is the identity
e.all?{|b|
x=m[a+b]
x==m[b+a]&&x==b # is a the identity?
}
}
e.all?{|a| # implicit return statement
t = !0 # t = false
e.all?{|b| # check for inverses
x=m[a+b]
t ||= x==m[b+a]&&x==s # t is now true if b was a's inverse
e.all?{|c|
m[m[a+b]+c]==m[a+m[b+c]] # check associativity
}
} && t
}&&s
}
JavaScript (ES6) 285 243 278
Run snippet to test (being ES6 it works only on Firefox)
Edit 2 Bug fix. I was wrong in finding the neutral element, checking just one way. (Need better test cases!!!)
Edit Using simpler string concatenation instead of double index (like @Quincunx), I don't know what I was thinking. Also, simplified inverse check, it should still work.
F=t=>(
e=t.slice(0,d=Math.sqrt(t.length)|0),
t=t.slice(d).match('.'.repeat(d+1),'g'),
t.map(r=>{
for(v=r[i=0],
j=e.search(v)+1, // column for current row element
r!=v+e|t.some(r=>r[j]!=r[0])?0:n=v; // find neutral
c=r[++i];
)h[v+e[i-1]]=c
},h={},n=''),
e=[...e],!e.some(a=>e.some(b=>(
h[a+b]==n&&--d, // inverse
e.some(c=>h[h[a+b]+c]!=h[a+h[b+c]]) // associativity
)
))&&!d&&n
)input { width: 400px; font-size:10px }Click on textbox to test - Result : <span id=O></span><br>
<input value='...' onclick='O.innerHTML=F(this.value)'> (?)
<br>Groups<br>
<input value='nezdnnezdeezdnzzdneddnez' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk' onclick='O.innerHTML=F(this.value)'> (n)<br>
<input value='yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw' onclick='O.innerHTML=F(this.value)'> (y)<br>
<input value='01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0'onclick='O.innerHTML=F(this.value)'> (0)<br>
Non groups <br>
<input value='12345112345224153335421441532553214' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='123456711234567223167543312764544765123556714326645327177542316' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>
<input value='012300123113132210333333' onclick='O.innerHTML=F(this.value)'> (FAIL)<br>Octave, 298 290 270 265 chars
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
e=(isscalar(e=find(all(a==u')))&&a(e,:)==u&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);
265: Removed unnecessary function handle.
270: After all, the check that e==h for e always satisfying e·a=a and h always satisfying a·h=a was not necessary. This is not possible for them to be different (e·h=?).
The details from the explanation for solution below are still relevant.
290:
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);
The first line
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')'); just stores the input into n x n table (with zero character at the place of operation mark), and then lexicographically sorts columns and rows, so that rows and columns receive the same order:
+ | z a t b + | a b t z
----------- -----------
z | t b a z becomes a | t a z b
b | z a t b ============> b | a b t z
t | a z b t t | z t b a
a | b t z a z | b z a t
Now, I remap "a","b","t","z" to standard 1, 2, 3, 4 , so that I can index the table efficiently. This is done by the line for i=2:b a(a==a(i))=i-1;end;. It yields table like
0 1 2 3 4
1 3 1 4 2
2 1 2 3 4
3 4 3 2 1
4 2 4 1 3
, where we can get rid of the first row and column with a=a(2:b,2:b--);u=1:b;:
3 1 4 2
1 2 3 4
4 3 2 1
2 4 1 3
This table has the given properties:
- if the neutral element e exists, exactly one (
isscalar) row and one column have the value of row vectoru=[1 2 3 ... number-of-elements]:
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&...
if each element a has a reverse element a', two things hold: the neutral element e occurs only once each column and only once each row (
sum(t=a==e)==1) and, to satisfy a'·a = a·a', the occurences of e are symmetrical in respect to translationt==t'a·b can be retrieved by simple
t(a,b)indexing. Then we check the associativity in the boring loop:
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;
The function returns the neutral element the way it appeared in original table (e=d(e+1)) or nil character if the table does not describe a group.