Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Ok, dann hier die nächste Aufgabe (hoffe sie ist nicht zu einfach^^):

Aufgabe

Gegeben sind zwei Klassen:


        class StringFinder
        {
            private StringHider stringHider;

            public StringFinder(StringHider s)
            {
              // ....
            }

            public void FindString()
            {
              // Hier seid ihr gefragt! 
            }
        }


        class StringHider
        {
            private string value;
            private int minLength, maxLength;
            public int Tries { get; private set; }

            public StringHider(int minLength, int maxLength)
            {
              // ....
            }

            public void GenerateString()
            {
               // ....
            }
            /// <returns>-2: Die Zeichenfolge stimmt
            ///          -1: Die Zeichenfolge hat die falsche Länge
            ///          0-... Die Zeichenfolge hat die richtige Länge, ist aber noch nicht korrekt.
            ///          Die Nummer gibt die Anzahl der richtig platzierten Zeichen an.
            ///</returns>
            public int Ask(string guess)
            {
               // ....
            }
        }

(Hinweis: Den Code habe ich nicht gepostet, sonst wäre es zu lang geworden - siehe Anhang!)

Der StringHider erstellt eine Zeichenfolge einer Länge zwischen minLength und maxLength, die aus zufällig ausgewählten Zeichen (Großbuchstaben, d. h. alle Zeichen von A bis Z, ohne Umlaute etc.) besteht.

Eure Aufgabe: Ergänzt die FindString() Methode des StringFinders dergestalt, dass diese mit möglichst wenigen Aufrufen der Ask(string guess)-Methode die Zeichenfolge "erraten" kann.

WICHTIG: Ich möchte nicht, dass hier mit irgendwelchen Tricks gearbeitet wird; einziges Hilfsmittel soll die Rückgabe des StringHiders sein, sprich:
  • -2: Die Zeichenfolge stimmt
  • -1: Die Zeichenfolge hat die falsche Länge
  • 0-... Die Zeichenfolge hat die richtige Länge, ist aber noch nicht korrekt. Die Nummer gibt die Anzahl der richtig platzierten Zeichen an.

Zu beachten: JEDE Ausführung der Ask-Methode setzt den Zähler im StringHider hoch, verschlechtert also das Endergebnis. Setzt sie daher mit Bedacht ein ;)

(Zugegeben, das ganze hat etwas von Mastermind ^^)

Zum Testen eurer Methode habe ich eine passende Main-Methode geschrieben, die das ganze für eine festgelegte Anzahl an Versuchen simuliert. Diese wird, in der Form wie unten angegeben, ausschlaggebend für die Bestimmung des Gewinners sein. Wer bei 10.000 Durchläufen (evtl. auch mehr, mal sehen) die kleinste durchschnittliche Anzahl an Versuchen benötigt, gewinnt dieses Programmierspiel.

Hier die Main-Methode in voller Länge:


        public const int SIMULATION_QUANTITY = 10000;

        static void Main(string[] args)
        {
            Console.WriteLine("Starte Simulation");
            // Zur Bestimmung des Gewinners werde ich 3 verschiedene (nicht bekannt gegebene)
            // Wertepaare für die Stringlänge benutzen!
            StringHider s = new StringHider(50, 100);
            StringFinder sf = new StringFinder(s);
            int tries = 0;
            for (int i = 0; i < SIMULATION_QUANTITY; i++)
            {
                if (i%(SIMULATION_QUANTITY/10) == 0)
                    Console.WriteLine(i*100 / SIMULATION_QUANTITY + "%");
                sf.FindString();
                tries += s.Tries;
                if (s.Ask(s.lastGuess) != -2)
                {
                    Console.WriteLine("Fehler: Deine FindString-Methode liefert falsche Ergebnisse!");
                    break;
                }
                s.GenerateString();
            }
            Console.WriteLine("Durchschnitt: {0} Versuche", tries / SIMULATION_QUANTITY);
            Console.ReadLine();
        }

Hinweise zur Lösung:
Bitte NUR die FindString()-Methode als Lösung posten! (evtl. noch die Anzahl der Versuche bei einem Probelauf - aber wenn, dann ehrlich^^)

Ende der Aufgabe

Hinweis:"Leider" bin ich bis nächsten Freitag (29. 07) im Urlaub und kann u. U. den Gewinner nicht schnell genug bekannt geben. Wenn möglich, soll die Aufgabe bis zum genannten Datum laufen, danach gewinnt derjenige, der den besten Algorithmus entwickelt hat; hierzu werde ich alle bis dahin geposteten Lösungen testen.
Wenn der Zeitraum zu lang ist (was ich nicht hoffe), kann ja notfalls ein Moderator einen Gewinner festlegen...


Ansonsten wünsche ich viel Erfolg!
Attachments

Moderationshinweis von herbivore (24.07.2011 - 10:52:54):

Der "Gewinner" einer Aufgabe des Programmierspiels ist - im Gegensatz zu dem von stes beschriebenen - nach den Regeln im allerersten Beitrag derjenige, der die erste Antwort gibt, die die Aufgabe löst. Es spielt keine Rolle, wie gut die Lösung gegenüber anderen (hypothetischen oder realen) Lösungen ist, solange sie im Sinne der Aufgabenstellung korrekt ist.

Ob eine Lösung im Sinne der Aufgabe korrekt ist, entscheidet der Aufgabensteller. Eine knappe Woche Wartezeit ist in Bezug auf die üblichen Reaktionszeiten im Forum zwar lang, aber auch nicht zu lang.

Apropos Länge: Die Aufgaben sollten in ca. 50 Codezeilen gelöst werden können. Die Länge des vorgegebenen Codes sollte ebenfalls überschaubar bleiben. Das nur als Hinweis für künftige Aufgabensteller, weil das bei den letzten Aufgaben nicht immer der Fall war. :-)

private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Wahrscheinlich gilt dies nicht als richtige Lösung aber man kanns ja mal versuchen ^^


 public void FindString()
            {
                // TODO Hier seid ihr gefragt!
                object erg = typeof(StringHider).InvokeMember("value", BindingFlags.GetField | BindingFlags.Instance | BindingFlags.NonPublic, null, stringHider, null);
                string asking = (string)erg;
                int ret = stringHider.Ask(asking);
            }

Grüße Daniel

Moderationshinweis von herbivore (25.07.2011 - 02:25:04):

Der Versuch war unnötig, da schon in der Aufgabe steht:

Zitat
WICHTIG: Ich möchte nicht, dass hier mit irgendwelchen Tricks gearbeitet wird; einziges Hilfsmittel soll die Rückgabe des StringHiders sein, sprich [der Rückgabewert der Ask-Methode]

private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 634

beantworten | zitieren | melden

Ich schaffs in ~1220 Versuchen, wer schafft weniger?

Edit:
Wie man sich nen Ast abbricht und dann liegts an ner Kleinigkeit.. Kopf -> Tisch.
Bin jetzt bei 675 mit einem optimierten naivem Ansatz. Ich denke, wer das überbieten will, muss einen Suchbaumalgo oder etwas in der Richtung verwenden.
Das hat mir aber einiges an Kopfzerbrechen bereitet und habs jetzt erstmal aufgegeben. Also viel Erfolg xD



Edit2:
Da nachgefragt wurde, poste ich jetzt auch mal meine Lösung. Dabei ist zu beachten, dass myUnderTakeR und Daniel B. vor mir ihren Code gepostet haben.
Ich ermittel zunächst die Länge des Strings, und dann, wie oft jedes Zeichen im String vorkommt. Mit den Vorraussetzungen verringert sich der Aufwand beträchtlich.


