(* CMSC 330 / Spring 2009 / Project 3 *)
(* Student: MY NAME *)

(* Fill in the implementation and submit puzzle.ml *)

#use "testUtils.ml";;

(*-------------------------------------------------------------------------*)
(* functions from lecture you may use *)

let rec map (f, l) = match l with
    [] -> []
  | (h::t) -> (f h)::(map (f, t))
;;

let rec fold (f, a, l) = match l with
    [] -> a
  | (h::t) -> fold (f, f (a, h), t)
;;

let length x = fold ((fun (a,y) -> a+1), 0, x)
;;

let rev x = fold ((fun (a,y) -> y::a), [], x)
;;

(*-------------------------------------------------------------------------*)
(* Part 1: Recursion *)

(* 
get_val (x, n) 	
int list * int -> int 	
element of list x at index n, or -1 if not found 	
Example: get_val ([5;6;7;3],1) => 6
*)

(* 
get_vals (x, y) 	
int list * int list -> int list 	
list of elements of list x at indices in list y, 
or [] if none found 	
elements must be returned in order listed in y 
Example: get_vals ([5;6;7;3],[2;0]) => [7;5]
*)

(* 
set_n (x, n, v) 	
'a list * int * 'a -> 'a list 	
list produced by setting n'th element of list x to value v 	
Example: set_n ([5;6;7;3],1,9) => [5;9;7;3]
*)

(* 
list_swap_val (b, u, v) 	
'a list * 'a * 'a -> 'a list 	
list b with values u,v swapped 	
Example: list_swap_val ([5;6;7;3],7,5) => [7;6;5;3]
*)

(* 
index (x, v) 	
'a list * 'a -> int 	
index of value v in list x, or -1 if not found 	
Example: index ([5;6;7;3],7) => 2
*)

(* 
uniq x 	
'a list -> 'a list 	
list of uniq elements in x 	
Example: uniq [5;6;5;3] => [6;5;3]
*)

(* 
find_new (x, y) 	
'a list * 'a list -> 'a list 	
list of members of list x not found in list y 	
Example: find_new ([4;3;7],[5;6;5;3]) => [4;7]
*)

(* 
is_sorted x 	
'a list -> bool 	
true if elements in x are in sorted order, false otherwise 	
Example: is_sorted ([5;5;7;9]) => true 
*)

(*-------------------------------------------------------------------------*)
(* Part 2: Higher order functions *)


(* 
grow_lists (x, y) 	 
'a list * 'a list -> 'a list list 	 
given list of elements x and list y, 
prepend every element of x to y 	 
Example: grow_lists ([1;2], [3;4]) => [[1;3;4]; [2;3;4]]
*)

(* 
concat_lists x 	
'a list list -> 'a list 	
given list of lists x, return list of concatenated lists in x 	
Example: concat_lists [[1;2];[7];[5;4;3]] => [1;2;7;5;4;3] 
*)

(*-------------------------------------------------------------------------*)
(* Part 3: Puzzle functions *)

(* 
find_board_size b 	 
'a list -> int 	 
size of board b, assuming board is square, given b as a list of ints 	 
Example: find_board_size [1;0;2;3;4;5;6;7;8] => 3
*)

let find_board_size b = 
    3
;;

(* 
pos_of_xy (x, y, s) 	
int * int * int -> int 	
position of x, y coordinate in board of size s 	
Example: pos_of_xy (1, 2, 3) => 5
*)

(* 
xy_of_pos (p, s) 	
int * int -> int * int 	
x, y coordinate of position p in board of size s 	
Example: xy_of_pos (5, 3) => (1, 2)
*)

(* 
move_pos b 	
int list -> int list 	
list of positions in board (in order) that can move to space in board 	
Example: move_pos [0;1;2;3;4;5;6;7;8] => [1;3]
*)

(* 
make_move (b,x) 	
int list * int -> int list 	
configuration of board after moving number at x to space 	
Example: make_move ([0;1;4;5;2;3;6;7;8], 3) => [5;1;4;0;2;3;6;7;8] 
*)

(* 
make_moves b 	
int list -> int list list 	
boards produced after all possible 1-step moves for board b 	
Example: make_move [0;1;2;3;4;5;6;7;8] => 
	[[1;0;2;3;4;5;6;7;8];[3;1;2;0;4;5;6;7;8]] 
*)


(*-------------------------------------------------------------------------*)
(* Part 4: Puzzle solver *)

(* 
solve_board (x,n) 	 
int list * int -> int list list list
given board x, return all solutions 
	(list of moves from solved board to x)
	within n moves, or [] if none exists 	
Example: solve_board ([1;2;0;3;4;5;6;7;8],3) => 
	[[[0;1;2;3;4;5;6;7;8];[1;0;2;3;4;5;6;7;8];[1;2;0;3;4;5;6;7;8]]]

*)


(*-------------------------------------------------------------------------*)
(* Bonus debugging utilities *)

(* print board as nXn square, with space @ 0 *)
let print_board b = 
    let board_size = (find_board_size b) in 
    let rec print_board_helper (b, x) = match b with
	  [] -> print_endline "------------------------"
	| (h::t) -> 
		print_string (if (h < 10) then "   " 
			else if (h < 100) then "  " else " ");
		if (h = 0) then print_string " " else (print_int h) ; 
		(if ((x mod board_size) = 0) then print_endline "") ; 
		print_board_helper (t, x+1)
    in print_board_helper (b, 1)
;;

(* print list of boards *)
let print_boards x = 
	print_endline "------------------------" ;
	ignore (map (print_board, x)) ;
	print_endline ""
;;

(* print some boards & lists of boards *)

(* uncomment following to test print! *)
(*
let try_out_print =
	let b1 = [0;1;2;3;4;5;6;7;8] in
	let b2 = [1;0;2;3;4;5;6;7;8] in
	let blist = [b1;b2] in
		prt_int_list b1;
		print_board b1;
		prt_int_list b2;
		print_board b2;
		prt_int_list_list blist;
		print_boards blist
;;
*)