Show Bid Request
Dijkstra's Shortest Paths
Bid Request Id: 51204
|
|
|
|
Posted by: |
BPEJMAN (3 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 0.00%
|
|
Posted: |
Mar 4, 2003
5:23:07 PM EDT
|
|
Bidding Closes: |
Mar 9, 2003 EDT
|
|
Viewed (by coders): |
321 times
|
|
Deadline: |
3/9/2003
TIME EXPIRED
|
|
|
|
|
Description:
Imagine you are confronted with the following puzzle. You are given a 3-gallon Jug and a 5-gallon Jug and
you're asked to fill the 5-gallon Jug with exactly 4 gallons. You're also provided with infinite amount
of water. You must solve this problem by filling Jug A or Jug B and emptying each one or pour one into
the other. For example, the solution to this problem would be:
to fill the 5-gallon jug, pour the 5-gallon jug into the 3-gallon jug (this left 2 gallons in the 5-gallon jug) empty the 3-gallon jug, pour the 5-gallon jug into the 3-gallon jug, fill the 5-gallon jug and then fill the 3-gallon jug from the 5-gallon jug, empty the 3 gallon jug, leaving 4 gallons in the 5 gallon jug.
You have two jugs, A and B, and an infinite supply of water. There are six types of actions that you can use, each with a cost:
(1) you can fill jug A or B
(2) you can empty jug A or B
(3) you can pour from one jug to the other.
(total of 6 operations)
Remember that your goal is to find the cheapest (shortest) path to the solution. Each action you take
has a cost to it (will be assigned a cost) and therefore you must use Dijkstra's graph in this program. No math formulas please!
Also note that pouring from one jug to the other stops when the first jug is empty or the second jug is full,
whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8,
then pouring from A to B leaves B full and 3 gallons in A.
A problem is given by (Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA), where Ca and Cb are the
capacities of the jugs A and B, respectively, and N is the goal. cfA is the cost to fill A, cfB
is the cost to fill B, ceA, is the cost to empty A, ceB is the cost to empty B, cpAB is the cost
to pour A to B and cpBA is the cost to pour B to A. A solution is a sequence of steps that leaves
jug A empty, and exactly N gallons in jug B. The possible steps are
fill A
fill B
empty A
empty B
pour A B
pour B A
success X
fill means to fill the jug from the infinite water supply empty means to discard the water in the jug
where "pour A B" means " pour the contents of jug A into jug B" "success X" means that the goal has been accomplished, jug B contains N gallons at a cost of X.
Error Checking: If a problem doesn't have a solution, which can happen, then simply print no solution. Program must also check that all entered costs for each action are not negative.
Deliverables:
***Please follow these specs***
You MUST solve this problem by building and traversing a graph, absolutely, no math formulas. Construction of graph is up to you. You may use queues, stacks, heaps, priority queues, trees or any other NON GRAPH structure you need.
Write a Jug class (located in jug.h) that takes 9 parameters in the constructor. All function definitions must be in jug.cpp.
(Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA) Note: the order IS definately important, so please keep the
parameters' order the same. Also checking for valid input is something you should do. (i.e. no negative costs)
Your Jug class must have a Solve() member which will solve and then print the CHEAPEST solution. Remember, each action will have an assigned cost to it.
class Jug
{
public:
Jug(int,int,int,int,int,int,int,int,int);
~Jug();
//Solve is used to check input and find the
solution if one exists
//returns -1 invalid inputs. Do not print
anything.
//returns 0 if inputs are valid but a solution
does not exist. Do not print anything.
//returns 1 if solution is found and also
prints solution.
int Solve();
private:
//anything else you need
};
Write a main.cpp and a Makefile for testing. Because your main is for you to test, you may hard
code in values or read them from a file or command line. Your main.cpp file should be independent
of all other source codes. Basically, the main should pass the 9 values entered by user or hard coded by user to the class.
Please be sure you do NOT rename any public functions or the class. This is because your main.cpp will
be replaced by mine and different cases will cause compilation error.
**Program Input
Input to your program consists of 9 ints defining one puzzle. Ca, Cb, N, cfA, cfB, ceA, ceB, cpAB, cpBA.
Ca and Cb are the capacities of jugs A and B, and N is the goal. the rest are the costs for each action.
If the inputs are invalid or there's no solution to a problem then Solve will return -1.
**Program Output
Output from your program will consist of a series of instructions from the list of the potential output lines which will result in jug A being empty and jug B containing exactly N gallons of water. The last line of output for each puzzle should be the line "success X". (where X is the cost) Output lines start in column 1 and there should be no empty lines nor any trailing spaces.
---Sample Input (hard coded or entered by user)
Jug Head(3, 5, 4, 1, 2, 3, 4, 5, 6);
Head.Solve();
---Sample Output
fill A
pour A B
fill A
pour A B
empty B
pour A B
fill A
pour A B
success 27
where 27 is the cheapest cost (fastest path to solution)
---Sample Output Not Shortest Path
fill B
pour B A
empty A
pour B A
fill B
pour B A
empty A
success 28
1) Please provide all source codes
2) comment here and there
3) This must compile under Linux Mandrake 9.0 using g++ or gcc compiler. PLEASE keep all .cc extentions to .cpp
4) Complete ownership and distribution copyrights to all work purchased.
Platform:
Linux Mandrake 9.0
Must compile with g++ or gcc compiler
Must be 100% finished and received by buyer on:
Mar 9, 2003 EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation please help out the site and report it. Thanks for your help.
|
|
|
Bidding/Comments:
|
All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. |
See all rejected bids (and all comments)
| Name |
Bid Amount
|
Date |
Coder Rating |
|
|
This bid was accepted by the buyer!
|
$100 (USD)
|
Mar 5, 2003
8:13:32 AM EDT
|
9.9
(Excellent)
|
|
|
hi,
we are extremely good in c/c++. we have done many several projects as you can check our rating. we are all with a master degree in computer science and informatics(now studying AI in our ph.D). here we are sending the demo of the project - it's a slight different version of the one you want because our bid is not accepted yet. right after acceptance we will make it the way you want it. here are the differences : the input is three integers A B and N where A and B are the capacities and N is the desired capacity in B. as you can see there are no costs, actually the costs are all the same. the input is read from the jugs_inp.txt where can be found several test cases each on a separate line. the first line is the test case you mentioned and the outputs is writed to jugs_out.txt and you can check that all works fine(when the costs are all the same). right after the acceptance we will make it to work with different cost which is a very simple task. just run the exe file provided in the zip and the output should be created for you(actually we've placed such one in the zip so you can delete it to check that the program works 8-)
thanks for bidding,
bye
P.S. we are placing that price because it's the only price that can be bid for this project - the minimum is 100$ and the maximum is 100$ so that's the only choice
GAD Software |
|
|
Attached File
|
|
|
|
|
|
