diff options
Diffstat (limited to 'src')
20 files changed, 1099 insertions, 80 deletions
diff --git a/src/act4e_solutions/intro.py b/src/act4e_solutions/intro.py index 2a4856d..acf62bf 100644 --- a/src/act4e_solutions/intro.py +++ b/src/act4e_solutions/intro.py @@ -3,4 +3,4 @@ import act4e_interfaces as I class SolSimpleIntro(I.SimpleIntro): def sum(self, a: int, b: int) -> int: - raise NotImplementedError() + return a + b diff --git a/src/act4e_solutions/maps.py b/src/act4e_solutions/maps.py index aff881f..f056da8 100644 --- a/src/act4e_solutions/maps.py +++ b/src/act4e_solutions/maps.py @@ -1,6 +1,7 @@ from typing import TypeVar import act4e_interfaces as I +from .maps_representation import MyFiniteMap A = TypeVar("A") B = TypeVar("B") @@ -10,7 +11,16 @@ C = TypeVar("C") class SolFiniteMapOperations(I.FiniteMapOperations): def identity(self, s: I.Setoid[A]) -> I.Mapping[A, A]: - raise NotImplementedError() + values = [] + for a in s.elements(): + values.append([a, a]) + + return MyFiniteMap(s, s, values) + def compose(self, f: I.FiniteMap[A, B], g: I.FiniteMap[B, C]) -> I.FiniteMap[A, C]: - raise NotImplementedError() + values = [] + for a in f.source().elements(): + values.append([a, g(f(a))]) + + return MyFiniteMap(f.source(), g.target(), values) diff --git a/src/act4e_solutions/maps_representation.py b/src/act4e_solutions/maps_representation.py index f532658..330b3fd 100644 --- a/src/act4e_solutions/maps_representation.py +++ b/src/act4e_solutions/maps_representation.py @@ -1,14 +1,100 @@ -from typing import Any, TypeVar +from pprint import pprint +from typing import Any, TypeVar, Dict, List import act4e_interfaces as I +from .sets_representation import SolFiniteSetRepresentation +from .sets_product import MyFiniteSetProduct A = TypeVar("A") B = TypeVar("B") +class MyFiniteMap(I.FiniteMap[A, B]): + _source: I.FiniteSet[A] + _target: I.FiniteSet[B] + _values: List[List] + + def __init__(self, source: I.FiniteSet[A], target: I.FiniteSet[B], values: Dict[A, B]): + self._source = source + self._target = target + self._values = values + + def source(self) -> I.FiniteSet[A]: + return self._source + + def target(self) -> I.FiniteSet[B]: + return self._target + + def __call__(self, a: A) -> B: + # print("Function call") + # print("src: ", self._source.elements()) + # print("dst: ", self._target.elements()) + # print("val: ", self._values) + # print("inp: ", a) + assert a in self._source.elements() + + rv = None + for v in self._values: + if self._source.equal(v[0], a): + # print(f"{v[0]} equals {a}") + rv = v[1] + + assert self._target.contains(rv) + # print("ret: ", rv) + # print("the type of rv is", type(rv)) + # print() + + return rv + class SolFiniteMapRepresentation(I.FiniteMapRepresentation): def load(self, h: I.IOHelper, s: I.FiniteMap_desc) -> I.FiniteMap[A, B]: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + + if not "values" in s.keys(): + raise I.InvalidFormat() + + if len(s["values"]) == 0: + raise I.InvalidFormat() + + A = fsr.load(h, s["source"]) + B = fsr.load(h, s["target"]) + values = [] + + for v in s["values"]: + a, b = A.load(h, v[0]), B.load(h, v[1]) + + if not A.contains(a): + print(f"{v[0]} is not in A: {A.elements()}") + raise I.InvalidFormat() + + if not B.contains(b): + print(f"{v[1]} is not in B: {B.elements()}") + raise I.InvalidFormat() + + values.append([a, b]) + + # Check that the domain values are unique + domain = [] + for a, _ in values: + if a in domain: + raise I.InvalidFormat() + domain.append(a) + + return MyFiniteMap(A, B, values) + def save(self, h: I.IOHelper, m: I.FiniteMap[Any, Any]) -> I.FiniteMap_desc: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + d = { + "source": fsr.save(h, m.source()), + "target": fsr.save(h, m.target()), + "values": [] + } + + for a in m.source().elements(): + b = m(a) + d["values"].append([ + m.source().save(h, a), + m.target().save(h, b)]) + + return d diff --git a/src/act4e_solutions/posets_bounds.py b/src/act4e_solutions/posets_bounds.py index 0d50baf..05f818f 100644 --- a/src/act4e_solutions/posets_bounds.py +++ b/src/act4e_solutions/posets_bounds.py @@ -1,4 +1,8 @@ -from typing import Any, List, Optional, overload, TypeVar, Collection +from typing import Any, List, Optional, overload, TypeVar +from itertools import product +from functools import cmp_to_key + +from .posets_representation import MyFinitePoset import act4e_interfaces as I @@ -15,15 +19,37 @@ class SolFinitePosetMeasurement(I.FinitePosetMeasurement): class SolFinitePosetConstructionOpposite(I.FinitePosetConstructionOpposite): def opposite(self, p: I.FinitePoset[X]) -> I.FinitePoset[X]: - raise NotImplementedError() # implement here + e = p.carrier().elements() + values = [] + for a, b in product(e, e): + if p.holds(a, b): + # then the opposite holds(b, a) + values.append((b, a)) + return MyFinitePoset(p.carrier(), values) class SolFinitePosetSubsetProperties(I.FinitePosetSubsetProperties): - def is_chain(self, fp: I.FinitePoset[X], s: Collection[X]) -> bool: - raise NotImplementedError() - - def is_antichain(self, fp: I.FinitePoset[X], s: Collection[X]) -> bool: - raise NotImplementedError() + def is_chain(self, fp: I.FinitePoset[X], s: List[X]) -> bool: + try: + def cmp(a, b): + return fp._cmp(a, b) + + s_sorted = sorted(s, key=cmp_to_key(cmp)) + except RuntimeError as e: + return False + return True + + def is_antichain(self, fp: I.FinitePoset[X], s: List[X]) -> bool: + # Comparison with itself should be ignored, since there is always a + # relation to itself by antisymmetry + not_the_same = lambda pair: not fp.carrier().equal(pair[0], pair[1]) + + # Check that no elements are comparable + for a, b in filter(not_the_same, product(s, s)): + assert fp.carrier().contains(a) and fp.carrier().contains(b) + if fp.holds(a, b): + return False + return True class SolFinitePosetSubsetProperties2(I.FinitePosetSubsetProperties2): diff --git a/src/act4e_solutions/posets_construction.py b/src/act4e_solutions/posets_construction.py index ae24f75..bba5b62 100644 --- a/src/act4e_solutions/posets_construction.py +++ b/src/act4e_solutions/posets_construction.py @@ -1,10 +1,37 @@ from typing import Any, TypeVar +from .sets_properties import SolFiniteSetProperties +from .sets_power import MyFiniteSetOfFiniteSubsets, SolFiniteMakePowerSet +from .posets_representation import MyFinitePoset + import act4e_interfaces as I X = TypeVar("X") +C = TypeVar("C") # Type of elements of set +E = TypeVar("E") + +class MyFinitePosetOfFiniteSubsets(I.FinitePosetOfFiniteSubsets[C, E]): + _subsets: I.FiniteSetOfFiniteSubsets[C, E] + def __init__(self, subsets): + self._subsets = subsets + self._prop = SolFiniteSetProperties() + + def carrier(self) -> I.FiniteSetOfFiniteSubsets[C, E]: + return self._subsets + + def holds(self, a: I.FiniteSet[C], b: I.FiniteSet[C]): + if self._prop.equal(a, b): + return True + + if self._subsets.contains(a) and self._subsets.contains(b): + if self._prop.is_subset(a, b): + return True + + return False class SolFinitePosetConstructionPower(I.FinitePosetConstructionPower): def powerposet(self, s: I.FiniteSet[X]) -> I.FinitePosetOfFiniteSubsets[X, Any]: - raise NotImplementedError() + setpow = SolFiniteMakePowerSet() + subsets = setpow.powerset(s) + return MyFinitePosetOfFiniteSubsets(subsets) diff --git a/src/act4e_solutions/posets_map.py b/src/act4e_solutions/posets_map.py index a91d4d8..8d28c62 100644 --- a/src/act4e_solutions/posets_map.py +++ b/src/act4e_solutions/posets_map.py @@ -1,5 +1,8 @@ from typing import TypeVar +from itertools import product +from .posets_bounds import SolFinitePosetConstructionOpposite + import act4e_interfaces as I A = TypeVar("A") @@ -9,7 +12,13 @@ X = TypeVar("X") class SolFiniteMonotoneMapProperties(I.FiniteMonotoneMapProperties): def is_monotone(self, p1: I.FinitePoset[A], p2: I.FinitePoset[B], m: I.FiniteMap[A, B]) -> bool: - raise NotImplementedError() + A = p1.carrier().elements() + for x, y in product(A, A): + if p1.holds(x, y): + if not p2.holds(m(x), m(y)): + return False + return True def is_antitone(self, p1: I.FinitePoset[A], p2: I.FinitePoset[B], m: I.FiniteMap[A, B]) -> bool: - raise NotImplementedError() + opp = SolFinitePosetConstructionOpposite() + return self.is_monotone(opp.opposite(p1), p2, m) diff --git a/src/act4e_solutions/posets_product.py b/src/act4e_solutions/posets_product.py index bf67efd..3dc1bde 100644 --- a/src/act4e_solutions/posets_product.py +++ b/src/act4e_solutions/posets_product.py @@ -1,10 +1,44 @@ -from typing import Any, Sequence, TypeVar +from typing import Any, Sequence, TypeVar, List + +from .sets_product import MyFiniteSetProduct import act4e_interfaces as I X = TypeVar("X") +C = TypeVar("C") # Type of the components +E = TypeVar("E") # Type of the product + +class MyFinitePosetProduct(I.FinitePosetProduct[C, E]): + _posets: List[I.FinitePoset[C]] + _carrier: I.FiniteSetProduct[C, E] + def __init__(self, posets: Sequence[I.FinitePoset[C]]): + self._posets = posets + + get_carrier = lambda p: p.carrier() + carriers = list(map(get_carrier, self._posets)) + self._carrier = MyFiniteSetProduct(carriers) + + def carrier(self): + return self._carrier + + def components(self) -> Sequence[I.FinitePoset[C]]: + return self._posets + + def holds(self, a: E, b: E) -> bool: + a = self._carrier.unpack(a) + b = self._carrier.unpack(b) + + # For all elements in both tuples, each element must be comparable with + # the element with the same index in the other tuple. If one is not + # comparable, then it is not comparable. + for ps, x, y in zip(self._posets, a, b): + if not ps.holds(x, y): + return False + + return True + class SolFinitePosetConstructionProduct(I.FinitePosetConstructionProduct): def product(self, ps: Sequence[I.FinitePoset[X]]) -> I.FinitePosetProduct[X, Any]: - raise NotImplementedError() + return MyFinitePosetProduct(ps) diff --git a/src/act4e_solutions/posets_representation.py b/src/act4e_solutions/posets_representation.py index c43da82..61a598c 100644 --- a/src/act4e_solutions/posets_representation.py +++ b/src/act4e_solutions/posets_representation.py @@ -1,11 +1,150 @@ -from typing import Any +from typing import TypeVar, Any, List, Tuple, Dict, Set +from itertools import product +from pprint import pprint + +# do we have numpy here? +import numpy as np + +from .sets_representation import SolFiniteSetRepresentation +from .posets_product import MyFinitePosetProduct +from .posets_sum import MyFinitePosetDisjointUnion import act4e_interfaces as I +X = TypeVar("X") + +class MyFinitePoset(I.FinitePoset[X]): + _carrier: I.FiniteSet[X] + _values: List[Tuple[X,X]] + + # Implementation using adjacency and reachability matrix + _adjacency: np.ndarray + _paths: np.ndarray + + def __init__(self, carrier: I.FiniteSet[X], values: List[Tuple[X,X]]): + self._carrier = carrier + self._values = values + self._paths = np.eye(carrier.size(), dtype=bool) + + if self._values: + self._compute_paths_naive() + # self._compute_paths_fast() + + def _compute_paths_naive(self): + # Create adjancency matrix. Because poset can be represented as a hasse + # diagram, which is the same as a directed graph we can create an + # adjacency matrix for the graph of the relation. In particular when + # the graph is acyclic the adjancency matrix is nilpotent. Even if the + # graph contains cycles we can still precompute a reachability matrix + # and check in O(1) whether there is a relation between two elements + + n = self._carrier.size() + # We use booleans to avoid overflow, we do not care how long the path + # is, only whether it exists or not + self._adjacency = np.zeros((n, n), dtype=bool) + + # Build adjacency matrix + for a, b in self._values: + ia = self._carrier.elements().index(a) + ib = self._carrier.elements().index(b) + self._adjacency[ia][ib] = True + + # Compute the reachability matrix, i.e. a power series of the adjacency + # matrix if the adjacency matrix is nilpotent the power series is + # finite, otherwise it is not, but this is not a problem since we can + # upper bound the number of terms needed in this case with the number + # of nodes + self._paths = np.eye(n, dtype=bool) + adjpow = np.eye(n, dtype=bool) + for _ in range(n): + # compute the p-th power of the adjacency matrix and add it to the + # series. + adjpow = (adjpow @ self._adjacency > 0) + self._paths = np.logical_or(self._paths, adjpow) + + # if the graph is acylic we stop earlier + if np.allclose(adjpow, 0): + break + + # if not np.allclose(adjpow, 0): + # print(f"Adjacency matrix may not be nilpotent! Ran for {_} " + # + "iterations and there are nonzero entries, " + # + f"the graph ({n} nodes) may contain cycles") + + # print(f"Computed path matrix for poset with elements {self._carrier.elements()}:") + # print(self._paths.astype(int)) + + def carrier(self) -> I.FiniteSet[X]: + return self._carrier + + def holds(self, a: X, b: X) -> bool: + # a is smaller than b, means that there is a path in the graph from a to b + if self._has_path(a, b): + return True + + return False + + def _cmp(self, a: X, b: X) -> bool: + assert self._carrier.contains(a) + assert self._carrier.contains(b) + + # a is both smaller and bigger than b + # i.e. they are equivalent + if self._has_path(a, b) and self._has_path(b, a): + return 0 + + # a is smaller than b + if self._has_path(a, b): + return 1 + + # b is smaller than a, or + # a is bigger than b + if self._has_path(b, a): + return -1 + + # else not comparable + raise RuntimeError(f"Cannot compare {a} with {b}.") + + + def _has_path(self, a: X, b: X) -> bool: + ia = self._carrier.elements().index(a) + ib = self._carrier.elements().index(b) + + # if self._paths[ia][ib] > 0: + # print(f"The path from {a = } to {b = } has length {self._paths[ia][ib]}") + + return self._paths[ia][ib] > 0 + + class SolFinitePosetRepresentation(I.FinitePosetRepresentation): def load(self, h: I.IOHelper, s: I.FinitePoset_desc) -> I.FinitePoset[Any]: - raise NotImplementedError() + if "poset_product" in s.keys(): + posets = [self.load(h, p) for p in s["poset_product"]] + return MyFinitePosetProduct(posets) + + if "poset_sum" in s.keys(): + posets = [self.load(h, p) for p in s["poset_sum"]] + return MyFinitePosetDisjointUnion(posets) + + if not all(k in s.keys() for k in ["carrier", "hasse"]): + raise I.InvalidFormat() + + fsr = SolFiniteSetRepresentation() + X = fsr.load(h, s["carrier"]) + + return MyFinitePoset(X, s["hasse"]) def save(self, h: I.IOHelper, p: I.FinitePoset[Any]) -> I.FinitePoset_desc: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + d = {"carrier": fsr.save(h, p.carrier()), + "hasse": []} + + for a in p.carrier().elements(): + for b in p.carrier().elements(): + if p.holds(a, b): + d["hasse"].append([a, b]) + + return d + + diff --git a/src/act4e_solutions/posets_sum.py b/src/act4e_solutions/posets_sum.py index a797a14..c26a6e5 100644 --- a/src/act4e_solutions/posets_sum.py +++ b/src/act4e_solutions/posets_sum.py @@ -1,11 +1,39 @@ -from typing import Any, overload, Sequence, TypeVar +from typing import Any, overload, Sequence, TypeVar, Tuple + +from .sets_sum import MyFiniteSetDisjointUnion import act4e_interfaces as I -X = TypeVar("X") +C = TypeVar("C") +E = Tuple[int, C] + +class MyFinitePosetDisjointUnion(I.FinitePosetDisjointUnion[C, E]): + _posets: Sequence[I.FinitePoset[C]] + _carrier: I.FiniteSetDisjointUnion[C, E] + def __init__(self, posets: Sequence[I.FinitePoset[C]]): + self._posets = posets + self._carrier = MyFiniteSetDisjointUnion(p.carrier() for p in posets) + + def components(self) -> Sequence[I.FinitePoset[C]]: + return self._posets + + def carrier(self) -> I.FiniteSetDisjointUnion[C, E]: + return self._carrier + + def holds(self, a: E, b: E): + ia, va = self._carrier.unpack(a) + ib, vb = self._carrier.unpack(b) + + if ia != ib: + return False + + return self._posets[ia].holds(va, vb) + + +X = TypeVar("X") class SolFinitePosetConstructionSum(I.FinitePosetConstructionSum): def disjoint_union(self, ps: Sequence[I.FinitePoset[X]]) -> I.FinitePosetDisjointUnion[X, Any]: - raise NotImplementedError() # implement here + return MyFinitePosetDisjointUnion(ps) diff --git a/src/act4e_solutions/relations.py b/src/act4e_solutions/relations.py index 26f90a7..4fba1f1 100644 --- a/src/act4e_solutions/relations.py +++ b/src/act4e_solutions/relations.py @@ -3,6 +3,8 @@ from typing import Any, TypeVar import act4e_interfaces as I from act4e_interfaces import FiniteRelation +from .relations_representation import MyFiniteRelation + E1 = TypeVar("E1") E2 = TypeVar("E2") E3 = TypeVar("E3") @@ -14,24 +16,64 @@ B = TypeVar("B") class SolFiniteRelationProperties(I.FiniteRelationProperties): def is_surjective(self, fr: I.FiniteRelation[Any, Any]) -> bool: - raise NotImplementedError() + # for all y in B there is an x in A s.t. x R y + # converse: there is a y in B s.t. for all x in A there is no x R y + for y in fr.target().elements(): + there_is_one = any([fr.holds(x, y) for x in fr.source().elements()]) + if not there_is_one: + return False + return True def is_defined_everywhere(self, fr: I.FiniteRelation[Any, Any]) -> bool: - raise NotImplementedError() + # for all x in A there is a y in B s.t. x R y + # converse: there is an x in A s.t. for all y in B there is no x R y + for x in fr.source().elements(): + there_is_one = any([fr.holds(x, y) for y in fr.target().elements()]) + if not there_is_one: + return False + return True def is_injective(self, fr: I.FiniteRelation[Any, Any]) -> bool: - raise NotImplementedError() + # x R y and z R y implies z = x + # converse: there is a z neq y such that x R y and z R y + image = [] + for y in fr.target().elements(): + for x in fr.source().elements(): + if fr.holds(x, y): + if y in image: + return False + image.append(y) + return True def is_single_valued(self, fr: I.FiniteRelation[Any, Any]) -> bool: - raise NotImplementedError() + # x R y and x R u imply y = u + # converse: there is an y neq u such that x R y and x R u + domain = [] + for x in fr.source().elements(): + for y in fr.target().elements(): + if fr.holds(x, y): + if x in domain: + return False + domain.append(x) + return True class SolFiniteRelationOperations(I.FiniteRelationOperations): def transpose(self, fr: I.FiniteRelation[A, B]) -> I.FiniteRelation[B, A]: - raise NotImplementedError() + # reverses the arrows in the relation + values = [] + for a in fr.source().elements(): + for b in fr.target().elements(): + if fr.holds(a, b): + values.append([b, a]) + return MyFiniteRelation(fr.target(), fr.source(), values) def as_relation(self, f: I.FiniteMap[A, B]) -> I.FiniteRelation[A, B]: - raise NotImplementedError() + values = [] + for a in f.source().elements(): + values.append([a, f(a)]) + + return MyFiniteRelation(f.source(), f.target(), values) class SolFiniteEndorelationProperties(I.FiniteEndorelationProperties): @@ -61,4 +103,14 @@ class SolFiniteEndorelationOperations(I.FiniteEndorelationOperations): class SolFiniteRelationCompose(I.FiniteRelationCompose): def compose(self, fr1: FiniteRelation[E1, E2], fr2: FiniteRelation[E2, E3]) -> I.FiniteRelation[E1, E3]: - raise NotImplementedError() + values = [] + # Yeah O(n^3), i really should do this better + for a in fr1.source().elements(): + for b in fr1.target().elements(): + for c in fr2.target().elements(): + if fr1.holds(a, b) and fr2.holds(b, c): + values.append([a, c]) + + return MyFiniteRelation(fr1.source(), fr2.target(), values) + + diff --git a/src/act4e_solutions/relations_representation.py b/src/act4e_solutions/relations_representation.py index 69ccdf0..a7fec7f 100644 --- a/src/act4e_solutions/relations_representation.py +++ b/src/act4e_solutions/relations_representation.py @@ -1,14 +1,66 @@ -from typing import TypeVar +from typing import TypeVar, List, Tuple import act4e_interfaces as I +from .sets_representation import SolFiniteSetRepresentation A = TypeVar("A") B = TypeVar("B") +class MyFiniteRelation(I.FiniteRelation[A,B]): + _source: I.FiniteSet[A] + _target: I.FiniteSet[B] + _values: List[Tuple[A,B]] + + def __init__(self, source: I.FiniteSet[A], target: I.FiniteSet[B], values: List[Tuple[A,B]]): + self._source = source + self._target = target + self._values = values + + def source(self) -> I.FiniteSet[A]: + return self._source + + def target(self) -> I.FiniteSet[B]: + return self._target + + def holds(self, a: A, b: B) -> bool: + for v, u in self._values: + if self._source.equal(v, a) and self._target.equal(u, b): + return True + return False + class SolFiniteRelationRepresentation(I.FiniteRelationRepresentation): def load(self, h: I.IOHelper, data: I.FiniteRelation_desc) -> I.FiniteRelation[A, B]: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + src = fsr.load(h, data["source"]) + dst = fsr.load(h, data["target"]) + values = [] + + for v in data["values"]: + a, b = src.load(h, v[0]), dst.load(h, v[1]) + + if not src.contains(a): + raise I.InvalidFormat() + + if not dst.contains(b): + raise I.InvalidFormat() + + values.append([a, b]) + + return MyFiniteRelation(src, dst, values) def save(self, h: I.IOHelper, f: I.FiniteRelation[A, B]) -> I.FiniteRelation_desc: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + d = { + "source": fsr.save(h, f.source()), + "target": fsr.save(h, f.target()), + "values": [], + } + + for a in f.source().elements(): + for b in f.target().elements(): + if f.holds(a, b): + d["values"].append([ + f.source().save(h, a), + f.target().save(h, b)]) + return d diff --git a/src/act4e_solutions/semicategory_representation.py b/src/act4e_solutions/semicategory_representation.py index 860a451..4ab9909 100644 --- a/src/act4e_solutions/semicategory_representation.py +++ b/src/act4e_solutions/semicategory_representation.py @@ -1,10 +1,120 @@ -from typing import Callable, Generic, Optional, TypeVar +from typing import Callable, Generic, Optional, TypeVar, List, Dict, Iterator, Tuple import act4e_interfaces as I from act4e_interfaces import EnumerableSet -OD = TypeVar("OD") -MD = TypeVar("MD") +from .sets_representation import MyFiniteSet + +from dataclasses import dataclass +from functools import reduce +from itertools import product + + +E = TypeVar("E") +OD = TypeVar("OD") # Type of the objects +MD = TypeVar("MD") # Type of the morphisms + +ROD = I.RichObject[OD] +RMD = I.RichMorphism[MD] + + +class MySemiCategory(Generic[OD, MD], I.SemiCategory[ROD, RMD]): + _objects: Dict[str, ROD] + _morphisms: Dict[int, Dict[Tuple[str, str], List[RMD]]] + _composition: Callable[[OD, OD, OD, MD], MD] + _equations: Dict[str, List[str]] + + def __init__( + self, + composition: Callable[[OD, OD, OD, MD, MD], MD], + equations: Dict[str, str], + ): + self._objects = {} + self._morphisms = {0: {}} + self._composition = composition + self._equations = equations + + def add_object(self, ob: ROD): + self._objects[ob.label] = ob + + def get_object(self, label: str): + return self._objects[label] + + def add_morphism(self, source: str, target: str, mor: RMD): + if not (source, target) in self._morphisms[0].keys(): + self._morphisms[0][source, target] = [] + self._morphisms[0][source, target].append(mor) + + def objects(self, uptolevel: Optional[int] = None) -> EnumerableSet[ROD]: + return MyFiniteSet(self._objects.values()) + + def hom(self, ob1: ROD, ob2: ROD, uptolevel: Optional[int] = None) -> EnumerableSet[RMD]: + def all_morphisms(source, target, lvl): + """ return all morphisms up to level lvl: """ + # Base case, for level zero return given morphisms + if lvl <= 0: + return self._morphisms[0].get((source, target), []) + + # We need to compute the morphisms for this level + if lvl not in self._morphisms.keys(): + self._morphisms[lvl] = {} + # For all intermediate object + for interm, interm_ob in self._objects.items(): + # Compute all paths through that interm object + fs = self._morphisms[lvl - 1].get((source, interm), []) + gs = all_morphisms(interm, target, lvl - 1) + + # Build all possible compositions + not_id = lambda m: not m.label.startswith("id_") + for f, g in product(filter(not_id, fs), filter(not_id, gs)): + # Compose the morphisms + source_ob = self._objects[source] + target_ob = self._objects[target] + h = self.compose(source_ob, interm_ob, target_ob, f, g) + + # Create entry in cache if not present + if (source, target) not in self._morphisms[lvl]: + self._morphisms[lvl][source, target] = [] + + # If the composition is in an equation have to replace it + if h.label in self._equations.keys(): + # Find the morphisms that compose the right hand side + rhs_morphisms = [] + for (s, d), mors in self._morphisms[0].items(): + for mor, f in product(mors, self._equations[h.label]): + if mor.label == f: + rhs_morphisms.append((s, d, mor)) + + # Build the RHS rich morphism object + compose = lambda m1, m2: self.compose(m1[0], m1[1], m2[0], m1[2], m2[2]) + _, _, rhs = reduce(compose, rhs_morphisms[1:], rhs_morphisms[0]) + + # Save this one instead of h + self._morphisms[lvl][source, target].append(rhs) + continue + + # Save the new morphism + self._morphisms[lvl][source, target].append(h) + + # Compute the union + morphisms = [] + for l in range(lvl + 1): + morphisms += self._morphisms[l].get((source, target), []) + + return morphisms + + morphisms = all_morphisms(ob1.label, ob2.label, uptolevel or 0) + return MyFiniteSet(morphisms) + + def compose(self, ob1: ROD, ob2: ROD, ob3: ROD, m1: RMD, m2: RMD) -> RMD: + m3 = self._composition(ob1.obdata, ob2.obdata, ob3.obdata, m1.mordata, m2.mordata) + return I.RichMorphism(";".join((m1.label, m2.label)), m3) + + def identity(self, ob: ROD) -> RMD: + if not self._objects[ob.label]: + raise I.InvalidValue() + + return self._objects[ob.label].identity class SolSemiCategoryRepresentation(I.SemiCategoryRepresentation): @@ -16,26 +126,33 @@ class SolSemiCategoryRepresentation(I.SemiCategoryRepresentation): MorData: I.Setoid[MD], compose: Callable[[OD, OD, OD, MD, MD], MD], ) -> I.SemiCategory[I.RichObject[OD], I.RichMorphism[MD]]: - raise NotImplementedError() + if not all(k in data.keys() for k in ["objects", "morphisms", "equations"]): + raise I.InvalidFormat() + equations = {} + for eq_name, eq in data["equations"].items(): + lhs, rhs = eq.split("=") + equations[lhs] = rhs.split(";") -class SolSemiCategory(Generic[OD, MD], I.SemiCategory[I.RichObject[OD], I.RichMorphism[MD]]): - """ Skeleton for a class implementing SemiCategory.""" + sc = MySemiCategory(compose, equations) - def __init__( - self, - add, more, parameters, here - ): - raise NotImplementedError + # Get the objects + for obname, ob in data["objects"].items(): + if not "obdata" in ob.keys(): + raise I.InvalidFormat() - def objects(self, uptolevel: Optional[int] = None) -> EnumerableSet[OD]: - raise NotImplementedError + if "identity" in ob.keys() and ob["identity"]: + identity = I.RichMorphism(f"id_{obname}", ob["identity"]["mordata"]) + sc.add_morphism(obname, obname, identity) - def hom(self, ob1: OD, ob2: OD, uptolevel: Optional[int] = None) -> EnumerableSet[MD]: - raise NotImplementedError + sc.add_object(I.RichObject(obname, ob["obdata"])) + + # Get the morphisms + for morname, mor in data["morphisms"].items(): + if not all(k in mor.keys() for k in ["mordata", "source", "target"]): + raise I.InvalidFormat() - def compose(self, ob1: OD, ob2: OD, ob3: OD, m1: MD, m2: MD) -> MD: - raise NotImplementedError + src, tar = mor["source"], mor["target"] + sc.add_morphism(mor["source"], mor["target"], I.RichMorphism(morname, mor["mordata"])) - def identity(self, ob: OD) -> MD: - raise NotImplementedError + return sc diff --git a/src/act4e_solutions/semigroups_morphisms.py b/src/act4e_solutions/semigroups_morphisms.py index 7c48610..5d832ee 100644 --- a/src/act4e_solutions/semigroups_morphisms.py +++ b/src/act4e_solutions/semigroups_morphisms.py @@ -1,16 +1,49 @@ from typing import Any, TypeVar +from .semigroups_representation import MyFiniteSemigroup, MyFiniteMonoid, MyFiniteGroup + import act4e_interfaces as I + A = TypeVar("A") B = TypeVar("B") class SolFiniteSemigroupMorphismsChecks(I.FiniteSemigroupMorphismsChecks): def is_semigroup_morphism(self, a: I.FiniteSemigroup[A], b: I.FiniteSemigroup[B], f: I.FiniteMap[A, B]) -> bool: - raise NotImplementedError + # Semigroup preserves the structure + # f(xy) = f(x) f(y) for all x, y in a + # converse: + # there is an x or a y in a such that + # f(xy) neq f(x) f(y) + for x in a.carrier().elements(): + for y in a.carrier().elements(): + inside = f(a.compose(x, y)) + outside = b.compose(f(x), f(y)) + if not b.carrier().equal(inside, outside): + return False + return True def is_monoid_morphism(self, a: I.FiniteMonoid[A], b: I.FiniteMonoid[B], f: I.FiniteMap[A, B]) -> bool: - raise NotImplementedError + # Monoid morphism is a semigroup morphism that maps identity to identity + if not self.is_semigroup_morphism(a, b, f): + return False + + if not b.carrier().equal(b.identity(), f(a.identity())): + return False + + return True + def is_group_morphism(self, a: I.FiniteGroup[A], b: I.FiniteGroup[B], f: I.FiniteMap[A, B]) -> bool: - raise NotImplementedError + # Group morphism preserve + # f(xy) = f(x)f(y) for all x, y in a + # converse is + # exists x, y in a such that + # f(xy) neq f(x)f(y) + for x in a.carrier().elements(): + for y in a.carrier().elements(): + inside = f(a.compose(x, y)) + outside = b.compose(f(x), f(y)) + if not b.carrier().equal(inside, outside): + return False + return True diff --git a/src/act4e_solutions/semigroups_morphisms_representation.py b/src/act4e_solutions/semigroups_morphisms_representation.py index 43df89f..abc2216 100644 --- a/src/act4e_solutions/semigroups_morphisms_representation.py +++ b/src/act4e_solutions/semigroups_morphisms_representation.py @@ -2,26 +2,113 @@ from typing import Any, TypeVar import act4e_interfaces as I +from .maps_representation import SolFiniteMapRepresentation +from .semigroups_representation import (MyFiniteSemigroup, MyFiniteMonoid, MyFiniteGroup, + SolFiniteSemigroupRepresentation, + SolFiniteMonoidRepresentation, + SolFiniteGroupRepresentation) + +A = TypeVar("A") +B = TypeVar("B") + +class MyFiniteSemigroupMorphism(I.FiniteSemigroupMorphism[A, B]): + _source: I.FiniteSemigroup[A] + _target: I.FiniteSemigroup[B] + _mapping: I.FiniteMap[A, B] + + def __init__(self, s: I.FiniteSemigroup[A], t: I.FiniteSemigroup[B], f: I.FiniteMap[A, B]): + self._source = s + self._target = t + self._mapping = f + + def source(self) -> I.FiniteSemigroup[A]: + return self._source + + def target(self) -> I.FiniteSemigroup[B]: + return self._target + + def mapping(self) -> I.FiniteMap[A, B]: + return self._mapping + + +class MyFiniteMonoidMorphism(MyFiniteSemigroupMorphism, I.FiniteMonoidMorphism[A, B]): + _source: I.FiniteMonoid[A] + _target: I.FiniteMonoid[B] + + +class MyFiniteGroupMorphism(MyFiniteMonoidMorphism, I.FiniteGroupMorphism[A, B]): + _source: I.FiniteGroup[A] + _target: I.FiniteGroup[B] + + class SolFiniteSemigroupMorphismRepresentation(I.FiniteSemigroupMorphismRepresentation): def load(self, h: I.IOHelper, s: I.FiniteSemigroupMorphism_desc) -> I.FiniteSemigroupMorphism[Any, Any]: - raise NotImplementedError() + if not all(k in s.keys() for k in ["source", "target", "mapping"]): + raise I.InvalidFormat() + + fsgr = SolFiniteSemigroupRepresentation() + fmr = SolFiniteMapRepresentation() + + A = fsgr.load(h, s["source"]) + B = fsgr.load(h, s["target"]) + f = fmr.load(h, s["mapping"]) + + return MyFiniteSemigroupMorphism(A, B, f) def save(self, h: I.IOHelper, m: I.FiniteSemigroupMorphism[Any, Any]) -> I.FiniteSemigroupMorphism_desc: - raise NotImplementedError() + fsgr = SolFiniteSemigroupRepresentation() + fmr = SolFiniteMapRepresentation() + + d = {"source": fsgr.save(h, m.source()), + "target": fsgr.save(h, m.target()), + "mapping": fmr.save(h, m.mapping())} + return d class SolFiniteMonoidMorphismRepresentation(I.FiniteMonoidMorphismRepresentation): def load(self, h: I.IOHelper, s: I.FiniteMonoidMorphism_desc) -> I.FiniteMonoidMorphism[Any, Any]: - raise NotImplementedError() + if not all(k in s.keys() for k in ["source", "target", "mapping"]): + raise I.InvalidFormat() + + fmor = SolFiniteMonoidRepresentation() + fmr = SolFiniteMapRepresentation() + + A = fmor.load(h, s["source"]) + B = fmor.load(h, s["target"]) + f = fmr.load(h, s["mapping"]) + + return MyFiniteMonoidMorphism(A, B, f) def save(self, h: I.IOHelper, m: I.FiniteMonoidMorphism[Any, Any]) -> I.FiniteMonoidMorphism_desc: - raise NotImplementedError() + fmor = SolFiniteMonoidRepresentation() + fmr = SolFiniteMapRepresentation() + + d = {"source": fmor.save(h, m.source()), + "target": fmor.save(h, m.target()), + "mapping": fmr.save(h, m.mapping())} + return d class SolFiniteGroupMorphismRepresentation(I.FiniteGroupMorphismRepresentation): def load(self, h: I.IOHelper, s: I.FiniteGroupMorphism_desc) -> I.FiniteGroupMorphism[Any, Any]: - raise NotImplementedError() + if not all(k in s.keys() for k in ["source", "target", "mapping"]): + raise I.InvalidFormat() + + fgr = SolFiniteGroupRepresentation() + fmr = SolFiniteMapRepresentation() + + A = fgr.load(h, s["source"]) + B = fgr.load(h, s["target"]) + f = fmr.load(h, s["mapping"]) + + return MyFiniteGroupMorphism(A, B, f) def save(self, h: I.IOHelper, m: I.FiniteGroupMorphism[Any, Any]) -> I.FiniteGroupMorphism_desc: - raise NotImplementedError() + fgr = SolFiniteGroupRepresentation() + fmr = SolFiniteMapRepresentation() + + d = {"source": fgr.save(h, m.source()), + "target": fgr.save(h, m.target()), + "mapping": fmr.save(h, m.mapping())} + return d diff --git a/src/act4e_solutions/semigroups_representation.py b/src/act4e_solutions/semigroups_representation.py index 4d75708..f5c2780 100644 --- a/src/act4e_solutions/semigroups_representation.py +++ b/src/act4e_solutions/semigroups_representation.py @@ -1,29 +1,131 @@ from typing import Any, TypeVar import act4e_interfaces as I +from .sets_representation import MyFiniteSet, SolFiniteSetRepresentation +from .sets_product import MyFiniteSetProduct +from .maps_representation import MyFiniteMap, SolFiniteMapRepresentation X = TypeVar("X") +class MyFiniteSemigroup(I.FiniteSemigroup[X]): + _carrier: I.FiniteSet[X] + _composition: I.FiniteMap[X, X] + + def __init__(self, s: I.FiniteSet[X], f: I.FiniteMap[X, X]): + self._carrier = s + self._composition = f + + def carrier(self) -> I.FiniteSet[X]: + return self._carrier + + def composition(self) -> I.FiniteMap[X, X]: + return self._composition + + def compose(self, a: X, b: X) -> X: + p = self._composition.source().pack([a, b]) + return self._composition(p) + + +class MyFiniteMonoid(MyFiniteSemigroup, I.FiniteMonoid[X]): + _identity: X + def __init__(self, s: I.FiniteSet[X], f: I.FiniteMap[X, X], e: X): + super().__init__(s, f) + self._identity = e + + # def compose(self, a: X, b: X) -> X: + # if self.carrier().equal(a, self._identity): + # return b + # elif self.carrier().equal(b, self._identity): + # return a + # else: + # return super().compose(a, b) + + def identity(self) -> X: + return self._identity + + +class MyFiniteGroup(MyFiniteMonoid, I.FiniteGroup[X]): + _inverse: I.FiniteMap[X, X] + def __init__(self, s: I.FiniteSet[X], f: I.FiniteMap[X, X], e: X, i: I.FiniteMap[X, X]): + super().__init__(s, f, e) + self._inverse = i + + def inverse(self, a: X): + return self._inverse(a) + class SolFiniteSemigroupRepresentation(I.FiniteSemigroupRepresentation): def load(self, h: I.IOHelper, s: I.FiniteSemigroup_desc) -> I.FiniteSemigroup[Any]: - raise NotImplementedError() + if not all(k in s.keys() for k in ["carrier", "composition"]): + raise I.InvalidFormat() + + fsr = SolFiniteSetRepresentation() + A = fsr.load(h, s["carrier"]) + + # FIXME: maybe use this? + # fmr = SolFiniteMapRepresentation() + for inp, out in s["composition"]: + if not all(A.contains(i) for i in inp): + raise I.InvalidFormat() + + if not A.contains(out): + raise I.InvalidFormat() + + p = MyFiniteSetProduct([A, A]) + f = MyFiniteMap(p, A, s["composition"]) + return MyFiniteSemigroup(A, f) def save(self, h: I.IOHelper, m: I.FiniteSemigroup[Any]) -> I.FiniteSemigroup_desc: - raise NotImplementedError() + fsr = SolFiniteSetRepresentation() + fmr = SolFiniteMapRepresentation() + + d = {"carrier": fsr.save(h, m.carrier()), + "composition": []} + + for a in m.carrier().elements(): + for b in m.carrier().elements(): + e = m.composition().source().pack([a, b]) + d["composition"].append([e, m.compose(a, b)]) + + return d class SolFiniteMonoidRepresentation(I.FiniteMonoidRepresentation): def load(self, h: I.IOHelper, s: I.FiniteMonoid_desc) -> I.FiniteMonoid[X]: - raise NotImplementedError() + fsgr = SolFiniteSemigroupRepresentation() + semi = fsgr.load(h, s) + + if not ("neutral" in s.keys()): + raise I.InvalidFormat() + + e = s["neutral"] + if not semi.carrier().contains(e): + raise I.InvalidFormat() + + return MyFiniteMonoid(semi.carrier(), semi.composition(), e) def save(self, h: I.IOHelper, m: I.FiniteMonoid[Any]) -> I.FiniteMonoid_desc: - raise NotImplementedError() + fsgr = SolFiniteSemigroupRepresentation() + d = fsgr.save(h, m) + d["neutral"] = m.identity() + return d class SolFiniteGroupRepresentation(I.FiniteGroupRepresentation): def load(self, h: I.IOHelper, s: I.FiniteGroup_desc) -> I.FiniteGroup[X]: - raise NotImplementedError() + fmor = SolFiniteMonoidRepresentation() + m = fmor.load(h, s) + + if not "inverse" in s.keys(): + raise I.InvalidFormat() + + i = MyFiniteMap(m.carrier(), m.carrier(), s["inverse"]) + return MyFiniteGroup(m.carrier(), m.composition(), m.identity(), i) def save(self, h: I.IOHelper, m: I.FiniteGroup[Any]) -> I.FiniteGroup_desc: - raise NotImplementedError() + fmor = SolFiniteMonoidRepresentation() + d = fmor.save(h, m) + d["inverse"] = [] + for c in m.carrier().elements(): + d["inverse"].append([c, m.inverse(c)]) + return d diff --git a/src/act4e_solutions/sets_power.py b/src/act4e_solutions/sets_power.py index 49b4b7b..1e7ec74 100644 --- a/src/act4e_solutions/sets_power.py +++ b/src/act4e_solutions/sets_power.py @@ -1,11 +1,70 @@ -from typing import Any, overload, TypeVar +from typing import Any, TypeVar, Iterator, Collection, List +import itertools + +from .sets_representation import MyFiniteSet +from .sets_properties import SolFiniteSetProperties import act4e_interfaces as I X = TypeVar("X") +C = TypeVar("C") # Type of elements of set +E = MyFiniteSet[C] # Type of sets + + +class MyFiniteSetOfFiniteSubsets(I.FiniteSetOfFiniteSubsets[C, E]): + # FIXME: _set could be removed + _set: I.FiniteSet[C] + _subsets: List[I.FiniteSet[C]] + + def __init__(self, theset: I.FiniteSet[C], subsets: Collection[I.FiniteSet[C]]): + self._set = theset + self._subsets = subsets + + self.fsp = SolFiniteSetProperties() + assert(self.fsp.is_subset(s, theset) for s in subsets) + + def size(self) -> int: + return len(self._subsets) + + def contains(self, x: E): + # print(f"Checking whether {x.elements()} is contained in " + + # str(list(map(lambda l: l.elements(), self._subsets)))) + + # Heuristic filter to make it a bit faster + same_size = lambda s: s.size() == x.size() + for s in filter(same_size, self._subsets): + if self.fsp.equal(x, s): + # print("it is in there!") + return True + + return False + + def elements(self): + return self._subsets + + def save(self, h: I.IOHelper, x: E) -> List[E]: + # FIXME: I don't think this is correct, same problem as in save + return cast(I.ConcreteRepr, x) + + def load(self, h: I.IOHelper, o: I.ConcreteRepr): + # FIXME: what the f am I supposed to do here + return cast(E, o) + + def contents(self, e: E) -> Iterator[C]: + return e.elements() + + def construct(self, elements: Collection[C]) -> E: + return MyFiniteSet(elements) + class SolFiniteMakePowerSet(I.FiniteMakePowerSet): def powerset(self, s: I.FiniteSet[X]) -> I.FiniteSetOfFiniteSubsets[X, Any]: - raise NotImplementedError() # implement here + subsets = [MyFiniteSet([]), s] + for i in range(1, s.size()): + # generate all possible subsets with i elements + for comb in itertools.combinations(s.elements(), i): + subsets.append(MyFiniteSet(list(comb))) + + return MyFiniteSetOfFiniteSubsets(s, subsets) diff --git a/src/act4e_solutions/sets_product.py b/src/act4e_solutions/sets_product.py index bdba104..508fd45 100644 --- a/src/act4e_solutions/sets_product.py +++ b/src/act4e_solutions/sets_product.py @@ -1,11 +1,65 @@ -from typing import Any, Sequence, TypeVar +from functools import reduce +from collections.abc import Iterable +from typing import Any, Sequence, TypeVar, List, Iterator, cast +from math import prod import act4e_interfaces as I -X = TypeVar("X") +C = TypeVar("C") # Type of components, "factors", are setoids +E = List[C] # Type of product, i.e. that holds components -class SolFiniteMakeSetProduct(I.FiniteMakeSetProduct): +class MyFiniteSetProduct(I.FiniteSetProduct[C, E]): + _components: E + def __init__(self, components: E): + self._components = components + + # Set behaviour + def size(self) -> int: + return prod(map(lambda c: c.size(), self._components)) + + def contains(self, x: E) -> bool: + if not isinstance(x, Iterable): + return False + + if len(x) != len(self._components): + return False + + for (e, s) in zip(x, self._components): + if not s.contains(e): + print(f"{s} does not contain {e}") + return False + + return True + + def elements(self) -> Iterator[E]: + def all_combinations(last, new): + return [l + [n] for l in last for n in new] + + parts = list(map(lambda c: list(c.elements()), self._components)) + elements = list(reduce(all_combinations, parts, [[]])) + + return elements + def save(self, h: I.IOHelper, x: E) -> I.ConcreteRepr: + return cast(I.ConcreteRepr, x) + + def load(self, h: I.IOHelper, o: I.ConcreteRepr): + return cast(E, o) + + # Product behaviour + def components(self) -> Sequence[I.FiniteSet[C]]: + return self._components + + def pack(self, args: Sequence[C]) -> E: + return cast(E, args) + + def unpack(self, args: E) -> Sequence[C]: + return cast(Sequence[C], args) + + +X = TypeVar("X") + +class SolFiniteMakeSetProduct(I.FiniteMakeSetProduct): def product(self, components: Sequence[I.FiniteSet[X]]) -> I.FiniteSetProduct[X, Any]: - raise NotImplementedError() # implement here + return MyFiniteSetProduct(components) diff --git a/src/act4e_solutions/sets_properties.py b/src/act4e_solutions/sets_properties.py index 5390d23..0d6b3fc 100644 --- a/src/act4e_solutions/sets_properties.py +++ b/src/act4e_solutions/sets_properties.py @@ -7,7 +7,14 @@ X = TypeVar("X") class SolFiniteSetProperties(I.FiniteSetProperties): def is_subset(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool: - raise NotImplementedError() + """ is a a subset of b ? """ + return all([b.contains(e) for e in a.elements()]) + + def equal(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool: + return self.is_subset(a, b) and self.is_subset(b, a) + + def is_strict_subset(self, a: I.FiniteSet[X], b: I.FiniteSet[X]) -> bool: + return self.is_subset(a, b) and not self.is_subset(b, a) class SolFiniteMakeSetUnion(I.FiniteMakeSetUnion): diff --git a/src/act4e_solutions/sets_representation.py b/src/act4e_solutions/sets_representation.py index 7f3e818..9e231c1 100644 --- a/src/act4e_solutions/sets_representation.py +++ b/src/act4e_solutions/sets_representation.py @@ -1,11 +1,65 @@ -from typing import Any +from typing import Any, Collection, Iterator, List, TypeVar, cast import act4e_interfaces as I +from .sets_product import MyFiniteSetProduct + +E = TypeVar("E") + +class MyFiniteSet(I.FiniteSet[E]): + _elements: List[E] + def __init__(self, elements: Collection[E]): + self._elements = elements + + def size(self) -> int: + return len(self._elements) + + def contains(self, x: E) -> bool: + return any(map(lambda y: y == x, self._elements)) + + def elements(self) -> Iterator[E]: + return self._elements + + def save(self, h: I.IOHelper, x: E) -> List[E]: + return cast(I.ConcreteRepr, x) + + def load(self, h: I.IOHelper, o: I.ConcreteRepr): + return cast(E, o) class SolFiniteSetRepresentation(I.FiniteSetRepresentation): def load(self, h: I.IOHelper, data: I.FiniteSet_desc) -> I.FiniteSet[Any]: - raise NotImplementedError() + if not isinstance(data, dict): + raise I.InvalidFormat() + + if "elements" in data: + if not isinstance(data["elements"], list): + raise I.InvalidFormat() + + elements = data["elements"] + return MyFiniteSet(elements) + + elif "product" in data: + if not isinstance(data["product"], list): + raise I.InvalidFormat() + + components = [] + for comp in data["product"]: + if not isinstance(comp, dict): + raise I.InvalidFormat() + + if not "elements" in comp: + raise I.InvalidFormat() + + if not isinstance(comp["elements"], list): + raise I.InvalidFormat() + + components.append(MyFiniteSet(comp["elements"])) + + return MyFiniteSetProduct(components) + + else: + raise I.InvalidFormat() def save(self, h: I.IOHelper, f: I.FiniteSet[Any]) -> I.FiniteSet_desc: - raise NotImplementedError() + all_elements = [f.save(h, e) for e in f.elements()] + return {"elements": all_elements} diff --git a/src/act4e_solutions/sets_sum.py b/src/act4e_solutions/sets_sum.py index eab93d3..19f1969 100644 --- a/src/act4e_solutions/sets_sum.py +++ b/src/act4e_solutions/sets_sum.py @@ -1,10 +1,53 @@ -from typing import Any, Sequence, TypeVar +from typing import Any, Sequence, TypeVar, List, Tuple, cast import act4e_interfaces as I X = TypeVar("X") +C = TypeVar("C") +E = List # Tuple[int, C] + +class MyFiniteSetDisjointUnion(I.FiniteSetDisjointUnion[C, E]): + _components: List[I.FiniteSet[C]] + def __init__(self, components: Sequence[I.FiniteSet[C]]): + self._components = list(components) + + def contains(self, e: E): + i, val = e + return self._components[i].contains(val) + + def size(self): + return sum(c.size() for c in self._components) + + def save(self, h: I.IOHelper, x: E) -> I.ConcreteRepr: + return cast(I.ConcreteRepr, list(self.unpack(x))) + + def load(self, h: I.IOHelper, o: I.ConcreteRepr): + return cast(E, o) + + def elements(self) -> Sequence[E]: + es = [] + for i, c in enumerate(self._components): + for e in c.elements(): + es.append([i, e]) + + return es + + def components(self) -> Sequence[I.FiniteSet[C]]: + return self._components + + def pack(self, i: int, e: C) -> E: + if i < 0 or i > len(self._components): + raise I.InvalidValue + + if not self._components[i].contains(e): + raise I.InvalidValue + + return [i, e] + + def unpack(self, e: E) -> Tuple[int, C]: + return tuple(e) class SolFiniteMakeSetDisjointUnion(I.FiniteMakeSetDisjointUnion): def disjoint_union(self, components: Sequence[I.FiniteSet[X]]) -> I.FiniteSetDisjointUnion[X, Any]: - raise NotImplementedError() # implement here + return MyFiniteSetDisjointUnion(components) |