IFB104 Assignment 1, Part A: Tessellation Solution

Overview
This is the first part of a two-part assignment. This part is worth 21% of your final grade for IFB104. Part B will be worth a further 4%. Part B is intended as a last-minute extension to the assignment, thereby testing the maintainability of your code, and the instructions for completing it will not be released until Week 7. Whether or not you complete Part B you will submit only one file, and receive only one assessment, for the whole 25% assignment.
Motivation
One of the most basic functions of any IT system is to process a given data set to produce some form of human-readable output. This assignment requires you to produce a visual image by following instructions stored in a list. It tests your abilities to:
• Process lists of data values;
• Produce maintainable, reusable code;
• Design a solution to a repetitive computational problem; and
• Display information in a visual form.
In particular, you will need to think carefully about how to design reusable code segments, via well-planned function definitions and the use of repetition, to make the resulting program concise and easy to understand and maintain.
Goal
Completely filling a plane with tiles of different shapes is a computational challenge that goes back to ancient times. Formally this process is called “tessellation”. In this assignment you will solve this challenge by drawing “tiles” (rectangular images) in a grid using automatically-generated solutions. To do so you must follow a set of instructions, provided as a Python list, to place differently-sized tiles in various locations in the grid. When this is done properly the grid will be entirely filled with non-overlapping tiles. Most importantly, the pattern to be followed is generated randomly, so your solution must be sufficiently general that it can work correctly for any possible pattern of tiles that fills the grid.
Resources provided
A template Python 3 program, tessellation.py, is provided with these instructions. When run it creates a drawing canvas and displays a simple grid image on which you will draw tiles of specific shapes in specific locations. You have a free choice in the design of the individual tiles, but they must all be related by a common theme. The default image drawn by running the provided Python template appears as shown overleaf. It consists of a numbered grid representing the plane to be tiled, with space on either side for a legend in which you will describe the theme and tokens you have designed.

For convenience, the “home” coordinate (0, 0) is marked by a dot. The canvas contains a
10 ´ 7 grid representing the plane to be tiled. Each of the grid’s squares measures 100 ´ 100 pixels. The spaces to the left and right of the grid are where the legend explaining the meaning of each of your tiles will be drawn.
Your task is to extend this template file so that it can draw tiles of various shapes that entirely fill the grid by following a provided pattern. To do so you must design four entirely distinct tiles, each of which can be drawn in any place on the grid (and in the legend). Your code will consist of a function called tessellate and any auxiliary functions you define to support it. This function takes a single argument, which is a list of instructions specifying where to draw the tiles. This list of instructions is created by a provided function called random_pattern which randomly generates the sequence of instructions, so your code must work correctly for any possible pattern that could be returned!
Designing the tiles
To complete this assignment you must design four entirely distinct tiles which can be used to fill the grid. There must be one tile in each of four required shapes: 2 ´ 2, 1 ´ 2, 2 ´ 1 and
1 ´ 1 grid squares. Each tile must fit exactly into the required number of 100 ´ 100 pixel squares. Each tile must contain a single image, different from the other tiles, and which fills its whole area. They must be drawn using Turtle graphics primitives only, must be easily recognisable, must be of a reasonable degree of complexity, involving multiple Turtle shapes, and must all be part of some common theme. You have a free choice of theme and are encouraged to be imaginative!
• Cartoon or comic characters
• TV or movie characters
• Sporting teams
• Businesses (banks, restaurants, IT companies, etc)
• Computer or board games (e.g., Monopoly tokens)
• Internet or cloud service providers
• Geographical sites (cities, countries or tourist attractions)
• Vehicles (cars, boats, planes, etc)
• Household objects
• Or anything else suitable for creating four distinct and easily-identifiable tiles
Data format
The random_pattern function used to assess your solution returns a list of “instructions” representing the places to draw each tile and the kind of tile to draw. Each of the instructions is itself expressed as a list containing two to five character strings, depending on the shape of tile. Their general form is as follows:
[squares, mystery_value]
• a “big” tile will occupy four grid squares;
• a “small” tile will occupy one square;
• a “wide” tile will occupy two squares in the same row; and
• a “tall” tile will occupy two squares in the same column.
The purpose of the “mystery value”, which is always either ‘O’ or ‘X’, will be revealed in Part B of the assignment.
For instance, instruction
['C5', 'O']
tells us to draw a “small” tile, occupying a single square, at grid location C5. Instruction
['H5', 'I5', 'X']
says to draw a “wide” tile, occupying two squares in the same row, spanning grid locations H5 and I5. Similarly, instruction
['E1', 'E2', 'O']
tells us to draw a “tall” tile, occupying squares E1 and E2 in the same column. Finally, instruction
['E5', 'F5', 'E6', 'F6', 'X']
specifies drawing a “big” tile, occupying four squares, E5, F5, E6 and F6, spanning two rows and two columns. The random_pattern function generates a list of such instructions which, when followed completely, fills every square in the grid with non-overlapping tiles.
In addition to the random_pattern function, the template file also contains a number of “fixed” data sets. These are provided to help you develop your code, so that you can work with a known pattern while debugging your code. However, the “fixed” patterns will not be used for assessing your solution. Your tessellate function must work correctly for any pattern randomly generated by function random_pattern.
Illustrative example
To illustrate the requirements we developed a solution which draws four tiles fitting the theme “Apollo 11”, in celebration of the 50th anniversary of the first moon landing. (Don’t copy our example! Develop your own idea!) We wrote Turtle graphics code that could draw the following four tiles, each representing an aspect of the historic mission.

Our small tile shows an astronaut on the moon and is exactly 100 pixels wide and high, so it will fit perfectly into one of the grid squares. Our wide tile shows the Command and Service Modules with rockets firing to escape the Moon’s gravity and return to Earth. It is exactly 200 pixels wide and 100 pixels high. Our tall tile is 100 pixels wide and 200 pixels high and shows the Saturn V launch vehicle. Finally, our big tile shows the Lunar (Excursion) Module and is 200 pixels wide and high. All of these images are drawn using basic Turtle graphics drawing steps. Your images do not need to be as complicated as these examples, but must still be recognisable and non-trivial. (And in case you’re wondering, yes, the Lunar Module was very difficult to draw using Turtle!)
From this basis, our implementation of the tessellate function can follow any list generated by function random_pattern, drawing one tile for each list element. For instance, consider the following list returned by function random_pattern:
[['B4', 'O'],
['D1', 'E1', 'X'],
['H3', 'O'],
['I6', 'J6', 'I7', 'J7', 'O'],
['C5', 'D5', 'C6', 'D6', 'O'],
['J4', 'O'],
['B5', 'O'],
['E4', 'F4', 'E5', 'F5', 'O'],
['J1', 'O'],
['F3', 'O'],
['A2', 'O'],
['G3', 'G4', 'O'],
['E6', 'F6', 'E7', 'F7', 'O'],
['I2', 'J2', 'I3', 'J3', 'O'],
['A7', 'X'],
['A1', 'O'],
['B7', 'C7', 'O'],
['G2', 'O'],
['G1', 'O'],
['H1', 'H2', 'O'],
['A3', 'B3', 'O'],
['F2', 'O'],
['G5', 'O'],
['B1', 'C1', 'O'],
['A6', 'B6', 'O'],
['D4', 'O'],
['C4', 'O'],
['I1', 'O'],
['B2', 'O'],
['G7', 'H7', 'O'],
['G6', 'H6', 'O'],
['A4', 'A5', 'O'],
['C2', 'C3', 'O'],
['D7', 'O'],
['F1', 'X'],
['J5', 'X'],
['H4', 'I4', 'H5', 'I5', 'O'],
['D2', 'E2', 'D3', 'E3', 'O']]
This requires us to draw a small tile in square B4, so our tessellate function draws an astronaut in this square. After this we must draw a wide tile in squares D1 and E1, so our function draws the Command and Service Modules in those squares. This is followed by another small tile in square H3. The fourth tile specified is a big one covering tiles I6, J6, I7 and J7, so our function draws the Lunar Module covering those squares. This process continues for all the “instructions” in the list. The resulting image, showing all the tiles drawn, is as follows:

Notice that each tile is of the appropriate shape and fits perfectly into the correct squares according to the instructions in the pattern provided.
Each time we call function random_pattern it produces a different list of drawing instructions. As another example, consider the following list returned by the function.
[['F6', 'F7', 'X'], ['E1', 'O'],
['G1', 'H1', 'G2', 'H2', 'O'], ['A1', 'O'],
['I1', 'J1', 'I2', 'J2', 'O'], ['J3', 'O'], ['H7', 'O'],
['B5', 'O'], ['E5', 'O'], ['I7', 'J7', 'O'],
['A6', 'A7', 'O'], ['F1', 'O'], ['A4', 'O'],
['B6', 'B7', 'X'], ['H5', 'O'],
['C6', 'D6', 'C7', 'D7', 'O'], ['F2', 'O'],
['I4', 'J4', 'O'], ['A3', 'O'], ['G3', 'H3', 'O'],
['C1', 'D1', 'C2', 'D2', 'X'], ['G6', 'O'],
['B1', 'B2', 'O'], ['G7', 'O'], ['I3', 'X'],
['I5', 'J5', 'I6', 'J6', 'X'], ['G4', 'O'], ['A5', 'O'],
['E4', 'O'], ['H4', 'O'], ['F5', 'G5', 'O'],
['C5', 'D5', 'O'], ['B3', 'B4', 'O'],
['E6', 'E7', 'O'], ['F4', 'O'], ['H6', 'O'], ['F3', 'O'],
['E2', 'E3', 'X'], ['A2', 'O'],
['C3', 'D3', 'C4', 'D4', 'O']]
In this case we begin with a tall tile in squares F6 and F7, so our tessellate function draws the Saturn V rocket in those squares. This is followed by a small tile in square E1, a big tile in squares G1, H1, G2 and H2, and so on. The resulting image appears below.

