Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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
http://www.rebol.org/cgi-bin/cgiwrap/rebol/download-a-script.r?script-name=lexpem.r
>> 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