Back to Questions
1.0k
views3
comments
Finding magic lines (some new kid questions)
f#functional

dear Friends

Thus far I figured:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

let Magic() = 
   let order = 4
   let dim = 2
   let rec power x n =
      if (n <= 0) then
         1
      else
         x * (power x (n-1))
   let max = power order dim
   let numbers = [0 .. max - 1];
   let sum = order * (max - 1) / 2;
   let magic list sum =
      match list with
      | [a,b,c,d] -> a + b + c + d = sum
      |_ -> false 
   let sumlines (lst:int list) (sum:int) = [ 
      for i1 in lst do // this is too imperative for my taste
      for i2 in lst do // tried filter but something like (fun a b c d -> a + b + c + d = sum)
      for i3 in lst do // doesn't work
      for i4 in lst do
      if (i1 < i2 && i2 < i3 && i3 < i4) then
         let lst = [i1,i2,i3,i4]
         if (magic lst sum) then
            yield lst ]
   printfn "MAGIC LINES:"
   let lines = sumlines numbers sum
   for line in lines do
      for lin in line do
         //for i1 in lin do // deactivated as (int * int * int * int) can't be enumerated by this syntax
         //   printf " %02d" i1
         printfn "%A" lin

as above mentioned sumlines works however my attemps to find a more functional approach have failed.
how can one get here 4 numbers out of 16 numbers obeying the "magic condition" in a functional manner.
the deactivated printstatement, is my inexperience I reckon why can't I iterate through those for numbers, VS2008 ctp intellisense doesn't provide me with a hint how I'm supposed to do it in an alternative manner
Any comments to the above code I welcome

1
2
3
4
5
6
7

let printline (i1,i2,i3,i4) = 
   printfn "%02d %02d %02d %02d" i1 i2 i3 i4
printfn "MAGIC LINES:"
let lines = sumlines numbers sum
for line in lines do
   for lin in line do
      printline lin


the above prints as wanted, but without means of iteration is statement limited to order 4

just back to add, that the above is about order 4, the goal is of course to be able to change this to some other number.
with the above I would have to make alterations I don't want to do, number of for loops equal to order, etc.
Of course there are elaborate ways around this, but those would with my current knowledge resemble my implementation in imperative C#

.

I wrote this very quickly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

let sub list n =
  let rec sub_inner list n =
    if (List.length list = n) then [list]
    else 
      match n with
       | 1 -> List.map ( fun u  ->  [ u ])  list
       | _ -> 
          let h,t = List.hd list, List.tl list
          List.append (List.map (fun u -> (h::u)) (sub_inner t (n - 1))) (sub_inner t n)
  if (List.length list < n) then failwith "length must be greater or equal to n"
  else if (n <=0) then failwith "n must be >= 1 "
       else sub_inner list n
   
let max = 16
let order = 4  
let sum = order * (max - 1) / 2 
let magic2 sum list = (List.sum list = sum)   
  
let l = sub [0..max - 1] order |> List.filter (magic2 sum)
  
l |> List.iter (printfn "%A")
By on 6/24/2009 2:08 PM ()

Though written quickly perhaps, it works! thanks, nice code and order and dimension independend (changed max to 25, and order to 5, and obtained the list of order 5 magic lines; changing 16 to 64 my familiar order 4 cube magic lines appears)

By on 6/24/2009 10:05 PM ()

Continuing the fun I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

let square list ord =
   let rec equ lst vl = 
      if (List.length lst = 0) then false 
      elif List.hd lst = vl then true 
      else equ (List.tl lst) vl
   let rec eq lst1 lst2 = 
      match lst1 with
      | [] -> false
      | [ a ] -> not (equ lst2 a)
      |_ -> not (equ lst2 (List.hd lst1)) && eq (List.tl lst1) lst2
   let rec lines list ord =
      if (List.length list = 0) then []
      elif (List.length list = ord) then [list]
      else
         let h,t = List.hd list, List.tl list
         let tf = List.filter (fun u -> eq h u) list
         //if (ord = 2) then
         // List.map (fun u -> (h::u)) tf
         //else
         List.append (List.map (fun u -> (h::u)) (lines tf (ord - 1))) (lines t ord)
   lines list ord |> List.filter (fun u -> eq u.[ord-2] u.[ord-1])
 
let squares = square l order
squares.Length |> printfn "%d"
squares |> printfn "%A"

which works, attempts to work the last filter into 'lines' is the ord = 2 statement, viriations on the statement above tried but everything ran up to a 'ranking problem' also I reckon the equ/eq combination can be stated using List.find, used here to list in tf the sublist holding the lines of numbers with number not in h thus forming squares of unique numbers.

As currently is you find the last set of numbers with possibly equal numbers as the previous set, this is filtered out by the last filter.
The ord = 2 statement has I reckon (debugging in VS2008 ctp, isn't possible) a head with all tails already ok possibilities, but yet to find a stement combining h with all tails.

Squares nicely hold the expected square, manupulation of which can be semi-magic squares by permutation of the lines above, permuting the lines one can get to the 880 possible magic squares of order 4. (just a goal of this little excercise)
The cube variation seems to be too lengthy (in duration) which prompts the question whether it is possible to halt a given iteration at some point, and continue at a later date?

By on 6/26/2009 3:46 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper