Inft1004 Introduction to Programming
School of Electrical Engineering and Computing
Inft1004 Introduction to Programming – Assignment (v2, 1 April)
Due 11.59pm on Sunday 12 May; students are advised to start work immediately
Weighting 30%
Paired work Students are strongly encouraged to work in pairs on this assignment
Your assessment task
For this assignment you are to write a Python program in JES that turns an image into a sliding-block puzzle and allows the user to solve that puzzle.
In a sliding-block puzzle, a square image is divided into a 4x4 grid and one piece (typically the top left piece) is removed. The pieces are called blocks, and the player can slide any block into the empty space. Of course this also moves the empty space, and another piece can then be moved into it. The game is played by shuffling the blocks somewhat arbitrarily, then trying to get them back into their starting order.
For convenience, we can describe the four possible moves as up, down, left, and right, meaning that a block is slid up, down, left, or right, into the empty space. Here are some images that should help you to understand the process. They show a puzzle in its solved state, then what it looks like after moves left, up, right, and down in that order. Note that the empty space seems to move in the opposite direction to the sliding block, so the empty space appears to have moved right, down, left, and up; but with the physical puzzle, the user slides a block, not the space, so it is the movement of the block that we describe.
The assignment can be loosely broken into five tasks, although some of them will have subtasks:
1. Crop the image to make it square.
2. Draw lines on the image to form the 16 blocks.
3. Implement block slides up, down, left, and right into the empty space.
4. Keep track of where each block is.
5. Allow user input to control the block slides.
6. Shuffle the puzzle arbitrarily.
7. Check whether the puzzle is solved.
Each of these tasks is described in more detail on the following pages.
Inft1004 Introduction to Programming Assignment 2
Journal
As programming is a complex task, you are required to maintain and submit a journal, a separate word-processed document in which you
• record when and for how long you work on which aspects of the assignment, and which bits are done by which member of the pair;
• briefly list questions that arise, difficulties that you encounter, and how you overcome them;
• summarise lessons that you learn.
By the time you’ve finished the program your journal will probably be many pages long. The journal is intended to record your design thoughts, your programming thoughts, and the time you spend on the task, so you must keep it up to date at all times. A ‘journal’ that is thrown together the day before the assignment is due is not a journal at all.
When you hand in your files, your journal must be a pdf file.
Cover sheet – no longer required
The original specification required you to include a cover sheet with your submission. The university no longer requires cover sheets for online submissions, so this requirement has been removed.
Files and folders
When you hand in the assignment you will be handing in two files: your Python program and your pdf journal. There is a particular structure that you are required to follow.
Both files (and no other files) will be in a folder whose name is your names, without spaces, followed by the abbreviation Assgt2. If Abby Archer and Zeke Zammit are working together, their folder will be called AbbyArcherZekeZammitAssgt2.
Within that folder, your Python program will have your names followed by Assgt2.py (eg AbbyArcherZekeZammitAssgt2.py); and your journal will have your names followed by Journal.pdf, (eg AbbyArcherZekeZammitJournal.pdf). Remember that the journal is to be a pdf file.
Problem-solving
Several aspects of this assignment involve problem-solving. This is not unusual: it is difficult to specify programming tasks that do not require problem-solving. While you might be tempted to just write some code and hope that it will eventually do what you want it to do, in the end it will be far more effective to first work out exactly what you want the code to do, and only then start writing the code.
Based on past experience, students who believe that they are having trouble with their program code are generally having trouble with their program design, their algorithm. If your program isn’t doing what you want it to do, this is probably because you haven’t solved the problem and clearly worked out how the program should do what you want it to do. You are most unlikely to get the program working correctly if you haven’t correctly solved the problems and designed the solutions.
When you need to problem-solve, the key is not to search the web for inspiration, it is not to randomly try things in the hope that one of them will work: it is to write down what you have, to write down what you want, and to think about how to get from the first to the second. It often helps to draw diagrams. It definitely helps to discuss the problem, and possible solutions, with your partner. If you actually solve the problem for yourself, rather than finding something somewhere that you might be able to bend into a solution, it will be a huge step in your development as a programmer.
Some general suggestions
Inft1004 Introduction to Programming Assignment 3
It’s really important to tackle one task, one function, at a time. At first the whole assignment will seem overwhelming. But by doing one function at a time you will find it much easier to come to grips with – although of course some functions are tougher than others. So long as you start early enough, you should complete most of the functions.
Assignment tasks
puzzle(picfile) – 5 marks
When we mark your assignment, the first thing we will do is run a function called puzzle() with an appropriate argument. This function will call functions for the other tasks in turn. Be sure that you name this function exactly the way it is named here; if the name is even slightly different, JES will not find the function when we try to run it. Also be sure that you define it as having exactly one parameter.
The parameter is the file in which the original image is stored. For example, if we want to make a puzzle of the beach picture, the argument will be the file in which that picture is stored. In the command area you might have entered beachFile = pickAFile() and then selected the file beach.jpg; you would then be able to use beachFile as the argument.
Of course it would be possible to program all of the assignment tasks within the single puzzle() function, but you know by now that it makes more sense to write a separate function for each task, and then call those functions appropriately from puzzle(). Before calling any of your own functions, this function should make a picture from the file.
Task 1: crop the image to make it square – 10 marks
You now have a picture that might be square, but probably isn’t. Your job here is to produce a square picture from what you have been given. The side of the square should be whichever is smaller, the width or height of the original picture. If the original is wider than it is high, it should lose equal amounts from its left side and its right side, so that the new image represents its middle. Likewise, if it is higher than it is wide, it should lose equal amounts from the top and bottom.
Here are the square versions of a couple of familiar pictures.
Task 2: draw the grid on the image – 5 marks
It’s possible to represent a sliding-block puzzle without gridlines, but there are clear lines on the physical version of the puzzle, and lines help us to see where the blocks are in parts of the picture that are in the right locations. So now draw lines on the image, just one pixel wide, to divide it into 16 blocks.
Inft1004 Introduction to Programming Assignment 4
Do you remember the problem we had with integer division in the week 5 lecture? Could that problem arise here when you’re drawing the lines? If so, what can you do about it?
Task 3: implement block slides into the empty space – 15 marks
Now you need to move blocks up, down, left, or right into the empty space. There isn’t an empty space yet, but that’s not a problem. By default, the empty space is in the top left of the puzzle, so you can put one there.
Moving a block is then as simple as copying the pixels from that block into the empty space – and remembering to empty the place that the block moved from.
You might need to consider what to do if the move doesn’t make sense. For example, if the empty space is at the top left of the puzzle, what should your program do with a request to move a block down into that space?
Did you deal with the rounding error problem while working on task 2? If not, you might start to see strange lines appear at the edges of blocks, and the grid lines might no longer line up properly:
What’s happening here is that the blocks are not all exactly the same size. When you copy the pixels from one block into a block that’s a slightly different size, it’s not quite going to work. Clearly, you need every block to be exactly the same size.
You should eventually work out that it’s not enough for the picture to be square; it must also be of a suitable size to accommodate four blocks and five single-pixel lines in each dimension. This is one place where you need to apply your problem-solving skills to work out how to implement that.
Inft1004 Introduction to Programming Assignment 5
Don’t think that you need to scale the picture in any way; just go back to task 1 and take slightly less of the original picture. But don’t guess this step: work it out!
At this stage you will probably be testing your program by making a series of calls to the function(s) that move the blocks. This is tedious, but tasks 4 and 5 will make it easier.
Task 4: keep track of where each block is – 10 marks
The moves in a sliding-block puzzle are just up, down, left, and right. But if the user wants to move a block in one of those directions, the program has to know where the empty block currently is. In fact, it’s a good idea for the program to know where every block is (see task 7). This could be done in various ways: here’s a relatively simple one.
Create a list of the numbers from 0 to 15, representing the blocks in their original order. The initial list will be [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; 0 represents the empty space at the top left, 3 represents the top right block, and 12 represents the bottom left block (see the numbered picture on p7). Every time you make a move, you will need to change the order of numbers in the list to reflect the blocks’ new positions in the puzzle.
For example, an initial move left would change the list to [1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], indicating that the empty space (0) is now in position 1 and block 1 (1) is now in position 0. Following this, a move up would give the list [1, 5, 2, 3, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], as block 5 moves into the spot where the empty space was, and the empty space moves to where block 5 was.
We might not have covered this in lectures, but lis.index(value) returns the index of value in lis. For example, if order is the list [1, 5, 2, 3, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], order.index(0) will be 5. So, given a list like this, you can find where the empty space is; and, given a move such as up or right, you can work out which block needs to move, and swap the positions of the two.
You’ll probably need to read those paragraphs several times over before you fully understand what they’re saying. When you do understand it, if you decide to use this method to keep track of which blocks are where, you’ll still need to do some problem solving.
For example, how do you swap two elements in a list, given their indexes? You might be able to find somebody else’s solution to this online, but you might struggle to understand it. It would be far better to work out your own approach, using pen and paper, and to implement that. Remember, you’ve known how to swap two variables since about week 2. Perhaps you can use that knowledge.
When you work that out, you’ll need to keep the list up to date. Every time you make a move, the list will need to change to reflect that move. If you have a function that moves a block in the picture, the function will also have to change the list.
This leads to a new problem. A function can only return one thing. If you have a function that moves a block, it can’t return both the new list and the new picture. Well, there are ways of doing this, but we haven’t covered them. So even though we’ve advised you not to rely on the side effects of functions, you may, if you wish, use side effects to directly change the picture, the list, or both. But if you write any functions that use side effects to change their arguments, be sure to say so in the comments, so that we can see that you’re aware that you’re doing this.
Task 5: allow user input to control the block slides – 10 marks
If you haven’t already done this as part of tasks 3 and 4, it’s time to allow the user to control the puzzle. Compared with task 4, this should be simple.
One possible approach would be to ask the user to input a single letter, u / d / l / r, and to use that input to make the move. How will you let users know what these letters mean?
Inft1004 Introduction to Programming Assignment 6
Of course this should be in a loop, so that the user can make more than one move before the program ends. What kind of loop? How, if at all, should it end? Should the user be given an additional input option, such as q for quit?
Task 6: shuffle the puzzle arbitrarily – 15 marks
To get the puzzle into a jumbled state, you might be tempted just to shift blocks arbitrarily into new locations. Unfortunately, that won’t work: there are many arrangements of the blocks that cannot be solved by sliding individual blocks. Here is just one of them:
So what you need to do now is to jumble the blocks in such a way that they can definitely be solved by a sequence of sliding moves. If you’re really good at mathematics, you might be able to work that out in some other way, but probably the easiest way is simply to apply a random sequence of moves to the puzzle. Depending on how you decided to deal with moves that don’t make sense, this might be relatively easy.
A potential problem is that because the empty square is initially in the top left corner, a random sequence of moves is likely to affect mainly the top left part of the puzzle, and might never reach into the lower right. There are various ways of adjusting for this; see what you can come up with.
Even though it might make some sense, don’t have your program shuffle the puzzle immediately; a user might want to explore the individual direction controls first. So add an s option to the possible user inputs, and shuffle the puzzle when the user enters s.
Task 7: check whether the puzzle is solved – 5 marks
Because you’re using a list to keep track of the block positions, it's very easy to check whether the puzzle is solved: just check whether the list is the same as the starting list.
Once the puzzle is solved, you should congratulate the user and end the input loop.
When you’re actually solving the problem yourself, as a user, you might find that with some pictures it’s not obvious which blocks belong where. Even though you’re quite familiar with the beach picture, can you look at this shuffled version and know where each block belongs? If not, it’s going to be harder to solve.
Inft1004 Introduction to Programming Assignment 7
For this reason, we’ve provided the image numbers.jpg, which should be a great deal easier to solve. Indeed, while some sliding-block puzzles do have an image on them, many have either the numbers from 1 to 15 or the letters from A to O, to make them easier to work with.
Assessment criteria
Your work will be assessed out of 100 marks. In addition to the 75 marks listed above with the task descriptions, there will be marks for
• your journal, as specified above, clearly showing the design and development process (12)
• well-named variables and appropriate and useful comments in the code (13)
Once these marks have been allocated, marks will be deducted for the following:
• failure to follow instructions/requirements, eg with file names
• syntax errors or runtime errors in your program
Inft1004 Introduction to Programming Assignment 8
• failure to fully and clearly reference any material from external sources, such as code written by other people or code with which other people have assisted you
• late submission – see below
If you get code from other people or sources, or if other people help you with your own code, you must add comments making this clear, and explain it in your journal. If the marker uncovers evidence that you have cheated in any way, for example, by sharing your code with others in the class, or by getting help from anyone other than your partner and not referencing it, the matter will be reported to the Student Academic Conduct Officer as a potential case of academic misconduct. (See Academic integrity below.)
Handing in your work
You are to hand in the assignment electronically using Blackboard’s Assignment facility. Because you need to hand in a whole folder and its contents, you are required to zip the files together. Remember, you are to hand in a folder containing exactly two files: your Python program and your pdf journal.
When you zip your folder and its contents, in way that preserves their directory structure, be sure that you produce a .zip file, not some other format such as a .rar file. (If you’re at all unsure about this, tell your operating system to display file extensions as well as file names.) There are many zipping software packages, some commercially available, some free, and some provided with operating systems. Well before you submit your assignment, be sure that you have access to appropriate software and know how to use it. Once you have zipped your files together, be sure to unzip them to a new location to check that they unzip correctly. Also be sure that the zip file has the same name as the folder, your names without spaces followed by Assgt2; for example, AbbyArcherZekeZammitAssgt2.zip.
When you are ready to submit your zipped file, log in to Blackboard, go to the site for this course, and follow these steps . . .
• Select the Assessment folder.
• Click the Assignment 2 link, which will take you to the appropriate upload page.
• Under Assignment submission, click Browse my computer (next to Attach files), and navigate to your zip file. Alternatively, just drag the file from where it’s located into the dashed rectangle. In the comments field put your name.
• When you’ve done that, click the Submit button.
• If you don’t see a message saying the assignment is complete, go back and check that you’ve done all these steps.
• If you want to submit an updated version of the assignment, go back to the Assignment link and click Start new submission on the assignment’s Review submission history page. Make sure you’re aware of the deadline: the final marking will be applied only to the most recent submission, and if it’s submitted late it will be marked as late.
You might be required to demonstrate your program, and to explain aspects of your code, in a subsequent lab class.
Paired work
When two students work as a pair, all folders and files (as described above) should clearly indicate the names of both students in the pair. Only one copy of the work needs to be handed in, only one journal needs to be handed in (a combined journal for the pair), and both students in the pair will normally get the same mark for the assignment, regardless of who did how much of the work, unless it is clear that this would be a serious injustice.
Inft1004 Introduction to Programming Assignment 9
Deadline and consequences for late submission
The assignment is due by 11.59pm on Sunday 12 May, the end of week 9 of classes. Work will be penalised 10% for every day or part day by which it is late.
Students are encouraged to aim to complete the assignment well before the deadline, as programming assignments are well known for taking far longer than the students expect.
Inft1004 Introduction to Programming Assignment 10
Academic integrity – getting assistance or code
This assignment is your chance to gain an understanding of fundamental concepts of program structure and coding syntax on which later learning will be based. It is important that you master these concepts yourself.
Since you are mastering fundamental skills, you are permitted to work from the textbook and course examples, but you must acknowledge assistance from other textbooks or classmates. In particular, you should try not to use code or algorithms from external sources, and not to obtain help from people other than your instructors, as this can prevent you from mastering these concepts. However, if you do get code or assistance from these external sources, you must ‘attribute’ it: both in your journal, and in comments in your code, you must clearly explain where or who the code or assistance came from, and how much help or code was provided.
Here is a detailed guide to who you can get help from, and where you can get code from. Please pay careful attention to it.
Assistance: who might you want help from?
Status
Yourself, your partner
Highly encouraged
Your lecturer, your tutor
Encouraged
Classmates, other tutors
Attribution required
Online forums, relatives, friends, other students not in this course
Not acceptable
Any other sources
Ask the lecturer
Resources: where might you want to get code from?
Status
Course textbook, course notes and examples, your partner
Encouraged
Other textbooks
Attribution required
Online programs, hired coders, relatives, friends, other students
Not acceptable
Any other sources
Ask the lecturer
Obtaining code or assistance for which attribution is required without attributing it, or obtaining any code or assistance from sources marked ‘Not acceptable’, is a breach of academic integrity, and can be referred to the Student Academic Conduct Officer for investigation. Furthermore, providing such code or assistance is also a breach of academic integrity, and can be treated as such.
If you do receive code or assistance for any of the assignment, there is a specific way in which you must provide the attribution in your program. We call this a reference comment.
The reference should say whether it is for externally sourced code, an externally sourced algorithm, or personal assistance. It should be given a unique identifier so that its end can be clearly marked.
The beginning and end of each reference should be marked in a particular way that stands out from the code. In the examples below we use lines of hash symbols to do this.
Each reference should include:
• its purpose: why was external code or assistance sought?
• the date the code or assistance was used;
• the source of the code or assistance;
• the author of the code, if known, or the person providing assistance;
• the url, if applicable;
Inft1004 Introduction to Programming Assignment 11
• any adaptation that was required to incorporate external code;
• a brief description of assistance that was provided, if applicable.
Here are some examples.
#############################################
# Reference A3: externally sourced algorithm
# Purpose: sort a list of sublists by the second element in each sublist, descending
# Date: 25 Sep 2018
# Source: Python documentation
# Author: Andrew Dalke and Raymond Hettinger
# url: https://docs.python.org/3/howto/sorting.html
# Adaptation required: changed variable names; saw need to assign result to original list name
#############################################
freqList = sorted(freqList, key = lambda wordFreq: wordFreq[1], reverse = True)
#############################################
# End reference A3
#############################################
#############################################
# Reference C5: externally sourced code
# Purpose: make a collage with various colour transformations because I didn’t understand the one in the book
# Date: 12 Oct 2018
# Source: stackoverflow
# Author: Gauthier Boaglio
# url: https:#stackoverflow.com/questions/15693938/how-do-i-change-image-colors-with-jes-programing
# Adaptation required: changed variable names
#############################################
This is where the copied code goes
#############################################
# End reference C5
#############################################
#############################################
# Reference P7: personal assistance
# Purpose: deal with 'inappropriate argument' error
# Date: 25 Oct 2018
# Source: fellow student Susan Piper
# Assistance: explained that these errors arise if we try to access pixels beyond the edge of the picture
#############################################
This is where the newly modified code goes
#############################################
# End reference P7
#############################################