Welcher Code ist einfacher (zu verstehen) - Motivation Springerproblem

Werner Salomon

Hallo alle!

Als ich dieses Programm im Thread Springerproblem gesehen habe, hatte ich doch etwas Mühe das eigentliche
Problem zwischen den Codezeilen zu sehen und fragte mich, wie man das besser machen könnte.

Ich habe meine Version hinten angehängt. Und jetzt die Frage bzw. die Aufforderung an Euch, die Unterschiede zu kommentieren.
Ist das, was ich da abgeliefert habe, auch für Anfänger einfacher oder schreckt die Verwendung von einigen nicht trivialen Stilmittel wie operator-Überladung, Algorithmen, ein bisschen Template und Lambda-Ausdrücke bereits so weit ab, dass man sich doch besser auf simpleren Code zurückzieht? Bzw. ist der den simple?

Bin neugierig auf Eure Kommentare - besonders von den "Anfängern"
Gruß
Werner

PS.: man kann in beiden Fällen sicher noch performanenter coden - aber das ist jetzt nicht das Thema.

#include <algorithm>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>

struct Pos // eine Position auf dem Brett
{
    Pos( int x, int y ) 
        : x_( x ), y_( y )
    {}
    Pos& operator+=( const Pos& b )
    {
        x_ += b.x_; y_ += b.y_;
        return *this;
    }
    Pos& operator-=( const Pos& b )
    {
        x_ -= b.x_; y_ -= b.y_;
        return *this;
    }

    template< typename B >
    bool ist_auf_dem_brett( const B& brett ) const
    {
        return x_ >= 0 && x_ < X(brett) && y_ >= 0 && y_ < Y(brett); 
    }
    std::size_t index( int nX ) const
    {
        return y_*nX + x_;
    }
    friend std::ostream& operator<<( std::ostream& out, const Pos& pos )
    {
        return out << pos.x_ << ";" << pos.y_;
    }
private:
    int x_, y_;
};
Pos operator+( Pos a, const Pos& b ) { return a += b; }

struct Brett
{
    Brett( int nX, int nY )
        : nX_( nX )
        , felder_( std::size_t(nX*nY), false ) // alle Felder sind nicht besetzt
        , belegte_felder_( 0 )
    {}
    bool setze( const Pos& pos ) // 'true' falls das Feld bei 'pos' vorhanden und frei war
    {
        if( !pos.ist_auf_dem_brett( *this ) )
            return false;
        const std::size_t idx = pos.index( nX_ );
        if( felder_[idx] )
            return false; // Feld ist bereits belegt
        felder_[idx] = true;
        ++belegte_felder_;
        return true;
    }
    void nehme_zurueck( const Pos& pos ) // gibt das Feld bei 'pos' wieder frei
    {
        assert( felder_[pos.index( nX_ )] ); // nur die Rücknahme besetzter Felder ist zulässig, wg. --belegte_felder_
        felder_[pos.index( nX_ )] = false;
        --belegte_felder_;
    }
    bool voll() const
    {
        return belegte_felder_ == felder_.size();
    }
    // --  Schnittstelle für Pos::ist_auf_dem_brett() (s.o.)
    friend int X( const Brett& b ) { return b.nX_; }
    friend int Y( const Brett& b ) { return b.felder_.size()/b.nX_; }

private:
    int nX_;
    std::vector< bool > felder_;
    std::size_t belegte_felder_;
};

namespace
{   // --  die möglichen Züge eines Springers
    const Pos springer_zuege[] = { 
        Pos( 2, 1), Pos( 1, 2), Pos(-1, 2), Pos(-2, 1), 
        Pos(-2,-1), Pos(-1,-2), Pos( 1,-2), Pos( 2,-1) };
    const Pos* const springer_zuege_ende = springer_zuege + sizeof(springer_zuege)/sizeof(*springer_zuege);
}

