Lecture 18 ECE264F12Lu - Rhea

John Ribeiro - Lecture 18

A square refers to a single building block the composes a piece. A piece refers to a compilation of multiple squares.

Duplicates are formed through:

Rotation Mirroring

Suppose you want to generate pieces of n squares:

1) Break n into the sum of positive integers. Each integer is the number of squares in each row. 2) Shift the squares to create different pieces 3) Eliminate Duplicates

void f ( int n ) { int i; if ( n == 0 ) {

 return;

} for ( i = 1 ; i < n ; i ++ ) {

 f ( n - i );

} }

That means that each integer can be partitioned into its components, for example,

4 = 1 + 3 4 = 2 + 2 4 = 3 + 1 4 = 4

For each n integer, there will be n partitions

This algorithm will not generate a non-continuous piece

NOT:

xox oxo xox

OR:

oxo oxo ooo

BUT:

ooo oxx ooo

• Where o denotes a block and x an empty space.

Lecture notes_Lecture18_Mar 20_Kailu Song

1. The explanation of program 2

  a. the square and piece(one piece have several square)
  b. duplicates: rotate the piece will generate another duplicate piece
  c. rotation mirror: horizontal mirror and vertical mirror
  e. invalid piece: there is a space between two square in one row(eg.010 101 010)
  For this assignment, give the number of squares, generate all picecs(delete invalid piece, deplicate piece and mirror piece) using one dimensional array.

2. Hint for this assignment:

  first stage: partition integers:
  ex. 4 = 1+1+1+1
      4 = 1+1+2
      4 = 1+2+1
      4 = 1+3
      4 = 2+2...
  Use recursion
  void f(int n)
  {
    int i;
    if (n==0)
      {
          return;
      }
     if (i=1;i<n;i++)
      {
        f(n-i);
      }
  }

Lecture 18 Summery Shiyu Wang Mar25th

This class talked about how to solve IPA2-1. Generally, Tetris usually has 4 squares in each block, in this assignment, we will have different number of squares in each block. And we will print out each combination,which does not includes any duplicates. The duplicates means rotation or mirror. For example,

(111,100)      ,
(100,100,110) are rotation.

(111,100), (111,001), are mirror. All square, need to be connected to each other by side, which means (1000,1100,0110,0011) is valid,but (1000,0100,0010,0001) is not valid. We can solve this problem by splitting the integer in different ways. hint: 5=1+3+1

=2+2+1
=4+1
...

The procedure for solving this problem is, 1. Break n into sum of positive integers, each is number of square in a row. 2. Shift the square to create different species. 3. Eliminate duplicates.

The sample code is like this,

Void f(int n) {

 int i;
 if(n==0)
 {
   print;
   return;
 }
 for(i=0;i<n;i++)
 {
   f(n-1);
 }

}