C++

Forum

 
Recursive paths repeated (Buckets problem)

icy1 (596)
I got inspired by another recent post that was trying to solve a version of a classic Buckets problem. Given one bucket with capacity 5 Liters, and another with capacity 8 Liters, measure out 4 Liters. Buckets have no gradients on them.

I figured I'd give it a stab with brute-force recursion, but for some reason paths/solutions are getting repeated (I'm not sure why). I'm purposely passing the structures by value.

Can run it at https://repl.it/repls/SkinnyLateWebmaster

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

const int GOAL = 4;
const int TOO_MANY_STEPS = 20;
static int total_solutions = 0;

struct Bucket
{
    Bucket(int capacity, int level=0) :
        capacity(capacity),
        level(level)
    {
    }
    
    int capacity;
    int level;
};

void Show(const vector<pair<string,string>>& v)
{
    cout << endl;
    for (int i=0; i<v.size(); ++i)
        cout << (i+1) << ". " << v[i].first << "\t\t" << v[i].second << endl;
}


void Pour(string op, Bucket a, Bucket b, 
          vector<pair<string,string>> steps,
          map<string,int> seen)
{
    string state = to_string(a.level)+","+to_string(b.level);
    if (seen.count(state)>0)
    {
        //cout << "Already saw the state " << state << "; aborting.\n";
        return;
    }
    seen[state]+=1;
    
    
    if (a.level==GOAL || b.level==GOAL)
    {
        steps.emplace_back(state, "");
        total_solutions += 1;
        Show(steps);
        cout << "Done." << endl;
        return;
    }
    
    if (steps.size() >= TOO_MANY_STEPS)
    {
        //cout << "Too many steps!\n";
        return;
    }
    steps.emplace_back(state, op);
    
    
    // Pour a into b, as much as can fit
    if (op=="a->b")
    {
        int diff = b.capacity - b.level;
        if (diff >= a.level)
        {
            b.level += a.level;
            a.level = 0;
        }
        else
        {
            b.level += diff;
            a.level -= diff;
        }
    }
    else if (op=="b->a")
    {
        int diff = a.capacity - a.level;
        if (diff >= b.level)
        {
            a.level += b.level;
            b.level = 0;
        }
        else
        {
            a.level += diff;
            b.level -= diff;
        }
    }
    // Fill a
    else if (op=="a") 
    {
        a.level = a.capacity;
    }
    else if (op=="b")
    {
        b.level = b.capacity;
    }
    // Empty a
    else if (op=="-a") 
    {
        a.level = 0;
    }
    else if (op=="-b")
    {
        b.level = 0;
    }
    
    if (a.level > 0 && b.capacity!=b.level)
        Pour("a->b", a, b, steps, seen);
    if (b.level > 0 && a.capacity!=a.level)
        Pour("b->a", a, b, steps, seen);
    if (a.level != a.capacity)
        Pour("a", a, b, steps, seen);
    if (b.level != b.capacity)
        Pour("b", a, b, steps, seen);
    if (a.level != 0)
        Pour("-a", a, b, steps, seen);
    if (b.level != 0)
        Pour("-b", a, b, steps, seen);
}

void FirstRun()
{
    vector<pair<string,string>> steps;
    Bucket a(5);
    Bucket b(8);
    map<string,int> seen;
    Pour("a", a, b, steps, seen);    //36 solutions, many duplicates
    //Pour("b", a, b, steps, seen);  //44 solutions, many duplicates
}


int main() 
{
    FirstRun();
    cout << "\ntotal solutions: " << total_solutions << endl;
    return 0;
}


Example output below.
First column shows the current levels of a and b.
Second column is the operation to perform next.
• a : Fill a
• -a : Empty a
• a->b : Transfer as much as possible from a to b
1. 0,0		a
2. 5,0		b
3. 5,8		-a
4. 0,8		b->a
5. 5,3		-a
6. 0,3		b->a
7. 3,0		b
8. 3,8		b->a
9. 5,6		-a
10. 0,6		b->a
11. 5,1		-a
12. 0,1		b->a
13. 1,0		b
14. 1,8		b->a
15. 5,4		
Done.

Last edited on
ne555 (10692)
you're printing too late.
let's say a=1, b=8 and you decide to transfer from b to a
you enter the condition else if (op=="b->a") at line 76 and so your new values are
a = 5, b=4.
there, you reached the goal.
however, you continue execution to lines 109, 111, 113, 115, 117, 119, where you add another operation and launch the recursion one more time.
tpb (1495)
however, you continue execution to lines 109, 111, 113, 115, 117, 119, where you add another operation and launch the recursion one more time.

