14
\$\begingroup\$

The challenge

Output an array or string representation of Dürer's famous magic square:

enter image description here

that is,

16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

Some properties of this square, which can perhaps be exploited, are:

  • It contains each integer from 1 to 16 exactly once
  • The sum of each column or row, as well as the the sum of each of the two diagonals, is the same. This is the defining property of a magic square. The sum is the magic constant of the square.
  • In addition, for this particular square, the sum of each of the four quadrants also equals the magic constant, as do the sum of the center four squares and the sum of the corner four squares.

Rules

Bultins that generate magic squares are not allowed (such as Matlab's magic or Mathematica's MagicSquare). Any other builtin can be used.

The code can be a program or a function.

There is no input.

The numbers must be in base 10. The output format is flexible as usual. Some possibilities are:

  • A nested array (either function output, or its string representation, with or without separators, any type of matching brackets):

    [[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]
    
  • A 2D array:

    {16, 3, 2, 13; 5, 10, 11, 8; 9, 6, 7, 12; 4, 15, 14, 1}
    
  • An array of four strings, or a string consisting of four lines. The numbers may be right-aligned

    16  3  2 13
     5 10 11  8
     9  6  7 12
     4 15 14  1
    

    or left-aligned

    16 3  2  13
    5  10 11  8
    9  6  7  12
    4  15 14  1
    
  • A string with two different separators for row and column, such as

    16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1
    

The output format should clearly differentiate rows and columns. For example, it is not allowed to output a flat array, or a string with all numbers separated by spaces.

Code golf. Shortest wins.

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Luis Mendo Oct 31 '16 at 22:07
  • 4
    \$\begingroup\$ Interestingly, the numbers 5, 8, 9 and 12 are in their (1-indexed) positions, 6, 7, 10 and 11 have been reflected vertically, 2, 3, 14 and 15 have been reflected horizontally and 1, 4, 13 and 16 have been rotated 180°. I doubt that will help anyone though. \$\endgroup\$ – Neil Oct 31 '16 at 22:38
  • 2
    \$\begingroup\$ Possibly useful observation: if you decrement 1 from each number, you can generate the square by starting with the array [15], then repeatedly concatenating it with its reverse with each item XORed by 13, 3, 8, and 15, respectively. \$\endgroup\$ – ETHproductions Oct 31 '16 at 22:41
  • 6
    \$\begingroup\$ This seems rather hard to compress in non-golfing languages. i think a larger magic square would have done better. \$\endgroup\$ – xnor Oct 31 '16 at 22:51
  • 1
    \$\begingroup\$ I'm fairly certain each rotation or reflection of the square would have the same properties. \$\endgroup\$ – Dennis Nov 1 '16 at 15:10

19 Answers 19

7
\$\begingroup\$

Jelly, 15 bytes

“¡6ṡƘ[²Ḳi<’ḃ⁴s4

TryItOnline!

Pretty boring, sorry:

Prep: Took the square, read it by rows, converted from bijective base 16, convert that to base 250, looked up the code page indexes for those "digits" (¡6ṡƘ[²Ḳi<).

Jelly then reads the indexes to make a base 250 number, converts to bijective base 16 (ḃ⁴) and splits into chunks of size 4 (s4).


If we are allowed to output a different orientation, upside-down is possible in 14:

“#⁷ƙ¤ṆWȷỤ’ḃ⁴s4

Test


In theory, given enough memory for 16! integers the following would give us the correct orientation in 14:

⁴Œ!“ŒCġŀḌ;’ịs4

This would create all permutations of [1,16] with ⁴Œ! and pick the value at index 19800593106060 (1-based) with using the base 250 representation ŒCġŀḌ; and split it into chunks of length 4 with s4.


Since then I have added four new atoms (Œ?, Œ¿, œ?, and œ¿) to Jelly to address such situations.
The monad Œ? takes an integer (or iterable of integers) and returns the shortest possible permutation of running natural numbers which would have the given index (or indexes) in a list of lexicographically sorted list of all permutations of those numbers.
...and it does so without creating any permutation lists.
As such the following would now work for 12 (obviously non-competing):

“ŒCġŀḌ;’Œ?s4

Give It A Go!

\$\endgroup\$
  • \$\begingroup\$ This should be shorter in your Jelly fork (which I had forgotten about until right now, sorry). \$\endgroup\$ – Dennis Nov 1 '16 at 3:53
  • \$\begingroup\$ Oh? How do you think? \$\endgroup\$ – Jonathan Allan Nov 1 '16 at 17:59
8
\$\begingroup\$

Pyth, 18 bytes

c4.PC"H#ût"_S16

Run the code.

c4.PC"H#ût"_S16

    C"H#ût"       Convert the packed string to the number 1122196781940
  .P       _S16   Take that-numbered permutation of the reversed range [16,15,...,1]
c4                Chop into piece of length 4

Reversing the range was meant to lower the permutation index, since the output starts with 16, but I think it only broke even.

This beat out a more boring strategy of converting the table directly to base 17 and then a string (link) for 20 bytes:

c4jC"úz(ás¸H"17 
\$\endgroup\$
7
\$\begingroup\$

Jelly, 16 15 bytes

4Œ!.ịm0µZḂÞ’×4+

Try it online!

Background

If we subtract 1 from the numbers in the square and divide them by 4 (computing quotient and remainder), a pattern becomes apparent.

quotients and remainders    quotients    remainders

   3 3  0 2  0 1  3 0        3 0 0 3      3 2 1 0
   1 0  2 1  2 2  1 3        1 2 2 1      0 1 2 3
   2 0  1 1  1 2  2 3        2 1 1 2      0 1 2 3
   0 3  3 2  3 1  0 0        0 3 3 0      3 2 1 0

The remainder matrix follows an obvious pattern and is easy to generate. The quotient matrix can be obtained by transposing the remainder matrix and swapping the middle rows.

How it works

4Œ!.ịm0µZḂÞ’×4+  Main link. No arguments.

4Œ!              Compute the array of all permutations of [1, 2, 3, 4], in
                 lexicographical order.
   .ị            Take the permutations at the indices adjacent to 0.5, i.e., the
                 ones at indices 0 ([4, 3, 2, 1]) and 1 ([1, 2, 3, 4]).
     m0          Concatenate the resulting [[4, 3, 2, 1], [1, 2, 3, 4]] with a
                 reversed copy, yielding the matrix
                 M := [[4, 3, 2, 1], [1, 2, 3, 4], [1, 2, 3, 4], [4, 3, 2, 1]].
       µ         Begin a new, monadic chain. Argument: M
        Z        Zip/transpose M, yielding the matrix
                 [[4, 1, 1, 4], [3, 2, 2, 3], [2, 3, 3, 2], [1, 4, 4, 1]].
         ḂÞ      Sort the rows by the lexicographical order of their parities,
                 yielding [[4, 1, 1, 4], [2, 3, 3, 2], [3, 2, 2, 3], [1, 4, 4, 1]].
           ’     Subtract 1 to yield the matrix of quotients, i.e.,
                 [[3, 0, 0, 3], [1, 2, 2, 1], [2, 1, 1, 2], [0, 3, 3, 0]].
            ×4+  Multiply the quotient by 4 and add the result to M (remainders).
\$\endgroup\$
5
\$\begingroup\$

J, 37 27 bytes

Saved 10 bytes thanks to miles!

4 4$1+19800593106059 A.i.16

Now with less boring! This takes the 19800593106059 permutation of the list i.16, which is 15 2 1 12 4 9 10 7 8 5 6 11 3 14 13 0. Then, that is incremented, then is shaped into a 4 by 4 list.

Alternate version, with no whitespace:

_4]\1+19800593106059&A.i.16

Output, for posterity:

   _4]\1+19800593106059&A.i.16
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1
   4 4$1+19800593106059 A.i.16
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1
\$\endgroup\$
  • \$\begingroup\$ I think _4]\1+19800593106059&A.i.16 works but it could be made shorter possibly \$\endgroup\$ – miles Nov 1 '16 at 3:35
  • \$\begingroup\$ @miles oo, nice use of A.. How did you fin that number? \$\endgroup\$ – Conor O'Brien Nov 1 '16 at 11:17
  • \$\begingroup\$ Monadic A. finds the permutation index of a zero-indexed permutation \$\endgroup\$ – miles Nov 1 '16 at 11:55
  • \$\begingroup\$ @miles huh. I guess I should learn a little more about those functions then. \$\endgroup\$ – Conor O'Brien Nov 1 '16 at 12:27