As well as drawing tiles in the grid according to a given pattern, the final requirement for this part of the assignment is to clearly explain your chosen theme and the four tiles you have designed by drawing a legend and putting a title on the drawing canvas. For instance, the image overleaf shows the complete drawing canvas for a pattern which begins as follows:
[['A1', 'A2', 'O'],
['C2', 'D2', 'C3', 'D3', 'O'],
['D1', 'X'],
['I4', 'J4', 'I5', 'J5', 'O'],
['F4', 'O'],
['J7', 'O'],
['B1', 'O'],
['J2', 'J3', 'O'],
['C4', 'O'],
['H1', 'H2', 'X'],
… etc

Notice that we have put a title on the top of the canvas explaining our theme. We have also created a legend describing each of the four tiles on either side of the grid. (The title and legend are always the same, regardless of the pattern drawn.) Also note that, to produce a nice looking image, you can stop the Python template writing “Put your legend here” on the canvas by changing one of the arguments to function create_drawing_canvas. You can also change the background colour and grid colour in the same way.
Requirements and marking guide
To complete this part of the assignment you are required to extend the provided tessellation.py Python file by completing function tessellate so that it can draw tiles as specified by the data sets generated by the random_pattern function. Your tessellate function must work correctly for all possible values returned by the random_pattern function.
Your submitted solution will consist of a single Python 3 file, and must satisfy the following criteria. Percentage marks available are as shown.
1. Drawing four entirely distinct tiles within a common theme (6%). Your program must be able to draw four clearly distinct tiles, each containing a single image different from the other tiles, in each of the four required shapes (2 ´ 2, 1 ´ 2, 2 ´ 1 and 1 ´ 1 squares), and each fitting exactly into the required number of 100 ´ 100 pixel squares. Each tile’s image must be clearly recognisable, must be of a reasonable degree of complexity, involving multiple Turtle shapes, and must entirely fill the tile’s area but without going outside the specified area. It must be easy to distinguish each tile from those adjacent to it through the use of distinct colours and/or borders.
2. Identifying the theme and tiles (3%). When executed your code must draw a “legend” on the left and right of the canvas which clearly describes your theme and indicates the meaning/identity of each of the four tiles. The legend must include a visual copy of each tile and text describing it. You must also put a title at the top of the Turtle drawing canvas describing your theme and tiles.
3. Placing tiles in the grid as per any given pattern (8%). Your code must be capable of drawing tiles to fill the grid, exactly as dictated by any valid data set provided to function tessellate. The tiles must be positioned precisely within the grid squares corresponding to the pattern described. The drawings of the tiles must preserve their integrity no matter where they are drawn, with no spurious additional or missing lines. Your solution for drawing the tiles must work correctly for any values returned by the random_pattern function.
4. Code quality and presentation (4%). Your program code, for both Parts A and B of the assignment, must be presented in a professional manner. See the coding guidelines in the IFB104 Code Presentation Guide (on Blackboard under Assessment) for suggestions on how to achieve this. In particular, given the obscure and repetitive nature of the code needed to draw complex images using Turtle graphics, each significant code segment must be clearly commented to say what it does. Similarly, the names of your functions, parameters and variables should be indicative of their purpose, not just “i”, “j”, etc. Also, you must use function definitions and loops to avoid unnecessary duplication of similar or identical code segments. To get full marks for this criterion you must provide a significant amount of code to assess.
Finally, you are not required to copy the example shown in this document. Instead you are strongly encouraged to be creative in the design of your solution. Surprise us!
Development hints
• Before creating code to draw the individual tiles give careful thought to how you can write the code so that they can be drawn in any square of the grid (and in the legend). In particular, you need to avoid “hardwiring” your drawing to fixed coordinates in the drawing canvas.
• One of the particular challenges in this assignment is “decoding” the grid coordinates, especially because the columns are labelled using letters instead of numbers. In your computer, however, each letter of the alphabet is actually represented by an “ordinal” number. In Python you can convert from numbers to letters using built-in function chr, and from letters to numbers using built-in function ord. For instance, chr(78) returns character 'N', whereas ord('A') returns integer 65 and ord('Z') returns 90. These functions will help you turn the letter-digit grid coordinates into numeric Turtle x-y coordinates expressed in pixels.
• If you are unable to complete the whole task, just submit whatever you can get working. You will receive partial marks for incomplete solutions.
• To help you debug your code we have provided some “fixed” patterns. Feel free to use these when developing your program, and add additional ones if you like, but keep in mind that these data sets will not be used for assessing your solution. Your tessellate function must work for any list that can be returned by function random_pattern.
• Part B of this assignment will require you to change your solution slightly in a short space of time. You are therefore encouraged to keep code maintainability in mind while developing your solution to Part A. Make sure your code is neat and wellcommented so that you will find it easy to modify when the instructions for Part B are released.
Portability
Artistic merit – The Hall of Fame!
Deliverable
You must develop your solution by completing and submitting the provided Python 3 file tessellation.py as follows.
1. Complete the “statement” at the beginning of the Python file to confirm that this is your own individual work by inserting your name and student number in the places indicated. We will assume that submissions without a completed statement are not your own work!
3. Submit a single Python file containing your solution for marking. Do not submit multiple files. Only a single file will be accepted, so you cannot accompany your solution with other files or pre-defined images. Do not submit any other files! Submit only a single Python 3 file!
Apart from working correctly your program code must be well-presented and easy to understand, thanks to (sparse) commenting that explains the purpose of significant code segments and helpful choices of variable, parameter and function names. Professional presentation of your code will be taken into account when marking this assignment.
If you are unable to solve the whole problem, submit whatever parts you can get working. You will receive partial marks for incomplete solutions.
How to submit your solution

Appendix: Some standard Turtle graphics colours


Source: www.discoveryplayground.com/computer-programming-for-kids/rgb-colors/