Home
Netbeans Eclipse Qt Java
Games
College of Engineering Aeronautics and Astronautics Agricultural and Biological Engineering Biomedical Engineering Chemical Engineering Civil Engineering Construction Engineering and Management Electrical and Computer Engineering Engineering Education Engineering Professional Education Environmental and Ecological Engineering Industrial Engineering Materials Engineering Mechanical Engineering Nuclear Engineering
EPICS (Engineering Projects In Community Service) First-Year Engineering Program First-Year Engineering Honors Program Global Engineering Program Minority Engineering Program Professional Practice (Co-Op) Program Women in Engineering Program
College Administration Schools Programs All Groups All People ECN Webmail
Purdue Home

ECE 264 Advanced C Programming

Generate "Super" Blokus Pieces

Summary

This assignment asks you to build a program that can generate "Super" Blokus pieces, each with 4 - 10 squares. This is called "Super" Blokus because the original Blokus has pieces up to  5 squares only. so we extend the game to generate pieces containing  10 squares .

You need to design several algorithms to generate different pieces . Your algorithm should also detect duplicates.

Stages

This assignment is divided into five stages

  1. March 24, partition integers
  2. March 31, convert 1-d formats to 2-d fmormats and vice-versa
  3. April 7, calculate the number of valid and  invalid pieces in a file
  4. April 16, calculate the number of distinct pieces in a file
  5. April 23, generate valid pieces, each with n squares (n is an integer between 4 and 8 inclusive)

In this assignment, all files use the ASCII (i.e. text) format.

"Super" Blokus Pieces

Tetris is a popular game that uses Blokus pieces. Tetris has 7 pieces, each with 4 squares, shown below.

as you can see Tetris allows mirror (the  'L' (blue) piece and  the orange piece are mirrors and the 'z' (red) piece and the green piece are mirrors) . if we disallow mirrors then we get only 5 unique valid pieces made of 4 squares . Blokus considers mirrors duplicates so your Blokus algorithm should consider the mirrors as invalid piece.

The figure bellow shows the 5 valid pieces that blokus needs to generate when the number of squares is 4.

Blokus consider any rotation or mirroring  of a piece as a duplicate and does not count it . the figure below shows the 8 different rotations and/or mirrors of a 4 squares Blokus piece. your algorithm should detect these as duplicates and generate only one of them

Your algorithm should generate 5 pieces of 4 squares,  12 pieces of 5 squares, 35 pieces of 6 squares, 107 pieces of 7 squares, 360 pieces of 8 squares.

The following figure shows pieces of 6 squares.

Stage 1 (5 points)

Your program takes one input argument (argv[1]) and it is a positive integer .Your program partition the integer into the sum of positive integers and print every positive partitions to the screen. 

Example 1: ./ipa3 3

produces output

	[1 1 1]
	[1 2]
	[2 1]
	[3]

Example 2: ./ipa3 4

produces output

	[1 1 1 1]
	[1 1 2]
	[1 2 1]
	[1 3]
	[2 1 1]
	[2 2]
	[3 1]
	[4]

Example 3: ./ipa3 5

produces output

	[1 1 1 1 1]
	[1 1 1 2]
	[1 1 2 1]
	[1 1 3]
	[1 2 1 1]
	[1 2 2]
	[1 3 1]
	[1 4]
	[2 1 1 1]
	[2 1 2]
	[2 2 1]
	[2 3]
	[3 1 1]
	[3 2]
	[4 1]
	[5]

The output of your program must be in this format:

  • Each line represents one valid partition.
  • Each line starts with '[' and ends with ']'.
  • There is one space between two numbers. There is no space after '[' and no space before ']'.
  • The orders of these lines can be different. The order will not affect your score.
  • Your program should throw errors if the number of command line arguments does not equal 2 or if the command line argument is not a positive integer

We may test your program using numbers larger than 10.

You can find code for printing the output and error messages here.

Stage 2 (5 points)

At this stage the program takes as input a file name (text file not binary).   The file contains 1-d and 2-d representations of pieces.  Your program should convert 1-d representations to 2-d representations and vice-versa.  For example, the piece

100100100 

would be transformed into

100
100
100
 
Each piece in the input files is separated by one blank line.  For example, a file could look like

110100000

1000
1100
1000
0000
 
1100110000000000

Your output should be the converted pieces in the same order.  Using the example from above, the output would be

110
100
000
 
1000110010000000
 
1100
1100
0000
0000
 
  • Testcases can contain combinations of 1-d and 2-d representations of pieces.
  • Error messages should be printed when the number of command-line arguments is not equal to 2 or if the input file cannot be opened and the program should exit with the status EXIT_FAILURE.
  • The biggest possible piece is 100 characters.
  • Transformations should be printed in the same order they are in the input file.  
  • You can find the code for the error messages here.   There will be node code provided for the printing of the arrays. 
  • You can find example testcases here.

Stage 3 (5 points)

At this stage the program takes as input a file name (text file not binary).  The file contains one Blokus piece per line (check the encoding section below) that  your program needs determine which are valid and which are not. Again, each piece is on a different line (i.e., separated by '\n').

The output of your program is simply 2 numbers separated by a space. the two numbers are :

  • the number of valid pieces.
  • the number of invalid pieces.

