Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /tests/trunk/bugs/tests.obsolete/bug980.sml
ViewVC logotype

View of /tests/trunk/bugs/tests.obsolete/bug980.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2460 - (download) (annotate)
Sat Apr 28 20:18:10 2007 UTC (12 years, 2 months ago) by gkuan
File size: 2694 byte(s)
(* bug980.sml *)

(* Internet Programming Contest 1991, Problem 5 *)

(* utilities *)

fun flatten [] = []
  | flatten (xs::ys) = xs @ (flatten ys);

(* ex *) flatten [[1,2],[4,3]];

fun ind 0 = "\n"
  | ind n = ind (n-1)^" ";

fun wvars [x] = x
  | wvars (x::xs) = x^","^wvars xs;

fun impl [] = ""
  | impl (xs::ys) = xs^impl ys;  

fun unparse plist = impl (flatten (map (fn (str, vl) => [str, "writeln("^wvars vl^")"]) (rev plist)));

(* special-cons f|r listorna som representerar programmet *)
fun cons2 ((s1,l1),[(s2,l2)]) = [(s1^s2,l1@l2)]
  | cons2 ((s1,l1),(s2,l2)::xs) = (s2,l1@l2)::(cons2 ((s1,l1),xs));

(* ex *) cons2 (("else", ["b","a"]),[ ("else", ["d","c"]), ("if c<d then ", ["c","d"])  ]);

(* som cons2, men beh}ll split *)
fun cons3 ((s1,l1),[(s2,l2)]) = [(s1^s2,(l1,l2))]
  | cons3 ((s1,l1),(s2,l2)::xs) = (s2,(l1,l2))::(cons3 ((s1,l1),xs));

(* list product *)
fun crossprod ([],_) = []
  | crossprod (x::xs, ys) = cons3 (x,ys) @ crossprod (xs, ys); 


(* mergar och levererar en lista som ska tolkas bakl{nges 
   (pga att cons2 ska bli enklare *)
fun merge ([], []) = [("",[])]
  | merge ([], y::ys) = cons2 (("",[y]), merge (ys, []))
  | merge (x::xs, []) = cons2 (("",[x]), merge (xs, []))
  | merge (x::xs, y::ys) =
      cons2 ((ind(2)^"else ", [y]), merge (x::xs, ys))
    @ cons2 (("if "^x^"<"^y^" then"^ind(2), [x]), merge (xs, y::ys))
;

(* ex *) merge (["a"],["b"]); 
 
fun mergelists (a,b) = 
  flatten (map ( fn (str,(l1,l2)) => cons2 ((str,[]), merge (l1,l2))) (crossprod (a,b)));

(* ex *) mergelists ([ ("else", ["b","a"]), ("if a<b then ", ["a","b"])  ],
	   [ ("else", ["d","c"]), ("if c<d then ", ["c","d"])  ]);

(* somthing like ordinary mergesort *)
fun split2 [] = ([],[])
  | split2 [x] = ([x],[])
  | split2 (x::y::zs) =
      let
        val (M,N) = split2 zs
      in
        (x::M, y::N)
      end;

(* something like insertion sort *)
fun split1 [] = ([],[])
  | split1 (x::ys) = ([x],ys);

fun mergesort _ [] = [("",[])]
  | mergesort _ [x] = [("",[x])]
  | mergesort split L =
   let
     val (M,N) = split L;
     val M = mergesort split M;
     val N = mergesort split N
   in
     mergelists (M,N)
   end;

(* ex *) mergesort split1 ["a","b","c"]; 

fun listgen 0 = []
  | listgen n = listgen (n-1) @ [String.implode[Char.chr (n-1+Char.ord #"a")]];

fun pascalsort split n = 
 let val lista = listgen n;
     val progstr = "program sort(input,output);\n"^
                   "var "^wvars lista^" : integer;\n"^
		   "begin\n"^
                   "  readln("^wvars lista^");\n  "^
		   unparse (mergesort split lista)^
                   "\nend.\n";
 in
   print progstr
 end;

(* ex *) pascalsort split2 4;
(* ex *) pascalsort split2 6;

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0