4
\$\begingroup\$

05AB1E, 18 17 bytes

Thanks to Emigna for saving a byte!

•3øѼž·Üý;•hSH>4ô

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ Incrementing before chunking saves a byte (>4ô). \$\endgroup\$ – Emigna Nov 1 '16 at 8:17
  • \$\begingroup\$ @Emigna Ahh, of course! Thanks! :) \$\endgroup\$ – Adnan Nov 1 '16 at 15:27
4
\$\begingroup\$

Ruby, 49 bytes (shorter than the naive solution!)

It took quite a few attempts to write a snippet for this challenge in a mainstream language that was shorter than what it evaluated to! Per usual rules I've made a program out of it by adding a p to output it.

p [15,4,8,3].map{|i|[1+i,1+i^=13,1+i^=3,1+i^=13]}

It outputs (the string representation of) an array of arrays. It's longer than wat's Ruby solution that outputs a differently-formatted string, but one byte shorter than the naive program below that simply returns the literal array.

p [[16,3,2,13],[5,10,11,8],[9,6,7,12],[4,15,14,1]] #naive solution, 50 bytes
p [15,4,8,3].map{|i|[1+i,1+i^=13,1+i^=3,1+i^=13]}  #submission, 49 bytes

Explanation: start with numbers 0..15 (38 bytes!)