public void FindString()
{
    #region variables
    string zeichensatz = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string tmp = new String('a', 50);
    int length = 0;
    Dictionary<char, int> zCount = new Dictionary<char, int>();
    char[] tmpa;
    char[] tmpb;
    bool charFound;
    #endregion variables

    #region länge ermitteln
    while (stringHider.Ask(tmp) < 0)
    {
        tmp = tmp + "a";
        stringHider.Ask(tmp);
    }
    length = tmp.Length;
    #endregion länge ermitteln

    #region anzahl jedes zeichens ermitteln
    foreach (char a in zeichensatz)
    {
        zCount.Add(a, stringHider.Ask(new String(a, length)));
    }
    #endregion anzahl jedes zeichens ermitteln

    #region position jedes zeichens ermitteln
    tmpa = tmp.ToCharArray();
    tmpb = tmp.ToCharArray();
    for (int i = 0; i < length; i++)
    {
        charFound = false;
        foreach (char a in zeichensatz)
        {
            if (zCount[a] > 0)
            {
                tmpa[i] = a;
                if (stringHider.Ask(new String(tmpa)) == 1)
                {
                    tmpb[i] = a;
                    zCount[a]--;
                    charFound = true;
                }
                tmpa[i] = 'a';
                if (charFound) break;
            }
        }
    }
    #endregion position jedes zeichens ermitteln

    stringHider.Ask(new String(tmpb));
}
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Alf Ator am .
private Nachricht | Beiträge des Benutzers
Lennart
myCSharp.de - Member



Dabei seit:
Beiträge: 429
Herkunft: Bawü

beantworten | zitieren | melden

919-924 bei 5-6 Durchläufen
private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

Euch ist schon klar, dass ihr zum lösen der Aufgabe euren Code der FindString Methode posten müsst oder? Die Anzahl der Versuche ist, wie Herbivore schon als Hinweis geschrieben hat, kein Kriterium ob eine Aufgabe gelöst ist oder nicht. Geht bei dieser Art Aufgabe auch gar nicht, da das Ganze nur raten und kombinieren der Ergebnisse ist - wenn man Glück hat, reicht auch ein Aufruf :)
Baka wa shinanakya naoranai.

Mein XING Profil.
private Nachricht | Beiträge des Benutzers
Lennart
myCSharp.de - Member



Dabei seit:
Beiträge: 429
Herkunft: Bawü

beantworten | zitieren | melden

Zitat von stes
Wer bei 10.000 Durchläufen (evtl. auch mehr, mal sehen) die kleinste durchschnittliche Anzahl an Versuchen benötigt, gewinnt dieses Programmierspiel.
&
Zitat von stes
Hinweis:"Leider" bin ich bis nächsten Freitag (29. 07) im Urlaub und kann u. U. den Gewinner nicht schnell genug bekannt geben.

Ich gehe einfach mal davon aus das hier keiner irgendne Zahl postet ohne den dazu passenden Code zu haben. Da das Posten vlt nur andere davon abhält selber zu knobeln hab ichs nicht getan.
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Das Ganze ist im Average Case wahrscheinlich überlogarithmisch mit etwa O(n * ln(n)) lösbar. Spontan fallen mir drei Alogrithmen ein, wovon einer der "naive" Brute-Force-Algorithmus ist. Der, den ich implementiert habe, verfängt im Schnitt wie der von Lennart.

Bestimmt gibt es wieder irgendeinen Kniff, den ich übersehe, bei solchen "Knobelaufgaben" übersehe ich diese Kniffe leider dauernd. 8[

Naja, bin mal auf die richtige Lösung gespannt!
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von ProgrammierTroll am .
q.e.d.
private Nachricht | Beiträge des Benutzers

Moderationshinweis von herbivore (25.07.2011 - 20:39:21):

Alles soweit verständlich, aber bitte lasst es nicht weiter ausufern. Die erste Regel des Spiels lautet: "So ein Thread erfordert Disziplin! Bitte nur Aufgaben und Lösungen posten! Keine Kommentare!"

jreusch
myCSharp.de - Member

Avatar #avatar-3346.jpg


Dabei seit:
Beiträge: 303

beantworten | zitieren | melden

Ich hatte gerade ein bisschen langeweile und habe es auch einmal gelöst. Ich hab auch den naiven Ansatz verfolgt und bin gespannt ob jemand einen besseren findet.
Schön geschrieben ists nicht, wenn ich Zeit finde schieb ich noch eine schönere Lösung nach.

Mit der Lösung komm ich im Schnitt auf ganz genau auf 900 Versuche (über 10 Ausführungen gemittelt).

Aufwand:
Der naive Ansatz sollte im Schnitt "StringLänge * MöglicheZeichen / 2" benötigen und liegt damit in O(n).

class StringFinder
{
    private StringHider stringHider;
    private const char StartCharacter = 'A';
    private const char EndCharacter = 'Z';

    public StringFinder(StringHider s)
    {
        stringHider = s;
    }

    public void FindString()
    {
        int lastResult;
        StringBuilder stringBuilder = FitStringBuilder(out lastResult);

        for (int idx = 0; idx < stringBuilder.Length; idx++)
        {
            for (char c = (char)(StartCharacter + 1); c ≤ EndCharacter; c++)
            {
                stringBuilder[idx] = c;
                int result = stringHider.Ask(stringBuilder.ToString());

                if (result == -2)
                {
                    // Zeichenfolge gefunden
                    return;
                }
                if (result > lastResult)
                {
                    // Ergebnis besser => Richtiges Zeichen gefunden
                    lastResult = result;
                    break;
                }
                if (result < lastResult)
                {
                    // Ergebnis schlechter => Richtiges Zeichen wiederherstellen
                    stringBuilder[idx]--;
                    break;
                }

                // Ergebnis gleich => nächstes Zeichen versuchen
                lastResult = result;
            }
        }
    }

    private StringBuilder FitStringBuilder(out int result)
    {
        for (int i = 0; i ≤ int.MaxValue; i++)
        {
            StringBuilder stringBuilder = new StringBuilder();
            for (int a = 0; a < i; a++)
            {
                stringBuilder.Append(StartCharacter);
            }

            result = stringHider.Ask(stringBuilder.ToString());

            if (result != -1)
                return stringBuilder;
        }

        throw new Exception("Konnte die richtige Länge nicht finden");
    }
}

Grüße

[edit]Formatierung, Aufwand...[/edit]
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von jreusch am .
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Hier ist noch meine Lösung, mir ist leider spontan auch nichts besseres als ein bruteforceartiger Algorithmus in den Sinn gekommen...


 public void FindString()
            {
                // TODO Hier seid ihr gefragt!
                StringBuilder guess = new StringBuilder();
                int erg = 0;
                do
                {
                    guess = guess.Append((char)64);
                    erg = stringHider.Ask(guess.ToString());
                } while (erg == -1);
                int len = guess.Length;
                for (int i = 0; i < len; i++)
                {
                    for (int v = 0; v < 26; v++)
                    {
                        guess[i]++;
                        int asked = stringHider.Ask(guess.ToString());
                        if (asked > erg || asked == -2)
                        {
                            erg++;
                            break;
                        }
                    }
                }
           }

Alles in allem auf die FindString Methode begrenzt, falls mir noch ein besserer Ansatz einfällt werde ich diesen Post editieren
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7541
Herkunft: Waidring

beantworten | zitieren | melden

Hallo,

die Lösung wird nach ~580 Versuchen gefunden.


using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace Programmierspiel
{
    public class StringFinder
    {
        private StringHider           _stringHider;
        private StringBuilder         _guess;
        private Dictionary<char, int> _characterCount;
        //---------------------------------------------------------------------
        public string Guess { get { return _guess.ToString(); } }
        //---------------------------------------------------------------------
        public StringFinder(StringHider s)
        {
            _stringHider = s;
        }
        //---------------------------------------------------------------------
        public void FindString()
        {
            int numberOfCorrectAs = this.FindLength();

            if (numberOfCorrectAs == -2) return;

            _characterCount = new Dictionary<char, int>();
            _characterCount['A'] = numberOfCorrectAs;
            this.GetCharacterCount();
            this.Match();
        }
        //---------------------------------------------------------------------
        private int FindLength()
        {
            StringBuilder sb = new StringBuilder();
            int result       = int.MinValue;

            do
            {
                sb.Append("A");
                result = _stringHider.Ask(sb.ToString());
            } while (result == -1 || result == -2);

            _guess = sb;
            return result;
        }
        //---------------------------------------------------------------------
        private void GetCharacterCount()
        {
            // for (char c = 'B'; c ≤ 'Z'; ++c)    ist aber aus der Angabe nicht eindeutig ob [A-Z] od. [A-Z)
            for (char c = 'B'; c < 'Z'; ++c)
            {
                string tmp         = _guess.ToString().Replace('A', c);
                _characterCount[c] = _stringHider.Ask(tmp);
            }

            _characterCount = _characterCount
                .Where(kvp => kvp.Value > 0)
                .ToDictionary(kvp => kvp.Key, kvp => kvp.Value);

            Debug.Assert(_characterCount.Sum(kvp => kvp.Value) == _guess.Length);
        }
        //---------------------------------------------------------------------
        private void Match()
        {
            _guess = _guess.Replace('A', default(char));

            for (int i = 0; i < _guess.Length; ++i)
            {
                List<KeyValuePair<char, int>> orderedCharCount = _characterCount
                    .Where(kvp => kvp.Value > 0)
                    .OrderByDescending(kvp => kvp.Value)
                    .ToList();

                if (orderedCharCount.Count == 1)
                {
                    _guess[i] = orderedCharCount[0].Key;
                    if (_stringHider.Ask(_guess.ToString()) == -2) return;
                }

                foreach (KeyValuePair<char, int> chars in orderedCharCount)
                {
                    _guess[i] = chars.Key;
                    if (_stringHider.Ask(_guess.ToString()) > i)
                    {
                        _guess[i] = chars.Key;
                        _characterCount[chars.Key]--;
                        break;
                    }
                }
            }
        }
    }
}

Kurz zur Erklärung was da passiert:
Zuerst wird - eh klar - die Länge ermittelt.
Danach wird untersucht wie oft jedes einzelne Zeichen vorkommt und somit gibt es eine Häufigkeitsverteilung der Buchstaben. Nun wird jede Position durchgegangen und versucht nach absteigend sortierter Häufigkeit, sprich der häufigste Buchstabe zuerst, einen Treffer zu landen. Wenn einer gefunden wurde ist diese Position erledigt und die Häufigkeitsverteilung für den restlichen String wird aktualisiert (~dynamische Verteilung) und das Suchen wiederholt sich.
Das hat den Vorteil, und spart wertvolle Versuche, dass nicht wahllos probiert wird. ZB wenn in der vorderen Hälfte des gesuchten Strings die zu verteilenden As schon fast verbraucht sind, dann braucht in der hinteren Hälfte - da dort eben A weniger wahrscheinlich ist - nicht mit dem A zu Suchen begonnen werden, sondern es kann ein Buchstabe verwendet werden der dort eher wahrscheinlich ist.

Es ist zwar Brute-Force ähnlich aber nicht ganz auf die brutale Art, sondern es wird mit Hilfe der Verteilung zu einer "Soft-Force" :-)


mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
private Nachricht | Beiträge des Benutzers
ProgrammierTroll
myCSharp.de - Member

Avatar #avatar-3285.jpg


Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

Das ist sehr seltsam. Ich habe auch einen "Algorithmus", der so ähnlich arbeitet wie deiner, kommt auf etwa 710 Versuche. Frag mich gerade, wo mein Fehler liegt.

            public void FindString()
            {
                String guessString = "";
                StringBuilder guessStringBuilder = new StringBuilder(guessString);
                int[,] letterAppearences = new int[(int)'Y' - (int)'A' + 1, 2];
                int testLetter = (int)'A';
                int targetNumberLetter = 1;
                int length = 0;
                int rightChar = 0;

                do
                {
                    guessString += " ";
                    length++;
                }
                while (stringHider.Ask(guessString) == -1);

                guessStringBuilder.Length = length;

                for (int i = 0; i < (int)'Y' - (int)'A'+1; i++)
                {
                    letterAppearences[i, 0] = testLetter;;
              
                    for (int j = 0; j < length; j++)
                    {
                        guessStringBuilder[j] = (char)testLetter;
                    }

                    letterAppearences[i, 1] = stringHider.Ask(guessStringBuilder.ToString());
                    testLetter++;
                }

                guessStringBuilder.Replace('Y', (char)0);

          
                for (int i = 0; i < length; i++)
                {
                    for (int j = 0; j < letterAppearences.GetLength(0); j++)
                    {
                        if (letterAppearences[j, 1] > 0)
                        {
                            if (guessStringBuilder[i] == (char)0)
                            {
                                guessStringBuilder[i] = (char)letterAppearences[j, 0];
                                rightChar = stringHider.Ask(guessStringBuilder.ToString());

                                if (rightChar==-2)
                                {
                                    letterAppearences[j, 1]--;
                                }
                                if (rightChar == targetNumberLetter)
                                {
                                    targetNumberLetter++;
                                    letterAppearences[j, 1]--;
                                }
                                else if(rightChar != -2)
                                {
                                    guessStringBuilder[i] = (char)0;
                                }
                            }
                        }
                    }
                }
            }
q.e.d.

Moderationshinweis von gfoidl (28.07.2011 - 00:30:13):

Dann frag dich bitte selbst wo dein Fehler liegt. Bitte beachte [Hinweis] Wie poste ich richtig? Punkt 4.c
Wenn jeder einen Lösungsvorschlag posten würde der nicht ganz passt und um den Fehler suchen zu lassen dann geht dieser "schöne" Thread komplett aus dem Leim. Bitte beachtet die Regeln und haltet eine gewisse Disziplin ein. Danke.

private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 634

beantworten | zitieren | melden

[Edit: Komplett überarbeitet]
So, ich habe meinen Algorithmus nochmal verbessert. Ich schaffe es jetzt auf durchschnittlich unter 400 Versuche. Diesmal wirklich.

