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 four stages

1. April 7, partition integers
2. April 14, calculate the number of valid and  invalid pieces in a file
3. April 21, calculate the number of distinct pieces in a file
4. April 28, 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, 36 pieces of 6 squares, 107 pieces of 7 squares, 360 pieces of 8 squares.

The following figure shows pieces of 6 squares.

Stage 1 (2 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.

We may test your program using numbers larger than 10.

Stage 2 (2 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 (note you must not add '\n' at the end of your output)

                  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 n², here n is an integer between 4 and 10.
• The ending character '\0' is not included in the n² 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 n² for a positive integer between 4 and 10.
2. In a string of n² 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 upload the following test case which should output 2 4

in this test case pieces 1 and and 5 are valid . the 2nd piece is invalid because n is 8 and there is only 7 ones. the 3rd piece is invalid because of a hole , the 4th piece does not have n^2 digits, the 6th piece has detached ones

Submission Tests:

the first test checks if you code detects pieces with less than n 1's

the second test checks if your code detects pieces with holes

the third test checks if your code detects pieces with less than n squared items

the fourth test checks if your code detects pieces with detached ones

Stage 3 (2 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 (without a '\n')

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

Test cases:

The first test case checks if your program can detect rotations  ./rotations-test-case-2

answer is: 4

The second test case checks if your program can detect mirrors ./Mirror- test-cases

answer is: 3

The third test case checks if your program can detect pieces that are both rotated and shifted./test-case-3

answer is: 3

Stage 4 (4 points)

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

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 two 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).
• Makefile to create the executable. Name the executable as ipa3. The file name must be Makefile.
• This program must be named "ipa3" (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.3 point for each warning message.

Syntax Error

You will receive zero if your Makefile cannot produce an executable called "ipa3".

Run-Time Error

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