[try Beta version]
Not logged in

 
Minimum moves to rearrange one string into another

Feb 18, 2017 at 8:10am
Code Apperentice (229)
I want to rearrange string a into string b in the minimum amount of moves. Both strings are of the same size. Groups of letters can be moved

For example:

Input:
5
3 2 1 4 5
2 3 1 4 5
Output:
3

You can cut the string a, [3], [2], [1, 4, 5], and then rearrange it into [2], [3], [1, 4, 5], which is string b.
Last edited on Feb 18, 2017 at 9:09am
Feb 18, 2017 at 9:04am
Mantorr22 (152)
You can do it like this, and your example needs just one move to accomplish everything.

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
 
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <assert.h>

typedef std::vector<std::string>::size_type size_t_t;

size_t_t effectiveFind(std::string val, const std::vector<std::string> &v1, const std::vector<std::string> &v2)
{
	for(std::vector<std::string>::size_type i = 0; i < v1.size(); i++)
	{
		if(v1[i] != v2[i])
		{
			if(v2[i] == val) return static_cast<size_t_t>(i);
		}
	}

	assert(NULL); return 0;
}

std::string addSpace(std::string val) {return (val += ' ');}

std::string rearrange(std::string a, std::string b, size_t_t &numMoves)
{
	std::string val;
	size_t_t position;
	numMoves = 0;

	std::vector<std::string> v1;
	std::vector<std::string> v2;

	std::istringstream iss1(a);
	std::istringstream iss2(b);

	while(iss1 >> val) v1.push_back(val);
	while(iss2 >> val) v2.push_back(val);

	assert(v1.size() && v2.size());
	assert(v1.size() == v2.size());

	std::vector<std::string>::size_type i;
	for(i = 0; i < v1.size(); i++)
	{
		assert(std::count(v1.begin(), v1.end(), v1[i]) == std::count(v2.begin(), v2.end(), v1[i]));
		assert(std::count(v1.begin(), v1.end(), v2[i]) == std::count(v2.begin(), v2.end(), v2[i]));
	}

	for(i = 0; i < v1.size(); i++)
	{
		if(v1[i] != v2[i])
		{
			position = effectiveFind(v1[i], v1, v2);
			std::swap(v2[i], v2[position]); 
			numMoves++;
		}
	}

	std::transform(v2.begin(), v2.end() - 1, v2.begin(), addSpace);

	return std::accumulate(v2.begin(), v2.end(), std::string());
}

int main()
{
	size_t_t numMoves;

	// Emptying these strings mean you have to input them manually
	std::string line1 = "3 2 1 4 5"; // "3 2 1 4 5"
	std::string line2 = "2 3 1 4 5"; // "1 3 2 5 4"

	std::cout << "Enter two strings : " << std::endl;

	if(!line1.size() || !line2.size())
	{
		std::getline(std::cin, line1);
		std::getline(std::cin, line2);
	}
	else
	{
		std::cout << line1 << std::endl;
		std::cout << line2 << std::endl;
	}

	line2 = rearrange(line1, line2, numMoves);

	std::cout << std::endl;
	std::cout << line1 << std::endl;
	std::cout << line2 << std::endl;
	std::cout << numMoves << std::endl;

	return 0;
}
Edit & Run


It is easy to understand though, feel free to ask if you have any questions.

Enter two strings :
3 2 1 4 5
2 3 1 4 5

3 2 1 4 5
3 2 1 4 5
1

http://rextester.com/HGY20186
Last edited on Feb 18, 2017 at 9:09am
Feb 18, 2017 at 9:13am
Code Apperentice (229)
How do you also get the number of groups it makes from splitting?
Feb 18, 2017 at 9:14am
Mantorr22 (152)
How do you also get the number of groups it makes from splitting?

Sorry friend, what do you mean by that?
Feb 18, 2017 at 9:19am
Code Apperentice (229)
O, I just wasted your time, I reread my question and I poorly worded the question, sorry. The output is three because you have to split the string first then rearranged, as well as minimum number of moves I want the minimum number of groups too. The output should be 3 1
Feb 18, 2017 at 9:22am
Mantorr22 (152)
The output should be 3 1

