/*H************************************************************************************************/
/*!

\File    main.cpp

\Description
    Hacker's Delight #8 - Matrix Flip

\Notes
    Please read the RULE and NOTE comments below. Entries that violate RULE(s) will be rejected.

*/
/************************************************************************************************H*/

/* 
 * !!!!!!!!!!!!!!!!!!!
$$RULE: All submitted code must be within the START and END tokens (see below). 
 * !!!!!!!!!!!!!!!!!!!
*/

#include <iostream>
#include <math.h>
#include <time.h>
#include <float.h>

/* $$RULE: Replace "Author_Institute" with your full name and institution (company or school)
           EXAMPLE: JonDoe_ElectronicArtsTiburon
*/
namespace Author_Institute
{

// MatrixFlip class
class MatrixFlipC
{
public:
    MatrixFlipC(int *pMatrix, int h, int w);
   ~MatrixFlipC();

    void Execute();
    int  Grade(char *pStrResult);

    // helper func for dereferencing 2d matrix of unknown size
    // Ex: Mat2d(3,4) == &Matrix[3][4]
    inline int * Mat2d(int x, int y) { return m_pMatrix + ((y * m_Width) + x); }

protected:
    void FlipSignRow(int);
    void FlipSignCol(int);
    void ComputeSums();

    int *m_pMatrix;
    int m_Width;
    int m_Height;

    int *m_SumC;    // col sum
    int *m_SumR;    // row sum
    int  m_SumM;    // matrix sum

