Programming Forums
User Name Password Register
 

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

Reply
 
Thread Tools Display Modes
Old Oct 8th, 2008, 10:57 AM   #1
Sane
Banned
 
Sane's Avatar
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 2,101
Rep Power: 6 Sane will become famous soon enough
Send a message via MSN to Sane
SMAC #4 [09-08] - Digging For Gold (Junior)
Attached to this post is the test data for Digging For Gold.


Digging For Gold (Junior)

This is a problem in Graph Theory very similar to Trapped (Junior) from SMAC #2.

It requires that you implement a standard depth-first search. Since the cube is limited to 10 x 10 x 10, efficiency is of low priority for this question. I will proceed with the most efficient solution. But even exponential solutions should still get full points unless over-done.



Suppose you have some function dig(i,j,k) which digs to square [i,j,k] (where i=level, j=x, and k=y), from some adjacent square (we really don't care what square it came from).

The function will return how much gold it can retrieve from here on, in as many digs as needed (since we always have the option to bring the rig back up to the top and get to this same square again).


If [i,j,k] is off the cube, then we can find no gold from here. So return 0.
If [i,j,k] is a rock, then we shouldn't be here. So return 0.
If [i,j,k] is a piece of gold, then add 1 to a local counter and remove the gold (alternatively, turn it into a rock-- see below end note).

Since the dig(i,j,k) function will return the amount of gold in as many digs as needed from square [i,j,k], it's pointless to call dig(i,j,k) more than once for the same [i,j,k] triple. Therefore, remember that you've visited [i,j,k]. Alternatively, turn [i,j,k] into a rock.

To see how much gold we can get from this point (in as many digs as necessary), by definition of the dig function, it is:

(Toggle Plain Text) 
(All the gold we can retrieve by repeating this on one square down) +
(All the gold we can retrieve by repeating this on each of the 4 side squares)

(Toggle Plain Text) 
dig(i+1,j,k) + 
dig(i,j-1,k) + dig(i,j,k-1) + dig(i,j+1,k) + dig(i,j,k+1)

So the total answer for dig(i,j,k) is the above plus 1 or 0 depending on the local counter (whether or not [i,j,k] is gold).



Now that we have a dig function, the problem is pretty much complete.

You are allowed to dig an infinite number of times from any of the ground-level squares. Therefore, call dig(0,j,k) for all j and for all k : {0 <= j,k < n} and sum the total.

This will work as long as we remember to remove all the gold we find during each dig. And this will work in polynomial time (O(N^3) to be precise) if we never process the same dig(i,j,k) request more than once.



Arla's perfect in Java. Congrats!

Java Syntax (Toggle Plain Text) 
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.FileReader;
  4. import java.io.FileWriter;
  5. import java.util.ArrayList;
  6. import java.util.List;
  7.  
  8. public class goldDigging {
  9. //	public static boolean isNotWall(int level, int row, int column, char[][][] goldCube)
  10. //	{
  11. //		if(level<0||row<0||column<0||
  12. //				level>=goldCube.length||row>=goldCube.length||column>=goldCube.length)
  13. //			return false;
  14. //		if(goldCube[level][row][column] == 'X') return false;
  15. //		goldCube[level][row][column]= 'X';
  16. //		
  17. //		return true;
  18. //	}
  19. 	public static ArrayList<String> isNotWall(int level, int row, int column, char[][][] goldCube)
  20. 	{
  21. 		if(level<0||row<0||column<0||
  22. 				level>=goldCube.length||row>=goldCube.length||column>=goldCube.length)
  23. 			return null;
  24. 		if(goldCube[level][row][column] == 'X') return null;
  25. 		goldCube[level][row][column]= 'X';
  26. 		//Increase and decrease row/column to see which we can get to.
  27. 		ArrayList<String> plusRowGetTo = isNotWall(level,row+1,column,goldCube);
  28. 		ArrayList<String> plusColumnGetTo = isNotWall(level,row,column+1,goldCube);
  29. 		ArrayList<String> minusRowGetTo = isNotWall(level,row-1,column,goldCube);
  30. 		ArrayList<String> minusColumnGetTo = isNotWall(level,row,column-1,goldCube);
  31. 		//Only need to have plusLevelGetTo, since you can never dig up
  32. 		ArrayList<String> plusLevelGetTo = isNotWall(level+1,row,column,goldCube);
  33. 		ArrayList<String> output = new ArrayList<String>();
  34. 		if(plusRowGetTo!=null)
  35. 			for(String s:plusRowGetTo)
  36. 				if(!output.contains(s))
  37. 					output.add(s);
  38. 		if(minusRowGetTo!=null)
  39. 			for(String s:minusRowGetTo)
  40. 				if(!output.contains(s))
  41. 					output.add(s);
  42. 		if(plusColumnGetTo!=null)
  43. 			for(String s:plusColumnGetTo)
  44. 				if(!output.contains(s))
  45. 					output.add(s);
  46. 		if(minusColumnGetTo!=null)
  47. 			for(String s:minusColumnGetTo)
  48. 				if(!output.contains(s))
  49. 					output.add(s);
  50. 		if(plusLevelGetTo!=null)
  51. 			for(String s:plusLevelGetTo)
  52. 				if(!output.contains(s))
  53. 					output.add(s);
  54. 		output.add(Integer.toString(level*100+row*10+column));
  55. 		return output;
  56. 	}
  57.  
  58. 	public static int goldDigger(char[][][] goldCube)
  59. 	{
  60. 		int goldCount = 0;
  61. 		List<String> accessible = new ArrayList<String>();
  62. 		List<String> goldpositions = new ArrayList<String>();
  63. 		int level=0,row=0,column=0;
  64. 		//Step one, find all gold
  65. 		for (level=0;level<goldCube.length;level++)
  66. 			for (row=0;row<goldCube.length;row++)
  67. 				for (column=0;column<goldCube.length;column++)
  68. 					if (goldCube[level][row][column]=='*')
  69. 						goldpositions.add(Integer.toString(level*100+row*10+column));
  70. 		//Step two, find all open spaces on the 1st level
  71. 		if (goldpositions!=null)
  72. 		{
  73. 			level =0;
  74. 			List<String> newAccessible = new ArrayList<String>();
  75. 			for (row=0;row<goldCube.length;row++)
  76. 				for (column=0;column<goldCube.length;column++)
  77. 					if(!accessible.contains(Integer.toString(level*100+row*10+column)))
  78. 					{
  79. 						newAccessible = isNotWall(level,row,column,goldCube);
  80. 						if (newAccessible!=null)
  81. 							for(String s:newAccessible)
  82. 								if(!accessible.contains(s))
  83. 									accessible.add(s);
  84. 					}
  85. 			//Now we have a complete list of all accessible places within the cube, simply compare
  86. 			for (String gold:goldpositions)
  87. 				if(accessible.contains(gold))
  88. 					goldCount++;
  89. 		}	
  90. 		return goldCount;
  91. 	}
  92. 	public static void main(String[] args)
  93. 	{
  94. 		try 
  95. 		{
  96. 			int n=0;
  97. 			int row;
  98. 			String inputText;
  99. 			BufferedReader in = new BufferedReader(new FileReader("gold.in"));
  100. 			n = Integer.parseInt(in.readLine());
  101. 			char[][][]goldCube = new char[n][n][n];
  102. 			//Read all the values for the goldCubes
  103. 			//format for goldcube is [Row][Column][Level]
  104. 			in.readLine();
  105. 			for(int level=0;level<n;level++)
  106. 			{
  107. 				//Read the blank line
  108. 				row=0;
  109. 				//Read the next n lines for level 0
  110. 				while (((inputText = in.readLine()) != null) && (row < n))
  111. 				{
  112. 					for(int column=0;column<n;column++)
  113. 						goldCube[level][row][column] = inputText.toCharArray()[column];
  114. 					row++;
  115. 				}
  116. 			}	
  117. 			//Now close the input since we are done with it
  118. 			in.close();
  119. 			BufferedWriter out = new BufferedWriter(new FileWriter("gold.out"));
  120. 			String s = Integer.toString(goldDigger(goldCube));
  121. 			out.write(s);
  122. 			out.write("\n");
  123. //			out.newLine();
  124. 			out.close();
  125. 		}
  126. 		catch (Exception e)
  127. 		{
  128. 			e.printStackTrace();
  129. 		}
  130. 	}
  131. }


Here is a courtesy submission from The Dark. It scores 100, but is not included in the results. It is here for sake of comparison and to learn from.

Thanks!

C++ Syntax (Toggle Plain Text) 
  1. // SMAC_4_2.cpp : SMAC #4 Entry 2.
  2. // By: The Dark
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. class Position
  10. {
  11. public:
  12.    Position(int level, int x, int y) : level(level), x(x), y(y) {}
  13.    Position() : level(0), x(0), y(0) {}
  14.    int level;
  15.    int x;
  16.    int y;
  17. };
  18.  
  19. class Ground
  20. {
  21. public:
  22.    Ground() { type = '.'; reachable = false;}
  23.    char type;
  24.    bool reachable;
  25. };
  26.  
  27. int size;
  28. Ground ***ground;
  29. int goldCount = 0;
  30. queue<Position> nodesToVisit;
  31.  
  32. void checkAndVisit(int level, int x, int y)
  33. {
  34.    if (x < 0 || x >= size || y < 0 || y >= size)
  35.       return;
  36.  
  37.    Ground &thisNode = ground[level][x][y];
  38.    if (thisNode.type != 'X')
  39.    {
  40.       if (!thisNode.reachable)
  41.       {
  42.          thisNode.reachable = true;
  43.          nodesToVisit.push(Position(level, x, y));
  44.          if (thisNode.type == '*')
  45.             goldCount++;
  46.       }
  47.    }
  48. }
  49.  
  50. int main(int argc, char *argv[])
  51. {
  52.    freopen("gold.in", "rt", stdin);
  53.    freopen("gold.out", "wt", stdout);
  54.    scanf("%d\n\n", &size);
  55.  
  56.    ground = new Ground **[size];
  57.    for (int level = 0; level < size; level++)
  58.    {
  59.       ground[level] = new Ground *[size];
  60.       for (int x = 0; x < size; x++)
  61.       {
  62.          ground[level][x] = new Ground[size];
  63.          for (int y = 0; y < size; y++)
  64.          {
  65.             scanf("%c", &ground[level][x][y].type);
  66.          }
  67.          scanf("\n");
  68.       }
  69.    }
  70.  
  71.    // Top level, all reachable if not rock
  72.    for (int x = 0; x < size; x++)
  73.    {
  74.       for (int y = 0; y < size; y++)
  75.       {
  76.          Ground &thisNode = ground[0][x][y];
  77.          if (thisNode.type != 'X')
  78.          {
  79.             thisNode.reachable = true;
  80.             nodesToVisit.push(Position(0, x, y));
  81.             if (thisNode.type == '*')
  82.                goldCount++;
  83.          }
  84.       }
  85.    }
  86.  
  87.    while (!nodesToVisit.empty())
  88.    {
  89.       Position pos = nodesToVisit.front();
  90.       nodesToVisit.pop();
  91.  
  92.       checkAndVisit(pos.level, pos.x-1, pos.y);
  93.       checkAndVisit(pos.level, pos.x, pos.y-1);
  94.       checkAndVisit(pos.level, pos.x, pos.y+1);
  95.       checkAndVisit(pos.level, pos.x+1, pos.y);
  96.       if (pos.level < size - 1)
  97.          checkAndVisit(pos.level+1, pos.x, pos.y);
  98.    }
  99.  
  100.    printf("%d\n", goldCount);
  101.  
  102.    return 0;
  103. }


And the official solution in C:

C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #define MAX 15
  3.  
  4. char cube[MAX][MAX][MAX];
  5. int n;
  6.  
  7. int dig(int i, int j, int k) {
  8.     int g=0;
  9.     if(i<0||j<0||k<0)        return 0; // Can't dig off cube
  10.     if(i==n||j==n||k==n)     return 0; // Can't dig off cube
  11.     if(cube[i][j][k] == 'X') return 0; // Can't dig through rock
  12.  
  13.     if(cube[i][j][k] == '*') g++; // Gather gold
  14.     cube[i][j][k] = 'X';     // Don't need to try this place again
  15.  
  16.     return g + dig(i+1,j,k) + dig(i,j-1,k) + dig(i,j+1,k) + dig(i,j,k-1) + dig(i,j,k+1);    
  17. }
  18.  
  19. int main() {
  20.     int i, j, k, gold=0;
  21.  
  22.     freopen("gold.in", "rt", stdin);
  23.     freopen("gold.out", "wt", stdout);
  24.  
  25.     scanf("%d", &n);
  26.     for(i=0; i<n; i++)
  27.         for(j=0; j<n; j++)
  28.             scanf("%s", cube[i][j]);
  29.  
  30.     for(j=0; j<n; j++)            // Try every starting place
  31.         for(k=0; k<n; k++)
  32.             gold += dig(0, j, k); // Gather gold and add to total
  33.  
  34.     printf("%d\n", gold);
  35.     return 0;
  36. }
Attached Files
File Type: zip gold.zip (3.1 KB, 3 views)
__________________
Looking for tough programming challenges? Try participating in Sane's Monthly Algorithms Challenges!
Composing Techno is a little side hobby of mine. Techno by DJ Sane. All free for download.
Last edited by Sane; Oct 8th, 2008 at 11:11 AM.
Sane is offline   Reply With Quote
Old Oct 9th, 2008, 12:52 AM   #2
Arla
Professional Programmer
 
Arla's Avatar
 
Join Date: Mar 2005
Posts: 346
Rep Power: 4 Arla is on a distinguished road
Re: SMAC #4 [09-08] - Digging For Gold (Junior)
Have to admit I made use of Trapped's official solution to figure my own solution for this one, it was an interesting challenge, I think the biggest thing that I needed to get "over" was that you can go in as many times as you like, which is where I ended up just going with just working out which squares you can get to (in the problem you always said which squares you went to in what order, where really what square you went to in what order was utterly irrelevant, it's whether I can get to a square or not).

Now, a harder problem would definitely be the same thing but having to figure both how many pieces you can get, and the shortest path to get them (in this modern gas-efficient age where we want to get the most gold for the least cost!).
Arla is online now   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
Linear Mode Linear Mode

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 #3 [07-08] - Stock Market (Junior) Sane Software Design and Algorithms 5 Aug 8th, 2008 11:50 AM
SMAC #3 [07-08] - Results Sane Software Design and Algorithms 4 Aug 6th, 2008 8:23 PM
SMAC #2 [06-08] - Trapped (Junior) Sane Software Design and Algorithms 0 Jul 1st, 2008 12:19 PM
SMAC #1 [05-08] - Mobile (Beginner) and "n Reach k" (Junior) Sane Software Design and Algorithms 2 Jun 3rd, 2008 9:10 AM
SMAC #1 [05-08] - Results Sane Software Design and Algorithms 6 Jun 2nd, 2008 5:56 PM


Contact Us - DaniWeb IT Discussion Community - Privacy Statement - Top


DaniWeb IT Discussion Community
All times are GMT -5. The time now is 10:10 AM.

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