Homework 11 – Bonus
Congratulations on finishing a semester of CS 1371 Homework! You have made it to the final extra credit assignment. These problems are meant to be somewhat challenging and also to help you review different concepts from throughout the semester. There are five problems, each worth 20 points. This homework is due on Sunday, July 19th at 8:00 pm, with the usual grace period until 11:59 pm. There will not be a resubmission. Have fun with these problems, good luck with finals, and thanks for a great semester in CS 1371!
Happy Coding! ~Homework Team
Homework 11 – Bonus
Function Name: mondrian Inputs:
1. (char) Filename of artwork to be analyzed
Outputs:
2. (uint8) 1x1x3 pixel
3. (double) Path taken through the array
Background:
While at the Museum of Modern Art (MoMA) in New York City, you come across the painting Broadway Boogie Woogie, a painting by Piet Mondrian. Mondrian was famous as a pioneer of abstract art as part of the De Stijl art movement in the early 20th century. His paintings are known for their use of geometric shapes painted in solid colors. Inspired by his work, you decide to create your own abstract art, but the meaning of it eludes you. Stumped, you turn to MATLAB to help you analyze your art…
Function Description:
You will be given a file containing a 2^N x 2^N image, which can be separated into four evenly sized quadrants. Three of the quadrants will contain all the same pixels. The fourth will contain the same four-quadrant setup, with three-quarters of that quadrant using the same pixel while one quadrant is different. Traverse the array until you are left with one pixel and output that pixel as the first input. As the second output, output a double vector of the quadrants that you traced through while searching the array.
● Top left is quadrant 1
● Bottom left is quadrant 2
● Top right is quadrant 3
● Bottom right is quadrant 4
Example:
art1.png =>
Homework 11 – Bonus
[abstract1,path1] = mondrian(‘art1.png’)
=> abstract1 = [71; 88; 220] (dimensions 1x1x3)
=> path1 = [4,2,1]
In the original 8×8 image, quadrants 1,2, and 3 all have the same color, while quadrant 4 does not. Now consider quadrant 2. Within quadrant 4, the quadrants 1, 3, and 4 all contain the same color, while quadrant 2 does not. Now consider that quadrant 2. Within that quadrant 2, the quadrants 2, 3, and 4 all contain the same color, but quadrant 1 does not. Now consider that quadrant 1. Since it is a single pixel, that is the first output. The second output is the order of the quadrants: [4,2,1].
Notes:
● The example image is upscaled so that you can see it – the real one is 8×8.
Homework 11 – Bonus
Function Name: taSort Inputs:
1. (struct) Nx1 structure array of TAs Outputs:
1. (struct) Nx1 sorted structure array of TAs Banned Functions:
sort(), sortrows(), max(), min()
Background:
Traditionally, CS 1371 TAs select which recitations they get based on seniority. However, you, a newly hired CS 1371 TA, want to try doing something different! You want to sort the TAs based on a variety of factors, so you naturally turn to MATLAB to help you out.
Function Description:
Write a function in MATLAB to sort a Nx1 structure array. Each structure will represent a TA. You have been provided a file, compareTAs.p, which contains a helper function that compares two TAs. Given two structures in the vector, putting
compareTAs(ta1, ta2)
in your code will return
● 0, if ta1 and ta2 are identical
● 1, if ta1 should come after ta2 in the sorted structure array
● -1, if ta1 should come before ta2 in the sorted structure array.
Sort the structures so that for any two indices i and j, with i < j, using c ompareTAs() with the structure at the ith index in the first input and the structure at the jth index in the second output returns -1.
Notes:
● You must use compareTAs() in your code to solve this problem.
● Do not try to guess what compareTAs.p is doing to compare two structures.
Hints:
● One possible strategy is to repeatedly iterate through the vector, and if two consecutive elements are in the wrong order, swap them (this is known as bubble sort).
● Another possible strategy is take the first structure and put it in a new vector. Then, take the second structure, and iteratively compare it to the elements in the new vector until you find where it belongs, then insert it into the correct place. Repeat this process,
Homework 11 - Bonus
inserting each element into its correct place in the second vector (this is known as
insertion sort).
● Feel free to try coming up with your own way to solve the problem!
Homework 11 - Bonus
Function Name: battleZone
Inputs:
1. (char) Filename of the battlefield
2. (double) Number of days of fighting
File Outputs:
1. A .txt file of the updated battlefield
Background:
As the high-ranking General you are, it is your job to plan out your battle strategies carefully to ensure the success of your troops. You are aware that battles are complex and disordered, but you can still identify a few trends that happen in terms of the movement of your troops on the battlefield. With little time on your hands, you call upon your trusted ally MATLAB to analyze the field and determine the course of the battle over the next few days.
Function Description:
You are given a text file containing a map of a battlefield, with the characters '.', 'A' and 'i' representing tiles of open ground, encampments, and soldiers respectively. Every day, some changes occur to the battlefield as the fight progresses, based on the following criteria:
1. A tile of open ground will become a soldier if it is adjacent to at least one encampment. Otherwise, nothing happens.
2. A soldier tile will become an encampment if it is adjacent to at least two soldiers. Otherwise, nothing happens.
3. An encampment become an open tile if it is adjacent to fewer than two soldiers. Otherwise, nothing happens.
An element is considered adjacent if it is directly above, below, to the right of, or to the
left of the element in consideration (diagonals are NOT considered adjacent). You must extract the map from the text file, update the map to show its status after N days and print out the new map to a new file with the same name as the original, but with '_updated.txt' appended.
Example:
N=2
map = 'A i i' '. i i' '. i A'
'.A.' ===> ‘iAi’ ===> ‘iAi’ ‘. i A’ ‘. i .’ ‘. i .’ Initial Field Day 1 Day 2
Notes:
● Do not ignore edge and corner cases, these tiles will have fewer adjacent tiles but still follow the same rules.
● The whole map must be updated all at once.
Homework 11 – Bonus
Function Name: trickOrTreat
Inputs:
1. (struct) 1XN Vector of structures representing houses
2. (cell) Mx2 cell array of candy preferences
3. (double) Number of houses you can visit
Outputs:
1. (cell) Px2 cell array of candy you have at the end of the night
2. (cell) Order of houses which you visited
Background:
It’s Halloween! After you have your spooky costume and completed your spooky CS 1371 homework, it’s time for the most important part of Halloween: candy! Your neighborhood has some great socially distant trick or treating, but you can’t go to every house because you need to wake up early to go to CS 1371 lecture! Naturally, you turn to MATLAB to help you plan out your Halloween night.
Function Description:
You are given a vector of structures where each structure represents a single house. The structure will have a ’Name’ field, containing the name of the family in the house, a ‘Count’ field, containing the number of candy you can get from that house, and a ’Candy’ field, containing a cell array of the types of candy that house has. You are also provided a cell array with the names of candies you like in the first column and the corresponding numerical rating value for each candy in the second column. Determine the total score of every house by multiplying the number of candy you can get by the rating of your favorite candy you can get from that house.
You then need to determine the order in which you will visit the houses. You will always start at the middle house, your own, and get candy from your own house. Store the name of the candy that you got from each house into the first column of a cell array, and the amount of candy you got into the second column.
Then, you will either go to the house on the left or on the right, choosing the one with the higher score. Store how much candy you got at that house by either adding the name and count to the bottom of the cell array if you have not already gotten that type of candy, or by adding the number of that type candy you just got to the number of that type of candy you already have.
After that house, you will go to either the closest house on the left of the house you are at that you have not already visited, or the closest house on the right in the vector that you have not already visited, again picking the one with the higher score. If you are all the way to the right or left, then you keep going in the opposite direction. If the houses on the left and right have the same score, go to the house in the direction of your own house (in the middle). For each house, repeat the process of storing the candy you got. Output a cell array of the names of the houses you visited in the order you visited them and the cell array of the candies you got.
Homework 11 – Bonus
Example:
houses =
Name
‘Htay’
‘Ho’
‘My house’
‘Schmitt’
‘Profili’
Count
6
6
9
2
2
Candy
{‘Twix’,
‘Skittles’,
‘Kit Kat’}
{‘Mochi’,
‘Twix’,
‘Skittles’}
{‘Mochi’,
‘Kit Kat’}
{‘Kit Kat’,
‘Pocky’,
‘Mochi’}
{‘Mochi’,
‘Skittles’}
candy =
‘Twix’
4
‘Pocky’
1
‘Skittles’
3
‘Mochi’
5
‘Kit Kat’
2
[bag,path] = trickOrTreat(houses,candy,4)
bag = {‘Mochi’,17;’Twix’,6}
path = {‘My House’,’Ho’,’Htay’,’Schmitt’}
First, calculate the scores of all the houses, which are [6 * 4, 6 * 5, 9 * 5, 2 * 5, 2 * 5] = [24,30,45,10,10]. We then start at My house, since that is in the middle. We add 9 Mochi to our bag. We then compare the Ho house to the Schmitt house, since they are to the left and right, and realize the Ho house has a higher score. We then move to the Ho house and add 6 Mochi to our bag. We then compare the Htay house to the Schmitt house and realize the Htay house has a higher score. We then move to the Htay house and add 6 Twix to our bag. Since there are no houses to the left, we move to the Schmitt house on the right, and then add 2 Mochi. That was the fourth house, so we stop there.
Notes:
● Every candy has a unique rating value.
● There will always be an odd number of houses.
● At each house, you only have to consider at most two houses for the next house you
visit.
● You are guaranteed to have a rating for every candy you can find.
● The number of houses you can visit includes visiting your own.
● The names of the houses will be unique.
Homework 11 – Bonus
Function Name: imitationGame
Inputs:
1. (char) Input message
2. (char) 26x(2N) array of rotor settings
3. (char) Mx2 array of plugboard wirings
Outputs:
1. (char) Output message
Background:
You are a British codebreaker working at Bletchley Park during World War II. Your task is to help the British government crack the Enigma machine, which Nazi Germany used to encode messages. While your co-worker Alan Turing works on his Bombe machine, you take a different approach. You’ve developed a handy MATrix LABoratory (MATLAB) that you believe can help turn the tide of the war. Thanks to some Polish cryptographers, you have a pretty decent understanding of how the German Enigma works, so you decide to create a simulation of it in MATLAB!
Function Description:
The Enigma machine was designed to encrypt a message one letter at a time. First, the letter was typed into a machine. The letter went to the plugboard, where it could be switched with another letter or remain the same. It then went through a series of rotors, each of which swapped letters in a fixed pattern. It then went through the rotors in reverse, then back through the plugboard, to get the encrypted letter. After each letter, the first rotor would shift by one, meaning that typing the same letter twice in a row resulted in two different letters output. After 26 rotations of the first rotor (i.e all the way around), the second rotor would shift by one, and after the second rotor rotated 26 times (and the first rotated 26 * 26 = 676 times), the third rotor would shift. The last rotor, known as a reflector, did not rotate, but simply linked two letters together. This made Enigma very difficult to crack.
Write a function that takes in an input message, a character array describing the rotors, and a character array describing the plugboard wirings, and outputs the encoded message. If there are N rotors, including the reflector, the rotor array will be 26 x (2N). The first two columns of the array describe the first rotor. Each row represents a letter and what it is mapped to. For example, if a row is ’AD’, then when a letter A is input into the rotor, it comes out as D. If going through the rotors in reverse, then an input of the letter D is mapped to A. The next rotor is represented by the next two columns. The last two columns represent the reflector. A rotation of the rotor is modeled by shifting the second column of each rotor down by one, so that the element in the first row becomes the second and the last element becomes the first. The reflector does not rotate.
Homework 11 – Bonus
The M plugboard wirings are represented by a Mx2 character array. Each row represents two letters that are connected to each other. For example, if a row is ’DZ’, then D becomes Z and Z becomes D when going through the plugboard. Using these components, the action of the Enigma machine that you should model is described below.
Example:
imitationGame(‘aa’,rotor1, [‘ad’;’cn’]) (rotor1 is the one used in the test cases) =>
The first letter we wish to encode is ’a’. We set the encrypted letter to be ’a’. One of the rows in the wiring is ’ad’, so we set the encrypted letter to be ’d’. rotor1 is 26×6, so we know there will be two rotors and a reflector. In the first two columns of rotor1, we see that one row is ’dp’. Thus, the encrypted letter becomes ’p’. In the third and fourth columns, we see that one row is ’pc’, Thus, the encrypted letter becomes ’c’. In the last two columns (the reflector), we see that one row is ’ca’, so the encrypted letter becomes ’a’. In the third and fourth column, we see that one row is ’ua’, so the encrypted letter becomes ’u’ (note that this is in reverse!). Finally, in the first two columns, we see the row ’ku’, so the encrypted letter becomes ’k’. None of the plugboard wirings have the letter ’k’, so the first letter in the output is ’k’.
We rotate the second column by one unit downward (the first row is now the second, the second the third, etc.) The letter we once again wish to encode is ’a’, so the encrypted letter is ‘a’, then ’d’, as in the first letter. Now however, the relevant row in the first two columns is ‘dc’, so the letter becomes ’c’. Then, in the third and fourth columns (which are unchanged!), we see the row ’ch’, so the letter becomes ’h’. In the reflector, we see the row ’hm’, so the letter becomes ‘m’. In the third and fourth columns, we see the row ’zm’, so the letter becomes ‘z’. In the first and second column (second is shifted), there is the row ’nz’, so the letter becomes ’n’. One of the wirings in the plugboard is ’cn’, so the letter becomes ’c’. Thus, the output is ’kc’.
Notes:
● Do not hardcode for the number of rotors or the number of wirings!
● Each letter only passes through the reflector once.
● Note that the example is not the same as the first test case. You can still use the solution
to verify the example provided.
Hints:
● You will need to think of a way to remember when to rotate the rotors.
● One flaw of the Enigma, which was used to help crack the machine, is that no letter can be encoded to itself. If your machine encodes a letter to itself, something has gone
wrong!
● The circshift() function will help you shift the rotors.