    // stats
    int m_RFlipCnt;
    int m_CFlipCnt;
};

//
// ----------------- START -----------------
//

/******************************************************************************/
/*! MatrixFlipC::Execute

    Compute the MINIMUM non-negative value of m_SumM that can be obtained by a succession 
    of calls to FlipSignCol() and FlipSignRow() such that all values in m_SumC and m_SumR are 
    also non-negative, AND give the shortest possible sequence of such calls which
    achieves this value m_SumM while satisfying the non-negative property for all elements 
    in m_SumC and m_SumR.

    Please provide a written (English) description of your implementation here.
    The more detail, the better!!!

    Your code must compile in MS Visual Studio 2005 and run on a standard P4.

    Have fun,

    --hackers

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

void MatrixFlipC::Execute()
{
#if 0
    // your tools:
    ComputeSums();      // compute m_SumC, m_SumR, and m_SumM.
    FlipSignCol(x);     // flip sign of column x
    FlipSignRow(y);     // flip sign of row y
#endif
}

//
// ----------------- END -----------------
//

MatrixFlipC::MatrixFlipC(int *pMatrix, int h, int w)
{
    m_pMatrix = pMatrix;
    m_Width = w;
    m_Height = h;

    m_SumC = new int[w];
    m_SumR = new int[h];

    m_RFlipCnt = m_CFlipCnt = 0;
}

void MatrixFlipC::ComputeSums()
{
    int x,y;

    // clear
    memset(m_SumC,0,sizeof(m_SumC[0])*m_Width);
    memset(m_SumR,0,sizeof(m_SumR[0])*m_Height);
    m_SumM = 0;

    // sum m_SumR/m_SumC
    for (y=0; y < m_Height; y++)
    {
        for (x=0; x < m_Width; x++)
        {
            int offset = (y * m_Width) + x;
            m_SumR[y] += m_pMatrix[offset];
            m_SumC[x] += m_pMatrix[offset];
        }
    }

    // sum m_SumM
    for (y=0; y < m_Height; y++)
    {
        m_SumM += m_SumR[y];
    }
    for (x=0; x < m_Width; x++)
    {
        m_SumM += m_SumC[x];
    }
}

MatrixFlipC::~MatrixFlipC()
{
    delete [] m_SumC;
    delete [] m_SumR;
}

int MatrixFlipC::Grade(char *pStrResult)
{
    int i;

    // determine m_SumC, m_SumR, and m_SumM
    ComputeSums();

    // test m_SumR
    for (i=0; i < m_Height; i++)
        if (m_SumR[i] < 0) { sprintf_s(pStrResult,1024,"FAIL: m_SumR[%d] is negative (%d)\n",i,m_SumR[i]); return -1; }

    // test m_SumC
    for (i=0; i < m_Width; i++)
        if (m_SumC[i] < 0) { sprintf_s(pStrResult,1024,"FAIL: m_SumC[%d] is negative (%d)\n",i,m_SumC[i]); return -1; }

    // minimization stats
    sprintf_s(pStrResult,1024,"Entry passed. Stats:\n\tRow flips: %d\n\tCol flips: %d\n\tS value: %d\n",
        m_RFlipCnt,m_CFlipCnt,m_SumM);

    return 0;
}

void MatrixFlipC::FlipSignRow(int i)
{
    m_RFlipCnt++;
    int *pElement = m_pMatrix + (i * m_Width);
    for (int x=0; x < m_Width; x++)
    {
        int * pElement = Mat2d(x,i);
        *pElement *= -1;
    }
}

void MatrixFlipC::FlipSignCol(int i)
{
    m_CFlipCnt++;
    for (int y=0; y < m_Height; y++)
    {
        int * pElement = Mat2d(i,y);
        *pElement *= -1;
    }
}

} // end namespace

// -------------------------------------------------------------

int main (int argc, char * const argv[])
{
    int matrix[27][9] = { 
    { 33,    30,    10,    -6,    18,    -7,   -11,    23,    -6, },
    { 16,   -19,     9,   -26,    -8,   -19,    -8,   -21,   -14, },
    { 17,    12,   -14,    31,   -30,    13,   -13,    19,    16, },
    { -6,   -11,     1,    17,   -12,    -4,    -7,    14,   -21, },
    { 18,   -31,    34,   -22,    17,   -19,    20,    24,     6, },
    { 33,   -18,    17,   -15,    31,    -5,     3,    27,    -3, },
   { -18,   -20,   -18,    31,     6,     4,    -2,   -12,    24, },
    { 27,    14,     4,   -29,    -3,     5,   -29,     8,   -12, },
   { -15,    -7,   -23,    23,    -9,    -8,     6,     8,   -12, },
    { 33,   -23,   -19,    -4,    -8,    -7,    11,   -12,    31, },
   { -20,    19,   -15,   -30,    11,    32,     7,    14,    -5, },
   { -23,    18,   -32,    -2,   -31,    -7,     8,    24,    16, },
    { 32,    -4,   -10,   -14,    -6,    -1,     0,    23,    23, },
    { 25,     0,   -23,    22,    12,    28,   -27,    15,     4, },
   { -30,   -13,   -16,    -3,    -3,   -32,    -3,    27,   -31, },
    { 22,     1,    26,     4,    -2,   -13,    26,    17,    14, },
    { -9,   -18,     3,   -20,   -27,   -32,   -11,    27,    13, },
   { -17,    33,    -7,    19,   -32,    13,   -31,    -2,   -24, },
   { -31,    27,   -31,   -29,    15,     2,    29,   -15,    33, },
   { -18,   -23,    15,    28,     0,    30,    -4,    12,   -32, },
   {  -3,    34,    27,   -25,   -18,    26,     1,    34,    26, },
   { -21,   -31,   -10,   -13,   -30,   -17,   -12,   -26,    31, },
    { 23,   -31,   -19,    21,   -17,   -10,     2,   -23,    23, },
    { -3,     6,     0,    -3,   -32,     0,   -10,   -25,    14, },
   { -19,     9,    14,   -27,    20,    15,    -5,   -27,    18, },
    { 11,    -6,    24,     7,   -17,    26,    20,   -31,   -25, },
   { -25,     4,   -16,    30,    33,    23,    -4,    -4,    23, },

    };

    Author_Institute::MatrixFlipC FlipperObj(*matrix,27,9);
    char strResult[1024];

    FlipperObj.Execute();
    FlipperObj.Grade(strResult);

    printf(strResult);

    return 0;
}