Laden...

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Letzter Beitrag vor 3 Jahren 762 Posts 773.801 Views

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!

Hinweis von herbivore vor 12 Jahren

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

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

Hinweis von herbivore vor 12 Jahren

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

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]

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));
}

919-924 bei 5-6 Durchläufen

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.

Wer bei 10.000 Durchläufen (evtl. auch mehr, mal sehen) die kleinste durchschnittliche Anzahl an Versuchen benötigt, gewinnt dieses Programmierspiel.

&

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.

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!

q.e.d.

Hinweis von herbivore vor 12 Jahren

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!"

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]

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

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!"

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;
                                }
                            }
                        }
                    }
                }
            }
Hinweis von gfoidl vor 12 Jahren

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.

q.e.d.

[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);
...

StringFinder - Auflösung

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 1.Länge 100-200 auf 1.000 Durchläufen 1.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 1.Daniel B., 27.07 (5:39): 974 / 1975 / 5681 1.Alf Ator, 27.07 (17:13): 680 / 1757 / 5672 1.gfoidl, 27.07 (22:56): 572 / 1356 / 4512 1.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

Juhu 😄
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!

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 😉

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

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 😃

Hallo!

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

Nach den Regelungen in herbivore's erstem Beitrag

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 😄 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 😄[/frame]

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!

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

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

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

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;
        }

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^^

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

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;
        }

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);
            }
        }
    }
}

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

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 😃

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ß!

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

Funktioniert 😃

Viel Spaß mit der nächsten Aufgabe 😃

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 😉

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 😄)


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

Hier noch ein Screenshot von der GUI:

Hallo stes, hallo Forum,

ich wollte mal wieder was in C# machen und stolperte über diesen Thread (in dem schon echt interessante Aufgaben waren). Im Anhang ist meine Lösung für stes' Aufgabe. Auf das Kopieren des Quellcodes verzichte ich aufgrund der Länge (~180 Zeilen oder so) mal, er findet sich jedoch in der ZIP-Datei.

Sollte stes mit der Lösung einverstanden sein, kann gern jemand anderes die nächste Aufgabe stellen. =)


using System;
using System.Collections.Generic;
using System.ComponentModel;
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;
        public const float KICK_POWER = -15;
        public const float GRAVITY = 0.7f;
        public const float MAX_SPEED = 15;

        // add/change fields as you please!
        private Image _ballImg;
        private PointF _ballPos;
        private PointF _speedVector;
        private int _score;
        private int _highscore;
        private bool _playing;
        private bool _newHighscore;

        public int Score {
            get {
                return _score;
            }
            private set {
                _score = value;
                // ggf. neue Highscore setzen
                if (value > Highscore) {
                    Highscore = value;
                }
         
            }
        }

        public int Highscore {
            get {
                return _highscore;
            }
            private set {
                _highscore = value;
                _newHighscore = true;
            }
        }

        public bool Playing {
            get {
                return _playing;
            }
            private set {
                _playing = value;

                if (value) {
                    _lblStartGame.Hide();
                    _timer.Start();
                }
                else {
                    _timer.Stop();
                    if (_newHighscore) {
                        ShowNewHighscore();
                    }
                    initBall();
                    _lblStartGame.Show();
                    Score = 0;
                    _speedVector = new PointF(0.0f, 0.0f);
                    _newHighscore = false;
                }
            }
        }

        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));
        }

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

        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) {
            // Spiel ggf. starten
            if (!Playing) {
                Playing = true;
            }

            // Ball ist nur unterhalb der Mittellinie spielbar
            int centerLine = _pnlGame.Height / 2;
            if (e.Y >= centerLine) {
                float dX = e.X - _ballPos.X;
                float dY = e.Y - _ballPos.Y;
                float distSqr = dX * dX + dY * dY;
                // Ball angeklickt?
                if (distSqr <= BALL_RADIUS * BALL_RADIUS) {
                    _speedVector.Y = KICK_POWER;
                    _speedVector.X = 1.5f * KICK_POWER * dX / BALL_RADIUS;
                }
            }
        }

        private void _timer_Tick(object sender, EventArgs e) {
            _ballPos.Y += _speedVector.Y;
            _ballPos.X += _speedVector.X;
            // Fallgeschwindigkeit begrenzen (lässt sich sonst zu schwer treffen)
            _speedVector.Y = Math.Min(_speedVector.Y + GRAVITY, MAX_SPEED);

            CheckGameOver();
            DoCollisionChecks();
            DoScoring();

            _lblScore.Text = Score.ToString();
            _lblHighscore.Text = Highscore.ToString();
            _pnlGame.Invalidate();
        }

        private void DoScoring() {
            // Hat Ball Mittellinie gerade eben nach oben gekreuzt?
            int centerLine = _pnlGame.Height / 2;
            if ((_ballPos.Y < centerLine) && (_ballPos.Y - _speedVector.Y > centerLine)) {
                Score += 1;
            }
        }

        private void CheckGameOver() {
            // Ball unten? -> Spiel vorbei
            // Ball soll erst ganz verschwunden sein, ist so einfacher spielbar
            if (_ballPos.Y >= _pnlGame.Height + BALL_RADIUS) {
                Playing = false;
            }
        }

        private void DoCollisionChecks() {
            // Kollision mit oberem Spielfeldrand?
            if (_ballPos.Y <= BALL_RADIUS) {
                _ballPos.Y = BALL_RADIUS;
                _speedVector.Y *= -1;
            }

            // Linker Spielfeldrand?
            if (_ballPos.X <= BALL_RADIUS) {
                _ballPos.X = BALL_RADIUS;
                _speedVector.X *= -1;
            }

            // Rechter Spielfeldrand?
            if (_ballPos.X >= _pnlGame.Width - BALL_RADIUS) {
                _ballPos.X = _pnlGame.Width - BALL_RADIUS;
                _speedVector.X *= -1;
            }
        }

        private void ShowNewHighscore() {
            MessageBox.Show("Gratulation, das ist ein neuer Highscore!", "Gratulation",
                            MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
    }
}


