Contest #1: Fibonacci Zahlen

314159265358979

Da hier im Forum (meiner Meinung nach) etwas Abwechslung fehlt, möchte ich gerne regelmäßig eine Art "Contest" machen.

Jeder soll in einem gewissen Zeitrahmen ein Programm zur Lösung einer Aufgabe schreiben. Danach wird von den Usern abgestimmt, welches den Contest gewinnt. Es soll das eleganteste Programm bewertet werden, Performance ist nebensächlich.
Die Abstimmung findet nach der Deadline statt, ihr dürft nicht für euer eigenes Programm stimmen. (wäre ja langweilig )

Ich könnte mir auch eine Art Rangliste vorstellen, die oben bei den Threads angepinnt wird. Dazu brauche ich aber regelmäßig neue Beispiele von euch, sowie die Hilfe eines Moderators

Hier ist die (einfache) erste Aufgabe:
Aufgabe #1: Gib die ersten 20 Fibonacci Zahlen auf der Standard-Ausgabe aus.
Deadline: Heute 21:00

Für diejenigen, die mit Fibonacci Zahlen nichts anfangen:
- Die ersten beiden Zahlen sind 0 und 1.
- Man erhält die nächste, indem man die beiden Vorgänger addiert.
Siehe auch: http://en.wikipedia.org/wiki/Fibonacci_number
**
Edit: Aufgabe während des Wettbewerbs geändert.**
- Der Benutzer gibt 2 beliebig große Zahlen ein. Diese Zahlen können _beliebig_ groß sein, also auch größer, als in einen unsigned long long passen.
- Diese beiden Zahlen stellen Schranken dar. Alle Fibonacci Zahlen zwischen diesen beiden sollen ausgegeben werden.
- Die Benutzung von Bignum-Libraries ist nicht gestattet.

Ihr dürft alle Mittel verwenden, die euch der Standard und Boost zur Verfügung stellen. Andere Libraries sind verboten.
Wichtig: Eure Programme müssen Standard-konform sein. Ein Programm, dass sich auf eine bestimmte Implementierung stützt, wird als ungültig gewertet. (Hier bitte ich euch auch, darauf zu achten, was andere schreiben. Ich sehe nicht alle Fälle von undefiniertem Verhalten. Bei Verdacht wird die Stelle aus dem Standard zitiert.)
C++11 ist erlaubt, das Programm muss mit GCC 4.6 kompilierbar sein.

Fröhliches Coden!

Codes und Bewertung:

Terminal schrieb:

091-141-078-232:desktop ***$ charcounter volkard
The file volkard contains 2339 non-space characters.
091-141-078-232:desktop ***$ charcounter wxSkip
The file wxSkip contains 2719 non-space characters.

Damit steht der Sieger wohl fest - volkard.

Das charcounter Tool ist ein kleines Programm von mir, das Zeichen wie folgt zählt:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>

int main(int argc, char** argv)
{
	if(argc != 2)
	{
		std::cout << "You must pass a file to count its characters." << std::endl;
		return 0;
	}

	std::ifstream is(argv[1]);

	auto i = std::count_if(std::istreambuf_iterator<char>(is), std::istreambuf_iterator<char>(), [](char c){ return !std::isspace(c); });
	std::cout << "The file " << argv[1] << " contains " << i << " non-space characters." << std::endl;

	return 0;
}

Ich werde es in Zukunft für weitere Wettbewerbe dieser Art einsetzen
Kommentare wurden selbstverständlich entfernt.

Was sind die Kriterien zur Auswahl des "Besten/Tollsten/Schönsten" Codes? Wir hatten mal ähnliche Projekte laufen, siehe hier: http://www.c-plusplus.net/forum/186387 bzw eine gescheitertes http://www.c-plusplus.net/forum/254984

Es gab sowas mal früher im großen Stil von Jester. M*blabla oder so hieß das ...

Lass mich raten, du willst uns einfach nur zeigen, wie toll du doch TMP kannst?

Edit:

pi schrieb:

eleganteste

Was ist elegant?

SeppJ

Und wonach richtet sich die Bewertung? Ich spekuliere mal auf eine Verbindung von Geschwindigkeitm Codegröße und Objectcodegröße und liefere diesen Beitrag:

edit: Spoiler auf andere Seite ausgelagert:
http://codepad.org/ChjGtRoL

edit2: Und ich gebe noch zu bedenken, dass ich das Programm in unter 5 Minuten entwickelt habe. Geringer Entwicklungsaufwand sollten auch höher benotet werden.

Ach daher hast du gestern gefragt wie man nochmal adjacent_difference zum Fibonacci-Berechnen nutzen kann.

314159265358979

jokester_ schrieb:

Ach daher hast du gestern gefragt wie man nochmal adjacent_difference zum Fibonacci-Berechnen nutzen kann.

