Welcher Code ist einfacher (zu verstehen) - Motivation Springerproblem

[hustbaer]

Arcoth schrieb:

Cool, die Assertion kannte ich noch gar nicht:

sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

rofl

Verdammter Dreisternprogrammierer.

[Columbo]

unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

Ja, einer der miesesten Zeilen. Habe mir auch überlegt es zu einer Schleife umzuschreiben, aber dann hatte ich IIRC gleich Vier Zeilen, also wieder zurückgeändert.

So schwer ist es doch nicht, sich da reinzudenken. i und j stellen jeweils einen Sprung dar. i + j Zwei verkettete Sprünge. Vielleicht aber sollte man das wohl nicht in ein Lambda welches als Prädikat für count_if fungiert quetschen.

@hustbaer: Am geilsten finde ich diesen Ausschnitt ((1) - 1) * 2
Das ist entweder ein schlechter Scherz - oder Ergebnis eines Makros.

[Nexus]

Mechanics schrieb:

Spontante Hypothese wäre, dass man komplexere Algorithmen möglichst einfach ausdrücken sollte, weil man sofort eine Struktur und einen Zusammenhang erkennen will.

Code wird auch unnötig komplex, wenn man ständig auf Biegen und Brechen versucht, die Standardbibliothek und fortgeschrittene Sprachmittel zu verwenden. Sowohl STL-Algorithmen als auch Lambda-Ausdrücke sind sehr praktisch, aber manchmal sind Schleifen um einiges einfacher.

Was allerdings auch schon massiv helfen würde, wäre die Aufteilung komplexer Ausdrücke auf mehrere Zeilen. Also den Lambda-Ausdruck separat deklarieren, eventuell in mehreren Zeilen, und an den Algorithmus übergeben. Inline übergeben lohnt sich nur bei sehr kurzen Funktionskörpern. std::begin(c) ist auch nur in der Theorie besser als c.begin() .

[volkard]

Arcoth schrieb:

Cool, die Assertion kannte ich noch gar nicht:

sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

Ist die bei dir schon mal aufgetaucht?

Nee, die kenne ich nicht.

//Ich kommentiere direkt rein

Arcoth schrieb:

... und mein Code.

#include <boost/container/static_vector.hpp>//gut, den hätte ich gebraucht

#include <iostream>
#include <iomanip>   // setw //ballastkommentare
#include <vector>    // vector
#include <utility>   // pair
#include <algorithm> // count_if

struct PositionInfo
{
	int const pos;
	boost::container::static_vector<std::pair<int, unsigned>, 8> moves;
//ok, die folgenden möglichen bis zu 8 Moves werden hier gespeichert. 
//Wäre nach "PositionInfo" nicht gleich drauf gekommen. Warum nicht 
//einfach "DieFolgendenMoeglichenBisZu8Moves"?
	explicit PositionInfo( int pos ) : pos(pos) {}
};

class Board
{
	std::size_t mWidth, mHeight;
//Uih, Breite, Höhe, Zeilen, Spalten, X, Y, das verwirrt mich immer. 
//Nur bei X/Y bin ich fest. Gerade die Matrizen mit m/n machen mich kaputt. 
//Wenn ich voll unsicher bin, mache ich google an. 
//Bei "geile Zeile" habe ich 89k Treffer, 
//bei "geile Spalte" sind es 402k Treffer. 
//So kann ich immer nachschauen, ob Zeilen oder Spalten senkrecht sind. 
//Aber wehe, Du verwendest nachher x und y, dann wären sizeX und sizeY 
//doch so, daß man gar nicht wissen muss, ob Height nun x oder y ist. 

	int const knight_jumps[8];

	std::size_t full_w() const { return w() + 4; }
	std::size_t full_h() const { return h() + 4; }
//das +4 ist jetzt ein wenig aus der Luft gegriffen. 

	std::vector<int> mArray;
	std::vector<PositionInfo> mTrace;
//oh, "mTrace". Sagt mir jetzt nix. 
public:

	explicit Board( std::size_t width, std::size_t height ) :
		mWidth{width}, mHeight{height},
		knight_jumps{ 2*int(full_w())+1, 2*int(full_w())-1, -2*int(full_w())-1, -2*int(full_w())+1,
		                int(full_w())+2,   int(full_w())-2,   -int(full_w())-2,   -int(full_w())+2 }, // hässlich wie sonst was, aber was solln wir machen?
		mArray( full_w()*full_h(), -1 ) {}
//Hä????
	std::size_t w() const { return mWidth; }
	std::size_t h() const { return mHeight; }
//intern Klartext aber nach außen Abkürzung? 
	void createMoves( PositionInfo& info ) const
	{
		for (auto i : knight_jumps)
			if (mArray[info.pos + i] == 0)
			{
				unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
				                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

				info.moves.emplace_back( info.pos + i, viable );

				std::sort( std::begin(info.moves), std::end(info.moves), []( auto& lhs, auto& rhs ){ return lhs.second > rhs.second; } );
			}
	}
//Ok, aber warum nicht die leichten Methoden nach vorn? 
	void clear()
	{
		auto i = 2*full_w() + 2;
		while( i != (full_h()-2)*full_w() + 2 )
		{
			std::fill_n( begin(mArray) + i, full_w() - 4, 0 );
			i += full_w();
		}

		mTrace.clear();
	}
//Weiß nicht, hast irgendwie eine innere Schleife gespart. 
	void do_next_move()
	{
		auto const next = last().moves.back();
		last().moves.pop_back();

		mTrace.emplace_back( next.first );
		mArray[next.first] = mTrace.size();
	}
//So fohle ich mich, wenn ich fremden Lisp-Code lese. 
	PositionInfo& last() { return mTrace.back(); }

	bool backtrack()
	{
		while( last().moves.empty() )
		{
			mArray[last().pos] = 0;

			mTrace.pop_back();

			if( mTrace.empty() )
				return false;
		}

		return true;
	}
//Das ist das Problem! Du redest hier nicht von Brettern, Stellungen, 
//Zügen, Springen und so, und daß sie Züge machen oder zurücknehmen, 
//sondern von empty, last, pop_back, und std::gehansele
	bool solve( int start_x, int start_y )
	{
		clear();

		mTrace.reserve( w()*h() );
//Habs wieder vergessen, was w und h waren. w war die anzahl der Spalten? 

		// Start-Position
		mTrace.emplace_back( (start_y + 2)*full_w() + 2 + start_x );

		mArray[last().pos] = 1;

		while( mTrace.size() != w()*h() )
		{
			createMoves( last() );

			if( !backtrack() )
				return false;

			do_next_move();
		}

		return true;
	}

	void pretty_print( std::ostream& stream )
	{
		auto const width = std::log10(w()*h()) + 1;
		for( auto anchor = 2*full_w() + 2; anchor != (full_h()-2)*full_w() + 2; anchor += full_w() )
		{
			for( auto i = anchor; i != anchor + full_w() - 4; ++i )
				stream << '|' << std::setw(width) << mArray[i];
			stream << "|\n";
		}
	}
};

int main()
{
	size_t w , h;
	if( !(std::cin >> w >> h) )
		return 0;

	Board board(w, h);

	for( size_t x = 0; x != w; ++x )
	for( size_t y = 0; y != h; ++y )
	{
		if( board.solve( x, y ) )
			board.pretty_print( std::cout );
		std::cout << std::string(50, '~') << '\n';
	}
}

Versagt aber leider bei so 16x16. Eine Ahnung woran es liegen könnte?

Hab keine Lust, Fehler zu suchen. Ich bau lieber Code ohne Fehler.

Arcoth schrieb:

Eindimensionale Indizierung und static_vector (welchen ich im Übrigen verdammt sexy finde!) sind für die Optimierung, genau wie die Sentinels. Seitlich an Sentinels sparen geht hier leider nicht (weil die Dimensionen kleiner als 8x8 sein können).

Geht.

Arcoth schrieb:

Mir fällt gerade auf dass die Eindimensionale Indizierung hier Schwachsinn ist... tja. Hätte ich nicht vom Schachprogrammieren übernehmen dürfen.

Ist hier nur O(1)-Schwachsinn, weil das Schachprogramm viel mehr Feldgrenzenüberprüfungen machen muss. Hab's ja auch gemacht (und dann rückgebaut).

Arcoth schrieb:

Edit: Ist schon krass wieviel lesbarer dein Code ist... wie schaffst du das nur?

Ich bin einfach viel zu faul, um Fehler zu suchen. Also gewöhne ich mir einen Stil an, den sogar ein Schimpanse lesen kann. Denn ICH muss nachher die Fehler wegmachen. Schmuddelcode nach einem halben Jahr?

