ECE 264 Advanced C Programming

IPA3-2: Detecting Valid "Super" Blokus Pieces

Due December 4, 2012 @ 6:00 pm

Summary

This assignment asks you to build a program that can evaluate "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 evaluate different pieces . Your algorithm should also detect duplicates.

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

Skeleton:

You can download the setup for this assignment here.  The zip file contains the following

• ipa3_2.c - Skeleton for the main function
• ipa3_2.h - Contains function headers and constants that can be useful for the assignment
• utility.c - Contains the auxiliary functions for the assignment
• Makefile - Can be used to compile and test assignment
• Testcases and their corresponding solutions

You can edit anything in the .c files, the .h files, and the Makefile to fit your program.

WHAT YOU NEED TO SUBMIT?

1. All the .c and .h files needed to execute your assignment.  All submissions for this IPA should have at least 2 .c files and 1 .hfile. You can more .c and .h file as you see fit. Any submisssions with one .c file will have points deducted.
2. Makefile to compile your assignment. For each submission, the executable should be named ipa3_2.
3. A README file that describes the algorithm used in your assignment.  The README should say how the functions accomplish their goals, not just the goals themselves.

HOW TO SUBMIT?