int main()
{
    using namespace std;
    Brett brett(8,8);
    vector< const Pos* > zuege; // s. springer_zuege[]
    const Pos start(0,0);

    Pos aktuell = start;
    brett.setze( aktuell ); // das erste Feld besetzen
    for( auto naechster_versuch = springer_zuege; !brett.voll(); )
    {
        auto zug = find_if( naechster_versuch, springer_zuege_ende, 
            [&aktuell, &brett]( const Pos& zug )-> bool { return brett.setze( aktuell + zug ); } );
        if( zug != springer_zuege_ende )
        {   // --   Zug konnte ausgeführt werden
            aktuell += *zug;
            zuege.push_back( zug );
            naechster_versuch = springer_zuege;
        }
        else if( !zuege.empty() )
        {   // --   ==> backtrack
            brett.nehme_zurueck( aktuell );
            aktuell -= *zuege.back();
            naechster_versuch = zuege.back() + 1; // nächster im Feld springer_zuege[]
            zuege.pop_back();
        }
        else
        {
            cout << "Fuer dieses Brett gibt es keine Loesung" << endl;
            break;
        }
    }

    // --   Ausgeben der Lösung
    aktuell = start;
    int i = 1;
    for( auto z = begin(zuege); z != end(zuege); ++z, ++i )
        cout << setw(3) << i << ") " << **z << " -> (" << (aktuell += **z) << ")\n";
}

Columbo

[&aktuell, &brett]( const Pos& zug )-> bool { return brett.setze( aktuell + zug ); }

[&]( const Pos& zug ) { return brett.setze(aktuell + zug); }

Ist das, was ich da abgeliefert habe, auch für Anfänger einfacher oder schreckt die Verwendung von einigen nicht trivialen Stilmittel wie operator-Überladung, Algorithmen, ein bisschen Template und Lambda-Ausdrücke bereits so weit ab, dass man sich doch besser auf simpleren Code zurückzieht? Bzw. ist der den simple?

Seit wann sind Algorithmen denn ein nicht triviales Stilmittel? Und Operatorenüberladung gehört zu den Basics. Lambdas hingegen sind hier mMn. unangebracht.
Edit: Wenn denn die passende Schleife nicht scheußlicher erscheint.

Jester

Imo verschlimmbessert. Den originalcode bissel aufräumen, dann schrumpft er noch deutlich. Aber auch jetzt schon sieht man dass die neue lösung deutlich länger und komplexer ist.

knivil

Problem zwischen den Codezeilen zu sehen

Es ist immer problematisch, die Funktion eines Gens anhand seiner DNA-Sequenz zu erkennen. Auch in diesem Fall laesst sich keine Vorstellung vom Problem durch den Programmcode gewinnen, wenn es nicht schon bekannt ist. Zu den verwendeten Sprachmitteln: Zuviel des Guten fuer Anfaenger bspw. Lambda oder anonyme namespaces. Zu wenig des Guten fuer Anfaenger. Warum ist Springer keine Klasse/Typ mit assoziertem Bewegungsmuster? Warum so haesslich im Namespace verstecken, warum ein anonymer namespace?

Werner Salomon

Hallo Ihr drei,

Arcoth schrieb:

Seit wann sind Algorithmen denn ein nicht triviales Stilmittel? Und Operatorenüberladung gehört zu den Basics. Lambdas hingegen sind hier mMn. unangebracht.

Na ja - manch anderer ist geschockt, wenn er auf die Kombination von all dem stößt. Für einen Profi sollte das Standard sein, aber es ist nicht jeder Profi.

Jester schrieb:

Imo verschlimmbessert. Den originalcode bissel aufräumen, dann schrumpft er noch deutlich. Aber auch jetzt schon sieht man dass die neue lösung deutlich länger und komplexer ist.

Könntest Du bitte begründen, warum Du die neue Lösung für komplexer hältst - ich unterstelle mal, dass 'komplexer' auch schwerer verständlich bedeutet. Warum ist die Lösung von brianfox für Dich besser verständlich - bzw. einfacher?

knivil schrieb:

Problem zwischen den Codezeilen zu sehen

