Palindrom in zweidimensionalem Array

[Lazyyy]

Hallo Zusammen,
ich arbeite derzeit an einer Aufgabe bei der ich zuerst einen String in ein Palindrom umwandeln soll (ich mache dies über ein Chararray).
Und anschliesend in einem zweidimensionalem Array auf bestimmte Weise unterbringen soll.

Von links oben nach rechts oben,
von links oben nach links unten,
von links oben nach rechts unten,
von rechts oben nach rechts unten,
von links unten nach rechts oben,
von links unten nach rechts unten.

public static char[][] palindromArray(String s) {
       char[] inhaltS = s.toCharArray();
       char[] palindrom = new char[(inhaltS.length * 2) - 1];

       for (int i = 0; i < inhaltS.length; i++) {
           palindrom[i] = inhaltS[i];
           palindrom[palindrom.length - i-1] = inhaltS[inhaltS.length - i-1];
       }

       char[][] result = new char[palindrom.length][palindrom.length];

       for (int i = 0; i < palindrom.length; i++) {
           result[i][0] = palindrom[i];
           for (int j = 0; j < palindrom.length; j++) {
               result[0][j] = palindrom[j];
               if (i == j) {
                   result[i][j] = palindrom[j];
               }
           }
       }

       return result;
   }

Zum einen komme ich von der Logik nicht darauf wie ich von links unten nach rechts oben eintragen kann und zum anderen bin ich mir beim Palindrom nocht sicher.

Zusatzfrage: Wenn ich eine Klasse Programm habe wie kann ich die Klasse Palindrom am besten aufrufen um zwischenschritte zu Testen.

Vielen Dank schon einmal
Lazy

 

[VfL_Freak]

Moin,
ich verstehe offen gestanden kein Wort!!

* was für eine Klasse 'Programm'?
* was für eine Klasse 'Palindrom'?
* wie sieht denn bei 'palindromArray' der Eingabestring aus?

* was soll mir dies hier sagen?

Von links oben nach rechts oben,
von links oben nach links unten,
von links oben nach rechts unten,
von rechts oben nach rechts unten,
von links unten nach rechts oben,
von links unten nach rechts unten.

Fragen über Fragen
Vg Klaus

 

[MoxxiManagarm]

String in ein Palindrom umwandeln

Rein vom Wording ist das nicht korrekt. Ein Palimdrom ist kein Datentyp (außer du hast eine eigene Klasse dafür). Umwandeln kannst du es daher nicht direkt. Du könntest Testen, ob der String, welcher dir vorliegt, ein Palimdrom ist - oder eben - du ergänzt den String so, dass er ein Palimdrom wird undabhängig davon, ob er danach noch ein echtes Wort ist. Du könntest also z.B. aus 'HAUS' 'HAUSUAS' machen, oder aus 'MANN' MANNAM'. Auf dem ersten Blick würde ich sagen dein Code macht vermutlich diese Erweiterung. Aber vermutlich würdest du im Fall von 'MANN' 'MANNNAN' erstellen. Natürlich ist das auch ein Palimdrom, aber ggf. sollst du das kürzeste wählen und das hätte hier ein N weniger.


Zum Verständnis, Weil auch mir deine Aufgabe nicht ganz klar ist. Soll sowas gemacht werden, dass du z.B. aus REITTIER folgendes bekommst:

R E I T T I E R
E E . . . . E E
I . I . . I . I
T . . T T . . T
T . . T T . . T
I . I . . I . I
E E . . . . E E
R E I T T I E R

Und aus 'NEBEN' das:

N E B E N
E E . E E
B . B . B
E E . E E
N E B E N

 

[Lazyyy]

der obere Code steht praktisch in der Klasse Palindrom.
Die Klasse Programm habe ich erfunden / könnte auch Klasse Test sein.
Gedanke: um zwischenergebnisse herauszuholen.

Und betrachtet man das Quadratische Array zb wie ein Schachbrett dann sollten nach den Richtungsangaben die Felder belegt werden .. sprich einige sind leer.

der Input ist eine Großbuchstabenfolge.

 

[Lazyyy]

