// Mole.cpp

//

// IEEE Challenge 13 - The Hard Life Of A Mole

// http://www.ieee.org/portal/cms_docs_iportals/iportals/membership/

// /students/scholarshipsawardscontests/

// /IEEEXtreme2008_Competitition_book_2.pdf

//

// by Adrian Dale 15/12/2008 / 26/07/2009

#include <iostream>

#include "Mole.h"

int main( int argc, char **argv)

{

Underground theUnderground;

cout << theUnderground.Solve() << endl;

return 0;

}

// Does what it says on the tin!

int Underground::Solve()

{

ReadInput();

Solve_Init();

// Clear out mWorkMap's visited record

// We no longer need to do this. Code is a left-over from when I

// was using the mWorkMap to do pre-checks on the validity of the map.

// I've left it in (but commented out) as a record of how to

// do this should it be needed in future

//for_each( mWorkMap.data(),

// mWorkMap.data() + mWorkMap.num_elements(),

// bind2nd(mem_fun_ref(&WorkingMapCell::SetVisited), false) );

Solve_FirstPass();

// Map is only solveable if the first pass visited our end point,

// having started from the start point.

if ( !mWorkMap[mEndPos.x][mEndPos.y].mVisited )

{

cout << "ERROR: Map has no solution" << endl;

return -1;

}

// Repeat scan until done

while ( RescanCheapest() != 0 )

;

return SolutionCost();

}

// Set up the map ready to be solved

void Underground::Solve_Init()

{

// Set up our working map

mWorkMap.resize(boost::extents[mCols][mRows]);

// Initialise it from the map data we read in.

// We'll keep a pristine copy of that, rather than work on it, so

// we can use it to refresh the display or work map, if necessary.

for( int y=0; y<mRows; ++y )

for( int x=0; x<mCols; ++x )

mWorkMap[x][y].SetCell( mMapData[x][y] );

// Find our starting and ending points - they are member variables

// to save us having to repeat this calculation

mStartPos = FindSquare('A');

mEndPos = FindSquare('B');

// Our first move will never be 0,0 as there will always

// a wall around the map. This checks that we did find a first move.

// We're using assertions to assert that a valid map was passed in.

// For a proper app, we'd have separate code to check maps.

// eg for valid start and end positions

assert(mStartPos.x != 0 && mStartPos.y != 0);

assert(mEndPos.x != 0 && mEndPos.y != 0);

}

// Routine to locate either our start ('A') or our end ('B') position

// Assumes map data is valid

Move Underground::FindSquare( MapDataCellType squType ) const

{

assert(squType == 'A' || squType == 'B');

for( int y=0; y<mRows; ++y )

for( int x=0; x<mCols; ++x )

if ( mWorkMap[x][y].mCell == squType )

return Move(x,y);

assert(false); // Map doesn't contain start or end - ERROR!

return Move();

}

// Solve_FirstPass starts from the start square and recursively

// (simulated using a stack) visits each neighbouring square and

// adds up the cost to travel back to the start square.

// This only gives an approximation to the final answer, because

// sometimes the cheapest route is one that hasn't yet been found

// by this pass of the solver.

// Once we have a first pass, which has visited all visitable

// squares, we will iteratively refine the solution using RescanCheapest

void Underground::Solve_FirstPass()

