# Parkplatz mit greedy finden



## hooked (26. Nov 2015)

Hey Leute,

ich steh wieder einmal vor einem problem.
Hier erstmal die Aufgabe mit dem dazugehörigen Code:

Implementieren Sie zunächst die Methode greedyPark, die einen Parkplatz für ein Auto der gegebenen Länge finden und besetzen soll. Autofahrer sind ein ungeduldiges Volk, das Parkplätze nach dem Greedy-Algorithmus auswählt. Sie fahren die Straße von Anfang an entlang und parken in der ersten Parklu ̈cke, die groß genug für ihr Auto ist. Die Methode soll also die erste Lücke finden, die mindestens so groß wie das Auto ist. Anschließend sollen alle Felder, die vom Auto belegt werden, durch Aufruf der Methode setOccupied besetzt werden. Beispiel:

Vorher: XX.....XXX...XX
greedyPark(3)
Nachher: XXXXX..XXX...XX


```
public class Parking
{
    // represents the segments (parking spots) of the road
    // true: the segment is free. false: it is occupied
    private boolean isFree[];

    // generates a road of the given length with random segments being occupied
    public Parking(int roadLength)
    {
        isFree = new boolean[roadLength];
        for (int i=1; i<roadLength; ++i)
            isFree[i] = Math.random() < 0.7 ? isFree[i-1] : !isFree[i-1];
    }
  
    // sets the segment of the given index to "occupied"
    public void setOccupied(int index)
    {
        if (isFree[index])
            isFree[index] = false;
        else
            System.err.println("Position " + index + " was already occupied!");
    }
  
    // prints the occupied and free parking spots to the screen
    public void printRoad()
    {
        for (int i=0; i<isFree.length; ++i)
            System.out.print(isFree[i] ? "." : "X");
        System.out.println();
    }

    // attempts to park a car of the given length
    // chooses the first available space that is large enough
    // sets the space to "occupied"
    public void greedyPark(int carLength)
    {
        // TODO: implement greedy parking
    }

    // attempts to park a car of the given length
    // among all available spaces, chooses the smallest one that fits
    // sets the space to "occupied"
    public void smartPark(int carLength)
    {
        // TODO: implement smart parking
    }
  
    public static void main(String[] args)
    {
        int roadLength = 100; // length of the road
        int numCars = 10; // number of cars trying to park
        int minLen = 2; // minimum length of a car
        int maxLen = 6; // maximum length of a car
      
        Parking park = new Parking(roadLength);
        park.printRoad();
        for (int i=0; i<numCars; ++i)
        {
            // determine random car length
            int carLength = (int)(Math.random()*(maxLen-minLen + 1));
            carLength += minLen;
            System.out.println("Parking a car of length " + carLength);
          
            // try to park it
            park.greedyPark(carLength);
            park.printRoad();
        }
    }
}
```

Ich habe jetzt echt Probleme mit der Aufgabe anzufangen...könntet ihr mir da ein paar Denkanstöße geben ?

Also mir ist schon klar, dass ich die Autolänge mit den freien Plätzen vergleichen muss. Aber wie soll ich das so coden ?


----------



## Joose (26. Nov 2015)

hooked hat gesagt.:


> Ich habe jetzt echt Probleme mit der Aufgabe anzufangen...könntet ihr mir da ein paar Denkanstöße geben ?
> Also mir ist schon klar, dass ich die Autolänge mit den freien Plätzen vergleichen muss. Aber wie soll ich das so coden ?



Hier wären 2 verschachtelte Schleifen hilfreich.
Die äußere geht jeden Platz durch, sobald du einen freien Platz findest wird die innere Schleife ausgeführt.
Diese kontrolliert ob genügend Platz für das Auto vorhanden ist. (der Start der inneren Schleife ist der Wert der Zählervariable der äußeren, die Grenze ist der Startwert der innern + länge des Autos).

Sollte nicht genügend Platz gefunden werden, läuft die äußere einfach weiter. Wird genügend Platz gefunden kannst du den Platz als belegt Kennzeichnen und die Schleifen (beide) abbrechen.


Anmerkungen zum Code:


hooked hat gesagt.:


> ```
> private boolean isFree[];
> .......
> for (int i=1; i<roadLength; ++i)
> ...


Bei der Deklarierung von Arrays hänge die "[]" an den Typ an und nicht an den Namen 
Du erstellt ja ein boolean Array und nicht ein boolean mit den Namen "isFree eckige Klammer auf und zu".
Java erstellt es zwar richtig und lässt es zu, aber auf den 1.Blick handelt es sich dabei um ein einfaches boolean.

Auch wenn Java es zulässt einfache Schleife und if-Abfragen immer mit Schleifen schreiben, dass minimiert die Fehlerquellen.
Erweiterst du später mal die Schleife und vergisst die Klammern kann es zu einen unerwünschten Verhalten kommen.
-> es ist zwar auch an der Einrückung erkennbar aber nicht jeder hat seine IDE so eingestellt das beim Speichern/Run/Debug automatisch der Code entsprechend formatiert wird so das man den Fehler erkennen könnte.


----------



## klauskarambulut (26. Nov 2015)

```
int[] gaps = new int[isFree.length];

for(int i = gaps.length-1; i >= 0; i--) {
  if(!isFree[i]) {
    gaps[i] = 0;
  } else {
    if(i == gaps.length-1) {
      gaps[i] = 1;
    } else {
      gaps[i] = gaps[i+1] + 1;
    }
  }
}

