Nxc: Infinite-Monkey-Theorem

Modelle zum Nachbauen oder wo gibt es etwas interessantes oder Projekte?

Moderator: Moderatoren

Benutzeravatar
NXT pro
Super-Enorm-Viel-Schreiber
Super-Enorm-Viel-Schreiber
Beiträge: 930
Registriert: 27. Sep 2010 21:38

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon NXT pro » 12. Jun 2011 10:06

Jetzt dauert es 7 mal länger!
Real coders don't comment their code - it was hard to write, it should be hard to understand!

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 10:17

nach meiner Rechnung (ich habe ja jetzt nur noch ein Wort mit 6 Buchstaben):
27 hoch 6 (mit Leerzeichen, das gönne ich mir) = 387.420.489 Möglichkeiten,
ca. 100 pro Sekunde => 3874205 sec = 45 Tage (??) für alle Möglichkeiten systematisch durchgerechnet
für jede weitere Buchstabenlänge 27 mal länger.
falsch oder richtig?
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

Benutzeravatar
NXT pro
Super-Enorm-Viel-Schreiber
Super-Enorm-Viel-Schreiber
Beiträge: 930
Registriert: 27. Sep 2010 21:38

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon NXT pro » 12. Jun 2011 10:24

Achso, ich habe nicht gesehen dass du den Hamlet auf 6 Buchstaben gekürzt hast.
Real coders don't comment their code - it was hard to write, it should be hard to understand!

Nicholas
Schreibt ab und zu
Schreibt ab und zu
Beiträge: 38
Registriert: 10. Jun 2011 18:35

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon Nicholas » 12. Jun 2011 10:47

also bei mir brauch er für 10000 Variationen 45 sek = 222,222222 varaitionen pro sek
ist auch egal wir werden schon sehen notfalls lass ich ihn halt mal 50 tage laufen (ist mein voller ernst) dann schalt ich aber mal ab
Mal was anderes: könnte mal einer nen deutschen Guide für die theoretischeren Befehle (zufall,variablen etc.) verfassen, weil im Moment gibts ja nur den mit anzeige sensoren motoren usw.
Biiiiiiiiiiiiiiiitte ich will irgendwann auchmal was allein machen.


Nicholas
Möge die Macht mit euch sein

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 10:58

das Programm ist sicher doppelt so schnell wenn man komplett auf permanente Zeitstring-Berechnung und permanente Displayausgabe verzichtet.
edit: ca. 450 loops/sec.
neuer Code etwas weiter unten!
[OT]: es gibt den NXC Guide von Daniele Benedettelli und jede Menge deutsche Bücher, bitte suchen, und bitte für solche OT Fragen immer einen eigenen Thread benutzen! [/OT]
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

hergipotter
Schreibt viel
Schreibt viel
Beiträge: 140
Registriert: 12. Jan 2011 19:26

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon hergipotter » 12. Jun 2011 12:57

Habe das gerade mal mit Hilfe eines endlichen Zustandsautomaten realisiert, der Einfachkeit halber aber auf meinem PC und in Java. Dort wurde der String "hamlet" gerade nach 109046067 Durchläufen gefunden, das ganze hat 2 Sekunden gedauert :D

Es ist schon klar, dass das auf dem NXT nicht so schnell läuft aber vielleicht ist es mit nem Zustandsautomaten doch besser als mit dem Schieberegisterzeug?

Der Automat funktioniert im Prinzip so: Bei nem Suchstring mit n Buchstaben hat der Automat n+1 Zustände. Am Anfang befindet man sich im ersten Zustand. Dann wird der erste Zufallsbuchstabe "gewürfelt". Ist der gewürfelte Buchstabe der erste aus meinem Suchstring, so geh ich in Zustand 2 über. Wenn nicht bleib ich in Zustand 1. Dann kommt der nächste Durchlauf. Angenommen ich bin jetzt im zweiten Zustand, da ich im ersten Durchgang den richtigen Buchstaben hatte. Wird dann der zweite Buchstabe aus dem Suchstring gewürfelt begeb ich mich in Zustand 3, wenn nicht muss ich wieder zurück in Zustand 1! Und so geht das ganze weiter bis ich mit Glück irgendwann im Zustand n+1 bin, dann hab ich den Suchstring in der Reihenfolge gefunden und bin fertig.

