Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Jul 1st, 2008, 11:19 AM   #1
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,819
Rep Power: 5 Sane will become famous soon enough
SMAC #2 [06-08] - Trapped (Junior)

Attached to this post is the test data for trapped.


Trapped (Junior)

Junior was definitely harder this month, and quite a step up from beginner. But I thought an ASCII map question would be fun, so I hope it was a fun challenge for those who tried.

And as it turns out, a huge congratulations to everyone who submitted a solution to this problem. You all got perfect! I was not expecting that at all, so I was really pleased. Quite amazing, especially for a challenging problem like this.


Openloop's solution was like none I've ever seen in my years doing these things. It was quite creative, logical, and it works perfectly. He basically finds all of the horizontal and vertical components of the map, and then continuously merges them together to form all of the different rooms. However, I would not recommend doing something like this since it must have been a pain in the butt to code. Some huge eye-brow raising props goes to Openloop for this beast:

C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <algorithm> // For sort()
  5. #include <functional> // For greater<int>( )
  6.  
  7.  
  8. //using namespace std;
  9. #define WALL 'X'
  10. #define ROOM '.'
  11. #define HIGH_VALUE 99999
  12. #define MAX_NODES 100
  13. #define MAX_CONNS 100
  14. #define MAX_ROWS 10
  15. #define MAX_COLS 10
  16.  
  17. struct Node
  18. {
  19. int i, j;
  20. Node(){i = -1;j = -1;}
  21. Node(int x,int y){i = x; j = y;}
  22. void print(){ std::cout<<"("<<i<<","<<j<<"),";}
  23. bool operator==(const Node& rhs) const {return ((i==rhs.i)&&(j==rhs.j))?true:false;} //used by sort()
  24. bool operator<(const Node& rhs) const {return ((i<rhs.i)&&(j<rhs.j))?true:false;} //used by sort()
  25. };
  26.  
  27.  
  28. struct Path
  29. {
  30. int value;
  31. Node node;
  32. };
  33.  
  34. class Connection
  35. {
  36. private:
  37. int nodeCount;
  38. public:
  39. bool active;
  40. Node node[MAX_NODES];
  41.  
  42. Connection(){nodeCount = 0; active = true;}
  43.  
  44. bool operator<(const Connection& rhs)const {return ((nodeCount<rhs.nodeCount))?true:false;} //used by sort()
  45. bool operator>(const Connection& rhs) const {return ((nodeCount>rhs.nodeCount))?true:false;} //used by sort() and greater()
  46.  
  47. void appendNode(Node n)
  48. {
  49. for(int i = 0; i < nodeCount; i++)
  50. if (node[i] == n) return;
  51. node[nodeCount] = n;
  52. nodeCount++;
  53. }
  54.  
  55. static bool intersects(Connection &lhs, Connection &rhs)
  56. {
  57. for (int i = 0; i < lhs.nodeCount; i++)
  58. for (int j = 0; j < rhs.nodeCount; j++)
  59. if (lhs.node[i] == rhs.node[j]) return true;
  60. return false;
  61. }
  62.  
  63. static Connection attachConnections(Connection& lhs, Connection& rhs)
  64. {
  65. Connection result = lhs;
  66. for (int i = 0; i < rhs.nodeCount; i++)
  67. result.appendNode(rhs.node[i]);
  68. return result;
  69. }
  70.  
  71. int weigth(){return nodeCount;}
  72. void print(){for(int a = 0; a < weigth(); a++) node[a].print();}
  73.  
  74. };
  75.  
  76. int main()
  77. {
  78. int w, h;
  79. char floor[MAX_ROWS][MAX_COLS];
  80. Connection hConn[MAX_CONNS],
  81. vConn[MAX_CONNS];
  82.  
  83. std::ifstream fin("trapped.in");
  84. std::ofstream fout("trapped.out");
  85. if (!fin || !fout) {std::cout<<"IO ERROR!\n"; return 12;}
  86.  
  87. //Read floor dimentions
  88. fin>>w>>h;
  89.  
  90. //Load the floorplan
  91. for (int i = 0; i < h; i++){
  92. for (int j = 0; j < w; j++){
  93. fin>>floor[i][j];
  94. std::cout<<floor[i][j];
  95. }
  96. std::cout<<"\n";
  97. }
  98.  
  99.  
  100. int hConCount = -1,
  101. vConCount = -1;
  102. bool hActiveConn = false,
  103. vActiveConn = false;
  104. //traverse array horizontally & vertically to discover connections
  105. for (int i = 0; i < h; i++){
  106. for (int j = 0; j < w; j++){
  107. //horizontal
  108. if (floor[i][j] == ROOM){
  109. if (!hActiveConn){ //start new connection
  110. hConCount++;
  111. hActiveConn = true;
  112. }
  113. hConn[hConCount].appendNode(Node(i,j));
  114. }else{ //disconnect
  115. hActiveConn = false;
  116. }
  117. //vertical
  118. if (floor[j][i] == ROOM){
  119. if (!vActiveConn){ //start new connection
  120. vConCount++;
  121. vActiveConn = true;
  122. }
  123. vConn[vConCount].appendNode(Node(j,i)); //add the room coordinates to this connection
  124. }else{ //disconnect
  125. vActiveConn = false;
  126. }
  127.  
  128. }
  129. hActiveConn = false; //end of row, close connection
  130. vActiveConn = false; //end of column, close connection
  131. }
  132. hConCount++;
  133. vConCount++;
  134.  
  135.  
  136. //intersect horizontal and vertical connections into the iConn array to build the rooms
  137. std::sort(hConn, hConn + hConCount, std::greater<Connection>());
  138. std::sort(vConn, vConn + vConCount, std::greater<Connection>());
  139. int iConCount = 0;
  140. Connection iConn[100];
  141. for(int m = 0; m < hConCount; m++)
  142. for(int n = 0; n < vConCount; n++)
  143. if (Connection::intersects(hConn[m],vConn[n]))
  144. iConn[iConCount++] = Connection::attachConnections(hConn[m],vConn[n]);
  145.  
  146. //Even though we intersected the connection, there is a possibility that two or more connection might still intersect.
  147. //Keep looping and intersecting iConn connections with each other until no more intersections are found.
  148. std::sort(iConn, iConn + iConCount, std::greater<Connection>());
  149. bool intersectFound = true;
  150. while (intersectFound)
  151. {
  152. intersectFound = false;
  153. for(int i = 0; i < iConCount; i++){
  154. for(int j = i+1; j < iConCount && iConn[i].active; j++){
  155. if (iConn[i].active && iConn[j].active && Connection::intersects(iConn[i],iConn[j]))
  156. {
  157. iConn[i] = Connection::attachConnections(iConn[i],iConn[j]);
  158. iConn[j].active = false;
  159. intersectFound = true;
  160. }
  161. }
  162. }
  163. }
  164.  
  165. //Now that we have the room configuration figured out(in the form of connections),
  166. //we can go to figure out the size of the smallest room
  167. //Also print the room configuration
  168. int roomAir = HIGH_VALUE;
  169. int minRoomAir = HIGH_VALUE;
  170. std::cout<<"Room configuration(s) follow:\n";
  171. int roomNum = 1;
  172. for(int i = 0; i < iConCount; i++)
  173. {
  174. if (iConn[i].active)
  175. {
  176. std::cout<<"Room #"<<roomNum++<<": ";
  177. iConn[i].print();
  178. std::cout<<"\n\n";
  179. roomAir = iConn[i].weigth() * 5;
  180. minRoomAir = std::min(minRoomAir,roomAir);
  181. }
  182. }
  183.  
  184. fout<<(minRoomAir==HIGH_VALUE?0:minRoomAir)<<"\n";
  185.  
  186. fin.close();
  187. fout.close();
  188. std::cout<<"Press ENTER To Exit\n";
  189. std::getchar();
  190.  
  191. return 0;
  192. }