example: if we have 4 valid pieces and 2 invalid pieces the output should appears as follows

                  4 2

Encoding

  • A piece is represented in the file using binary encoding using a string of 0's or 1's.
  • The length of the string is n2, here n is an integer between 4 and 10.
  • The ending character '\0' is not included in the n2 characters.
  • There are n 1's and the others are 0's.

The following is an example of a 5-squares piece encoding.

Invalid pieces:

The reasons that makes a piece invalid are :

  1. A string whose length is not n2 for a positive integer between 4 and 10.
  2. In a string of n2 characters, there are less than n 1's or more than n 1's.
  3. The 1's are not connected. For example, 0100101001100000 .
  4. There is one or more holes in the same row.  A hole is defined as an unoccupied square that is enclosed by squares in the same row.  (Note that this is an additional constraint that we add to make the checking and the generation of Blokus pieces easier. A physical Blokus piece does not have this constraint. In part 4 we will discuss how it makes the generation task easier.)

Test Case:

You can download examples testcases here.

Output

You can find the functions used for printing here.

Stage 4 (5 points)

The program takes as input a file name. The file has a set of valid pieces. The code must check the duplicates in this file and print out as a result the number of distinct pieces.

So the output is one number printed to the screen followed by a newline character

Two pieces are duplicates if they are the same by

  • Rotation. Two pieces are duplicates if one is identical to the other after rotating by 90, 180, or 270 degrees.  example 0100010001100000 and 0111010000000000 are duplicates since the second piece is the 1st piece rotated by 90 degrees
  • Mirror. Two pieces are duplicates if one is identical to the other after vertical mirror, or horizontal mirror, or both.  example 0100010001100000 and 0110010001000000 are duplicates

Note that : Two pieces are duplicates if one is identical to the other after some combinations of the two types of operations (rotation and mirror) mentioned above .

Note: a piece will have at least a one in the 1st column and a one in the 1st row. So you don't have to worry about shifts.

Input file format:

  • The input file has each piece on a line ( each piece ends with a '\n')
  • The last piece also has '\n'
  • The pieces in the same file can be of variable size

Specifications:

  • If you are storing blokus pieces from the file, they must be stored in a linked list.
  • All pieces are given with a rotation or inversion of a valid blokus piece.
  • The output is the number of distinct pieces given in the input plus a newline character.

Test cases:

You can find sample testcases for this part of the project here.

 

Stage 5 (5 points)

The program takes a single number n as input  (between 4 and 8) . The program needs to generate all possible UNIQUE pieces composed of n  squares. The output is printed to the screen each piece on a line.

e.g. If 6 is given as an input, then your output should have 35 lines.

Note a piece should have at least one square in the 1st row and and least one square in the first column (in other words, the piece should be shifted as far left and up as possible).

Hint: Because of constraint 4, that Blokus pieces must not have holes in the same row (unoccupied squares enclosed by occupied squares in the same row), you can keep all occupied squares in the same row together and just shift them horizontally when generating new pieces.

Warnings

This assignment is much more challenging (in algorithm design) and complex (in programming) than the previous assignments. You must start early. Do not procrastinate.

  • You need to have a strategy before writing code. For complex problems like this, it is usually true that "The earlier you start coding, the longer it takes."  Why is this true? If you start coding without a strategy, you will likely write code that does not meet your purpose.  As a result, you will keep changing the code and spend more time.
  • You should use version control to manage your assignment. By using version control, you can experiment new ideas without losing the code that is already working. Every time you have an idea, you can write the code, commit it into your repository, and test the code. If the program has problems, you can easily retrieve a earlier version.
  • You are strongly encouraged to discuss your algorithms with classmates. However, do not share code.
  • The sample solution takes less one second. Your program must finish within one minute. Otherwise, the grading server will timeout and you receive zero.

What to Submit?

Please submit a zip file containing the following files:

  • Necessary source code (including all .c and .h needed to generate the final executable)  You should submit at least 2 .c files  and 1 .h file for each assignment.
  • Makefile to create the executable. Name the executable as ipa2-x, where x is the corrsponding step. The file name must be Makefile.
  • This program must be named "ipa2-x" (in Makefile).
  • README that explains your strategy, algorithms and data structures used in your program. The file name must be README.
  • Create a single zip file. Do not include object files, executable files, sample input, or sample output in your package.

Submission Procedure

You must submit through this web site. This is the only way to submit your exercises and programming assignments. 

You need to provide a user name and a password through Blackboard before submission.  The user name and the password are different from your Purdue career account.

Requirements

Memory Management

Memory management (allocation and release) is an important part of ECE 264. You have to allocate enough memory to make your program work. You have to allocate and release memory as needed. You are not allowed to allocate a large piece of memory regardless of the input size. We will restrict stack size to prevent that. You will receve heavy penalty (50%) if your program does not release all memory (i.e. memory leak). We will use valgrind to check for memory leaks.

Compiler Warnings

You must remove all warning messages reported by gcc -Wall -Wshadow. You will use 0.2 point for each warning message.

Syntax Error

You will receive zero if your Makefile cannot produce an executable called "ipa2-x", where x is the corresponding step.

Run-Time Error

You will receive zero if your has a run-time error (such as "Segmentation Fault")