aboutsummaryrefslogtreecommitdiff
path: root/Semestr 3/pf/lista7
diff options
context:
space:
mode:
Diffstat (limited to 'Semestr 3/pf/lista7')
-rw-r--r--Semestr 3/pf/lista7/Map1.ml56
-rw-r--r--Semestr 3/pf/lista7/Perm.cmibin1693 -> 0 bytes
-rw-r--r--Semestr 3/pf/lista7/Perm.cmobin1179 -> 0 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/zajbin21848 -> 0 bytes
-rw-r--r--Semestr 3/pf/lista7/zaj.cpp80
7 files changed, 0 insertions, 274 deletions
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
--- a/Semestr 3/pf/lista7/Perm.cmi
+++ /dev/null
Binary files differ
diff --git a/Semestr 3/pf/lista7/Perm.cmo b/Semestr 3/pf/lista7/Perm.cmo
deleted file mode 100644
index 527f12a..0000000
--- a/Semestr 3/pf/lista7/Perm.cmo
+++ /dev/null
Binary files 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
--- a/Semestr 3/pf/lista7/zaj
+++ /dev/null
Binary files 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 <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