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!

Edited 7 Years Ago by Tamaki: n/a

Attachments
#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;
}

I glimpsed at you problem and I'm not sure why you would use recursion when a loop is better and easier.

To kenji,
Yeah, i would use a loop
but the assignment states that I have to solve with recursion...

This article has been dead for over six months. Start a new discussion instead.