ECE 264 Advanced C Programming

IPA 3-3: Detecting Duplicate "Super" Blokus Pieces

Due December 4, 2012 @ 6:00pm

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

Skeleton:

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

 

• ipa3_3.c - Skeleton for the main function
• ipa3_3.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.  

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 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 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 .h file.  You can have more .c and .h files as you see fit.  Any submissions with one .c file will have points deducted.

2.    Makefile to compile your assignment.  For each submission, the executable should be names ipa3_1. 

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?

1.    You can submit as many submission on the checking website as you would need.  For this assignment, if you pass the testcases on the server,  it will not guarantee a perfect score during grading.  

 

2. Your submission for grading should be submitted through Blackboard.  You can submit as many times on Blackboard as you need before the deadline. We will grade the final submission, so please make sure that it is your FINAL version with everything included.  

HOW WILL WE GRADE YOUR SUBMISSION?

We will grade your assignments on algorithm correctness through DDD, memory allocation and deletions through valgrind , proper coding standards, content of README, a proper Makefile, and commenting.