Anzahl möglicher Reiserouten zurückgeben

[Ibrahim]

Ich möchte eine rekursive Methode implementieren, die mittels Backtracking die Anzahl der möglichen Reiserouten bestimmt und zurückgibt, deren jeweilige Schönheitssumme genau goal ist.

Die Anzahl der möglichen Routen ist 2, aber ich gebe anscheinend mehr als 2 zurück.

Wie kann man also die Städte der jeweils aktuellen Reiseroute in int [] path erfassen und die richtige Anzahl der Reiserouten zurückgeben?

public static int solve(int values [], int [][] next, int goal, int city,
                            int [] path, int pathIdx, TravelCheck tc)
    {
        tc.check(); // automatic check

        tc.report(path);
    
int [][] newCity = new int[next.length][next[0].length];

        for(int i = 0; i < next.length;i++){
            for(int j = 0;j < next[i].length;j++){
                if((next[i][j]) < -1){
                    //newCity[i][j] = next[i][j];
                    newCity[i][j] = 2;
                }
            }
        }
        int d = values[3];
        int b = values[0];
        int e = 3;
        int c = 6;
        int a;
        int f;

       if(city == 0){

           for (int i = 0; i < values.length; i++) {
               a = b * c;
               i++;
               return a;
           }
          
           } else if (city == 0 || city == 3) {
           for(int i = 0; i < values.length; i++) {
               f = b + (d * e);
               return f;

           }
       }
       int res = solve(values,next,goal,city,path,pathIdx,tc);

                return res;

    }

 

[Neumi5694]

Ich hab mir jetzt nicht alles so genau angeschaut, aber dieser Codeteil schaut suspekt aus:

for (int i = 0; i < values.length; i++) {
               a = b * c;
               i++;
               return a;
           }

Das entspricht

if (values.length > 0) {
  return a * b * c;
}

Und ich glaube nicht, dass das im Sinne des Erfinders ist.

 

[MarvinsDepression]

a) Die Parameterliste ist viel zu lang. was davon kannst Du als Klassen- oder besser als InstanzAtribute zugänglich machen?

b) Diese Methode arbeitet weder rein rekursiv, noch iterativ. Schreibe Hilfsmethoden, welche die iterativen Teile des Codes ausführen. Kleine Methoden sind viel übersichtlicher und leichter zu warten. Mit einer guten Benennung der Methoden UND Variablen wird der Code lesbar und verständlich.

 

[Ibrahim]

Es handelt sich um eine testgetriebene Entwicklung. Neue Attribute bzw. Methoden sind nicht zulässig.

a) Die Parameterliste ist viel zu lang. was davon kannst Du als Klassen- oder besser als InstanzAtribute zugänglich machen?

b) Diese Methode arbeitet weder rein rekursiv, noch iterativ. Schreibe Hilfsmethoden, welche die iterativen Teile des Codes ausführen. Kleine Methoden sind viel übersichtlicher und leichter zu warten. Mit einer guten Benennung der Methoden UND Variablen wird der Code lesbar und verständlich.

 

[Ibrahim]

Soweit ich verstehe, muss ich meine berechneten Werte in Feld namens int [] path ablegen. Mir fällt aber dazu kein Ansatz ein.

Hier der Test:

public static final int[] VALUES = {3, 5, 10, 5, 13, 23};
    // beauty values of the cities (city 0 has beauty 3)
    // city 1 has beauty 5
    // ...
    public static final int[][] NEXT = { // neighbouring cities
            {0, 3}, // starting at city 0 we can travel to city 0 (again) or city 3
            {3, 5}, // from city 3 we can reach cities 3 and 5
            {0, 1, 2, 3}, // from city 0 we can reach cities 1, 2 and 3
            {3, 4}, // from city 3 we can travel to city 4
            {2}, // from city 2 we can only reach city 2 again
            {4, 5} // from city 4 we can reach city 5
    };
    final static int GOAL = 18; // target value for the beauty of the whole itinerary - this is just a possible example!
    final static int START_CITY = 0; // start of the itinerary (first city to be visited) - this is just a possible example!
    final static int[] DEFAULT_PATH = new int[GOAL]; // template for the itinerary - initially all entries are set to -1

    static {
        Arrays.fill(DEFAULT_PATH, -1);
    }

boolean foundFirst = false, foundSecond = false;
        for (int[] p : bb.paths) {
            if (Arrays.equals(p, new int[]{0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1})) {
                foundFirst = true;
            } else if (Arrays.equals(p, new int[]{0, 3, 3, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1})) {
                foundSecond = true;
            } else {
                fail("An unexpected itinerary has been reported: " + Arrays.toString(p));
            }
        }

 

[KonradN]

Es handelt sich um eine testgetriebene Entwicklung. Neue Attribute bzw. Methoden sind nicht zulässig.

Also wenn Du damit Test Driven Development meinst, dann ist das schlicht falsch. Test Driven Development ist ein ständiges Durchlaufen des Zyklus:

• Rot
• Grün
• Refactoring

Also
1. Test schreiben, der fehlschlägt.
2. Anpassung, so dass der Test grün wird.
3. Refactorings durchführen

Und wenn ich so Code sehe, bei dem Daten in keiner Weise gekapselt sind und statt dessen mehrdimensionale Arrays so herum gereicht werden mit statischen Methoden, dann ist das durchaus etwas, das geradezu nach Refactorings schreit 🙂