Bits of Learning

Learning sometimes happens in big jumps, but mostly in little tiny steps. I share my baby steps of learning here, mostly on topics around programming, programming languages, software engineering, and computing in general. But occasionally, even on other disciplines of engineering or even science. I mostly learn through examples and doing. And this place is a logbook of my experiences in learning something. You may find several things interesting here: little cute snippets of (hopefully useful) code, a bit of backing theory, and a lot of gyan on how learning can be so much fun.

Friday, September 27, 2013

8-Queens Puzzle using Functional Programming

Following is the OCaml code I wrote yesterday to solve the 8-queen puzzle. I have presented a solution in Python in an earlier post for the same purpose. However, there's a key difference. This solution is purely functional programming. This means that we do a completely side-effect free computing here. Therefore, we don't have assignments, mutable types, and of course, no loops. Once I got the code in place, I re-implemented the whole thing using loops. For the benefit of those accustomed to a procedural way of programming (me included), I have included that code too here.

 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
module EightQueen = struct
 let conflict a b diff =
  (a = b) || (abs (a - b) = diff)

 let emptyList = [];;
 let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];;
 let maxlength = List.length allValues;;

 let shuffle d =
      let nd   = List.map (fun c -> (Random.bits (), c)) d in
      let sond = List.sort compare nd in
      List.map snd sond

 let rec checkConflict newList =
  let rec check i =
   let c = conflict (List.nth newList 0) (List.nth newList i) i in
   if c then
    false
   else if i = (List.length newList - 1) then
    true
   else
    check (i + 1)
  in
  if List.length newList < 2 then
   true
  else 
   check 1

 let rec solve pos =
  if checkConflict pos = false then
   emptyList
  else if List.length pos = maxlength then
   pos
  else
   let rec loop lst allowedValues =
    if allowedValues = emptyList then
     emptyList
    else
     let head         = List.hd allowedValues
     and tail         = List.tl allowedValues in
     let extendedList = head::pos in
     let answer       = solve extendedList in
     if answer <> emptyList then
      answer
     else
      loop lst tail
   in
   loop pos (shuffle allValues)
end;;

let rec printList lst =
 match lst with
   []   -> ()
 | e::l -> print_int e ; print_string " " ; printList l
;;

let lst = EightQueen.solve EightQueen.emptyList in
printList lst; print_string "\n";;


And here follows pretty much the same code using imperative style:



 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
let conflict a b diff =
 (a = b) || (abs (a - b) = diff)
;;

let emptyList = [];;
let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];;
let maxlength = List.length allValues;;

let rec print_list = function 
 [] -> ()
 | e::l -> print_int e ; print_string " " ; print_list l
;;

let shuffle d =
    let nd   = List.map (fun c -> (Random.bits (), c)) d in
    let sond = List.sort compare nd in
    List.map snd sond

let rec checkConflict newList =
 let result = ref true in
 for i = 1 to ((List.length newList) - 1) do
  if !result = true then
   if conflict (List.nth newList 0) (List.nth newList i) i then
    result := false
 done;
 !result
;;

let rec solve pos =
 if checkConflict pos = false then
  emptyList
 else if List.length pos = maxlength then
  pos
 else
  let result = ref emptyList in
  for i = 0 to ((List.length allValues) - 1) do
   if !result = emptyList then
    let value = (List.nth allValues i) in
    let extendedList = value::pos in
    let answer       = solve extendedList in
    if answer <> emptyList then
     result := answer
  done;
  !result
;;

let lst = solve emptyList in
print_list lst; print_string "\n";;

No comments: