From 9477dbe667f250ecd23f8fc0d56b942191526421 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Thu, 25 Feb 2021 14:42:55 +0100 Subject: Stare semestry, niepoukladane --- Semestr 3/pf/lista7/Map1.ml | 56 +++++++++++++++++++++ Semestr 3/pf/lista7/Perm.cmi | Bin 0 -> 1693 bytes Semestr 3/pf/lista7/Perm.cmo | Bin 0 -> 1179 bytes Semestr 3/pf/lista7/Perm.ml | 114 +++++++++++++++++++++++++++++++++++++++++++ Semestr 3/pf/lista7/Perm.mli | 24 +++++++++ Semestr 3/pf/lista7/zaj | Bin 0 -> 21848 bytes Semestr 3/pf/lista7/zaj.cpp | 80 ++++++++++++++++++++++++++++++ 7 files changed, 274 insertions(+) create mode 100644 Semestr 3/pf/lista7/Map1.ml create mode 100644 Semestr 3/pf/lista7/Perm.cmi create mode 100644 Semestr 3/pf/lista7/Perm.cmo create mode 100644 Semestr 3/pf/lista7/Perm.ml create mode 100644 Semestr 3/pf/lista7/Perm.mli create mode 100644 Semestr 3/pf/lista7/zaj create mode 100644 Semestr 3/pf/lista7/zaj.cpp (limited to 'Semestr 3/pf/lista7') diff --git a/Semestr 3/pf/lista7/Map1.ml b/Semestr 3/pf/lista7/Map1.ml new file mode 100644 index 0000000..90cf893 --- /dev/null +++ b/Semestr 3/pf/lista7/Map1.ml @@ -0,0 +1,56 @@ +type ('a, _) order1 = + | Lt : ('a, 'b) order1 + | Eq : ('a, 'a) order1 + | Gt : ('a, 'b) order1 + +module type Type1 = sig + type 'a t +end + +module type OrderedType1 = sig + include Type1 + val compare : 'a t -> 'b t -> ('a, 'b) order1 +end + +module type S = sig + type 'a key + type 'a value + type t + val empty : t + val add : 'a key -> 'a value -> t -> t + val remove : 'a key -> t -> t + val find : 'a key -> t -> 'a value +end + +module Make(Key : OrderedType1)(Value : Type1) : + (S with type 'a key = 'a Key.t and type 'a value = 'a Value.t) = +struct + type 'a key = 'a Key.t + type 'a value = 'a Value.t + type ex_key = + | Key : 'a key -> ex_key + type key_value_pair = + | KeyVal : 'a key * 'a value -> key_value_pair + module ExKey = + struct + type t = ex_key + let compare (Key k1) (Key k2) : int = + match Key.compare k1 k2 with + | Lt -> -1 + | Eq -> 0 + | Gt -> 1 + end + module ExMap = Map.Make(ExKey) + type t = key_value_pair ExMap.t + let empty : t = ExMap.empty + let add (k: 'a key) (v: 'a value) (m: t) : t = + ExMap.add (Key k) (KeyVal (k, v)) m + let remove (k: 'a key) (m: t) : t = + ExMap.remove (Key k) m + let find (type a) (k: a key) (m: t) : a value = + let (KeyVal (kf, v)) = ExMap.find (Key k) m in + match Key.compare k kf with + | Eq -> v + | _ -> failwith "sth is wrong" +end + diff --git a/Semestr 3/pf/lista7/Perm.cmi b/Semestr 3/pf/lista7/Perm.cmi new file mode 100644 index 0000000..30fe896 Binary files /dev/null and b/Semestr 3/pf/lista7/Perm.cmi differ diff --git a/Semestr 3/pf/lista7/Perm.cmo b/Semestr 3/pf/lista7/Perm.cmo new file mode 100644 index 0000000..527f12a Binary files /dev/null and b/Semestr 3/pf/lista7/Perm.cmo differ diff --git a/Semestr 3/pf/lista7/Perm.ml b/Semestr 3/pf/lista7/Perm.ml new file mode 100644 index 0000000..1b19bac --- /dev/null +++ b/Semestr 3/pf/lista7/Perm.ml @@ -0,0 +1,114 @@ +module type OrderedType = sig + type t + val compare : t -> t -> int +end + +module type S = sig + type key + type t + (** permutacja jako funkcja *) + val apply : t -> key -> key + (** permutacja identycznościowa *) + val id : t + (** permutacja odwrotna *) + val invert : t -> t + (** permutacja która tylko zamienia dwa elementy miejscami *) + val swap : key -> key -> t + (** złożenie permutacji (jako złożenie funkcji) *) + val compose : t -> t -> t + (** porównywanie permutacji *) + val compare : t -> t -> int +end + +module Make(Key : OrderedType) : (S with type key = Key.t) = +struct + type key = Key.t + module MapModule = Map.Make(Key) + type t = key MapModule.t * key MapModule.t + let apply ((map, invmap) : t) k = + try (MapModule.find k map) with + | Not_found -> k + let id : t = (MapModule.empty, MapModule.empty) + let invert ((map, invmap) : t) : t = + (invmap, map) + let swap k1 k2 : t = + let (map, invmap) = id in + (MapModule.add k2 k1 (MapModule.add k1 k2 map), MapModule.add k2 k1 (MapModule.add k1 k2 invmap)) + let compose ((map1, invmap1) : t) ((map2, invmap2) : t) : t = + let f map x m1_of_x m2_of_x = match m1_of_x with + | None -> m2_of_x + | Some y -> match MapModule.find_opt y map with + | None -> Some y + | Some z -> Some z + in (MapModule.merge (f map2) map1 map2, + MapModule.merge (f invmap1) invmap2 invmap1) + let compare ((map1, invmap1) : t) ((map2, invmap2): t) = + MapModule.compare Key.compare map1 map2 +end + +module StringOrder: (OrderedType with type t = string) = +struct + type t = string + let compare s1 s2 = if s1 < s2 then -1 else if s1 > s2 then 1 else 0 +end + +module StringPerm = Make(StringOrder) +let p = StringPerm.compose (StringPerm.swap "1" "2") (StringPerm.swap "2" "3");; + +(* Zadanie 2 *) + +let is_generated (type a) (packed : (module S with type t = a)) (perm : a) (generators : (a list)) = + let module PermModule = (val packed : (S with type t = a)) in + let module OrderedPerm : (OrderedType with type t = a) = + struct + type t = a + let compare p1 p2 = PermModule.compare p1 p2 + end in + let module SS = Set.Make(OrderedPerm) in + let rec flatmap f = function + | [] -> [] + | x :: xs -> (f x) @ flatmap f xs in + let saturate xn = + let perms = SS.elements xn in + let inverts = List.map (fun p -> PermModule.invert p) perms in + let compositions = flatmap (fun p -> (List.map (fun q -> PermModule.compose p q) perms)) perms in + SS.union xn (SS.union (SS.of_list inverts) (SS.of_list compositions)) in + let rec iter xn = + let xn1 = saturate xn in + if SS.mem perm xn1 then true else + if SS.compare xn xn1 == 0 then false else + iter xn1 + in iter (SS.of_list generators) + +(* Zadanie 3 *) + +module OrderedList (X : OrderedType) : (OrderedType with type t = X.t list) = +struct + type t = X.t list + let rec compare (xs: t) (ys: t) = + match (xs, ys) with + | ([], []) -> 0 + | ([], _) -> -1 + | (_, []) -> 1 + | (x :: xs, y :: ys) -> let cmp = X.compare x y in + if cmp == 0 then compare xs ys else cmp +end + +module OrderedPair (X : OrderedType) : (OrderedType with type t = X.t * X.t) = +struct + type t = X.t * X.t + let compare ((a, b): t) ((c, d) : t) = + let cmp = X.compare a c in + if cmp == 0 then X.compare b d else cmp +end + +module OrderedOption (X : OrderedType) : (OrderedType with type t = X.t option) = +struct + type t = X.t option + let compare (a: t) (b: t) = + match (a, b) with + | (None, None) -> 0 + | (None, _) -> -1 + | (_, None) -> 1 + | (Some a, Some b) -> X.compare a b +end diff --git a/Semestr 3/pf/lista7/Perm.mli b/Semestr 3/pf/lista7/Perm.mli new file mode 100644 index 0000000..cc18496 --- /dev/null +++ b/Semestr 3/pf/lista7/Perm.mli @@ -0,0 +1,24 @@ + +module type OrderedType = sig + type t + val compare : t -> t -> int +end + +module type S = sig + type key + type t + (** permutacja jako funkcja *) + val apply : t -> key -> key + (** permutacja identycznościowa *) + val id : t + (** permutacja odwrotna *) + val invert : t -> t + (** permutacja która tylko zamienia dwa elementy miejscami *) + val swap : key -> key -> t + (** złożenie permutacji (jako złożenie funkcji) *) + val compose : t -> t -> t + (** porównywanie permutacji *) + val compare : t -> t -> int +end + +module Make(Key : OrderedType) : S with type key = Key.t \ No newline at end of file diff --git a/Semestr 3/pf/lista7/zaj b/Semestr 3/pf/lista7/zaj new file mode 100644 index 0000000..1d0bbec Binary files /dev/null and b/Semestr 3/pf/lista7/zaj differ diff --git a/Semestr 3/pf/lista7/zaj.cpp b/Semestr 3/pf/lista7/zaj.cpp new file mode 100644 index 0000000..403754f --- /dev/null +++ b/Semestr 3/pf/lista7/zaj.cpp @@ -0,0 +1,80 @@ +#include +using namespace std; + +const int ALPHABET_SIZE = 26; + +struct node +{ + node *children[ALPHABET_SIZE]; + int cnt; + bool is_end; + + node() + { + for (int i = 0; i < ALPHABET_SIZE; i++) + children[i] = nullptr; + is_end = false; + cnt = 0; + } +}; + +struct TRIE +{ + node *root; + + TRIE() + { + root = new node; + } + + // dodaje słowo do słownika + void add_word(string word) + { + node *crawl = root; + for (auto c : word) + { + int letter = c - 'a'; + if (crawl->children[letter] == nullptr) + { + crawl->children[letter] = new node; + } + crawl = crawl->children[letter]; + } + crawl->is_end = true; + } + + // sprawdź czy słowo jest w słowniku + bool find(string word) + { + node *crawl = root; + for (auto c : word) + { + int letter = c - 'a'; + if (crawl->children[letter] == nullptr) + return false; + crawl = crawl->children[letter]; + } + return crawl->is_end; + } + + // usuń słowo ze słownika + void erase(string word) {} +}; + +int main() +{ + TRIE dictionary; + int q; + cin >> q; + while (q--) + { + char c; + string s; + cin >> c >> s; + if (c == 'A') + dictionary.add_word(s); + else + cout << (dictionary.find(s) ? "TAK" : "NIE") + << "\n"; + } +} \ No newline at end of file -- cgit v1.2.3