Viele Grüße!

Hinweis von michlG vor 12 Jahren

So viel ist der code nun auch wieder nicht. ich hab den mal reinkopiert dann braucht nicht jeder extra den download machen.
Zusätzlich lass ich mal den Anhang dran 🙂

Hallo Mao,

habe mir die Lösung angeschaut, funktioniert alles soweit 😉

Beim Öffnen in Visual Studio musste ich allerdings noch das Icon in den Debug-Ordner kopieren, als Anmerkung für alle, die sich das Projekt auch noch ansehen wollen..
Weiterhin sollte man den jetzt doch noch nachträglich eingefügten Sourcecode nicht in mein ursprüngliches Projekt reinkopieren, da in Mao's Projekt noch ein zusätzliches Label zum Einsatz kommt, kurz: Einfach das angehängte Projekt downloaden ^^

Ansonsten kann Mao, oder

jemand anderes die nächste Aufgabe stellen.

Gruß stes

Highlighter

Hallo
weil sich ja jetzt nichts getan hat will ich eine neue Aufgabe stellen.

Zu schreiben ist eine Funktion, die in einer RichTextBox beim Hineinschreiben Syntax-Highlighting aktiviert.
Es sollten wenigstens folgende Wörter rot hervorgehoben werden:

if, else, while, for, int, bool, string, void, var, 42

Dazu soll darauf geachtet werden, dass die Funktion nicht länger als 15-20 Zeilen sein sollte.
Viel Spaß beim proggen =)

Der Don

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

Also ich finde das so Highlighting nicht mal eben so in 20 Zeilen gemacht werden kann.


[System.Runtime.InteropServices.DllImport("user32.dll")]
private extern static IntPtr SendMessage(IntPtr hWnd, int msg, IntPtr wp, IntPtr lp);

private void HighlightText()
{
    SendMessage(richTextBox1.Handle, 0xb, (IntPtr)0, IntPtr.Zero);
    int selectionStart = richTextBox1.SelectionStart;
    int selectionLength = richTextBox1.SelectionLength;
    richTextBox1.SelectAll();
    richTextBox1.SelectionColor = Color.Black;

    foreach (var keyword in Keywords)
    {
        foreach (int position in GetHighlightPositions(richTextBox1.Text, keyword.Key))
        {
            richTextBox1.Select(position, keyword.Key.Length);
            richTextBox1.SelectionColor = keyword.Value;
            richTextBox1.Select(position + keyword.Key.Length, 1);
            richTextBox1.SelectionColor = Color.Black;
        }
    }
    richTextBox1.Select(selectionStart, selectionLength);
    SendMessage(richTextBox1.Handle, 0xb, (IntPtr)1, IntPtr.Zero);
    richTextBox1.Invalidate();
}

private List<int> GetHighlightPositions(string text, string keyword)
{
    List<int> positions = new List<int>();
    int pos = 0, lastPos = 0;
    while (pos > -1 && lastPos < text.Length)
    {
        pos = text.IndexOfAny(Separators.ToArray(), lastPos);
        if (pos > -1)
        {
            if (pos - lastPos == keyword.Length)
            {
                if (text.Substring(lastPos, keyword.Length) == keyword)
                {
                    positions.Add(lastPos);
                }
            }
        }
        lastPos = pos + 1;
    }
    return positions;
}

Hallo thetruedon,

für den Fall, dass die Lösung von Alf Ator nicht anerkannt wird, weil sie zu lang ist 😃 hier meine Lösung innerhalb der Vorgaben: 14 Zeilen ohne Leerzeilen, 18 mit.

