CAB203

Special Topics Assignment

1. Introduction

   In this assignment you will demonstrate your knowledge and skill with the material in the unit by developing a solution to one real world problem by translating it to mathematical language, using mathematical techniques from the unit to solve the problem, and implementing software to solve the problems.

   Your submission will consist of two parts: a report detailing the mathematical descriptions of the problems and solutions, and a Python file containing your implementation of the solutions.

   This assignment is worth 30% of your final grade. Please see t

2. Tasks

   Choose one out of the following three tasks to solve.

   1. Regular languages and finite state automata

      It’s time to write the ultimate Teams/Slack/Discord replacement, reChat ! No more resource intensive GUIs, as reChat will be entirely text based with a command line interface.

      Your task is to program the controlling logic that parses commands and keeps track of the state of a user’s connection. To do this you will write a Python function:

      def reChatParseCommand(message, state):

      # your code here

      return action, state

      Here message contains the input (i.e. command or message) from the user. state is a variable that you can use to store whatever you like. It is initially set to None on the first invocation of your function. Further explanation appears below.

      The returned variable action is a dictionary indicating what action should be taken along with additional parameters for that action, as described below. The returned variable state will be used as the state

      argument on the next time the function is invoked. This mechanism allows you to keep track of the state of the connection without resorting to global variables or other mechanisms. The state return value is ignored by the tests.

      The required behaviour is given below. Note that text surrounded by ‘<>’ like ‘<spec>’ in the action should be replaced with an appropriate value (eg. from the command):

      • When the user first connects (indicated by the message argument set to ” and the state argument set to None), the action is { ‘action’: ‘greeting’ } and the connection enters command mode.

      • In command mode the user has four possible commands:

        • list <spec> : where <spec> is either channels or users. The connection remains in command mode and the action is

          { ‘action’: ‘list’, ‘param’: ‘<spec>’ }

        • quit : The connection disconnects and the action is

          { ‘action’: ‘quit’ }

        • join <channel> : where <channel> is a channel name (see below). The connection enters

          channel mode and the action is

          {

        • enters direct

          { ‘action’: ‘dm’, ‘user’: ‘<username>’ }

      • In channel mode, the users has three possible commands. In the following, <channel> refers to the channel currently joined by the previous join <channel> command :

        • leave : The connection enters command mode and the action is

          { ‘action’: ‘leaveChannel’, ‘channel’: ‘<channel>’ }

        • read : The connection remains in channel mode and the action is

          { ‘action’: ‘readChannel’, ‘channel’: ‘<channel>’ }

        • <message> (not starting with ) : The connection remains in channel mode and the action is

          { ‘action’: ‘postChannel’, ‘channel’: ‘<channel>’, ‘message’: ‘<message>’, ‘mentions’: { ‘<username1>’, ‘<username2>, …’ } }

          where the mentions value gives all the usernames that appear in <message>.

      • In direct message mode the users has three possible commands. Note that, in the following, <username> refers to the same username given in the pervious dm <username> command, i.e. the user that is being messaged:

        • leave: The connection enters command mode and the action is

          { ‘action’: ‘leaveDM’, ‘user’: ‘<username>’ }

        • read: The connection remains in direct message mode and the action is

          { ‘action’: ‘readDM’, ‘user’: ‘<username>’ }

        • <message> (not starting with ) : The connection remains in direct message mode and the action is

          { ‘action’: ‘postDM’, ‘user’: ‘<username>’, ‘message’: ‘<message>’,

          ‘mentions’: { ‘<username1>’, ‘<username2>, …’ } }

          where the mentions value gives all the usernames that appear in <message>.

      • In all other circumstances the mode does not change and the action is

        { ‘error’: ‘Invalid command’ }

        The following specifications apply to channels and usernames:

      • A username is @ followed immediately by a valid email address according to the limited criteria from Tutorial 10, Section 2, Question 5b. (You can use the regular expression in the tutorial solutions; there is no need for you to recreate it yourself.)

      • A channel name is # followed immediately by a sequence of letters (upper or lower case) and numbers, beginning with a letter

        Please note the following additional requirements:

      • Your program should not use any global variables. All state information should be kept in the state

        argument/return value. Using global variables may cause problems with the testing system.

      • While on is that you

        will us he connection

        and to

      • Your report must include a state change diagram depicting the state changes in the behaviour described above. You do nothnetedttpo hsav:e /st/atpe choanwge dciagoramds foer rreg.uclaroexmpressions that you use.

      For this task the Python code will be marked automatically according to test cases similar to the sample test cases in test_STA_fsa.py. You can run the sample test cases with python test_STA_fsa.py while ensuring that your solution is called specialtopics.py and is in the same directory as test_STA_fsa.py. There are 10 test cases in total, including one test case which checks to see if you have used any for or while loops. As with the Graphs project, your priority should be to have working code as the loops criterion is only worth 1 mark.

   2. Linear algebra

      Dana is a wheat farmer. She has three fields which she has harvested and stored in three separate grain bins. Each field has di↵erent characteristics and hence the quality of the wheat stored in each bin is di↵erent. She wants to maximise her profit by blending wheat from the bins to maximise the amount of High Protein Grade wheat she has to sell.

      High Protein grade wheat needs to meet two criteria 1:

      • minimum 14% protein by weight

      • maximum 12.5% moisture by weight

        1Australia currently has 32 grades for wheat determined by 47 criteria (See Wheat Standards 2023/24 All Grades). We’re simplifying here.

        You task is to determine how Dana should blend the wheat from her three bins to maximise the amount of High Protein grade wheat she can sell.

        Important! Solving the problem as stated in full generality goes beyond what is learned the unit (it is what’s called a linear programming problem) so we’ll restrict the problem to cases where it is possible to exactly match the requirements, i.e. exactly 14% protein, and exactly 12.5% moisture. This will always be possible for our test cases and there is no need for your solution to work with other cases.

        Create a Python function which calculates how much wheat to use from each bin to blend together:

        def blendWheat(csvfilename):

        # your code here

        return blend, amount

        Your input data will come from a CSV file with filename given by the csvfilename parameter, formatted like so:

        Bin,Weight A,12,15,12 B,15,13.5,

        C,7,12,14

        where the Weight columnhgitvets pthesam:o/u/ntpofowhweat inceaochdbine, inrt.oncneos, wmhile the remaining two numbers are percentages.

        Your function should return a pair consisting of a Python dictionary containing how many tonnes of wheat from each bin to blend, and the amount of High Protein grade wheat obtained, rounded to the nearest 0.01 tonnes. The solution for the CSV file above is:

        ( { ‘A’: 12.0, ‘B’: 10.29, ‘C’: 3.43 }, 25.71)

        In order to deal with numerical precision problems (because floating point numbers are not exact), all test cases will accept an error of up to 0.01 tonnes.

        Hint: You can solve this in two steps by first determining the amount of wheat from each bin required to make exactly 1 tonne of High protein grade wheat with the correct percentages for protein and moisture. This is a system of 3 equations with 3 unknowns. The second step is to scale this so that you run out of wheat in one bin.

        For this task the Python code will be marked automatically according to test cases similar to the sample test cases in test_STA_linalg.py. You can run the sample test cases with python test_STA_linalg.py while ensuring that your solution is called specialtopics.py and is in the same directory as test_STA_linalg.py. There are 10 test cases in total, including one test case which checks to see if you have used any for or while loops. As with the Graphs project, your priority should be to have working code as the loops criterion is only worth 1 mark.

   3. Probability

Recently you have inherited your long lost uncle’s wheat farm, and you are determined to make a go of it. It’s exciting, but there’s a lot to learn. While spending some time around the local co↵ee shop an old farmer o↵ers you some advice:

“You’ll be wanting to get some kind of crop insurance. Input costs are high these days, so don’t want to lose it all if you have crop failure. There’s a few kinds of crop insurance. The expensive kind pays out for any kind of crop failure. Then there’s cheaper kinds that don’t pay out as well, and some that don’t cover all kinds of crop failure. Plus there’s some that only work for certain things. Hail insurance is like that; only pays out if your crop gets hailed out.”

You ask the old farmer how to decide what kind to get.

“Depends on your land. This area has a lot of di↵erent soil types. Sandy soils are bad if there is a drought. Clay tends to get flooded out if there is lots of rain. Then there’s the hills that a↵ect the weather patterns so some places get lots of rain or hail, and others tend to be dry. And for whatever reason, some places get grasshoppers real bad some years and they’ll eat your crop right down to the ground. Now seems to me you’ve got one of old Charlie’s fields. He used to keep track of everything that happened in this little book of his, and h rone to what

from that.”

From Charlie’s book you have determined that there are three events that you need to worry about for your field: drought, hail, and grasshoppers (and of course, it is possible that none of these things happen!). Charlie recorded which of these happened for each of his fields for 20 years. Table 1 summarises the information.

Field Drought Hail Grasshoppers No failure

Home quarter 4 1 1 14

BAreakdingd We3 Ch3at po3 wcod11er

Lyon quarter 0 4 0 16

Down south 1 1 3 15

Up north 2 2 2 14

The farm 1 1 1 17

Table 1: Number of years in which each event occurred out of 20 years, by field.

Unfortunately, Charlie used names for the fields that apparently made sense to him, but not to anybody else, so you don’t know which of Charlie’s fields you have.

You have managed to sign a contract with a company that will buy your entire crop at a fixed price, unless your crop fails2.

Asking around to crop insurance companies, you find that there are five kinds available3:

• Comprehensive. Pays 80% of your contract price in the event of any kind of crop failure.

• Hail. Pays 80% of your contract price in the event of crop failure due to hail.

2This is not the way contracts usually work, but we’re simplifying for this exercise.

3This is also not how crop insurance usually works.