Nein, die Idee ist mir gerade unter der Dusche gekommen.

Skym0sh0

wie wärs mit etwa solchen regeln wie im spieleprogrammierer.de forum?!

Werner Salomon

314159265358979 schrieb:

Hier ist die (einfache) erste Aufgabe:
Aufgabe #1: Gib die ersten 20 Fibonacci Zahlen auf der Standard-Ausgabe aus.

das ist doch zu einfach - oder?

#include <iostream>
#include <ostream>

int main()
{
    using namespace std;
    cout << "0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 620 987 1597 2584 4181" << endl;
    return 0;
}

.. ich kann mir nicht vorstellen, dass hier eine Lösung kommt, die ich vorher noch nicht gesehen habe. Das Problem ist einfach zu bekannt. Denk' Dir doch mal was eigenes aus

Gruß
Werner

314159265358979

Ich hatte eigentlich gehofft, dass hier Lösungen kommen, in denen die Zahlen nicht im Programm stehen. Vielleicht sind die Regeln auch zu wenig durchdacht.
Immer her mit den Vorschlägen (und auch mit Vorschlägen für eine neue Aufgabe, wenn euch Fibonacci Zahlen langweilen )

bmario

#include <iostream>

template <unsigned n>
class fibo {
public:
    static const unsigned long Value=fibo<n-1>::Value + fibo<n-2>::Value;
};

template <>
class fibo<0> {
public:
    static const unsigned long Value=0;
};

template <>
class fibo<1> {
public:
    static const unsigned long Value=1;
};

template <unsigned maxn, unsigned i, template<unsigned> class calc>
class mpl_for_impl {
public:
    void operator()(){
        std::cout << calc<i>::Value << ' ';
        mpl_for_impl<maxn, i+1, calc>()();
    }
};

template <unsigned maxn, template<unsigned> class calc>
class mpl_for_impl<maxn,maxn, calc>
{
public:
    void operator()(){
        std::cout << std::endl;
    }
};

template <unsigned maxn, template<unsigned> class calc>
class mpl_for {
public:
    void operator()(){
        mpl_for_impl<maxn, 0, calc>()();
    }
};

int main (int argc, const char * argv[])
{

    mpl_for<20, fibo>()();

    return 0;
}

Wobei ich Werner Salomons Lösung am besten finde

SeppJ

bmario schrieb:

Wobei ich Werner Salomons Lösung am besten finde

Och . Meine ist schneller und kürzer. Zu C-ig?

bmario

Ich nehm' es zurück, SeppJ's ist schöner, Werner hat einen sinnlosen Include

SeppJ

314159265358979 schrieb:

Ich hatte eigentlich gehofft, dass hier Lösungen kommen, in denen die Zahlen nicht im Programm stehen. Vielleicht sind die Regeln auch zu wenig durchdacht.

Das war doch klar, du musst schon eine Initiative liefern, warum die Leute das anders machen sollten. 20 zur Compilezeit bekannte Zahlen zu berechnen ist viel zu einfach. Eigentlich ist alles was zur Compilezeit geht trivial, denn dann kann es auch der Programmierer vorher selbst ausrechnen und direkt in's Programm schreiben. Du hättest wenigstens sagen können, dass zwei Zahlen eingegeben werden und diese als Start gelten sollen, anstatt fest 0 und 1 zu nehmen.
Und du musst Bewertungskriterien vorher(!) festlegen. Ein Programm um aus zwei vorgegebenen Zahlen eine Fib-Folge zu berechnen scheint einfach, aber ist es gut? Ist es schnell? Kommt es mit Überläufen zurecht? Negative Startwerte? Ist der Code kurz oder umständlich?

Kóyaánasqatsi

314159265358979 schrieb:

Aufgabe #1: Gib die ersten 20 Fibonacci Zahlen auf der Standard-Ausgabe aus.
Deadline: Heute 21:00

Finde ich ja eine coole Idee mit dem Contest, aber sollte das mit der Standard-Ausgabe nen Witz sein?

Bashar

bmario schrieb:

Ich nehm' es zurück, SeppJ's ist schöner, Werner hat einen sinnlosen Include

Du meinst <ostream>? Ob der sinnlos ist, kommt drauf an, ob man sich an den Standard oder an die Realität hält.

314159265358979

SeppJ schrieb:

Das war doch klar, du musst schon eine Initiative liefern, warum die Leute das anders machen sollten. 20 zur Compilezeit bekannte Zahlen zu berechnen ist viel zu einfach. Eigentlich ist alles was zur Compilezeit geht trivial, denn dann kann es auch der Programmierer vorher selbst ausrechnen und direkt in's Programm schreiben. Du hättest wenigstens sagen können, dass zwei Zahlen eingegeben werden und diese als Start gelten sollen, anstatt fest 0 und 1 zu nehmen.

