Given a string of X's and O's and a maximum number of swaps, determine the longest possible sequence of X's after swaps.
"OXXOX", 25 swaps: 3. You can only get 3 X's consecutively.
"OXXOX", 25 swaps: 3. You can only get 3 X's consecutively.
if nbrOfSwaps > nbrOfXinTheString:
return nbrOfXinTheString
else:
bruteforce()
I would appreciate a sliver of humility, especially when one is wrong.geek's method (as shown by Ra8) yields the same result as yours, which is 5. The example I gave shows it failing.
#include <iostream>
#include <string>
using namespace std;
void swap(string & s, int i, int j)
{
string::value_type tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
int maxSwapsForBlock(string state, int i, int j, int maxswaps);
int reverseMaxSwapsForBlock(string state, int i, int j, int maxswaps){
string reverse = string(state.rbegin(), state.rend());
int ri = state.size()-i-1;
int rj = state.size()-j-1;
return maxSwapsForBlock(reverse, rj, ri, maxswaps);
}
int maxSwapsForBlock(string state, int i, int j, int maxswaps){
int swaps = 0;
for(int k = 0; k < i && swaps < maxswaps; k++){
if(state[k] == 'O') continue;
while((i > k) && (state[i] == 'X')){
--i;
}
if(state[i] == 'O' && i != k){
swap(state, i, k);
swaps++;
}
}
while(i > 0 && state[i-1] == 'X')
i--;
if(swaps == maxswaps){
return j-i;
}
else {
return reverseMaxSwapsForBlock(state, i, j, maxswaps - swaps);
}
}
int maxSwaps(string s, int maxswaps){
int max = 0;
int i = 0;
while(i < s.size()){
if(s[i] == 'O'){
i++;
continue;
}
int j = i;
while(j < s.size() && s[j] == 'X') j++;
int spread = maxSwapsForBlock(s, i, j, maxswaps);
int rspread = reverseMaxSwapsForBlock(s, i, j, maxswaps);
max = std::max(max, std::max(spread, rspread));
i = j;
}
return max;
}
int main(int argc, const char * argv[])
{
// insert code here...
std::cout << maxSwaps("XXOXOXX", 2) << endl;
return 0;
}
import itertools
import sys
def swaps_gen(s):
"""This generator yields all the possible outcome of applying one swap
to the input string
"""
x_positions = [index for index, value in enumerate(s) if value == "X"]
o_positions = [index for index, value in enumerate(s) if value == "O"]
for x in x_positions:
for o in o_positions:
swapped_list = list(s) # copy string so I can modify it
swapped_list[x], swapped_list[o] = swapped_list[o], swapped_list[x]
yield ''.join(swapped_list)
def flatten(l):
"""flatten one level. [[a], [b, c]] --> [a, b, c]
"""
return itertools.chain.from_iterable(l)
def max_x_after_swap(s, n):
"""repeat the generate swaps_gen n times.
I used a set() to avoid duplicates.
Then returns the highest number of consecutive "X"s it finds.
"""
outcomes = set([s])
for _ in range(n): # repeat n times
outcomes = set(flatten(map(swaps_gen, outcomes)))
return max(nbr_of_consecutive_x(x) for x in outcomes)
def nbr_of_consecutive_x(s):
"""return the number of consecutive "X"
"""
return max(len(list(v)) for k, v in itertools.groupby(s) if k == "X")
def main():
instring = "".join(flatten(zip("X"*10, "O"*10)))
swaps_nbr = 4
print(max_x_after_swap(instring, swaps_nbr))
main()
Outcome:>>> 9
/**
*
* @author NaderSl
*/
public class MaxSwap {
private static int maxCount, nextOIdx, nextXReplacement;
/**
* **********************Control Fields ************
*/
private final static String xoString = "XXXOXOXOX";
private final static int swaps = 25;
/**
* ********************************************************
*/
public static void main(String[] argV) {
System.out.println("The longest X sequence consisting of : " + getLongestXSeq(new Integer(swaps), xoString.toCharArray()) + " consecutive chars using " + swaps + " swaps.");
}
/**
* @desc recursive
*
* @param swaps max allowed swaps
* @param xoString the XO String
* @return number of X's in the longest x's sequence found.
*/
public static int getLongestXSeq(int swaps, char... xoString) {
if (swaps == 0) {//reached swaps limit
System.out.println("Final pattern " + new String(xoString));
return maxCount;
}
grabNextIndices(xoString);
if (nextXReplacement == -1) {//bypassed swapping constraints.
System.out.println("Final pattern " + new String(xoString));
return maxCount;
}
//swap chars
char temp = xoString[nextOIdx];
xoString[nextOIdx] = xoString[nextXReplacement];
xoString[nextXReplacement] = temp;
return getLongestXSeq(swaps - 1, xoString);
}
/**
*
* @param xoString the XO String grabs the indices of the next targeted O
* and the X to be swapped with.
*
*/
public static void grabNextIndices(char... xoString) {
int nextXIdx = 0, count = 0;
maxCount = 0;//reset maxCount.
/*
* find the index of the longest X-sequence
*/
for (int i = 0; i < xoString.length; i++) {
if (xoString[i] == 'X') {
count++;
} else {
if (count > maxCount) {
nextXIdx = (i - count);
nextXIdx = nextXIdx < 0 ? 0 : nextXIdx;//clamp val at 0.
maxCount = count;
}
count = 0;
}
}
/*
* pick the 'O' before the X-sequence incase the index of it is > 0 ,
* otherwise grab the O right after the sequence.
*/
nextOIdx = nextXIdx > 0 ? nextXIdx - 1 : nextXIdx + maxCount;
for (int i = 0; i < xoString.length; i++) {
/*
* constraints of the X to be replaced : 1- not belonging to the
* longest found X-Sequence; 2- value of it should be 'X';
*/
if ((i < nextXIdx || i > nextXIdx + maxCount) && xoString[i] == 'X') {
nextXReplacement = i;
return;
}
}
nextXReplacement = -1; // if no X replacement was found, this would also indicates the end of the swapping method before the swaps are out.
}
}
Random outputs: #0 : [xoString = "XXXOXOXOX"] // here is where its currently failing
Output:
Final pattern XXXXXOOO[X]
The longest X sequence consisting of : 5 consecutive chars using 25 swaps.
#1[xoString = "OXXOX"]
Output:
Final pattern XXXOO
The longest X sequence consisting of : 3 chars.
#2[xoString = "OXXXOXXXXOXXXXXOXXXXXOXXOOXOXXXOO"]
Output:
Final pattern XXXXXXXXXXXXXXXXXXXXXXXOOOOOOOOOO
The longest X sequence consisting of : 23 chars.
#3[xoString = "XXO"]
Output:
Final pattern XXO
The longest X sequence consisting of : 2 chars.
Taken literally, my interpretation is correct. Nondeterminism should not be specified implicitly. What if it was indeed the case that you really meant: "Any X such that and that.." would do.Pick the longest sequence of X's and swap one of its adjacent O's with an X that is not already in the sequence. Repeat until you no longer can. Find a counter-example (you can).
//
//
// main.cpp
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void swap(string & s, int i, int j)
{
string::value_type tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
string trim(string s){
string::iterator begin = s.begin();
string::iterator end = s.end();
while(begin < end && *begin == 'O') begin++;
while(begin < end && *(end-1) == 'O') end--;
return string(begin, end);
}
struct item {
char c;
int n;
};
vector<item> tokenize(string s){
vector<item> items;
string::iterator itr = s.begin();
while(itr != s.end()){
{
string::iterator Xstart = itr;
while(itr < s.end() && *itr == 'X') itr++;
int count = itr - Xstart;
if(count > 0){
item i = { 'X', itr - Xstart };
items.push_back(i);
}
}
{
string::iterator Ostart = itr;
while(itr < s.end() && *itr == 'O') itr++;
int count = itr - Ostart;
if(count > 0){
item i = { 'O', itr - Ostart };
items.push_back(i);
}
}
}
return items;
}
int maxInsertions(string s, int insertions){
s = trim(s);
int max = 0;
vector<item> items = tokenize(s);
vector<item>::iterator start = items.begin();
while(start != items.end()){
int used = 0;
int curr = 0;
vector<item>::iterator walker = start;
while(walker != items.end() && (walker->c == 'X' || (used + walker->n) <= insertions)) {
if(walker->c == 'O')
used += walker->n;
curr += walker->n;
walker++;
}
int remaining = insertions - used;
curr += remaining;
max = std::max(max, curr);
start++;
while(start != items.end() && start->c == 'O') start++;
}
return max;
}
int maxSwaps(string s, int maxswaps){
s = trim(s);
// guard so that iterators don't fall out of bounds
int count = 0;
for(string::iterator itr = s.begin(); itr < s.end(); itr++)
if(*itr == 'X')
count++;
if(count <= maxswaps)
return count;
// maxswaps < count, iterators will not fall out of bounds
int max = 0;
for(int left = 0; left <= maxswaps; left++){
int right = maxswaps - left;
string::iterator begin = s.begin(), end = s.end();
for(int i = 0; i < left; i++){
while(*begin == 'O') begin++;
begin++;
}
for(int i = 0; i < right; i++){
while(*(end-1) == 'O') end--;
end--;
}
string x(begin, end);
int curr = maxInsertions(x, maxswaps);
max = std::max(max, curr);
}
return max;
}
int main(int argc, const char * argv[])
{
// insert code here...
std::cout << maxSwaps("XXX", 1) << endl;
return 0;
}
At this point I had no idea where to continue from.A few things I've been thinking about that may (not necessarily) help others into some insight about the exercise:
1 - O's on the sides are irrelevant.
2 - Intuitively, X's on the edges are the ones that should be swapped to the inside. This is in a greedy sense, but I'm not sure how greedy we're allowed to go yet.
3 - X's from the right side are more usefully moved to the inner left side (at least not just packed away into the nearest X).