14
\$\begingroup\$

Here are all the 2x2 binary matrices

#0  #1  #2  #3  #4  #5  #6  #7  #8  #9  #10 #11 #12 #13 #14 #15
--  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  
00  00  00  00  01  01  01  01  10  10  10  10  11  11  11  11  
00  01  10  11  00  01  10  11  00  01  10  11  00  01  10  11  

Two binary square matrices are equivalent under the relation ~ if one can be mapped onto the other by any number of reflections in the horizontal or vertical axes.

#1 ~ #2 under reflection in the vertical axis so we only need to keep one of these (it doesn't matter which). Likewise #3 ~ #12, #6 ~ #9 and so on.

THE GOAL is to produce a program which takes a single input N and prints as many N x N binary matrices as exist such that all matrices in the output are distinct under the above relation.

In hand-wavey pseudocode, an admissible solution would be

define M[i] = N by N matrix with bit pattern equal to i

for i = 0 to (2^(N^2)) - 1
    valid = true
    for j = i+1 to (2^(N^2)) - 1
        if (equivalent(M[i], M[j]))
            valid = false
            break
    if (valid)
        print (M[i])

For the input N=2 one valid output would be

00  00  00  01  10  01  11
00  01  11  01  01  11  11

But by selecting different matrices from the same equivalence class another valid output would be

00  10  11  11  11  10  01
00  00  00  10  11  10  10

The order of matrices doesn't matter, the particular choice from equivalent matrices doesn't matter, and whitespace doesn't matter, output the matrices however you like as long as it's human-readable.

The output must be exhaustive.

Shortest code wins.

EDIT: this is my first golf post and I've changed my mind on the winning criteria.

Shortest code in a language not specifically designed for conciseness/golfing wins.

I hope it's not bad etiquette to change this criterion post-hoc, but I think doing it in a "normal" language is a much more interesting proposition.

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to PPCG! This is a nice first challenge, but I'd recommend letting people output the result in a flexible format (e.g. each matrix as a list of lists). That way people can focus on the very interesting core of the challenge (finding the unique matrices up to symmetries) instead of also having to worry about formatting the output (which could easily take just as many bytes and make the golfing of the main challenge less important). \$\endgroup\$ – Martin Ender Oct 4 '16 at 20:38
  • \$\begingroup\$ Thanks for the feedback, both of you, I have edited the question accordingly. \$\endgroup\$ – spraff Oct 4 '16 at 21:07
  • 2
    \$\begingroup\$ I was tempted to include rotations as an equivalence. I was also tempted to include inverting each bit as an equivalence. I was also tempted to include permutations of rows/columns as an equivalence. In the end, I made an arbitrary decision to keep the requirements fairly simple. Feel free to post a variation. \$\endgroup\$ – spraff Oct 5 '16 at 13:38
  • 1
    \$\begingroup\$ We've discussed this in the past and ruled against excluding or penalizing certain languages in code golf competitions, meaning that challenge that do so should be considered off topic. Furthermore, the accepted answer is the answer that wins the challenge, which means shortest code for code golf questions. Summarizing: If you don't want to accept any answer at all, then don't. However, if you accept an answer, it has to be the shortest one. \$\endgroup\$ – Dennis Oct 6 '16 at 18:47
  • 1
    \$\begingroup\$ Finally, the J language is not a golfing language, but a high-level, general-purpose, high-performance programming language that has existed for 25 years. Even with your current rules, you've still accepted the wrong answer. \$\endgroup\$ – Dennis Oct 6 '16 at 18:50
1
\$\begingroup\$

J, 66 56 53 bytes

[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:

Brute-force search.

Usage

   f =: [:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:
   f 2
┌───┬───┬───┬───┬───┬───┬───┐
│0 0│0 0│0 0│0 1│0 1│0 1│1 1│
│0 0│0 1│1 1│0 1│1 0│1 1│1 1│
└───┴───┴───┴───┴───┴───┴───┘
   # f 3
168
   # f 4
16576

Explanation

[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:  Input: integer n
                                                   *:  Square n
                                           2      ^    Compute m = 2 ^ (n ^ 2)
                                               i.@     Make a range [0, m)
                                            #:@        Convert each to binary digits
    ,~                                                    Pair, make [n, n]
                                       $"#.            Reshape each binary list
                                                          to a matrix with size [n, n]
             (                       )@                Operate on each
                                    <                    Box it, call x
              2:                                         The constant 2
                _&(                )                     Repeat that many times on x
                       (        )&>                        For each box
                            |."1                             Reverse by column
                         |.                                  Reverse by row
                           ;                                 Join them
                        ;                                    Join with initial
                    [:,                                    Flatten
                   ]                                       Return that as the new x
         /:~@                                          Sort each
      {.@                                              Take the head of each
[:~.                                                   Unique and return
\$\endgroup\$
4
\$\begingroup\$

Jelly, 19 bytes

Ṛ€;U;
2ḶṗṗµWdz¡Ṃµ€Q

Try it online!

How it works

2ḶṗṗµWdz¡Ṃµ€Q  Main link. Argument: n (integer)

2Ḷ             Unlength 2; yield [0, 1].
  ṗ            Cartesian product; construct all vectors of {0, 1}^n.
   ṗ           Cartesian product; construct all vectors of ({0, 1}^n)^n.
               This yields A, the array of all binary n×n matrices.
    µ     µ€   Begin a new, monadic chain and apply it to all matrices M in A.
     W           Wrap; yield [M].
      dz¡        Call the helper link n times, initially with argument [M], then
                 on the previous return value.
         Ṃ       Take the minimum of the results.
               This replaces all matrices with the lexicographical minimum of their
               equivalence classes, mapping equivalent matrices to the same matrix.
            Q  Unique; deduplicate the resulting array of matrices.

Ṛ€;U;          Helper link. Argument: L (array of matrices)

Ṛ€             Reverse the order of the rows of each M in L.
   U           Reverse the order of the columns of each M in L.
  ;            Concatenate the resulting matrix arrays.
    ;          Concatenate the result with L.
\$\endgroup\$
2
\$\begingroup\$

Pyth - 24 23 21 bytes

Wanna look for better way of getting all the reflections.

Thanks to @Pietu1998 for golfing me 2 bytes!

hM.gS+K_Bk_MMKcRQ^`T*

Try it online here.

Going to wait for golfing before doing a full explanation, but it essentially makes all possible binary matrices, then .groups them by the sorted list of all the possible reflections, then only takes one from each group.

\$\endgroup\$
  • \$\begingroup\$ If I run that with argument 3 the output begins [['000', '000', '00'], note the missing zero at the end. \$\endgroup\$ – spraff Oct 4 '16 at 21:20
  • \$\begingroup\$ @spraff whoops, I did ^2Q instead of Q^2. fix saves me a byte too :D \$\endgroup\$ – Maltysen Oct 4 '16 at 21:21
  • \$\begingroup\$ @spraff fixed it. \$\endgroup\$ – Maltysen Oct 4 '16 at 21:22
  • \$\begingroup\$ I'm pretty sure you can do _MM instead of mC_Cd. \$\endgroup\$ – PurkkaKoodari Oct 5 '16 at 7:38
  • \$\begingroup\$ @Pietu1998 oh yeah, thanks! \$\endgroup\$ – Maltysen Oct 5 '16 at 20:42
1
\$\begingroup\$

Haskell, 100 bytes

import Data.List
r=reverse
e#n=mapM id$e<$[1..n]
f n=nubBy(\a b->elem a[r b,r<$>b,r$r<$>b])$"01"#n#n

Usage example: f 2 -> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

How it works:

e#n=mapM id$e<$[1..n]        -- helper function: creates a list of all combinations
                             -- of the elements of e of length n
                             -- "01" # 2 -> ["00","01","10","11"]

                   "01"#n#n  -- creates all binary n x n matrices
nubBy                        -- remove duplicates according to the equivalence
                             -- relation
   \a b ->                   -- a equals b if
       a elem                -- a is an element of
         [r b,r<$>b,r$r<$>b] -- the list of reflections of b 
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 195 bytes

n=>[...Array(p=1<<n*n)].map(_=>(p++).toString(2).slice(1)).filter((s,i,a)=>![1,0,1].some(c=>a.indexOf((c?b.reverse():b=b.map(s=>[...s].reverse().join``)).join``)<i,b=s.match(eval(`/.{${n}}/g`))))

Returns strings representing all matrix entries concatenated e.g. 111101111 represents a 3×3 matrix of 1s with a 0 in the middle. Explanation:

n=>[...Array(p=1<<n*n)].map(            Enumerate all binary matrices
 _=>(p++).toString(2).slice(1)          Convert to padded binary
).filter((s,i,a)=>![1,0,1].some(        Check reflections of each matrix
 c=>a.indexOf((c?b.reverse():           Reverse the order of lines
  b=b.map(s=>[...s].reverse().join``    Or reverse each line
  )).join``)<i,                         Has this been seen before?
 b=s.match(eval(`/.{${n}}/g`))))        Reshape string into a square
\$\endgroup\$
  • \$\begingroup\$ A recursive number-to-binary function is exactly the same length: .map(f=(x=p++)=>x>1?f(x>>1)+x%2:"") \$\endgroup\$ – ETHproductions Oct 5 '16 at 19:48
1
\$\begingroup\$

Mathematica, 94 bytes

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi JHM! Thanks for the answer. I don't understand Mathematica very well, so could you add a bit of explanation as to what's going on? (I posted the same thing on your other recent answer. Giving some explanation is a strong expectation for answers on this site) \$\endgroup\$ – isaacg Oct 6 '16 at 5:25
0
\$\begingroup\$

JavaScript (ES6), 184

This turned out to be quite similar to Neil's, but all in all the bag of tricks in javascript is not so diverse.

n=>eval("r=x=>[...x].reverse();for(l='',i=m=1<<n*n;i<m+m;i++)a=i.toString(2).slice(1).match(eval(`/.{${n}}/g`)),[b=a.map(x=>r(x).join``),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+`\n`")

Less golfed

n=>{
  r = x =>[...x].reverse();
  for(l = '', i = m = 1<<n*n; i < m+m; i++)
    a = i.toString(2).slice(1).match(eval(`/.{${n}}/g`)), // base matrix as an array of strings
    b = a.map(x => r(x).join``), // horizontal reflection
    c = r(a), // vertical reflection
    d = r(b), // both reflections
    // check if already found 
    [b, c, d].some(x => ~l.search(x)) // using search, arrays are converted to comma separated strings 
      ? 0 
      : l += a+`\n` // add new found to list (again as a comma separated string)
  return l
}

Test Beware, even for input 4 the running time is overly long

f=n=>eval("r=x=>[...x].reverse();for(l='',i=m=1<<n*n;i<m+m;i++)a=i.toString(2).slice(1).match(eval(`/.{${n}}/g`)),[b=a.map(x=>r(x).join``),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+`\n`")

function update() {
  var i=+I.value;
  
  result = f(i)
  count = result.split('\n').length
  O.textContent = count+'\n'+result
}

update()
Input <select id=I onchange="update()"><option>2<option>3<option>4<option>5</select>
<pre id=O></pre>

\$\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.