1

The task is to convert a given state to the final state least possible steps. For example if you input a string like this:

213456

The state looks like this (it's always 6 characters):
2 1 3
4 5 6

The state you need to convert it to is always the same:
1 2 3
4 5 6

You need to switch the numbers to get the final state, you only switch them horizontally and vertically. It's not a hard task, but I'm having a problem with my never-ending recursion. Please don't comment on the code yet (using namespace std; not using functions for repeating processes etc.) since I'm not finished, I need you to help me understand why is this a never-ending recursion.

Edit: CODE IS NOW WORKING!

#include <iostream> #include <map> #include <string> #include <algorithm> #include <vector> using namespace std; int f(string s, map <string, int>& visited, int steps = 0) { string s2 = s; vector <int> solutions; solutions.push_back(721); if(s == "123456") return steps; else { swap(s2[0], s2[1]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[1], s2[2]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[3], s2[4]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[4], s2[5]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[0], s2[3]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[1], s2[4]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } s2 = s; swap(s2[2], s2[5]); if(visited.find(s2) == visited.end() or steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); } return *(min_element(solutions.begin(), solutions.end())); } } int main() { string s; cin >> s; map <string, int> visited; cout << f(s, visited) << endl; return 0; }

Sample input:

321456

Sample output:

3

Improve this question
14
  • 2
    Maybe I'm just missing it, but I'm not seeing any recursive calls. Commented Nov 12, 2014 at 19:50
  • 2
    Step through the code, line by line, in a debugger to see what's happening. Commented Nov 12, 2014 at 19:52
  • 1
    Are you sure the recursive calls are "never-ending"? To me, it looks like your brute force solution to this problem quickly grows out of control and won't finish in a timely manner. I think you simply need a smarter algorithm. Commented Nov 12, 2014 at 20:08
  • 1
    @TomislavToplak It's not "repeating randomly", but it is repeating. Your algorithm doesn't keep track of minimum steps to a certain state, so it checks every possible state over and over again from every possible PREVIOUS state, even when it is not needed. In short, your algorithm is dumb. Looks like O(a^n) complexity, which means that even for small inputs you will see very very long run times. Commented Nov 12, 2014 at 20:38
  • 1
    I did give you advice - you have to remember the states you enter so you don't enter them again unnecessarily. For instance, if I reach the state "345612" in 3 steps, then in some other path I reach it in 5 steps, you can totally discard that path as a possibility, instead of following it to its conclusion (which is what you do right now). Commented Nov 12, 2014 at 21:04

2 Answers 2

Reset to default
3

The problem is that visited is passed by value. If you change it in a recursive call, once you return, you loose this change, as if you'd visited nothing.

Try with argument passed by reference the following: 

int f(string s, map <string, bool>& visited, int steps = 0) // & in the dfinition of f

For me it returns 5. I don't know f it's correct value, but there is an end to the recursion

Edit:

I've analysed this recursive algorithm:

  • each if correspond to a potential alternative move.
  • each further recursion coresponds to trying a move.
  • a succession of moves correspond to a succession of recursive calls
  • when passing by value, visited acumulates all the alteratives considered in the previous levels. But not necessarily those of the succesion of moves played. This will result in ignoring potential moves that did not yet lead to a solution.
  • when passing by reference, all previously visited nodes will be accumulated. Again, this will result in ignoring potential moves. However the ignored nodes did previously conduct either to a solution or a dead-end. Ignoring them will not ignore potential solutions, but simply might nof find out that there a shorter paths.
  • the right way would be to pass by value, but reinitalize the visited for each alternative.
  • the algorithm then would tests all possible non cycling succession of moves, using a depth first approach.
  • Your puzzle has 6 items, that can be arranged in 720 ways, but your algorithm seems to explore each of this combination the full possible set of combinations. Thats over half a million recursive combinations.
  • Unfortunately, the alogrithm is very expensive: lots of vector and map copies need to be done and memory needed. It took almost several minutes minutes for the 4000 first attempts, and due to memory consumption, it goes slower as it makes progresses ! In conclusion, the run will need several hours

Now I propose an easy trick that is called pruning: we will keep a trace of the shortest number of moves leding to the solution. Whenever in our exploration we come to more steps than this shortest path, we don't continue to search.

I've done two other changes: for one, I use a loop to explore the alternatives, because I'm to lazy to copy almost the same code several times. I did get rid of the vector of solutions, just keeping trace of the smallest number of steps in another way: 

int f(string s, int &sh, map <string, int> visited, int steps = 0) { if (steps >= sh) // THIS IS THE KEY: PRUNING !!! return INT_MAX; static vector <pair<size_t, size_t>>possible_swaps{ { 0, 1 }, { 1, 2 }, { 2, 3 }, { 4, 5 }, { 0, 3 }, { 1, 4 }, { 2, 5 } }; // yes if (s == "123456") { // solution found !! if (sh > steps) // check if it's the shortest solution for later pruning sh = steps; return steps; // in any case, return the number of steps found } else { int smin = INT_MAX; // just keep trace shortest number of steps in this iteration so far for (pair<size_t, size_t> sw : possible_swaps) { // try possible swaps string s2 = s; swap(s2[sw.first], s2[sw.second]); if (visited.find(s2) == visited.end()) { map <string, int> testvisited = visited; // attention: we work on a temporary so to keep visited unchanged, for the next loops. testvisited[s2] = true; int stp = f(s2, sh, testvisited, steps + 1); // Recursion if (stp < smin) // if it's the shoretst alternative smin = stp; // keep track of it } } return smin; // return the shortest nmber of steps in iteration. } }

Then in main() you just have to call, using an initialized variable that shall contain the shortest path found so far accross all the recursion: 

... int shortest = INT_MAX; cout << "Result: "<<f(s, shortest, visited) << endl;

For the records, this time I found 3.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I think that passing by value is correct in this case. If you pass by reference, the first recursive call will populate visited with a bunch of trues, which would then cause future calls to ignore those as possible paths (resulting in a faster, yet incorrect result)
Yes, I have tried that. But then the problem is if i make the visited map global, I won't get the minimal number of steps since there are more ways to get to that point.
Thanks for finding out what really happened in the recursion, as you have probably seen I already got the idea that i should use a map with string and int not string and bool. Thanks again anyway.
1

Instead of map <string, bool> visited, you should use a map <string, int>& visited (note the pass by reference).

Then you can change your if statements to:

if(visited.find(s2) == visited.end() || steps < visited[s2]) { visited[s2] = steps; solutions.push_back(f(s2, visited, steps + 1)); }

This lets lets your paths at all depths convey some path information to each other.

Note that you could probably optimize further by using an iterative solution & breadth first search, but this should be good enough to finish running sometime in our lives :)

Improve this answer

4 Comments

I was waiting for you to write an actual answer and not a comment, so i can approve it! Got the idea from your comment and already did the coding.
@TomislavToplak If you want an even faster run time, you can look into a Bidirectional search, though I doubt your assignment would call for that.
The teacher mentioned using bfs after he failed trying it this way, but I wanted to do it this way even though it isn't the optimal way but anyway I was persistent and now did it. It's good to stand out to the teacher and do it another way. My next assignment is to print out the swaps.
@Tomislav This technique is fairly common. It is known as memoization and it can be used with any pure function. Also for future reference, please don't edit the code in your questions when you find the solution; this makes it harder for future viewers to understand the original problem. Rather if you think access to a working implementation would be helpful to others, put in a new answer (you can answer your own question).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.