首页 >
> 详细

CISC 106 Spring 2020 Project 2

May 10, 2020

1 Background

For this project, you’ll be implementing a solution to the packing problem as it relates to tetrominoes.

Your goal will be to fill a board represented as a N × M matrix of characters by packing a

random sequence of tetrominoes as tightly1 as possible on the board until it is full. Empty

squares on the board are represented as space characters, and filled squares are represented as

one of I, J, L, O, S, T, or Z; each letter corresponding to a single square of one of the seven

tetromino shapes.

NB: Please make sure to follow the links to and read all of the footnotes in this writeup, as

they contain useful information!

2 Objectives

After completing this project you will have gained the following experience with the MATLAB

programming language and environment:

• Creating functions which return one value as well functions which return multiple values.

• Working with 2-dimensional matrices in MATLAB:

– Using loops to iterate over elements

– Using filtering and logical indexing rather than loops when applicable

– Creating and manipulating slices.

• Using MATLAB’s robust plotting API:

– Creating and configuring figures and axes

– Drawing a scene composed of simple geometric shapes.

• Using MATLAB’s extensive online documentation.

3 Outline of Steps

The following section describes the steps you must take in order to complete this project.

1That is, with the fewest gaps between them

1

Project Set Up

In MATLAB creating a project is as simple as making a new folder and then saving your code

there as a collection of .m files. Create yourself a folder for your project, and then download the

following files from Canvas and put them there:

• run game.m

• draw test board.m

• unittests.m

• assertEqual.m

Now if you open MATLAB and navigate to that folder you can open those files, look at the

code, and run the function defined in them at the REPL.2

A MATLAB project is composed of files, each with at least one function in them. You can call

the first function defined in a file by using the name of the file3

, and as such the convention is to

name that first function the same as the name of the file. For this project, you will be following

this convention.

Open the unittests.m that you downloaded from Canvas. Note that there is one test already

written for seven of the eight functions you’ll be writing for this project.4 You’ll be following the

Beginner Design Recipe when writing your functions for this project, and here is where you’ll put

all of your tests. You should add two or three more tests for each of your functions as you’re

implementing them to test different possibilities. You can run your tests any time at the REPL

by entering the command unittests.

From now on, when you see instructions saying something along the lines of ”write a function

do stuff”, you should understand that to mean first create a script and save it as do stuff5

and then implement the function in that file, also calling the function do stuff.

Part 1

Write a function draw game board which consumes a board which is a 2D matrix of characters

as described in Section 1, and a figure6

. This function will then clear whatever happens to be on

the passed in figure, and construct a new axes with that figure as parent. You’ll then use the

rectangle function to create a graphical depiction of the passed in board on the created axes

object, and return the axes object. Keep in mind that you’ll be drawing one rectangle for every

character on the board - this means you’ll probably want to consider using nested for loops!

You can run the draw test board function you downloaded in the Project Setup section to

test your draw game board. Open draw test board.m to see the example board matrix, as well as

how to create a figure and how your function will be called. See Figure 1 for how your drawn

board should look.7 You should check the documentation for axes to see how to make your

board match Figure 1. You can also take a look at this improperly configured axes document to

see some common axes misconfigurations.

Part 2

Write a function make board which consumes a whole number of rows and a whole number of

columns. This function will return a rows × columns empty board - that is, a matrix of all space

2Of course, if you try to run them now, you’ll get an error message because they call code that you will write.

3Other functions defined in the same file can only be called within that file, and are called as they’re named in the file

4As we’ll see draw game board needs to be eyeballed for correctness, and as such you won’t write unit tests for it.

5you can add the .m extension or leave it off - MATLAB will add it for you automatically

6See MATLAB’s documentation for figure

7Assuming you’re using the standard tetromino colors. Feel free to get creative and pick your own color palette! The

positions and rotations and ”squareness” of the shapes should match Figure 1 regardless of your color choices.

2

Figure 1: A correctly drawn test board, using the standard colors for the seven tetrominoes. See

the discussion about setting colors in MATLAB’s documentation for rectangle.

characters. You should be able to implement the body of this function in just a single line of code!

Look in MATLAB’s documentation on Creating and Combining Arrays - from Documentation

Home, MATLAB→Language Fundamentals→Matrices and Arrays.

Part 3

Write a function get shape which consumes a single character that should be one of I, J, L,

O, S, T, or Z and returns the matrix representing that shape. The returned matrix should be

the smallest sized matrix necessary to represent the requested shape. Elements representing

squares occupied by the shape should be the letter, and elements representing empty squares

surrounding the shape should be a space. For example, the J could be represented by the matrix:

[’J’ ’J’ ’J’;

’ ’ ’ ’ ’J’]

Part 4

Write a function get board slice which consumes a board, a shape (such as what would be

returned by get shape), an integer row, and an integer column. The function should return the

slice of the board starting from (row, column) and having the same dimensions as the shape, as

well as the ending row and ending column for the slice. For example, given the board

[’I’ ’ ’ ’ ’ ’ ’;

’I’ ’ ’ ’ ’ ’ ’;

’I’ ’O’ ’O’ ’ ’;

’I’ ’O’ ’O’ ’ ’]

3

the shape

[’L’ ’L’;

’ ’ ’L’;

’ ’ ’L’]

along with row 2 and column 3, the resulting slice would be

[’ ’ ’ ’;

’O’ ’ ’;

’O’ ’ ’]

the ending row would be 4, and the ending column would also be 4.

If attempting to place the shape at the passed in row and column would cause the shape to be

partially or fully off the board, then the empty matrix [] should instead be returned. Going with

our exmple from above, we would get the empty matrix if we instead passed in 4 for the column,

since the three rightmost blocks of the ”L” would be pushed off the right edge of the board.