Hier mal mein Java Code zum vergleichen, muss aber dazu sagen, dass ich alles andere als erfahren in Java bin und die Sprache eigentlich eher nicht mag und das ganze in ner Viertelstunde hingeklatscht hab, könnte also sein, dass das sehr schlecht programmiert ist =)

Code: Alles auswählen

import java.util.Random;
/**
 *
 * @author hergi
 */
public class Main {

    Random randomGenerator = new Random();

    // Zufalsszahl zwischen 96 und 122 generieren
    int getRandomInt()
    {
        return randomGenerator.nextInt(27)+96;
    }


    public static void main(String[] args) {

        Main mainInstance = new Main();
        long count = 0;
        int zustand = 0;

   
        while (true)
        {
            char affe = (char)mainInstance.getRandomInt();
            if (affe == 96) affe = 32;
            count++;

            switch (zustand)
            {
                case 0: if (affe == 'h') zustand = 1;
                        break;
                case 1: if (affe == 'a') zustand = 2;
                        else zustand = 0;
                        break;
                case 2: if (affe == 'm') zustand = 3;
                        else zustand = 0;
                        break;
                case 3: if (affe == 'l') zustand = 4;
                        else zustand = 0;
                        break;
                case 4: if (affe == 'e') zustand = 5;
                        else zustand = 0;
                        break;
                case 5: if (affe == 't') zustand = 6;
                        else zustand = 0;
                        break;
            }

            if (zustand == 6) break;
        }

        System.out.println("gefunden!!");
        System.out.println(count);
    }

}



Beim zweiten Mal warens übrigens 299484754 Durchgänge und 6 Sekunden, danach 355586429 und 8 Sekunden...

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 13:23

das ist aber nicht das, was der Affe macht, denn der tippt ja Buchstabe für Buchstabe, einen nach dem anderen, und das als unabhängige Ereignisse, also unabhängig davon, ob er bereits einen Buchstaben richtig gemacht hat oder nicht.
Was du gemacht hast, erinnert grob an meinen 2. Programmvorschlag ganz oben im Thread ("ein bisschen gemogelt"). Da war er schon nach wenigen Sekunden fertig...
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

hergipotter
Schreibt viel
Schreibt viel
Beiträge: 140
Registriert: 12. Jan 2011 19:26

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon hergipotter » 12. Jun 2011 13:30

nene, der Affe tippt bei mir auch einfach Buchstabe für Buchstabe. Der Automat überwacht quasi nur was der Affe tippt.

Code: Alles auswählen

char affe = (char)mainInstance.getRandomInt();

Das ist der Code für den Zufallsbuchstaben, der wird in jedem Durchgang der while Schleife aufgerufen.

tippt der affe z.B. xyzhaml dann wäre der automat in zustand 5, weil haml bis jetz richtig ist. Kommt danach aber kein "e", dann rutscht man zurück in Zustand 1 und muss von vorne anfangen. Da is also nix gemogelt.


Was ganz witzig ist: Wenn ich den Suchstring auf 5 Zeichen verkürze, dauert es fast immer weniger als ne Sekunde. Bei 6 Zeichen warens ja immer so 2 bis 10 Sekunden. Wenn ich jedoch 7 Zeichen nehm dauerts schon mehrere Minuten! Will garnicht wissen wie langs bei "sein oder nicht sein" dauern würde....

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 13:40

verstehe nicht, was du genau machst.

nehmen wir an, der Affe tippte bisher eine Reihe
abcdef
ist das Ergebnis=hamlet?
nein. Also neuer Buchstabe hinten dran, erster ist unwichtig und fällt raus.

der Affe tippt jetzt "h"
bcdefh
ist das Ergebnis=hamlet?
nein. Also neuer Buchstabe hinten dran, erster ist unwichtig und fällt raus.

der Affe tippt jetzt "a"
cdefha
ist das Ergebnis=hamlet?
nein. Also neuer Buchstabe hinten dran, erster ist unwichtig und fällt raus.
...
...
der Affe tippt dann "e"
fhamle
ist das Ergebnis=hamlet?
nein. Also neuer Buchstabe hinten dran, erster ist unwichtig und fällt raus.

Jetzt wird der nächste Buchstabe randomisiert.
ist er zufällig "t", sind wir fertig,
wenn nicht, geht es weiter.

was anderes darf dein Programm nicht machen, sonst wird der tippende Affe nicht richtig simuliert.
Vllt schreibst du es mal auf ähnliche Weise hin?
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 15:14