Was eine Lösung über Templates, wie die von bmario, verhindert hätte.

SeppJ schrieb:

Und du musst Bewertungskriterien vorher(!) festlegen. Ein Programm um aus zwei vorgegebenen Zahlen eine Fib-Folge zu berechnen scheint einfach, aber ist es gut? Ist es schnell? Kommt es mit Überläufen zurecht? Negative Startwerte? Ist der Code kurz oder umständlich?

Eleganz definiert jeder anders für sich. Abstimmungen sind per Definition subjektiv, vielleicht hätte ich aber etwas eingrenzen können.

Kóyaánasqatsi schrieb:

Finde ich ja eine coole Idee mit dem Contest, aber sollte das mit der Standard-Ausgabe nen Witz sein?

Nein. Siehe bmarios Lösung.

Ihr könntet auch einfach Vorschäge machen, wie man es euch Recht machen kann, anstatt zu sagen, dass alles scheiße ist.

SeppJ

Was eine Lösung über Templates, wie die von bmario, verhindert hätte.

Na und? Templatemetaprogrammierung nur um ihrer selbst willen ist nun einmal realitätsfern. Man kann ja schicke Sachen damit machen, aber mathematische Konstanten damit zur Compilezeit zu berechnen ist immer nur das Anfängerbeispiel, weil man es besser nachvollziehen kann, als wildes Jonglieren mit Typeninformation. Man kann durchaus Templatemetaprogrammierung auch mit Benutzerinteraktion kombinieren. Ich hatte hier mal so ein Zahlenratespiel, bei dem sämtliche möglichen Pfade die der Benutzer eventuell wählen könnte zur Compilezeit im Voraus berechnet wurden. Der Trick ist eben zu wissen, wann man sie einsetzen sollte und wann nicht.

Und sofern dein Bewertungsmaßstab nicht "möglichst kompliziert" ist, muss die Aufgabe an sich schon ganz schön schwer sein, damit sich echte TMP lohnt.

314159265358979 schrieb:

Ihr könntet auch einfach Vorschäge machen, wie man es euch Recht machen kann, anstatt zu sagen, dass alles scheiße ist.

Oje, du hast so eine unausgegorene 5 Minutenidee unter der Dusche und wenn man sagt was man da dran besser hätte machen können, dann ist man ein böser Basher der nur motzen kann? Ich halte mich lieber mal raus...

314159265358979

Gut, dann wird die Aufgabe wie folgt abgeändert:
- Der User gibt 2 _beliebig_ große natürliche Zahlen ein, wobei die erste kleiner ist als die zweite.
- Ihr sollt alle Fibonacci Zahlen zwischen diesen beiden Zahlen ausgeben. "zwischen" bedeutet exclusive-exclusive. Bignum-Libraries dürfen nicht verwendet werden.
- Deadline ist Montag 18:00

Bitte ein Bit

#include <stdio.h>

int main(int, char**)
{
int f[4]={0,0,1,0},&g=f[2],&h=f[3];
for (;*f<20;(*f)++) h=g+f[1],f[1]=g,g=h,printf("%i ",h);
}

Naja, wie wäre es mit einem Obfuscation Wettbewerb. Oder wir sagen derjenige, der die wenigsten Zeichen Quelltext benötigt, gewinnt.

Edit:
Umstellung des Codes auf minimale Zeichenanzahl. #Bytes: 144

camper

Meine Lösung macht mehr als gefordert (hört nicht nach 20 Zahlen auf), und braucht den meisten Speicher und die längste Zeit zum Compilieren. Ein klarer Gewinner.

#include <cstddef>
#include <cstdio>
#include <utility>
#include <type_traits>
#include <boost/mpl/at.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/has_key.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/vector.hpp>

using boost::mpl::at;
using boost::mpl::if_;
using boost::mpl::if_c;
using boost::mpl::front;
using boost::mpl::has_key;
using boost::mpl::identity;
using boost::mpl::map;
using boost::mpl::pair;
using boost::mpl::pop_front;
using boost::mpl::push_front;
using boost::mpl::vector;

constexpr char source[] =
">++++++++++>+>+["
"    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>["
"        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-"
"            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>"
"    ]<<<"
"]"
"This program doesn't terminate; you will have to kill it."
"Daniel B Cristofani (cristofdathevanetdotcom)"
"http://www.hevanet.com/cristofd/brainfuck/";