private const String keywordPattern
   = @"\b(?:if|else|while|for|int|bool|string|void|var|42)\b";

protected void HighlightText (Object sender, EventArgs e)
{
  int selectionStart  = _rtb.SelectionStart;
  int selectionLength = _rtb.SelectionLength;

  _rtb.SelectAll ();
  _rtb.SelectionColor = Color.Black;

  foreach (Match m in Regex.Matches (_rtb.Text, keywordPattern)) {
     _rtb.Select (m.Index, m.Length);
     _rtb.SelectionColor = Color.Red;
  }

  _rtb.Select (selectionStart, selectionLength);
}

Regex rules! 😃

herbivore

Sehr schön! Dann bist du jetzt auch dran, eine neue Aufgabe zu Posten =)

@Alf
OK der Ansatz ist zu erkennen, wobei natürlich die Keywords von mir gekonnt mal nicht verwendet wurden 😄 Aber am Ende hast du ja diese gefärbt also wenn keiner Einwände hat geht die Lösung klar.

@herbivore
Jap ziemlich genau so hab ich das ganze auch gelöst. Thumbs up

Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!

Hallo Community,

nachdem Alf Ator das Recht, eine Aufgabe zu stellen, an mich abgetreten hat (ich habe extra noch mal per PM nachgefragt), habe ich gleich eine Aufgabe, mit direktem Bezug zur vorigen. Wie man gesehen hat, ist die Lösung mit Regex viel kürzer und - wie ich finde - viel verständlicher, als die ohne.

