Greetings Java Friends
Warning: This is going to be slightly long.
The Challenge:
Create Two Bots that will exit the Graph safely. The first bot called ( QuickBot ) will aim to exit the Graph as fast as possible. The second bot called ( GreedyBot ) will aim to exit the graph with the highest amount of resource possible.
A bot can not reach a resource level of 0 << it will die if that happens.
My Solution:
The Bot will always land at the Entrance node. There I will make the bot look through the graph via the getMap() method (returns Hashtable<Node<Adjustment>, ArrayList<Node<Adjustment>>>) and somehow get all the available paths to the Exit node. Each one of these will be saved in an ArrayList<Stack<String>>, the Stack represents a single path. Once that is done, The Bot will go through each of the available stacked paths and see which ones cause the Bot to die, and delete those. The Bot will then somehow calculate which of the Stack Paths gives the shortest route possible (for Quick) or the route that deducts least resources (for Greedy) to the Exit node.
Once the ideal stack path is calculated (depending on nature of the Bot, Quick or Greedy), that stack will be left as a message at the Entrance node of the Graph. This way all the nodes entering later, can read the Stack from the message and follow the path specified in the Stack, and they too can Exit according to the Bot's nature.
Relax ! I know that was a lot to take in :(nod):. For me personally images always help. I hope it is the same for you. Here's a particular Graph. Called Graph5.
http://i55.tinypic.com/25g82s1.jpg
I hope you appreciate my handy photoshop work, it took me 20 minutes to create that :(blush):
So that's what the Graph looks like on Paper. But in Code it is represented as a Hashtable. Here's an image representation of the Hashtable.
http://i56.tinypic.com/2s5zgyg.jpg
On the left the Key representing a node. On the right are the values and they are an ArrayList of the neighbouring nodes.
And now my code:
Where I'm Stuck:Code:/**
* The stuff in this method is run when the Bot is present at the node.
*/
public void visitNodeActions() throws BotError {
if(isAtEntrance())
{
// A place to store the safe paths.
ArrayList<Stack<String>> paths = new ArrayList<Stack<String>>();
// The variable g stands for, and is the Graph object < which in itself is a Hashtable.
Hashtable<Node<Adjustment>, ArrayList<Node<Adjustment>>> g = getMap().getAdjacencyList();
// Iterating through [g] to find safe paths.
Enumeration<Node<Adjustment>> e = g.keys();
while(e.hasMoreElements())
{
// e.nextElement can only be used once within the while loop. So I'm assigning it to a variable that can be used many times.
Node<Adjustment> x = (Node<Adjustment>)e.nextElement();
// Check to see if we have the Start Node.
if(getLocation() == x.getName())
{
// A variable called [neighbours]. It represents the neighoubrs of the current node in the loop
ArrayList<Node<Adjustment>> neighbours = g.get(x);
// The Path [p] represented as a Stack. This will be inserted into our safe [paths] ArrayList later on.
Stack<String> p = new Stack<String>();
// Iterating through the neighbours of the current node, and foreach building a path [p] from them.
for(Node<Adjustment> n : neighbours)
{
p.push(x.getName());
p.push(n.getName());
// Adding the stacked path [p] to the safe paths list [paths]
paths.add(p);
// Now that the stacked path [p] has been stored, we need to clear, empty [p] for the next path.
p.clear();
}
}
}
}
}
My code currently stores the following two paths successfully.
AB
AC
But what I need it to do afterwards, is get me the following paths:
ABF
ACD
Whilst still keeping the original two paths, so all in all the saved paths will be:
AB
AC
ABF
ACD
and then after that, it will be:
AB
AC
ABF
ACD
ACDE
and so on ..
I do not know how to get my code to get me results such as above. :=(: If you think there is ill-logic in my solution to the challenge, please help point them out. If not, I would greatly appreciate any help in getting the code to do what I need it to do.
If you have any questions, or if I have not explained something clearly, please do not hesitate to ask. I have tried to make it as easy as possible for you to help me (I hope).
Thank You So Much.
