Introduction
TipTop: Our Last Hope
How it Started
The year is 2097, and the world has gotten as close to a utopia as it ever has.
All diseases are cured, all needs are provided for, and it appears all problems in the world are solved... all but one: loneliness.
So a group of entrepreneurs gathered and came up with an original idea: "What if you could be friends with people digitally, online? What if you could see what they do and feel close to them? Something like... hmmm... what's a good way to describe it... like an online social platform? I know no one has ever heard of a fresh idea like this, but I think it just might work."
And it did. They called it TipTop. Millions of users flocked to it to find joy. Never in the history of earth had so much dopamine been present at once. The response was overwhelming. Many called it one small Tip for man, one giant Top for mankind.
The Assignment
Like all other software, the work is never done as there are always features that must be added and bugs that must be fixed. You are tasked with implementing some of these features to increase the happiness of humanity (and the revenue of TipTop for this coming quarterly release). Upon successful completion of your tasks, you will be awarded either a brand new flying car of your choice, or a number of marks for this unit (the unit's teaching team will decide which).
Getting Familiar
You are given a scaffold containing many files. You are expected to complete the assignment inside this scaffold. There are 3 tasks and 3 files you'll need to work on: user.py, session.py, and connections.py. While they are all part of one system conceptually, the files don't actually depend on each other in any way. That means, even if you don't do tasks 1 and 3, for example, you can still work on task 2 with no problems.
Please download the assignment scaffold from here and open it in VS Code:
We will go through the details of each task and what needs to be implemented. But it's good to first get ourselves familiar with the concepts and objects we are going to be working. The parts of the system you're tasked with are around these concepts:
User
A user is an object of the User class. It contains basic information for a user like their username and their password, and the logic for operations such as changing the password or posting content.
TipTop
A TipTop is what the users post online. Each TipTop is basically a picture: a collection of pixels in a rectangle. There is no TipTop class - the TipTop data is carried in 3D arrays.
The first dimension of the array contains the rows. The second dimension will be the pixels in that row. The third dimension is the data of one single pixel and it has 3 integers: R, G, and B. The red, the green, and the blue of each pixel, which will collectively determine what color that pixel is. Here is an example of a 4x3 TipTop array:
[ [P00, P01, P02], [P10, P11, P12], [P20, P21, P22], [P30, P31, P32], ]
In this demonstration, each pixel is named by the indices by which it can be accessed. The pixel P02, for example, can be accessed through the first row (index 0) and the third column (index 2). As described above, each pixel is an array with exactly 3 numbers. So if we were to expand the shape above to a flat 3D array, it would look like this (the brackets don't mean this is a Python list - as mentioned before, this is a 3D array constructed with ArrayR objects):
[ [[10, 42, 134], [149, 252, 9], [0, 11, 11]], [[205, 90, 100], [34, 200, 150], [11, 45, 78]], [[125, 67, 89], [255, 255, 255], [0, 0, 0]], [[45, 85, 200], [60, 120, 180], [70, 140, 210]], ]
Session
A session is when a user opens a TipTop, from which point they can swipe to get new TipTops, go back and forward, leave comments, etc. Whenever a session starts, a new object of the class Session will be created. That's where the information and the functionalities of one session is stored.
Connections
The whole purpose of TipTop was for digital friendship, and that's what it does. Users can become friends with each other.
All information about friendships comes in the class Connections. An instance of this class is created in the app to handle connections. This object will hold the information of all connections, and a few methods that will be useful for the application.
The Remote Server
Occasionally, you will need to communicate with parts of the app that aren't within the code you're given. For instance, once a user leaves a comment on a TipTop, you will process the comment but to actually post it, you will send it to the remote server. This is simulated in a file called remote_server.py, which includes a small number of methods. In different parts of the assignment, you will be asked to call these methods when necessary.
Not So Fast
You have now seen a high-level overview of all the relevant concepts. But before we go through the details of what actually needs to be implemented, I must warn you this is a highly sensitive codebase. You could even say you are given a lever that controls how half the humans on earth behave every day. As such, there are certain restrictions on what is allowed to be used in the code and what is not.
These restrictions act as hurdles for this assignment - not following them in a task will result in an automatic 0 for that task. So make sure you understand and follow them. Let's proceed to the "Restrictions" slide which explains these in details.
Restrictions and Assumptions
Restrictions
Everything listed here as a restriction is not allowed to be used in this assignment. Using them in a task will automatically result in a 0 mark for that task.
Anything that's not restricted here is allowed. For more confidence, and from the questions we've heard in the past, we will listsome of the allowed options here explicitly. But again, the main rule is anything that's not restricted is allowed.
❌ You cannot...
·
Use AI generated code in any part of the assignment. This will not only result in a 0 but will also raise a plagiarism case for you in the faculty. I come from year 2097 so trust me when I say you don't want this on your record.
·
·
Use Python lists, sets, or dictionaries, in any form. That includes list comprehension (e.g. [x for x in range(...)]) and type conversion (e.g. a = set(... some other type...)). Note that slicing other data structures using Python's syntax of obj[index1 : index2] also returns a Python list, which makes it banned.
·
·
Use Python sort functions, in any form. That includes the sorted(...) method, calling list.sort(), etc.
·
·
Implement your own sorting algorithms, even if they are the ones taught in the unit. This will change for your next assignment, but in A1, try to use the provided data structures instead.
·
·
Use recursion in any of the tasks. This will also change in future assignments, but it's not allowed in A1 yet. If you don't know what recursion is, don't worry about it - we'll cover it later in the unit.
·
·
Use Python's reverse or reversed functions.
·
·
Implement something that's already given to you. Have a look at what's in the scaffold before you start. If you need a linked list (or anything else provided to you for that matter), you should use the one given to you instead of implementing your own version of it.
·
·
Import anything other than the files given to you in the scaffold. That includes standard Python libraries or external packages.
·
·
Create your own files - all tasks can and should be done in the files already provided to you in the scaffold.
·
·
Change any files other than user.py, session.py, and connections.py.
·
✅ You can...
·
Use other Python functions like min, max, enumerate, map, etc.
·
·
Define your own functions, your own classes, functions inside functions, etc. as long as it's in the same scaffold (that means no new files).
·
Assumptions
There are some assumptions we make in solving the tasks. These may or may not help you in implementing your solution. But either way, they are listed here so you'd know your code will be marked according to these assumptions. The list below are some general ones, each task may have some additional assumptions on top of these which you can find in the relevant slides.
·
You may assume all comparisons are done in O(1). While some of the slides in pre-readings and the workshops talk of the cost of comparison as something separate to be analysed, and while that is correct and important in theory, in the case of our assignments we assume this to be constant time.
·
·
You may assume Python numbers can grow large with no limits, without affecting the cost of operations. While we know after a certain number of digits, the operations on a large number won't be constant time anymore because the number won't fit in one computer word, we assume Python can magically handle numbers of any size and do operations on it in O(1) time. That means, multiplying 123456789123456789 by 123456789 can be done in O(1).
·
Marking Process and Criteria
Your work will be marked on 3 aspects: the functionality, the approach, and your analysis. Different tasks will have different number of marks allocated to each category but as a general estimate, you can expect something between 55-85% of marks for each task in "functionality", with the remaining marks distributed between "approach" and "complexity analysis".
Each of these is explained below. There are also some hurdles as mentioned before. If any of these aren't met, that task will get a 0 for all 3 aspects.
Functionality
This means whether your code actually works, regardless of how you've implemented it, and how efficient it is.
There is a number of automated tests for each task, which will simply run your code with some input and will check what your code does/what output it produces.
Not all tests have the same number of marks. The more challenging the test, the more marks it will grant.
These tests are crafted by us to cover every edge case and all possible scenarios according to the assignment specs. You will not see these tests - if you want to make sure your code works properly, you will need to test it for yourself. More details in the "How do I" slide.
Tests will be run on Ed, and Ed will terminate your program if:
·
It prints too many lines in the output
·
·
It takes too long to execute (the entire program should finish in a few seconds)
·
Unless there are major flaws in the code, neither of these will be issues to worry about. Make sure you don't submit your assignment with too many print statements, and make sure you don't have any infinite loops that could cause your program take more than a couple of seconds to run.
Lastly, when running the tests, we'll remove all files from your submission except the files you were meant to modify (see the Restrictions slide) and will insert the default version of those files. That means, if you make any changes to these files such that your code depends on it, those changes are simply not going to be there when the tests are run and your code may break.
For all of these reasons, make sure you always press the "Check" button on Ed before submitting your work. That will ensure the tests run properly on Ed.
Approach
Like any other program, this assignment can be implemented in many different ways, but only a few of those are good approaches towards the challenges explained. That's what the approach mark in the assignment represents, and one of the main things you need to be careful about if you want to get full marks isselecting the right data structures.
You will be storing and manipulating data in the assignment and you need to pick the correct data types for them. There are 2 aspects to choosing the right data types:
·
Efficiency: if there is a certain data structure that performs better for what you are implementing (i.e. has a better time complexity) then that data structure is likely the best choice.
·
·
Appropriate for the Requirements: there may be cases where multiple data structures can be used in ways to achieve the same efficiency. When that happens, you need to think about which one is the most robust choice. Here are some points to consider:
·
o
Do you need to twist the data structure into some unexpected shape for it to do what you can achieve quite straightforward with another data structure? If so, you're making your code more complex, more prone to errors, and therefore less robust.
o
o
Does your choice of data structure expose methods, attributes, and values, that should ideally not be exposed? For instance, a stack only allows you to access the top element, and only insert elements to the top. You will never be able to mistakenly change the order of the elements in the stack, you will never be able to accidentally change any of the values. So if that's the functionality you need, using an array may not be a good idea because then all of those mistakes are possible in your code, hence making it less robust.
o
Analysis
As you will see, some functions ask you to analyse their time complexity once you're done with them. What we expect here is the same as what you do in the first couple of weeks of classes. We have put together some good and bad examples of how the time complexity should be analysed/documented in your code here: https://edstem.org/au/courses/25271/lessons/84607/slides/577622
Hurdles
The first set of hurdles are the restrictions listed in the slide. Using banned options will mean the expected learning from the assignment did not happen, and no marks will be awarded.
Additionally, each task must pass a few particular tests to get any marks. These will be the most basic tests.
In other words, if the code you write is not doing what the task asks at all, then the approach and the complexity of the code are irrelevant.
The good news is, all of these hurdles are given to you. In the scaffold you will find a folder called "tests" and a file "run_tests.py". If you run this file, it will run the hurdles for you and you can see if you're passing them. In order to run the hurdle tests for task 1, for example, you can type this in your terminal:
python3 run_tests.py 1
If python3 is not recognised as a command, try replacing it with python. If that's not found either, you may need to install Python on your computer.
Late Submissions and Extensions
In line with the general Monash policy on assessments, late submissions will receive a 10% late penalty for every day after the due date, until 7 days when they just can't be accepted anymore.
For information about Special Consideration and Extensions, please read this slide on Ed.
How do I...
Test my code?
You can write tests for your code in 2 ways.
1. In each file, there is a section at the bottom that you can use for interacting with your code.
Add any logic you'd like there, and simply run the file to see the output in the terminal. If you open user.py you will see a couple of lines already provided for you as a template. Do more, call more functions, make more changes, and check if the outputs are still what's expected.
If they are not, print the values, use breakpoints, and debug your code.
If you need help with any of that, feel free to ask the teaching team either on Ed or in person in your classes.
2. Alternatively, you can write tests how we wrote the hurdle tests. This is a more standard approach, and it's called unit testing.
Feel free to open the tests/test_task1.py file, for example, and see how the tests are created. Then follow the same logic and add more tests.
For the sake of testing your code, you can use any of the banned items if you think they could help you test the code more easily. But these must be strictly in either the tests folder or the testing section at the bottom of every file, under if __name__ == '__main__'. If you use the banned options anywhere else, it will fail the automatic hurdles.
You can (and should) always make sure your automated hurdles are passing by pressing the "Check" button on Ed before you submit.
Ask a question on Ed?
The most important thing here is to not reveal your code when you're asking a question on Ed. This is a public forum (no private posts are allowed for assignment queries) and all students can see what you write there. That means, if you share your code, you've basically shared it with everyone and it will be considered plagiarism.
That includes sharing your tests too! One of the main learning objectives of a take-home coding assignment is for you to test it, and make sure it's working as expected. You will have to think of edge cases, you will have to understand the requirements and come up with examples for them. While we don't ask you to submit these in your code, you are not allowed to share them with other students - that's part of the work.
Additionally, the teaching team are not supposed to tell you how to solve the problems - it is an assignment worth 15% of your marks, after all. So please don't ask questions like "how do I do this thing?". Think about it on your own, and when you face problems in your thinking, share those. Write down what you have thought of, why you think it doesn't work, etc. When we see your thinking, we can guide you in the right direction.
Reference a bit of work?
It's completely okay if you look things up online about how Python works or how certain algorithms are implemented. And there is no need to reference them if you simply learn the theory, and implement your own version of something. However, if you copy a piece of code directly from the internet, then make sure you leave a reference in the function docstrings to show the name of the author/website you copied from, the URL, and the date if available.
Task 1 - Users [40 Marks]
You are given a User class. This is where most user-related logic happens. You are given an empty body of a few methods. Implement them such that they meet the requirements listed below.
1.1 - User Password
Once a user is created, their password will be sent to the __init__ method of the class. This is stored on the password attribute.
Users can change their password. This logic should be handled by the change_password method, which takes the new password. There is a condition, however. Users cannot change their password to something they used before - all passwords must be new.
You can assume the moment the user object is created is when they made their account, and the password given to __init__ is their first password. From that point onwards, whenever they try to change the password, it should be new.
If the change_password method is called with a used password,the function should raise aValueError. Otherwise, it can change the password, and it must call the user_password_changed function from the remote_server once the password is changed.
Example
The user is created with password abcde.
The change_password method is called, and the new password is abcde: we get ValueError.
The method is called again, this time with abcde123: the password is changed.
The method is called again with abcde: we get ValueError.
Assumptions
You may assume that no user will ever change their password more than 50 times.
1.2 - Posting TipTops
Now that our users can manage their accounts, we want them to be able to post TipTops. This will be done using the post_tiptop method.
This method takes the TipTop as its input, which will be a 3D array as described in the introduction slide. But remember, this is 2097, and things are more advanced. A normal upright picture is not interesting to anyone. What makes it a TipTop is that it's upside down, and it's mirrored.
So once this function is called, the first thing we need to do is to flip the given TipTop both horizontally and vertically.
Additionally, to pay our respects to what's left of the earth at this time, and given blue is the rarest color pigment in the nature, no social media is allowed to have any content with even a single pixel with too much blue. That means, we need to modify this TipTop before we can post it, so the blue component (the third of RGB) of no pixel ismore than 200. If any pixel's blue is higher than 200, we'll simply bring it down to 200.
After these adjustments are made, the TipTop is ready to be sent off. You can do so by calling the post_tiptop function of the remote_server.
This method's time complexity should not exceed O(P), where P is the number of pixels in the TipTop.
Example
Let's say this is the TipTop when the function is called:
[10, 42, 134] [149, 252, 9] [0, 11, 11] [205, 90, 100] [34, 200, 150] [11, 45, 78] [125, 67, 89] [255, 255, 255] [0, 0, 0] [45, 85, 200] [60, 120, 180] [70, 140, 210]
Once we make these adjustments, the TipTop will look like this:
[70, 140, 200] [60, 120, 180] [45, 85, 200] [0, 0, 0] [255, 255, 200] [125, 67, 89] [11, 45, 78] [34, 200, 150] [205, 90, 100] [0, 11, 11] [149, 252, 9] [10, 42, 134]
Assumptions
·
All 3 components of all pixels (RGB) will be an integer between 0 and 255.
·
·
You may assume every TipTop will have at least 1 pixel.
·
·
You may change the given arrays in place or make new copies of them - it's fine either way.
·
·
You may assume calling the remote_server.post_tiptop function is O(1).
·
1.3 - User Previews
One of the features of the app is to show a preview of a user's recent TipTops without having to open their profile.
For this feature to work, we need to implement the get_preview function. This function doesn't take any inputs, and it returns the last (up to) X TipTops posted by this user,where the first item is the most recent TipTop. It's up to you to choose what data structure you use to return these, just make sure it's one of those given to you in the data_structures folder - don't implement your own data structures.
For this function and all other functions from now on, when we talk about "TipTops posted by the user" we mean after they are processed in post_tiptop (i.e. the flipped version we send to the remote server, not the raw one). When you're choosing a suitable data structure for this task, consider thatthepost_tiptop method will be called a lot more thanget_preview. That means, if it ever comes down to an efficiency trade-off between these two, post_tiptop is priority.
X is initially 3 (i.e. the first time we get the preview, we'll get up to 3 TipTops). But this is a dynamic and adaptive platform. So if there is a lot of interest in a user's preview, the preview becomes longer. That means, every time the get_preview method is called on a user, the maximum number of items returned in thenext preview (i.e. X from above) should increase by 1.
However, to avoid having to remember all the TipTops the user has posted, we'll only usethe new TipTops to fill up this preview buffer. This may sound a bit vague, but the example below will make it clear.
Example
For simplicity's sake, we call the TipTops T1, T2, T3, ... in the order they are posted.
Consider this sequence of events as an example of what should happen:
·
T1 is posted (i.e. post_tiptop is called)
·
·
T2 is posted
·
·
get_preview is called -> it returns [T2, T1] (capped at 3 - the cap now increases to 4 for next time)
·
·
T3, T4, T5, T6 are posted
·
·
get_preview is called -> it returns [T6, T5, T4, T3] (capped at 4 - cap increases to 5)
·
·
get_preview is called again -> it returns the same items [T6, T5, T4, T3] because although the cap was 5 (and now it becomes 6), at the time when the preview size increased, we only had these 4 TipTops in the preview. The remaining spaces in the preview will always only be filled with the future TipTops.
·
The examples above use [T2, T1] notation, but that doesn't mean your return type has to be an array. As mentioned above, it's up to you to choose the most appropriate data structures.
Visual Demo
Hopefully the description above made sense and the examples clarified what's supposed to happen. But if you're in doubt, this video might help.
Notice that in the video, we leave some empty spots in the preview buffer just to demonstrate the preview size. You're not supposed to return empty spots / None values if the preview has empty spots in it. This is simply demonstrating what it means when we say "the preview is only filled with new TipTops, it doesn't go back in history".
1.4 - Generating Feeds (1054 Only)
This task is only for FIT1054 students. FIT1008/2085 are welcome to attempt, but you don't need to, and there are no marks.
All the previous methods were only concerned with what the user posts. But we also need to implement the logic of the user seeing their friends' posts.
That happens in the generate_feed method, where we merge the TipTops posted by this user's friends into one timeline.
It takes one argument: an array of linked lists. Each linked list contains the TipTops posted by one of the user's friends,in the order they were posted, along with the timestamp of when it was posted. Here is an example of how this input could look like for a user with 5 friends, where the first one has 4 TipTops, the second one has 1 TipTop, the third one has 3 TipTops, the fourth one has 1 TipTop, and the last one doesn't have any:
[ Linked List: (10, T1) -> (13, T2) -> (15, T3) -> (19, T4) Linked List: (9, T5) Linked List: (20, T6) -> (25, T7) -> (40, T8) Linked List: (14, T9) Linked List: <empty> ]
Each item in each linked list will be a tuple of two elements: the first element is the timestamp of that TipTop, the second element is the TipTop itself. Timestamp means how many seconds after the program started it was posted. So in the example above, the first TipTop posted was T5 by the second friend, and the last TipTop posted was T6 by the third friend.
Now we want to generate a feed for this user. This feed should also be a linked list, showing a number of TipTops capped at a limit (which we'll call X for now).
We don't want the user to miss any TipTops, so the feed should start from theoldest TipTops available and go forward (oldest means the smallest timestamp). But we also don't want the user to miss any of their friends! We want to try and include as many of their friends as possible. After many scientific experiments and simulations, we have figured out how to balance joy and relevancy for the users. Follow this algorithm carefully or the user ends up putting their phone down and getting outside:
Until all friends who have a TipTop (e.g. the first 4 friends from the example above) have at least one of their TipTops in the feed, priority is given to those who haven't had any of their TipTops in the feed yet. There is just one exception: if two TipTops are posted within 3 seconds of each other, it's fair to assume they must be related. Therefore, if someone's TipTop goes in the feed and their next one is related (i.e. it's within 3 seconds), we don't assume they have contributed to the feed yet, and they retain their priority as someone who is yet to be included. If this sounds vague, please read the detailed example below.
As soon as all friends who have a TipTop have at least one of their TipTops in the feed, we drop all matters of priorities and just start going off based on the timestamps to fill up the rest of the feed: oldest TipTops first.
Lastly, the feed size cap starts at 1. But just like the preview feature, it's dynamic, and every time the generate_feed function is called, this size willdouble. If there are not enough TipTops to fill up the feed, then just include as many as there are, in the same order described above; that is, we should never see two TipTops from the same user before all users have had one of their TipTops seen. See the examples below.
There are partial marks for this function. So even if your implementation doesn't take care of the 3-second rule, still submit your code, you'll get some marks if the rest of the logic is correct.
Example
Let's call the function multiple times using the same input as above (5 friends, with 4, 1, 3, 1, and 0 TipTops respectively).
The feed size is currently 1, so when I call the function, I'll simply get T5 as it's the oldest TipTop. The feed size now doubles to 2.
I call the function the second time, and I should get a linked list containing T5 -> T1 because T1 is the next oldest. The size doubles to 4.
I call the function again, I should get T5 -> T1 -> T2 -> T9. We already had a TipTop from friend #1 (T1), but the next one is within 3 seconds so it must be related. Therefore we didn't count friend #1's contribution complete yet, and considered their next TipTop (T2) in our search for the next oldest, and it was indeed the next oldest TipTop. Note that even their next TipTop (T3) is still within 3 seconds of T2 so it's part of the same story and the contribution isn't complete. However, although we are considering T3, there is another TipTop that's older and is also from a user who hasn't contributed: T9. The size doubles to 8.
I call the function again, I'll get T5 -> T1 -> T2 -> T9 -> T3 -> T6 -> T4 -> T7. That's because after the first four, friends #2 and #4 are done, and #5 didn't have any TipTops to begin with. It's only between friend #1 and #3, and neither of them have contributed to the feed yet (we haven't seen any TipTops from #3, and the ones we have seen from #1 seem to have been in connection with the next one, so the contribution isn't complete yet). Between T3 and T6, T3 is the older one so it gets in. Now friend #1 has finally contributed, because their next TipTop is more than 3 seconds away! Therefore, the next onehas to be from friend #3, as the only user who hasn't contributed. So we get T6, and the next one is more than 3 seconds away. At this point, all users who had a TipTop have contributed, so priorities aren't relevant anymore and we just continue adding the next oldest TipTops until the feed is full. The next oldest one is T4, followed by T7. The feed size now doubles to 16.
Assumptions
·
You can assume the order of the TipTops in each linked list is according to their timestamp. I.e. the first TipTop is always the oldest.
·
·
You cannot assume there is any order among the users.
·
·
You cannot assume all users will necessarily have a TipTop. Some of them may just have an empty linked list, meaning the user hasn't posted anything.
·
·
You can assume the timestamps across the whole input are unique. I.e. no two TipTops will ever have the same timestamp.
·
·
You are allowed to change the input object if you need to, or to make copies of it.
·
Task 2 - Sessions [35 Marks]
Now that we have users and their feeds, we move on to implementing sessions. A session is simply started when a user opens a TipTop. Implement the functionalities required for a session inside the Session class, as described below.
2.1 - Initialisation
Once a session is started, a new object of Session class will be created. We need to know which user has started this session, and the initial TipTop they opened - both of which are arguments to the __init__ method.
While the session is open (i.e. we have the object), we should be able to get the currently open TipTop in this session by calling the get_current_tiptop method. Remember that TipTops are 3D arrays - that will be the case for the __init__ function's arguments, and it will be what this function returns too. Initially, when the session has just started, the current TipTop will be the one the session was started with. But as the user navigates around, this will change.
Example
The user cool_username has started a session with a small 1-pixel TipTop: [[[10, 244, 200]]].
The get_current_tiptop method is called. It will return the 3D array above.
Assumptions
·
Because the blue part of all TipTops are capped to 200 at the time of posting (in the previous task), you can assume all TipTops passed to you in this class will have their blue capped at 200.
·
·
TipTop is a responsible platform and for the well-being of its users, it has a limit on how many TipTops they can open in a single session. This limit is not the same for all users or all times - it's calculated dynamically. You are given a number max_tiptops_in_session in the __init__ method. You may assume for this entire task/class, there will not be more than max_tiptops_in_session TipTops opened by the user. You may assume this number is larger than 1 for all users at all times.
·
2.2 - Navigating
Our scientists have found the most efficient way of enabling user interactions: swiping around. This is elegant because it takes so little effort from the user, yet it shapes a strong behaviour more than just sending input to the program. We want to support three swipes: up, right, and left.
⬆️Swiping up means the user wants to see the next TipTop. The logic for this should happen in the swipe_up function, which will take one argument: the new TipTop for this user to see.
➡️Swiping right means the user wants to go back one TipTop. That means the current TipTop will become whatever the user had before this one. The user can swipe right multiple times, which should just go further and further back. If the user reaches the initial TipTop the session started with, then swiping right will not do anything. The logic for this swipe should be implemented in the swipe_right method.
⬅️Swiping left means the user wants to go forward. This is different to swiping up which shows a new TipTop. This can only be used after swiping right. I.e. you can think of this as undoing a swipe right action. If the user hasn't swiped right, then this won't do anything.
❗️ If the user swipes right (goes back), then swipes up (opens a new TipTop), the initial swipe right cannot be undone anymore because a new TipTop has been opened. So swiping left won't do anything. If you want to see this logic in action, open a web browser and play around with the back/forward buttons as you navigate around different pages, and click on links in between. That would be the same logic we are implementing in TipTop.
Example
Let's assume TipTops are called T1, T2, T3, ... in the order the user sees them.
The session starts with T1.
User swipes up -> we get T2.
User swipes right -> we go back to T1.
User swipes right again -> we stay at T1.
User swipes up -> we see T3.
User swipes left -> we stay at T3.
User swipes right -> we go back to T1.
User swipes left -> we go to T3.
2.3 - Blueness
I'm sure you remember the importance of the color blue in TipTop. Let's define the blueness of a TipTop as the number of unique blue values across all its pixels. For example, this TipTop's blueness is 3, because it has 3 different values for blue across all pixels (44, 98, and 132):
[ [[123, 230, 98], [10, 10, 132]], [[39, 0, 132], [209, 0, 44]], ]
Building on top of that, we define the blueness of a session as the median of the blueness across all TipTops viewed in that session. This is an important statistic for us, to ensure we are not exposing too much blue in the app. Implement the get_blueness function so that it returns the blueness of the current session, considering all the TipTops the user has seen so far.
The median of a list of numbers is the number that sits in the middle once we sort the list. For instance, the median of [3, 1, 1, 4, 1] is 1. If the list's length is even, then we take the average of the two median items. For example, the median of [1, 1, 5, 3, 4, 4] is 3.5.
This method should always work in O(1) time.
Example
Let's say the session has just started, and the initial TipTop is the one shown above. If get_blueness is called, we should get 3. That's because there is only one TipTop, and its blueness is 3. So the median blueness is also 3.
Let's say the user continues by swiping up which gives them a new TipTop looking like this:
[ [[123, 230, 0], [10, 10, 1]], [[39, 0, 0], [209, 0, 0]], ]
If we call get_blueness now, the response would be 2.5. Because we have two TipTops, and their blueness is 3 and 2 (only 2 unique blue values in this new TipTop). So the median will be the average of the two, which is 2.5.
The user could do a bunch of swipe left and rights, but going back and forth between the same TipTops won't change the stats. Even if the user watches the same TipTop multiple times, we only ever saw 2 TipTops, and that's what we use in calculating the stats.
2.4 - Pinching Out
Like many other apps, TipTop has a variety of accessibility features. One of these is increasing the brightness of TipTops when the user pinches out on a pixel. Users can pinch out with different intensities. We measure this as an integer greater than or equal to 0. The higher the number, the more intense the pinching out and the more the change in brightness.
Increasing the brightness of a pixel simply means increasing all 3 colors of it (RGB). So when we say "increase the brightness of a pixel by 10" that means increase all 3 colors by 10. But remember! Red and Green should still be capped at 255, and Blue should still be capped at 200.
Let's define the distance between the pixel at row R1 and column C1, and the pixel at row R2 and column C2, as abs(R1 - R2) + abs(C1 - C2) (abs means the absolute value i.e. if it's negative, make it positive). A more intuitive way of saying it is: The distance between two pixels is how many up/down/left/right steps I need to take form one to get to another. The distance between (0, 0) and (5, 6) is 11. The distance between (4, 7) and (0, 8) is 5.
When the user pinches out on the pixel at (R, C) with intensity I, all pixels with the distance of I - 1 or less should increase their brightness according to their distance from (R, C). The pixel at the center i.e. (R, C) increases by I, the pixel at (R + 1, C - 2) increases by I-3, and in general terms, the pixel at (R + x, C + y) increases by max(I - x - y, 0). Again, a more intuitive way of saying it is: You start with I at (R, C), the farther you get the less intense increasing the brightness will be.
Implement this logic in the pinch_out method. The method doesn't need to return anything. It just needs to update the current TipTop accordingly.
Note that once the current TipTop is updated, this could change the blueness of this TipTop and as a result, the blueness of the whole session! If we call get_blueness after pinching out, it should return the correct blueness after these changes (when we say it should update the session's blueness, that means update the existing contribution of this TipTop - it's the same TipTop that's being updated, not a new one).
Example
Let's say the current TipTop is this:
[ [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 255, 200], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], ]
If the user pinches out on row = 2 (remember computer scientists use 0-based indexing! Row index 2 means the third row) and column = 2 with intensity = 3, the TipTop will look like this:
[ [[0, 0, 0], [0, 0, 0], [1, 1, 1], [0, 0, 0]], [[0, 0, 0], [1, 1, 1], [2, 2, 2], [1, 1, 1]], [[1, 1, 1], [2, 2, 2], [3, 255, 200], [2, 2, 2]], [[0, 0, 0], [1, 1, 1], [2, 2, 2], [1, 1, 1]], ]
That is because the center's brightness increases by 3, but the G and B colors are already capped, so only the R increases to 3. And the 4 neighbours of the center become all 2, and their neighbours all 1. All other pixels are untouched.
The blueness of this TipTop was 2 before pinching out, now it's 4.
Assumptions
·
You can assume the row and column given to the function will be valid and within the bounds of the TipTop.
·
·
You can assume the intensity will be an integer greater than or equal to 0. If it's 0, then no pixels should change.
·
·
You cannot assume a TipTop will be pinched out only once.
·
·
You can assume (like all other parts of the assignment) that the current TipTop's RGB values are valid (R and G capped at 255, B at 200).
·
·
You cannot assume the size of the TipTops is limited. We are using small examples here to explain the task, but the TipTop sizes can be much larger than the pinch out intensity.
·
2.5 - Posting Comments
TipTop is no ordinary platform. As such, it allows no ordinary comments to be posted. If any user wants to share a comment, they have to put in the effort and make it a palindrome string. A palindrome string is one that reads the same forward and backward. In this instance, we ignore the space character. An example of a palindrome string is "taco cat". An example of a non-palindrome (and therefore an invalid comment) is "taco dog".
In the post_comment method of the Session class, we want to handle this logic and make sure the comment the user intends on posting is valid. This is normally done with a simple for loop, but there is a problem. Because these comments could be too long, we cannot carry the whole string and send it around the functions. Instead, we are given an iterable object that always only tells us what's the next character in the string. That way, we can start reading the characters one by one, and terminateas soon as we are certain whether or not the comment is a palindrome.
If it's not a palindrome, then this method should return False. If it is a palindrome, that means it's a valid comment so we should call the post_comment method of the remote_server with the correct arguments (i.e. pass it the username, the current TipTop, and the comment_retriever object), and return True.
This function takes 2 inputs: the comment length (excluding the spaces - although we don't have the full string at hand, we know how many characters are in there) and the comment retriever. We will see more about iterables in future weeks, but for now, all you need to know is whenever you need to get the next character, you should say:
next_char = next(comment_retriever)
You can do this only a maximum of comment_length times! Do it more and you'll receive a StopIteration exception! And remember, you shouldn't read a single character more than necessary. If by reading just 2 characters, for example, you can confidently say the string is or is not a palindrome, you should.
Example
Let's say the user is viewing a TipTop asking a riddle "I'm a statement always wrong about integers, but I'm also a mirror of myself! What am I?" and they want to comment "never odd or even". The post_comment function will be called with 14 as the comment length (because we don't count spaces), and the comment retriever will yield the letters n, e, v, ... every time it's called with next. The comment is a palindrome so the method will call the remote server and will return True.
Let's say another user decides to post a comment on the same riddle saying "never even or odd". The function will be called with again 14 as the length, but this time right after reading 8 characters (i.e. the second e from even), we can confidently say this is not a palindrome. So no more characters are read and we return False.
Assumptions
·
You may assume the comment is always non-empty.
·
·
You may assume calling next(comment_retriever) will always only give you lower case alphabet letters (no spaces, no digits, no special characters).
·
Task 3 - Connections [25 Marks]
It's all coming together! One last bit of work (but certainly a more challenging task than the previous two) is handling the connections. Users can become friends on TipTop. But given the basis of these friendships are paid subscriptions, the friendships aren't necessarily mutual - not in 2097. So the way we keep track of these connections is by keeping a list for every user, containing their friends.
3.1 - Initialisation
Once the app loads, an instance of the class Connections will be created. The __init__ method receives two arguments: usernames and connections. usernames is simply an array containing the usernames of all users, in a random order.
connections is a 2D array. connections[i] is an array holding the usernames of all friends of the user with username usernames[i].
Example
Let's say there are 4 users: Alice, Bob, Charles, and Diane. Assume Alice is friends with Bob and Charles, Bob is friends with Diane and Charles, Charles doesn't consider himself to have friends, and Diane is friends with Bob. The two arrays could look like this:
usernames: [Bob, Alice, Diane, Charles] connections: [ [Charles, Diane], [Charles, Bob], [Bob], [] ]
Assumptions
·
You can assume there is at least one user in the system.
·
·
You cannot assume everyone will necessarily have friends.
·
·
You cannot assume the usernames in either of the lists to be in any particular order.
·
·
You can assume all users have unique usernames. I.e. no two users will have the same username.
·
·
You may assume all usernames are valid. That means, no one will have any friends in connections whose username is not present in usernames.
·
·
You may assume the length of usernames is exactly the same as the length of connections (the first dimension). In other words, each username will have a corresponding array of friends.
·
3.2 - Mutual Friends
As mentioned before, not all friendships are mutual in 2097 and TipTop is no exception. That means finding these mutual friendships is very valuable. Implement the method mutual_friends that takes two usernames and returns True if they are mutual friends. Otherwise, it returns False.
This method should work pretty fast.It should always run in a time complexity strictly better than O(N), where N is the number of users.
Example
Let's use the same example as above with the 4 users. If mutual_friends is called with Alice and Charles, it should return False. Because although Alice is friends with Charles, Charles is not friends back with Alice.
If the method is called with Bob and Diane, however, it will return True, because those two are mutually connected.
Assumptions
You may assume both usernames are valid (i.e. they exist in the usernames array above).
3.3 - AI Clusters
You only need to complete one of the tasks below, depending on the unit cohort you are enrolled in.
FIT1008/FIT2085
This task is only for FIT1008/2085 students. FIT1054 are welcome to attempt, but you don't need to and there are no marks.
Like all other online platforms, TipTop is dealing with swarms of bots and crawlers, signing up pretending to be humans. This is a platform for human connection, so we want to get rid of these AI-run bots.
As far as we are concerned, if someone is mutual friends with all of their connections, they must be a bot. But if someone has at least one one-sided connection from either side, they must be human. We want to get rid of these botsand all of their friends, regardless of whether those friends are also bots or not.
So with that in mind, here's how we define an AI cluster: if a user (let's call her Helen) is mutual friends with all of her connections then we know Helen is a bot, and the whole cluster of Helen and her friends is an AI-cluster, with Helen being the center of the cluster. Note that we don't care about whether Helen's friends are also friends with each other or they have any connections outside the cluster. The only condition that matters is that Helen doesn't have any one-sided connections (from either side). So Helen and all her friends should be reported as a cluster, with Helen being the center.
Implement the get_ai_clusters_1008_2085 method, that returns these clusters. It should return acollection of collections. Each internal collection contains the users in one cluster, with the center user of the cluster (e.g. Helen from above) as the first item of the collection. When we saycollection we mean any of the given data structures. You're welcome to return them as a linked list of linked lists, a queue of arrays, or anything else. You will not be marked for this choice of data structure, pick whatever is convenient. The examples below will use an array of arrays.
The clusters you return should not overlap. That means, no user should be part of 2 different clusters. Because of that, you may find that depending on which user you put as the center of the cluster, there might be multiple different valid clusterings of users. For the purpose of this assignment, you're welcome to return any of these clusterings. All that matters is that:
·
The clusters you return are valid (i.e. the center of cluster is a bot and all their friends are included in a cluster - remember we don't want overlaps, so if a friend is already included in some other cluster, they should be ignored from here)
·
·
There aren't any missing clusters (i.e. you didn't miss any bots - all bots belong to some cluster). See the example below for more information.
·
Hint: with the definition above, a user who doesn't have any connections (isn't friends with anyone, and is no one's friend) is a cluster of 1, because it doesn't have any one-sided connections, so it's a bot.
Note on Marking: For this function, there are no marks for complexity analysis of the function or the details of your approach. Instead, we will run your code on large inputs, and you will get full marks if your code finishes in a few seconds. For that reason, try to optimise your code as much as you can, and avoid unnecessary logic in the code, to ensure it will run quickly.
Example
Let's say the connections look like this:
One of the valid responses from the method would be [[A, B, C], [D, E], [G, H], [K]]. Another valid reponse could be [[C, A, B], [E, D, F], [H, G], [K]]. Note that in the second one, the center of the second cluster is E, so both D and F count in this cluster; whereas in the first one, because the center was D, only E could be part of the cluster, because D and F aren't mutual friends.
You can return any valid response, and the clusters don't need to be in any particular order. The only thing that matters is for the first item in each cluster to be the center of the cluster (the one who's mutual friends with everyone).
Here's another example:
Let's say the users are: [A, B, C, D, E] and the connections are:
A: [B] B: [C, D] C: [B, E] D: [B, E] E: []
There are no bots here. B might be particularly interesting here because although it is mutually connected with both C and D, it also has an incoming connection from A, which is not mutual.
Here's another example:
Let's say the users are: [A, B, C, D] and the connections are:
A: [B] B: [A, C] C: [D, B] D: [C]
Everyone is a bot here. But depending on who you will place at the center, the clusters may look different. You could return [[A, B], [C, D]] as one possible combination of clusters, or you could return [[B, C], [A], [D]] as another possible answer. Either one ensures all bots are included, the friends of the bots are included, and no user is seen twice.
FIT1054
This task is only for FIT1054 students. FIT1008/2085 are welcome to attempt, but you don't need to and there are no marks.
Like all other online platforms, TipTop is dealing with swarms of bots and crawlers, signing up pretending to be humans. This is a platform for human connection, so we want to get rid of these AI-run bots.
Here's the definition of an AI cluster: if a group of users are all mutual friends with each other (all pairs) and they have no connection to anyone outside this group, then this is an AI cluster because humans don't form closed colonies like that.
Implement the get_ai_clusters_1054 method, that returns these clusters. It should return acollection of collections. Each internal collection contains the users in one cluster, in any order. When we saycollection we mean any of the given data structures. You're welcome to return them as a linked list of linked lists, a queue of arrays, or anything else. You will not be marked for this choice of data structure, pick whatever is convenient. The examples below will use an array of arrays.
Hint 1: with the definition above, a user who doesn't have any connections (isn't friends with anyone, and is no one's friend) is a cluster of 1, because technically, all of its connections are mutual (vacuous truth).
Hint 2: you may want to look at the breadth-first search algorithm. It won't exactly solve this problem, and you will see it's usually referred to as a method of finding the shortest path or searching for a specific item when connections are mutual. But its core idea of traversing the users and connections using a queue would be helpful.
Note on Marking: For this function, there are no marks for complexity analysis of the function or the details of your approach. Instead, we will run your code on large inputs, and you will get full marks if your code finishes in a few seconds. For that reason, try to optimise your code as much as you can, and avoid unnecessary logic in the code, to ensure it will run quickly.
Example
Let's say the connections look like this:
The clusters you should return are [[A, B, C], [G, H], [K]]. The order in which you insert the clusters, or the users in each cluster, does not matter. You can return them in any order.
Here's another example:
Let's say the users are: [A, B, C, D, E] and the connections are:
A: [B] B: [A] C: [E] D: [] E: []
The clusters are [[A, B], [D]].