Rein vom Wording ist das nicht korrekt. Ein Palimdrom ist kein Datentyp (außer du hast eine eigene Klasse dafür). Umwandeln kannst du es daher nicht direkt. Du könntest Testen, ob der String, welcher dir vorliegt, ein Palimdrom ist - oder eben - du ergänzt den String so, dass er ein Palimdrom wird undabhängig davon, ob er danach noch ein echtes Wort ist. Du könntest also z.B. aus 'HAUS' 'HAUSUAS' machen, oder aus 'MANN' MANNAM'. Auf dem ersten Blick würde ich sagen dein Code macht vermutlich diese Erweiterung. Aber vermutlich würdest du im Fall von 'MANN' 'MANNNAN' erstellen. Natürlich ist das auch ein Palimdrom, aber ggf. sollst du das kürzeste wählen und das hätte hier ein N weniger.


Zum Verständnis, Weil auch mir deine Aufgabe nicht ganz klar ist. Soll sowas gemacht werden, dass du z.B. aus REITTIER folgendes bekommst:

R E I T T I E R
E E . . . . E E
I . I . . I . I
T . . T T . . T
T . . T T . . T
I . I . . I . I
E E . . . . E E
R E I T T I E R

Und aus 'NEBEN' das:

N E B E N
E E . E E
B . B . B
E E . E E
N E B E N

genau so ist es gedacht.

 

[MoxxiManagarm]

Du hast aus meiner Sicht 2 Problemstellungen

1. Das Minimale ergänzte Palimdrom finden. Ich bezweifle dass alle anderen akzeptiert werden, auch wenn es sich bei diesen rein nach Definition auch um Palimdrome handeln würde.

public class PalimdromBuilder {

    public static String buildPalimdrom(String input) {
        String forward = input.toUpperCase();
        String backward = new StringBuilder(forward).reverse().toString();
      
        for(int i = 0; i < forward.length(); i++) {
            String sub1 = forward.substring(i, forward.length());
            String sub2 = backward.substring(0, backward.length() - i);
          
            if(sub1.equals(sub2)) {
                backward = backward.replaceFirst(sub2, "");
                break;
            }
        }
      
        return forward + backward;
    }
  
    public static void main(String[] args) {
        System.out.println(buildPalimdrom("ANNA"));
        System.out.println(buildPalimdrom("MANN"));
        System.out.println(buildPalimdrom("HAUS"));
    }
}

Ausgabe:

ANNA
MANNAM
HAUSUAH

2. Das Palimdrom aus 1. in das Gitter packen.
- Das Gitter hat die Größe nxn mit n=palimdrom.length()
- Du hast 6 'Pfade', welche du alle in einer Schleife abfrühstücken kannst.

 

[Lazyyy]

Die Idee das Palimdrom noch aus dem String zu erstellen gefällt mir gut und leuchtet ein. Danke dafür!

In meiner Lösung hat es sich meiner Meinung nach, nach drei Pfaden "ausgefrühstückt" und ich komme nicht auf die Restlichen. :/

 

[MoxxiManagarm]

Vermutlich hast du nur die ersten 3. Füge n als feste Größe mit ein.

//Von links oben nach rechts oben,
array[0][i]
//von links oben nach links unten,
array[i][0]
//von links oben nach rechts unten,
array[i][i]
//von rechts oben nach rechts unten,
array[n][i]
//von links unten nach rechts oben,
array[n-i][i]
//von links unten nach rechts unten.
array[i][n]

 

[httpdigest]

Interessantes Problem, das mit dem minimalen Palindrom durch rechts anfügen zu bilden. Wollte hier auch mal eine eigene Lösung bauen:

public static String buildPalindrome(String input) {
    String extension = "";
    /*
     * Idee: Laufe den String von links nach rechts ab und prüfe, ob
     * der String von rechts nach links abgelaufen derselbe wäre.
     * Immer, wenn er es nicht ist, füge den von links nach rechts
     * abgelaufenen Buchstaben zu "extension" hinzu.
     */
    for (int i = 0, j = input.length() - 1; i < j; i++, j--) {
        if (input.charAt(i) != input.charAt(j)) {
            extension = input.charAt(i) + extension;
            j++; // <- bleibe erstmal auf dem Buchstaben
        }
    }
    return input + extension;
}

EDIT: Mist, das funktioniert so nicht. Bitte ignorieren

 

[MoxxiManagarm]

Ich habe es mir einfach bildlich vorgestellt. Meine Lösung kann man sich so gedanklich nachstellen:
Das Wort auf einen Papierstreifen vorwärts schreiben.
Das Wort auf einen Papierstreifen rückwärts streiben
Beide Papierstreifen übereinanderlegen
Die Papierstreifen solange verschieben (auseinanderziehen), bis die sich überlappenden Teile identisch sind
Schere nehmen und den identischen Teil vom Rückwärts-Streifen abschneiden
Beide Streifen zusammenfügen.

