22
\$\begingroup\$

Write a program or function that takes in a 4×4 text grid consisting of exactly 4 A's, 4 B's, 4 C's, and 4 D's, such as:

ACDC
BBCA
BADD
ABCD

The ABCD's may be in any arrangement but there will always be 4 of each. You can assume the input is valid. If desired you can also assume it has a trailing newline and/or that it comes as one line in reading order, e.g. ACDCBBCABADDABCD. You may also replace the characters ABCD with 0123 or 1234 respectively, if desired (but that's all).

Output a truthy value if the text grid has any form of reflective or rotational symmetry. Specifically:

  • If there is a central horizontal line of symmetry. e.g.

    BACD
    BACD 
    BACD \___ bottom mirrors top
    BACD /
    
  • If there is a central vertical line of symmetry. e.g.

    BCCB
    DAAD
    CAAC
    BDDB
      \/___ right mirrors left
    
  • If there is a diagonal line of symmetry (in either direction). e.g.

         ___ diagonally mirrored
        /
    ABDC
    BACD
    DCAB
    CDBA
        \___ diagonally mirrored
    
  • If there is 90° rotational symmetry. e.g.

    BDAB
    ACCD    same if rotated 90 degrees (or 180 or 270)
    DCCA
    BADB
    
  • If there is 180° rotational symmetry. e.g.

    DBCA
    BDCA    same if rotated 180 degrees
    ACDB
    ACBD
    

(Note that translational symmetry doesn't come into play here.)

Output a falsy value if the grid doesn't have one of the symmetries mentioned above. e.g. the very first example grid.

The shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can we take a list of four strings as input? \$\endgroup\$ – Martin Ender Aug 18 '16 at 8:11
  • \$\begingroup\$ @MartinEnder Yes, alright. \$\endgroup\$ – Calvin's Hobbies Aug 18 '16 at 8:13
  • 4
    \$\begingroup\$ I just read that and thought "nope" lol \$\endgroup\$ – Shaun Wild Aug 18 '16 at 8:22
  • \$\begingroup\$ Had you thought to tile the square then you could have taken translational symmetry into account too. \$\endgroup\$ – Neil Aug 18 '16 at 10:10
  • 1
    \$\begingroup\$ @Adám No. No more input formats. I feel I shouldn't really have allowed Martin's. \$\endgroup\$ – Calvin's Hobbies Aug 18 '16 at 12:31

10 Answers 10

16
\$\begingroup\$

CJam, 16 bytes

{{z_W%_}4*;])e=}

An unnamed block which expects the input as a list of four strings on top of the stack and leaves a 0 (falsy) for asymmetric inputs and a positive integer (truthy) for symmetric inputs.

Test it here. Or run a full test suite.

Explanation

The symmetries of the square are the elements of the dihedral group of order 8 (which are just the 4 rotations of the square and the same 4 rotations of some reflected version of the square). It's not possible to generate this group from repeated application of a single permutation. But two reflections always give some rotation. Hence, the entire group can be generated by alternating between two reflections four times. (We just need to make sure that the two reflections give the 90 degree or 270 degree rotation, not 0 or 180.)

The challenge asks whether the input square is equal to any of the other 7 symmetries. So this answer just generates all of them and then checks whether the input is among the others.

{      e# Run this block 4 times.
  z_   e# Transpose the grid and duplicate it. (This is one type of reflection.)
  W%_  e# Reverse the lines and duplicate it. (This is another type of
       e# reflection. Together they rotate the grid by 90 degrees.)
}4*    e# The last element will be the original grid again.
;      e# Discard one copy of that original grid.
]      e# Wrap all symmetries in a list.
)      e# Pull off the original grid.
e=     e# Count how many times it appears among the other symmetries.

To see how the repeated application of z and W% generates all symmetries, have a look at this "diagram":

     0123
     4567
     89ab
     cdef

     original

 z   048c       W%       37bf
-->  159d  ----------->  26ae
     26ae                159d
     37bf                048c

     diag. refl.         rot. 90 degrees ccw

 z   3210       W%       fedc
-->  7654  ----------->  ba98
     ba98                7654
     fedc                3210

     vert. refl.        rot. 180 degrees

 z   fb73       W%       c840
