be.dhaval
BAN USERvoid
car_parking_order(vector<char> currentOrder, vector<char> desiredOrder) {
unordered_map<char, int> umap;
int eindex = -1;
for (int i = 0; i < currentOrder.size(); i++) {
// maps car to index position for current order
umap.insert(make_pair(currentOrder[i], i));
if (currentOrder[i] == 'e') {
eindex = i; // remember the index where empty element in current order
}
}
for (int i = 0; i < currentOrder.size(); i++) {
cout << currentOrder[i] << " ";
}
cout << "\n";
int numSwap = 0;
for (int i = 0; i < currentOrder.size(); i++) {
char desiredCar = desiredOrder[i];
if (desiredCar != currentOrder[i] && currentOrder[i] != 'e') {
// if we find eindex at its desired position then first swap the current
// eindex ('e') with current unordered element and update current eindex as
// current position.
// when we update current element we need to update umap to reflect that.
if (desiredOrder[eindex] == 'e') {
char temp = currentOrder[i];
currentOrder[i] = 'e';
umap[currentOrder[i]] = i;
currentOrder[eindex] = temp;
cout << "\n";
}
// move around empty positions until empty position moves to its correct
// place, get the corresponding desired element for the empty index and
// look for its index in current element to swap it..
while (desiredOrder[eindex] != 'e') {
char desired = desiredOrder[eindex]; // 6
int swapPos = umap[desired]; // position of 6 in current order
currentOrder[swapPos] = 'e'; // position of 6 made empty
umap[currentOrder[swapPos]] = swapPos;
currentOrder[eindex] = desired; // position of empty made 6
umap[currentOrder[eindex]] = eindex;
eindex = swapPos;
for (int j = 0; j < currentOrder.size(); j++) {
cout << currentOrder[j] << " ";
}
numSwap++;
cout << "\n";
}
}
}
cout << "number of swaps:" << numSwap << "\n";
}
Resubmitting with code brackets.
/**
* Created by dhavalp on 9/1/16.
*/
public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}
if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}
strBuilder.setCharAt(index, str.charAt(i));
// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}
permutationSet(strBuilder, str, index + 1, soFarMap);
if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}
public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);
}
}
- Basic logic is to create permutation set but just add the additional condition given to avoid those possibilities of consecutive more than 2 'c' and allow only one instance of 'b'.
public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}
if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}
strBuilder.setCharAt(index, str.charAt(i));
// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}
permutationSet(strBuilder, str, index + 1, soFarMap);
if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}
public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);
}
}
Repjoycejflora, Android Engineer at ABC TECH SUPPORT
I am excited about cooperation and interesting projects. Last year I work for a person who provides the black magic ...
Repjonej8821, Blockchain Developer at Alliance Global Servies
I am EbonyTuckson .I am a teacher who works in High school. I work during school hours but may also ...
Basic logic is:
- be.dhaval December 28, 2016currentCar[i] - input.
desiredCar[i] - output.
1) Map car to position based on the input order (umap) and remember empty index.
2) Now loop through the input order cars.
For each entry check desiredCar[i] and if it is not same as currentCar[i] and
currentCar[i] is not "-1" then we need to keep swaping empty index with currentCar
until empty index reaches to its desired position.
If empty index is found to be at desired position and we still have cars which are not
at the appropriate position then first swap the empty car position with current position
to allow us to move the current car to its appropriate slots.