Ich gebe zwar zu, dass Regex-Pattern zwar nicht immer leicht zu lesen sind (es ist einfacher, sie zu schreiben 😃, aber ich behaupte, dass Regex-Pattern immer noch leichter zu lesen sind, als wenn man sie in normalem Code ausprogrammieren würde.

Hier kommt eure Chance mich zu widerlegen!

Ich habe einen typisches Regex-Pattern zum Erkennen von HTML-Tags (inkl. eines Attributs) geschrieben. (Dass es in bestimmten Situationen günstiger sein kann, einen HTML-Parser zu verwenden, ist mir klar, soll hier aber keine Rolle spielen. Für die Aufgabe darf jedenfalls keiner verwendet werden.)

[B]Die Aufgabe ist, eine Methode zu schreiben, die mit normalen (String-)Operation exakt das gleiche tut, wie der folgende Code:[/B]

[CSHARP]
public static bool GetTag (String input, out String tag, out String key, out String value)
{
   tag = key = value = "";
   Match m = Regex.Match (input, pattern, RegexOptions.IgnoreCase | RegexOptions.IgnorePatternWhitespace);
   if (m.Success) {
      tag = m.Groups ["tag"].Value;
      key = m.Groups ["key"].Value;
      value = m.Groups ["value"].Value;
      return true;
   }
   return false;
}
[/CSHARP]

[CSHARP]
private static String pattern = @"
<\s*(?<tag>beispiel)
(?:
   \s+(?<key>[a-z]+)
   \s*=\s*
   (?:
      '(?<value>[^'>]*)'
   |
      (?<value>[^'>\s]+)
   )
)?\s*>
";
[/CSHARP]

Der Pattern bedeutet also mit anderen Worten:

Zuerst kommt eine öffnende eckige Klammer, dann können beliebig viele Spaces folgen, dann folgt das Tag (Gruppe "tag"), bestehend aus der Zeichenfolge "beispiel", also b, e, i, s, p, i, e, l, wegen RegexOptions.IgnoreCase unabhängig von der Groß- und Kleinschreibung.
dann kommt optional ein Attribut, das wie folgt aufgebaut ist:
... zuerst kommen ein oder mehrere Spaces, dann der Attributname (Gruppe "key"), bestehend aus beliebigen Buchstaben (a-z/A-Z, ohne Umlaute),
... dann können beliebig viele Spaces folgen, dann kommt ein Gleichheitszeichen, dann können beliebig viele Spaces folgen,
... dann kommt der Attributwert (Gruppe "value"),
...... wobei dieser entweder aus beliebigen Zeichen, aber nicht Anführungszeichen und nicht schließende spitze Klammer, zwischen genau zwei Anführungszeichen besteht
...... oder aus beliebigen Zeichen, aber nicht Space, nicht Anführungszeichen und nicht schließende spitze Klammer,
danach können beliebig viele Spaces folgen und am Ende steht eine schließende eckige Klammer.

"Spaces" sind z.B. alle White-Spaces-Zeichen, die auf \s passen. "Anführungszeichen" sind einfache Anführungszeichen, damit diese problemlos innerhalb von String-Literalen verwendet werden können. Die verbale Beschreibung dient ohnehin nur dazu, den Einstieg zu erleichtern; maßgeblich in allen Detailfragen und Zweifelsfällen ist der Regex-Pattern.

Achtet darauf, dass alle optionalen Teile und alle möglichen Alternativen berücksichtigt werden. Wo Spaces steht "dann können beliebig viele Spaces folgen", können sie vorhanden sein oder fehlen. Achtet anderseits darauf, dass nichts akzeptiert wird, was nicht erlaubt ist. Einfach bei den Anführungszeichen zu splitten und den Text dazwischen zu nehmen, reicht nicht, denn <beispiel 'value'=key> ist nicht erlaubt. Auch sind an vielen Stellen nur Leerzeichen erlaubt, nicht beliebige Zeichen. <beispiel : key='value'> und <beispiel key='value' nochirgendwas> würden also keinen Treffer liefern.

Ich habe den Pattern extra in mehrere Zeilen aufgeteilt, damit er lesbarer wird. Dank RegexOptions.IgnorePatternWhitespace geht das problemlos und erhöht die Lesbarkeit ziemlich. Dadurch hat er 10 Zeilen. Ich würde tippen, dass es keine native Lösung gibt, die mit weniger als 20-30 Zeilen auskommt, selbst wenn man Leerzeilen und Zeilen, die nur eine Klammer enthalten, nicht mitzählt, vorausgesetzt, jede Anweisung steht auf einer eigenen Zeile. Ich hätte zwar eine Idee, wie mit der man Anzahl der nötigen Zeilen drücken kann, doch die will ich noch nicht verraten.

Jetzt habe ich viel geschrieben. Entscheidet selbst, ob es euch hilft. Die Aufgabe ist jedenfalls in einem Satz und etwas Code beschrieben, siehe Kasten. Die Aufgabe gilt als nicht gelöst, wenn es mir oder jemand anderem gelingt, mindestens einen Input zu finden, bei dem eure Methode eine andere Rückgabe hat als meine. Andernfalls ist sie gelöst.

Zu guter Letzt noch ein paar Beispiele, mit denen ihr beiden Methoden (eure und meine) füttern könnt, um die gröbsten Schnitzer selbst zu finden.


private static String [] examples = new String [] {
"<beispiel key='value'>",
"<beispiel  key= value >",
"<BeiSpiel  Key= Value >",
"<beispiel  key= val>ue >",
"<beispiel  key ='val>ue'>",
"<beispiel  key ='val<ue'>",
"<beispiel> key ='value'>",
@"<
   beispiel  key
= value
>",
" <  beispiel   a     =      'a, b, c'       >       ",
"abc<beispiel key='value'>def",
"<beispiele key='value'>",
"<beispielkey=value>",
"<beispiel k,e,y='value'>",
"<beispiel : key='value'>",
"<beispiel key='value' nochirgendwas>",
"<beispiel 'key'=value>",
"<beispiel 'key'='value'>"
"<beispiel < key ='value'>>",
};

Viele Spaß und viel Erfolg!

herbivore

PS: Aufgrund eines Hinweises von dN!3L, habe ich mich entschlossen, die Bedingungen für eine korrekte Lösung etwas abzuschwächen: Wenn der input null ist, muss eure Methode nicht das gleiche tun wie meine. Meine wirft eine ArgumentNullException. Jede andere Exception, insbesondere eine NullReferenceException, ist auch ok. Exakt die gleiche Exceptions zu werfen wäre gar nicht möglich, weil im Stacktrace meiner das für euch "verbotene" Regex.Match auftaucht. 😃

@herbivore: Nachträglich einfach noch ein return true in die Referenzimplementierung einfügen, tztzt...

Folgende Methode gibt (für die gegebenen Beispiele) das gleiche wie der Referenzcode zurück:


public static bool GetTag2(String input,out String tag,out String key,out String value)
{
	for (int start = input.IndexOf('<');start>=0;start = input.IndexOf('<',start+1))
	{
		tag = key = value = "";

		int end = input.IndexOf('>',start);
		if (end>0)
		{
			string current = input.Substring(start+1,end-start-1).Trim();

			tag = current.Substring(0,Math.Min(current.Length,8));
			if (String.Compare(tag,"beispiel",true)==0)
			{
				if (current.Length>8 && !Char.IsWhiteSpace(current[8]))
					continue;

				if (tag.Length==current.Length)
					return true;

				int equalIndex = current.IndexOf('=');
				if (equalIndex>0)
				{
					key = current.Substring(8,equalIndex-8).Trim();
					value = current.Substring(equalIndex+1).Trim();

					if (key.All(c => (Char.ToLower(c)>='a' && Char.ToLower(c)<='z')))
					{
						if (value.StartsWith("'") && value.EndsWith("'"))
						{
							value = value.Substring(1,value.Length-2);
							if (!value.Contains("'"))
								return true;
						}
						else if (!value.Contains("'") && !value.Any(c => Char.IsWhiteSpace(c)))
							return true;
					}
				}
			}
		}
	}

	tag = key = value = "";
	return false;
}

EDIT: Code verkürzt.
EDIT2: Fehler beseitigt.
EDIT3: Den komplett richtigen Code gibt's hier.

Hallo dN!3L,

sieht schon mal nicht schlecht aus. Und durch die mehrfache Verwendung von Trim auch kürzer als ich dachte. Trotzdem bestätigt der Code mich in meiner Meinung, dass schwieriger zu erkennen und verstehen ist, was der ausprogrammierte Code macht als der Pattern (vorausgesetzt natürlich man kennt Regex). Und schwerer zu warten scheint solcher Code auch zu sein, wie mir aufgefallen ist. Wenn ich im Pattern "beispiel" durch "example" ersetze, ist der Fall gegessen. Du müsstest deine Indexberechungen anpassen (7 statt 8). Ok, das könnte man zwar durch eine Variable im wahrsten Sinne des Wortes variabel machen, aber vermutlich wird man an sowas bei ersten Anlauf oft nicht denken.

Wie dem aber auch sei, der Code ist zwar dicht dran, aber noch nicht ganz korrekt. Damit meine ich nicht, dass IsLetterOrDigit eine andere Zeichenmenge repräsentiert als das (zugegeben auch nachträglich geänderte) [a-z]. Das ist gebongt. Willst du selber suchen (du braucht nicht den ganzen Code neu zu posten, sondern nur die geänderte Zeile) oder (bitte per PM) einen Tipp?

Solange kann dir natürlich noch jemand anders mit seine eigenen Lösung zuvorkommen. 😃

herbivore

Und schwerer zu warten scheint solcher Code auch zu sein, wie mir aufgefallen ist. Wenn ich im Pattern "beispiel" durch "example" ersetze, ist der Fall gegessen. Du müsstest deine Indexberechungen anpassen (7 statt 8). Ok, das könnte man zwar durch eine Variable im wahrsten Sinne des Wortes variabel machen, aber vermutlich wird man an sowas bei ersten Anlauf oft nicht denken.

Die verwenden Konstanten sind allerdings "Opfer" meiner premature optimization (um Zeilen zu sparen). Im Normalfall hätte das auch gleich "im ersten Anlauf" genau so gemacht - und hätte mir auch den zusätzlichen Aufwand, die Buchstaben selbst zu zählen, erspart. 😃

Wie dem aber auch sei, der Code ist zwar dicht dran, aber noch nicht ganz korrekt. Damit meine ich nicht, dass IsLetterOrDigit eine andere Zeichenmenge repräsentiert als das (zugegeben auch nachträglich geänderte) [a-z]. Das ist gebongt.

Der Fall, der nicht ging, war <beispiel key= va lue >. Da wurde fälschlicherweise "va lue" als korrekt erkannt. Um das zu beheben, habe ich einfach in der viertletzten Codezeile ein && !value.Any(c => Char.IsWhiteSpace(c)) angefügt.
Um das [a-z] umzusetzen, habe ich key.All(c => Char.IsLetterOrDigit(c)) durch key.All(c => (Char.ToLower(c)>='a' && Char.ToLower(c)<='z')) ersetzt.

Trotzdem bestätigt der Code mich in meiner Meinung, dass schwieriger zu erkennen und verstehen ist, was der ausprogrammierte Code macht als der Pattern.

Naja, dein Vorteil ist, dass du das Pattern selbst geschrieben hast und somit besser "siehst", was gemacht wird. Bei der Nur-Stringoperationen-Variante bin wiederum ich unobjektiv, da der Code von mir ist. Soo kompliziert finde ich es nicht.
Wie dem auch sein: Die Nur-Stringoperationen-Lösung profitiert allerdings stark von einigen Besonderheiten des Patterns. So kann man z.B. davon ausgehen, dass eine geschlossene Klammer ">" immer das Ende des (potentiellen) Matches anzeigt (und nicht z.B. noch in value erlaubt sind). Ebenso gibt es klare Trenner für den Anfang (<) und zwischen Key und Value, wobei die Trenner innerhalb andere Elemente ebenso nicht vorkommen dürfen.

Hallo dN!3L,

ich habe leider im geänderten Code noch eine kleine Abweichung gefunden. Nochmal bei der Attributwerten ohne Anführungszeichen. Sollte aber auch nicht schwer zu beheben sein. Einen Tipp gibt es bei Bedarf wieder per PM. Jetzt will ich aber mal so fair sein, dich in Erwartung dieser letzten kleinen Fehlerbehebung schon zum Sieger zu küren.

Die verwenden Konstanten sind allerdings "Opfer" meiner premature optimization (um Zeilen zu sparen). Im Normalfall hätte das auch gleich "im ersten Anlauf" genau so gemacht

Für einen realistischen Vergleich wäre Code, der die spätere Wartung berücksichtigt, sicher besser gewesen. In der Praxis nützt es ja nichts zu sagen, hey, mein Code ist so wenig wie möglich länger als der Pattern, wenn der Code dadurch unnötig schwerer zu warten ist. In der Praxis wäre der Code also wohl noch ein bisschen länger.

Da hätte man - um den Preis einer zusätzlichen Anweisung - vermutlich auch die Bedingung in if (end>0) ... negiert und dann ein break gemacht, denn wenn keine schließende Klammern mehr gefunden wird, gibt es keinen Match, egal wieviel öffnende noch kommen.

Für die Aufgabe im Rahmen des Programmierspiels ist es natürlich legitim, Zeilen zu sparen, zumal ich ja selbst den Fokus auf die Zeilenanzahl gelegt habe. Anderseits lag mir auch ein realistischer Vergleich am Herzen. Der ist aber nach diesen Anmerkungen sicher möglich.

Naja, dein Vorteil ist, dass du das Pattern selbst geschrieben hast und somit besser "siehst", was gemacht wird. Bei der Nur-Stringoperationen-Variante bin wiederum ich unobjektiv, da der Code von mir ist. Soo kompliziert finde ich es nicht.

Natürlich ist es für einen realistischen Vergleich wichtig, dass jemand, der den Vergleich anstellt, weder den Pattern noch den ausprogrammierten Code geschrieben hat - aber genau das ist ja bei allen Lesern des Threads der Fall.

Natürlich ist dein Code nicht "soo kompliziert". Trotzdem bleibe ich bei meiner Behauptung, dass es im Vergleich zu einem Regex-Pattern schwerer zu erfassen ist, was ausprogrammierter Code macht, der das gleiche wie der Pattern tut. Jeder Leser kann sich anhand dieses Beispiel nun ein eigenes Urteil bilden - ausreichende Regex-Kenntnise vorausgesetzt.

Die Nur-Stringoperationen-Lösung profitiert allerdings stark von einigen Besonderheiten des Patterns.

Richtig, ich ärgere mich jetzt wirklich, dass ich in Attributwerten in Anführungsstrichen keine schließenden spitzen Klammern erlaubt habe. Ich denke, das hätte den Code nochmal wesentlich schwieriger gemacht. Anderseits ist es mir auch wieder recht, weil es ja einen Blick auf die schlechtere Wartbarkeit des ausprogrammieten Codes wirft, wenn eine kleine Änderung am Pattern zu einer großen Änderung am ausprogrammierten Code führt.

Ich überlasse es den Lesern als Aufgabe außer Konkurrenz, Code zu schreiben, der das gleiche tut, wie der obige Pattern, nur dass in '(?<value>[^'>]*)' die schließende spitze Klammer weggelassen wird, also '(?<value>[^']*)'. Ich vermute, diese kleine Änderung würde starken Einfluss auf den ausprogrammierten Code haben, ihn vielleicht sogar komplett umwerfen.

herbivore

So, mein aktueller Code. Ein Regex-"+" ist halt was anderes, als ein "*"...
Außerdem habe ich die magischen Konstanten ersetzt und das von herbivore vorgeschlagene break eingebaut. Wenn ich den Aufwand der ganzen Nacharbeiten noch mit dazurechne, sind reguläre Ausdrücke eindeutig einfacher erstellt und man findet Fehler schneller...


public static bool GetTag2(string input,out string tag,out string key,out string value)
{
	for (int start = input.IndexOf('<');start>=0;start = input.IndexOf('<',start+1))
	{
		tag = key = value = "";

		int end = input.IndexOf('>',start);
		if (end<0) break;
		string current = input.Substring(start+1,end-start-1).Trim();

		string tagLiteral = "beispiel";
		tag = current.Substring(0,Math.Min(current.Length,tagLiteral.Length));
		if (String.Compare(tag,tagLiteral,true)==0)
		{
			if (current.Length>tagLiteral.Length && !Char.IsWhiteSpace(current[tagLiteral.Length]))
				continue;

			if (tag.Length==current.Length)
				return true;

			int equalIndex = current.IndexOf('=');
			if (equalIndex>0)
			{
				key = current.Substring(tagLiteral.Length,equalIndex-tagLiteral.Length).Trim();
				value = current.Substring(equalIndex+1).Trim();

				if (key.All(c => (Char.ToLower(c)>='a' && Char.ToLower(c)<='z')))
				{
					if (value.StartsWith("'") && value.EndsWith("'"))
					{
						value = value.Substring(1,value.Length-2);
						if (!value.Contains("'"))
							return true;
					}
					else if (value.Length>=1 && !value.Contains("'") && !value.Any(c => Char.IsWhiteSpace(c)))
						return true;
				}
			}
		}
	}

	tag = key = value = "";
	return false;
}

Richtig, ich ärgere mich jetzt wirklich, dass ich in Attributwerten in Anführungsstrichen keine schließenden spitzen Klammern erlaubt habe. Ich denke, das hätte den Code nochmal wesentlich schwieriger gemacht. [...] Ich vermute, diese kleine Änderung würde starken Einfluss auf den ausprogrammierten Code haben, ihn vielleicht sogar komplett umwerfen.

Einfach nach dem string current = ... folgenden Block einfügen:


if (current.Count(c => c=='\'')==1)
{
	end = input.IndexOf('>',input.IndexOf('\'',end));
	current = input.Substring(start+1,end-start-1).Trim();
}

Zum Thema Lesbarkeit von Code vs. Pattern: Es vielen ja öfter die Worte "wer Regex lesen kann". Joshua Flanagan hat eine Fluent API entwickelt, mit der man Patterns für reguläre Ausdrücke erstellen kann. So kann z.B. das Pattern "\d{,3}" mithilfe von Pattern.With.Digit.Repeat.AtMost(3) oder das Pattern "[^\s]" mittels Pattern.With.NegatedSet(Pattern.With.WhiteSpace) erzeugen.

Nun wäre doch einmal interessant, ob der von herbivore verwendete reguläre Ausdruck auch etwas lesbarer erzeugt werden kann.


Erzeuge das [url]oben verwendete Pattern[/url] mithilfe der [url]Readable Regular Expressions API[/url]. Es muss nicht exakt so aussehen (kann es z.B. aufgrund der Leerzeichen auch gar nicht), aber es muss semantisch übereinstimmen. 
Bsp. kann folgendes Pattern mithilfe dieser API erzeugt werden: [tt]<\s*(?<tag>beispiel)(?:\s+(?<key>[a-z]+)\s*=\s*(?:('(?<value>[^'>]*)'|(?<value>[^'>\s]+))))?\s*>[/tt]

