fall2023

1 files changed, 521 insertions, 20 deletions

diff --git a/src/act4e_mcdp_solution/solver_dp.py b/src/act4e_mcdp_solution/solver_dp.py
index 8a4d58c..d6d1a7a 100644
--- a/src/act4e_mcdp_solution/solver_dp.py
+++ b/src/act4e_mcdp_solution/solver_dp.py
@@ -1,29 +1,530 @@
-from act4e_mcdp import DPSolverInterface, Interval, LowerSet, PrimitiveDP, UpperSet
+from typing import Optional, TypeVar
+from act4e_mcdp import *  # type: ignore
+from decimal import Decimal
 
 __all__ = [
     "DPSolver",
 ]
 
 
+X = TypeVar("X")
+FT = TypeVar("FT")
+RT = TypeVar("RT")
+R1 = TypeVar("R1")
+R2 = TypeVar("R2")
+F1 = TypeVar("F1")
+F2 = TypeVar("F2")
+
+
 class DPSolver(DPSolverInterface):
-    def solve_dp_FixFunMinRes(
-        self,
-        dp: PrimitiveDP,
-        functionality_needed: object,
-        /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
+    # walkthrough: identity
+
+    def solve_dp_FixFunMinRes_IdentityDP(
+        self, _: IdentityDP[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[X]]:
+        # Easy: the minimal resources are the functionality itself
+        f = query.functionality
+        min_r = f
+        min_resources = UpperSet.principal(min_r)
+
+        # We need to return an interval of upper sets. It is a degenerate interval
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_IdentityDP(
+        self, _: IdentityDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[X]]:
+        # same as above, but we return lower sets
+
+        r = query.resources
+        max_f = r
+        max_functionalities = LowerSet.principal(max_f)
+        return Interval.degenerate(max_functionalities)
+
+    # walkthrough: constant resources
+
+    def solve_dp_FixFunMinRes_Constant(
+        self, dp: Constant[X], query: FixFunMinResQuery[tuple[()]]
+    ) -> Interval[UpperSet[X]]:
+        # The DP is a relation of the type
+        #
+        #    42 ≤ r
+
+        # The functionalities are the empty tuple
+
+        assert query.functionality == (), query.functionality
+
+        # The minimal resources do not depend on functionality
+        # They are the constant value of the DP
+
+        min_r = dp.c.value
+        min_resources = UpperSet.principal(min_r)
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_Constant(
+        self, dp: Constant[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[tuple[()]]]:
+        # The DP is a relation of the type
+        #
+        #    42 ≤ r
+
+        # Here we need to check whether the resources are at least 42
+
+        R = dp.R
+        if R.leq(dp.c.value, query.resources):
+            # the functionalities are the empty tuple
+            max_f = ()
+            return Interval.degenerate(LowerSet.principal(max_f))
+        else:
+            # the given budget is not enough
+            empty: LowerSet[tuple[()]] = LowerSet.empty()
+            return Interval.degenerate(empty)
+
+    # exercise: limit
+
+    def solve_dp_FixResMaxFun_Limit(self, dp: Limit[X], query: FixResMaxFunQuery[X]) -> Interval[LowerSet[X]]:
+        # The DP is a relation of the type
+        #
+        #    f ≤ 42
+
+        # This is the dual of Constant above. Swap functionalities and resources.
+
+        raise NotImplementedError
+
+    def solve_dp_FixFunMinRes_Limit(
+        self, dp: Limit[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[tuple[()]]]:
+        # The DP is a relation of the type
+        #
+        #    f ≤ 42
+
+        # This is the dual of Constant above. Swap functionalities and resources.
+
+        raise NotImplementedError
+
+    # walkthrough: ceil(f) <= r  DP
+
+    def solve_dp_FixFunMinRes_M_Ceil_DP(
+        self, dp: M_Ceil_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # In the documentation of the class M_Ceil_DP we have
+        # that the relation is defined as:
+        #
+        #   ceil(f) ≤ r
+
+        # Therefore, the minimal resources are the ceiling of the functionality
+        #   r >= ceil(f)
+        f = query.functionality
+        assert isinstance(f, Decimal)
+
+        # For M_Ceil_DP, the F and R posets are Numbers
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # Note: the f = +inf is a special case for which __ceil__() does not work
+        if f.is_infinite():
+            min_r = f
+        else:
+            # otherwise, we just use the ceil function
+            min_r = Decimal(f.__ceil__())
+
+        # now, one last detail: in general, the F poset can have
+        # different upper/lower bound or discretization than the R poset.
+        # We need to make sure that we provide a valid resource.
+
+        # There is a function largest_upperset_above() that will do this for us.
+        # See documentation there.
+
+        min_resources = R.largest_upperset_above(min_r)
+        return Interval.degenerate(min_resources)
+
+    def solve_dp_FixResMaxFun_M_Ceil_DP(
+        self, dp: M_Ceil_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # Now r is fixed
+        r = query.resources
+        assert isinstance(r, Decimal), r
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # For M_Ceil_DP, the F/R posets are Numbers
+
+        # first special case: r = +inf
+        if r.is_infinite():
+            max_f = r
+
+        else:
+            # what is the maximum f such that
+            #   ceil(f) <= r
+            # ?
+
+            # for example, if r = 13.2, then the maximum f is 13
+            # in fact, we obtain the floor of r
+
+            max_f = Decimal(r.__floor__())
+
+        # one last detail: we need to make sure that the functionality is valid
+        # for the F poset. We use the largest_lowerset_below() function in Numbers.
+        # See documentation there.
+
+        max_functionalities = F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(max_functionalities)
+
+    # exercise: floor relation
+
+    def solve_dp_FixFunMinRes_M_FloorFun_DP(
+        self, dp: M_FloorFun_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f <= floor(r)
+
+        # This is dual to M_Ceil_DP
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_M_FloorFun_DP(
+        self, dp: M_FloorFun_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= floor(r)
+
+        # This is dual to M_Ceil_DP
+
+        raise NotImplementedError
+
+    # exercise: catalogue
+
+    def solve_dp_FixFunMinRes_CatalogueDP(
+        self, dp: CatalogueDP[FT, RT], query: FixFunMinResQuery[FT]
+    ) -> Interval[UpperSet[RT]]:
+        f = query.functionality
+        F = dp.F
+
+        # Hint: iterate over the entries of the catalogue
+        name: str
+        entry_info: EntryInfo[FT, RT]
+        for name, entry_info in dp.entries.items():
+            # Then check if this entry is valid for the functionality
+            # In that case,  the resources of the entry are a valid solution
+            ...
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_CatalogueDP(
+        self, dp: CatalogueDP[FT, RT], query: FixResMaxFunQuery[RT]
+    ) -> Interval[LowerSet[FT]]:
+        # Same pattern as above, but functionalities and resources are swapped.
+
+        raise NotImplementedError
+
+    # exercise: series interconnections
+
+    def solve_dp_FixFunMinRes_DPSeries(
+        self, dp: DPSeries, query: FixFunMinResQuery[object]
     ) -> Interval[UpperSet[object]]:
-        optimistic = pessimistic = UpperSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
-
-    def solve_dp_FixResMaxFun(
-        self,
-        dp: PrimitiveDP,
-        resource_budget: object,
-        /,
-        resolution_optimistic: int = 0,
-        resolution_pessimistic: int = 0,
+        # This is the interconnection of a sequence of DPs.
+        # (You can assume that the sequence is at least 2 DPs).
+
+        # Hint: you should solve each DP in the sequence, and then
+        # pass it to the next.
+        # You can use the function self.solve_dp_FixFunMinRes() for this.
+
+        # Note 1: the solve_dp_FixFunMinRes_DPSeries() takes a single functionality.
+        # But in general the previous DP returns an upperset. You need to call it multiple times.
+        # Note 2: the solve_dp_FixFunMinRes_DPSeries() returns an *interval* of upper sets.
+        # Just treat the optimistic and pessimistic cases separately and then combine them in an interval.
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_DPSeries(
+        self, dp: DPSeries, query: FixResMaxFunQuery[object]
     ) -> Interval[LowerSet[object]]:
-        optimistic = pessimistic = LowerSet([])
-        return Interval(pessimistic=pessimistic, optimistic=optimistic)
+        # Hint: same as above, but go the other way...
+        raise NotImplementedError
+
+    # walkthrough: add a constant to functionalities ( f + constant <= r)
+
+    def solve_dp_FixFunMinRes_M_Res_AddConstant_DP(
+        self, dp: M_Res_AddConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        f: Decimal = query.functionality
+        assert isinstance(f, Decimal)
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # the relation is of the type
+        #
+        #    f + constant <= r
+
+        # therefore, the minimum resource is simply f + constant
+        min_r = f + dp.vu.value
+
+        # one last detail: we need to make sure that the resource is valid
+        # for the R poset. We use the largest_upperset_above() function in Numbers.
+        # See documentation there.
+        us = R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_M_Res_AddConstant_DP(
+        self, dp: M_Res_AddConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        r = query.resources
+        assert isinstance(r, Decimal)
+
+        R: Numbers = dp.R
+        F: Numbers = dp.F
+
+        # the relation is of the type
+        #
+        #    f + constant <= r
+
+        # therefore, the maximal functionality is r - constant
+
+        max_f = r - dp.vu.value
+
+        # one last detail: we need to make sure that the functionality is valid
+        # for the F poset. We use the largest_lowerset_below() function in Numbers.
+        # See documentation there.
+        ls = F.largest_lowerset_below(max_f)
+
+        return Interval.degenerate(ls)
+
+    # exercise: add a constant to resource ( f <= r + constant)
+
+    def solve_dp_FixFunMinRes_M_Fun_AddConstant_DP(
+        self, dp: M_Fun_AddConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f <= r + constant
+        # This is dual to the M_Res_AddConstant_DP case above.
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_M_Fun_AddConstant_DP(
+        self, dp: M_Fun_AddConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= r + constant
+        # This is dual to the M_Res_AddConstant_DP case above.
+
+        raise NotImplementedError
+
+    # walkthrough: multiplying constants (f * constant <= r)
+    def solve_dp_FixFunMinRes_M_Res_MultiplyConstant_DP(
+        self, dp: M_Res_MultiplyConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        #  (f * constant <= r)
+
+        # This is similar to the M_Res_AddConstant_DP case above with
+        # multiplication instead of addition.
+
+        f = query.functionality
+        assert isinstance(f, Decimal)
+        min_r = f * dp.vu.value
+
+        # one last detail: we need to make sure that the resource is valid
+        # for the R poset. We use the largest_upperset_above() function in Numbers.
+        # See documentation there.
+        us = dp.R.largest_upperset_above(min_r)
+
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_M_Res_MultiplyConstant_DP(
+        self, dp: M_Res_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        #  (f * constant <= r)
+
+        raise NotImplementedError
+
+    # exercise: multiply by constant (f  <= r * constant)
+
+    def solve_dp_FixFunMinRes_M_Fun_MultiplyConstant_DP(
+        self, dp: M_Fun_MultiplyConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_M_Fun_MultiplyConstant_DP(
+        self, dp: M_Fun_MultiplyConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        raise NotImplementedError
+
+    # walktrough: multiply functionalities
+
+    def solve_dp_FixResMaxFun_M_Fun_MultiplyMany_DP(
+        self, dp: M_Fun_MultiplyMany_DP, query: FixResMaxFunQuery[tuple[Decimal, ...]]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f <= r1 * r2 * r3 * ...
+
+        # This direction is easy, we just multiply the resources
+
+        res = Decimal(1)
+        for ri in query.resources:
+            res *= ri
+        ls = dp.F.largest_lowerset_below(res)
+        return Interval.degenerate(ls)
+
+    # exercise: multiply resources
+
+    def solve_dp_FixFunMinRes_M_Res_MultiplyMany_DP(
+        self, dp: M_Res_MultiplyMany_DP, query: FixFunMinResQuery[tuple[Decimal, ...]]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f1 * f2 * f3 * ... <= r
+        # similar to the above
+
+        # this is the easy direction
+
+        raise NotImplementedError
+
+    # walkthough: add many
+
+    def solve_dp_FixFunMinRes_M_Res_AddMany_DP(
+        self, dp: M_Res_AddMany_DP, query: FixFunMinResQuery[tuple[Decimal, ...]]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f1 + f2 + f3 + ... <= r
+
+        f = query.functionality
+        F: PosetProduct[Decimal] = dp.F
+        assert isinstance(f, tuple), f
+        assert len(f) == len(F.subs), (f, F)
+
+        # This direction is easy, we just add the functionalities
+        res = f[0]
+        for fi in f[1:]:
+            res += fi
+
+        min_r = res
+        us = dp.R.largest_upperset_above(min_r)
+        return Interval.degenerate(us)
+
+    # exercise: add many functionalities
+
+    def solve_dp_FixResMaxFun_M_Fun_AddMany_DP(
+        self, dp: M_Fun_AddMany_DP, query: FixResMaxFunQuery[tuple[Decimal, ...]]
+    ) -> Interval[LowerSet[Decimal]]:
+        # this is a relation of the type
+        #  (f1 ≤  r) and (f2 ≤ r) and (f3 ≤ r) and ...
+
+        # This direction is easy, we just add the resources
+
+        raise NotImplementedError
+
+    # exercise: meet
+
+    def solve_dp_FixFunMinRes_MeetNDualDP(
+        self, dp: MeetNDualDP[X], query: FixFunMinResQuery[X]
+    ) -> Interval[UpperSet[tuple[X, ...]]]:
+        # this is a relation of the type
+        #  (f ≤  r₁) and (f ≤  r2)  and (f ≤  r3) and ...
+
+        # this direction is very easy, as we can just let each resource
+        # be equal to the functionality
+
+        f = query.functionality
+        min_res = (f,) * len(dp.R.subs)
+
+        us = dp.R.largest_upperset_above(min_res)
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_MeetNDualDP(
+        self, dp: MeetNDualDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[tuple[X, ...]]]:
+        raise NotImplementedError
+
+    # exercise: join
+
+    def solve_dp_FixFunMinRes_JoinNDP(
+        self, dp: JoinNDP[X], query: FixFunMinResQuery[tuple[X, ...]]
+    ) -> Interval[UpperSet[X]]:
+        # this is a relation of the type
+        #  (f1 ≤  r) and (f2 ≤ r) and (f3 ≤ r) and ...
+
+        # similar to above
+
+        f = query.functionality
+        min_r: Optional[X] = dp.opspace.join(f)
+        if min_r is None:
+            raise NotImplementedError("TODO: join")
+        us: UpperSet[X] = dp.R.largest_upperset_above(min_r)
+        return Interval.degenerate(us)
+
+    def solve_dp_FixResMaxFun_JoinNDP(
+        self, dp: JoinNDP[X], query: FixResMaxFunQuery[X]
+    ) -> Interval[LowerSet[tuple[X, ...]]]:
+        raise NotImplementedError
+
+    # The above are sufficient for lib1
+    #
+    #
+    #
+    #
+
+    # The following are only for lib2.
+    #
+    #
+
+    def solve_dp_FixResMaxFun_M_Res_DivideConstant_DP(
+        self, dp: M_Res_DivideConstant_DP, query: FixResMaxFunQuery[Decimal]
+    ) -> Interval[LowerSet[Decimal]]:
+        # f/c <= r
+
+        # Similar to a case above
+        raise NotImplementedError
+
+    def solve_dp_FixFunMinRes_M_Res_DivideConstant_DP(
+        self, dp: M_Res_DivideConstant_DP, query: FixFunMinResQuery[Decimal]
+    ) -> Interval[UpperSet[Decimal]]:
+        # f/c <= r
+
+        # Similar to a case above
+        raise NotImplementedError
+
+    # Exercise: parallel interconnection
+
+    def solve_dp_FixFunMinRes_ParallelDP(
+        self, dp: ParallelDP[FT, RT], query: FixFunMinResQuery[tuple[FT, ...]]
+    ) -> Interval[UpperSet[tuple[RT, ...]]]:
+        # This is the parallel composition of a sequence of DPs.
+
+        f = query.functionality
+
+        # F and R are PosetProducts
+        F: PosetProduct[FT] = dp.F
+        R: PosetProduct[RT] = dp.R
+
+        # and f is a tuple of functionalities
+        assert isinstance(f, tuple), f
+        # ... of the same length as the number of DPs
+        assert len(f) == len(dp.subs), (f, F)
+
+        # You should decompose f into its components, and then solve each DP.
+        # Then you need to take the *product* of the solutions.
+        # The product of upper sets is the upper set of the cartesian product
+        # and it is implemented as UpperSet.product().
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_ParallelDP(
+        self, dp: ParallelDP[FT, RT], query: FixResMaxFunQuery[tuple[RT, ...]]
+    ) -> Interval[LowerSet[FT]]:
+        # Hint: same as above, swapping functionalities and resources
+
+        # You will need to use LowerSet.product()
+        raise NotImplementedError
+
+    # exercise (advanced): loops!
+
+    def solve_dp_FixFunMinRes_DPLoop2(
+        self, dp: DPLoop2[F1, R1, object], query: FixFunMinResQuery[F1]
+    ) -> Interval[UpperSet[R1]]:
+        # Note: this is an advanced exercise.
+
+        # As in the book, the intermediate goal is to define a function f such that
+        # the solution is the least fixed point of f.
+
+        raise NotImplementedError
+
+    def solve_dp_FixResMaxFun_DPLoop2(
+        self, dp: DPLoop2[F1, R1, object], query: FixResMaxFunQuery[R1]
+    ) -> Interval[LowerSet[F1]]:
+        # Note: this is an advanced exercise.
+
+        # Hint: same as above, but go the other way...
+        raise NotImplementedError