This is where I started and it´s much easier. If we convert the 0..15 square into binary, we note that each cell contains the value at the bottom of its column XORed with the value at the right hand side of its row:

15 2  1  12            1111 0010 0001 1100
4  9  10 7             0100 1001 1010 0111
8  5  6  11            1000 0101 0110 1011
3  14 13 0             0011 1110 1101 0000

From this we derive the code below. But by using the first column instead of the last column, we save one byte, as shown.

p [12,7,11,0].map{|i|[i^3,i^14,i^13,i]}            #0..15 square, 39 bytes         
p [15,4,8,3].map{|i|[i,i^13,i^14,i^3]}             #0..15 square, 38 bytes

The required 1..16 version was more difficult. In the end I realised the way to do it was to add 1 to each cell of the 0..15 square. But as ^ has lower priority than + I needed a lot of parentheses, which ate bytes. Finally I hit on the idea of using ^=. The new value of i is calculated by augmented assignment ^= before the 1 is added to it, so the calculation is done in the correct order.

\$\endgroup\$
  • \$\begingroup\$ Nice characterization! A simple realization in Python is 6 chars above hardcode: for a in 12,7,11,0:print[(a^b)+1for b in 3,14,13,0]. It would win if we could do 0 to 15 with for a in 12,7,11,0:print[a^3,a^14,a^13,a]. \$\endgroup\$ – xnor Nov 2 '16 at 1:52
3
\$\begingroup\$

JavaScript (ES6), 43 bytes

_=>`16,3,2,13
5,10,11,8
9,6,7,12
4,15,14,1`

Separated by newlines, then commas. I doubt there's any shorter way...

\$\endgroup\$
  • \$\begingroup\$ Yeah, this is probably the shortest possible. \$\endgroup\$ – Conor O'Brien Nov 1 '16 at 1:31
2
\$\begingroup\$

sed 39 bytes

c16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1

Try it Online!

It can't get much simpler than this. And, unfortunately, I don't think it can get any shorter either.

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

Jelly, 20 bytes

“Ѥ£Æ¦½¿®µ©¬€¥ÐÇ¢‘s4

Try it online!

This simply looks up the Jelly code point of each character, then slices into subarrays of length 4 with s4.

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

DASH, 24 bytes

<|>4tc"................"

Replace the periods with the characters of charcodes 16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, and 1 respectively.

Explanation

Simply converts the characters to an array of charcodes and chunks by 4.

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

Actually, 22 bytes

4"►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"♂┘╪

Try it online!

Explanation:

4"►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"♂┘╪
 "►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"     push a string containing the numbers in the magic square, encoded as CP437 characters
                   ♂┘   convert to ordinals
4                    ╪  chunk into length-4 slices
\$\endgroup\$
2
\$\begingroup\$

Groovy, 57 bytes / 46 bytes

"F21C49A7856B3ED0".collect{Eval.me("0x$it")+1}​.collate(4)​

Parse each as hexidecimal digit and add 1, collate by 4 into a 2D array.