Um den Implementierungsaufwand etwas zu minimieren, habe ich ein VS-Projekt mit den nötigen Verweisen und einem Codegerüst angehängt.
Die Aufgabe sollte nicht allzu schwer zu lösen sein. Mit einigen Zeilenumbrüchen für Formatierungszwecke habe ich etwa 15 Zeilen benötigt.

dN!3L

Meine Lösung:

         public static string Pattern2
        {
            get
            {
                // TODO: Pattern fluent deklarieren
                return Pattern.With.Literal("<").WhiteSpace.Repeat.ZeroOrMore.NamedGroup("tag", Pattern.With.Literal("beispiel"))
                    .Group(
                    Pattern.With.WhiteSpace.Repeat.OneOrMore.NamedGroup("key", Pattern.With.Set(Pattern.With.Word).Repeat.OneOrMore)
                    .WhiteSpace.Repeat.ZeroOrMore.Literal("=").WhiteSpace.Repeat.ZeroOrMore
                     .Group(Pattern.With.Choice.Either(
                        Pattern.With.Literal("'").NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'>")).Repeat.ZeroOrMore).Literal("'")
                ,
                Pattern.With.NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'>").WhiteSpace).Repeat.OneOrMore)
                )
                ).Repeat.Optional).Repeat.Optional.WhiteSpace.Repeat.ZeroOrMore.Literal(">");

            }
        }