I don't understand these numbers. Could you please clarify?
Feb 18, 2017 at 10:31am
Mantorr22 (152)
Yeah, it is not that much of a challenge though. You just need to add some features so that the program can recognize string groups.

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <assert.h>

typedef std::vector<std::string>::size_type size_t_t;

size_t_t effectiveFind(std::string val, const std::vector<std::string> &v1, const std::vector<std::string> &v2)
{
	for(std::vector<std::string>::size_type i = 0; i < v1.size(); i++)
	{
		if(v1[i] != v2[i])
		{
			if(v2[i] == val) return static_cast<size_t_t>(i);
		}
	}

	assert(NULL); return 0;
}

std::string addSpace(std::string val) {return (val += ' ');}

struct groupRecord
{
	groupRecord(size_t_t _pos, std::string _val) : pos(_pos), val(_val) {}

	size_t_t pos;
	std::string val;
};

void insertProperPosition(std::vector<groupRecord> &target, std::string result, size_t_t position)
{
	std::vector<groupRecord>::iterator it;
	for(it = target.begin(); it != target.end() && it->pos < position; it++);

	if(it == target.end()) target.push_back(groupRecord(position, result));
	else target.insert(it, groupRecord(position, result));
}

std::string rearrange(std::string a, std::string b, size_t_t &numMoves, size_t_t &numGroups)
{
	std::string val;
	size_t_t position;
	numMoves = 0;
	numGroups = 0;

	std::vector<std::string> v1;
	std::vector<std::string> v2;

	std::istringstream iss1(a);
	std::istringstream iss2(b);

	while(iss1 >> val) v1.push_back(val);
	while(iss2 >> val) v2.push_back(val);

	assert(v1.size() && v2.size());
	assert(v1.size() == v2.size());

	std::vector<std::string>::size_type i;
	for(i = 0; i < v1.size(); i++)
	{
		assert(std::count(v1.begin(), v1.end(), v1[i]) == std::count(v2.begin(), v2.end(), v1[i]));
		assert(std::count(v1.begin(), v1.end(), v2[i]) == std::count(v2.begin(), v2.end(), v2[i]));
	}
	
	std::vector<groupRecord> v1_a;
	std::vector<groupRecord> v2_a;

	std::vector<std::string> v1_b;
	std::vector<std::string> v2_b;

	if(std::equal(v1.begin(), v1.end(), v2.begin()))
	{
		numGroups = 1;
		numMoves = 0;

		std::transform(v2.begin(), v2.end() - 1, v2.begin(), addSpace);
		return std::accumulate(v2.begin(), v2.end(), std::string());
	}

	size_t_t group_size, j, k;
	for(group_size = v1.size() - 1; group_size >= 2; group_size--)
	{
		for(i = 0; i <= v1.size() - group_size; i++)
		{
			if(!v1[i].empty())
			{
				for(j = 0; j <= v2.size() - group_size; j++)
				{
					if(!v2[j].empty())
					{
						if(std::equal(v1.begin() + i, v1.begin() + i + group_size, v2.begin() + j))
						{

							std::transform(v1.begin() + i, v1.begin() + i + group_size - 1, v1.begin() + i, addSpace);
							std::transform(v2.begin() + j, v2.begin() + j + group_size - 1, v2.begin() + j, addSpace);

							insertProperPosition(v1_a, std::accumulate(v1.begin() + i, v1.begin() + i + group_size, std::string()), i);
							insertProperPosition(v2_a, std::accumulate(v2.begin() + j, v2.begin() + j + group_size, std::string()), j);

							std::fill(v1.begin() + i, v1.begin() + i + group_size, std::string());
							std::fill(v2.begin() + j, v2.begin() + j + group_size, std::string());
							
							numGroups++;
						}
					}
				}
			}
		}
	}

	for(i = 0; i < v1.size(); i++)
	{
		if(!v1[i].empty())
		{
			insertProperPosition(v1_a, v1[i], i);
		}

		if(!v2[i].empty())
		{
			insertProperPosition(v2_a, v2[i], i);
		}
	}

	std::cout << std::endl;

	for(i = 0; i < v1_a.size(); i++)
	{
		std::cout << v1_a[i].val << " ## ";
	}
	std::cout << std::endl;

	for(i = 0; i < v2_a.size(); i++)
	{
		std::cout << v2_a[i].val << " ## ";
	}
	std::cout << std::endl;

	numGroups += v1.size() - std::count(v1.begin(), v1.end(), std::string());

	assert(v1_a.size() && v2_a.size());
	assert(v1_a.size() == v2_a.size());

	for(i = 0; i < v1_a.size(); i++)
	{
		v1_b.push_back(v1_a[i].val); 
		v2_b.push_back(v2_a[i].val); 
	}

	for(i = 0; i < v1_b.size(); i++) 
	{
		if(v1_b[i] != v2_b[i])
		{
			position = effectiveFind(v1_b[i], v1_b, v2_b);
			std::swap(v2_b[i], v2_b[position]); 
			numMoves++;
		}
	}

	std::transform(v2_b.begin(), v2_b.end() - 1, v2_b.begin(), addSpace);

	return std::accumulate(v2_b.begin(), v2_b.end(), std::string());

}