Titanium Decoy must have cheated, because he copied my code almost exactly.

Andrew, our third perfect, did things a bit differently with his use of globals, but still got the job done.

Jimbo, the fourth and final perfect, demonstrated his solid understanding of graph theory by using a Breadth-First Search (BFS) to fill each room. The BFS is no faster than a DFS here, but it certainly looks cool.


Knowing how and when to do a BFS may or may not PROVE TO BE USEFUL for one of July's challenges!!


C# Syntax (Toggle Plain Text)
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.IO;
  6.  
  7. namespace SMAC2_Junior
  8. {
  9. class Program
  10. {
  11. /// strategy:
  12. /// create a matrix to represent the floor plan
  13. /// for each open space, do a BFS on it's surrounding open spaces to get the size of the room
  14. /// when finished with the room, save the result if it's the smallest encountered yet
  15. /// if an unused space still exists, repeat from the for loop
  16. static void Main(string[] args)
  17. {
  18. StreamReader swapIn = null;
  19. StreamWriter swapOut = null;
  20. try
  21. {
  22. swapIn = new StreamReader("swap.in");
  23. swapOut = new StreamWriter("swap.out");
  24. string buffer = swapIn.ReadLine();
  25. int w, h;
  26. string[] nums = buffer.Split(" ".ToCharArray());
  27. w = int.Parse(nums[0]);
  28. h = int.Parse(nums[1]);
  29.  
  30. char[][] map = new char[h][];
  31. // read in map
  32. for (int i = 0; i < h; i++)
  33. {
  34. string line = swapIn.ReadLine();
  35. if (line.Length != w)
  36. {
  37. throw new InvalidDataException(String.Format("Line width is incorrect. Expected width: {0}; Actual string: {1}", w, line));
  38. }
  39. map[i] = new char[w];
  40. line.ToCharArray().CopyTo(map[i], 0);
  41.  
  42. }
  43.  
  44. #if DEBUG
  45. Console.WriteLine("Read map as: ");
  46. for (int i = 0; i < h; i++)
  47. {
  48. Console.WriteLine(map[i]);
  49. }
  50. #endif
  51.  
  52. int smallestRoom = int.MaxValue;
  53. // now check them all
  54. for (int i = 0; i < h; i++)
  55. {
  56. for (int j = 0; j < w; j++)
  57. {
  58. if (map[i][j] == RoomState.Unchecked)
  59. {
  60. int size = getRoomSize(map, i, j);
  61. #if DEBUG
  62. Console.WriteLine("Found room of size {0}", size);
  63. #endif
  64. if (size < smallestRoom)
  65. {
  66. smallestRoom = size;
  67. }
  68. }
  69. }
  70. }
  71.  
  72.  
  73. // output result * 5
  74. #if DEBUG
  75. Console.WriteLine(smallestRoom * 5);
  76. #endif
  77. swapOut.WriteLine(smallestRoom * 5);
  78. }
  79. catch (Exception e)
  80. {
  81. Console.WriteLine(String.Format("Error encountered, aborting. Error: [{0}]", e.ToString()));
  82. }
  83. finally
  84. {
  85. if (swapIn != null)
  86. {
  87. swapIn.Close();
  88. swapIn = null;
  89. }
  90. if (swapOut != null)
  91. {
  92. swapOut.Close();
  93. swapOut = null;
  94. }
  95. }
  96. }
  97.  
  98. private static int getRoomSize(char[][] map, int y, int x)
  99. {
  100. if (map[y][x] != RoomState.Unchecked)
  101. {
  102. return int.MaxValue;
  103. }
  104. HashSet<CoordinatePair> toCheck = new HashSet<CoordinatePair>();
  105. toCheck.Add(new CoordinatePair(x, y));
  106. int size = 0;
  107. CoordinatePair current;
  108. while (toCheck.Count > 0)
  109. {
  110. current = toCheck.First();
  111. toCheck.Remove(current);
  112. if (map[current.Y][current.X] != RoomState.Unchecked)
  113. {
  114. continue;
  115. }
  116. // update for this square
  117. size++;
  118. map[current.Y][current.X] = RoomState.Checked;
  119.  
  120. CoordinatePair temp;
  121. temp = new CoordinatePair(current.X, current.Y - 1);
  122. if (temp.Y > 0 && map[temp.Y][temp.X] == RoomState.Unchecked)
  123. toCheck.Add(temp);
  124. // check down
  125. temp = new CoordinatePair(current.X, current.Y + 1);
  126. if (y < map.Length - 1 && map[temp.Y][temp.X] == RoomState.Unchecked)
  127. toCheck.Add(temp);
  128. temp = new CoordinatePair(current.X - 1, current.Y);
  129. if (temp.X > 0 && map[temp.Y][temp.X] == RoomState.Unchecked)
  130. toCheck.Add(temp);
  131. temp = new CoordinatePair(current.X + 1, current.Y);
  132. if (temp.X < map[temp.Y].Length && map[temp.Y][temp.X] == RoomState.Unchecked)
  133. toCheck.Add(temp);
  134. }
  135. return size;
  136. }
  137. static class RoomState
  138. {
  139. public const char Wall = 'X';
  140. public const char Unchecked = '.';
  141. public const char Checked = 'O';
  142. }
  143.  
  144. class CoordinatePair
  145. {
  146. public int X;
  147. public int Y;
  148.  
  149. public CoordinatePair(int x, int y)
  150. {
  151. X = x;
  152. Y = y;
  153. }
  154. }
  155. }
  156. }


