Knights and Mazes Puzzle Followup
There were a few less takers for this one than the others, it seems the complexity of the problem may have been a little high for an Internet competition.
None the less, let's plow through what a good answer is.
First, the point of this one was to make people work around programming restrictions found in most languages. Specifically, how do you keep track of where you've been when you have two 32-bit position values? Granted, you can't have a full 2^32x2^32 board as this is more than you can fit in 32-bit memory, but you can have a board that breaches 2^16, so although you won't use all of the bits, you need to use a storage method that can store both positions.
If you're lucky, you can just use something someone else gave you to combine the values into one place, specifically __int64 can be used in a set to store both values. Or the SDL comes with make_pair. Done and done.
However not all languages support this, so how do you do it? Almost all collection frameworks come with a way to write your own "comparer". In C#, it can look like the following:
public class PositionComparer : IComparer
{
int IComparer.Compare(Object o1, Object o2)
{
Position p1 = o1 as Position;
Position p2 = o2 as Position;
// If x's are the same, compare y's
if (p1.x == p2.x)
return p1.y - p2.y;
else
return p1.x - p2.x;
}
}
Now we have a way to compare a class holding any kind of data. We can throw it into a set collection and we'll have a way of determing which positions we've already visited.
So, other than storage what else was tricky about this problem? Ambiguous knight movements. Chess knights have two was of getting to any point immediately available to them. For example, the knight can move left one and up two or up two and left one. One way may be blocked where the other is not. However, once we've gotten there, there's no need to try the other method. So, this means you need to have a set of unvisited spots and then try both ways when trying to visit that spot. It would memory be inefficient to store both moves in a set.
Without further anticipation building, here is the answer I came up with (I've left out the comparer above)
struct Position
{
int x, y;
Position(int x, int y);
};
int move[8][2] = {{1,2},{2,1},{-1,2},{-2,1},
{1,-2},{2,-1},{-1,-2},{-2,-1}};
bool RunTheMaze()
{
Set<Position,PositionComparer> visitedSpots;
Set<Position,PositionComparer> toVisit;
// Add our start
toVisit.Add( Position( 0, 0 ) );
while( toVisit.Count() > 0 )
{
Position currentPosition = toVisit.GetFirst();
toVisit.RemoveFirst();
// Add all places to visit from here
for( int i = 0; i < 8; i++ )
{
if( CheckValid( currentPosition, move[i] ) )
{
Position newPosition = currentPosition;
newPosition.x += move[i].x;
newPosition.y += move[i].y;
if( IsExit( newPosition.x, newPosition.y ) )
return true; // Yay!
toVisit.Add( newPosition );
}
}
}
// Can't find the exit
return false;
}
bool CheckValid( Position pos, int* theMove )
{
// Try moving x first
Position copyPos = pos;
if( !Run( copyPos, theMove[0], true ) )
return false;
if( !Run( copyPos, theMove[1], false ) )
return false;
// Now try moving y first
copyPos = pos;
if( !Run( copyPos, theMove[1], false ) )
return false;
if( !Run( copyPos, theMove[0], true ) )
return false;
return true;
}
bool Run( Position& pos, int val, bool fX )
{
do
{
if( fX )
pos.x += val;
else
pos.y += val;
if( IsWall( pos.x, pos.y ) )
return false;
val += ( val < 0 ? 1 : -1 );
}
while( val != 0 );
return true;
}
Few! Hopefully our knight enjoys his freedom from the maze.
Multi-Threading
Some people brought up that this could be a good candidate for mutlithreading. Indeed you're right, with the advent of multi-core CPUs, making applications multi-threaded is becoming a priority. So how would we multi-thread this problem?
Well, working your way through a maze with multi-threads can be tricky. You don't know how big the maze is and you can't start just anywhere, you have to start at the start. Otherwise you could end up searching a part of the maze that is completely sealed off. Maybe there's an exit in there, but since you can't get to it from the start, it's not accessible. Returning true here could be the wrong answer. Whoops.
What about having a pool of threads, and pulling one to process a potential vector to visit? If we make the "visited" set a thread safe resource, then this would allow us to divy up the work. This would be a good solution if calls like IsWall and IsExit are slow. Otherwise, determining if a knight can get to a certain position is fairly simple and we may end up thrashing around accessing the visited set and losing more time than we save.
To address this problem, we could segment the maze up into "spaces". 0x0 to 31x31 could be one thread and 0x32 to 31x63 could be another and so on. If the "toVisit" node falls into another threads space we let it handle it. The code could look something like this:
KnightRunner* runners[5];
// Global visited set
ThreadSafeSet<Position,PositionComparer> visited;
struct KnightRunner
{
void Run()
{
while(true)
{
if( toVisit.Count() > 0 )
{
// generate next set of positions
//...
AddNewToVisit( newPosition );
}
}
}
static void AddNewToVisit( Position pos )
{
runners[abs(pos.x%5)]->toVisit.Add( pos );
}
ThreadSafeSet<Position,PositionComparer> toVisit;
bool fFoundExit = false;
}
bool RunTheMaze()
{
// Start up all 5 KnightRunners, seed one with (0,0)
//...
while( true )
{
// Anyone found the exit yet?
for( int i = 0; i < 5; i++ )
if( runners[i]->fFoundExit )
return true;
// Anyone found the exit yet?
PauseAllKnightThreads();
bool fAllEmpty = true;
for( int i = 0; i < 5; i++ )
fAllEmpty &= runners[i]->toVisit.Count() > 0;
// Nothing left
if( fAllEmpty )
return false;
UnPauseAllKnightThreads();
Sleep( 1000 );
}
}
We spawn a bunch of threads and each one owns a vertical swatch of the maze. When there are new positions to add, they add them to each other. If all threads have no places to go, we've run out of room.
Some things I'll let you think about:
- What is the potential for dead lock here?
- How can we make AddNewToVisit better?
Best Entry
As 'shoaxp' was the only one to submit a complete solution, he gets the win for this week. Congrats!