ich glaube, ich habe dein Programm verstanden:
du schreibst nicht auf, welche Buchstaben getippt wurden, sondern merkst dir nur, ob eine gewisse Reihenfolge inzw erreicht wurde.
Damit ersparst du es dir, die getippten Buchstaben in einen string schreiben zu müssen.

nach einer beliebigen Reihe, z.B.
abcdef
Zustand=0, Prüfung auf string[0]

der Affe tippt jetzt zufällig "h"
Zustand=1, ab jetzt Prüfung auf string[1] (wenn nicht, bleibt in Zustand=0)

der Affe tippt jetzt zufällig "a" (wenn nicht, wieder Zustand=0)
Zustand=2 , ab jetzt Prüfung auf string[2]
...
...
der Affe tippt dann zufällig "e" (wenn nicht, wieder Zustand=0)
Zustand=5, ab jetzt Prüfung auf string[5]

Jetzt wird also wieder randomisiert.
ist er zufällig "t", Zustand=6 => fertig,
wenn nicht, wieder Zustand=0


Das muss ich jetzt mal in NXC umsetzen und gegeneinander austesten.
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 15:54

habe deine Idee in NXC programmiert, und siehe da: es ist ziemlich genau doppelt so schnell wie das vorherige mit dem Schieberegister:
1000 loops pro Sekunde!
neueste Versionen:

Code: Alles auswählen

// Hamlet's Monkeys version Zustandsautomat 3.5

#define printf1( _x, _y, _format1, _value1) { \
  string sval1 = FormatNum(_format1, _value1); \
  TextOut(_x, _y, sval1); \
}


#define clock()  (CurrentTick()-FirstTick())


//------------------------------------------

unsigned long count, level, maxZ, statZ;
string hamlet="hamlet",   // Kurzform
       monkey="      ",
       leer  ="      ";
int len;
char i=0;
byte c;


//------------------------------------------

string gettimeofday(unsigned long lTime) {
  int s1000, sec, min, hour, day;
  string sTime;

  s1000=lTime%1000;
  lTime/=1000;
  sec=lTime%60;
  lTime/=60;
  min=lTime%60;
  lTime/=60;
  hour=lTime%24;
  lTime/=24;

  sTime=StrCat(FormatNum("%d",lTime),"d ",FormatNum("%02d",hour),":",FormatNum("%02d",min),"'",FormatNum("%02d",sec),"\"", FormatNum("%03d",s1000));
  return(sTime);
}


//------------------------------------------

void showWhat(){
  float V;
  TextOut( 0,32, Flatten(c));    TextOut(16,32, ">"+monkey);
  printf1( 0,24,"Lmax%3d",maxZ); printf1(56,24,"H()%4d",statZ);

  printf1(0,16,"count=%d", count);
  TextOut(0, 8, gettimeofday(clock()) );
  V=BatteryLevel()/1000.0;
  printf1(0, 0,"Volt=%6.3f",V);
}

//------------------------------------------

task main(){
  len=StrLen(hamlet);
  TextOut(0,56, "der Affe tippt...");
  TextOut(0,48, "show BtnCtr/Right");
  showWhat();
  level=0;

  while(1) {

    c=(rand()%27)+96;
    if (c==96) c=32;

    if (c==hamlet[level])
    {
      monkey[level]=hamlet[level];
      level+=1;
      if (level>maxZ)
      {
        maxZ=level;
        statZ=1;
      }
      else
      if (level==maxZ) statZ+=1;
    }
    else
    {
      if (level>0)
      {
        level=0;
        monkey=leer;
      }
    }
    count+=1;

    while (ButtonPressed(BTNCENTER, false)) showWhat();
    if (ButtonPressed(BTNRIGHT,  false))  { showWhat(); Wait(50);}

    if (count%2000==0)  showWhat();
    if (level>3) {PlayTone(200*level,100);}

    if (monkey==hamlet)
    {
      PlaySound(SOUND_FAST_UP);
      ClearScreen();
      TextOut(0,56, "Affe schrieb:");
      showWhat();

      while(1);
    }
  }
}



hier nochmal die vorherige (ältere, langsamere) Schieberegister-Version zum Gegeneinanderlaufenlassen:

Code: Alles auswählen

// Hamlet's Monkeys version Schiebestring