{

// The stack will hold each square that remains to be checked.

// This simulates recursion but without the function call

// overhead.

MoveStackType moveStack;

// Kick the algorithm off by marking our start position as

// visited and pushing it onto the stack

mWorkMap[mStartPos.x][mStartPos.y].mVisited = true;

mWorkMap[mStartPos.x][mStartPos.y].mCostToStart = 0;

mWorkMap[mStartPos.x][mStartPos.y].mCheapestMove = mStartPos;

moveStack.push(mStartPos);

// We keep popping moves off the stack and processing them

// until there are no more moves left on the stack.

// Processing means checking each neighbour to see if we've

// visited it before, and if not, if it is visitable.

// If yes, then push it onto the stack, so its neighbours can

// be checked in turn.

// Eventually (when there are no moves left on the stack) we'll

// have visited all of the visitable squares.

while( !moveStack.empty() )

{

Move &currentMove = moveStack.top();

moveStack.pop();

const int x = currentMove.x; // A bit of renaming so that our macro

const int y = currentMove.y; // works. Messy, but compiler should

// optimise it away

#define DIRECTION(xx,yy) ProcessDirection(moveStack, xx,yy);

DIRECTION(x-1,y-1);

DIRECTION(x,y-1);

DIRECTION(x+1,y-1);

DIRECTION(x+1,y);

DIRECTION(x+1,y+1);

DIRECTION(x,y+1);

DIRECTION(x-1,y+1);

DIRECTION(x-1,y);

#undef DIRECTION

}

}

// Not sure what this could be, but didn't want to use -1, as we're

// always looking for a number less than this to start the algorithm

#define MAX_COST 1000000

// ProcessDirection is called from Solve_FirstPass and is used to

// work out what to do with a square joining onto the one we are

// currently investigating.

// We need to mark it as visited, then find the cheapest cost back to

// the start. If the cheapest cost back to the start is lower than an

// existing route to the start then we need to recurse back through the

// map updating the cheapest route

void Underground::ProcessDirection(MoveStackType &moveStack, int x, int y)

{

// If we've already visited this square, then no need to process it again.

if ( mWorkMap[x][y].mVisited == true || mWorkMap[x][y].mCell == '@')

return;

mWorkMap[x][y].mVisited = true;

// Store move so that all possible moves from this direction will

// get processed once this move is popped from the stack

moveStack.push(Move(x,y));

// We need to see which (known) direction has the cheapest cost of a move back

// to the start.

int cheapestToStart = MAX_COST;

Move cheapestMove;

WorkingMapCell *workCell;

#define CHECK_COST_TO_START(xx,yy) \

if (workCell->mVisited == true) \

{ \

if ( workCell->mCostToStart < cheapestToStart ) \

{ \

cheapestToStart = workCell->mCostToStart; \

cheapestMove = Move(xx,yy); \

} \

}

// This code calls CHECK_COST_TO_START for each direction.

#define DIRECTION(xx,yy) \

workCell = &mWorkMap[xx][yy]; \

CHECK_COST_TO_START(xx,yy);

DIRECTION(x-1,y-1);

DIRECTION(x,y-1);

DIRECTION(x+1,y-1);

DIRECTION(x+1,y);

DIRECTION(x+1,y+1);

DIRECTION(x,y+1);

DIRECTION(x-1,y+1);

DIRECTION(x-1,y);

#undef DIRECTION

#undef CHECK_COST_TO_START

// The end result should be that cheapestToStart shows the cost

// of the cheapest move back to the start and cheapestMove shows

// which square to move to to get that.

// We need to store these values for the current square and also add in

// the cost of moving to the current square

mWorkMap[x][y].mCostToStart = cheapestToStart + MoveCost(x,y);

mWorkMap[x][y].mCheapestMove = cheapestMove;

}

// RescanCheapest scans through the map and adjusts the cheapest costs

// of squares where there is a cheaper route via a neighbouring square.

// It returns a count of the number of adjustments made.

// If this is zero the map is fully optimised. This function should be

// called repeatedly until this is the case.

int Underground::RescanCheapest()

{

int cellsAltered = 0;

// Note the 1 and -1 so we don't try to scan the walls

for( int y=1; y<mRows-1; ++y )

{

for( int x=1; x<mCols-1; ++x )

{

WorkingMapCell *workCell = &mWorkMap[x][y];

// See how the cost from our cell compares to the

// costs from neighbouring cells

WorkingMapCell *neighbourCell;

#define DIRECTION(xx,yy) \

neighbourCell = &mWorkMap[xx][yy]; \

if ( RescanCheapestCell(workCell, neighbourCell, \

x, y, xx, yy) ) \

++cellsAltered;

DIRECTION(x-1,y-1);

DIRECTION(x,y-1);

DIRECTION(x+1,y-1);

DIRECTION(x+1,y);

DIRECTION(x+1,y+1);

DIRECTION(x,y+1);

DIRECTION(x-1,y+1);

DIRECTION(x-1,y);

#undef DIRECTION

}

}

return cellsAltered;

}

