At least for me it is:)
This is an assignment problem and I can really use some help!
INTRO TO PROBLEM:
So the problem is a basic logic problem, where I'm sure you're all familiar with...
From my assignment page, the problem
Imagine that you have 2 jugs, a small one and a large one, with integer capacities of sCap
and lCap gallons, respectively (sCap < lCap). Initially both jugs are empty. You are
allowed to completely fill each jug from a tap, or empty them on the ground. You can also
pour one jug into the other: pouring stops when either the receiving jug is full or no water is left
in the pouring jug (i.e. no water is spilled). Note that each pouring action will cause a positive
number of whole gallons to be transferred.
Given two integer values sFinal and lFinal, the problem is to find a valid sequence
of actions such that after performing the actions, the small and large jugs contain exactly
sFinal and lFinal gallons of water, respectively.WHAT I NEED HELP ON
Basically I have a few functions that are ready to be used...
I will attach a .c file at the end of this post for the code...
I took a long time checking over this post and adding comments, any sort of help on recursion is appreciated...
I just don't understand how to start this recursion
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
char *solve(const char curSequence[], int sCur, int lCur, int sCap, int lCap, int sFinal, int lFinal);
void prettyPrint(const char solution[], int sCap, int lCap);
bool actionIsPossible(char action, int sCur, int lCur, int sCap, int lCap);
void getUpdatedJugsAmounts(char action, int sCur, int lCur, int sCap, int lCap, int *sUpdated, int *lUpdated);
bool occurs(const char curSequence[], int sVal, int lVal, int sCap, int lCap);
bool applyAction(char action, const char curSequence[], int sCur, int lCur, int sCap, int lCap, char updatedSequence[], int *sUpdated, int *lUpdated);
//a testing main method that was given
int main(int argc, char *argv[])
{
int sCap, lCap, sFinal, lFinal;
if (argc < 5)
{
printf("Usage: jugs smallCapacity largeCapacity smallFinal largeFinal\n");
return 0;
}
sCap = atoi(argv[1]);
lCap = atoi(argv[2]);
sFinal = atoi(argv[3]);
lFinal = atoi(argv[4]);*/
char *solution;
solution = solve("", 0, 0, 3, 4, 0, 2);
printf("The solution is: %s\n", solution);
if (strcmp(solution, "Not Found") != 0)
prettyPrint(solution, sCap, lCap);
free(solution);
return 0;
}
//This is the function I'm having trouble with...
//Basically this function should follow this idea
////////////////////////////////////////////////////////////////////////
/*char *solve(curSequence, curConfig, capacities, finalConfig)
// if the current configuration == the final configuration then
// it means that no further action is needed so simply
// allocate space and return a copy of curSequence as the solution
// else
// pick one of the 6 actions and apply it to the curConfig
// (you may want to call applyAction)
// if the action is applicable (i.e. it is possible and it
// does not create a cycle) and a recursive call to
// solve(updatedSequence, updatedConfig, capacities, finalConfig)
// returns a solution then return this solution
// otherwise clean up any dynamically allocated spaces and if any
// un-tried action is left, then try it (as above)
// if no more action is left to try then
// allocate space and return the string "Not Found".8?*/
//////////////////////////////////////////////////////////////////////
///////////////////my crappy recursion////////////////////////////////
char *solve(const char curSequence[], int sCur, int lCur, int sCap, int lCap, int sFinal, int lFinal){
if (sCur == sFinal && lCur == lFinal) {
int i;
for(i = 0; curSequence[i] != '\0'; i++);
char *solution = (char *)malloc(i*sizeof(char *));
strcpy(solution,curSequence);
return solution;
}
else {
char *solution = (char *)malloc(sizeof(char *));
printf("here\n");
char *curAct = (char *) malloc (sizeof(char *));
char god[] = {'f', 'F', 'p', 'P', 'e', 'E'};
int i;
for(i = 0; i < 6; i++){
if(applyAction(god[i], solution, sCur, lCur, sCap, lCap, curAct, &sCur, &lCur)){
curAct = solve(solution, sCur, lCur, sCap, lCap, sFinal, lFinal);
printf("recur\n");
}
else
free(curAct);
strcat(solution,curAct);
return solution;
}
solution = (char *)malloc(sizeof(char)*(strlen("Not Found") + 1));
strcpy(solution,"Not Found");
return solution;
}
//A simple print method in the format <S0, L0> A1 <S1, L1> so on
void prettyPrint(const char curSequence[], int sCap, int lCap){
int i, j = strlen(curSequence)+1;
int s = 0, l = 0;
for(i = 0 ; i < j; i++){
printf("<%d,%d> ", s, l);
getUpdatedJugsAmounts(curSequence[i], s, l, sCap, lCap, &s, &l);
printf("%c ", curSequence[i]);
}
}
//There are certain restrictions on which action is possible at a given configuration
//returns true if possible, false otherwise
bool actionIsPossible(char action, int sCur, int lCur, int sCap, int lCap){
bool final = false;
if (action == 'f' && sCur < sCap){final = true;} //the small jug is not already full
else if (action == 'F' && lCur < lCap){final = true;} //the big jug is not already full
else if (action == 'p' && sCur > 0 && lCur < lCap){final = true;} //the small jug is not empty AND the big jug is not full
else if (action == 'P' && lCur > 0 && sCur < sCap){final = true;} //the big jug is not empty AND the small jug is not full
else if (action == 'e' && sCur > 0){final = true;} //the small jug is not already empty
else if (action == 'E' && lCur > 0){final = true;} //the big jug is not already empty
return final;
}
//calculated the new amounts and returns them through pointers
void getUpdatedJugsAmounts(char action, int sCur, int lCur, int sCap, int lCap, int *sUpdated, int *lUpdated){
*sUpdated = sCur; *lUpdated = lCur;
if (action == 'f'){*sUpdated = sCap;}
else if (action == 'F'){*lUpdated = lCap;}
else if (action == 'p'){for (; lCur < lCap && sCur > 0; sCur--, lCur++);*sUpdated = sCur; *lUpdated = lCur;}
else if (action == 'P'){for (; sCur < sCap && lCur > 0; lCur--, sCur++);*sUpdated = sCur; *lUpdated = lCur;}
else if (action == 'e'){*sUpdated = 0;}
else if (action == 'E'){*lUpdated = 0;}
}
//If the given sequence does not for a repeated config/cycle
//ie: if you start wiht <0,0> and perform PP on sCap = 3 lCap = 4, first <0,4> then <0,4>, which gives u a repeated configuration...
//returns true if there is a repeated config, false otherwise
bool occurs(const char curSequence[], int sVal, int lVal, int sCap, int lCap){
int i, j = strlen(curSequence)+1;
int sCur = 0, lCur = 0;
bool final = false;
if (sVal == 0 && lVal == 0){final = true;}
for (i = 0; i < j ; i++){
//printf("%d = %d %d = %d\n",sCur,sVal,lCur,lVal);
if (actionIsPossible(curSequence[i], sCur, lCur, sCap, lCap)){
getUpdatedJugsAmounts(curSequence[i], sCur, lCur, sCap, lCap, &sCur, &lCur);
if (sCur == sVal && lCur == lVal){final = true;}
}
}
return final;
}
//apply the action, update the sequence with the new action, and pass the new values back with points and the updated sequence with the array.
//return true if the action is possible and does not cycle, false otherwise
bool applyAction(char action, const char curSequence[], int sCur, int lCur, int sCap, int lCap, char updatedSequence[], int *sUpdated, int *lUpdated){
bool final = false;
strcpy(updatedSequence,curSequence);
int s = 0, l = 0;
const char act[2] = {action};
if (actionIsPossible(action, sCur, lCur, sCap, lCap)){
getUpdatedJugsAmounts(action, sCur, lCur, sCap, lCap, &s, &l);
if (!occurs(curSequence, sCur, lCur, sCap, lCap)){
*sUpdated = s;
*lUpdated = l;
updatedSequence = strcat(updatedSequence,act);
final = true;
}
}
return final;
}Thank you again for any help!