for(int j = 0; j < gaps.length; j++) {
  if(gaps[j] >= carLength) {
    for(int k = j; k <j+carLength; k++) {
      setOccupied(k);
    }
    break;
  }
}
```


----------



## hooked (27. Nov 2015)

danke euch beiden für die Hilfe...dank Joose konnte ich schon den Großteil des Codes erstellen aber ich hatte noch 2-3 kleinere Fehler drin, die ich dann dank klauskarambulut lösen konnte 

leider steh ich noch vor einem weiteren Problem.
Ich habe nun noch das folgende Problem:

Ich würde gerne eine Methode implementieren, mit der erst die ganze Strecke abgesucht wird und dann die am besten passendste Lücke dem Auto zugeordnet wird (also quasi immer die kleinste Lücke, damit keine Parkplätze verschwendet werden).

Hier muss ich sagen, dass ich noch mehr Verständnisschwierigkeiten habe als bei der Aufgabe zuvor...ich hoffe ihr könnt mir nochmal so gut helfen


----------



## Joose (27. Nov 2015)

Du musst über dein "isFree" Array iterieren, wenn du einen freien Platz findest zählst du nach wie lange dieser ist.
Den Index wo der freie Platz beginnt und die Länge speicherst du dir dann. (Am einfachsten wäre hier eine kleine Klasse zu schreiben welche diese beiden Informationen übergeben bekommt, danach eine Liste von Objekten dieser Klasse).

Hast du 1x alle freie Parklücken erfasst kannst du nun über diese Liste itererieren und kontrollierst jede Parklücke.
Die 1. Parklücke in welche den Auto passen würde speicherst du dir in eine Hilfsvariable, aber du iterierst noch weiter über die Liste.
Solltest du wieder eine Parklücke finden in die dein Auto passen würde musst du überprüfen welche der beiden Parklücken (die Hilfsvariable oder die aktuelle Schleifenwert) die kürzere ist.
Die kürzere speicherst du in die Hilfsvariable.
Sollten beiden gleich lang sein ist es egal welche du nimmst, findest du ein genau passende kannst du entweder die Schleife abbrechen oder fertig laufen lassen

(ausführlicherer) Pseudocode:

```
public class Luecke {
   int index;
   int laenge;
  
   getter/setter
}
....
List<Luecke> luecken = new Liste();

for(i = 0;i < isfree.length; i++){
   if(isfree[i] ist frei){
     index = i
     länge der lücke zählen // möglich mit einer while-schleife
     liste.add(neue Luecke(index, laenge))
   }
}

hilfsvariable
for(Luecke l in luecken) {
   if(lücke passend o größer für auto) {
     if(hilfsvariable schon belegt) {
       if(ist hilfsvariable oder l kürzer) {
         ..
       } else {
         ..
       }
     } else {
       hilfvariable = l
     }
   }
}
```


----------



## strußi (27. Nov 2015)

mit einer for-schleife über alle Elemente gehen und die start-end-werte deiner freien Plätze in einem Object notieren und dieses in einer Liste ablegen. Die länge erhältst du als Nebenprodukt ende-start =Länge.


----------



## Dompteur (27. Nov 2015)

Wobei man da eigentlich gar keine Liste braucht.
Man braucht 2 Variablen: Position der Lücke und Länge der Lücke.
Anfangs bekommt die Position einen ungültigen Wert (zB -1)

Dann suchst du in einer Schleife nach passenden Lücken. 
Wenn du eine gefunden hast, dann vergleichst du ob diese Lücke kürzer als deine bisher beste ist. Wenn du bisher noch keine hattest, dann ist die gefundene die vorerst beste.
Nach diesem Vergleich setzt du die Suche fort.
Sobald aber deine beste Lücke genau so lang wie dein Auto ist bist du fertig.
Wenn du keine genau passende Lücke gefunden hast, hast du nach der Schleife 2 Fälle: keine gefunden (Position ist immer noch -1) oder die beste passende Lücke steht in Positon.


----------



## Joose (27. Nov 2015)

@Dompteur da hast du natürlich recht 

So einfach habe ich da wieder nicht gedacht.

Meine Variante wäre nur von Vorteil wenn man der Reihe nach jeweils eine Lücke für ein paar Autos sucht. 
Da ich nur 1x das Array durchgehen muss und mir alle Lücken speichern kann. Sollte eine Lücke belegt werden kann ich deren Länge einfach kürzen bzw. bei Länge 0 die Lücke aus der Liste entfernen.


----------



## hooked (29. Nov 2015)

Jetzt habt ihr mich etwas verwirrt XD ich Blick noch nicht ganz durch


----------



## Flown (29. Nov 2015)

Anders gefragt wie würdest es du als Mensch Schritt für Schritt machen?


----------



## strußi (29. Nov 2015)

der Mensch würde sich egoistisch wie er ist, in die nächste freie Lücke mittig reinstellen, damit er später gut ausparken kann ;-)


----------



## Flown (29. Nov 2015)

ich meinte wie der vernünftige Mensch das lösen würde in einer uthopischen Welt.


----------



## hooked (29. Nov 2015)

ja das Problem ist weniger der Sinn, sondern die Umsetzung als Code XD


----------



## Dompteur (29. Nov 2015)

Trotzdem sollte du damit beginnen, den Lösungsweg in prosa zu formulieren.
Du wirst sehen, dass dir hier genug Leute im Dialog helfen werden, dich der Lösung zu nähern...


----------



## strußi (30. Nov 2015)

suche die ganze Straße ab und merke dir die kleinste PASSENDE Parklücke


----------