Die tests laufen alle durch, allerdings finde ich da den ganz normalen regulären ausdruck einfacher zu lesen

Das Pattern von pdelvo stimmt nicht komplett semantisch mit dem geforderten überein. So gibt beispielsweise Abweichungen bei den Eingaben <beispiel köy=value> (für die Attributschlüssel sind Umlaute nicht erlaubt) und <beispiel key=> (Attributwert entweder in Anführungszeichen oder mindestens ein Zeichen).

Hier ist meine Lösung, die das oben genannte Pattern <\s*(?<tag>beispiel)(?:\s+(?<key>[a-z]+)\s*=\s*(?:('(?<value>[^'>]*)'|(?<value>[^'>\s]+))))?\s*> erzeugt:


return Pattern.With
    .Literal("<").WhiteSpace.Repeat.ZeroOrMore
    .NamedGroup("tag",Pattern.With.Literal("beispiel"))
    .Phrase(Pattern.With
        .WhiteSpace.Repeat.OneOrMore
        .NamedGroup("key",Pattern.With.Set(Range.Of('a','z')).Repeat.OneOrMore)
        .WhiteSpace.Repeat.ZeroOrMore
        .Literal("=")
        .WhiteSpace.Repeat.ZeroOrMore
        .Phrase(Pattern.With.Choice.Either
        (
            Pattern.With.Literal("'").NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'").Literal(">")).Repeat.ZeroOrMore).Literal("'"),
            Pattern.With.NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'").Literal(">").WhiteSpace).Repeat.OneOrMore)
        ))
    ).Repeat.Optional
    .WhiteSpace.Repeat.ZeroOrMore
    .Literal(">");