Es ist immer problematisch, die Funktion eines Gens anhand seiner DNA-Sequenz zu erkennen. Auch in diesem Fall laesst sich keine Vorstellung vom Problem durch den Programmcode gewinnen, wenn es nicht schon bekannt ist.

Ich interpretiere Deine Antwort, dass Du beide Varianten als schwer verständlich einstufst.

knivil schrieb:

Zu wenig des Guten fuer Anfaenger.

Welche Stil- oder Design-Mittel würdest Du denn vorschlagen, um den Code besser verständlich zu machen?

knivil schrieb:

Warum ist Springer keine Klasse/Typ mit assoziertem Bewegungsmuster?

Interessanter Vorschlag - kannst Du mal ein Code-Schnipsel posten, was verdeutlicht, was Du genau damit meinst.

knivil schrieb:

Warum so haesslich im Namespace verstecken, warum ein anonymer namespace?

Das limitiert die Gültigkeit der 'globalen' Variable auf diese Datei. Ist eine Empfehlung von Bjarne Stroustrup - Link finde ich gerade nicht, soll aber auch hier stehen: "The C++ Programming Language, 3rd ed, pg 819"

Ich möchte meine Frage noch mal wiederholen. Warum ist der eine oder andere Code verständlicher? Wie kann man erreichen den Code besser lesbar zu machen?
Wäre prima, wenn sich auch der eine oder andere Beginner dazu äußern würde.

Gruß
Werner

Jester