Du bist ja an sich gut darin noch optimierte Lösungen zu finden httpdigest. Ich bin gespannt, ob du deinen Fehler noch findest oder gar einen anderen Weg und wie ich mir diesen verbildlichen kann

 

[MoxxiManagarm]

Ich glaube ich habe gerade verstanden, was du mit deinem Ansatz abbilden wolltest.
Mein "überlappender" Streifen, ist immer selbst ein Palindrom welches hinten am Wort ist.

ANNA
BASIS
MANN

Eventuell hilft dir diese Formulierung bei der Fehlersuche

 

[Lazyyy]

Vermutlich hast du nur die ersten 3. Füge n als feste Größe mit ein.

//Von links oben nach rechts oben,
array[0][i]
//von links oben nach links unten,
array[i][0]
//von links oben nach rechts unten,
array[i][i]
//von rechts oben nach rechts unten,
array[n][i]
//von links unten nach rechts oben,
array[n-i][i]
//von links unten nach rechts unten.
array[i][n]

das wäre dann einfach so gedacht?:

int n = palimdrom.length;
       
       for (int i = 0; i < palimdrom.length; i++) {
           
           result[i][0] = palimdrom[i];
           result[0][i] = palimdrom[i];
           result[i][i] = palimdrom[i];
           result[n][i] = palimdrom[i];
           result[i][n] = palimdrom[i];
           //result[n-i][i] = palimdrom[i];

       }

wieso geht letzteres über die Grenzen des Arrays hinaus ?

 

[Lazyyy]

Der aktuelle Stand sieht praktisch so aus:
wobei das "einpflanzen" nicht funktioniert.

public class PalindromArray {

   public static char[][] palindromArray(String s) {
      
           String result;
           String forward = s.toUpper();
           String backward = new StringBuilder(forward).reverse().toString();
      
           for(int i = 0; i < forward.length(); i++) {
               String sub1 = forward.substring(i, forward.length());
               String sub2 = backward.substring(0, backward.length() - i);
        
              
               if(sub1.equals(sub2)) {
                   backward = backward.replaceFirst(sub2, "");
                   break;
               }
           }
           result = forward + backward;
      
       char[] palimdrom = result.toCharArray();
      
       char[][] result2 = new char[palimdrom.length][palimdrom.length];
       int n = palimdrom.length;
      
       for (int i = 0; i < palimdrom.length; i++) {
          
           result2[i][0] = palimdrom[i];
           result2[0][i] = palimdrom[i];
           result2[i][i] = palimdrom[i];
           result2[n][i] = palimdrom[i];
           result2[i][n] = palimdrom[i];
           result2[n-i][i] = palimdrom[i];

       }

       return result2;
   }

}

 

[MoxxiManagarm]

Eventuell war es irritierend, dass ich es n genannt hatte, entschuldige. Es ist eine feste Größe, muss aber ganz normal wie beim Array

int n = palindrom.length - 1;

sein. Außerdem hatte ich in meinem Beispiel ein Schreibfehler drin. Es heißt Palindrom. Stört das Programm natürlich nicht, aber wir wollen doch korrekt bleiben

 

[Lazyyy]

->

 char[][] result = PalindromArray.[palindromArray]("FF");
  result erwartet: char[][] mit Länge 3 = {
     char[] mit Länge 3 = {
     'F',
     'F',
     'F'
  },
     char[] mit Länge 3 = {
     'F',
     'F',
     'F'
  },
     char[] mit Länge 3 = {
     'F',
     'F',
     'F'
  }
  }
  tatsächlich: char[][] mit Länge 2 = {
     char[] mit Länge 2 = {
     'F',
     'F'
  },
     char[] mit Länge 2 = {
     'F',
     'F'
  }
  }

 

[MoxxiManagarm]

Sagt das dein Vorgegebener Tester? Dann erwartet ihr vermutlich doch nicht das minimale Palindrom...
Halte ich für fragwürdig aber ok. Dann vergiss meinen Lösungsvorschlag und nimm doch wieder nur den letzten Buchstaben... Jedenfalls weißt du wie es gehen würde ;-)

 

[Lazyyy]

Jo hast mir einiges geholfen