17
\$\begingroup\$

Write a program, that determines whether the multiplication table of the given finite magma represents a group. A magma is a set with a binary operation that is closed, that means

  • for all a,b in G, a*b is again in G (Closedness)

Let (G, * ) be a magma. (G, * ) is a group if

  • for all a,b,c in G, (a*b) * c = a * (b*c) (Associativity)
  • there exists an element e in G such that e * a = a * e = a for all a in G (Existence of neutral Element)
  • for all a in G there is a b in G such that a * b = b * a = e where e is the neutral element (Existence of Inverse)

Specs

The input is of a string of n^2-1 characters (one character for each element of the magma, allowed are 0-9,a-z) and just represents the table read row by row, ommiting the operator name. You can assume that the input represents a valid magma (that means each of the elements appers exactly once in the header row/colum).

Example: Here we have the table of Z_4

+ | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 2 3 0
2 | 2 3 0 1
3 | 3 0 1 2

The input string will be 012300123112302230133012. (Or if we use symbols it could also be nezdnnezdeezdnzzdneddnez). Be aware that the sequence of the elements in the row and in the column do not have to be the same, so the table of Z_4 could also look like so:

+ | 1 3 2 0
-----------
1 | 2 0 3 1
0 | 1 3 2 0
2 | 3 1 0 2
3 | 0 2 1 3

This also means that the neutral element is not necessarily in the first column or first row.

If it is a group, the program has to return the character representing the neutral element. If not it has to return a falsy (distinct from the values 0-9 a-z) value

Test cases

Non-groups can easily be constructed by just altering one digit of the string or by artificially altering the tables defining a operation that contradicts one of the group axioms.

Groups

Trivial

* | x
-----
x | x

xxx

Neutral Element: x

H (quaternion group)

* | p t d k g b n m 
-------------------
m | b d t g k p m n 
p | m k g d t n p b 
n | p t d k g b n m 
b | n g k t d m b p 
t | g m n p b k t d 
d | k n m b p g d t 
k | t b p m n d k g 
g | d p b n m t g k 

ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk

Neutral Element: n

D_4

* | y r s t u v w x
-------------------
u | u x w v y t s r
v | v u x w r y t s
w | w v u x s r y t
x | x w v u t s r y
y | y r s t u v w x
r | r s t y v w x u
s | s t y r w x u v
t | t y r s x u v w


yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw

Neutral Element: y

Z_6 x Z_2

x | 0 1 2 3 5 7 8 9 a b 4 6
---------------------------
0 | 0 1 2 3 5 7 8 9 a b 4 6 
1 | 1 2 3 4 0 8 9 a b 6 5 7 
2 | 2 3 4 5 1 9 a b 6 7 0 8 
7 | 7 8 9 a 6 2 3 4 5 0 b 1 
8 | 8 9 a b 7 3 4 5 0 1 6 2 
9 | 9 a b 6 8 4 5 0 1 2 7 3 
a | a b 6 7 9 5 0 1 2 3 8 4 
b | b 6 7 8 a 0 1 2 3 4 9 5 
3 | 3 4 5 0 2 a b 6 7 8 1 9 
4 | 4 5 0 1 3 b 6 7 8 9 2 a 
5 | 5 0 1 2 4 6 7 8 9 a 3 b 
6 | 6 7 8 9 b 1 2 3 4 5 a 0 

01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0

Neutral Element: 0

A_4

* | i a b c d e f g h j k l
---------------------------
i | i a b c d e f g h j k l
a | a b i e c d g h f l j k
b | b i a d e c h f g k l j
c | c f j i g k a d l b e h
d | d h k b f l i e j a c g
e | e g l a h j b c k i d f
f | f j c k i g d l a h b e
g | g l e j a h c k b f i d
h | h k d l b f e j i g a c
j | j c f g k i l a d e h b
k | k d h f l b j i e c g a
l | l e g h j a k b c d f i

iabcdefghjkliiabcdefghjklaabiecdghfljkbbiadechfgkljccfjigkadlbehddhkbfliejacgeeglahjbckidfffjckigdlahbegglejahckbfidhhkdlbfejigacjjcfgkiladehbkkdhflbjiecgalleghjakbcdfi