So now, on to the easy solution.

The key here is to not worry about how many rooms there are, or the shape of each individual room.

All you really need is a "fill" function that accepts an (x,y) co-ordinate and returns the size of the room at that point.

Then repeatedly call the fill function for every possible co-ordinate, and output the smallest non-zero size.



Writing the fill function is the hard part, since rooms can span and branch out in all directions from a particular point.

For example, if you were to start the fill function at "@", the room branches off into three different paths which are all part of the same room.

XXXXXXXX
XXXX.XXX
XXXX.XXX
X...@XXX
XXXX.XXX
XXXX.XXX
XXXXXXXX

This idea of "branching" makes it suitable to use recursion.

Recursion will automatically take care of the way a room can branch out into many different directions.

I won't bother proving this fact. Explaining recursion is even more difficult than learning it. But if you're interested, I'm sure someone here is willing to help you understand the logic.

A rough version of our function might look something like this:

void fill(int x, int y) {
    if(x<0||y<0||x>=w||y>=h) return;
    if(grid[y][x] == 'X') return;
    fill(x+1,y);
    fill(x,y+1);
    fill(x-1,y);
    fill(x,y-1);
}

But there's quite a big problem here, and its name is Infinite Recursion. Nothing's stopping fill from recursing back to where it was initially, which would result in everything repeating over and over again until the sun explodes.

