#!/usr/bin/env python3 # -*- coding: utf-8 -*- from collections import deque from src.testing import AD2TestCase, get_return_type, recursion_variant from src.weightlifting_data import data from typing import * import logging import math import unittest ''' Assignment 1, Problem 1: Weightlifting Student Name: ''' ''' Copyright: justin.pearson@it.uu.se and his teaching assistants, 2024. This file is part of course 1DL231 at Uppsala University, Sweden. Permission is hereby granted only to the registered students of that course to use this file, for a homework assignment. The copyright notice and permission notice above shall be included in all copies and extensions of this file, and those are not allowed to appear publicly on the internet, both during a course instance and forever after. ''' # Note: you must give a recursion variant for each recursive function fun by # wrapping fun with the '@recursion_variant(lambda a, b, ..., z): expr)' # wrapper, where the set {a, b, ..., z} is a subset of the arguments to fun and # expr is evaluated to an integer. # If your solution needs a queue, then you can use deque. # If you need to log information during tests, execution, or both, # then you can use this library: # Basic example: # logger = logging.getLogger('put name here') # a = 5 # logger.debug(f'a = {a}') __all__ = ['weightlifting_recursive', 'weightlifting_top_down', 'weightlifting_bottom_up', 'weightlifting_list'] # You must give a valid recursion variant for weightlifting_recursive. # the recursion wrapper takes a subset of the parameters of the function it # wraps, and with the same name. This wrapper can therefore take a subset # {P, w, p} and the order doesn't matter. @recursion_variant(lambda P, w, p: 0) def weightlifting_recursive(P: List[int], w: int, p: int) -> bool: ''' Pre: for 0 <= i < len(P): P[i] >= 0 Post: Ex: P = [2, 32, 234, 35, 12332, 1, 7, 56] weightlifting_recursive(P, 299, 8) returns True weightlifting_recursive(P, 11, 8) returns False ''' # 1. Add base case(s) # 2. add recursive case(s) pass def weightlifting_top_down(P: List[int], w: int, dp_matrix: List[List[None]]) -> bool: ''' Pre: for 0 <= i < len(P): P[i] >= 0 Post: the element at the last row and column in dp_matrix is True Ex: dp_matrix [[None, ..., None], ..., [None, ..., None]]] P = [2, 32, 234, 35, 12332, 1, 7, 56] weightlifting_top_down(P, 299, dp_matrix) returns True weightlifting_top_down(P, 11, dp_matrix) returns False ''' # If you want to make a recursive solution, you may use inner (also called # nested) or helper functions that perform the recursion. # Rembember to wrap your recursive function with the @recursion_variant # wrapper. pass def weightlifting_bottom_up(P: List[int], w: int, dp_matrix: List[List[None]]) -> bool: ''' Pre: for 0 <= i < len(P): P[i] >= 0 Post: no element in dp_matrix is None Ex: dp_matrix [[None, ..., None], ..., [None, ..., None]]] P = [2, 32, 234, 35, 12332, 1, 7, 56] weightlifting_bottom_up(P, 299, dp_matrix) returns True weightlifting_bottom_up(P, 11, dp_matrix) returns False ''' # 1. Fill first column and row of dp_matrix # 2. iteratively fill rest of dp_matrix # 3. return the result from the dp_matrix pass def weightlifting_list(P: List[int], w: int, dp_matrix: List[List[None]]) -> List[int]: ''' Pre: 0 <= w for 0 <= i < len(P): P[i] >= 0 Post: the element at the last row and column in dp_matrix is True Ex: P = [2, 32, 234, 35, 12332, 1, 7, 56] weightlifting_list(P, 299) returns a permutation of [2, 7, 56, 234] weightlifting_list(P, 11) returns [] ''' pass class WeightliftingTest(AD2TestCase): logger = logging.getLogger('WeightLiftingTest') data = data weightlifting_recursive = weightlifting_recursive weightlifting_recursive_ret_type = get_return_type(weightlifting_recursive) weightlifting_top_down = weightlifting_top_down weightlifting_top_down_ret_type = get_return_type(weightlifting_top_down) weightlifting_bottom_up = weightlifting_bottom_up weightlifting_bottom_up_ret_type = get_return_type(weightlifting_bottom_up) weightlifting_list = weightlifting_list weightlifting_list_ret_type = get_return_type(weightlifting_list) src_code_path = __file__ def source_code_path(self): return WeightliftingTest.src_code_path def dp_matrix(self, P: List[int], w: int) -> List[List[None]]: return [[None for _ in range(w + 1)] for _ in range(len(P) + 1)] def assertDpMatrix(self, dp_matrix: List[List[Any]]) -> None: for p in range(len(dp_matrix)): for w in range(len(dp_matrix[p])): self.assertIsNotNone( dp_matrix[p][w], f'Expected bool at dp_matrix[{p}][{w}], but found ' f'"{type(dp_matrix[p][w]).__name__}".') def test_recursive(self) -> None: for i, instance in enumerate(self.data): with self.subTest(instance=i): P: List[int] = instance['plates'].copy() if len(P) > 20: continue w: int = instance['weight'] min_recursions: int = instance['min_recursions'] res = self.assertSelfRecursiveAlgorithm( WeightliftingTest.weightlifting_recursive, WeightliftingTest.weightlifting_bottom_up_ret_type, min_recursions, P, w, len(P)) self.assertEqual(res, instance['expected']) def test_top_down(self) -> None: for i, instance in enumerate(self.data): with self.subTest(instance=i): P: List[int] = instance['plates'].copy() w: int = instance['weight'] dp_matrix = self.dp_matrix(P, w) res = self.assertAlgorithm( WeightliftingTest.weightlifting_top_down, WeightliftingTest.weightlifting_top_down_ret_type, P, w, dp_matrix) self.assertEqual(res, instance['expected']) self.assertIsNotNone(dp_matrix[-1][-1], 'weightlifting_top_down must use ' 'dp_matrix for memoisation.') contains_none = any(x is None for array in dp_matrix for x in array) self.assertTrue(contains_none, 'weightlifting_top_down must use the ' 'top-down approach.') def test_bottom_up(self) -> None: if WeightliftingTest.weightlifting_bottom_up([], 0, [[None]]) is None: self.skipTest('weightlifting_bottom_up not implemented.') for i, instance in enumerate(self.data): with self.subTest(instance=i): P: List[int] = instance['plates'].copy() w: int = instance['weight'] dp_matrix = self.dp_matrix(P, w) res = self.assertIterativeAlgorithm( WeightliftingTest.weightlifting_bottom_up, WeightliftingTest.weightlifting_bottom_up_ret_type, P, w, dp_matrix) self.assertDpMatrix(dp_matrix) self.assertEqual(res, instance['expected']) def test_list(self) -> None: if WeightliftingTest.weightlifting_list([], 0, [[None]]) is None: self.skipTest('weightlifting_list not implemented.') for i, instance in enumerate(self.data): with self.subTest(instance=i): P: List[int] = instance['plates'].copy() w: int = instance['weight'] dp_matrix = self.dp_matrix(P, w) res = self.assertAlgorithm( WeightliftingTest.weightlifting_list, WeightliftingTest.weightlifting_list_ret_type, P.copy(), w, dp_matrix) self.assertIsNotNone(dp_matrix[-1][-1], 'weightlifting_top_down must use ' 'dp_matrix for memoisation.') plate_counts = {p: P.count(p) for p in set(P)} used_plates = {p: res.count(p) for p in set(res)} for p in used_plates: self.assertLessEqual(used_plates[p], plate_counts.get(p, 0), f'plate {p} occurs {used_plates[p]} ' 'times in the solution, but only ' f'{plate_counts[p]} times in P') if instance['expected']: self.assertEqual(sum(res), instance['weight'], 'The sum of the returned list of plates ' 'does not equal the expected weight.') else: self.assertListEqual(res, list()) if __name__ == '__main__': # Set logging config to show debug messages: logging.basicConfig(level=logging.DEBUG) # run unit tests (failfast=True stops testing after the first failed test): unittest.main(failfast=True)