Another coffee break problem?
[1/17] from: joel::neely::fedex::com at: 10-Nov-2003 18:01
If Sunanda will allow me to steal his subject line... ;-)
The following 3-by-3 display is a simple magic square:
0 8 4
5 1 6
7 3 2
because each row and each column sums to 12. Write a function which
uses the integers 0 thru 8 (once each!) to construct all possible
3-by-3 simple magic squares. Make it run as quickly as possible.
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
Enron Accountingg in a Nutshell: 1c=$0.01=($0.10)**2=(10c)**2=100c=$1
[2/17] from: greggirwin:mindspring at: 10-Nov-2003 18:13
Hi Joel,
JN> The following 3-by-3 display is a simple magic square:
JN> 0 8 4
JN> 5 1 6
JN> 7 3 2
JN> because each row and each column sums to 12. Write a function which
JN> uses the integers 0 thru 8 (once each!) to construct all possible
JN> 3-by-3 simple magic squares. Make it run as quickly as possible.
No diagonals? I thought magic squares had to work on the diagonal as
well? (not to be nit-picky or anything :)
-- Gregg
[3/17] from: tomc:darkwing:uoregon at: 10-Nov-2003 17:34
On Mon, 10 Nov 2003, Gregg Irwin wrote:
> Hi Joel,
> JN> The following 3-by-3 display is a simple magic square:
<<quoted lines omitted: 7>>
> well? (not to be nit-picky or anything :)
> -- Gregg
I think that may be why he stipulated "simple" magic squares
[4/17] from: antonr:iinet:au at: 11-Nov-2003 12:46
I can see you are going to ask us to
generalize it later so it can do integers
higher than 8.
I think for this set of numbers 12 is the
only sum you will get, but just to be clear,
shouldn't it be: "it's a magic square because
each row and column sum to the same number" ?
Anton.
[5/17] from: joel:neely:fedex at: 11-Nov-2003 7:02
Hi, Gregg,
Gregg Irwin wrote:
> JN> The following 3-by-3 display is a simple magic square:
> JN> 0 8 4
<<quoted lines omitted: 3>>
> No diagonals? I thought magic squares had to work on the diagonal as
> well? (not to be nit-picky or anything :)
To be equally picky ;-)
That's why I said "simple magic" square instead of "totally magic". I
was going to post a follow-up problem to refine the first program so
that it also checks diagonals.
Also, not all sources I've looked at insist on diagonal operations. One
interesting way to generalize the problem is to "magic" rectangles with
different height and width. In that case, the definition of "diagonal"
becomes more interesting...
-jn-
[6/17] from: joel:neely:fedex at: 11-Nov-2003 7:35
Hi, Anton...
Anton Rolls wrote:
> I can see you are going to ask us to
> generalize it later so it can do integers
> higher than 8.
>
Since Gregg has already partially debagged the cat, I'll admit that
I have some generalizations in mind, but not that particular one ;-)
> I think for this set of numbers 12 is the
> only sum you will get, but just to be clear,
> shouldn't it be: "it's a magic square because
> each row and column sum to the same number" ?
>
Yes, but only because a square is a rectangle with the same height
and width...
WARNING: YOU ARE NOW ENTERING THE [scary music] ALGEBRA ZONE!
A rectangular display of numbers with R rows and C columns contains
R*C cells. The simplest way to fill those cells with distinct values
is to use the first R*C natural numbers, such that 0 <= n < R*C. The
sum of all of the values is then
(+i : 0 <= i < R*C : i) = R*C * (R*C - 1) / 2
Adding the requirement that all row totals be equal tells us that the
row total must be the grand total divided by the number of rows, so
all row totals = R * C * (R * C - 1) / 2 / R
= C * (R * C - 1) / 2
and likewise
all col totals = R * C * (R * C - 1) / 2 / C
= R * (R * C - 1) / 2
so that e.g. for a 3 x 5 "simple magic" rectangle,
grand total = 3 * 5 * (3 * 5 - 1) / 2
= 15 * 14 / 2
= 15 * 7
= 105
all row totals = 105 / 3 = 35
all col totals = 105 / 5 = 21
and, of course, if R and C are equal, the magic row and col totals
will be equal (so e.g. for the 3 x 3 case, 9 * 8 / 2 / 3 = 12).
If I wanted to be sneaky, I'd ask how many magic rectangles there are
with 99 rows and 100 columns!
YOU ARE NOW ENTERING AN ALGEBRA-FREE ZONE! ;-)
HINT AHEAD -- Don't read if you want to solve it on your own steam!
.
.
.
.
.
.
.
.
.
.
Since there are 362880 ways to arrange 9 distinct values, the key
issue is to do something more economical than simply generating all
possible permutations, checking each one for magicness.
-jn-
[7/17] from: greggirwin:mindspring at: 11-Nov-2003 8:54
Hi Joel,
JN> That's why I said "simple magic" square instead of "totally magic".
My mistake then; I wasn't aware there was such a distinction. (and you
were only one diagonal off :)
-- Gregg
[8/17] from: Patrick:Philipot:laposte at: 11-Nov-2003 22:03
Hello Joel,
Tuesday, November 11, 2003, 1:01:52 AM, you wrote:
JN> If Sunanda will allow me to steal his subject line... ;-)
JN> The following 3-by-3 display is a simple magic square:
JN> 0 8 4
JN> 5 1 6
JN> 7 3 2
JN> because each row and each column sums to 12. Write a function which
JN> uses the integers 0 thru 8 (once each!) to construct all possible
JN> 3-by-3 simple magic squares. Make it run as quickly as possible.
JN> --
As you have got no solution yet, this is mine just to start the
engine. It is not very clever and I don't know if it's right.
I am looking forward to see other results though.
Rebol [
date: 11-10-2003
author: "pat665"
purpose: {
Post from Joël Neely
The following 3-by-3 display is a simple magic square:
0 8 4
5 1 6
7 3 2
because each row and each column sums to 12. Write a function which
uses the integers 0 thru 8 (once each!) to construct all possible
3-by-3 simple magic squares. Make it run as quickly as possible.
}
]
nums: [0 1 2 3 4 5 6 7 8]
; all the triplets that sum to 12
triplets: copy []
for i 1 9 1 [
for j (i + 1) 9 1 [
for k (j + 1) 9 1 [
if 12 = (nums/:i + nums/:j + nums/:k) [
append/only triplets reduce [nums/:i nums/:j nums/:k]
]
]
]
]
triplets: sort unique triplets
; == [[0 4 8] [0 5 7] [1 3 8] [1 4 7] [1 5 6] [2 3 7] [2 4 6] [3 4 5]]
; Grouping the triplets that use exactly the 9 available numbers
groups: copy []
temp: copy []
nb-group: length? triplets
for i 1 nb-group 1 [
for j (i + 1) nb-group 1 [
for k (j + 1) nb-group 1 [
append clear temp triplets/:i
append temp triplets/:j
append temp triplets/:k
temp: sort temp
if equal? nums temp [
append/only groups compose/deep [
[(triplets/:i)]
[(triplets/:j)]
[(triplets/:k)]
]
]
]
]
]
; groups: [[[0 4 8] [1 5 6] [2 3 7]] [[0 5 7] [1 3 8] [2 4 6]]]
; Help function for permutation
n: [1 2 3]
permutations: copy []
for i 1 3 1 [
for j 1 3 1 [
for k 1 3 1 [
if all [ i <> j i <> k j <> k ][
append/only permutations reduce [n/:i n/:j n/:k]
]
]
]
]
permutations: unique permutations
; permutations: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
; Help function
magic?: func [
"test for magicallness"
b [block!]
][
; rows are already magical
; just testing the columns here
all [
b/1/1 + b/2/1 + b/3/1 = 12
b/1/2 + b/2/2 + b/3/2 = 12
b/1/3 + b/2/3 + b/3/3 = 12
]
]
; The solutions
nb-solution: 0
foreach group groups [
; triplet permutations
for p 1 6 1 [
gp: compose/deep [
[(pick group permutations/:p/1)]
[(pick group permutations/:p/2)]
[(pick group permutations/:p/3)]
]
; number permutation inside each triplet
for i 1 6 1 [
t1: reduce [
pick gp/1 permutations/:i/1
pick gp/1 permutations/:i/2
pick gp/1 permutations/:i/3
]
for j 1 6 1 [
t2: reduce [
pick gp/2 permutations/:j/1
pick gp/2 permutations/:j/2
pick gp/2 permutations/:j/3
]
for k 1 6 1 [
t3: reduce [
pick gp/3 permutations/:k/1
pick gp/3 permutations/:k/2
pick gp/3 permutations/:k/3
]
if magic? solution: compose/deep [[(t1)][(t2)][(t3)]] [
print mold solution/1
print mold solution/2
print mold solution/3
print newline
nb-solution: nb-solution + 1
]
]
]
]
]
]
?? nb-solution
--
Best regards,
Patrick
[9/17] from: tomc:darkwing:uoregon at: 11-Nov-2003 16:06
ok, first a smart aleck answer that is true to the specification but not
the intent ...
>> do
>> ms: lexperm "012345678" 362880
; all 3-by-3 simple magic squares are constructed and in the 'ms block
; I doubt it will be fastest ('cept maby to write)
; Will try one that matches your intent better when I am not at work ;)
On Mon, 10 Nov 2003, Joel Neely wrote:
[10/17] from: antonr:iinet:au at: 12-Nov-2003 21:50
You can simplify this to:
repeat i 9 [
Anton.
[11/17] from: lmecir:mbox:vol:cz at: 12-Nov-2003 21:45
Hi,
how about this one:
basic-magic: [
[0 8 4]
[7 3 2]
[5 1 6]
]
permuts: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
id: func [block] [reduce [block/1 block/2]]
swap: func [block] [reduce [block/2 block/1]]
magic: copy/deep basic-magic
foreach rp permuts [
foreach cp permuts [
foreach k reduce [:id :swap] [
repeat r 3 [
repeat c 3 [
set [pr pc] k reduce [rp/:r cp/:c]
poke magic/:pr pc basic-magic/:r/:c
]
]
probe magic
]
]
]
-L
[12/17] from: patrick:philipot:laposte at: 12-Nov-2003 12:58
Thanks Anton,
I always use 'for and it's a bad habit.
I'll try to use more repeat.
Regards
Patrick
[13/17] from: tomc:darkwing:uoregon at: 12-Nov-2003 23:23
On Tue, 11 Nov 2003, Joel Neely wrote:
> Hi, Gregg,
> Gregg Irwin wrote:
<<quoted lines omitted: 19>>
> becomes more interesting...
> -jn-
ok here is my first pass, Im sure there is cleanup to do
have not done any benchmarking ... time for bed
Rebol[
title: "magic square generator"
author: "Tom Conlin"
date: 12-Nov-2003
file: %itsawrap.r
version: 0.0.2
purpose: { Post from Joel Neely
The following 3-by-3 display is a simple magic square:
0 8 4
5 1 6
7 3 2
because each row and each column sums to 12. Write a function
which uses the integers 0 thru 8 (once each!) to construct all
possible 3-by-3 simple magic squares.
Make it run as quickly as possible.
}
]
n: 3
ns: n * n
flip: func[b [series!] n[integer!]][ ; this one I like
forskip b n[reverse/part b n]
head b
]
; not so happy with this, I finaly brute forced it
reflect: func [b [series!] n[integer!] /local t ][
t: make block! n * n
forskip b n[insert tail t pick b 1]
repeat i n - 1[
b: skip head b i
forskip b n[insert tail t pick b 1]
]
b: copy t
]
pprint: func[b [series!] n[integer!]][
loop n[print copy/part b n b: skip b n]
b: head b print ""
]
;; to be general these should be made functions
;; but with non 0 array origin it makes messy modulo math
ur: [8 9 7 2 3 1 5 6 4]
dn: [4 5 6 7 8 9 1 2 3]
s: t: 0
for i 1 ns 1 [
ms: copy [0 0 0 0 0 0 0 0 0]
s: i
poke ms s 1
for j 2 ns 1[
either equal? 0 pick ms t: pick ur s
[poke ms s: t j]
[poke ms s: pick dn s j]
]
b: copy ms
pprint b 3 ; normal
pprint flip b 3 3 ; about vertical axis
pprint reflect b 3 3 ; rotate left
pprint flip b 3 3 ; about backslash
b: head reverse copy ms
pprint b 3 ; rotated 180 degrees
pprint flip b 3 3 ; about horizontal axis
pprint reflect b 3 3 ; rotate right
pprint flip b 3 3 ; about slash
print ""
]
halt
[14/17] from: tomc:darkwing:uoregon at: 13-Nov-2003 10:30
On Wed, 12 Nov 2003, Tom Conlin wrote:
> On Tue, 11 Nov 2003, Joel Neely wrote:
> >
<<quoted lines omitted: 26>>
> >
> > -jn-
I did wake up in in the middle of the night remembering I had
only coverd a third of the cases. and it looks like I should not have
those dups in there ...
pprint b 3 ; normal
pprint flip b 3 3 ; about vertical axis
pprint reflect b 3 3 ; rotate left 90
flip b 3 3 ; back to normal
pprint reflect b 3 3 ; about backslash
b: head reverse b
pprint b 3 ; rotated 180 degrees
pprint flip b 3 3 ; about horizontal axis
pprint reflect b 3 3 ; rotate right 90
flip b 3 3 ; back to 180
pprint reflect b 3 3 ; about slash
but still have to handle the other 16 cases
[15/17] from: tomc:darkwing:uoregon at: 16-Nov-2003 14:01
OK ... I think this is complete enough
Rebol[
title: "Magic Square generator"
author: "Tom Conlin"
date: 12-Nov-2003
file: %magic-squares.r
version: 0.1.0
purpose: { Post from Joel Neely
The following 3-by-3 display is a simple magic square:
0 8 4
5 1 6
7 3 2
because each row and each column sums to 12.
Write a function which uses the integers 0 thru 8 (once each!)
to construct all possible 3-by-3 simple magic squares.
Make it run as quickly as possible.
}
]
magic-squares: func [
{ generate simple magic squares
and their symetrical reflections
for a particular ODD size
}
n[integer!] "odd natural number"
/verbose "pretty print the solutions as well as returning a block"
/local flip transpose pprint ms nn ur dn s t blank result
][
;; be sensible
if any[not integer? n not positive? n not odd? n][
print "argument needs to be positive odd integer"
return -1
]
nn: n * n
;; actualy quite neat
flip: func[b [series!] n[integer!]][
while[not tail? b][reverse/part b n b: skip b n]
head b
]
;; a bit tedious
transpose: func[b[block!] n[integer!] /local t u d ni][
for i 1 n 1[
ni: n * i - n
for j i + 1 n 1[
t: pick b u: ni + j
poke b u pick b d: n * j - n + i
poke b d t
]
]
b
]
;;
pprint: func[b [series!] n[integer!]][
loop n[print copy/part b n b: skip b n]
print ""
]
; for building upper-right LUT
wrap: func[ b[block!] n[integer!]][
join skip tail b negate n copy/part b subtract length? b n
]
;;make LUTs for next move, either up & right or down (with wrapping)
dn: make block! nn + n
repeat i nn[insert tail dn i]
ms: copy ur: copy dn ;; populate blocks
insert tail dn copy/part dn n ;; down LUT
remove/part dn n
ur: wrap ur n ;; up & right LUT
while[not tail? ur][
change/part ur wrap copy/part ur n n - 1 n
ur: skip ur n
]
ur: head ur
result: make block! 8 * nn ;; storage
;; starting from 0 isn't worth the hassle
for i 1 nn 1[
s: i
poke ms s 1
for j 2 nn 1[ ;; build one of the n simple magic squares
either equal? 1 j // n
[poke ms s: pick dn s j]
[poke ms s: pick ur s j]
]
;; store the simple magic square and its reflections
insert/only tail result copy ms ; normal
loop 3[
insert/only tail result copy flip ms n
insert/only tail result copy transpose ms n
] insert/only tail result copy flip ms n
]
if verbose [
while[not tail? result][
pprint pick result 1 n result: next result
]
]
head result
]
[16/17] from: antonr:iinet:au at: 17-Nov-2003 14:14
Let's see some results:
draw-bar: func [n height /local p1 p2 p3 p4][
p1: to-pair reduce [(n * 20) 270]
p2: p1 - (height * 0x1 / 20)
p3: p2 + 18x0
p4: p1 + 18x0
compose/deep [
text (p1 + 0x4) (form n)
polygon (p1) (p2) (p3) (p4) (p1)
text (p2 - 0x18) (form height)
]
]
draw-blk: compose [pen sky fill-pen white font (probe make face/font [size:
10])]
view/new center-face layout [b: box black 500x300 effect compose/deep [draw
[(draw-blk)]]]
repeat n 23 [if odd? n [append b/effect/draw draw-bar n length?
magic-squares n show b]]
wait none
Anton.
[17/17] from: tomc:darkwing:uoregon at: 16-Nov-2003 22:27
since the length? magic-squares n is known to be 8 * n * n
lets try a variation and plot wall time in thousandths of a second.
run: func [f [word!] n[integer!] /local then][
then: now/time/precise
do f n
to-integer 1000 * subtract now/time/precise then
]
draw-bar: func [n height /local p1 p2 p3 p4][
p1: to-pair reduce [(n * 20) 270]
p2: p1 - (height * 0x1 / 20)
p3: p2 + 18x0
p4: p1 + 18x0
compose/deep [
text (p1 + 0x4) (form n)
polygon (p1) (p2) (p3) (p4) (p1)
text (p2 - 0x18) (form height)
]
]
draw-blk: compose[
pen sky fill-pen white font (probe make face/font [size: 10])
]
view/new center-face layout [
b: box black 500x300 effect compose/deep [draw[(draw-blk)]]
]
repeat n 23[
if odd? n[append b/effect/draw draw-bar n run 'magic-squares n show b]
]
wait none
On Mon, 17 Nov 2003, Anton Rolls wrote:
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted