Re: Rekursion bricht nicht ab

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> (permalink)
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

Show key headers only | View raw

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

Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-08 23:28 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-09 16:13 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:41 +0200
      Re: Rekursion bricht nicht ab Peter Büttner <not_for_mail_peb@gmx.net> - 2016-04-10 16:45 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 18:28 +0200
          Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-13 19:25 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 21:56 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 17:31 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:53 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:56 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 19:22 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 00:42 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 09:20 +0200
              Re: Rekursion bricht nicht ab Christoph Schneegans <Christoph@Schneegans.de> - 2016-04-14 18:47 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:07 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 17:38 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 22:36 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-28 08:26 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-10 22:15 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:46 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:32 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 20:44 +0200
              Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-14 12:07 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-23 13:35 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 14:57 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 23:05 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-26 01:16 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 16:05 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:48 +0200
  Re: Rekursion bricht nicht ab v_borchert@despammed.com (Volker Borchert) - 2016-04-10 06:07 +0000
  Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:40 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-11 11:21 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:57 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:28 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 23:36 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 21:42 +0200

csiph-web