2016-CCOQR-Q2 Through A Maze Darkly - Brute Force

# 2016-CCOQR-Q2 Through A Maze Darkly - Brute Force Solution

## Algorithm

The algorithm is the most basic approach - start in each room and walk through each door and keeping track of the number of hallways travled following the path until you return to the room. Then compute the maximum path for that room.

## Optimization

The one optimization that can be applied to the brute force approach is precomputing the next door. The results of that optimization are presented in the results.

## Testing Results

Task# Test# Rooms Questions Total Distance Simple Execution Time Optimized Execution Time
1 1 100 100 19,800 0.063 0.042
1 2 100 100 19,800 0.053 0.039
1 3 100 100 19,800 0.038 0.04
1 4 2 2 4 0.037 0.037
1 5 65 43 5,850 0.038 0.039
1 6 100 100 620 0.037 0.038
1 7 100 100 2,008 0.036 0.04
1 8 100 100 7,776 0.038 0.04
1 9 100 100 13,652 0.039 0.038
1 10 15 15 2,964 0.039 0.037
2 11 100,000 1 199,998 0.222 0.235
2 12 100,000 1 199,998 2.477 0.37
2 13 100,000 1 199,998 0.223 0.228
2 14 100,000 1 2 0.182 0.18
2 15 100,000 1 2 0.191 0.195
2 16 100,000 1 179,898 0.253 0.261
2 17 100,000 1 294,035 0.392 0.372
2 18 635 1 399,350 0.353 0.321
2 19 10,000 1 396198 0.295 0.306
3 20 100,000 100,000 19,999,800,000 9 Minutes 9 Minutes
3 21 100,000 100,000 19,999,800,000 62 Hours (est) 5 Minutes
3 22 100,000 100,000 19,999,800,000 6 Minutes 6 Minutes
3 23 100,000 100,000 19,999,800,000 6 Minutes 6 Minutes
3 24 100,000 100,000 597,452 0.982 0.548
3 25 100,000 100,000 26,746,872,867 15 Minutes 18 Minutes
3 26 635 635 253,642,605 62 8.375
3 27 4,500 4,500 1,791,483,017 85.5 67.189
3 28 100,000 100,000 32,236,609,882 18 Minutes 21 Minutes
3 29 100,000 100,000 11,256,017,057 4 Minutes 4 Minutes

## Simple Implementation

``````#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int   totalRooms;
int*  roomDoorCounts;
int** roomDoors;

//---------------------------------------------------------------------------
// Input
//---------------------------------------------------------------------------

{
std::cin >> totalRooms;
roomDoorCounts = new int[totalRooms];
roomDoors = new int*[totalRooms];

for (int room = 0; room < totalRooms; room++)
{
std::cin >> roomDoorCounts[room];
roomDoors[room] = new int[roomDoorCounts[room]];

for (int door = 0; door < roomDoorCounts[room]; door++)
{
int next_room;
std::cin >> next_room;
roomDoors[room][door] = next_room - 1; // 0-based index
}
}
}

//---------------------------------------------------------------------------
// Next Door Precomputation
//---------------------------------------------------------------------------

int get_next_door(int currentDoor, int roomDoorCount)
{
int nextDoor;
if (currentDoor != 0)
nextDoor = currentDoor - 1;
else
nextDoor = roomDoorCount - 1;
return nextDoor;
}

int find_door_in_room(int currentRoom, int roomDoorCount, int nextRoom)
{
for (int door = 0; door < roomDoorCount; door++)
{
if (roomDoors[currentRoom][door] == nextRoom)
return door;
}
abort();
}

//---------------------------------------------------------------------------
// Solver
//---------------------------------------------------------------------------