Ich verwende einen Suchbaum der Schritt für Schritt aufgebaut wird. Dabei Teste ich für jeweils die Hälfte des Strings, wie oft jedes Zeichen vorkommt. Davon wieder jeweils die Hälfte, solange bis auf Stringlänge 1 jedes Zeichen zugeordnet ist.
Die Aufträge zum Durchsuchen eines Teilstrings werden in eine Queue gegeben. (Wen's intressiert: Stichwort Breitensuche).


public void FindString()
{
    string zeichensatz = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char z = '.';
    int length = 0;
    char[] result;
    Queue<StringObj> q = new Queue<StringObj>();
    Dictionary<char, int> zCount = new Dictionary<char, int>();

    string countString = "";
    while (stringHider.Ask(countString) < 0)
    {
        countString += z;
    }

    length = countString.Length;
    result = new String(z, length).ToCharArray();

    // Start vorbereiteun
    foreach (char a in zeichensatz) zCount.Add(a, stringHider.Ask(new String(a, length)));
    zCount = SortDict(zCount);
    Start(new StringObj(zCount, 0), ref z, ref length, result, q);

    // solange arbeiten, bis keine neuen Einträge in der Queue erscheinen.
    while (q.Count > 0) Start(q.Dequeue(), ref z, ref length, result, q);
}

public class StringObj
{
    public int i = 0;
    public int l = 0;
    public Dictionary<char, int> d;
    public StringObj(Dictionary<char, int> d, int i)
    {
        this.i = i;
        this.d = d;
        foreach (KeyValuePair<char, int> p in d) l += p.Value;
    }
}

Dictionary<char, int> SortDict(Dictionary<char, int> d)
{
    return (from item in d
            where item.Value > 0
            orderby item.Value descending
            select item).ToDictionary(kvp => kvp.Key, kvp => kvp.Value) as Dictionary<char, int>;
}

string DictToString(Dictionary<char, int> d)
{
    string s = "";
    foreach (KeyValuePair<char, int> p in d) s += new String(p.Key, p.Value);
    return s;
}

public void Start(StringObj sobj, ref char z, ref int length, char[] result, Queue<StringObj> q)
{
    if (sobj.l > 1)
    {
        Dictionary<char, int> vorne = new Dictionary<char, int>();
        Dictionary<char, int> hinten = new Dictionary<char, int>(sobj.d);
        int iVorne = sobj.i;
        int iHinten = sobj.i + sobj.l / 2;

        char[] buildstring = new String(z, length).ToCharArray();

        foreach (KeyValuePair<char, int> p in sobj.d)
        {
            for (int i = iVorne; i < iHinten; i++) buildstring[i] = p.Key;
            vorne.Add(p.Key, stringHider.Ask(new String(buildstring)));
        }

        foreach (KeyValuePair<char, int> p in vorne)
        {
            hinten[p.Key] -= p.Value;
        }

        vorne = SortDict(vorne);
        hinten = SortDict(hinten);

        if (vorne.Count > 0) q.Enqueue(new StringObj(vorne, iVorne));
        if (hinten.Count > 0) q.Enqueue(new StringObj(hinten, iHinten));
    }
    if (sobj.l == 1)
    {
        foreach (KeyValuePair<char, int> p in sobj.d) result[sobj.i] = p.Key;
        if (!result.Contains(z))
        {
            if (stringHider.Ask(new String(result)) == -2)
            {
                q.Clear();
            }
        }
    }
}


PS:
Die gesuchten Strings sind bei jedem durchlauf gleich. Wenn man zufällige Strings verwendet, braucht mein Programm kurioserweise durchschnittlich mehr Versuche. (Genauso verhält es sich mit meinem anderen Algo)


int seed = DateTime.Now.Millisecond; 
if (value != null)
{
    foreach (char a in value)
    {
        seed += a;
    }
}
value = "";
...
Random r = new Random(seed);
...
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von Alf Ator am .
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

StringFinder - Auflösung

beantworten | zitieren | melden

Hallo zusammen,

bin wieder da Die Aufgabe scheint ja (aus welchem Grund auch immer --> zu einfach? ) ganz gut bei euch angekommen sein.

Ich habe mir aus diesem Grund auch die Arbeit gemacht und alle (gültigen) Lösungsvorschläge getestet. Hier eine kleine Zusammenfassung:

1. Testbedingungen
Alle Algorithmen wurden dreimal getestet:
  1. Länge 50-100 auf 10.000 Durchläufen
  2. Länge 100-200 auf 1.000 Durchläufen
  3. Länge 300-500 auf 1.000 Durchläufen

Außerdem habe ich mit Rücksicht auf den Moderationshinweis von herbivore auch das Datum des letzten Edits als "Abgabedatum" berücksichtigt.

2. Ergebnisse
Insgesamt habe ich fünf gültige Lösungen getestet.
Hier die Ergebnisse
Format: <Name>, <Datum>: <Anzahl Test 1>/<Anzahl Test 2> / <Anzahl Test 3
  1. myUnderTakeR, 26.07: 903 / 1841 / 5265
  2. Daniel B., 27.07 (5:39): 974 / 1975 / 5681
  3. Alf Ator, 27.07 (17:13): 680 / 1757 / 5672
  4. gfoidl, 27.07 (22:56): 572 / 1356 / 4512
  5. ProgrammierTroll, 28.07: 708 / 1688 / 5426


3. Gewinner der Aufgabe

Laut den von herbivore angesprochenen Regeln gilt derjenige als Gewinner, der die erste gültige Lösung postet.
Daher erkläre ich myUnderTakeR zum Gewinner und überlasse ihm die nächste Aufgabe Die Anzahl der Versuche ist auf jeden Fall zufriedenstellend und entspricht in etwa der von mir erwarteten Lösung.

Nichtsdestotrotz möchte ich eine "besondere Anerkennung" an Alf Ator und gfoidl aussprechen (auch wenn Alf Ator's zweite Lösung nicht fehlerlos funktioniert ^^), da die Algorithmen deutlich optimiert und umfangreicher ausgefallen sind.

Freue mich auf die nächste Aufgabe.

Gruß
stes
private Nachricht | Beiträge des Benutzers
jreusch
myCSharp.de - Member

Avatar #avatar-3346.jpg


Dabei seit:
Beiträge: 303

beantworten | zitieren | melden

Juhu :D
Dann kommt von mir nun die nächste Aufgabe.

Ziel ist es folgende Methode zu implementieren:

/// <summary>
/// Berechnet die Anzahl der Permutation von [1,...,n], bei denen der
/// Absolutbetrag der Differenz zweier aufeinanderfolgender Zahlen zwischen
/// min und max liegt. (min ≤ max ≤ n)
/// </summary>
/// <param name="n">Anzahl und Werte der Elemente (n Elemente mit den Werten 1-n)</param>
/// <param name="min">Minimaler Abstand zwischen zwei aufeinanderfolgenden Elementen (inklusive)</param>
/// <param name="max">Maximaler Abstand zwischen zwei aufeinanderfolgenden Elementen (inklusive)</param>
/// <returns>Anzahl der möglichen Permutationen</returns>
public static int CountPermutations(int n, int min, int max)
{
//[...]
}


Um das Ganze etwas klarer zu machen, gibt es hier zwei Beispiele:

Gültige Permutationen für 'n=4; min=2; max=3' sind:
[2, 4, 1, 3]
[3, 1, 4, 2]
=> 2 Möglichkeiten

Gültige Permutationen für 'n=10; min=4; max=5' sind:
[1, 5, 9, 4, 8, 3, 7, 2, 6, 10]
[1, 5, 10, 6, 2, 7, 3, 8, 4, 9]
[1, 6, 2, 7, 3, 8, 4, 9, 5, 10]
[1, 6, 10, 5, 9, 4, 8, 3, 7, 2]
[2, 7, 3, 8, 4, 9, 5, 1, 6, 10]
[2, 7, 3, 8, 4, 9, 5, 10, 6, 1]
[9, 4, 8, 3, 7, 2, 6, 1, 5, 10]
[9, 4, 8, 3, 7, 2, 6, 10, 5, 1]
[10, 5, 1, 6, 2, 7, 3, 8, 4, 9]
[10, 5, 9, 4, 8, 3, 7, 2, 6, 1]
[10, 6, 1, 5, 9, 4, 8, 3, 7, 2]
[10, 6, 2, 7, 3, 8, 4, 9, 5, 1]
=> 12 Möglichkeiten


Hier gibts noch drei Lösungen, mit denen ihr eure Ergebnisse abgleichen könnt:
n=13; min=6; max=9 => 264 Möglichkeiten
n=15; min=7; max=10 => 502 Möglichkeiten
n=20; min=10; max=15 => 2 Möglichkeiten


Ziel ist es nicht die Permutationen selbst, erst recht nicht in aufsteigender Reihenfolge,
sondern nur die Anzahl der Möglichkeiten anzugeben.

Das Ganze hilft aber ungemein, um zu prüfen wie die Berechnung vorranschreitet.


Um hier unnötig viel Codepostings vorzubeugen, hat derjenige gewonnen, der die korrekten Lösungen für folgende Eingaben errechnet:
a) n=27; min=6; max=7
b) n=23; min=11; max=14
c) n=16; min=5; max=8

Bei den Eingaben sollte spätestens jetzt klar sein, dass der naive Ansatz hier nicht zum Ziel führt.
Wenn die Ergebnisse stimmen könnt ihr dann Euren Code posten und Ruhm und Ehre einstreichen :-)

