aboutsummaryrefslogtreecommitdiff
path: root/semestr-3/pf/lista7
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-10-05 21:49:54 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-10-05 21:49:54 +0200
commitc5fcf7179a83ef65c86c6a4a390029149e518649 (patch)
treed29ffc5b86a0d257453cedcf87d91a13d8bf3b0d /semestr-3/pf/lista7
parentf8a88b6a4aba1f66d04711a9330eaba49a50c463 (diff)
Duzy commit ze smieciami
Diffstat (limited to 'semestr-3/pf/lista7')
-rw-r--r--semestr-3/pf/lista7/Map1.ml56
-rw-r--r--semestr-3/pf/lista7/Perm.cmibin0 -> 1693 bytes
-rw-r--r--semestr-3/pf/lista7/Perm.cmobin0 -> 1179 bytes
-rw-r--r--semestr-3/pf/lista7/Perm.ml114
-rw-r--r--semestr-3/pf/lista7/Perm.mli24
-rw-r--r--semestr-3/pf/lista7/zaj.cpp80
6 files changed, 274 insertions, 0 deletions
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
--- /dev/null
+++ b/semestr-3/pf/lista7/Perm.cmi
Binary files differ
diff --git a/semestr-3/pf/lista7/Perm.cmo b/semestr-3/pf/lista7/Perm.cmo
new file mode 100644
index 0000000..527f12a
--- /dev/null
+++ b/semestr-3/pf/lista7/Perm.cmo
Binary files 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.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 <bits/stdc++.h>
+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