Neutral Element: i

Non-Groups

A loop (Group missing associativity, or a Quasi-Group with neutral element)

* | 1 2 3 4 5
-------------
1 | 1 2 3 4 5 
2 | 2 4 1 5 3 
3 | 3 5 4 2 1 
4 | 4 1 5 3 2 
5 | 5 3 2 1 4

12345112345224153335421441532553214

Neutral Element: 1
(2*2)*3 = 4*3 = 5 != 2 = 2*1 = 2*(2*3)

An IP-loop (from http://www.quasigroups.eu/contents/download/2008/16_2.pdf)

* | 1 2 3 4 5 6 7
-----------------
1 | 1 2 3 4 5 6 7
2 | 2 3 1 6 7 5 4
3 | 3 1 2 7 6 4 5
4 | 4 7 6 5 1 2 3
5 | 5 6 7 1 4 3 2
6 | 6 4 5 3 2 7 1
7 | 7 5 4 2 3 1 6

123456711234567223167543312764544765123556714326645327177542316

Neutral Element: 1
2*(2*4) = 2*6 = 5 != 7 = 3*4 = (2*2)*4

Monoid (by Quincunx, thanks!)

Monoids are Magmas with associativity and a neutral element.

* | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 3 1 3
2 | 2 1 0 3
3 | 3 3 3 3

012300123113132210333333

Neutral Element: 0

Another Monoid

(Multiplication mod 10, without the 5) We obviously do not have inverses, and the associativity is given by the multiplication modulo 10.

* | 1 2 3 4 6 7 8 9
-------------------
1 | 1 2 3 4 6 7 8 9
2 | 2 4 6 8 2 4 6 8
3 | 3 6 9 2 8 1 4 7
4 | 4 8 2 6 4 8 2 6
6 | 6 2 8 4 6 2 8 4
7 | 7 4 1 8 2 9 6 3
8 | 8 6 4 2 8 6 4 2
9 | 9 8 7 6 4 3 2 1

Neutral Element: 1   12346789112346789224682468336928147448264826662846284774182963886428642998764321
\$\endgroup\$
  • \$\begingroup\$ Thought I'd add another table, much bigger, just for fun: ideone.com/823aRG \$\endgroup\$ – Justin Apr 19 '15 at 7:21
  • \$\begingroup\$ Just for fun, here's another really big one that breaks the 0-9a-z rule: ideone.com/vC0ewt \$\endgroup\$ – Justin Apr 19 '15 at 7:37
  • \$\begingroup\$ For one that knows nothing about groups,magmas and so on, the specs are fuzzy. For instance, are operations commutative? (so the table is redundant). Moreover. the position of neutral in first row is not related to having the same order in row and column: with 10101010 the order is the same and the neutral is in the last row and column \$\endgroup\$ – edc65 Apr 19 '15 at 9:40
  • \$\begingroup\$ @edc Groups are not necessarily commutative (commutative groups are called abelian). The definition of the a group is complete (it is the usual definition), anything additional would provide further restriction. In those tables the multiplication with the neutral element is usually in the first row/column, and the sequence of the elements of the header row/column are usually the same, but you can still write down a valid table without following those conventions, which is what I wanted to include here. \$\endgroup\$ – flawr Apr 19 '15 at 10:12
  • 1
    \$\begingroup\$ I deleted some comments which appeared to be obsolete. Please notify me of any comments that should be undeleted. \$\endgroup\$ – Martin Ender Apr 19 '15 at 20:08
4
\$\begingroup\$

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 vector u=[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 translation t==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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Well done and well explained. Should return the neutral element instead of 1. \$\endgroup\$ – edc65 Apr 19 '15 at 20:35
  • \$\begingroup\$ Corrected, now returns proper value. \$\endgroup\$ – pawel.boczarski Apr 19 '15 at 21:27
  • 1
    \$\begingroup\$ OCTAVE FTW=) I am not sure about two things (coming from matlab), but perhaps you can use it to improve your answer: Could ` a(f(a==a(i)))=i-1` be reduced to a(a==a(i))=i-1? Other than that you can perhaps use (...)^.5 instead of sqrt(...). \$\endgroup\$ – flawr Apr 19 '15 at 21:38
  • \$\begingroup\$ @flawr Thanks, they both work in octave (version 3.8.1). \$\endgroup\$ – pawel.boczarski Apr 19 '15 at 22:01
6
\$\begingroup\$

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
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to the wonders of golfing in Ruby! ;) nil is a shorter falsy value than false. Functions can be defined as lambdas like q=->{abort'false'} (if they take parameters, then use [] to call them instead of ()). I believe .chars should already give you an array, so no need for .to_a. If you don't need a trailing newline $><< is one byte shorter than puts plus space. Hash.new doesn't need the parentheses. That's all I can see for now. Keep it up! ;) \$\endgroup\$ – Martin Ender Apr 19 '15 at 2:08
  • \$\begingroup\$ The chars thing is odd. What version of Ruby are you using? \$\endgroup\$ – Martin Ender Apr 19 '15 at 2:13
  • \$\begingroup\$ @MartinBüttner 1.9.3 \$\endgroup\$ – Justin Apr 19 '15 at 2:16
  • \$\begingroup\$ Ah, right, I've been looking at the documentation of 2.1.5. \$\endgroup\$ – Martin Ender Apr 19 '15 at 2:16
  • 1
    \$\begingroup\$ You can replace Math.sqrt(...) with ...**0.5. Also, a if b can be rewritten: b&&a to avoid the two spaces \$\endgroup\$ – Cristian Lupascu Apr 19 '15 at 19:17