Viel Spaß bei der Aufgabe!
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Hallo myUnderTakeR

Hier sind meine Ergebnisse:
a) n=27; min=6; max=7 ---> 112
b) n=23; min=11; max=14 --> 5552
c) n=16; min=5; max=8 -----> 17088


class Program
    {
        static List<int> permutation = new List<int>();
        static List<List<int>> solutions = new List<List<int>>();
        static void Main(string[] args)
        {
            Console.WriteLine("Count Permutations!\n\n");
            Console.Write("Höchstmögliche Zahl [1 .. n]: ");
            int n, min, max;
            while (!int.TryParse(Console.ReadLine(), out n))
            {
                Console.Write("Ungültige Eingabe! Erneuter Versuch: ");
            }
            Console.Write("Minimaler Abstand: ");
            while (!int.TryParse(Console.ReadLine(), out min))
            {
                Console.Write("Ungültige Eingabe! Erneuter Versuch: ");
            }
            Console.Write("Maximaler Abstand: ");
            while (!int.TryParse(Console.ReadLine(), out max))
            {
                Console.Write("Ungültige Eingabe! Erneuter Versuch: ");
            }
            int ret = CountPermutations(n, min, max, 1, true);
            Console.Write("{0} Lösungen gefunden! Sollen die Lösungen ausgegeben werden? [N/y]: ", ret);
            if (Console.ReadLine().ToLower() == "y")
            {
                Console.WriteLine();
                foreach (List<int> perm in solutions)
                {
                    Console.Write("[");
                    foreach (int item in perm)
                    {
                        Console.Write(item.ToString() + " ");
                    }
                    Console.Write("]\n");
                }
                Console.ReadLine();
            }
        }

        /// <summary>
        /// Berechnet die Anzahl der Permutation von [1,...,n], bei denen der
        /// Absolutbetrag der Differenz zweier aufeinanderfolgender Zahlen zwischen
        /// min und max liegt. (min ≤ max ≤ n)
        /// </summary>
        /// <param name="n">Anzahl und Werte der Elemente (n Elemente mit den Werten 1-n)</param>
        /// <param name="min">Minimaler Abstand zwischen zwei aufeinanderfolgenden Elementen (inklusive)</param>
        /// <param name="max">Maximaler Abstand zwischen zwei aufeinanderfolgenden Elementen (inklusive)</param>
        /// <returns>Anzahl der möglichen Permutationen</returns>
        public static int CountPermutations(int n, int min, int max, int act, bool basicCall)
        {
            //Rekursiver Ausstieg
            if (act > n || act < 1 || permutation.Contains(act)) //Außerhalb des Definitionsbereiches!
            {
                return -1;
            }
            //Da wir innerhalb des Bereiches sind - gültige Zahl hinzufügen!
            permutation.Add(act);
            if (permutation.Count == n) //Lösung gefunden!
            {
                List<int> list = new List<int>(permutation);
                solutions.Add(list);
                permutation.RemoveAt(permutation.Count - 1); //Letztes Element wieder entfernen
                return -1; //Da wir alle Lösungen wollen, geben wir an, keine Lösung gefunden zu haben!
            }
            //Rekursiver Abstieg
            for (int i = min; i ≤ max; i++)
            {
                CountPermutations(n, min, max, act + i, false);
                CountPermutations(n, min, max, act - i, false);
            }
            if (basicCall)
            {
                permutation.Clear();
                act++;
                CountPermutations(n, min, max, act, true);
            }
            permutation.Remove(act);
            return solutions.Count;
        }
    }
Dirty-Backtracking aber was solls - es funktioniert ;)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
jreusch
myCSharp.de - Member

Avatar #avatar-3346.jpg


Dabei seit:
Beiträge: 303

beantworten | zitieren | melden

Hallo Daniel B.,

knapp zwei Stunden hats gedauert, die Aufgabe war wohl zu leicht :-)

Glückwunsch, die Ergebnisse sind richtig. Dann kannst du nun deine Lösung posten (vll. als Edit zu den Ergebnissen?) und eine neue Aufgabe stellen.

Grüße
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von jreusch am .
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Ich möchte eine Klasse die einen Generischen Binärbaum zur verfügung stellt. Die Objekte die in den Baum eingefügt werden müssen ICompareable sein.

Der Baum soll folgende
-Methoden: Insert, Remove, Clear, Contains
-Properties: Count
-Indexer: item setzen und zurückgeben

Insert: Fügt Element T in den Baum ein
Remove: Löscht übergebenes Element
Clear: Löscht den gesamten Baum
Contains: Falls das übergebene Object im Baum ist wird 'true' zurückgegeben ansonsten 'false'
Count: Liefert die Anzahl der Elemente im Baum (beim Insert mitzählen - nicht jedesmal neu Zählen)


public class BinaryTree<T> where T: IComparable<T>
{
      public bool Remove(T data) {}
      public void Insert(T data) {}
      public bool Contains(T data) {}
      public void Clear() {}
      public int Count { get { return this.count; }}
      public T this[int index] { get; set; }
}

Vielleicht noch hilfreich: Binärbaum

Der Baum MUSS immer ausgeglichen sein. D.h. jeder Knoten hat maximal zwei Blätter und beim Einfügen in den Baum muss man darauf achten wie man absteigt (rechts oder links).
Beim Zugriff mit Index wird der Baum nach Preorder durschucht (hier gut zu erkennen)



//EDIT:

Da mir keine "lustigen" Sachen einfallen - kann man ersatzweise auch vorheriges Beispiel iterativ lösen :)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hallo!

ich will den Thread mal wieder aus der Inaktivität zurückholen :D

Nach den Regelungen in herbivore's erstem Beitrag
Zitat von herbivore
Wenn eine Woche seit dem jeweils letzten Beitrag vergangen ist, ist der Thread wieder frei für eine neue Aufgabe (egal wer die neue Aufgabe stellen möchte und egal ob dieser letzte Beitrag nun eine Aufgabe, eine Nachfrage oder eine Lösung ist und egal ob die Lösung richtig oder falsch war, also einfach: eine Woche Inaktivität = neue Aufgabe erlaubt).

darf ja jetzt jeder wieder eine Aufgabe stellen, daher hier eine (zur Abwechslung mal wieder kurz lösbare) - Aufgabe:
[B]Aufgabe[/B]

Herr A und Herr B möchten sicher* Nachrichten übermitteln. Dabei gelten folgende Regeln:

[list]
[*]Eine Nachricht besteht nur aus Großbuchstaben
[*]Leerzeichen sind die einzigen erlaubten Sonderzeichen
[*]das heißt auch: Umlaute sind nicht erlaubt
[/list] 

Eine Nachricht wird folgendermaßen codiert:
Vor den Zeichen B, E, H, K, N, Q, T, W und Z wird jeweils das vorherige Zeichen angehängt (Bsp.: HALLO -> HGALLO; TEEKANNE -> TSEDEDKJANMNMED).
Anschließend wird die komplette Zeichenkette umgedreht (Bsp.: HALLO -> HGALLO -> OLLAGH; ...)

Um einen solchen String zu decodieren, haben Herr A und Herr B die folgende Methode entworfen:

[csharp]
        string decode(string s, int i = 0, bool replace = false)
        {
            return (i == s.Length) ? "" : (s.Length > i + 1)
            ? decode(s, i + 1, s[i + 1] % 3 == 0 &&
            s[i + 1] != ' ') + (s[i + 1] % 3 == 0
            && s[i + 1] != ' ' ? "" : s[i].ToString())
            : decode(s, i + 1) + s[i];
        }
[/csharp]

Wie man sieht, ist der Code nicht sonderlich übersichtlich. Herr A und Herr B's Code Style ist nämlich durchaus zu optimieren.