-->  ea62  ----------->  d951
     d951                ea62
     c840                fb73

     antidiag. refl.     rot. 270 degrees ccw

 z   cdef       W%       0123
-->  89ab  ----------->  4567
     4567                89ab
     0123                cdef

     horiz. refl.        original
\$\endgroup\$
  • \$\begingroup\$ Wow, can you explain this? Do you have a built-in for all rotations/flips? \$\endgroup\$ – Adám Aug 18 '16 at 8:25
  • \$\begingroup\$ @Adám I'll add a full explanation in a bit, but z is transpose and W% reverses the lines, so I'm just generating all symmetries by repeated application of those. \$\endgroup\$ – Martin Ender Aug 18 '16 at 8:30
  • 4
    \$\begingroup\$ There is, of course, nothing special about the first value, but sadly the more purist approach of counting whether you get 8 distinct values costs one char more. \$\endgroup\$ – Peter Taylor Aug 18 '16 at 10:54
8
\$\begingroup\$

Pyth, 11 bytes

<7.u?%Y2CN_

Test suite

This uses Martin's transpose and reverse technique, but with a twist. While other solutions have explicitly generated all 8 symmetries, then counted the number of appearances of the original, this program uses Pyth's .u function.

The .u function is the "Apply until repeat is found". In this case, we alternately transpose and reverse until a repetition happens, then accumulate the results into a list. Then, I remove the last 7 values, so there will only be a value remaining if there were no symmetries, and the first repetition happened after all 8 reflections and repetitions were generated.

Explanation:

<7.u?%Y2CN_
<7.u?%Y2CN_NQ    Implicit variables
                 Q = eval(input())
  .u        Q    Starting with Q, apply the following until a repeat occurs, 
                 then accumulate all values into a list.
    ?%Y2         If the iteration number is odd
        CN       Transpose
          _N     Else reverse
<7               Remove the last 7 results
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 13 bytes

4Fø€JÂD}\\)¹å

Explanation

Uses the method expertly explained by Martin in his CJam answer.

4F     }       # 4 times do:
  ø€J          # zip and join each
     ÂD        # bifurcate, duplicate
        \\     # delete the top 2 items on the stack
          )    # wrap stack in list
           ¹å  # check if input is in that list

Try it online

\$\endgroup\$
4
\$\begingroup\$

Perl, 61 60 bytes

Includes +3 for -p0a

Give input square on STDIN, prints 0 for no symmetry, otherwise some positive number

./symmetry.pl
DBCA
BDCA
ACDB
ACBD
^D

symmetry.pl:

#!/usr/bin/perl -p0a
s,.,chop$F[$i++/($j-4?1:4)%4],eg;$\+=$$_++;++$j<8&&redo}{
\$\endgroup\$
4
\$\begingroup\$

Dyalog APL, 37 19 17 bytes

@ngn reduced it by 20 bytes!

8>≢(∪⊢,⌽¨,⍉¨)⍣≡⊂⎕

TryAPL online!

\$\endgroup\$
  • \$\begingroup\$ ⍉¨ instead of ⌽∘⍉¨ works too. \$\endgroup\$ – ngn Aug 20 '16 at 23:16
  • \$\begingroup\$ @ngn Done. Thanks. See you tomorrow. \$\endgroup\$ – Adám Aug 21 '16 at 8:19
3
\$\begingroup\$

Brachylog, 38 36 bytes

@eL:1fbeL
(L;?:raL)(.;L$\.;L$/.;Lr.)

Try it online!

This expects a list of strings as input. This prints either true. or false..

Explanation

  • Main predicate:

    @eL    Split each line into a list of chars ; call that list of lists L
    :1f    Find all symmetries
    b      Remove the first one (the identity)
    eL     L is an element of that list of symmetries
    
  • Predicate 1: Output is one of the 8 symmetries of the input.

    (
        L             L = Input
    ;             Or
        ?:raL         L = reverse all lines of the input
    )
    (
        .             Output = L
    ;             Or
        L$\.          Output = transpose of L    
    ;             Or
        L$/.          Output = antitranspose of L
    ;             Or
        Lr.           Output = reverse of L
    )
    
\$\endgroup\$
3
\$\begingroup\$

TSQL, 229 bytes

Be aware TSQL has no build-in for rotating, so this is included in the code.

Golfed:

DECLARE @1 char(16)=
'BCCBDAADCAACBDDB'

,@i INT=0,@ varchar(16)=''WHILE @i<16SELECT @+=substring(@1,@i*4%16+@i/4+1,1),@i+=1SELECT sign(count(*))FROM(SELECT LEFT(x,8)a,RIGHT(x,4)b,substring(x,9,4)c FROM(values(@1),(@))x(x))x WHERE c+b=reverse(a)or a=reverse(b+c)or a=b+c

Ungolfed:

DECLARE @1 char(16)=
'BCCBDAADCAACBDDB'

,@i INT=0,@ varchar(16)=''
WHILE @i<16
  SELECT @+=substring(@1,@i*4%16+@i/4+1,1),@i+=1

SELECT sign(count(*))
FROM
  (SELECT LEFT(x,8)a,RIGHT(x,4)b,substring(x,9,4)c
   FROM(values(@1),(@))x(x))x
WHERE c+b=reverse(a)or a=reverse(b+c)or a=b+c

Fiddle

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

Python 2, 154 146 bytes

Checks if any of the necessary transformations is equivalent to the original using numpy arrays. Input is taken as a list of four strings.

from numpy import*
A=array(map(list,input()))
R=rot90
T=transpose(A)
print any([all(A==Z)for Z in(A[:,::-1],A[::-1],R(A),R(A,2),R(A,3),T,R(T,2))])

Try it online

Taking input as a single string is one char longer, with A=array(list(input())).reshape(4,4). A[:,::-1] is the same as fliplr(A). A[::-1] is the same as flipud(A).

\$\endgroup\$
  • \$\begingroup\$ Maybe use map(list,input()) instead of [list(r)for r in input()] \$\endgroup\$ – Cyoce Aug 18 '16 at 18:35
  • \$\begingroup\$ @Cyoce Thanks. Idk how I missed that. \$\endgroup\$ – mbomb007 Aug 18 '16 at 22:00
  • \$\begingroup\$ any takes a generator expression, so you can save a few bytes by dropping the outer pair of square brackets. \$\endgroup\$ – TheBikingViking Aug 19 '16 at 20:17
  • \$\begingroup\$ @TheBikingViking I had already tried that. If you pass a generator, then it returns a generator, making the print statement not work. Try forking my online code and running it that way to see. \$\endgroup\$ – mbomb007 Aug 19 '16 at 20:32
  • \$\begingroup\$ Ah, ok. I didn't realise that it would break the print. \$\endgroup\$ – TheBikingViking Aug 19 '16 at 20:36
2
\$\begingroup\$

Python 3, 99 bytes

def f(x):
 t=x;c=[]
 for i in range(7):*t,=[map(''.join,zip(*t)),t[::-1]][i%2];c+=t,
 return x in c

A function that takes input, via argument, of a list of strings and returns True or False as relevant.

This uses the same approach as @MartinEnder's answer.

How it works

def f(x)                Function with input list of strings x
 t=x;c=[]               Initilaise temporary square t and combination list c
 for i in range(7):...  For i in range [0,6]:
 [...][i%2]              If i is even:
 zip(*t)                  transpose(t)
 *t,=map(''.join,...)     t = t with each line concatenated (such that t is in the same
                          format as x)
                         Else:
 *t,=t[::-1]              t = reverse(t)
 c+=t,                   Append t to c
 return x in c           Return True if x is in c else return False

Try it on Ideone

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

JavaScript (ES6), 131 bytes

s=>[...`0101010`].map(c=>+c?``+b.reverse():`${b=b.map((s,i)=>s.replace(/./g,(_,j)=>b[j][i]))}`,b=a=s.match(/..../g)).includes(``+a)

17 bytes could be removed if you pass an array of 4 strings directly. I tried bit-twiddling (input in "0123301223011230" format) but that took me 199 bytes:

s=>[...'0101010'].map(c=>r=+c?r<<24&255<<24|r<<8&255<<16|r>>8&255<<8|r>>>24:r&0xc0300c03|r<<6&806093568|r<<12&3075<<16|r<<18&3<<24|r>>6&0xc0300c|r>>12&49200|r>>18&192,r=n=parseInt(s,4)|0).includes(n)
\$\endgroup\$

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.