// workCell is the cell we're considering.

// neighbourCell is the one we're checking. This will be called for each

// neighbour of workCell

// x,y is the coords of workCell

// xx,yy is the coord of neighbourCell

bool Underground::RescanCheapestCell( WorkingMapCell * workCell,

WorkingMapCell * neighbourCell,

int x, int y, int xx, int yy )

{

// Don't need to worry about unreachable cells

if ( neighbourCell->mVisited == false )

return false;

// If it costs less from our cell to the start than it would cost

// to get to our cell from the neighbour, then onto the start, then

// our cell is cheaper than going that way, so continue.

if ( neighbourCell->mCostToStart + MoveCost(x,y) >= workCell->mCostToStart )

return false;

// Otherwise we need to alter our cell to go via our neighbour

workCell->mCostToStart = MoveCost(x,y) + neighbourCell->mCostToStart;

workCell->mCheapestMove = Move(xx,yy);

return true;

}

// Calculates the cost of the route from B to A.

// This only should be called after RescanCheapest has been called

// enough times to find the solution.

int Underground::SolutionCost()

{

#ifdef _DEBUG

int safetyCount = 0;

#endif

Move currentMove = mEndPos;

int squaresDug = 0;

while(true)

{

// This loop traverses from currentMove to the preceding

// closest to the start move, until the start is reached.

// Note that we count moves rather than move costs.

squaresDug += MoveCost(currentMove.x, currentMove.y) ? 1 : 0;

currentMove = mWorkMap[currentMove.x][currentMove.y].mCheapestMove;

if ( currentMove.x == mStartPos.x && currentMove.y == mStartPos.y )

break;

assert( ++safetyCount < 10000 ); // In case of infinite loop

}

return squaresDug;

}

// Read the input map from stdin

void Underground::ReadInput()

{

cin >> mRows;

cin >> mCols;

// We're going to add a fake stone border to the map

// to save us having to worry about making paths that

// go off the edge of the map, so increase the map size

// to allow for it.

mRows += 2;

mCols += 2;

// Set the size of our map data multi_array.

mMapData.resize(boost::extents[mCols][mRows]);

for( int y=0; y < mRows; ++y )

{

if ( y == 0 || y == mRows-1 )

{

// Add our fake row of stones

for( int x=0; x < mCols; ++x )

mMapData[x][y] = '@';

}

else

{

// All other rows get read from the input

for( int x=0; x < mCols; ++x )

{

if ( x == 0 || x == mCols-1 )

{

// Add stones at start and end of row

mMapData[x][y] = '@';

}

else

{

char mapCell;

cin >> mapCell;

mMapData[x][y] = mapCell;

}

}

}

}

}

#ifdef _DEBUG

// Dump the map onto the console

// For debug purposes

void Underground::DumpMap() const

{

for( int y=0; y<mRows; ++y )

{

for( int x=0; x<mCols; ++x )

{

cout << mMapData[x][y];

}

cout << endl;

}

// Blank line to separate repeated map dumps

cout << endl;

}

#endif

// Assign costs to moving to the different types of square.

// This allows us to define the cheapest route.

int Underground::MoveCost(int x, int y) const

{

switch ( mMapData[x][y] )

{

case 'X':

return -1;

case 'A':

return 0;

case 'B':

return 1;

case '.':

return 0;

case '@':

return -1;

case '#':

return 1;

case '~':

// This is the count of all the #'s in puzzle to show that

// the mole would rather dig all of the earth than a single unit of castor oil.

return mRows * mCols;

};

return 0;

}