3. Contest #1: Fibonacci Zahlen

Contest #1: Fibonacci Zahlen

  • B
     

    #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

    0
  • C
    Mod

    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 );
}
    0
  • 3

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

    0
  • V
     

    #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.

    0
  • Mod

    Bitte ein Bit schrieb:

    Oder wir sagen derjenige, der die wenigsten Zeichen Quelltext benötigt, gewinnt.

    314159265358979 schrieb:

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

    Eigentlich fand ich die neue Aufgabe langweilig und hätte nicht mitgemacht, aber das klingt interessant.

    Da gerade immer noch Lösungen zum Ursprungsbeitrag eingehen, solltest du dort vielleicht mal editieren (Ok, ich könnte das auch für dich machen, aber ich fände es nicht gut, wenn andere Leute meine Beiträge editieren).

    0
  • ?

    Erster Versuch fuer kurzen Code:

    Zeile 1: 16 Zeichen + 1 Newline
    Zeile 2: 63 Zeichen

    Macht 80 Byte Code. Das sind ~2/3 von der allerersten Lösung von SeppJ.

    Also noch viel Luft für Verkürzungen.

    Link:
    http://codepad.org/yy2fZHrB

    0
  • Mod

    Aber die neue Aufgabe ist, alle Fib-Zahlen zwischen zwei benutzergegebenen Zahlen auszugeben

    0
  • C
    Mod

    nicht besonders kurz, dafür einfach:

    #include<iostream>
#include<math.h>
int main(){auto t=[](int x){return[](int x){return x*x;}(sqrt(x))==x;};int a,b;std::cin>>a>>b;for(;a<=b;++a)if(t(5*a*a+4)||t(5*a*a-4))std::cout<<a<<' ';}

    193 Zeichen

    0
  • ?

    Ich würde eine Regel einführen, dass Whitespaces und Newlines nicht gezählt werden.

    0
  • Mod

    math.h ist länger als cmath 😉 . Auch wenn es nicht Standard ist, so kann man doch ziemlich verlässlich annehmen, dass ein cmath die sqrt auch im globalen Namensbereich auslädt.

    Um solche Konflikte zu vermeiden, sollte man eventuell noch einen oder zwei bestimmten Compiler definieren. Wie wäre es, wenn das Programm entweder auf einem g++ 4.4 oder auf einem MSVC(was immer gerade aktuell ist) compilieren muss?

    0
  • C
    Mod

    SeppJ schrieb:

    math.h ist länger als cmath 😉

    Dafür spar ich mir ein std::

    0
  • Mod

    camper schrieb:

    SeppJ schrieb:

    math.h ist länger als cmath 😉

    Dafür spar ich mir ein std::

    Siehe Rest meines Beitrags. Auch wenn es nicht mehr im Standard liegt, so ist da doch noch Sparpotential.

    0
  • C
    Mod 

    #include<iostream>
int f(int x,int y=0){return y*y==x||y*y<x&&f(x,y+1);}int main(){int a,b;std::cin>>a>>b;for(;a<=b;++a)if(f(5*a*a+4)||f(5*a*a-4))std::cout<<a<<' ';}

    166 Zeichen.
    Mups Code um einen Bereichscheck erweitert dürfte immer noch kürzer sein. Vielleicht hat ja jemand eine Idee, wie nman den square-Test verkürzen könnte.

    0
  • ?

    @camper
    I lol'd 😃

    @Topic
    Gute Idee. Blöde Aufgabe.

    0
  • ?

    Meine angepasste Lösung:

    #include<iostream>
int a,b=1,x,y;int main(){std::cin>>x>>y;for(;a<y;b+=a,a=b-a){if(a>x)std::cout<<a<<" ";}}

    18+1+88 Zeichen == 107 Zeichen

    Allerdings werden hier wirklich nur die Zahlen *zwischen* den Grenzen (exklusive der Grenzen) ausgegeben. Wenn man die Zahlen inklusive Grenzen ausgeben möchte, werden es noch zwei Zeichen mehr.

    0
  • K

    Ich habe auch mal etwas runtergetippt, ohne bei den anderen vorher zu spicken. Es kann etwas mehr als gefordert war...

    0
  • ?

    http://upload.wikimedia.org/math/1/6/e/16ea0dee516003a472c75c4e0b8b4154.png

    0
  • Mod

    @Mups: Du kannst dir noch zwei Klammern sparen.

    Und coole Nullinitialisierung 👍 😋

    Ich hatte gerade einen ganz ähnlichen Ansatz gebastelt, dank expliziter Initialisierung aber länger. Hat sich nun wohl erledigt, kürzer als deines (minus die Klammern), bekomme ich es vorerst nicht mehr 😞

    0
  • V

    SeppJ schrieb:

    Aber die neue Aufgabe ist, alle Fib-Zahlen zwischen zwei benutzergegebenen Zahlen auszugeben

    Ich habe in der Tat angefangen damit. Bin jetzt bei 122 Zeilen und das Prog schweigt sich einfach aus und zeigt mal gar nichts an. Wiedermal sowas, wo man den Debugger anmachen möchte. Aber nein, ohne ist es viel spannender und schärft den Blick. 🙂

    0
  • S

    Ich schlage einen neuen Ansatz vor: Die ausdrucksstärkste Implementierung.

    Vorschläge?

    MfG SideWinder

    0
Anmelden zum Antworten