int compute_door_cost(int startingRoom, int startingDoor)
{
int currentRoom = startingRoom;
int currentDoor = startingDoor;
int cost = 0;
do
{
// Get the next Room & index
int nextRoom = roomDoors[currentRoom][currentDoor];
int nextRoomDoorCount = roomDoorCounts[nextRoom];
int index = find_door_in_room(nextRoom, nextRoomDoorCount, currentRoom);
int nextDoor = get_next_door(index, nextRoomDoorCount);

// Increase Cost
cost++;

// Go to next room
currentRoom = nextRoom;
currentDoor = nextDoor;
} while (currentRoom != startingRoom);
return cost;
}

int compute_room_max(int room)
{
int maxCost = 0;
int roomDoorCount = roomDoorCounts[room];
for (int door = 0; door < roomDoorCount; door++)
maxCost = std::max(maxCost, compute_door_cost(room, door));
return maxCost;
}

//---------------------------------------------------------------------------
// Output
//---------------------------------------------------------------------------

{
int totalQuestions;
std::cin >> totalQuestions;
for (int q = 0; q < totalQuestions; q++)
{
int room;
std::cin >> room;
std::cout << compute_room_max(room - 1) << std::endl;
}
}

int main()
{
return 0;
}
``````

## Optimized Implementation

The only optimization involved is to pre-compute the next door so the navigation along the paths is fast.

``````#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>

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

int get_next_int()
{
int n;
scanf("%d", &n);
return n;
}

//---------------------------------------------------------------------------
// Room Storage
//---------------------------------------------------------------------------

typedef struct
{
int nextRoom;
int nextDoor;
bool valid;
} RoomDoor;

typedef struct
{
int doorCount;
RoomDoor* doors;
std::unordered_map<int, int> doorMap;
} Room;

//---------------------------------------------------------------------------
// Input
//---------------------------------------------------------------------------
int   totalRooms;
Room*  rooms;
{
totalRooms = get_next_int();
rooms = new Room[totalRooms];
for (int room = 0; room < totalRooms; room++)
{
int doorCount = get_next_int();
rooms[room].doorCount = doorCount;
rooms[room].doors = new RoomDoor[doorCount];
for (int door = 0; door < doorCount; door++)
{
int nextRoom = get_next_int() - 1; // 0-Based Index
rooms[room].doors[door].nextRoom = nextRoom;
rooms[room].doors[door].valid = true;
rooms[nextRoom].doorMap[room] = door; // Store the reverse Lookup to the door
}
}
}

//---------------------------------------------------------------------------
// Next Door Precomputation
//---------------------------------------------------------------------------
void precompute_next_door()
{
for (int room = 0; room < totalRooms; room++)
{
int roomDoorCount = rooms[room].doorCount;
for (int door = 0; door < roomDoorCount; door++)
{
int nextRoom = rooms[room].doors[door].nextRoom;
int nextDoor = rooms[room].doorMap[nextRoom] - 1;
if (nextDoor == -1)
nextDoor = rooms[nextRoom].doorCount - 1;
rooms[room].doors[door].nextDoor = nextDoor;
}
}
}

//---------------------------------------------------------------------------
// Solver
//---------------------------------------------------------------------------

int compute_door_cost(int startingRoom, int startingDoor)
{
int currentRoom = startingRoom;
int currentDoor = startingDoor;
int cost = 0;
do
{
// Get the next Room & index
int nextRoom = rooms[currentRoom].doors[currentDoor].nextRoom;
int nextDoor = rooms[currentRoom].doors[currentDoor].nextDoor;

// Increase Cost
cost++;

// Go to next room
currentRoom = nextRoom;
currentDoor = nextDoor;

} while (currentRoom != startingRoom);

return cost;
}

int compute_room_max(int room)
{
int maxCost = 0;
int roomDoorCount = rooms[room].doorCount;
for (int door = 0; door < roomDoorCount; door++)
maxCost = std::max(maxCost, compute_door_cost(room, door));
return maxCost;
}

//---------------------------------------------------------------------------
// Output
//---------------------------------------------------------------------------

{
int totalQuestions = get_next_int();
for (int q = 0; q < totalQuestions; q++)
{
int question = get_next_int() - 1; // 0 Based Index
int cost = compute_room_max(question);
printf("%d\n", cost);
}
}

int main()
{