[[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]

Shorter, but also lamer:

print '16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1'
\$\endgroup\$
2
\$\begingroup\$

Javascript ES6, 66 65 55 bytes

Yes, it isn't the shortest one. And yes, it can be reduced.

_=>`f21c
49a7
856b
3ed0`.replace(/./g,_=>'0x'+_-~0+' ')

For now, it isn't perfect. But is something!


Thanks to @Neil's suggestion that could save 5-8 bytes, and that inspired @ETHproductions suggestion that saves 10 bytes!

This makes the answer only 12 bytes longer than his 43 bytes solution.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could use g instead of 0 and parseInt(c,17) instead, which I think saves you 4 bytes, or you could use +0x${c}||16, which I think saves you 5 bytes, and you could then subtract 1 from all of the digits and add it back later, which I think saves you another byte. \$\endgroup\$ – Neil Nov 1 '16 at 12:49
  • 1
    \$\begingroup\$ Building on @Neil's suggestions, you can save at least 10 bytes in total. \$\endgroup\$ – ETHproductions Nov 1 '16 at 15:12
  • \$\begingroup\$ @Neil Thank you a lot for the idea. Using base17 really does save a few bytes. It really is something I didnt think about. \$\endgroup\$ – Ismael Miguel Nov 1 '16 at 18:20
  • \$\begingroup\$ @ETHproductions Thank you a lot for the suggestion! I'm still trying to understand how it works. But I think I will get there. Now, just need to shorten 13 bytes to beat you. But it does seem your answer is the shortest possible in Javascript \$\endgroup\$ – Ismael Miguel Nov 1 '16 at 18:21
1
\$\begingroup\$

PowerShell v2+, 40 bytes

'16,3,2,13
5,10,11,8
9,6,7,12
4,15,14,1'

A literal multiline string, left on the pipeline. Output via implicit Write-Output happens at program completion. Nice and boring.


Constructed version, 77 bytes

'f21c59a7856b3dc0'-split'(....)'-ne''|%{([char[]]$_|%{"0x$_+1"|iex})-join','}

Takes the string, -splits it every four elements, loops on them, changes each to a hex 0x$_ and adds 1, pipes that to iex (short for Invoke-Expression and similar to eval), then -joins the result into a string with , as the separator. Outputs four strings onto the pipeline, with implicit printing.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 60 bytes - first attempt

%w(f21c 49a7 856b 3ed0).map{|i|i.chars.map{|i|i.to_i(16)+1}}

Ruby, 45 bytes - cheap

puts '16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1'
\$\endgroup\$
1
\$\begingroup\$

Pyth - 17 bytes

Base conversion. This unfortunately beats @xnor's approach

c4jC"úz(ás¸H"17

Try it online here.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 15 bytes

16Lœ•iPNÍš¯•è4ä

Explanation

16L              # range [1 ... 16]
   œ             # compute all permutations of the range
    •iPNÍš¯•è    # take the permutation at index 19800593106059
             4ä  # split the permutation into 4 parts

The index of the permutation was found using the formula:

a*15! + b*14! + c*13!+ ... + o*1! + p*0!

Where the variables are replaced with the number of succeeding elements which are smaller than the number at the current index for each number in the target list
[16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1]

which for our sought after permutation is
a=15, b=2, c=1, d=10, e=2, f=6, g=6, h=4, i=4, j=2, k=2, l=2, m=1, n=2 o=1, p=0

This gives us the formula: 15*15!+2*14!+1*13!+10*12!+2*11!+6*10!+6*9!+4*8!+4*7!+2*6!+2*5!+2*4!+1*3!+2*2!+1*1!+0*0!

which is equal to 19800593106059.

\$\endgroup\$
1
\$\begingroup\$

Matlab, 38 35 bytes

Anonymous function:

@()['pcbm';'ejkh';'ifgl';'dnoa']-96

Direct printing (38 bytes):

disp(['pcbm';'ejkh';'ifgl';'dnoa']-96)

In Matlab best way to produce an array of integers is though a string.

\$\endgroup\$
  • \$\begingroup\$ Using an anonymous function would save a few bytes: @()['pcbm';'ejkh';'ifgl';'dnoa']-96 \$\endgroup\$ – Luis Mendo Nov 1 '16 at 21:12
  • \$\begingroup\$ @LuisMendo I didn't notice that returning value is also acceptable, thanks! \$\endgroup\$ – pajonk Nov 2 '16 at 8:52
1
\$\begingroup\$

Scala, 52 bytes

()=>Seq(15,4,8,3)map(x=>Seq(x,x^13,x^14,x^3)map(1+))

Ungolfed:

()=>
  Seq(15, 4, 8, 3)
  .map(x=>
    Seq(x, x^13, x^14, x^3)
    .map(1+)
  )

Inspired by Level River St's ruby answer.

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