Die Methode zum Codieren geht noch einen Schritt weiter. Nach etwas Überlegen und Herausnehmen jeglicher Struktur hat es Herr A geschafft, den Methodenrumpf (ohne "{" und "}" ) auf unter 80 Zeichen zu komprimieren und in eine Zeile zu bringen.

[FRAME]Aufgabe: Implementiere die Methode zum Codieren der Nachricht nach dem oben beschriebenen Verfahren. Der Rumpf darf dabei höchstens 100 Zeichen lang sein (optimal wären natürlich unter 80, mal sehen wer es schafft^^).

Der Methodenkopf soll dabei wie folgt aussehen:


        string c(string s, int i = 0)
        {
           // max. 100, besser sogar 80 Zeichen!!
        }

Kleiner Tipp zu den o.g. Zeichen: Schaut euch mal eine ASCII-Tabelle an, die sind nicht willkürlich ausgesucht ;)

[Wichtiger Hinweis: Zu lange Beschäftigung mit dieser Aufgabe kann den eigenen Programmierstil irreparabel degradieren :D bzw. "MNDERDEIDARGDED LDEABARAPDERRI LISTSRDEIMMARGORP MNDEMNDEGIDE MNDED MNMNAJK DEABAGFUA RDESDEID STIM GMNUGISTFDEAGHCSDEAB DEGMNAL UYZ"]

(*) Und zum Schluss.. dass das Verfahren alles andere als "sicher" ist, wissen wir wahrscheinlich alle :D [/frame]
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von stes am .
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Erster versuch:


return string.Concat(p.Reverse().Select((c)=>(c%3==0?(char)(c-1)+"":"")+c).ToArray());
Zweiter versuch:

return (i+1<p.Length?encode(p,i+1):"")+(p[i]%3==0?(char)(p[i]-1)+"":"")+p[i];
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hallo Floste,

den zweiten Versuch lasse ich gelten, habe in der Aufgabenstellung vergessen zu sagen dass nur die string.Length aus der string Klasse verwendet werden darf (wegen string.Reverse ^^).
Naja läuft auf jeden fall, wen es interessiert hier die Lösung die ich zusammengebastelt habe:


return(s.Length>i)?c(s,i+1)+(s[i]%3==0&s[i]!=' '?""+(char)(s[i]-1):"")+s[i]:"";
ist sogar etwas länger ^^

Jedenfalls bist du dann jetzt dran, bin gespannt auf die neue Aufgabe.

Gruß
stes
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Zitat
string.Reverse
String hat garkeine Reverse-methode^^
Du meinst wohl eher System.Linq.Enumerable.Reverse

Naja Ich stell mal eine neue aufgabe:

Erstelle einen "synthesizer" mit OpenAL

Konkret: Ein ton soll on the fly generiert und mittels OpenAL ausgegeben werden.
Das kann z.B. eine sinus- oder sägezahnwelle sein, eine schwebung oder sogar eine melodie wäre auch nett, bei ner einfachen sinusschwingunggilt die aufgabe aber auch schon als gelöst.
Um auf OpenAL zuzugreifen habe ich unten die nötigen dllimports angefügt, aber wer unbedingt will kann auch OpenTK verwenden.
Ich hatte an eine konsolenanwendung gedacht, die einfach solange spielt, bis man das fenster schließt, aber die oberfläche ist jedem selbst überlassen!

Noch ein paar regeln:
-Es ist nicht erlaubt, eine sounddatei auf der platte zu erstellen. Der ton muss die ganze zeit on the fly generiert werden.
-Die tonhöhe muss durch konstanten im quelltext oder sonstige parameter/eingaben frei wählbar sein.

Aufwand: Je nachdem, wie man sich anstellt, sollte es zwischen 55 und 110 zeilen liegen. (Meine lösung hat 55 zeilen)

Ich hoffe, dass ihr es nicht bei einem sinuston belasst, sondern auch ein bisschen damit rumspielt und verschiedene klänge und effekte ausprobiert, denn das war die eigendliche grundidee!

Wer sich nicht so auskennt: Hier sind die benötigten apis:
alcOpenDevice, alcCreateContext, alcMakeContextCurrent, alGenSources, alGenBuffers, alGetSourcei, alSourceUnqueueBuffers, alBufferData, alSourceQueueBuffers, alSourcePlay (lieber zu oft als zu selten), Thread.Sleep
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Floste am .
Attachments
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Berechnung von: http://en.wikipedia.org/wiki/Sine_wave



        static void Main(string[] args)
        {
            IntPtr device = OpenAL.ALC.OpenDevice(null);
            IntPtr context = OpenAL.ALC.CreateContext(device, null);
            OpenAL.ALC.MakeContextCurrent(context);
            uint sources;
            OpenAL.AL.GenSources(1, out sources);
            short[] wave = GenerateWave(8000, 1000);
            uint buffer = OpenAL.AL.GenBuffer();
            OpenAL.AL.SourceUnqueueBuffers(sources, 1);
            OpenAL.AL.BufferData(buffer, AlAudioFormat.Mono16Bit, wave, wave.Length, 1000);
            OpenAL.AL.SourceQueueBuffers(sources, 1, ref buffer);
            while (true)
            {
                OpenAL.AL.SourcePlay(sources);
                System.Threading.Thread.Sleep(1500);
            }
        }

        static short[] GenerateWave(int sampleRate, int frequenz)
        {
            short[] waves = new short[sampleRate];
            short amplitude = short.MaxValue / 8;
            for (int n = 0; n < waves.Length; n++)
            {
                waves[n] = (short)(amplitude * Math.Sin((2 * Math.PI * n * frequenz) / sampleRate));
            }
            return waves;
        }
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Ich weiß ned so recht: Die lösung spielt zwar einen ton mit 125 hz** ab, aber man hört ein regelmäßiges ploppen, da das abspielen erst kurz nach dem ende wieder angestoßen wird.

Der trick es unterbrechungsfrei hinzubekommen liegt eigendlich darin, mehr als einen buffer zu verwenden und diese nacheinander einzureihen, sodass SourcePlay eigendlich nur einmal aufgerufen werden muss! Mit on the fly meinte ich, dass man die buffer neu befüllt, bevor man sie wieder verwendet. Wenn man das nicht macht, hat man ein problem wenn man zwei oder mehr frequenzen gleichzeitig spielen will.


AL.GetSourcei(source, AlSourceInts.Buffers_Queued);
AL.GetSourcei(source, AlSourceInts.Buffers_Processed);
Buffers_Processed gibt an, wieviele buffer vollständig abgespielt wurden und entfernt werden können. Buffers_Queued gibt an, wieviele buffer insgesamt in der schlange sind.

**125hz und nicht 1000 hz, weil der letzte parameter von BufferData die sampelrate ist, aber daran solls ned scheitern^^
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Hier mein 2ter Versuch:


static void Main(string[] args)
        {
            int bufferCount = 5;
            Random rand = new Random();
            IntPtr device = OpenAL.ALC.OpenDevice(null);
            IntPtr context = OpenAL.ALC.CreateContext(device, null);
            OpenAL.ALC.MakeContextCurrent(context);
            uint source;
            OpenAL.AL.GenSources(1, out source);
            uint[] buffers = new uint[bufferCount];
            OpenAL.AL.GenBuffers(bufferCount, buffers);
            OpenAL.AL.SourceUnqueueBuffers(source, bufferCount, buffers);
            for (int i = 0; i < bufferCount; i++)
            {
                short[] wave = GenerateSound(rand.Next(3000, 8001), rand.Next(500, 2001));
                OpenAL.AL.BufferData(buffers[i], AlAudioFormat.Mono16Bit, wave, wave.Length, 1000);
            }
            OpenAL.AL.SourceQueueBuffers(source, bufferCount, buffers);
            OpenAL.AL.SourcePlay(source);
            int act = 0;
            while (true)
            {
                int proc = OpenAL.AL.GetSourcei(source, OpenAL.AlSourceInts.Buffers_Processed);
                if (proc > 0)
                {
                    OpenAL.AL.SourceUnqueueBuffers(source, 0);
                    short[] wave = GenerateSound(rand.Next(3000, 8001), rand.Next(500, 2001));
                    OpenAL.AL.BufferData(buffers[act], AlAudioFormat.Mono16Bit, wave, wave.Length, 1000);
                    act++;
                    if (act == bufferCount) { act = 0; }
                    OpenAL.AL.SourceQueueBuffer(source, buffers[act]);
                }
            }
        }

        static short[] GenerateSound(int sampleRate, int frequenz)
        {
            short[] waves = new short[sampleRate];
            short amplitude = short.MaxValue / 2;
            for (int n = 0; n < waves.Length; n++)
            {
                waves[n] = (short)(amplitude * Math.Sin((2 * Math.PI * n * frequenz) / sampleRate));
            }
            return waves;
        }
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Wirklich glücklich bin ich nicht:
Mein PC mag es irgendwie nicht, dass du die bufferlängen auswürfelst und spielt deshalb keinen ton ab.
Deine Schleifenlogik ist auch recht ulkig:

Wenn mehr als 0 buffer verarbeitet wurden, dann:
1. Nimm 0 (=keine) buffer aus der queue
2. Befülle genau einen buffer mit daten (ganz egal wieviele buffer gespielt wurden)
3. Packe den nachfolger dieses buffers in die warteschlange

Außerdem lastest du einen kern zu 100% aus.

Ich poste hier einfach mal meine lösung und wer will kann eine neue aufgabe stellen.

using System;
using OpenAL;

namespace ALSynthesizer
{
    class Program
    {
        const int samplerate = 44100;
        const double frequency = 1000;
        const double frequency2 = 0.5;

        static void Main(string[] args)
        {
            //Setup OpenAl:
            IntPtr device = ALC.OpenDevice(null);
            IntPtr ctx = ALC.CreateContext(device, null);
            ALC.MakeContextCurrent(ctx);

            uint source = AL.GenSource();
            short[] samples = new short[1024];
            uint[] buffers = AL.GenBuffers(10);
            int iCurrentBuffer = 0;
            //Status of sine wave:
            double rotangle = 0, rotangle2 = 0;
            while (true)
            {
                //Get information:
                int numQueued = AL.GetSourcei(source, AlSourceInts.Buffers_Queued);
                int numProcessed = AL.GetSourcei(source, AlSourceInts.Buffers_Processed);
                int numRemaining = numQueued - numProcessed;
                //Take the processed buffers from the queue:
                if (numProcessed > 0) AL.SourceUnqueueBuffers(source, numProcessed);

                if (numRemaining ≥ buffers.Length)//Nothing to do?
                {
                    System.Threading.Thread.Sleep(5);//Then wait a bit
                    continue;//and try again
                }
                //Calculate the new samples:
                for (int i = 0; i < samples.Length; i++)
                {
                    rotangle += frequency * ((Math.PI * 2) / samplerate);
                    if (rotangle > Math.PI * 2) rotangle -= Math.PI * 2;

                    rotangle2 += frequency2 * ((Math.PI * 2) / samplerate);
                    if (rotangle2 > Math.PI * 2) rotangle2 -= Math.PI * 2;
                    samples[i] = (short)(Math.Sin(rotangle) * Math.Sin(rotangle2) * short.MaxValue);
                }
                //Queue the samples
                AL.BufferData(buffers[iCurrentBuffer], AlAudioFormat.Mono16Bit, samples, sizeof(short) * samples.Length, samplerate);
                AL.SourceQueueBuffer(source, buffers[iCurrentBuffer]);
                if (++iCurrentBuffer ≥ buffers.Length) iCurrentBuffer = 0;//Increment iBuffer
                //Play if the source is not already playing
                if ((AlSourceState)AL.GetSourcei(source, AlSourceInts.Source_State) != AlSourceState.Playing)
                    AL.SourcePlay(source);
            }
        }
    }
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Naja da ich mich noch nie mit dieser Sound Api beschäftigt habe bin ich einfach nach den Variablennamen in den Methoden gegangen - was definitiv falsch war^^. Ich habe mir zwar die Doku zu der API angesehen aber zu wenig Zeit und da auf meinem Rechner ununterbrochen einen Ton abgespielt wurde dachte ich ich poste es einfach mal :)
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Mir ist gerade etwas eingefallen und dachte ich Poste das einfach mal.

Ein Algorithmus der ein 2-Dimensionales Array ausgibt. Der Haken ist, dass das ganze 'schön' aussehen soll. Dass heißt man soll sehen wie die Ausgabe erfolgt:


public void Print2Console()
        {
            for (int i = 0; i < field.GetLength(0); i++)
            {
                for (int j = 0; j < field.GetLength(1)*2+1; j++)
                {
                    Console.Write("-");
                }
                Console.WriteLine();
                Console.Write("|");
                for (int j = 0; j < field.GetLength(1); j++)
                {
                    Console.Write(field[i, j].ToString() + "|");
                    System.Threading.Thread.Sleep(10); //Somit 'sieht' man den Aufbau
                }
                Console.WriteLine();
            }
        }

Dadurch dass man manchmal aber nicht einfach nur Zeile für Zeile, Spalte für Spalte ausgeben möchte, sollt ihr eine Methode implementieren die ca. so aussieht:


public static void PrintField(object[,] field, (enum/flag) PrintOption, int sleepTime)

Es kann nur eine PrintOption ausgewählt werden - also niemals zwei zur gleichen Zeit.

Als PrintOption sollen verfügbar sein:

Normal (Array wird Zeile für Zeile, Spalte für Spalte ausgegeben)
BottomUp (Array wird von letzter Zeile bis zur ersten ausgegeben, Spalten wieder wie bei Normal)
BottomUpSecond (Array wird von letzter Zeile bis zur ersten ausgegeben, Spalten werden jedoch einmal von 0 - x und dann von x - 0 usw. ausgegeben)

Bin gespannt ob es jemand lösen möchte, bis dahin: Viel Spaß!
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Moin moin,