#define printf1( _x, _y, _format1, _value1) { \
  string sval1 = FormatNum(_format1, _value1); \
  TextOut(_x, _y, sval1); \
}


#define clock()  (CurrentTick()-FirstTick())

string hamlet="hamlet",   // Kurzform
       monkey="      ";
int len;
char i=0;
byte c;
unsigned long count;

//------------------------------------------

string gettimeofday(unsigned long lTime) {
  int s100, sec, min, hour, day;
  string sTime;
 
  s100=lTime%1000;
  lTime/=1000;
  sec=lTime%60;
  lTime/=60;
  min=lTime%60;
  lTime/=60;
  hour=lTime%24;
  lTime/=24;

  sTime=StrCat(FormatNum("%d",lTime),"d ",FormatNum("%02d",hour),":",FormatNum("%02d",min),"'",FormatNum("%02d",sec),".",FormatNum("%03d",s100));
  return(sTime);
}

//------------------------------------------

void showWhat(){
  float V;
  TextOut(0,32, monkey);

  printf1(0,16,"count=%d", count);
  TextOut(0, 8, gettimeofday(clock()) );
  printf1(0, 0,"Volt =%5.3f", V=BatteryLevel()/1000.0);
}

//------------------------------------------

task main(){
  len=StrLen(hamlet);
  TextOut(0,56, "Affe tippt...");
  TextOut(0,48, "show: BtnCenter");
  showWhat();
 
  while(1) {
    for (i=1; i<len; ++i) {    // nach vorn schieben
      monkey[i-1]=monkey[i];
    }
    c=(rand()%27)+96;
    if (c==96) c=32;
    monkey[len-1]=c;            // hinten einfügen
    count+=1;


    // Wait(500); showWhat();   // for testing

    while (ButtonPressed(BTNCENTER, false)) showWhat();
    if (ButtonPressed(BTNRIGHT,  false))  { showWhat(); Wait(200);}
   
    if (count%2000==0) showWhat();

    if (monkey==hamlet)
    {
      PlaySound(SOUND_FAST_UP);
      ClearScreen();
      TextOut(0,56, "Affe schrieb:");
      showWhat();

      while(1);
    }
  }
}
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

Nicholas
Schreibt ab und zu
Schreibt ab und zu
Beiträge: 38
Registriert: 10. Jun 2011 18:35

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon Nicholas » 12. Jun 2011 16:47

ja nach 30 min hab ich schon maxzustand=4 mathematisch gesehen max=5 bei ca 3 h 15 min
hamlet bei 3,5 d
:prima: dass du das powermeter eingebaut hast. aber ab wann soll er an die steckdose ?

Nicholas
Möge die Macht mit euch sein

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 16:55

kA, vllt 6,2V
übrigens jetzt piepst er verschieden hoch ab level 4
:)

ps
es gibt kein "mathematisch gesehen ", sondern nur ein "statistisch gesehen", das statistische Ergebnis wird auf dich in keinster Weise zutreffen!
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E

Benutzeravatar
elomatreb
Schreibt viel
Schreibt viel
Beiträge: 171
Registriert: 16. Nov 2010 16:53

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon elomatreb » 12. Jun 2011 17:50

Ich würde ihn die ganze Zeit am Netz lassen,wenn ich könnte,habe leider nur "normale"Akkus :(

Ist aber sehr interessant dein Programm und deine Idee :respekt:

elomatreb.
http://www.elomatreb.jimdo.com "Hochspannende" Elektronik,Elektronenröhren uvm.
______________________________________
A Computer is like a Submarine - If you open Windows,you get problems.
;)

Benutzeravatar
HaWe
Administrator
Administrator
Beiträge: 5257
Registriert: 11. Jan 2006 21:01
Wohnort: ein kleiner Planet in der Nähe von Beteigeuze

Re: Nxc: Infinite-Monkey-Theorem

Beitragvon HaWe » 12. Jun 2011 17:57

...und hergipottis Idee :)
Gruß,
HaWe
±·≠≈²³αβγδε∂ζλμνπξφωΔΦ≡ΠΣΨΩ∫√∀∃∈∉∧∨¬⊂⊄∩∪∅∞®
NXT NXC SCHACHROBOTER: https://www.youtube.com/watch?v=Cv-yzuebC7E


Zurück zu „Projekte, Showcase, Bauanleitungen“

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 15 Gäste

Lego Mindstorms EV3, NXT und RCX Forum : Haftungsauschluss