Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: "Christian H. Kuhn" <qno-news@qno.de>
Newsgroups: de.comp.lang.java
Subject: Re: Rekursion bricht nicht ab
Date: Wed, 13 Apr 2016 20:44:16 +0200
Lines: 124
Message-ID: <dn7iceFt0j4U1@mid.individual.net>
References: <dmqm4qFkm0hU1@mid.individual.net> <neb2mi$m27$1@newsreader4.netcologne.de> <dmv3g8Fngq5U2@mid.individual.net> <neec9f$sgh$1@newsreader4.netcologne.de> <dn4chpF3vqkU1@mid.individual.net> <nej7v8$29p$1@newsreader4.netcologne.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Trace: individual.net D4FmHjClme2rUhXrdL9zowJjpNW9uzcbJRgv2PFpVRImC8/g0=
Cancel-Lock: sha1:9vm9wnETb12Z1WkqcjW8b2RRNVY=
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:38.0) Gecko/20100101 Thunderbird/38.7.2
In-Reply-To: <nej7v8$29p$1@newsreader4.netcologne.de>
Xref: csiph.com de.comp.lang.java:12933

Am 12.04.2016 um 18:32 schrieb Patrick Roemer:
> Responding to Christian H. Kuhn:
>> Am 10.04.2016 um 22:15 schrieb Patrick Roemer:
>>
>>> Also statt
>>
>>> [[a,b], [a,b], [b,a], [], []] => move b to empty [[b], [a,b],
>>> [b,a], [a], []]
>>
>>> sowas wie
>>
>>> {[a,b] -> 2, [b,a] -> 1, [] -> 2} => move b to empty {[a] -> 1, [b]
>>> -> 1, [a,b] -> 1, [b,a] -> 1, [] -> 1}

> Da finde ich meinen Ansatz schöner. Du kannst eine "redundante" Stellung
> nach einem Zug gleich wegwerfen, ich muss den Zug gar nicht erst
> ausprobieren. :)

Hab ich dann auch mal ausprobiert, aber anders.

public final Vector<LSMove> getMoveList() {
        Vector<LSMove> moveList = new Vector<LSMove>();
        HashSet<Integer> startTubes = new HashSet<Integer>();
        for (int i = 0; i < boardSize; i++) {
            if (startTubes.contains(tubes.get(i).hashCode())) {
                continue;
            }
            startTubes.add(tubes.get(i).hashCode());
            HashSet<Integer> targetTubes = new HashSet<Integer>();
            for (int j = 0; j < boardSize; j++) {
                if (targetTubes.contains(tubes.get(j).hashCode())) {
                    continue;
                }
                targetTubes.add(tubes.get(j).hashCode());
                LSMove move = new LSMove(i, j);
                try {
                    isLegalMove(move);
                    moveList.add(move);
                } catch (LSBoardBadSizeParameterException |
LSBoardEmptyStartTubeException | LSBoardNoMoveAtAllException
                        | LSBoardFullTargetTubeException |
LSBoardDifferentColoursException e) {
                    // illegale Züge werden einfach nicht geaddet, keine
weitere Aktion nötig.
                }
            }
        }
        return moveList;
    }

Mit erstaunlichen Ergebnissen:

    public static void main(final String[] _args) throws Throwable {

        // Ohne Zugreduzierung: 499 ms, mit 864 ms.
        // LSBoard board = new LSBoard(4, 3, 2);
        // Vector<Vector<Character>> positionOneLevelOne = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'c', 'b')),
        // new Vector<Character>(Arrays.asList('a', 'a', 'c', 'c')),
        // new Vector<Character>(Arrays.asList('c', 'a', 'b', 'b'))));

        // Ohne Zugreduzierung: 39 ms, mit 33 ms.
        // LSBoard board = new LSBoard(3, 2, 2);
        // Vector<Vector<Character>> positionOne = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'b'))));

        // Ohne Zugreduzierung: 231 ms, mit 340 ms.
        // LSBoard board = new LSBoard(4, 4, 1);
        // Vector<Vector<Character>> positionTwentyLevelTwo = new
Vector<Vector<Character>>(
        // Arrays.asList(new Vector<Character>(Arrays.asList('a', 'b',
'a', 'c')),
        // new Vector<Character>(Arrays.asList('c', 'd', 'c', 'd')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'b', 'd')),
        // new Vector<Character>(Arrays.asList('a', 'b', 'c', 'd'))));

        // Ohne Zugreduzierung: 2496251 ms, mit 2270765 ms.
        LSBoard board = new LSBoard(4, 10, 2);
        Vector<Vector<Character>> positionOneLevelFour = new
Vector<Vector<Character>>(
                Arrays.asList(new Vector<Character>(Arrays.asList('a',
'b', 'c', 'd')),
                        new Vector<Character>(Arrays.asList('b', 'c',
'e', 'f')),
                        new Vector<Character>(Arrays.asList('f', 'g',
'e', 'h')),
                        new Vector<Character>(Arrays.asList('h', 'c',
'g', 'e')),
                        new Vector<Character>(Arrays.asList('b', 'h',
'i', 'g')),
                        new Vector<Character>(Arrays.asList('a', 'd',
'd', 'i')),
                        new Vector<Character>(Arrays.asList('f', 'a',
'i', 'j')),
                        new Vector<Character>(Arrays.asList('i', 'j',
'b', 'g')),
                        new Vector<Character>(Arrays.asList('j', 'e',
'a', 'j')),
                        new Vector<Character>(Arrays.asList('h', 'f',
'c', 'd'))));

        board.initializeBoard(positionOneLevelFour);
        long startTime = System.nanoTime();
        LSResult result = board.result();
        long endTime = System.nanoTime();
        long elapsedTime = (endTime - startTime) / 1000000;

        System.out.println("Lösung:");
        for (LSMove move : result.getOneShortestSolution()) {
            System.out.println(move.toString());
        }
        System.out.printf("Zeit: %1$d ms", elapsedTime);
    }

Es gibt wirklich Stellungen, bei denen das Aussondern mehr Zeit kostet
als der größere Baum.

lg
QNo