Part 5

Write a function place shape which consumes a board, a shape, an integer row, and an integer

column. The function should then return a new board which is the old board modified to have

the shape placed on the board such that location (row, column) corresponds to the upper left

corner of the shape. Using the example from Part 4, with the board

[’I’ ’ ’ ’ ’ ’ ’;

’I’ ’ ’ ’ ’ ’ ’;

’I’ ’O’ ’O’ ’ ’;

’I’ ’O’ ’O’ ’ ’]

the shape

[’L’ ’L’;

’ ’ ’L’;

’ ’ ’L’]

the row 2, and column 3, the resulting board would be:

[’I’ ’ ’ ’ ’ ’ ’;

’I’ ’ ’ ’L’ ’L’;

’I’ ’O’ ’O’ ’L’;

’I’ ’O’ ’O’ ’L’]

If you take advantage of your get board slice from the previous section, you should be

able to do this in just a few lines of code without resorting to a for loop. Look at the ”Replace

Values That Meet a Condition” section of the ”Find Array Elements That Meet a Condition” page

in MATLAB’s documentation. You can find a link to this page in the documentaion for logical

operators.8 Then keep in mind that:

1. If, for example, you have two matrices A and B with the same dimensions, you can replace

all the elements of A that correspond to elements in B that are less than 10 with those

elements in B by doing A(B < 10) = B(B < 10).

2. You can replace a slice of a matrix A with matrix B by doing

A(start row:end row, start column:end column) = B, assuming B and the resulting

slice of A have the same dimensions.

8

from Documentation Home, MATLAB→Language Fundamentals→Operators and Elementary Operations→Logical

Operations.

4

Part 6

Write a function try fit which consumes a board slice and a shape, and returns two values:

1) A boolean which is true if the shape fits in this slice (that is, if all the squares that would be

occupied by the shape are spaces on the board slice), f alse otherwise; and 2) The fill score for

this fit - that is, the number of squares where a space in the shape lines up with a non-space on

the board slice. You should be able to implement the body of this function with 2 lines of code

- one for each of the return values - using relational operators to filter your matrices along with

some reducing functions9

Part 7

Write a function find best place for rotation which consumes a board and a shape and finds

the best fitting location on the board for the shape in its current rotation. If two locations are

equally good fits, then you should default to the lowest, rightmost position on the board. This

function will return the following values:

1. A boolean which is true if the shape fits on the board at all, f alse if there isn’t anywhere on

the board where it fits.

2. The row of the upper left block of the best location for the shape on the board.

3. The column of the upper left block of the best location for the shape on the board.

4. A numeric score for the shape’s best location on the board. Higher scores are better. This

score can be any heuristic you believe leads to a better packing of shapes on the board.

NB that the fit returned by try fit can be used here, either as the entire score or as a

component of it.

You should make use of your try fit and get board slice functions when implementing

this function.

Part 8

Write a function find best place which consumes a board and a shape. This function should

find the best fitting location on the board for the shape over its current rotation and three possible

90◦

rotations10 This function will return the following values:

1. A boolean which is true if the shape fits on the board at all, f alse if there isn’t anywhere on

the board where it fits.

2. The row of the upper left block of the best location for the shape on the board.

3. The column of the upper left block of the best location for the shape on the board.

4. The number of clockwise11 rotations (which will be between 0 and 3, inclusive) required for

the best fit.

You should make use of your find best place for rotation function when implementing

this function.

9Namely, the sum and all functions. You should read MATLAB’s documentation for these.

10Look up how to do this on the same documentation page that discusses creating and combing arrays referenced in

Part 2! This time you’ll want to look in the section on reshaping and rearranging.

11Yes, the direction here is important!

5

4 Putting it all Together

Open the run game.m file you downloaded in the Project Setup section. You don’t need to change

any code here, but you can look at it to get an idea of how it’s calling the code you just wrote in

the above parts. Now you should be able to call run game at the REPL and watch your program

fill up the game board as best it can.

Submit the following files on Canvas:

• unittests.m

• draw game board.m

• make board.m

• get shape.m

• get board slice.m

• place shape.m

• try fit.m

• find best place for rotation.m

• find best place.m

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Comp 250 Assignment 3 2020-05-24
- Macm 316 – Computing Assignment 7 2020-05-24
- Sta457 Assignment 2020-05-24
- Homework 10 2020-05-24
- Lab 2 Msc: Time Series Prediction With... 2020-05-24
- Comp2011作业代做、Data Analysis作业代写、C++编程语言 2020-05-24
- 代做compsys201作业、Python，Java，C/C++编程语言作业 2020-05-24
- Program留学生作业代做、Python编程设计作业调试、Data作业代写 2020-05-24
- 代写 Practical 3 Covid-19程序作业，代写... 2020-05-23
- 代写comp3059作业、代做programming作业、Java语言作业代 2020-05-23
- Coit12206作业代写、Program课程作业代做、Java、Pytho 2020-05-23
- Data2001作业代做、Data Science作业代做、Sql语言作业代 2020-05-23
- 代写comp2017作业、代写c/C++语言作业、代写data作业、C/C+ 2020-05-23
- Data留学生作业代做、Python编程设计作业调试、代写program课程 2020-05-22
- Mkan1-Uc 5103作业代写、代做analytics作业、Java，P 2020-05-22
- Pols 512作业代写、R编程设计作业调试、Data留学生作业代做、代写r 2020-05-21
- Econ 6070作业代做、Data课程作业代写、代做java，Python 2020-05-21
- Pstat 170 2020-05-20
- Comp 250 Assignment 3 2020-05-20
- Data留学生作业代做、代写r程序语言作业、代做r实验作业、代写progra 2020-05-20