From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 5 Oct 2021 21:49:54 +0200 Subject: Duzy commit ze smieciami --- Semestr 3/pf/lista7/Map1.ml | 56 --------------------- Semestr 3/pf/lista7/Perm.cmi | Bin 1693 -> 0 bytes Semestr 3/pf/lista7/Perm.cmo | Bin 1179 -> 0 bytes Semestr 3/pf/lista7/Perm.ml | 114 ------------------------------------------- Semestr 3/pf/lista7/Perm.mli | 24 --------- Semestr 3/pf/lista7/zaj | Bin 21848 -> 0 bytes Semestr 3/pf/lista7/zaj.cpp | 80 ------------------------------ 7 files changed, 274 deletions(-) delete mode 100644 Semestr 3/pf/lista7/Map1.ml delete mode 100644 Semestr 3/pf/lista7/Perm.cmi delete mode 100644 Semestr 3/pf/lista7/Perm.cmo delete mode 100644 Semestr 3/pf/lista7/Perm.ml delete mode 100644 Semestr 3/pf/lista7/Perm.mli delete mode 100644 Semestr 3/pf/lista7/zaj delete 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 deleted file mode 100644 index 90cf893..0000000 --- a/Semestr 3/pf/lista7/Map1.ml +++ /dev/null @@ -1,56 +0,0 @@ -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 deleted file mode 100644 index 30fe896..0000000 Binary files a/Semestr 3/pf/lista7/Perm.cmi and /dev/null differ diff --git a/Semestr 3/pf/lista7/Perm.cmo b/Semestr 3/pf/lista7/Perm.cmo deleted file mode 100644 index 527f12a..0000000 Binary files a/Semestr 3/pf/lista7/Perm.cmo and /dev/null differ diff --git a/Semestr 3/pf/lista7/Perm.ml b/Semestr 3/pf/lista7/Perm.ml deleted file mode 100644 index 1b19bac..0000000 --- a/Semestr 3/pf/lista7/Perm.ml +++ /dev/null @@ -1,114 +0,0 @@ -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 deleted file mode 100644 index cc18496..0000000 --- a/Semestr 3/pf/lista7/Perm.mli +++ /dev/null @@ -1,24 +0,0 @@ - -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 deleted file mode 100644 index 1d0bbec..0000000 Binary files a/Semestr 3/pf/lista7/zaj and /dev/null differ diff --git a/Semestr 3/pf/lista7/zaj.cpp b/Semestr 3/pf/lista7/zaj.cpp deleted file mode 100644 index 403754f..0000000 --- a/Semestr 3/pf/lista7/zaj.cpp +++ /dev/null @@ -1,80 +0,0 @@ -#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