template <std::ptrdiff_t N> struct mod_ptr_cmd { template <typename Env> static void run(Env& env) { env.ptr += N; } };
template <unsigned char N> struct mod_data_cmd { template <typename Env> static void run(Env& env) { *env.ptr += N; } };
struct get_cmd                                 { template <typename Env> static void run(Env& env) { *env.ptr = std::getchar(); } };
struct put_cmd                                 { template <typename Env> static void run(Env& env) { std::putchar( *env.ptr ); } };
struct block_begin                             { template <typename Env> static void run(Env&) {} };
struct block_end                               { template <typename Env> static void run(Env&) {} };

typedef map<
    pair<std::integral_constant<char, '>'>, mod_ptr_cmd<1>>,
    pair<std::integral_constant<char, '<'>, mod_ptr_cmd<-1>>,
    pair<std::integral_constant<char, '+'>, mod_data_cmd<1>>,
    pair<std::integral_constant<char, '-'>, mod_data_cmd<-1>>,
    pair<std::integral_constant<char, ','>, get_cmd>,
    pair<std::integral_constant<char, '.'>, put_cmd>,
    pair<std::integral_constant<char, '['>, block_begin>,
    pair<std::integral_constant<char, ']'>, block_end>> commands;

template <typename Command, char... Tail> struct fuse;

template <typename Command, typename Next, char... Tail> struct compile
    : compile<Next, void, Tail...>
{
    template <typename Env> static void run(Env& env)
    {
        Command::run( env );
        compile<Next, void, Tail...>::run( env );
    }
};

template <typename Command, char... Tail> struct compile<Command, void, Tail...>
    : fuse<Command, Tail...> {};

template <char... Tail> struct compile<block_begin, void, Tail...>
{
    typedef compile<void, void, Tail...> base;
    typedef typename front<typename base::tails>::type this_tail;
    typedef typename pop_front<typename base::tails>::type tails;
    template <typename Env> static void run(Env& env)
    {
        while ( *env.ptr != 0 )
        {
            base::run( env );
        }
        this_tail::run( env );
    }
};

template <char... Tail> struct compile<block_end, void, Tail...>
{
    typedef compile<void, void, Tail...> base;
    typedef typename push_front<typename base::tails, base>::type tails;
    template <typename Env> static void run(Env&) {}
};

template <typename T, typename U> struct fuse_command
    : pair<T, U> {};
template <std::ptrdiff_t a, std::ptrdiff_t b> struct fuse_command<mod_ptr_cmd<a>, mod_ptr_cmd<b>>
    : pair<mod_ptr_cmd<a+b>, void> {};
template <unsigned char a, unsigned char b> struct fuse_command<mod_data_cmd<a>, mod_data_cmd<b>>
    : pair<mod_data_cmd<a+b>, void> {};
template <typename U> struct fuse_command<void, U>
    : pair<U, void> {};

template <typename Command, char c, char... Tail> struct fuse<Command, c, Tail...>
    : compile<
        typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::first,
        typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::second,
        Tail...> {};
template <typename Command> struct fuse<Command>
{
    typedef vector<> tails;
    template <typename Env> static void run(Env& env) { Command::run( env ); }
};
template <> struct fuse<void>
{
    typedef vector<> tails;
    template <typename Env> static void run(Env&) {}
};

template <char... src> struct program
{
    template <typename Env> static void run(Env& env) { compile<void, void, src...>::run( env ); }
};

// Ein bisschen Hilfsmagie um den String ins Template zu bekommen
// wird irgendwann überflüssig
template <std::size_t... i> struct indexes
    : identity<indexes<i...>> {};

template <typename T, typename U> struct concat
    : concat<typename T::type, typename U::type> {};
template <std::size_t... i, std::size_t... j> struct concat<indexes<i...>, indexes<j...>>
    : indexes<i..., ( j + sizeof... i )...> {};

template <typename T> struct twice
    : concat<T, T> {};

template <std::size_t N> struct make_indexes
    : concat<twice<make_indexes<(N / 2)>>, if_c<(N % 2 == 1),
indexes<0>, indexes<>>> {};
template <> struct make_indexes<0>
    : indexes<> {};

template <typename = typename make_indexes<sizeof source - 1>::type> struct source_to_program;
template <std::size_t... i> struct source_to_program<indexes<i...>>
    : identity<program<source[ i ]...>> {};

struct Environment
{
    unsigned char data[32768];
    unsigned char* ptr;
};

int main()
{
    Environment env = { {}, env.data };
    source_to_program<>::type p;
    p.run( env );
}

314159265358979

Klingt wie eine interessante Idee. Dann setzen wir das als Bewertungs-Kriterium fest.

volkard

#include <iostream>

int main()
{
    using namespace std;
    cout << "0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 620 987 1597 2584 4181" << '\n';
}

Wie Werner, aber endl halte ich für schlecht. Auch, wenn hier das flushen nicht schadet, so habe ich dennoch sicher kein flushen gemeint. Trotzdem habe ich das newline von den Daten abgetrennt.