Last Survivor (Codewars)



  • Hallo,
    eigentlich eine ganz einfache Aufgabe, aber ich verstehe nicht ganz die Aufgabenstellung. Statt nun zu verzweifeln, will ich versuchen es mir erklären zu lassen.

    Die Aufgabe:

    You are given a string of letters and an array of numbers.
    The numbers indicate positions of letters that must be removed, in order, starting from the beginning of the array.
    After each removal the size of the string decreases (there is no empty space).
    Return the only letter left.

    Notes

    The given string will never be empty.
    The length of the array is always one less than the length of the string.
    All numbers are valid.
    There can be duplicate letters and numbers.

    Kata

    Valid numbers sind doch 0 bis string.size() - 1?
    Wenn der string jetzt verkleinert wird, ist doch das alte string.size() -1 nicht mehr valid?
    Dazu gibt es auch ein Beispiel:

    let str = "zbk", arr = [0, 1] // arr = [0, 2] noch valid
        str = "bk", arr = [1]     // arr = [2]  nicht mehr valid
        str = "b", arr = []
        return 'b'
    

    Es wird also auch das numbers-Array verkleinert.
    Aber siehe Kommentare, es gibt nach jedem Verkleinern des string mögliche nicht mehr valide nummern.
    Wäre jetzt die Lösung, den Inhalt des array nach jedem Verkleinern neu anzupassen?



  • @zeropage sagte in Last Survivor (Codewars):

    Valid numbers sind doch 0 bis string.size() - 1?

    Ja, so verstehe ich das auch. Und zwar so, dass garantiert ist, dass das Array keine ungültigen Zahlen enthält. Ich interpretiere das so, dass man theoretisch keinen Range-Check benötigt.

    Wenn der string jetzt verkleinert wird, ist doch das alte string.size() -1 nicht mehr valid?

    Meine Lesart ist diese:

    The numbers indicate positions of letters that must be removed, in order, starting from the beginning of the array.
    [...]
    All numbers are valid.
    There can be duplicate letters and numbers.

    "All numbers are valid" bedeutet, dass es keine ungültigen Zahlen im Array gibt, d.h. Jede dieser Zahlen ist ein Index, der innerhalb des String liegt.

    "There can be duplicate letters and numbers" lese ich so, dass sich die Zahlen im Array immer auf den String beziehen, den man erhält, nachdem man die Vorgänger entfernt hat und nicht ausschliesslich auf den Start-String. Wäre letzteres der Fall, müsste sich eine doppelte Zahl auf einen Buchstaben beziehen, den man bereits entfernt hat und wäre damit ungültig (Widerspruch zu "all numbers are valid").

    Also:

    Ja, für den gegebenenen String und das Array ist string.size() - 1 eine gültige erste Zahl, aber eine ungültige zweite Zahl. Oder um es allgemeiner zu formulieren:

    Sei n=n = string.size() und aia_i die Zahl mit dem Array-Index ii. Dann ist die Bedingung für ein gültiges Array, dass für alle 0i<n0 \le i < n: 0ai<ni0 \le a_i < n - i gilt .

    Da jede Zahl im Array gültig ist, wird mit jeder Interation ein Buchstabe aus dem String entfernt, d.h. nach der Bearbeitung einer Array-Zahl ist der String jedes Mal um eins kleiner, weshalb die maximal gültige Zahl im Array mit jeder weiteren Array-Position ebenfalls um eins kleiner wird.

    let str = "zbk", arr = [0, 1] // arr = [0, 2] noch valid
    

    Das Array [0, 2] verletzt daher die Vorbedingung, dass alle Zahlen im Array gültig sind. Die 2 ist eine gültige erste Zahl, aber keine gültige zweite Zahl.

    Wäre jetzt die Lösung, den Inhalt des array nach jedem Verkleinern neu anzupassen?

    Nach meiner Interpretation nein. Auch denke ich nicht, dass man überhaupt die Array-Größe anpassen muss. Ich denke es reicht, einfach das Array abzuschreiten und die Buchstaben an den gegebenen Positionen zu entfernen.

    Das ist aber nur so wie ich das verstehe. Es ist möglich, dass ich etwas missverstanden habe oder die Aufgabe anders gemeint war, als sie formuliert ist.


  • Mod

    Das ist zu einfach, du denkst zu kompliziert: Du sollst von vorne nach hinten durch die Zahlenliste durchgehen. Fertig.

    • "abcd"; [2, 1, 1] -> Gültige Eingabe, es soll 'a' rauskommen.
    • "abcd"; [0, 3, 1] -> Würde beim 2. Schritt scheitern, weil "bcd"[3] ungültig. Solche Fälle brauchst du aber nicht zu beachten

    Ob du intern mit einem Index durch das Array gehst, oder vorne popst, oder Rekursion nutzt, ist ganz dir überlassen. Du bekommst nur so etwas wie "abc"; [2, 1] und darfst erwarten, dass die Eingabe selbstkonsistent gestellt ist. Das soll verhindern, dass du deinen ganzen Code mit if(index >= string.length() fehler(); und ähnlichem vollpflasterst, anstatt dich auf die eigentliche Aufgabe zu konzentrieren.



  • @zeropage
    Wenn das Array nur aus 0 (Nullen) besteht, bleibt das letzte Zeichen im String übrig.
    Der letzte Wert im Array kann nur 0 oder 1 sein
    Wenn keine 0 im Array steht, bekommst du das erste Zeichen vom String.



  • @zeropage sagte in Last Survivor (Codewars):

    The length of the array is always one less than the length of the string.

    Ich frage mich gerade, ob man das irgendwie zur Optimierung nutzen kann. Das Endergebnis der Funktion nach dem Entfernen ist also immer genau ein Zeichen.


  • Mod

    @wob sagte in Last Survivor (Codewars):

    @zeropage sagte in Last Survivor (Codewars):

    The length of the array is always one less than the length of the string.

    Ich frage mich gerade, ob man das irgendwie zur Optimierung nutzen kann. Das Endergebnis der Funktion nach dem Entfernen ist also immer genau ein Zeichen.

    Das ist doch nur die Voraussetzung, damit die Aufgabe wie gestellt aufgeht. Ich denke nicht, dass dies zu Optimierungen führen kann, die tiefer greifen, als das man für die Rückgabe char statt string benutzen kann.



  • Ich hätte normalerweise erwartet, dass das Zahlenarray auch kürzer sein darf, sodass z.B. nur 2 von 4 Buchstaben (oder 42 von 1 Million) entfernt werden. Hier werden immer alle bis auf einen entfernt. Vielleicht kann man irgendwie effizienter mit den Zahlen im Array "rummachen" als nacheinander einzelne Buchstaben aus dem String zu löschen.



  • @wob sagte in Last Survivor (Codewars):

    Ich hätte normalerweise erwartet, dass das Zahlenarray auch kürzer sein darf, sodass z.B. nur 2 von 4 Buchstaben (oder 42 von 1 Million) entfernt werden. Hier werden immer alle bis auf einen entfernt. Vielleicht kann man irgendwie effizienter mit den Zahlen im Array "rummachen" als nacheinander einzelne Buchstaben aus dem String zu löschen.

    Ich fände es auch eine sehr elegante Lösung den Index dieses "letzten Buchstaben" ausschliesslich aus dem Index-Array zu berechnen. Mein Bauchgefühl sagt mir, dass da bestimmt irgendwas pfiffiges geht, da müsste ich aber noch etwas mehr drüber nachdenken 😉

    Eine Beobachtung schonmal: Wenn keine 0 im Array vorkommt, dann muss der gesuchte Buchstabe str[0] sein.


  • Mod

    Eine Beobachtung wäre, dass vorhergehende Zahlen die Nachfolger effektiv um 1 erhöhen, wenn diese größergleich sind als der entfernte Wert. Das ist aber rekursiv nachwirkend anzuwenden, wodurch es wieder kompliziert wird. Aber es kann dann kein Wert 2x entfernt werden. Vielleicht kann man da etwas machen, indem man sich die entfernten Werte merkt.

    Beispiel: [6, 2, 6, 3, 3, 2, 0, 1, 1] auf "0123456789", Lösung ist '1'

    1. Nehme 6, es wurden noch keine kleinergleiche Zahlen entfernt, merke 6 wurde entfernt. Merkliste [6]
    2. Nehme 2, es wurden noch keine kleinergleiche Zahlen entfernt, merke 2 wurde entfernt. Merkliste [2, 6]
    3. Nehme 6, es wurden schon 2 und 6 entfernt, d.h. effektiv ist die 6 eine 8. Es wurden keine weiteren kleinergleichen Zahlen als 8 entfernt. Merke 8 entfernt. Merkliste [2, 6, 8]
    4. Nehme 3. Es wurde schon eine 2 entfernt, also effektiv ist die 3 eine 4. wurden keine weiteren kleinergleichen Zahlen als 4 entfernt. Merke 4 entfernt. Merkliste [2, 4, 6, 8]
    5. Nehme 3. 2 wurde schon entfernt, also effektiv 4. 4 wurde schon entfernt, also effektiv 5. Merke 5 entfernt. Merkliste [2, 4, 5, 6, 8]
    6. Nehme 2. 2 wurde schon entfernt, also effektiv 3. Es wurden keine zusätzlichen kleinergleichen Werte als 3 entfernt, also merke 3 entfernt. Merkliste [2, 3, 4, 5, 6, 8]
    7. Nehme 0. Keine kleinergleichen Vorentfernungen, merke 0. Merkliste [0, 2, 3, 4, 5, 6, 8]
    8. Nehme 1. 0 war kleiner, also 2, 2 schon weg; also 3; 3 schon weg, also 4; … ; 6 schon weg, also 7, 7 noch frei. Merke 7 entfernt. Merkliste [0, 2, 3, 4, 5, 6, 7, 8].
    9. Nehme 1. 0 war kleiner, also 2, 2 schon weg; also 3; …; 8 schon weg, also 9, 9 noch frei. Merke 9 entfernt. Merkliste [0, 2, 3, 4, 5, 6, 7, 8, 9].
    10. Wir sind fertig und gucken nach der Lücke in der Merkliste: Die 1 fehlt, also ist das letzte Zeichen an Index 1.

    Das könnte effizienter sein, wenn man das clever implementiert. Es ist ganz sicher effizienter, wenn man nur 42 aus 1 Million entfernt. Aber ich bin mir nicht sicher bei 999,999 aus 1 Million, denn in den letzten Schritten hat die Merkliste eine ähnliche Länge wie der Originalstring, was sich auch ganz schön ziehen kann. Bei der Variante mit der Stringmanipulation hat man die hohen Kosten zu Anfang, solange der String noch lang ist. Bei der Variante mit der Merkliste hat man die hohen Kosten am Ende, wenn die Merkliste lang wird.

    Ohne es genau durchgerechnet zu haben, hat beides wahrscheinlich die gleiche Komplexitätsklasse, wenn man Eingaben der Länge N und N-1 hat. Aber wenn man Eingaben der Länge N und M (mit M < N-1) hat, dann ist die Merkliste besser. Grob geschätzt (ist hier ein Informatiker anwesend, der Lust hat, das genau zu durchdenken?) hat der Stringalgorithmus die Komplexität O(N * M), wohingegen die Merkliste etwas in der Richtung O(M² + N) haben dürfte.

    Außerdem haben wir hier einen echten Algorithmus, wo eine linked list tatsächlich mal die bestmögliche Datenstruktur (für die Merkliste) sein dürfte, weil wir sowohl Iteration als auch Einfügen an der iterierten Stelle brauchen. Kann man sich rot im Kalender ankreuzen. edit: Oder auch nicht. Die Idee von Finnegan (siehe unten) ist viel besser und will keine Listen.

    PS: Algorithmus als Pseudocode:

    • Starte mit leerer Merkliste, String der Länge N, und Zahlenliste der Länge M (M < N).
    • Gehe durch alle Zahlen im Array:
      • Nehme die Zahl X aus dem Array
      • Iteriere durch Merkliste
        • Stopp, wenn wir am Ende sind oder auf eine Zahl treffen, die größer ist als das aktuelle X
        • Erhöhe X um 1, wenn wir nicht gestoppt haben
      • Füge das aktuelle X vor der Position ein, an der wir geendet sind
    • Die fehlenden Werte in der Merkliste sind die Indizes der verbliebenen Zeichen
      • Man braucht nicht unbedingt die komplette Merkliste zu durchsuchen, man kann aufhören, wenn man N - M fehlende Werte gefunden hat.


  • Bei der trivialen Iteration kann man x-Zeichen auf einmal löschen, wenn x mal hintereinander die selbe Zahl n kommt.
    Bei n, n-1, n-2,...Folgen kann man diese auch in einem Rutsch löschen.

    Aber die Idee nur auf dem Array zu arbeiten finde ich intuitiv auch erst mal besser.



  • Wie wäre es das Problem rückwärts anzugehen?

    Ich habe den Index i des letzten Buchstabens innerhalb str in einem beliebigen Schritt in dem Algorithmus.

    "...a..."
        i
    

    Im vorherigen Schritt gab es zwei Möglichkeiten, wie der String ausgesehen hat:

    "...a...X..."
        i   j
    

    oder

    "...X...a..."
        j  i
    

    a ist der letzte Buchstabe, j ist der Index und X der Buchstabe der in diesem Schritt entfernt wurde. Im ersten Fall verändert sich i nicht, da ein nachfolgendes Zeichen entfernt wird. Im zweiten ist der Index von a um 1 kleiner geworden, d.h. er war im vorherigen Schritt um 1 größer.

    Ich würde jetzt mal so intuitiv sagen, wenn j <= i, dann muss i um 1 erhöht werden, ansonsten bleibt es unverändert. Am Ende, wenn man das Array rückwärts abgearbeitet hat, sollte man den korrekten Index innerhalb des Ausgangs-Strings in i haben.

    Könnte das hinhauen, oder hab ich hier irgendwo nen Denkfehler?

    a = <array>
    n = length(a)
    // Im letzten Schritt beinhaltet str nur ein Zeichen, der Index des
    // "Letzten Buchstabens" innerhalb von str ist hier also immer 0.
    i = 0
    
    for (j = n - 1; j >= 0; j--)
       i += (a[j] <= i)
    
    print(str[i]) // Hinweis: str ist hier natürlich der Ausgangs-String.
    

  • Mod

    @Finnegan : Ich kann dein Argument nachvollziehen, und kann kein Gegenbeispiel finden. Das wäre linear in der Länge des Zahlenarrays, was unschlagbar sein dürfte.

    Es müsste sich sogar auf eine beliebige Anzahl verbleibender Zeichen anwenden lassen, weil man deren Anzahl kennt.

    PS: Mittagspause gehabt:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <numeric>
    #include <iterator>
    
    template<typename T> std::string last_survivors(const std::string &letters, const T& numbers)
    {
      std::vector<std::size_t> survivor_indices(letters.size() - numbers.size());
      std::iota(survivor_indices.begin(), survivor_indices.end(), 0);
      // Habe hier gerade keinen C++20 Compiler parat für reverse_view :-(
      for(auto number_it = std::make_reverse_iterator(std::end(numbers)); 
          number_it != std::make_reverse_iterator(std::begin(numbers)); 
          ++number_it)
        {
          for (auto& survivor_index: survivor_indices)
            survivor_index += survivor_index >= *number_it;
        };
      std::string result;
      result.reserve(survivor_indices.size());
      for (auto survivor_index: survivor_indices)
        result.push_back(letters[survivor_index]);
      return result;
    }
    
    int main()
    {
      std::cout << last_survivors("abcd", std::vector<std::size_t>({0, 2, 1})) << '\n'
                << last_survivors("abcdefghij", std::vector<std::size_t>({6, 2, 6, 3, 3, 2, 0, 1, 1})) << '\n'
                << last_survivors("abcdefghijklmnopqrstuvwxyz", std::vector<std::size_t>({20, 2, 6, 9, 11, 4, 0, 19, 14, 13, 13, 2})) << '\n';
    }
    

    Ich sehe nicht, wie O(M * (N-M)) noch schlagbar sein sollte.



  • @SeppJ sagte in Last Survivor (Codewars):

    Ich sehe nicht, wie O(M * (N-M)) noch schlagbar sein sollte.

    Hah cool. Grad auch schon überlegt, dass man dafür für jedes verbleibende Zeichen den Index individuell berechnen muss und man ne innere Schleife benötigt.

    Hatte eben noch an der Komplexität überlegt, die hatte mich etwas verwirrt. Seh ich das richtig, dass die für M=1: O(1 * (N - 1)) = O(N) ist und für M=N/2: O((N/2) * (N - N/2)) = O(N²/2) = O(N²) ... das macht mich irgendwie wenig Kirre wenn ich nen Algo sehe, der nicht weiss ob er lineare oder quadratische Laufzeit haben will 🙂


  • Mod

    @Finnegan sagte in Last Survivor (Codewars):

    Hatte eben noch an der Komplexität überlegt, die hatte mich etwas verwirrt. Seh ich das richtig, dass die für M=1: O(1 * (N - 1)) = O(N) ist und für M=N/2: O((N/2) * (N - N/2)) = O(N²/2) = O(N²) ... das macht mich irgendwie wenig Kirre wenn ich nen Algo sehe, der nicht weiss ob er lineare oder quadratische Laufzeit haben will 🙂

    Und für M=N-1 ist es dann wieder (N-1)*(N-(N-1)) = N-1 ~ O(N). Ja, das ist ja wirklich etwas verrückt, ist mir gar nicht aufgefallen 🙂
    Aber soweit ich das sehe, stimmt meine Abschätzung doch, oder?



  • @SeppJ sagte in Last Survivor (Codewars):

    Und für M=N-1 ist es dann wieder (N-1)*(N-(N-1)) = N-1 ~ O(N). Ja, das ist ja wirklich etwas verrückt, ist mir gar nicht aufgefallen 🙂
    Aber soweit ich das sehe, stimmt meine Abschätzung doch, oder?

    Ich denke ja, da kam ich eben auch drauf bevor du gepostet hast, vorhin beim Tee machen, da stand ich am Wasserkocher und war verwirrt ob nun quadratisch oder linear... trotzdem keinen Nerv für nen richtig formellen Beweis (den man eh nicht unbeding besser verstehen kann) 😉

    P.S.: Und da sag noch einer, wir würden hier keine "Hausaufgaben" machen. Das stimmt nur bedingt, für die langweiligen Allerweltshausaufgaben 😛


  • Mod

    In 2D kann man Funktionen halt nicht so einfach als linear oder quadratisch kategorisieren 🙂

    @Finnegan sagte in Last Survivor (Codewars):

    P.S.: Und da sag noch einer, wir würden hier keine "Hausaufgaben" machen. Das stimmt nur bedingt, für die langweiligen Allerweltshausaufgaben 😛

    Es hilft sicher auch, dass zeropage eine anregende Frage gestellt hat, anstatt nur die Aufgabe zu posten.

    Vom Titel her ist das aber keine Hausaufgabe, sondern von einer Codechallengeseite: https://www.codewars.com/kata/609eee71109f860006c377d1
    Wäre interessant, wenn @zeropage uns hinterher zurück meldet, wie deine Idee sich so schlägt.



  • @SeppJ sagte in Last Survivor (Codewars):

    In 2D kann man Funktionen halt nicht so einfach als linear oder quadratisch kategorisieren 🙂

    @Finnegan sagte in Last Survivor (Codewars):

    P.S.: Und da sag noch einer, wir würden hier keine "Hausaufgaben" machen. Das stimmt nur bedingt, für die langweiligen Allerweltshausaufgaben 😛

    Es hilft sicher auch, dass zeropage eine anregende Frage gestellt hat, anstatt nur die Aufgabe zu posten.

    Vom Titel her ist das aber keine Hausaufgabe, sondern von einer Codechallengeseite: https://www.codewars.com/kata/609eee71109f860006c377d1

    Daher auch in Anführungsstrichen. Zumindest mir gehts so, dass wenn das Problem interessant genug ist, ich oft nicht widerstehen kann 😁

    Wäre interessant, wenn @zeropage uns hinterher zurück meldet, wie deine Idee sich so schlägt.

    Würde mich auch interessieren, allerdings habe ich den Verdacht, dass die Aufgabe eventuell mit dem Hintergedanken einer solchen Lösung gestellt wurde. Das sind eigentlich wie ich finde die besten Aufgaben, die eine naheliegende Geradeaus-Lösung haben, aber auch eine besonders elegante, wenn man etwas um die Ecke denkt. Als Dozent sollte man sich die ins Merkheft schreiben.


  • Mod

    Ja, garantiert ist das so gemeint. Es fühlt sich zu richtig an, wie man sich hier schön von der naiven Lösung zu der super-effizienten von-hinten-gedacht Lösung vorarbeitet. Aber mich würde noch interessieren, ob wir wirklich nicht noch einen genialen Trick übersehen haben beim Update der N-M Indizes. Vielleicht kann man ausnutzen, dass diese (per Konstruktion) sortiert sind? So kann man schneller gezielt die Indizes finden, die um 1 erhöht werden müssen. Das senkt aber nicht die Komplexitätsklasse, weil man im Durchschnitt immer noch ca. (N-M)/2 Updates macht, was für jeden Teilschritt immer noch O(N-M) ist. Aber vielleicht übersehe ich auch noch einen genialen Kniff. Deine Lösung habe ich ja selber auch nicht gesehen, weil ich mich zu sehr auf meine Merkliste versteift hatte und zu viel Entwicklungszeit dort rein gesteckt habe, anstatt nochmal über das Problem an sich nachzudenken.

    Leider ist die Aufgabe aber mit einem festen N-M=1, insofern wird diese spezielle Frage wohl ohne Antwort bleiben.

    PS: Hier die leichte Verbesserung, die die Sortierung ausnutzt. Die Verbesserung sind die Zeilen 10-13.

    template<typename T> std::string last_survivors(const std::string &letters, const T& numbers)
    {
      std::vector<std::size_t> survivor_indices(letters.size() - numbers.size());
      std::iota(survivor_indices.begin(), survivor_indices.end(), 0);
      // Habe hier gerade keinen C++20 Compiler parat für reverse_view :-(
      for(auto number_it = std::make_reverse_iterator(std::end(numbers));
          number_it != std::make_reverse_iterator(std::begin(numbers));
          ++number_it)
        {     
          for (auto lb = std::lower_bound(std::begin(survivor_indices), std::end(survivor_indices), *number_it);
               lb != std::end(survivor_indices); 
               ++lb)
             ++*lb;
        };
      std::string result;
      result.reserve(survivor_indices.size());
      for (auto survivor_index: survivor_indices)
        result.push_back(letters[survivor_index]);
      return result;
    }
    


  • @SeppJ sagte in Last Survivor (Codewars):

    Ja, garantiert ist das so gemeint. Es fühlt sich zu richtig an, wie man sich hier schön von der naiven Lösung zu der super-effizienten von-hinten-gedacht Lösung vorarbeitet. Aber mich würde noch interessieren, ob wir wirklich nicht noch einen genialen Trick übersehen haben beim Update der N-M Indizes.

    Instinktiv würde ich vermuten, dass da irgendwas gehen muss - vielleicht auch nur weil ich noch nicht darüber hinweg bin, dass der in der Mitte der M-Größe des Problems plötzlich quadratisch wird 😣 ... habe da aber auch keine gute Idee gerade.

    Vielleicht kann man ausnutzen, dass diese (per Konstruktion) sortiert sind?

    Bei O(n²) hätte man auch einmal explizit Sortieren frei, auch das ganze Array oder den String... falls das denn hilft und man auf dieser Basis mit irgendwas linearem weitermachen kann. Der gute alte Hammer aus dem Algorithmen-Werkzeugkasten 😁

    So kann man schneller gezielt die Indizes finden, die um 1 erhöht werden müssen. Das senkt aber nicht die Komplexitätsklasse, weil man im Durchschnitt immer noch ca. (N-M)/2 Updates macht, was für jeden Teilschritt immer noch O(N-M) ist. Aber vielleicht übersehe ich auch noch einen genialen Kniff.

    Jo, vielleicht kommt mir noch was in den Sinn. Ist auf jeden Fall ein interessantes Problem, weil man irgendwie eine Lösung riechen kann (haben sich aber in der Geschichte auch schon so manche mit in die Nesseln gesetzt mit diesem "Geruchssinn" 🙂 )



  • @SeppJ sagte in Last Survivor (Codewars):

    Wäre interessant, wenn @zeropage uns hinterher zurück meldet, wie deine Idee sich so schlägt.

    Ich konnte immerhin einen funktionierenden Code mit @Finnegan Idee schreiben.
    Ich hab das dann so verstanden, das der Trick an der Sache ist, das array vorzubereiten:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <random>
    
    struct LSStruct
    {
    	std::string str;
    	std::vector<int> arr;
    	void print()
    	{
    		std::cout << "\nstring: " << str << '\n';
    		std::cout << "array : ";
    		for (const auto i : arr) std::cout << i << " ";
    		std::cout << '\n';
    	}
    };
    
    LSStruct createLSStruct(const int n)
    {
    	std::random_device rd;
    	std::mt19937 rng(rd());
    
    	LSStruct Str;
    	// create string width size n
    	for (auto i = 0; i < n; ++i)
    	{
    		std::uniform_int_distribution<int> dist(33, 126); // ascii from char '!' to  char '~'
    		Str.str.push_back(char(dist(rng)));
    	}
    	// create array width size str.size() - 1
    	auto size = Str.str.size() - 1;
    	for (auto i = 0; i < Str.str.size() - 1; ++i)
    	{
    		std::uniform_int_distribution<int> dist(0, size);
    		Str.arr.push_back(char(dist(rng)));
    		size--;
    	}
    
    	return Str;
    }
    
    void removeLetters(LSStruct& Str)
    {
    	Str.print();
    	for (const auto i : Str.arr)
    	{
    		Str.str.erase(Str.str.begin() + i); // erase char at position i
    		Str.arr.erase(Str.arr.begin());     // erase first number in array
    		Str.print();
    	}
    }
    
    int main()
    {
    	LSStruct Str = createLSStruct(5);
    	
    	removeLetters(Str);
    	std::cout << "\nLast Survivor: " << Str.str << '\n';
    }
    

    Die print Funktionen sind nur zur Anschauung da.


Anmelden zum Antworten