Gleichzeitig bin ich total performancefixiert und haue keine Zeile raus, die lahmer wäre als mit C. Das geht mit C++. Ich kenne keine andere Sprache, wo ich so gut meine beiden Hobbies unter einen Hut bringen könnte.

Mein Schlüsselerlebnis war, als ich zu Studienbeginn (schon 5 Jahre Basic-Erfahtung) einen Kompimierer (in C) schrieb, wegen Zeitbelastung ihn ein halbes Jahr liegen lassen musste, und bei Wiederaufnahme von ca 300 Zeilen Code genau außer der "void main()" (ja, damals war void üblich) und geschweiften Klammern genau keine Zeile Code entschlüsseln konnte, obwohl mir mein geplantes Verfahren noch 100%-ig klar war. Einige Wochen habe ich damit verbracht, mir den alten Code anzuschauen, in der Hoffnung, das Rätsel zu knacken. Nöö, es ist nicht gelungen. Ok, damals war ich jung und doof. Jetzt bin ich nicht mehr jung.

Dann so rumgelesen und rumgelernt…
Irgendwann kam der C++-Hype. Mein erstes C++-Buch war ein Wurstbrot-Buch. Danach war ich so klug als wie zuvor oder dümmer.

Das zweite war der Meyers, GRANATE! Habs ca 30-mal gelesen. Anfangs nix verstanden und mit jedem Lesen ein wenig mehr. 9 Monate nix außer Meyers und nicht vermeidbaren Körperfunktionen.

Gegenfrage: Warum willst Du (in Vertretung der PlayStation-Generation) immer den Code noch komplizierter machen als das Problem ist?

[volkard]

Arcoth schrieb:

unsigned viable = std::count_if( std::begin(knight_jumps), std::end(knight_jumps),
                                 [=, &info] ( int j ) {  return mArray[info.pos + i + j] == 0 && i != -j;  } );

Ja, einer der miesesten Zeilen. Habe mir auch überlegt es zu einer Schleife umzuschreiben, aber dann hatte ich IIRC gleich Vier Zeilen, also wieder zurückgeändert.

Hätte ein Schimpanse die 4 Zeilen auf Anhieb verstanden?

Ich hätte die innere Schleife von

if(board.isMoveValid(m)) {
                for(auto offset:offsets) {
                    Move m2(m+offset);
                    if(board.isMoveValid(m2))
                        ++m.weight;
                }
                moves.push_back(m);
            }

behandeln müssen.

Wegalgorithmieren? Nee, ist selten gut. Also im Prinzip

if(board.isMoveValid(m)) {
                moves.push_back(m,r=for(auto offset:offsets) {
                    Move m2(m+offset);
                    if(board.isMoveValid(m2))
                        ++r;
                });
            }

und die ähnlichen Schreibweisen verbessern das Problem nicht wirklich.

Lamdas sind in manchen Fällen unendlich geil, aber fast nie.
(wie auch Referenzen)

[hustbaer]

Arcoth schrieb:

@hustbaer: Am geilsten finde ich diesen Ausschnitt ((1) - 1) * 2
Das ist entweder ein schlechter Scherz - oder Ergebnis eines Makros.

Jaaaaa, Makro, das wird der Grund sein.
Trotzdem... bäh!

EDIT: Wobei, ... eigentlich sollte der Parameter von assert() ohne Makro-Expansion angezeigt werden. Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

[volkard]

hustbaer schrieb:

EDIT: Wobei, ... eigentlich sollte der Parameter von assert() ohne Makro-Expansion angezeigt werden. Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

Hab's noch nie anders erlebt. Türlich liefert assert den Quelltext.
Vielleicht ist diese assert-Bedingung vorher von einem Make-Tool erzeugt worden.

[Columbo]

Warum willst Du immer den Code noch komplizierter machen als das Problem ist?

Ich möchte den Code so knapp wie möglich halten, und ihn außerdem nie wieder anschauen müssen oder auch wollen (bei dem Code ist letzteres ja auch selbstverständlich). Das wars. Kacke Einstellung, brauchst nichts zu sagen. Kommt von selber schon bald weg - schreibe gerade eine Schachengine, die will ich definitiv lesbar halten, da eigne ich mirs an.

//Uih, Breite, Höhe, Zeilen, Spalten, X, Y, das verwirrt mich immer.

Was ist direkter als width , welches für Breite steht? WidthOfDaBoard ?

Hätte ein Schimpanse die 4 Zeilen auf Anhieb verstanden?

