Alright, now that that class is over I've decided that I'm actually going to keep this blog. I'm going to turn it into a programming blog of sorts, and if people start following it great. I program mainly in Java, however I'm fairly adequate in C++ as well. Let's jump straight into things, and here's the first problem that I'm trying to solve.
There's an island, and it is broken up into sections (similiar to a 2-d array). Each section is associated with a height. Unlike most islands that have mountains in the middle, this island has mountains on the edges. Assuming there's no water evaporation happening during a rainstorm the island could potentially form lakes. The problem is to be given a random island, and to calculate the maximum amount of water it can hold. Each height increment can hold 1 million gallons of water.
example:
We have the island
5 6 4
3 1 5
9 8 7
This island can hold 2 million gallons of water because the height in the middle can be raised by 2 before water starts leaking out into the ocean.
For simplicity we'll always deal with a square island (of sizes up to 20x20), and we can say that water does not leak diagonally. However the edges are not always higher than the middle spots.
Here's my solution in bits and pieces. I decided to go with a recursive function.
ReplyDeleteFirst is my create island function, it randomly generates an island anywhere from a 3x3 up to a 20x20:
// generates an island that is at least 3x3 squares big all the way up to
// 20x20
private void createIsland() {
Random rand = new Random();
dimensions = rand.nextInt(17) + 3;
waterTotal = 0;
island = new int[dimensions][dimensions];
edges = new boolean[dimensions][dimensions];
for (int j = 0; j < dimensions; j++) {
for (int i = 0; i < dimensions; i++) {
// assign random heights
island[i][j] = rand.nextInt(7) + 1;
if (j == 0 || j == dimensions - 1 || i == 0
|| i == dimensions - 1) {
// the edges tend to be more mountainous
island[i][j] = rand.nextInt(4) + 6;
edges[i][j] = true;
} else
edges[i][j] = false;
}
}
// verify the edges
for (int i = 0; i < dimensions; i++)
for (int j = 0; j < dimensions; j++)
verifyEdges(i, j);
}
next I had a method that verified the edges were correct, and updated them if they weren't. There were several times when I was leaking out when I shouldn't have been because the edge of my lake wasn't where it was supposed to have been.
// when generating the island, the edges are set as the edges, this
// function ensures that if an edge is in the middle, it is still
// counted as an edge
// example:
// 4 5 6 7
// 4 5 3 8
// 5 2 1 9
// 9 9 9 9
// the index of x = 1, y = 1 where the height is 5, is also an edge
// because it's higher than the 4 edge
private void verifyEdges(int i, int j) {
if (edges[i][j]) {
if (i != 0 && !edges[i - 1][j])
if (island[i - 1][j] >= island[i][j]) {
edges[i - 1][j] = true;
verifyEdges(i - 1, j);
}
if (j != 0 && !edges[i][j - 1])
if (island[i][j - 1] >= island[i][j]) {
edges[i][j - 1] = true;
verifyEdges(i, j - 1);
}
if (i != dimensions - 1 && !edges[i + 1][j])
if (island[i + 1][j] >= island[i][j]) {
edges[i + 1][j] = true;
verifyEdges(i + 1, j);
}
if (j != dimensions - 1 && !edges[i][j + 1])
if (island[i][j + 1] >= island[i][j]) {
edges[i][j + 1] = true;
verifyEdges(i, j + 1);
}
}
}
Next is my Calculate method. It traverses over the whole island filling it in with water as necessary.
ReplyDelete// calculates the total amount of water an island can hold
public void calculate() {
printIsland();
for (int i = 1; i < dimensions - 1; i++)
for (int j = 1; j < dimensions - 1; j++) {
// System.out.println("currently at: " + i + " " + j);
// System.out.println(island[i][j]);
if (!edges[i][j]) {
lowestEdge = Integer.MAX_VALUE;
lowestNeighbor = Integer.MAX_VALUE;
currentSize = 1;
fillUpTo = island[i][j];
currentLake = new int[dimensions * dimensions][2];
visited = new boolean[dimensions][dimensions];
currentLake[0][0] = i;
currentLake[0][1] = j;
fillIsland(i, j);
fillLake(Math.min(lowestEdge, lowestNeighbor));
// printIsland();
}
}
printIsland();
System.out.println("This island can hold up to " + waterTotal
+ " million gallons of water.");
}
Here's my recursive fillIsland method that goes through and fills it with water.
ReplyDelete// the recursive method that handles filling the whole island
private void fillIsland(int i, int j) {
visited[i][j] = true;
// check above
if (!edges[i - 1][j]) {
// if not an edge
if (island[i - 1][j] <= island[i][j] && !visited[i - 1][j]) {
// if lower or equal in elevation and we haven't visited before
currentLake[currentSize][0] = i - 1;
currentLake[currentSize][1] = j;
currentSize++;
// fill up that spot too
fillIsland(i - 1, j);
// don't replace higher spots with lower spots. The ground can't
// move
if (fillUpTo > island[i][j]) {
waterTotal += fillUpTo - island[i][j];
island[i][j] = fillUpTo;
}
// find the lowest neighbor of the whole lake
} else if (island[i - 1][j] > island[i][j]
&& island[i - 1][j] < lowestNeighbor) {
lowestNeighbor = island[i - 1][j];
}
} else {
// if it is an edge check to see if it's the lowest we've seen so
// far
if (island[i - 1][j] < lowestEdge)
lowestEdge = island[i - 1][j];
}
// to the left
if (!edges[i][j - 1]) {
if (island[i][j - 1] <= island[i][j] && !visited[i][j - 1]) {
currentLake[currentSize][0] = i;
currentLake[currentSize][1] = j - 1;
currentSize++;
fillIsland(i, j - 1);
if (fillUpTo > island[i][j]) {
waterTotal += fillUpTo - island[i][j];
island[i][j] = fillUpTo;
}
} else if (island[i][j - 1] > island[i][j]
&& island[i][j - 1] < lowestNeighbor) {
lowestNeighbor = island[i][j - 1];
}
} else {
if (island[i][j - 1] < lowestEdge)
lowestEdge = island[i][j - 1];
}
// below
if (!edges[i + 1][j]) {
if (island[i + 1][j] <= island[i][j] && !visited[i + 1][j]) {
currentLake[currentSize][0] = i + 1;
currentLake[currentSize][1] = j;
currentSize++;
fillIsland(i + 1, j);
if (fillUpTo > island[i][j]) {
waterTotal += fillUpTo - island[i][j];
island[i][j] = fillUpTo;
}
// printIsland();
} else if (island[i + 1][j] > island[i][j]
&& island[i + 1][j] < lowestNeighbor) {
lowestNeighbor = island[i + 1][j];
}
} else {
if (island[i + 1][j] < lowestEdge)
lowestEdge = island[i + 1][j];
}
// to the right
if (!edges[i][j + 1]) {
if (island[i][j + 1] <= island[i][j] && !visited[i][j + 1]) {
currentLake[currentSize][0] = i;
currentLake[currentSize][1] = j + 1;
currentSize++;
fillIsland(i, j + 1);
if (fillUpTo > island[i][j]) {
waterTotal += fillUpTo - island[i][j];
island[i][j] = fillUpTo;
}
// printIsland();
} else if (island[i][j + 1] > island[i][j]
&& island[i][j + 1] < lowestNeighbor) {
lowestNeighbor = island[i][j + 1];
}
} else {
if (island[i][j + 1] < lowestEdge)
lowestEdge = island[i][j + 1];
}
}
and finally here's my method that takes the current lake, and fills it up to the lowest next highest neighbor, or the lowest edge, whichever is lower.
// fills the current lake up to the fillTo point
private void fillLake(int fillTo) {
for (int i = 0; i < currentSize; i++) {
waterTotal += fillTo - island[currentLake[i][0]][currentLake[i][1]];
island[currentLake[i][0]][currentLake[i][1]] = fillTo;
}
}