/*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;
}