5CCS2PEP Practical Experiences Of Programming: PEP C++ Tasks
PEP C++ Tasks
Due to varia2on in c++ compilers it’s important to note that your code will be considered working (compiling/linking/func2oning) if it compiles and passes the tests on the module server. To check whether or not that’s the case you’ll need to commit your code via github (as per instruc2ons via Keats). This will inject the code to my server and generate a feedback report that will appear under the ‘issue’ tab of your git account (aGer 15 minutes or so).
---
For Part 1 tasks you will code using some of the basic building blocks of C++: vectors, functions, and classes.
Where you are to write functions, ensure you use constness and references where appropriate, to avoid needlessly copying objects, and to help ensure you have wriCen correct code.
Make sure you don't commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE. You can make these on your machine, but don't `commit` or `add` them to your repository -- this isn't what git is designed for.
----
[Part 1 – 10 Marks in total]
# Solving the Countdown Numbers Game
- When solving this task your code must be in C++. Do not use any of the 'C' language func>ons for working with strings (the func>ons defined on the following page <hCps://en.cppreference.com/w/cpp/header/cstring>, or those on the following page in the 'Numeric string conversion' sec>on -- <hCps://en.cppreference.com/w/cpp/header/cstdlib>).
You are also limited to the following libraries: string, sstream and vector. If there is any issue with this, contact me via email.
The Countdown numbers game is specified as follows:
- Players are given six integer numbers and a target integer number
- The six numbers should be combined using the mathema>cal operators + - * and / in a way that gets as close as possible to the target number.
-Each number can only be used once at most, but it is okay not to use any given number/s. -Divisions by zero can be discarded
For instance if the numbers are (100,4,17,9,3,2) and the target is 37, then one way to do is `(100 / (3 + 2)) + 17)`
## Evalua>ng numeric expressions [1 mark]
In `Countdown.h`, where it says `TODO: write code here`, implement a func>on `evaluateCountdown` that takes a `string` containing a mathema>cal expression wriCen in Reverse Polish Nota>on (RPN) and returns the result of that expression as an `double`. For more details of on RPN see: hCps://en.wikipedia.org/wiki/Reverse_Polish_nota>on. In short, when using Reverse Polish Nota>on (RPN), operators are wriCen *ager* rather than between what they act upon. For instance:
`3.0 4.0 +` ...is the same as the usual (infix) nota>on `(3.0 + 4.0)`.
`3.0 4.0 + 2.0 *` ...is the same as `(3.0 + 4.0) * 2`.
Using the above example, we can write `(100 / (3 + 2)) + 17)` in RPN as: `100 3 2 + / 17 +`
The advantage of RPN is that there is no need to worry about brackets and order of precedence.
How to implement RPN in code? An expression (the string) can be evaluated by making a stack of numbers (using e.g. a `vector<double>`) splikng the input string by spaces into tokens, and working through the calcula>on one token at a >me:
* If the token is a `+`, pop two numbers a and b off the stack, and push (b + a) onto the stack * If the token is a `-`, pop two numbers a and b off the stack, and push (b - a) onto the stack * If the token is a `*`, pop two numbers a and b off the stack, and push (b * a) onto the stack * If the token is a `/`, pop two numbers a and b off the stack, and push (b / a) onto the stack * Otherwise, the token is a number: push it onto the stack
Ager going through all the tokens, the answer should be the only number on that stack. Because you only need to be able to evaluate numeric expressions for 'countdown' problems, you can safely assume your stack won’t be bigger than six elements -- the worst case is an expression with six numbers (all put on the stack) followed by five arithme>c operators, e.g. `100 4 17 9 3 2 + + + + +`.
To test your code, compile and run `TestEval.cpp`. This will evaluate four expressions, and check they give the right answer. As a reminder, to compile using g++ at the command line, with debugging turned on using (`-g`):
`g++ -std=c++11 -g -o TestEval TestEval.cpp`
...then run `./TestEval`
Notes:
- `std::stod(s)` will convert the string `s` into a double, and return its value
## Solving countdown problems [9 marks]
The file `Countdown.h` contains a small class `CountdownSolu>on` for storing solu>ons to Countdown numbers problems: a string containing an RPN numeric expression, and an int containing the value that expression evaluates to.
In `Countdown.h` implement a func>on `solveCountdownProblem` that takes a `vector<int>` containing 6 numbers, and a target number; and returns a `CountdownSolu>on` object containing the solu>on to the problem that gets as close as possible to the target.
To test your code, compile and run `TestCountdown.cpp`. This will evaluate some Countdown sets (6 numbers and their associated targets) and check they give the right answer.
Notes:
- The suggested approach to solve this task is by wri>ng code that constructs different RPN
expressions (using each number once at most with the 4 available mathema>cal operators).
- Evaluates these expressions (using your `evaluateCountdown` func>on) and returns the
best solu>on found (closest to target number).
- The given code `intToString` may be helpful in the process of building RPN expressions: it
takes an int, and returns a string.
Countdown Rules:
- Each number can only be used once.
- No nega>ve numbers or Zeros will be fed into the code (Countdown.h).
- Once the code reaches the target it can stop.
[Part 2 – 5 marks in total]
# String construc>on [5 marks]
This part of the assignment considers a string construc>on problem defined as follows:
- You are given as input a target string. Star>ng with an empty string, you add characters to it, un>l your new string is same as the target. There are two op>ons in which you can add characters to the empty string:
1. You can append an arbitrary character to your new string, with cost x OR
2. You can clone any substring of your new string (as it stands at that point), and
append it to the end of your new string, with cost y
- For a given target you’ll be given an append cost x and a clone cost y. At the end of the process, we want to know what is the *cheapest cost* of building the target string
For some simple examples:
- Target "aa" that has append cost 1, clone cost 2: the cheapest cost is 2:
- Start with an empty string, ""
- Append 'a' (cost 1), giving the string "a"
- Append 'a' (cost 1), giving the string "aa"
- Target "aaaa" that has append cost 2, clone cost 3: the cheapest cost is 7:
- Start with an empty string, ""
- Append 'a' (cost 2), giving the string "a"
- Append 'a' (cost 2), giving the string "aa"
- Clone "aa" (cost 3), giving the string "aaaa"
- Target "xzxpzxzxpq", append cost 10, clone cost 11: the cheapest cost is 71:
- Start with an empty string, ""
- Append 'x' (cost 10): "x"
- Append 'z' (cost 10): "xz"
- Append 'x' (cost 10): "xzx"
- Append 'p' (cost 10): "xzxp"
- Append 'z' (cost 10): "xzxpz"
- Clone "xzxp" (cost 11): "xzxpzxzxp"
- Append 'q' (cost 10) : "xzxpzxzxpq"
In the file `StringConstruc>on.h` write a func>on `stringConstruc>on` that takes the target string, the clone cost, and the append cost (in that order!) and returns the cheapest way of making the target string. It doesn't need to return *how* to do it, just the cost.
To test your code, TestStringCons.cpp contains some test cases. To compile and run at the
command line:
`g++ -std=c++11 -o TestSC TestStringCons.cpp`
`./TestSC`
Note: when your work is marked, it will be tested with target strings of a range of sizes. To get full marks, it will need to work for the largest of these target strings, which is 30,000 characters. Your code will be run on a modest desktop PC, and allowed 10 seconds.
[Part 3 – 10 marks in total]
For these tasks you will be making a Linked List template class.
Make sure you don't commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE. You can make these on your machine, but don't `commit` or `add` them to your repository -- this isn't what git is designed for.
----
# LinkedList basics [3 marks]
## a) Making a list node
Note that in answering this task, you should not add any `#include` or `using` statements. You must implement the func>onality yourself, without using any data structures from the Standard Template Library (STL). I have added `#include <iostream>` for if you want to print things out to help with your debugging. Any issues about this, please get in touch.
In the file `node.h` implement a template class `Node` that represents a node in a doubly linked list. It should have three `public` member variables:
- The `data` stored in that Node. The type of this should be a template argument.
- A pointer to the `next` Node in the list
- A pointer to the `previous` Node in the list
Make a constructor that takes an item of data, stores it in the node, and sets the two pointers to `nullptr`.
## b) Making an iterator for list nodes
The file `node.h` contains an incomplete `NodeIterator` class, that contains a pointer to a `Node`. It is a template class -- a `NodeIterator<T>` object contains a pointer to a `Node<T>`.
Complete the defini>on of the `NodeIterator` class, so that:
- We can increment the iterator, using ++, which makes it point to the next node in the list
- We can see if two iterators are the same, using the == operator. Two iterators are the same
if they point to the same Node.
- We can see if two iterators are different, using the != operator
To test your code, compile and run TestNode.cpp. A Makefile has been provided, run: `make TestNode`
...at the command line. This makes two Nodes, one linked to the other, then makes an iterator over these.
If you don't have make, you can always open the Makefile and copy-paste the command that will be used to compile TestNode:
`g++ -Wall -g -std=c++11 -o TestNode TestNode.cpp`
# Making a LinkedList class [7 marks]
Note that in answering this task, you should not add any `#include` or `using` statements. You must implement the func>onality yourself, without using any data structures from the Standard Template Library (STL). I added #include "node.h” and #include <u2lity>. Any issues about this, please get in touch.
In the file `linkedlist.h` implement a template class LinkedList. This should use the ` #include "node.h"` class you have wriCen so far. As member variables you should have:
- A pointer to the head of the list
- A pointer to the tail of the list
- A count of how many elements are in the list
The func>ons in LinkedList should be:
- A constructor, that creates an empty list (head and tail are `nullptr`, zero elements in the list)
- A `push_front` func>on that takes an item and pushes it onto the front of the list, i.e. it becomes the head of the list. (Note this should *not* take a Node. For a LinkedList<T>, we should be able to pass a T to push_front.)
- A `front()` func>on, that returns a reference to the data inside the head node
- A `push_back` func>on that takes an item and pushes it onto the back of the list, i.e. it
becomes the tail
- A `back()` func>on, that returns a reference to the data inside the tail node
- A `size()` func>on that returns the count of how many elements are in the list
- A `begin()` func>on that returns an iterator poin>ng to the head of the list
- An `end()` func>on that returns an iterator poin>ng to `nullptr` (NB it doesn't point to the
tail: it points *off the end* of the list -- and the Node ager the tail is `nullptr`.)
- A destructor, that `delete`s every node in the list.
- A `reverse()`func>on that reverses the order of the nodes in the list (NB it doesn't make new nodes, it should re-order the exis>ng nodes.)
Recommenda2on: The above list of func>ons is in order of difficulty. It is therefore recommended you implement them in this order.
To test your LinkedList at this point, compile and run TestList.cpp. You can do this using: `make TestList`
It may help you to comment out tests that use code you haven't wriCen yet (as they won't compile). Alterna>vely, if you push your code to github, the automated tests will be run individually and should work even if you have not completed all parts.
Note: when your work is marked, deduc>ons will be made for memory leaks. Take care to ensure that you have deleted every object you created with new, exactly once.
Once you're happy with your work so far, it's >me to make the class a bit more useful.
First, extend your class to have a constructor that takes a :
[std::ini>alizer\_list<T>](hCp://en.cppreference.com/w/cpp/u>lity/ini>alizer_list) as its argument, and makes a list containing these. You can `#include <ini>alizer_list>` for this. This will allow lists to be created using the handy syntax:
`LinkedList<int> numbers {4,6,8,10,12};`
When we write this, the numbers in braces are put in the ini>alizer_list and passed to the constructor.
Next, inser>ng and erasing elements from linked lists is a classic interview ques>on. Add func>onality as follows:
- `insert()`, taking as arguments a NodeIterator poin>ng to where to insert the new element in the list; and the element itself. The element should be inserted in this posi>on, and an iterator to the new element returned. For instance, in the list: `[3,5,7]`
...if we have an iterator poin>ng to element `5` and call insert of element `4`. The new list would become: `[3,4,5,7]` returning an iterator poin>ng to 4.
Note you may edit your iterator class to provide a func>on to access the Node pointer from inside the iterator.
- `erase()`, taking as argument a NodeIterator poin>ng to an element to erase; and returning what is now in its place -- ager removing element *i*, it should return a NodeIterator to what is now element *i*. For instance, if the list was: `[3,5,7]`
...and an iterator poin>ng to the 2nd element `5` was erased, that would update the list to be: `[3,7]` and return an iterator poin>ng to 7. If you are dele>ng the last item off the list, it should return an iterator poin>ng to nullptr.
Again, as above, make sure your implementa>on avoids memory leaks.
- Addi>onal overloads of `begin()` and `end()` that are const methods -- i.e. can be used on a `const LinkedList`, to iterate through and provide read-only access to the elements. To go with this, you will need to make another iterator class with a different name of your choosing.
To test your LinkedList now, compile and run TestListD.cpp. You can do this by using: `make TestListD` , which is provided.
[PART 4- 25 marks in total]
In this part you will be solving a puzzle.
No addi>onal libraries are allowed to be used apart from <vector>, <iostream>, <memory> and <string>.
#The Puzzle
NumberSets is a numbers puzzle, which is very similar to Sudoku. It is played on a 9x9 board where the board is par>ally filled with numbers in white and black cells. The aim in this task is to fill the empty white cells with the correct numbers. White cells with numbers and all black cells (both empty and not) are blocked and mustn’t be changed.
In this task you will write a program that fills the board’s white cells that are empty by taking into account all the rules that are described below. All tasks refer to cells using 0-8 index to represent cell posi>ons for both rows and columns.
1. 2.
3.
4. 5.
6. 7.
Table 1- Board 1
031
1
2735 357 469 54 65 628
723 843681
ABCDEFGHI
Rows and columns are divided into compartments.
A compartment is a series of uninterrupted white cells (above column F, is made up
of two compartments marked in green border)
Each compartment needs to be filled with an unordered but uninterrupted set of numbers. That said, compartments do not necessarily need to con>nue each other’s numbers. So the answer for column F top compartment is: (2,F) 4 , (3,F) 6 and (4,F) 7 (crea>ng an unordered but uninterrupted set of numbers: 4,6,7 and 5). Similarly the answer to column F low compartment is: (7,F) 9 crea>ng the set of 9,8.
Possible numbers are 1-9
By uninterrupted we mean there are no gaps in the middle (e.g., 3, 1, 2 or 5, 9, 6, 8,
7).
The number within any given compartment can appear in any order.
Like Sudoku, no single number can repeat in any row or column (irrespec>ve of compartments).
As men>oned above, a black square is a blocked square, which means that your solver cannot input a number into it. If a black square contains a number, it helps you by providing a clue that this number can effec>vely be removed from the list of possibility for any cell in that row and column.
As an example, the board below is showing different compartments in red, purple and green. Both the red and purple squares cannot contain the number 3 as it appears in 0,F. Similar is the case for the number 1 in 0,G. It is also the case that the red compartment cannot contain the numbers 5, 6, 8 and 3 as they already appear in columns C and D (see arrows).
RED 0 31 1
2735 357 469 54 65 628
Purple Green
This process can be used to eliminate and deduce which number fits in which empty white square. Looking above at the orange compartment (8,F and 8,G) it already contains the number 8 (8,F). This means that the empty white square to its right (8,G) can only be a 7 or a 9 as a compartment can only contain uninterrupted numbers, although these can appear in any order. As such, because column G contains the numbers 1, 5, 7 and 6, it means that 7 can also be removed as possibili>es, leaving 9 as the only viable op>on.
067312 167584 23 278 34512 389 526743 45 12 7694 5412365 87 632845 76 7234 79865 8436891
ABCDEFGHI
Table 2- solu0on to board 1
As can be view in the above solu>on to the puzzle, the sequence of uninterrupted numbers only persists within a compartment. Row zero has two compartments marked in Red and Purple. Within each compartment the numbers are uninterrupted, but there is a gap between the compartments.
723 843681
ABCDEFGHI
Represen2ng a board in code
To represent the board, a vector of strings (vector <std::string>) will be provided in the .cpp test file. It represents an empty black square as Zero, an empty white square as an asterisk and a black square with a number as a nega2ve of that that number. We’re only using nega>ve numbers for black squares that have numbers in order to dis>nguish them from a white cell with number. For example, the number 3 in row 0 (0,F) will be represented as -3 in the string. For clarity, empty white squares can only contain posi>ve numbers 1 through to 9.
As an example, the above board will be represented in the following way:
vector<string> easyBoard =
{"00**0-31*0", "*****0**0", "7*003*-5**",
"**05**7**", "*0**0*6-9*", "4***650**", "*2-8**00**", "-23*0*****",
"043-608*0-1"};
-In the file SetSolverSquareSet.h a SetSolverSquareSet class has been created with a vector of integers as its member variable. You need to write a constructor that ini>alises that vector to contain the numbers 0 – 8.
-In the file SetSolver.h a SetSolver class has been created with two member variables: a 2D vector of SetSolverSquareSet and the boardSize.
Your task is to write the following func>ons:
#PopulateTheBoard [1 mark]
- void PopulateBoard(vector<string>skeletonBoard). The func>on takes a vector of strings and translates/converts them to a vector of integers based on the following rules.
1. A zero remains a zero (denotes an empty black square)
2. A string of “-x” (nega>ve integer) remains a nega>ve number as an int (denotes a
black square with a number)
3. An asterisk is converted and stored as the number 99. (e.g. it denotes an empty
white square, which may hold any value from 1 to 9).
#ReturnCellValue [2 mark]
-int ReturnValue (int row, int col), which returns the value for a par>cular cell. It should return -x for a nega>ve number (deno>ng a black square with a number), x for a white square with a number, a zero for an empty black square and 99 for an empty white square.
#SolveBoards [22 mark]
- void Solve() this func>on will solve the board so that each empty white cell has been filled with the correct value. This will be checked using the ReturnValue func>on described above. Please note that using the process of elimina>on described above can only solve some boards. More difficult boards will require addi>onal mechanisms to break deadlocks, etc. Below you’ll find 4 addi>onal boards to prac>ce/test you code with. You can use NumberSetSolveTest.cpp and NumberSetPopulateTest.cpp as a boilerplate for these tests.
Ager the deadline, when I mark your code, I will test it with against Easy [3 marks], Intermediate [4 marks], Difficult [6 marks] and Very Difficult [9 marks] boards. Some research will be required for the laCer 2 difficul>es.
Addi>onal example of boards and their solu>ons: Board 2