But the first thing the function does (after checking for a repeated state) is check if it's reached the goal (before applying the latest op). It's a weird way to do it, but that's how it works.
Last edited on
ne555 (10692)
> is check if it's reached the goal (before applying the latest op).
yes, the goal is reached and so the steps are printed.
to clarify, in the example you've got to the goal after doing the operation "b->a" ending with a=5, b=4, but you don't print the steps here, you launch the recursive calls and they check the goal.


> after checking for a repeated state
the goal state fails to register as repeated because `seen' is passed by value (and again, the state is check before doing the operation)
lets say that "a->b" sees the goal a=5, b=4 and register it in `seen'
when it's the turn of "b->a" `seen' does not have that state because you updated a copy, so that check will not end the function.

this may be a wanted behaviour, as intermediate steps may be reached by different paths.
Last edited on
tpb (1495)
Sorry, but I don't get what you are saying.
Luckily I'm not the OP so it doesn't matter!
I'll leave it to him to ask for further clarification if needed.
icy1 (596)
ne555 wrote:
you're printing too late.
let's say a=1, b=8 and you decide to transfer from b to a
you enter the condition else if (op=="b->a") at line 76 and so your new values are
a = 5, b=4.
there, you reached the goal.
however, you continue execution to lines 109, 111, 113, 115, 117, 119, where you add another operation and launch the recursion one more time.


Thanks ne555, you found it! The key problem was not the general design, but the end in particular, exactly as you mentioned. I simply moved the GOAL check section after performing the operation, then did a minor update of state again to add to final solution. Both sets of solutions (starting with a, starting with b) went down by a factor of 4, and just scrolling through, they seem to be unique. Thanks! Updated the online version, which hopefully updates for you too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

const int GOAL = 4;
const int TOO_MANY_STEPS = 20;
static int total_solutions = 0;

struct Bucket
{
    Bucket(int capacity, int level=0) :
        capacity(capacity),
        level(level)
    {
    }
    
    int capacity;
    int level;
};

void Show(const vector<pair<string,string>>& v)
{
    cout << endl;
    for (int i=0; i<v.size(); ++i)
        cout << (i+1) << ". " << v[i].first << "\t\t" << v[i].second << endl;
}


void Pour(string op, Bucket a, Bucket b, 
          vector<pair<string,string>> steps,
          map<string,int> seen)
{
    string state = to_string(a.level)+","+to_string(b.level);
    if (seen.count(state)>0)
    {
        //cout << "Already saw the state " << state << "; aborting.\n";
        return;
    }
    seen[state]+=1;
    
    if (steps.size() >= TOO_MANY_STEPS)
    {
        //cout << "Too many steps!\n";
        return;
    }
    steps.emplace_back(state, op);
    
    
    // Pour a into b, as much as can fit
    if (op=="a->b")
    {
        int diff = b.capacity - b.level;
        if (diff >= a.level)
        {
            b.level += a.level;
            a.level = 0;
        }
        else
        {
            b.level += diff;
            a.level -= diff;
        }
    }
    else if (op=="b->a")
    {
        int diff = a.capacity - a.level;
        if (diff >= b.level)
        {
            a.level += b.level;
            b.level = 0;
        }
        else
        {
            a.level += diff;
            b.level -= diff;
        }
    }
    // Fill a
    else if (op=="a") 
    {
        a.level = a.capacity;
    }
    else if (op=="b")
    {
        b.level = b.capacity;
    }
    // Empty a
    else if (op=="-a") 
    {
        a.level = 0;
    }
    else if (op=="-b")
    {
        b.level = 0;
    }
    
    if (a.level==GOAL || b.level==GOAL)
    {
        state = to_string(a.level)+","+to_string(b.level);
        steps.emplace_back(state, "");
        total_solutions += 1;
        Show(steps);
        cout << "Done." << endl;
        return;
    }
    
    if (a.level > 0 && b.capacity!=b.level)
        Pour("a->b", a, b, steps, seen);
    if (b.level > 0 && a.capacity!=a.level)
        Pour("b->a", a, b, steps, seen);
    if (a.level != a.capacity)
        Pour("a", a, b, steps, seen);
    if (b.level != b.capacity)
        Pour("b", a, b, steps, seen);
    if (a.level != 0)
        Pour("-a", a, b, steps, seen);
    if (b.level != 0)
        Pour("-b", a, b, steps, seen);
}

void FirstRun()
{
    vector<pair<string,string>> steps;
    Bucket a(5);
    Bucket b(8);
    map<string,int> seen;
    Pour("a", a, b, steps, seen);  // 9 solutions
    Pour("b", a, b, steps, seen);  // 11 solutions
}


int main() 
{
    FirstRun();
    cout << "\ntotal solutions: " << total_solutions << endl;
    return 0;
}
Topic archived. No new replies allowed.