# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# include "polyomino_embed.h"

/******************************************************************************/

int i4mat_sum ( int m, int n, int a[] )

/******************************************************************************/
/*
  Purpose:

    I4MAT_SUM sums the entries of an I4MAT.

  Discussion:

    An I4MAT is an MxN array of I4's, stored by (I,J) -> [I+J*M].

  Example:

    A = ( 1, 2 )
        ( 3, 4 )

    I4MAT_SUM = 10

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    01 May 2018

  Author:

    John Burkardt

  Parameters:

    Input, int M, N, the number of rows and columns.

    Input, int A[M*N], the vector to be summed.

    Output, int I4MAT_SUM, the sum of the entries of A.
*/
{
  int i;
  int j;
  int value;

  value = 0;
  for ( j = 0; j < n; j++ )
  {
    for ( i = 0; i < m; i++ )
    {
      value = value + a[i+j*m];
    }
  }

  return value;
}
/******************************************************************************/

int *polyomino_embed_list ( int mr, int nr, int r[], int mp, int np, int p[], 
  int number )

/******************************************************************************/
/*
  Purpose:

    POLYOMINO_EMBED_LIST lists the polyomino embeddings in a region.

  Discusion:

    A region R is a subset of an MRxNR grid of squares.

    A polyomino P is a subset of an MPxNP grid of squares.

    Both objects are represented by binary matrices, with the property that
    there are no initial or final zero rows or columns.

    For this computation, we regard P as a "fixed" polyomino; in other words,
    no reflections or rotations will be allowed.

    An "embedding" of P into R is an offset (MI,NJ) such that 
      P(I,J) = R(I+MI,J+NJ) 
      for 1 <= I <= MP, 1 <= J <= NP, and 
      for 0 <= MI <= MR-MP, 0 <= MJ <= NR-NP.
    We can detect an embedding simply by taking what amounts to a kind of
    dot product of P with a corresponding subregion of R.

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    01 May 2018

  Author:

    John Burkardt

  Parameters:

    Input, int MR, NR, the number of rows and columns in the representation
    of the region R.

    Input, int R(MR,NR), a matrix of 0's and 1's representing the 
    region.

    Input, int MP, NP, the number of rows and columns in the representation
    of the polyomino P.

    Input, int P[MP*NP], a matrix of 0's and 1's representing the 
    polyomino.

    Input, int NUMBER, the number of embeddings.

    Output, int LIST[NUMBER*2], for each embedding, the I and J offsets
    applied to the polyomino P.
*/
{
  int i;
  int j;
  int k;
  int *list;
  int mi;
  int nj;
  int pr;
  int srp;

  list = ( int * ) malloc ( number * 2 * sizeof ( int ) );
/*
  Count the 1's in P.
*/
  pr = i4mat_sum ( mp, np, p );
/*
  For each possible (I,J) coordinate of the upper left corner of a subset of R,
  see if it matches P.
*/
  k = 0;
  for ( mi = 0; mi <= mr - mp; mi++ )
  {
    for ( nj = 0; nj <= nr - np; nj++ )
    {
      srp = 0;
      for ( j = 0; j < np; j++ )
      {
        for ( i = 0; i < mp; i++ )
        {
          srp = srp + p[i+j*mp] * r[i+mi+(j+nj)*mr];
        }
      }
      if ( srp == pr )
      {
        list[k+0*number] = mi;
        list[k+1*number] = nj;
        k = k + 1;
      }
    }
  }

  return list;
}
/******************************************************************************/

int polyomino_embed_number ( int mr, int nr, int r[], int mp, int np, int p[] )

/******************************************************************************/
/*
  Purpose:

    POLYOMINO_EMBED_NUMBER counts the number of polyomino embeddings in a region.

  Discusion:

    A region R is a subset of an MRxNR grid of squares.

    A polyomino P is a subset of an MPxNP grid of squares.

    Both objects are represented by binary matrices, with the property that
    there are no initial or final zero rows or columns.

    For this computation, we regard P as a "fixed" polyomino; in other words,
    no reflections or rotations will be allowed.

    An "embedding" of P into R is an offset (MI,NJ) such that 
      P(I,J) = R(I+MI,J+NJ) 
      for 1 <= I <= MP, 1 <= J <= NP, and 
      for 0 <= MI <= MR-MP, 0 <= MJ <= NR-NP.
    We can detect an embedding simply by taking what amounts to a kind of
    dot product of P with a corresponding subregion of R.

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    01 May 2018

  Author:

    John Burkardt

  Parameters:

    Input, int MR, NR, the number of rows and columns in the representation
    of the region R.

    Input, int R[MR*NR], a matrix of 0's and 1's representing the 
    region.

    Input, int MP, NP, the number of rows and columns in the representation
    of the polyomino P.

    Input, int P[MP*NP], a matrix of 0's and 1's representing the 
    polyomino.

    Output, int POLYOMINO_EMBED_NUMBER, the number of distinct embeddings of 
    P into R.
*/
{
  int i;
  int j;
  int mi;
  int nj;
  int number;
  int pr;
  int srp;

  number = 0;
/*
  Count the 1's in P.
*/
  pr = i4mat_sum ( mp, np, p );
/*
  For each possible (I,J) coordinate of the upper left corner of a subset of R,
  see if it matches P.
*/
  for ( mi = 0; mi <= mr - mp; mi++ )
  {
    for ( nj = 0; nj <= nr - np; nj++ )
    {
      srp = 0;
      for ( j = 0; j < np; j++ )
      {
        for ( i = 0; i < mp; i++ )
        {
          srp = srp + p[i+j*mp] * r[i+mi+(j+nj)*mr];
        }
      }
      if ( srp == pr )
      {
        number = number + 1;
      }     
    }
  }

  return number;
}
/******************************************************************************/

void polyomino_print ( int m, int n, int p[], char *label )

/******************************************************************************/
/*
  Purpose:

    POLYOMINO_PRINT prints a polyomino.

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    29 April 2018

  Author:

    John Burkardt

  Parameters:

    Input, int M, N, the number of rows and columns in the representation
    of the polyomino P.

    Input, int P[M*N], a matrix of 0's and 1's representing the 
    polyomino.  

    Input, char *LABEL, a title for the polyomino.
*/
{
  int i;
  int j;

  printf ( "\n" );
  printf ( "%s\n", label );
  printf ( "\n" );
  if ( m <= 0 || n <= 0 )
  {
    printf ( " [ NULL matrix ]" );
  }
  else
  {
    for ( i = 0; i < m; i++ )
    {
      for ( j = 0; j < n; j++ )
      {
        printf ( " %d", p[i+j*m] );
      }
      printf ( "\n" );
    }
  }
  return;
}
/******************************************************************************/

void timestamp ( )

/******************************************************************************/
/*
  Purpose:

    TIMESTAMP prints the current YMDHMS date as a time stamp.

  Example:

    17 June 2014 09:45:54 AM

  Licensing:

    This code is distributed under the GNU LGPL license. 

  Modified:

    17 June 2014

  Author:

    John Burkardt

  Parameters:

    None
*/
{
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct tm *tm;
  time_t now;

  now = time ( NULL );
  tm = localtime ( &now );

  strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm );

  printf ( "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}