4
\$\begingroup\$

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>

\$\endgroup\$
2
\$\begingroup\$

Haskell 391B

import Data.Maybe
import Data.List
o a b=elemIndex b a
l£a=fromJust.o a$l
a§b=[a!!i|i<-b]
f s|isJust j&&and(map(isJust.o h)s)&&and[or[p%q==e|q<-h]&&and[p%(q%r)==(p%q)%r|q<-h,r<-h]|p<-h]=[e]|True="!"where n=floor$(sqrt(fromIntegral$length s+1))-1;h=take n s;g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]];v=s§[n,1+2*n..n+n*n];a%b=g!!(b£v)!!(a£h);j=o g h;e=v!!fromJust j

Curse those imports!

import Data.Maybe
import Data.List

{- rename elemIndex to save characters -}
o a b=elemIndex b a

{- get the index of l in a -}
l£a=fromJust.o a$l

{- extract a sublist of a with indices b -}
a§b=[a!!i|i<-b]

f s |isJust j {-Identity-}
     &&and (map (isJust.o h) s) {-Closure-}
     &&and[
        or [p%q==e|q<-h] {-Inverse-}
        && and [ p%(q%r)==(p%q)%r | q<-h,r<-h ] {-Associativity-}
     |
        p<-h
     ]=[e]
    |True="!"
    where
    {-size-}    n=floor$(sqrt(fromIntegral$length s+1))-1
    {-horiz-}   h=take n s
    {-table-}   g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]]
    {-vert-}    v=s§[n,1+2*n..n+n*n]
    {-operate-} a%b=g!!(b£v)!!(a£h)
                j=o g h {-index of the first row identical to the top-}
    {-ident-}   e=v!!fromJust j

Explanation

f::String->String maps the string to either e::Char, the identity element, or !.

The where clause creates a bunch of variables and functions, which I've commented; v::[Int] is the vertical list of elements, h::[Int] the horizontal one.

%::Char->Char->Char applies the group operation to its arguments.

g::[[Int]] is the group table (for dereferencing using %)

j::Maybe Int contains the index of the identity in v if it exists, otherwise Nothing, which is why isJust j is the condition in f for identity.

\$\endgroup\$
  • \$\begingroup\$ Can you explain a little bit what is going on here? \$\endgroup\$ – xebtl Apr 22 '15 at 14:59
  • \$\begingroup\$ I've added a few comments, but the basic gist is 'apply the tests to the group table'. Note that {- -} is a comment. Do you have any more specific questions, or does that clear it up? \$\endgroup\$ – alexander-brett Apr 22 '15 at 15:31
  • \$\begingroup\$ Thanks. I guess to really understand it I would need to learn some Haskell first :-) \$\endgroup\$ – xebtl Apr 22 '15 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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