Last Survivor (Codewars)

[SeppJ]

Die Implementierung finde ich jetzt aber schwer enttäuschend nach diesem Thread. Nicht nur algorithmisch, sondern auch vom Stil her. Ein String ist bei dir eine Kombination aus Array und Zeichenkette?

[zeropage]

Wieso?

[SeppJ]

@zeropage sagte in Last Survivor (Codewars):

Wieso?

Weil es ja der dumme, naive Algorithmus ist, der O(N²) ist, nicht der coole von Finnegan.

[zeropage]

@SeppJ sagte in Last Survivor (Codewars):

Ein String ist bei dir eine Kombination aus Array und Zeichenkette?

Namensgebung. Mir ist nicht besseres eingefallen. Habe auch schon "Team" oder Group" überlegt. Werde das mal schnell editieren, auch wenn ich noch keine Idee habe.

[zeropage]

@SeppJ sagte in Last Survivor (Codewars):

@zeropage sagte in Last Survivor (Codewars):

Wieso?

Weil es ja der dumme, naive Algorithmus ist, der O(N²) ist, nicht der coole von Finnegan.

Achso. Daran war ich jetzt nicht so fokussiert. ich glaube, Du überschätzt mich ein wenig.

[SeppJ]

Nun, es ist eine Codingchallenge, da hatte ich schon irgendwie auf die bestmögliche Implementierung gehofft . Aber ich habe ja meine Implementierung von Finnegans Idee. Da kann ich wenigstens sagen, dass auch ich etwas beigetragen habe, mit dem binary search auf den Restindizes.

[Finnegan]

@zeropage sagte in Last Survivor (Codewars):

@SeppJ sagte in Last Survivor (Codewars):

@zeropage sagte in Last Survivor (Codewars):

Wieso?

Weil es ja der dumme, naive Algorithmus ist, der O(N²) ist, nicht der coole von Finnegan.

Achso. Daran war ich jetzt nicht so fokussiert. ich glaube, Du überschätzt mich ein wenig.

In diesem Thread hier beschrieben, wie der schnelle Algorithmus funktioniert, inklusive Implementierung in Pseudo-C++.

Oder hier (direkt darunter) eine konkrete Implementierung von @SeppJ, die auf der Idee aufbaut, das Problem allerdings für beliebig viele "last survivors" löst.

Hier auch nochmal eine konkrete Implementierung von mir in ziemlich modernem C++ (C++20) für das einfache Problem mit nur einem Survivor:

#include <cstddef>
#include <string>
#include <iostream>
#include <ranges>
#include <algorithm>

auto last_survivor(
    const std::string& s,
    const std::ranges::input_range auto& remove_indices
)
{
    std::size_t i = 0;
    std::ranges::for_each(
        remove_indices | std::views::reverse,
        [&](const auto& j){ i += i >= j; }
    );
    return s[i];
}

auto main() -> int
{
    std::string s = "zbk";    
    int a[] = { 0, 1 };
    
    std::cout << last_survivor(s, a) << std::endl;
}

(bitte nicht wieder für den Stil mit Trailing Return und schmalem Zeichen-Limit lynchen! )

Oder als "superkompakte" Alternative für Fans von "Einzeilern":

#include <numeric>

...

auto last_survivor(
    const std::string& s,
    const std::ranges::input_range auto& remove_indices
)
{
    return s[
        std::accumulate(
            std::rbegin(remove_indices),
            std::rend(remove_indices),
            std::size_t{ 0 },
            [](const auto& i, const auto& j){ return i >= j; }
        )
    ];
}

[Leon0402]

@Finnegan Ich finde den Einzeiler deutlich eleganter hier. Wobei ihn natürlich auch als zweizeiler schreiben kann wie in deiner ersten Version, wenn es einem dann doch bisschen zu viel in einer Zeile ist.

Und mit https://github.com/ericniebler/range-v3 kann man auch ranges accumulate mit remove_indices | std::views::reverse wieder verwenden, was ich schöner finde.