Schau doch nur mal die Menge an Code an die du fanriziert hast, das ist viel mehr, dabei kann man das Original noch sehr bequem kürzen (man muss ja nichg 10 zeilen lang die springerzüge auflisten und etliche leere ifs haben. Wenn man mit aufräumen ferrig ist schätz ich mal dass allein die anzahl der zeilen bei <2/3 deiner lösung liegen, ganz zu schweigen vond er anzahl der tokens in den zeilen. Und das ganze völlig ohne irgendwelchen unnötigen ballast wie operatorüberladung etc.

Das hier ist imo typisches over-engineering, wie es hier gelehrt wird.

Jester schrieb:

Schau doch nur mal die Menge an Code an die du fanriziert hast, das ist viel mehr, dabei kann man das Original noch sehr bequem kürzen (man muss ja nichg 10 zeilen lang die springerzüge auflisten und etliche leere ifs haben. Wenn man mit aufräumen ferrig ist schätz ich mal dass allein die anzahl der zeilen bei <2/3 deiner lösung liegen, ganz zu schweigen vond er anzahl der tokens in den zeilen. Und das ganze völlig ohne irgendwelchen unnötigen ballast wie operatorüberladung etc.

Das hier ist imo typisches over-engineering, wie es hier gelehrt wird.

Mir fällt gerade auf, dass C++.de ja schon ewig den "Like-Button" hat, nur ohne Zähler.

otze

Jester schrieb:

Das hier ist imo typisches over-engineering, wie es hier gelehrt wird.

volkard

Die schlichte Lösung bettelt darum, weiter vereinfacht und optimiert zu werden. Die fette Lösung eigentlich nicht mehr, die mag man nicht anfassen, zu viel steckt wo, wo man es nicht erwartet: nX ist da, nY steckt verrechnet im vector, das Brett erledigt die Zeidimenionalität(also eigentlich den op[][]) UND das setzen/zurücknehmen, aber die main() macht dann das Vollsetzen, aber der Kern der Zweidimenionsionalität, das y*sizex+x passiert in Pos (und Pos kriegt dazu ein Brett gezeigt, um mal schnell Brett-Interna anzuschauen(!!!)), also alles da, wo man es nicht erwartet.

CConflict

ACHTUNG! offtopic:

Findet ihr denn Unterstrich bei privaten Variablen besser lesbar, als denn gleichen Namen in C++11 zu verwenden ?

class Foo
{
    public:
        explicit Foo( int x ) : x_(x) 
    private:
        int x_;
};

class Bar 
{
    public:
        explicit Bar( int x ) : x(x)
    private:
        int x;
};

Wo ist bei euch noch der Unterschied zwischen Struct und Class? Das struct hat private Variablen und es werden sogar Operatoren überladen. Ist struct hier schneller oder ressourcenschonender oder macht der Compiler daraus eine Klasse ?

camper

Keiner der die fehlende Unterscheidung zwischen einer Position und einem Bewegungsvektor bemängelt? :p

volkard

CConflict schrieb:

Ist struct hier schneller oder ressourcenschonender oder macht der Compiler daraus eine Klasse ?

Der Compiler macht das selbe daraus. Es gibt in C++ (nicht C++/CLI) keinen Leistungsunterschied zwischen struct und class, nur wenn man nix hinschreibt, ist in der class alle private und in der struct public.

Columbo

Findet ihr denn Unterstrich bei privaten Variablen besser lesbar, als denn gleichen Namen in C++11 zu verwenden ?

Das ist pure Geschmackssache, aber was auch immer du tust: Konsequent bleiben!

I.A. haben private/ protected Membervariablen eine Kennzeichnung. Bei mir ist das ein m als Präfix:

unsigned mCounter;

Andere packen vor oder hinter den Namen einen Unterstrich.

Pass aber auf dass du dich nicht in Namenskonflikte verrennst:

Each name that contains a double underscore __ or begins with an underscore followed by an uppercase letter (2.12) is reserved to the implementation for any use.

Ist struct hier schneller oder ressourcenschonender oder macht der Compiler daraus eine Klasse ?

Der einzige Unterschied zwischen den beiden sog. class-keys ist, dass der Access bei Vererbung und den Membern standardmäßig public bei struct ist, und private bei class .

class B {};

	struct A : B { int c; };

	A a;
	B& b1 = a; // Da B eine public Basisklasse von A ist, funktioniert dieser implizite Upcast
	a.c = 7;  // c ist public

	class W : B { int c; };

	W w;
	B& b2 = w; // Fehler
	w.c = 7;  // Fehler

Keiner der die fehlende Unterscheidung zwischen einer Position und einem Bewegungsvektor bemängelt?

... und deswegen brauchen wir strong typedefs.

volkard

Arcoth schrieb:

Keiner der die fehlende Unterscheidung zwischen einer Position und einem Bewegungsvektor bemängelt?

... und deswegen brauchen wir strong typedefs.

Nö. Habs für Vektorrechnung mit dieser Unterscheidung probiert und es war nur umständlich.
Hier würde auffallen, daß es sich arg seltsam anfühlt, daß ein Bewegungsvektor fragen kann, ob er auf dem Brett liegt.

strong typedefs sind toll, aber nicht für *diese* Unterscheidung.

Columbo

Hier würde auffallen, daß es sich arg seltsam anfühlt, daß ein Bewegungsvektor fragen kann, ob er auf dem Brett liegt.

Naja, du willst einen anderen Namen, falls die beiden Zahlen als Richtungsvektor verwendet werden, oder nicht?
Ein einfaches Typedef ist dann aber doof.

Den Code habe ich mir gar nicht so genau angesehen (sondern nur sehr grundlegende Operationen erwartet).

Wie wäre es also mit

class Vector2 : Pos
{
    using Pos::ist_auf_dem_brett;
    using Pos::index; // ?

public:
    using Pos::Pos;
};

// Edit: Und dann noch
Pos operator+( Pos, Vector2 );

volkard

Arcoth schrieb:

Wie wäre es also mit

class Vector2 : Pos
{
    using Pos::ist_auf_dem_brett;
    using Pos::index; // ?

public:
    using Pos::Pos;
};

// Edit: Und dann noch
Pos operator+( Pos, Vector2 );

Was ist das? Willste damit sagen: Ein Vector2 ist ein Pos (aber ohne Brettkenntnis), aber keiner darf es wissen (private Erblichkeit), weil ein Pos eigentlich ein Vector2 (aber mit Brettkenntnis) ist?

Columbo

Was ist das? Willste damit sagen: Ein Vector2 ist ein Pos, aber keiner darf es wissen, weil ein Pos eigentlich ein Vecor2 ist?

Mein Fehler, das soll natürlich ganz andersherum passieren. Pos ist ein Vector2 mit speziellen Eigenschaften.
Warte, lass mich mal eine minimalistische Implementierung nach deinem Geschmack schreiben.

~Edit: Wird wohl noch warten, Argentinien vs Schweiz steht auf dem Plan!~

Nexus

CConflict schrieb:

Findet ihr denn Unterstrich bei privaten Variablen besser lesbar, als denn gleichen Namen in C++11 zu verwenden ?

Nein. Ich vermeide Unterstriche ausser in Makros, weil sie zusammengehörige Bezeichner unnötig trennen und es schwerer machen, tatsächliche Trennzeichen (Operatoren) zu erkennen. Aus dem selben Grund benutze ich auch keinen standard_stil .

volkard schrieb:

strong typedefs sind toll, aber nicht für *diese* Unterscheidung.

Kann ich bestätigen. Ich habe auch schon mal die Diskussion geführt, ob 2 Klassen für Position und Grösse besser (weil typsicherer) als generische Vektoren sind. Fand ich nicht, weil es viele Fälle gibt, in denen das eine das andere ist (je nach Kontext macht es Sinn, Position als Vektor vom Ursprung zu betrachten), oder in denen beide nichts bringen (Geschwindigkeit, Beschleunigung, Skalierung, ...). Ausserdem multipliziert sich die Anzahl zu überladender Operatoren, auch wenn einiges davon generisch gelöst werden kann. Schlussendlich hast viele explizite Konvertierungen und komplizierteren Code für etwas, das kaum Fehler verursacht.

Arcoth schrieb:

~Edit: Wird wohl noch warten, Argentinien vs Schweiz steht auf dem Plan!~

War ein wirklich gutes Spiel, schade haben wir so knapp verloren

volkard

CConflict schrieb:

Findet ihr denn Unterstrich bei privaten Variablen besser lesbar, als denn gleichen Namen in C++11 zu verwenden ?

Ich nicht mehr. Hab's mit m_ und _ vorne und hinten probiert, vorne hat's mir am besten gefallen.
Kollissionen gab es eh nur bei Konstruktoren und Settern. Bei Konstruktoren gleift die Initialisiererliste recht gut (als Hilfsmittel auch noch weitergerechte Konstruktoraufrufe und Lamdas). Und Setter muss ich höchst selten bauen (keine GUI-Klassen). Zur Not kann ich ja noch this->x=x schreiben.

Werner Salomon

Ja Wahnsinn, da gibt man den Link auf diesen Thread preis (siehe http://www.c-plusplus.net/forum/326676), und schon stürzen sich die Hyänen auf den hingeworfenen Fleischbrocken.
Soviel Feedback in so kurzer Zeit hätte ich mir im Dezember gewünscht.

camper schrieb:

Keiner der die fehlende Unterscheidung zwischen einer Position und einem Bewegungsvektor bemängelt? :p

Danke Camper, endlich mal eine vernünftige Kritik. Ja - der Gedanke war mir selbst beim Schreiben gekommen - nur..

volkard schrieb:

Habs für Vektorrechnung mit dieser Unterscheidung probiert und es war nur umständlich.

.. mir ging es so wie volkard.
Vielleicht reicht es, Pos einfach einen anderen Namen zu geben (Vector2 ?)

volkard schrieb:

... und Pos kriegt dazu ein Brett gezeigt, um mal schnell Brett-Interna anzuschauen(!!!)), also alles da, wo man es nicht erwartet.

Hm - ok. Irgendwann muss wohl mal entschieden werden, ob ein Springerzug noch auf dem Brett landet. Wen fragt man da?
Das Brett könnte entscheiden, ob die Pos gültig ist, wobei X und Y der Pos zur Verfügung stehen müssten. Zugegeben - ich neige dazu, diese zu 'verstecken'. Aber es spielt natürlich keine Rolle, ob ich die Brettgröße mit X() und Y() abhole oder die Koordinaten der Position.
Also am besten wohl - ab in die Methode Brett::setze mit dieser Abfrage - oder?

macht doch selber mal Vorschläge - oder stehe ich mit meiner Meinung hier tatsächlich gänzlich allein, dass dieses Problem durchaus einen objektorientierten Ansatz verträgt.

Ich lege schon mal was vor - mit Beherzigung Eurer Kritik:

// --   das Spinger Problem (nächster Versuch)
#include <cassert>
#include <complex> // das soll ein Position bzw. ein Zug sein ;-)
#include <iomanip> // setw
#include <iostream>
#include <vector>

namespace knight
{
    const std::complex< int > moves[] = {
        {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}
    };
}

// --   syntactic suger (spart aber die class/struct Pos)
template< typename T > T X( const std::complex< T >& c ) { return real( c ); }
template< typename T > T Y( const std::complex< T >& c ) { return imag( c ); }

// --   das (Schach)brett
class Board
{
public:
    typedef std::complex< int > pos_type; // absolute & relative Position auf dem Brett
    friend class Move;
    static int const FREE = -1;

    Board( int rows, int columns )
        : rows_( rows )
        , columns_( columns )
        , occupies_( rows_ * columns_, FREE )
        , occupy_counter_( 0 )
    {}

    bool is_free( const pos_type& next_pos ) const
    {
        return ( ( Y(next_pos) >= 0 ) && ( Y(next_pos) < rows_ ) ) && ( ( X(next_pos) >= 0 ) && ( X(next_pos) < columns_ ) )
            && field(next_pos) == FREE;
    }
    bool full() const
    {
        return occupy_counter_ == occupies_.size();
    }

    friend std::ostream& operator<<( std::ostream& out, const Board& b )
    {
        auto pos = begin(b.occupies_);
        for( int row = 0; row < b.rows_; ++row )
        {
            for( int column = 0; column < b.columns_ ; ++column, ++pos )
                out << std::setw(3) << *pos << " |";
            out << std::endl;
        }
        return out << std::endl;
    }

    // --   diese Klasse modelliert einen konkreten Zug des Springers
    //      auf dem Brett 'b' an die Position 'pos'
    class Move
    {
    public:
        Move( Board& b, const Board::pos_type& pos )
            : board_( b )
            , current_field_( board_.field(pos) )
        {
            assert( board_.is_free( pos ) );
            current_field_ = board_.occupy_counter_++;
        }
        ~Move() // mit Löschen des Zuges wird der Zug zurück genommen
        {
            assert( current_field_ == board_.occupy_counter_-1 );
            --board_.occupy_counter_;
            current_field_ = FREE;
        }
    private:
        Board& board_;
        int& current_field_;
    };

private:
    int field( const pos_type& pos ) const
    {
        return occupies_[ Y(pos) * columns_ + X(pos) ];
    }
    int& field( const pos_type& pos )
    {
        return occupies_[ Y(pos) * columns_ + X(pos) ];
    }

    int rows_, columns_; // Brettgröße
    std::vector< int > occupies_; // die (überstrichenen) Felder 
    std::size_t occupy_counter_; // Anzahl der bereits vom Springer überstrichenen Felder
};

template< typename B >
void solve( B& board, typename B::pos_type const& current_position, std::ostream& out )
{
    if( board.is_free( current_position ) )
    {
        typename B::Move move( board, current_position );
        if( board.full() )
            out << board << std::endl;
        else
            for( auto next_move: knight::moves )
                solve( board, current_position + next_move, out );
    }
}

int main()
{
    using namespace std;
    cout << "Bitte Feldgroesse eingeben: " << endl;
    int zeilen, spalten;
    cin >> zeilen >> spalten;
    Board board( zeilen, spalten );
    solve( board, Board::pos_type(), cout );
    return 0;
}

Gruß
Werner