Assignment 2: Solving Efficiency #

Due date: 09/13/2024

Task: Upgrade the existing generic solver with a memo table and an iterative solving algorithm. Implement the game of Number Scrabble for an arbitrary sum of \( n \in \mathbb{N}^{+} \) from a set \( S \subseteq \mathbb{N}_{n} \) , creating a hashing function for it in the process.

Provided:

• No additional skeleton code or utilities.
• High-level explanations, steps, and hints in this web page.
• A symbolic representation of the iterative solving algorithm.
• The binary they installed in Assignment 1 also includes a correct solution for this assignment, and the same testing framework still works.

Metrics: After executing the python program, stdout should match the output of the provided game implementation on arbitrary inputs of \( n \) and \( S \) (within the now extended bounds of an iterative and memoized solution). The specific inputs on which it will be evaluated is not provided. This output should now be a breakdown of the number of winning, losing, and tying positions in the game (which they can print via the provided analysis utilities).

Learning objectives:

• Overcome the difficulty of a more complicated implementation of the game interface.
• Understand the added efficiency of iterative and memoized solving algorithms.
• Become familiarized with creating injective state hashing functions.
• Ease into being able to create a new game module from scratch.

Note: Participants did not need to create a hashing function for the first assignment, as it is not generally necessary for N-to-0. No additional downloads or installations are necessary for this assignment. They should be able to just pass in the memo table they populate with their solving algorithm to the utility functions (which will provide a specific API).