int main()
{
	size_t_t numMoves;
	size_t_t numGroups;

	// Emptying these strings mean you have to input them manually
	std::string line1 = "3 2 1 4 5"; // "3 2 1 4 5"
	std::string line2 = "2 3 1 4 5"; // "2 3 1 4 5"

	std::cout << "Enter two strings : " << std::endl;

	if(!line1.size() || !line2.size())
	{
		std::getline(std::cin, line1);
		std::getline(std::cin, line2);
	}
	else
	{
		std::cout << line1 << std::endl;
		std::cout << line2 << std::endl;
	}

	line2 = rearrange(line1, line2, numMoves, numGroups);

	std::cout << std::endl;
	std::cout << line1 << std::endl;
	std::cout << line2 << std::endl;
	std::cout << numGroups << ' ' << numMoves << std::endl;

	return 0;
}
Edit & Run


Enter two strings :
3 2 1 4 5
2 3 1 4 5

3 ## 2 ## 1 4 5 ##
2 ## 3 ## 1 4 5 ##

3 2 1 4 5
3 2 1 4 5
3 1

http://rextester.com/PETP40773
Feb 18, 2017 at 10:41am
Code Apperentice (229)
Last thing, is there a way to just calculate the groups without actually rearranging the strings? I became intrigued after I made that initial mistake in my wording of the question
Feb 18, 2017 at 10:45am
Mantorr22 (152)
Last thing, is there a way to just calculate the groups without
actually rearranging the strings? I became intrigued after I made that
initial mistake in my wording of the question

I already gave the code you ask for, it is up to you how to implement it.
If you copy that challenge from somewhere, please provide the link.

Feb 18, 2017 at 1:17pm
jonnin (11471)
code aside, I think the answer is always 1 move per group. Getting there might be tricky, but I can't see any place where it would take more than 1.

Feb 18, 2017 at 1:21pm
Mantorr22 (152)
Code aside, I think the answer is always 1 move per group. Getting there might be tricky, but I can't see any place where it would take more than 1.

How about this? It takes two moves.

3 2 1 4 5
5 3 4 2 1

3 ## 2 1 ## 4 ## 5 ##
5 ## 3 ## 4 ## 2 1 ##

3 2 1 4 5
3 2 1 4 5
4 2
Feb 18, 2017 at 2:52pm
fasravo (7)
Hey, new to the forum.
Can I ask how people do it? I mean how they did everything, I don't understand what they are doing with the code.

By the way, I tested such a long string and it still performs marvelously.

"Enter two strings :
1 2 0 ax 3 5 100 0 C C++ 4 1 1 0 ax ax ax ax ax hello >
C C++ 1 2 0 ax ax ax 1 3 4 hello ax ax 5 0 ax 0 1 > 100

...

1 2 0 ax 3 5 100 0 C C++ 4 1 1 0 ax ax ax ax ax hello >
1 2 0 ax 3 5 100 0 C C++ 4 1 1 0 ax ax ax ax ax hello >
14 11"
Feb 18, 2017 at 3:02pm
jonnin (11471)
one move per substring, I meant, as in should be able concat all the substrings at the end and its done. Figuring out where each substring goes and how to slice it up front is the work, and getting the least # of substrings.


Last edited on Feb 18, 2017 at 3:03pm
Feb 19, 2017 at 2:14am
Code Apperentice (229)
Thanks for the help everryone
Topic archived. No new replies allowed.