In what concerns the "exercises during classes" component of the evaluation, the exercises that you can submit for this class are:
Deadline for submission: December 21st (submit to IP's Mooshak)
You are encouraged to talk to the professors and your colleagues if you encounter difficulties.
However, any more direct help that you receive should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each practical class is worth 10% of your final component for exercices during class. Since there will be 11 classes with submissions, you can achieve maximum grade even without doing all classes.
For a problem to count you must pass all tests (that is, to have an accepted). Even if you solve all problems, the maximum on one class is 100%.
To obtain 100% it will always be enough to solve the main exercises.
With the exercises in this class you will develop the following skills:
Until now you have mostly made small programming assignments that would fit on a single function and with a very reduced number of lines of code.
This week we will put our hands on slightly larger problems, that need a more structured approach and a division of the problem into simplex blocks.
This exercises are harder then those of the previous weeks, but you will learn more while doing them.
Take your time to think about the problems (there are only 2 main + 1 extra + 1 challenge) and revisit them after your first accepted solution to see how you could improve.
Make sure you have a look at: T17: Structured Programming
This week's theme for the exercises is Naruto.
1) Elementary Cellular Automaton [main]
For this exercise you will be solving the problem [IP093] The Mysteries of Cellular Automata.
Read the statement, code and try to submit an Accepted solution. Don't forget to test first on your computer!
By the end of this part of the class you will be submitting the problem at hand, but for now let's approach it differently and on a more structured way (resist to urge to just go directly to Mooshak and stick with the strategy given here).
Seems simple enough, but it of upmost importance! Start by reading the problem carefully: [IP093] The Mysteries of Cellular Automata (you cannot solve a problem you do not understand it completely first)
Try to really understand everything and what is the concept of a cellular automaton. Here are some useful links to complement the problem statement:
You can of course divide the problem as you want (and/or you can try again afterwards with your own approach or variation), but for now we propose you follow a specific organization of the code into different functions.
You can use as a start the following "skeleton" code with all functions already with their headers made (but still missing the code: all of them are with the pass instruction so that the code compiles):
The code is structured in the following way:
We know that for now this is a bit "too much", but it serves to give you a brief overview of what you will be doing next.
Let's start by implementing the read() function. You should start by putting the input examples on files (e.g. ip093_input01.txt and ip093_input02.txt) so that you can easily call them afterwards to test your code.
To get you started we will give you the code for this one:
def read(): global r, k, line r, k = map(int, input().split()) line = input()
If you put this code, not only will the input be read to variables r, k and line, but they will also be available outside of the function (you could as well return the 3 valies (e.g. as a tuple) but here we want to also show how you could have a global variable that can does not need to be passed around all the functions - and in this case this is the global data of the problem).
Don't forget to test that you are reading correctly. To do that, put the following code outside of all functions (in the bottom), right after you call read():
print(f'{r=}, {k=}, {line=}')
If you call you program and feed it with the input (python ip095_skeleton.py < ip093_input01.txt) you should be able to see the following output, signaling it it is correct:
r=128, k=5, line='#############'
Don't forget to also that with the second example input to see if everything seems ok
Let's start implementing the small functions, beginning with rule_to_8bits.
This should convert the integer representing a rule to its individual bits (that we will use afterwards). When called with the following tester code:
print(f'{rule_to_8bits(30)=}') print(f'{rule_to_8bits(128)=}') print(f'{rule_to_8bits(42)=}')
It should produce the following output (notice they come reversed in relation to the table in the problem statement - this is not a problem, as we will see):
rule_to_8bits(30)=[0, 1, 1, 1, 1, 0, 0, 0] rule_to_8bits(128)=[0, 0, 0, 0, 0, 0, 0, 1] rule_to_8bits(42)=[0, 1, 0, 1, 0, 1, 0, 0]
Now let's proceed with str_to_number.
This function should convert a triplet of chars '.' and '#' and return a number representing the positoin of the triplet if interpreted as a binary string (with zero being '.' and one being '#'). Test the code with:
print(f'{str_to_number("...")=}') print(f'{str_to_number("..#")=}') print(f'{str_to_number(".#.")=}') print(f'{str_to_number(".##")=}') print(f'{str_to_number("#..")=}') print(f'{str_to_number("#.#")=}') print(f'{str_to_number("##.")=}') print(f'{str_to_number("###")=}')
Which should produce (notice how they correspond to the position in the table of the problem statement... and to the positions of the bits we produced with rule_to_8bits):
str_to_number("...")=0
str_to_number("..#")=1
str_to_number(".#.")=2
str_to_number(".##")=3
str_to_number("#..")=4
str_to_number("#.#")=5
str_to_number("##.")=6
str_to_number("###")=7
Now calculate should be "a piece of cake" given the past two functions, right?
Here is example tester code:
rules = rule_to_8bits(30) print(f'{calculate(rules, "...")=}') print(f'{calculate(rules, "..#")=}') print(f'{calculate(rules, ".#.")=}') print(f'{calculate(rules, ".##")=}') print(f'{calculate(rules, "#..")=}') print(f'{calculate(rules, "#.#")=}') print(f'{calculate(rules, "##.")=}') print(f'{calculate(rules, "###")=}')
And the expected output:
calculate(rules, "...")='.' calculate(rules, "..#")='#' calculate(rules, ".#.")='#' calculate(rules, ".##")='#' calculate(rules, "#..")='#' calculate(rules, "#.#")='.' calculate(rules, "##.")='.' calculate(rules, "###")='.'
To help you here is a possible implementation assuming you did the previous functions as expected:
def calculate(rules, triplet): if rules[str_to_number(triplet)] == 1: return "#" return '.'
Now onto generating a new line with function create. You just need to traverse the current line and generate a new line for each triplet. How to deal with the special case of the first and last character of the line not having a the entire triplet? Here are two options:
Can you implement and test this function by yourself?
After all of your previous work with short functions only one piece of the puzzle is now missing...
Implement the simulate that can simply iterate k times and keep calling create to produce the new line given the previous line.
Don't forget to test!
After testing everything, now is the time to submit and get your deserved Accepted.
If you get a Wrong Answer or another error, you can use the details of the submission to fetch a case where your code fails and use it to debug your code.
2) A 2D Cellular Automaton [main]
For this exercise you will be solving the problem [IP094] Game of Life.
Read the statement, code and try to submit an Accepted solution. Don't forget to test first on your computer!
Can you try to organize the code yourself? Try first to think on how to do it and use modular programming to divide the task into small simple blocks that you can incrementally develop and test.
If you are stuck or want to see a possible approach, the hints sections provides a possible code organization.
- As before, divide into reading and solving
- We suggest you convert to a list of lists while reading (and you can use that format also for the output)
- For solving, simulate all generations by calling a simpler function that produces just one generation
- To produce a new generation iterate over all the cells and use a helper function to count the number of neighbor cells to decide the state of any new cell
- Use a helper function to print the list of lists as a "normal" output of matrix of chars
3) The Minesweeper Game
For this exercise you will be solving the problem [IP095] Minesweeper.
Read the statement, code and try to submit an Accepted solution. Don't forget to test first on your computer!
You know the game, right? 😎 Here is an online versiona
Can you think about the problem by yourself and think on how to divide the code?
For the "recursive propagation" part have a look at the recursion notebook (there is a section explaining flood fill)
IMPORTANT NOTE: you might hit the maximum recursion depth (which is only 1000 by default, on Python). You can increment it on your code by adding the following:
import sys # set maximum recursion depth to 100 000 # (can you see why this is enough for this problem?) sys.setrecursionlimit(100000)
- On each cell, like in game of life, count the bomb in neighbor cells and act accordingly:
4) Advent of Code
If you want more exercises, have a look at Advent of Code 2024 for more fun every day until Christmas! 🎄 [more about the Advent of Code on Wikipedia]
For the last exercise, the proposal is to do one of the (eaiser) problems of SWERC'2024, an international programming competition that took place this past weekend
Because it is a challenge, we will not give hints beforehand, but if you get stuck contact @PedroRibeiro at Discord. This is an exercise on efficiency, as a naive solution will get a Time Limit Exceeded (Mooshak will give 2 seconds to your code and it needs to be able to solve the 200 thousand case in that amount of time - for instance the following naive solution will fail: cycle through all towers and for each of them do another cycle over all towers to search which one is taller and closer)
For this exercise you will be solving the problem [IP096] The Towers of the Temple
Read the statement, code and try to submit an Accepted solution to the following problem. Don't forget to test first on your computer!
Happy coding! 😊