[Exercise] Max Swaps

arithma · 2012-08-16T13:40:48+00:00

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...

Joe

@arithma: how's that a counter example?

Correct me if I'm wrong but:

XXOXOXOX 2

XXXOOXOX 1

XXXXOOOX 0

The result is 4 following geek's method. Am I missing something?
I think the following is a better counter example:

XXXOOOXXOXXOXX 2

Ra8

@arithma and @rahmu

if we can swap anywhere this is better:

XXOXOXOX, 2
XXXXOXOO, 1
XXXXXOOO, 0

result =5

anyway I think rahmu's counter example is better

arithma

Xxoxoxox 2
Oxoxxxox 1
Oooxxxxx 0

arithma

Btw, better in what sense. A counter example is a counter example.
For what it's worth, I think my example is one of the shortest possible.

Joe

Bikeshedding moment
geek's method (as shown by Ra8) yields the same result as yours, which is 5. The example I gave shows it failing.

That said, I cannot find a solution to your problem beyond brute forcing. Oh wait I got one thing:

if nbrOfSwaps > nbrOfXinTheString:
    return nbrOfXinTheString
else:
    bruteforce()

arithma

geek's method (as shown by Ra8) yields the same result as yours, which is 5. The example I gave shows it failing.

I would appreciate a sliver of humility, especially when one is wrong.
Geek's algo would result in the following under left-to-right discovery of X's:

XXOXOXOX
XXXOOXOX
XXXXOOOX

This shows that abiding by the algorithm can result in wrong results. I suppose you can understand why this shows the algorithm is wrong.

As for your solution rahmu, it is condescending and arrogant. I am not a fan. Not all bruteforce algorithms are equal anyway.

arithma

It passes the trivial tests, but I am not 100% yet.

#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;
}

Joe

Wow why the aggressiveness arithma? What you find "condescending and arrogant" is my own admission of failure at doing anything meaningful in this exercise.

I didn't say bruteforcing was easy or but it is a little trivial. And that's not a bad thing. I came up with the following (commented to the best I know how to).

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

arithma

Sorry rahmu, but that "better counter example" mandated that the cave man take control.
Your solution shows a lot of python fu, and I like it. It also serves as a good base to measure other solutions against. It is much more probably correct than any other clever solution that may suffer from many slips.
I am trying to come up with a counter example for my code, I know something is off, but can't seem to extract that counter example out. Counter examples usually steer solutions in the right direction, in spite of being largely a hit-miss thing.

nader-sleiman

Purpose : Confirming Arithma's attempt to fail Geek's concept., however it can be modified a bit to make it work ( i hid that part though, it's a test for you).
Why? : Trolling + making the test easier for you.
Language : : Java
Algorithm : : w.e geek said.

/**
 *
 * @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.

arithma

There's a lot to be improved with the naive solution. It takes forever to work over a string of length 20 and only 5 swaps.

A few things I've been thinking about that may (not necessarily) help others into some insight about the exercise:
- O's on the sides are irrelevant.
- 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.
- 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).

geek

@arithma: From a technical perspective, your example is not a counter one. Since the way of selecting the candidate X was not fully specified, all valid choices should be considered---in a non-deterministic fashion---when evaluating an example. The goal of a counterexample was to show that picking the _longest_ initial sequence is a bad choice.

Feed ("XOXXOOXXXOOOXXXX", 2) to your program, you get 6 instead of 7.
Feed ("XXX", 1), it loops endlessly.

I think these are errors in the implementation. The approach looks good: instead of just considering the longest initial sequence, you process them all by feeding on the sides with the furthest X's.

You could experiment with picking the X with the largest number of O's separating it from the current sequence, and swapping it with the side that has the shortest sequence of O's adjacent to it.

@Nader.Sleiman: I would love to see that _small bit_ of modification (bluff) you're hiding. What was proposed is a method/way; neither a concept, which is a more abstract thing, nor an algorithm.

arithma

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).

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.

Compare with:
Pick the longest sequence of X's and then for each X not in the sequence try swapping it with an adjacent O.

Never the less, I am convinced that conceptually.

I found a polynomial solution, will post soon.

arithma

So here's the promised polynomial time solution:

//
//
//  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;
}

arithma

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).

At this point I had no idea where to continue from.
This exercise has actually made me more aware of the technique I use for solving logical problems. The difficult thing about optimization is that exhaustive search already solves the problem. You are left in an infinite? graph of logical connectives that you can walk through from multiple nodes. That's the closest thing I can describe of my process at the moment.
From the above points, I was able to use point (1) and point (2). (3) was more of an occasional observation, but wasn't strong enough. However what I was able to salvage out of it is that X's are more valuable on the inside rather than on the edges, which is intuitive.
From (1), I immediately trimmed O's on the sides.
A little explanation about (2). The whole problem relies on connectedness. X's on the sides can only extend other groups of X's. Hence they are more valuable on the inside between other groups.
From (2), it is possible to see that there are (maxSwaps + 1) ways to select X's to swap into the inside. Ie (0 X's from left, MaxSwaps from the right), (1 X from left, MaxSwaps-1 from the right) and so on till (MaxSwaps from left and none from the right).
Each of these (MaxSwaps+1) possibilities creates a new problem.
Of course, again, after we have removed MaxSwaps X's from the sides, we also need to trim the remaining O's.
To move on, we note one thing, our swapping operation has become a replace operation. Replace O's with X's. We wouldn't want to replace X's with X's, because that would always lead to poorer results.
Given the series of X's and O's in alternation, we'll do the following.
Start consecutively with a group of O's. Continue filling following O groups to its right. If there are remaining X's with no O's, then just add that to the sum of the spread. We get our subsubmax.
Our submax is for each of the configuration of left X's and right X's.
Our max is the max of all of these.