Da sich pdelvo bisher noch nicht wieder gemeldet hat, steht es jedem frei, eine neue Aufgabe zu stellen.

da ich selbst einige nachmittage daran gesessen habe, und man im netz nicht viel dazu findet, bin ich gespannt wie ihr das löst:

es geht darum, termine in einem kalender (typischer office kalender z.b.) so anzuordnen, dass sie sich grafisch nicht überdecken, aber dennoch den vorhandenen platz sinnvoll ausnutzen. bild siehe anhang.

gegeben sei dazu jetzt folgende klasse, die einen termin darstellt:



class CTermin
{
    //wieviel Platz braucht der Termin im Kalender? Divider = 1/3 --> Termin.Width = 1/3 * Breite des Tages in Pixeln
    public double Divider { get; set; }

    //an welcher Stelle beginnt der Termin im Kalender? HorizontalIndex = 0 --> ganz am Anfang, HorizontalIndex = 1 --> an 2. Stelle
    public int HorizontalIndex { get; set; }

    //Start- und Endzeit 
    public DateTime StartTime { get; set; }
    public DateTime EndTime { get; set; }

    //Breite in Pixeln
    public int Width { get; set; }

    public CTermin(DateTime start, DateTime end)
    {
        StartTime = start;
        EndTime = end;
    }
}


