Data representation and Operations   Vertical flip

  

 The grid of 4 numbers is represented by a 2×2 array:

   int grid[2][2] = {{1,2},{3,4}};
                    // 1 2
                    // 3 4



 The vertical flip operation is implemented as:

     // Exchange:    grid[0][0] <--->  grid[0][1]  
     //
     //              grid[1][0] <--->  grid[1][1]

     int h;
     h = grid[0][0]; grid[0][0] = grid[0][1]; grid[0][1] = h;
     h = grid[1][0]; grid[1][0] = grid[1][1]; grid[1][1] = h;

Data representation and Operations   Horizontal flip

  

 The grid of 4 numbers is represented by a 2×2 array:

   int grid[2][2] = {{1,2},{3,4}};
                    // 1 2
                    // 3 4



 The horizontal flip operation is implemented as:

     // Exchange:    grid[0][0]   grid[0][1]  
     //                  ^            ^
     //                  |	      |
     //                  V	      V
     //              grid[1][0]   grid[1][1]

     int h;
     h = grid[0][0]; grid[0][0] = grid[1][0]; grid[1][0] = h;
     h = grid[0][1]; grid[0][1] = grid[1][1]; grid[1][1] = h;

Naive solution    Pseudo Code 
   cin >> myString;

   for ( int i = 0; i < myString.size(); i++ )
   {
      if ( myString[i] == 'V' )
      {  
        Flip vertically



      }
      else
      {  
        Flip horizontally



      }
   }

   Print grid;

Naive solution    C++ code 
   cin >> myString;

   for ( int i = 0; i < myString.size(); i++ )
   {
      if ( myString[i] == 'V' )
      {  // Flip vertically

         int h;
         h = grid[0][0]; grid[0][0] = grid[0][1]; grid[0][1] = h;
         h = grid[1][0]; grid[1][0] = grid[1][1]; grid[1][1] = h;
      }
      else
      {  // Flip horizontally

         int h;
         h = grid[0][0]; grid[0][0] = grid[1][0]; grid[1][0] = h;
         h = grid[0][1]; grid[0][1] = grid[1][1]; grid[1][1] = h;
      }
   }

   cout << grid[0][0] << " " << grid[0][1] << endl;
   cout << grid[1][0] << " " << grid[1][1] << endl;

Faster solution:    H and V operations are commutative

H and H commutes: 

  HH commutes:

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    H1    | c | d |    H2    | a | b |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | a | b |          | c | d |
     +---+---+          +---+---+          +---+---+

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    H2    | c | d |    H1    | a | b |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | a | b |          | c | d |
     +---+---+          +---+---+          +---+---+

In fact:    HH will cancel each other !

Faster solution:    H and V operations are commutative

V and V commutes: 

  VV commutes:

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    V1    | b | a |    V2    | a | b |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | d | c |          | c | d |
     +---+---+          +---+---+          +---+---+

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    V2    | b | a |    V1    | a | b |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | d | c |          | c | d |
     +---+---+          +---+---+          +---+---+

In fact:    VV will cancel each other !

Faster solution:    H and V operations are commutative

H and V commutes: 

  HH commutes:

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    H     | c | d |    V     | d | c |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | a | b |          | b | a |
     +---+---+          +---+---+          +---+---+

    arbitrary 
    initial state
     +---+---+          +---+---+          +---+---+
     | a | b |    V     | d | c |    H     | a | b |
     +---+---+  ----->  +---+---+  ----->  +---+---+
     | c | d |          | d | c |          | b | a |
     +---+---+          +---+---+          +---+---+

Therefore:    we can re-order the H, V operations

How to transform operations

  

   (1) Move all H operations to the front
   (2) Cancel every pair of H operations

   (3) Move all V operations to the back
   (4) Cancel every pair of V operations

   (5) Perform the remaining operations on the grid



 Example:

   input:             HHVHVVHHV

   transformed input: HHHHHVVVV

   cancel:            ----H----

   We end up doing only 1 H operation on the grid !

Improved solution:    J4 solution in C++ 
   cin >> myString;

   int nH = 0, nV = 0;

   for ( int i = 0; i < myString.size(); i++ )
   {
      if ( myString[i] == 'V' )
         nV++;
      else
         nH++;
   }

   if ( nV % 2 == 1 )
   {  // Flip vertically
      int h;
      h = grid[0][0]; grid[0][0] = grid[0][1]; grid[0][1] = h;
      h = grid[1][0]; grid[1][0] = grid[1][1]; grid[1][1] = h;
   }

   if ( nH % 2 == 1 )
   {  // Flip horizontally
      int h;
      h = grid[0][0]; grid[0][0] = grid[1][0]; grid[1][0] = h;
      h = grid[0][1]; grid[0][1] = grid[1][1]; grid[1][1] = h;
   }