Ein Schimpanse hätte die 4 Zeilen wie eine Banane aufgegessen. Im Nachhinein habe ich wenig Ahnung mehr, warum ich nicht die Schleife gewählt habe...

unsigned viable = 0;
for( auto j : knight_jumps )
    if( mArray[info.pos + i + j] == 0 && i != -j )
        ++viable;

Lamdas sind in manchen Fällen unendlich geil, aber fast nie.

Hihi, deine Sprüchlein werden nur besser und besser. Bist du eine Frucht, die noch reift?

Ist natürlich nicht standardisiert, aber ich sag' mal es wäre verdammt schlau.

Da stimm' ich dir mal zu. Und nein. Der Standard legt nicht klar fest was hier passiert. C11 sagt "including the text of the argument", was aber soviel wie Stringize heißen wird.

Jetzt gibt es aber ein Problem: Forwardest du den Parameter an ein anderes Makro tritt folgendes in Kraft:

A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded. Before being substituted, each argument’s preprocessing tokens are completely macro replaced as if they formed the rest of the preprocessing file; no other preprocessing tokens are available.

Das heißt, falls assert so definiert ist

#define assert(...) ((void)__call_my_func(#__VA_ARGS__))

Dann werden tatsächlich die Makros im Text beibehalten. Anders ist es hier

#define assert(...) ((void)__call_my_func(__STRING(__VA_ARGS__)))

Hier wird __VA_ARGS__ noch gescannt bevor es durchgereicht wird. Und das macht den Unterschied aus. Jetzt schaun wir mal in die Definition von cassert:

# define assert(expr)							\
  ((expr)								\
   ? __ASSERT_VOID_CAST (0)						\
   : __assert_fail (__STRING(expr), __FILE__, __LINE__, __ASSERT_FUNCTION))

Und in Zeile 89 von cdefs.h :

#define __STRING(x)	#x

Reicht schon. Makros werden aufgelöst. Menno. Und ich kann den Fehler leider auch nicht reproduzieren.

Türlich liefert assert den Quelltext.

Ja, genau... und die Makros darin sind aufgelöst. Also war es ein Makro, höchstwahrscheinlich kein Make-Tool, so einfach ist das.

Ich hatte Dir angeboten, hatte darum gebettelt, daß wir KarateKid oder 256KammernDerShaoLin oder so zusammen spielen. Du erinnerst Dich.

Ich habe angenommen, Sensei! Ich darf dich daran erinnern dass du 'keine Zeit für mich hattest', privater Schnickschnack und dergleichen.

[volkard]

Arcoth schrieb:

volkard schrieb:

Ich hatte Dir angeboten, hatte darum gebettelt, daß wir KarateKid oder 256KammernDerShaoLin oder so zusammen spielen. Du erinnerst Dich.

Ich habe angenommen, Sensei! Ich darf dich daran erinnern dass du 'keine Zeit für mich hattest'.

Jup, nachdem Du abgelehnt hattest, meine Hausprobleme zu erledigen. Meinen Zauberwürfelzugfolgenfinder, …, waren noch einige. Holla(!), an denen arbeitest Du ja selber jetzt gerade.

Da hätte ich soo viel angemeckert und gelehrt. Mit Selbstaufgabe.

Wischi wischi Auto putzi… Wie im Film.

[Columbo]

Jup, nachdem Du abgelehnt hattest, meine Hausprobleme zu erledigen

Hab' und hätte ich nie getan. Ich kann mich im Übrigen überhaupt nicht daran erinnern deine Hausproblemchen vorgeschlagen bekommen zu haben.

Zauberwürfelzugfolgenfinder

Ist das ein Hausproblemchen? Verdammt, das trifft genau ins Schwarze - man muss alles definieren, sowas wie Cube , Position und so, alles schön aufteilen in kleine Funktionen. Soll ich mich dran machen?

[volkard]

Arcoth schrieb:

Zauberwürfelzugfolgenfinder

Ist das ein Hausproblemchen? Verdammt, das trifft genau ins Schwarze - man muss alles definieren, sowas wie Cube , Position und so, alles schön aufteilen in kleine Funktionen. Soll ich mich dran machen?

Falls Du so einen mal anfängst, dann schau dir zuerst an, wie es Cube Explorer http://kociemba.org/cube.htm macht und mach es anders. Keine Klasse für Cubies. Die schränkt den Fragesteller zu stark ein.