sowie eine liste von terminen, die ihr selbst füllen könnt:


List<CTermin> termine = new List<CTermin>();

eure aufgabe ist es, eine funktion/methode zu schreiben, die diese liste so bearbeitet, dass die werte für Divider, HorizontalIndex und Width korrekt gesetzt werden, um diese termine anhand dieser angaben wie im bild unten zeichnen zu können.

(das schema mit Divider, HorizontalIndex und Width ist meine idee, ich denke wir bleiben für diese aufgabe dabei, denn so kann ich es am schnellsten überprüfen)

anforderungen, die schon aus dem bild hervorgehen:

  • termine dürfen sich nicht überlagern
  • je "früher" die startzeit, desto weiter links steht der termin
  • je länger die dauer des termins, desto weiter links steht der termin
  • der platz muss voll ausgenutzt werden (war für mich der schwerste part, habe ich selbst erst am wochenende fertig bekommen ^^)

die lösungen/werte für Divider, HorizontalIndex und Width für das beispiel im bild wären unter der annahme, dass die tagesbreite 100px ist wie folgt (meine zeichenroutine ermittelt automatisch eine "größte teilbare" tagesbreite für in diesem falle 3 termine nebeneinander --> 96px)

blau: 1/3, 0, 32
grün: 1/3, 1, 32
braun: 1/3, 2, 32
rot: 1/3, 2, 32
orange: 2/3, 1, 64
gelb: 1/1, 0, 96

bin gespannt 😃

(ich brauche mehr als 50 zeilen, aber ich bin mir sicher, dass mein code nicht der effizienteste ist.. ist über mehrere wochen gewachsen)

Na, da bin ich aber mal auf Lösungen gespannt. Mal schauen, ob mir eine clevere Idee kommt, wie man die Aufgabe lösen kann - vielleicht beim Joggen oder Duschen 😉

Edit: Ach ja, es wäre schön, wenn du ein paar Beispieldaten geben könntest, so dass man sich gleich auf die Problemlösung stürzen kann.

dann vielleicht direkt die daten für das beispiel im bild:

blau: 09:00 - 15:30 uhr
grün: 09:00 - 14:30 uhr
braun: 09:30 - 11:30 uhr
rot: 11:30 - 12:00 uhr
orange: 14:30 - 15:00 uhr
gelb: 15:30 - 16 uhr

breite eines tages: 96px (durch 3 teilbar für unser beispiel)



termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 15:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 14:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:30:00"), Convert.ToDateTime("16.02.2012 11:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 11:30:00"), Convert.ToDateTime("16.02.2012 12:00:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 14:30:00"), Convert.ToDateTime("16.02.2012 15:00:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 15:30:00"), Convert.ToDateTime("16.02.2012 16:00:00")));

EDIT:

nur zur erinnerung, es geht nicht darum, die zeichenroutine etc umzusetzen!
nur eine funktion, die die 3 werte Divider, HorizontalIndex und Width berechnet!

klasse CTermin wurde um ctor ergänzt