hier meine Lösung:


        static void Main(string[] args)
        {
            int i = 0;
            object[,] arr = new object[5, 5];
            for (int x = 0; x < 5; x++)
            {
                for (int y = 0; y < 5; y++)
                {
                    arr[x, y] = i++;
                }
            }
            PrintField(arr, PrintOptions.BottomUpSecond, 100);
            Console.ReadKey();
        }

        public static void PrintField(object[,] field, PrintOptions PrintOption, int sleepTime)
        {
            if (PrintOption == PrintOptions.Normal)
            {
                for (int i = 0; i < field.GetLength(0); i++)
                {
                    // länge der zeile bestimmen
                    StringBuilder s = new StringBuilder();
                    s.Append("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        s.Append(field[i, j].ToString() + "|");
                    }

                    for (int j = 0; j < s.Length; j++)
                    {
                        Console.Write("-");
                    }
                    Console.WriteLine();
                    Console.Write("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        Console.Write(field[i, j].ToString() + "|");
                        System.Threading.Thread.Sleep(sleepTime); //Somit 'sieht' man den Aufbau
                    }
                    Console.WriteLine();
                }
            }
            else if (PrintOption == PrintOptions.BottomUp)
            {
                Console.CursorTop = field.GetLength(0)*2-1;
                for (int i = field.GetLength(0)-1; i ≥ 0; i--)
                {
                    Console.Write("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        Console.Write(field[i, j].ToString() + "|");
                        System.Threading.Thread.Sleep(sleepTime); //Somit 'sieht' man den Aufbau
                    }
                    Console.CursorTop--;
                    Console.CursorLeft = 0;
                    // länge der zeile bestimmen
                    StringBuilder s = new StringBuilder();
                    s.Append("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        s.Append(field[i, j].ToString() + "|");
                    }

                    for (int j = 0; j < s.Length; j++)
                    {
                        Console.Write("-");
                    }
                    Console.CursorTop-= Console.CursorTop > 0 ? 1 : 0;
                    Console.CursorLeft = 0;
                }
                Console.CursorTop = field.GetLength(0) * 2;
            }
            else if (PrintOption == PrintOptions.BottomUpSecond)
            {
                Console.CursorTop = field.GetLength(0) * 2 - 1;
                bool left2right = false;
                for (int i = field.GetLength(0) - 1; i ≥ 0; i--)
                {
                    // länge der zeile bestimmen
                    StringBuilder s = new StringBuilder();
                    s.Append("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        s.Append(field[i, j].ToString() + "|");
                    }
                    if (left2right)
                    {
                        Console.Write("|");
                        for (int j = field.GetLength(1) - 1; j ≥ 0; j--)
                        {
                            Console.Write(field[i, j].ToString() + "|");
                            System.Threading.Thread.Sleep(sleepTime); //Somit 'sieht' man den Aufbau
                        }
                    }
                    else
                    {
                        Console.CursorLeft = s.Length;
                        for (int j = field.GetLength(1) - 1; j ≥ 0; j--)
                        {
                            string write = field[i, j].ToString() + "|";
                            Console.CursorLeft -= write.Length;
                            Console.Write(field[i, j].ToString() + "|");
                            Console.CursorLeft -= write.Length;
                            System.Threading.Thread.Sleep(sleepTime); //Somit 'sieht' man den Aufbau
                        }
                        Console.CursorLeft = 0;
                        Console.Write("|");
                    }
                    left2right = !left2right;
                    Console.CursorTop--;
                    Console.CursorLeft = 0;
                    for (int j = 0; j < s.Length; j++)
                    {
                        Console.Write("-");
                    }
                    Console.CursorTop -= Console.CursorTop > 0 ? 1 : 0;
                    Console.CursorLeft = 0;
                }
                Console.CursorTop = field.GetLength(0) * 2;
            }
        }

        public enum PrintOptions
        {
            Normal,         // Array wird Zeile für Zeile, Spalte für Spalte ausgegeben
            BottomUp,       // Array wird von letzter Zeile bis zur ersten ausgegeben, Spalten wieder wie bei Normal)
            BottomUpSecond  // Array wird von letzter Zeile bis zur ersten ausgegeben, Spalten werden jedoch einmal
                            // von 0 - x und dann von x - 0 usw. ausgegeben)
        }

Nicht schön programmiert, aber immerhin habe ich mal meine alten Freunde Strg+C, Strg+V sowie if & else wieder getroffen ^^

Gruß
stes

P.S.: Ich war mal so frei und habe die Länge der Trennstriche zwischen den Zeilen auf die tatsächliche Zeilenlänge hochgesetzt, siehe


                    // länge der zeile bestimmen
                    StringBuilder s = new StringBuilder();
                    s.Append("|");
                    for (int j = 0; j < field.GetLength(1); j++)
                    {
                        s.Append(field[i, j].ToString() + "|");
                    }
Wobei s.Length dann die Zeilenlänge darstellt
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Funktioniert :)

Viel Spaß mit der nächsten Aufgabe :)
Zitat
P.S.: Ich war mal so frei und habe die Länge der Trennstriche zwischen den Zeilen auf die tatsächliche Zeilenlänge hochgesetzt, siehe
Nachdem ich in dem Programm wo ich das raushab nur 1 Zeichen pro Spalte hatte, habe ich es so lassen können, aber deine Variante ist natürlich die Verallgemeinerung ;)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hallo zusammen,

hier die neue Aufgabe:
[B][U]MouseBall[/U][/B]

Ziel soll die Entwicklung eines kleines Spielchens sein. Evtl kennt es der ein oder andere von iPod & Co.: Ein Ball muss durch Antippen (hier: Anklicken) möglichst oft hochgehalten werden.

Die GUI für das Spiel gebe ich vor (siehe Anhang). Wenn ihr das Projekt so startet, befindet sich der Ball auf Startposition. Punkte bekommt man, indem man den Ball über die Linie in der Mitte spielt.

[FRAME]
Anforderungen an eine korrekte Lösung:

* Aktualisierung der Punktzahl während des Spiels und evtl. der Highscore (Informierung über neue Highscore z.B. per MessageBox möglich, aber nicht unbedingt gefordert)
* Ball kann nur [U]unter[/U] der Linie angespielt werden. Beim Anspielen erhält der Ball zusätzlich zur Bewegung nach oben noch eine Bewegung nach rechts oder links, je nachdem wo ihn die Maus trifft.
* Trifft der Ball an eine der Ränder des Panels, soll er von diesen auch abprallen.
* Wie erwähnt, gibt es einen Punkt, sobald der Ball über die Mittellinie gespielt wird

Hinweis: Es ist nicht unbedingt das Ziel, eine physikalisch besonders korrekte Flugkurve zu erhalten, das ganze ist ein [U]kleines Spiel zum Zeitvertreib und keine Simualtionssoftware[/U] ;) Andererseits soll es natürlich einigermaßen realistisch wirken (wenn ich z. B. von links unten gegen den Ball "schlage" soll er natürlich nicht nach links oben fliegen, sondern nach rechts oben^^)

Hier der (unvollständige) Code für die Interaktion. Meine Lösung erfordert das Hinzufügen von knapp 80 Codezeilen (wenn ich mich nicht verzählt habe :D)


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Reflection;
using System.IO;

namespace MouseBall
{
    public partial class Form1 : Form
    {
        public const float BALL_RADIUS = 20;

        // add/change fields as you please!
        private Image _ballImg;
        private PointF _ballPos;
        private PointF _speedVector;

        public int Score { get; private set; }
        public int Highscore { get; private set; }

        public Form1()
        {
            InitializeComponent();
            _pnlGame.Paint +=new PaintEventHandler(_pnlGame_Paint);
            _pnlGame.MouseClick += new MouseEventHandler(_pnlGame_MouseClick);

            this.initBall();

            // load and resize ball icon
            string s = Path.Combine(
                Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location),
                "soccer-ball.ico");
            _ballImg = new Bitmap(new Icon(s).ToBitmap());
            _ballImg = new Bitmap(_ballImg, new Size((int)BALL_RADIUS*2, (int)BALL_RADIUS*2));

            // let's start playing!
            _timer.Start();
        }

        private void initBall()
        {
            _ballPos = new PointF(_pnlGame.Width / 2, _pnlGame.Height - BALL_RADIUS);
        }

        private void _pnlGame_Paint(object sender, PaintEventArgs e)
        {
            Graphics g = e.Graphics;
            // paint middle line
            g.FillRectangle(
                Brushes.White,
                0,
                _pnlGame.Height/2-2,
                _pnlGame.Width,
                4);
            // paint the ball
            g.DrawImage(_ballImg, _ballPos.X - BALL_RADIUS,
                _ballPos.Y - BALL_RADIUS);
        }

        void _pnlGame_MouseClick(object sender, MouseEventArgs e)
        {
            // ... your part ;)
        }

        private void _timer_Tick(object sender, EventArgs e)
        {
            // ...your part ;)
            _lblScore.Text = Score.ToString();
            _pnlGame.Invalidate();
        }
    }
}



Kleiner Hinweis zur verwendeten Grafik: Quelle, Lizenz: Creative Commons (Attribution 3.0 Unported)

Das fertige Spiel liegt bereits fertig auf meiner Festplatte, evtl. wird es dann zusammen mit einer hier geposteten Lösung unter der GNU GPL v3 unter den "Projekten" veröffentlicht.
[/frame]

Viel Spaß mit der Aufgabe!

Gruß
stes
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von stes am .
Attachments
private Nachricht | Beiträge des Benutzers