The trick is to replace the space with a wall (X) once it's been visited. Consequently, we only "look" at each space once. Since we only need to count each space once, that's perfect. Again, the proof behind this takes a solid understanding of recursion.

There's only one more thing that needs taking care of, and that's the actual counting of spaces in the room. By recursive definition, the number of open spaces in a room is 1 + the number of open spaces in all of its adjacent neighbours.

Combine all of that together, and you've got your fill function:

int fill(int x, int y) {
    if(x<0||y<0||x>=w||y>=h) return 0;
    if(grid[y][x] == 'X') return 0;
    grid[y][x] = 'X';
    return 1 + fill(x+1,y) + fill(x,y+1) + fill(x-1,y) + fill(x,y-1);
}


And here's the solution:

C++ Syntax (Toggle Plain Text)
  1. #include <stdio.h>
  2. #define MAX 11
  3.  
  4. char grid[MAX][MAX];
  5. int w, h;
  6.  
  7. int fill(int x, int y) {
  8. if(x<0||y<0||x>=w||y>=h) return 0;
  9. if(grid[y][x] == 'X') return 0;
  10. grid[y][x] = 'X';
  11. return 1 + fill(x+1,y) + fill(x,y+1) + fill(x-1,y) + fill(x,y-1);
  12. }
  13.  
  14. int main() {
  15. int vol=MAX*MAX;
  16.  
  17. freopen("trapped.in", "rt", stdin);
  18. freopen("trapped.out", "wt", stdout);
  19.  
  20. scanf("%d %d", &w, &h);
  21. for(int y=0; y<h; y++) scanf("%s", grid[y]);
  22.  
  23. for(int x=0; x<w; x++) for(int y=0; y<h; y++) if(int r=fill(x,y)) vol<?=r;
  24. printf("%d\n", vol*5);
  25.  
  26. return 0;
  27. }
Attached Files
File Type: zip trapped.zip (2.6 KB, 1 views)
Sane is offline   Reply With Quote
Reply

Bookmarks

Tags
smac junior solutions

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
SMAC #2 [06-08] - Swapping Stories (Beginner) Sane Software Design and Algorithms 1 Jul 1st, 2008 1:35 PM
SMAC #1 [05-08] - Mobile (Beginner) and "n Reach k" (Junior) Sane Software Design and Algorithms 2 Jun 3rd, 2008 8:10 AM
SMAC #1 [05-08] - Results Sane Software Design and Algorithms 6 Jun 2nd, 2008 4:56 PM
SMAC #1 [05-08] - Ranged Reach (Senior) Sane Software Design and Algorithms 0 Jun 2nd, 2008 4:21 PM
SMAC #1 [05-08] - Hurtles (Senior) Sane Software Design and Algorithms 0 Jun 1st, 2008 3:59 PM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 6:54 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC