Re: Sorting a row of letters, using a blank space, with some added rules

Hi again,

ThemePark wrote:
....


hehe... The fact that I coded it in 15 lines of code after reading
your problem! (note that I said that the main recursive method
could be done in 15 lines of code, note the whole program).

:)


which is why you add, as I wrote, a check that verifies that
you're not recursing too deeply: if you're examinating a position
that you already examined (with a similar or highest cost), then
you stop recursing that path (for you know, for sure, that a
solution costing less has already been tried or is beeing tried).

Here's a small program you can cut'n'paste that finds the
minimal max_depth assumes that there will always be
a solution in less than 200 moves (which is very generous
given the problem's constraints).

(Note that I use "final's" everywhere for it helps my
wonderfull IDE to give me very interesting informations
due to its very elaborate code-analysis engine... But YMMV).

(Note also that I used an 120 columns wide editor to
code this small examples... YMMV and complaints to
/dev/null).

:)

This is working Java 1.5 code solving your problem:

--- BEGIN CUT HERE ---
import java.util.Map;
import java.util.HashMap;

public final class SwapLetters {

    private static final int MAX = Integer.MAX_VALUE;
    private static final int[][] moves = new int[][] {
        {1, 2},{1, 4},{1, 6},{2, 3},{2, 5},{3, 4},{3, 6},{4, 5},{5, 6},
    };

    private final Map<String, Integer> m;
    private int max_depth;

    public static void main(final String[] args) {
        final SwapLetters sl = new SwapLetters();
        final String source = "BCEAD ";
        final String target = "ABCDE ";
        System.out.println("Minimal cost is: " + sl.min(target, source,
0));
    }

    public SwapLetters() {
        m = new HashMap<String, Integer>();
        max_depth = 200;
    }

    private int min(final String target, final String s, final int
cost) {
        if (cost >= max_depth || (m.containsKey(s) && m.get(s) <= cost)
) {
                return MAX;
        }
        if (s.equals(target)) {
            max_depth = cost;
            return cost;
        }
        m.put(s, cost);
        int min = MAX;
        for (final int[] iar : moves) {
            if (s.charAt(iar[0] - 1) == ' ' || s.charAt(iar[1] - 1) ==
' ') {
                final int swapcost = min(target, swap(s, iar[0] - 1,
iar[1] - 1), cost + 1);
                min = swapcost < min ? swapcost : min;
            }
        }
        return min;
    }

    private static String swap(final String s, final int l, final int
r) {
        return "" + s.substring(0, l) + s.charAt(r) + s.substring(l +
1, r) + s.charAt(l) + s.substring(r + 1);
    }

}
--- END CUT HERE ---

The recursive method contains 16 lines (18 with declarations) and that
can be reduced if needed (but it's not an obfuscation contest, is it?
:)

Every time a solution is found, the max_depth is lowered (we know
for sure it's unnecessary to try a path costing more than the solution
we found).

Note that here this only computes the minimal number of moves
needed, but that should give you a good starting point.

If you want to keep track of the moves, it's not much harder:
instead of associating a cost to the string you're processing
(Map<String, Integer>), you can associate the list of moves
made so far (eg Map<String, List<Integer>). The cost hence
simply becomes the size of the List<Integer> (and each integer
in the list represent the number of the move made [eg '2' for
"swap 1 and 6"]).

To see the algorithm at work, you may want to insert
System.out statements that adjusts the output given
the cost so far... (for testing, you'll also probably want
to lower the MAX_DEPTH value).

This could look, for example, like this:

cost 0 "BCEAD "
  cost 1 " CEADB"
    cost 2 "C EADB"
      cost 3 " CEADB"
         (dropping this path because: inferior cost exists)
      cost 3 "CE ADB"
        cost 4 "C EADB"
         (dropping this path because: inferior cost exists)
..
..
..

As you can see it is not "continously going from one position
to another position and back again" for as soon as it
encounters a position (eg " CEADB") it checks the cost (3)
and notice that the same position with a lower cost (1) is
already being examinated.

If the method gives back Integer.MAX_VALUE then it means
either your problem has no solution or that the max_depth
given is too low (try changing the 200 to 4 to see what
happens).

As I said previously, this is a simple recursive brute-force approach
(with some precaution taken as to not recursive indefinitely or
unnecessarly) that works given your constraints.

Now wether this problem is NP-hard (like the TSP you cited) or
not is another matter :)

Hope it helps,

  Alex (that likes to eat recursivity at breakfast ;)

P.S : If you like puzzle and optimization/minimization/maximization
problems, here's a famous one (many variations exists)... It is
interesting to solve both by hand and by writing a small
program (recursive of course).

5 pirates have a treasure of 100 gold pieces to split up
after a long and profitable trip. The pirates are ranked
by seniority and it is always the most senior pirate who
decides how to divide up the booty amongst himself and
any remaining pirates. However, the pirates are
democratic: if the most senior pirate does not get at
least 50% of the vote (including himself), then he is
killed and the process repeats itself with the nextmost
senior pirate proposing the breakup. The pirates are all
completely rational and know that their compatriots are
also completely rational. All of the pirates use the
following priorities the drive their voting: 1. They don't
want to get killed 2. They want to get the most money
possible 3. They want to kill other pirates. How does the
most senior pirate divide up the treasure such that he
keeps as much as he possibly can for himself?