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

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

Mitglieder
» Liste / Suche
» Wer ist online?

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

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

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



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Okay, ich wäre nie auf die Idee gekommen, dass C# currying kann ;-)

Hier mal die Lösung:


 private static void Main(string[] args)
        {
            Func<int, int, int, int, int> Add = (a, b, c, d) => a + b + c + d;
            Console.WriteLine(Add(1,2,3,4));
            var tmp = Add.SomethingNice()(1)(2);
            Console.WriteLine(tmp(3)(4));
        }

        public static Func<T1, Func<T2, Func<T3, Func<T4, T5>>>>
            SomethingNice<T1,T2,T3,T4,T5> (this Func<T1,T2,T3,T4,T5> f)
        {
            return a => b => c => d => f(a, b, c, d);
        }
private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

Kann es :)

Aber die Möglichkeiten die sich in C# durch die Einbindung von Eigenschaften funktionaler Sprachen bieten, sind in der Tat recht unbekannt. Ne Suche hier im Forum danach liefert kein einziges Thema wo Currying mal behandelt wird. Nur einen Artikel wo das als Möglichkeit erwähnt wird, eine Einladung zu einem Usergroup Treffen in dem es als Feature von F# vorgestellt wird, und dann meine Frage hier im Thread ;)

Wie dem auch sei - du bist dran :)
Baka wa shinanakya naoranai.

Mein XING Profil.
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von talla
Durch die Antwort ist ja praktisch schon verraten das es natürlich in C# geht - ich hätte neben der Lösung aber auch noch den Namen der Technik ( aber bitte beides zusammen, nur die Nennung des Namens würde die Lösung dann durch suchen im Inet trivial machen)
Das Vorgehen nennt sich "Currying". Funktioniert in C# folgendermaßen:


using System;
public static class Program
{
	public static Func<A,Func<B,Func<C,Func<D,R>>>> SomethingNice<A,B,C,D,R>(this Func<A,B,C,D,R> f)
	{
		return a => b => c => d => f(a,b,c,d);
	}

	public static void Main(string[] args)
	{
		Func<int,int,int,int,int> add = (a,b,c,d) => a + b + c + d;
		
		var erg = add(1,2,3,4);
		var erg2 = add.SomethingNice()(1)(2)(3)(4);
		
		var tmp = add.SomethingNice()(1)(3);
		var erg3 = tmp(4)(2);
	}
}

EDIT: GRML! Zu langsam...

Gruß,
dN!3L
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Okay, da wir hier gerade so schön bei funktionaler Programmierung sind ist meine Aufgabe auch in diesem Bereich angesiedelt.

Es soll eine Erweiterung für die Klasse List<T> geschrieben werden, welche eine Methode FoldLeft bereitstellt. FoldLeft bekommt einen Anfangswert vom Typen T und eine Funktion übergeben. Die übergebene Funktion wird für jedes Element der Liste mit dem Ergebnis des vorherigen Aufrufs und dem aktuellen Element aufgerufen. Der erste Aufruf geschieht mit dem Anfangswert und dem Element, da dort ja noch kein Ergebnis vorhanden ist ;-)
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Corpsegrinder,

das war ja mal eine kleine, schöne Aufgabe. Hier meine Lösung. Damit daraus eine Erweiterungsmethode wird, müsste man wohl nur ein this an den Beginn der Parameterliste von FoldLeft setzen. Hier habe ich momentan nur C# 2.0, weshalb ich das nicht testen konnte.


public delegate T FoldFunc <T> (T accumulatedValue, T currentValue);

public static T FoldLeft <T> (List <T> list, T startValue, FoldFunc <T> foldFunc)
{
   T accumulatedValue = startValue;
   foreach (T currentValue in list) {
      accumulatedValue = foldFunc (accumulatedValue, currentValue);
   }
   return accumulatedValue;
}

herbivore
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Corpsegrinder
FoldLeft bekommt einen Anfangswert vom Typen T und eine Funktion übergeben. Die übergebene Funktion wird für jedes Element der Liste mit dem Ergebnis des vorherigen Aufrufs und dem aktuellen Element aufgerufen. Der erste Aufruf geschieht mit dem Anfangswert und dem Element, da dort ja noch kein Ergebnis vorhanden ist ;-)
Gibt's doch schon im Framework!?
IEnumerable.Aggregate-Methode

Moderationshinweis von herbivore (10.05.2010 - 11:15:44):

Lösungen zu den meisten der Aufgaben, die hier gestellt werden, gibt es schon irgendwie und irgendwo. Das ist kein KO-Kriterium für das Programmierspiel. Jeder Mitspieler ist aber mehr als gehalten eine eigene Lösung zu erstellen und nicht einfach eine fremde zu posten.

Als reine Information lass ich deinen Beitrag mal stehen.

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



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Alles klar herbivore, funktioniert super. Dann stell mal die nächste Aufgabe ;-)
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

dann kommt jetzt eine weitere Episode zum Thema, iterativ programmieren, was man üblicherweise rekursiv lösen würde.
Für die folgende Klasse Tree soll die innere Klasse Enumerator so implementiert werden, dass die Knoten des Baums von [TT]foreach (T t in root)[/TT] depth-first [URL]in-order[/URL] durchlaufen werden.

[LIST]
[*]Dabei dürfen keine rekursiven Methoden verwendet werden. 

[*]Entsprechend bringt die Verwendung von yield return auch keine Vorteile und sollte unterbleiben.

[*]Man darf sich allerdings den aktuellen Pfad (und etwaige Zusatzinformationen) in einem Stack<> merken (ganz ohne kommt man vermutlich nur aus, wenn die Tree-Klasse um eine Property Parent erweitert wird; eine solchermaßen erweiterte Klasse findet sich im folgenden Post).

[*] Andere Collections sollten nicht verwendet werden, also insbesondere keine List<>, in die schon im Konstruktor alle Knoten in der richtigen Reihenfolge gepackt werden.

[*]Der Enumerator darf ungeprüft davon ausgehen, dass der Baum während der Aufzählung nicht verändert wird.

[*]Der Enumerator darf ungeprüft davon ausgehen, dass der Baum wohlgeformt ist, also dass er keine Zyklen enthält und auf jeden Knoten im Baum (außer der Wurzel) nur von genau einem (Vater-)Knoten aus verwiesen wird.
[/LIST]


using System;
using System.Collections.Generic;

using IUntypedEnumerable = System.Collections.IEnumerable;
using IUntypedEnumerator = System.Collections.IEnumerator;

public class Tree <T> : IEnumerable <T>
{
   public Tree (T value)
   {
      _value = value;
   }

   private T        _value;
   private Tree <T> _left;
   private Tree <T> _right;

   public T Value
   {
      get { return _value; }
      set { _value = value; }
   }

   public Tree <T> Left
   {
      get { return _left; }
      set { _left = value; }
   }

   public Tree <T> Right
   {
      get { return _right; }
      set { _right = value; }
   }

   public IEnumerator <T> GetEnumerator ()
   {
      return new Enumerator (this);
   }

   IUntypedEnumerator IUntypedEnumerable.GetEnumerator ()
   {
      return GetEnumerator ();
   }

   private class Enumerator : IEnumerator <T>
   {
      //...
   }
}

herbivore
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

hier noch die Klasse Tree mit Parent-Property, für alle, die - was ich sehr begrüßen würde - ganz ohne Stack<> auskommen wollen (s. Aufgabenbeschreibung im vorigen Beitrag).

using System;
using System.Collections.Generic;
using System.Diagnostics;

using IUntypedEnumerable = System.Collections.IEnumerable;
using IUntypedEnumerator = System.Collections.IEnumerator;

public class Tree <T> : IEnumerable <T>
{
   public Tree (T value)
   {
      _value = value;
   }

   private T        _value;
   private Tree <T> _left;
   private Tree <T> _right;
   private Tree <T> _parent;


   public T Value
   {
      get { return _value; }
      set { _value = value; }
   }

   public Tree <T> Left
   {
      get { return _left; }
      set {
         if (_left == value) {
            return;
         }

         if (value == null) {
            Debug.Assert (_left != null);
            _left._parent = null;
            _left = null;
            return;
         }

         Debug.Assert (value != null);

         if (value._parent != null) {
            if (value._parent._left == value) {
               value._parent._left = null;
            } else {
               Debug.Assert (value._parent._right == value);
               value._parent._right = null;
            }
         }

         _left = value;
         value._parent = this;
      }
   }

   public Tree <T> Right
   {
      get { return _right; }
      set {
         if (_right == value) {
            return;
         }

         if (value == null) {
            Debug.Assert (_right != null);
            _right._parent = null;
            _right = null;
            return;
         }

         Debug.Assert (value != null);

         if (value._parent != null) {
            if (value._parent._left == value) {
               value._parent._left = null;
            } else {
               Debug.Assert (value._parent._right == value);
               value._parent._right = null;
            }
         }

         _right = value;
         value._parent = this;
      }
   }

   public Tree <T> Parent
   {
      get { return _parent; }
   }

   public IEnumerator <T> GetEnumerator ()
   {
      return new Enumerator (this);
   }

   IUntypedEnumerator IUntypedEnumerable.GetEnumerator ()
   {
      return GetEnumerator ();
   }

   private class Enumerator : IEnumerator <T>
   {
      //...
   }
}

herbivore
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 386

beantworten | zitieren | melden

Ich muss zugeben, ich hab mir den Algorithmus nicht selbst ausgedacht. Er ist bekannt als Morris Traversal.
Die Implementierung stammt jedoch komplett von mir.


private class Enumerator : IEnumerator<T>
        {
            private Tree<T> root;
            private Tree<T> current;
            private bool running;

            public Enumerator(Tree<T> root)
            {
                this.root = root;
                Reset();
            }

            #region IEnumerator<T> Members

            public T Current
            {
                get { return current.Value; }
            }

            #endregion

            #region IEnumerator Members

            object System.Collections.IEnumerator.Current
            {
                get { return this.Current; }
            }

            /// <summary>
            /// Morris Traversal
            /// </summary>
            /// <returns></returns>
            public bool MoveNext()
            {
                // skip this the first time
                if (running)
                {
                    current = current.Right;
                }
                else running = true;

                while (true)
                {
                    // if current is null, we are done.
                    if (current == null)
                        return false;

                    if (current.Left == null)
                    {
                        // Print Current if left is empty
                        return true;
                    }
                    else
                    {
                        // Find the inorder predecessor of current
                        Tree<T> pre;
                        pre = current.Left;
                        while (pre.Right != null && pre.Right != current)
                            pre = pre.Right;

                        // Make current as right child of its inorder predecessor
                        if (pre.Right == null)
                        {
                            pre.Right = current;
                            current = current.Left;
                        }
                        else
                        {
                            // Revert the changes to restore the original tree: fix the right child of predecssor
                            pre.Right = null;
                            
                            // Print Current
                            return true;
                        }
                    }
                }
            }

            public void Reset()
            {
                current = root;
                running = false;
            }

            #endregion

            #region IDisposable Members

            public void Dispose()
            {
            }

            #endregion
        }
private Nachricht | Beiträge des Benutzers

Moderationshinweis von herbivore (26.07.2012 - 08:53:29):

Das ist noch nicht die abschließende Lösung der Aufgabe, weiter geht es auf der nächsten Seite.

herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tarion,

ich ringe schwer mit mir!

Zwar würde die einfache foreach-Schleife aus der Aufgabe die geforderte Reihenfolge zeigen, aber während die Schleife läuft wird der Baum selbst ständig umgeordnet. Wenn man in der Schleife (lesend) auf den Baum zugreift, bekommt man also teilweise falsche Ergebnisse. Nun habe ich solche lesenden Zugriffe innerhalb der Schleife nicht explizit gefordert, aber denke, dass man so eine Forderung implizit voraussetzen kann.

Aber selbst wenn du mir da noch nicht zustimmen würdest: Ganz haarig wird die Sache, wenn man zwei oder mehr Enumeratoren verzahnt über den Baum laufen lassen würde, weil sie sich dann gegenseitig den Baum umordnen. Mehrere Enumeratoren verzahnt über eine Collection laufen zu lassen, sollte aber möglich sein, auch wenn das nicht explizit gefordert ist, denn sowas wäre ja schon bei einer gängigen Konstruktion wie

foreach (int n1 in root) {
   foreach (int n2 in root) {
   }
}

der Fall.

Ich bin geneigt die Lösung deswegen als falsch zu erklären, auch wenn sie gegen keine explizite Forderung in der Aufgabenstellung verstößt.

herbivore
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 386

beantworten | zitieren | melden

Das mit dem Leseproblem stimmt allerdings. Ich finde die Implementierung unabhängig von der Richtigkeit bezüglich der Aufgabenstellung dennoch sehr elegant, da sie fast ganz ohne Zusatzspeicher auskommt.

Dann stellt sich mir aber wieder die Frage ob es lösbar ist ohne sich für jeden Knoten eine Information zu speichern. (z.B. ob der Knoten schon besucht wurde)
Es ist ja gefordert keine Enumaration zu benutzten schließt das dann auch arrays aus?
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tarion,

in einem gewissen Sinne ist die Lösung ohne Frage elegant. Ihr großer Vorteil, kaum Zusatz-Informationen zu benötigen, wird allerdings durch denn entscheidenden Nachteil erkauft, den Baum selbst durch ständiges Umordnen als Informationsspeicher zu verwenden. Und das darf man eben nur machen, wenn man sicher ist, dass man den Baum für sich hat. Spätestens bei mehreren Enumeratoren ist das leider nicht mehr der Fall. Es freut mich, dass du an diesem Punkt mit mir übereinstimmst, obwohl das nicht explizit in der Aufgabe stand.

Wenn man die Klasse Tree mit der Parent-Property verwendet, kommt man mit ähnlich wenig Zusatzinfomationen aus wie Morris Traversal. Man muss sich also keine Zusatzinformationen pro Knoten merken, nicht mal für die Knoten des aktuellen Pfads. Ein Array ist insofern ebenfalls nicht nötig. In der verschärften Aufgabenstellung sind alle Collections ausgeschlossen.

Mal so überlegt: Wenn ich dir einen großen Baum zeigen würde und in diesem Baum auf einen bestimmten Knoten, der als bisher letzter aufgezählt wurde, dann kannst du mir doch auch von diesem Knoten ausgehend sagen, welcher der nächste Knoten sein muss, ohne dass du für alle schon besuchten Knoten Zusatzinformationen brauchst.

herbivore
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 386

beantworten | zitieren | melden

Sodala, hab ne Lösung.

Edit 1:
Lösung geht für beliebig große Bäume.
Meine Tests bezogen sich zwar nur aus Ausbalancierte Bäume, aber das sollte dann auch für jeden Anderen funktionieren.

Edit 2:
Hier die Lösung.
Ist auch für die Extremen Bäume: nur links oder nur Rechts Knoten getestet.


private class Enumerator : IEnumerator<T>
        {
            private Tree<T> root;
            private Tree<T> current;

            private Tree<T> last;
            private Tree<T> totalLast;

            public Enumerator(Tree<T> root)
            {
                this.root = root;
                Reset();
            }

            #region private Functions

            /// <summary>
            /// Try to move the current to the right direction.
            /// </summary>
            /// <returns>True if moved</returns>
            private bool MoveOne()
            {
                // Noch nichts ausgegeben -> Nach links gehen
                if (last == null)
                {
                    if (current.Left != null)
                    {
                        current = current.Left;
                        return true;
                    }
                    else
                    {
                        return false;
                    }
                }
                // Wir waren schon irgendwo -> Richtung bestimmen
                else
                {
                    // Hier waren wir grade -> nach rechts oder oben gehen
                    if (last == current)
                    {
                        // Nach rechts gehen wenn möglich
                        if (current.Right != null)
                        {
                            current = current.Right;
                            return true;
                        }
                        else // Sonst nach oben 
                        {
                            current = current.Parent;
                            return true;
                        }
                    }

                    // Wir kommen von rechts-unten (last is right of current) -> Weiter nach oben
                    if (IsRightOf(last, current))
                    {
                        Debug.Assert(current.Parent != null, "Error in the Tree");
                        current = current.Parent;
                        return true;
                    }

                    // Wir können nach Links und kommen von oben -> nach links gehen
                    if (current.Left != null && IsChildOf(current, last))
                    {
                        current = current.Left;
                        return true;
                    }

                    // Sonstige Fälle ohne Bewegung -> Ausgabe
                    // Z.b.
                    // Wir waren grade beim linken Kind. (last == current.Left)

                    return false;
                }
            }

            /// <summary>
            /// True if a is child of b
            /// </summary>
            /// <param name="a"></param>
            /// <param name="b"></param>
            /// <returns></returns>
            private bool IsChildOf(Tree<T> a, Tree<T> b)
            {
                // Suche von a nach oben bis b gefunde nwird
                Tree<T> finder = a;

                while (finder.Parent != null)
                {
                    finder = finder.Parent;
                    if (b == finder)
                    {
                        return true;
                    }
                }
                return false;
            }

            /// <summary>
            /// True if a is right of b
            /// </summary>
            /// <returns></returns>
            private bool IsRightOf(Tree<T> a, Tree<T> b)
            {
                Tree<T> finder = b;

                while (finder.Right != null)
                {
                    finder = finder.Right;
                    if (a == finder)
                    {
                        return true;
                    }
                }
                return false;
            }

            #endregion


            #region IEnumerator<T> & IEnumerator Members

            public T Current
            {
                get { return current.Value; }
            }

            object System.Collections.IEnumerator.Current
            {
                get { return this.Current; }
            }

            public bool MoveNext()
            {
                if (last == totalLast) return false;

                while (MoveOne()) ;

                last = current;
                return true;
            }

            public void Reset()
            {
                current = root;
                last = null;
                SetTotalLast();
            }

            private void SetTotalLast()
            {
                totalLast = root;
                while (totalLast.Right != null)
                {
                    totalLast = totalLast.Right;
                }
            }

            #endregion

            #region IDisposable Members

            public void Dispose()
            {
            }

            #endregion
        }
    
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Tarion am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Tarion,

es freut mich, dass du dich nochmal daran gemacht hast.

Es geht zwar um einiges kürzer (siehe meine Lösung), aber mir ist ein selbst entwickelter etwas umständlicher Algorithmus tausendmal lieber als eine reine Reimplementierung eines gefundenen Algorithmus, egal wie elegant dieser ist. :-)

Ich habe keine Fehler gefunden. Insofern ist die Aufgabe gelöst. Du bist mit der nächsten Aufgabe dran.

Hier meine Lösung. Das Grundprinzip ist folgendes: Wenn man irgendwo steht, schaut man, ob es einen rechten Teilbaum gibt. Wenn ja, geht man in diesen einen Schritt hinein und läuft von dort sofort nach ganz links unten. Wenn nein, läuft man solange es geht nach links oben und danach noch einen Schritt nach rechts oben. Es gibt also nur zwei Bewegungen, die beide eine einmal abgeknickte Linie bilden, bei der der eine Schenkel genau einen Schritt und der andere n Schritte lang ist. Beim abwärts Laufen, erst einmal nach rechts und dann n-mal nach links, beim aufwärts Laufen erst n-mal nach links und dann einmal nach rechts. Der Code enthält neben der Umsetzung dieses Grundprinzip zusätzlich noch eine besondere Behandlung für den ersten und den letzten Knoten.

private class Enumerator : IEnumerator <T>
{
   private bool             _eot;
   private Tree <T>         _root;
   private Tree <T>         _currentNode;

   public Enumerator (Tree <T> root)
   {
      _root = root;
      Reset ();
   }

   public T Current
   {
      get { return _currentNode == null ? default (T) : _currentNode.Value; }
   }

   Object IUntypedEnumerator.Current
   {
      get { return Current; } // nicht ganz akkurat
   }

   public bool MoveNext ()
   {
      // Wenn wir schon am Ende sind, ist nichts weiter zu tun
      if (_eot) { return false; }

      if (_currentNode == null) {
         // Bei der Wurzel beginnen
         _currentNode = _root;
      } else {
         // Wenn es keinen rechten Teilbaum gibt, müssen wir wieder nach oben
         if (_currentNode.Right == null) {
            while (_currentNode.Parent != null && _currentNode.Parent.Right == _currentNode) {
               // Solange wir von rechts unten kommen weiter nach oben
               _currentNode = _currentNode.Parent;
            }
            if (_currentNode.Parent == null) {
               // Wir sind wieder bei der Wurzel angekommen -> Ende
               _eot = true;
               return false;
            }
            // Wir kommen von links unten -> ein Schritt weiter nach oben
            _currentNode = _currentNode.Parent;
            return true;
         }
         // Da es einen rechten Teilbaum gibt, einen Schritt nach rechts unten
         _currentNode = _currentNode.Right;
      }

      // Wir kommen von oben und gehen solange nach links, wie möglich
      while (_currentNode.Left != null) {
         _currentNode = _currentNode.Left;
      }
      return true;
   }

   public void Reset ()
   {
      _currentNode = null;
      _eot         = false;
   }

   public void Dispose ()
   {
      // Nothing to do
   }
}

herbivore
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 386

beantworten | zitieren | melden

Ist jetzt nichts aufwändiges, aber ein nettes Spielzeug wenn es fertig ist:

Gebaut werden soll ein Russisch Roulette.
Es gibt einen Revolver mit 6 Schächten und einer Kugel.
Wer an der Reihe ist, muss entweder abdrücken oder die Trommel drehen und dann abdrücken.
Dann wird der Revolver weiter geben. Wer abdrückt und die Kugel erwischt, hat verloren.

Jetzt soll das Ganze für einen Spieler sein und der Gegenspieler ist Computergesteuert.
Ein zufälliger Spieler fängt an.

Besondere Anforderungen:
- Der Computer soll Logisch handeln, also nicht rein zufällig drehen / Schießen. Beispiel: Nach 5 Schüssel wäre es unklug nicht zu drehen.

Optional, nicht erforderlich für die Lösung:
- Man kann sich die Anzahl der Gegner selber aussuchen.
- Falls es nicht zu lang wird, kann auch eine WinForms Anwendung geschrieben werden.

Viel Spaß, ich freu mich auf das Programm ;)


Edit:
Ja natürlich muss man immer auch schießen. :P
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Tarion am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Tarion
Der Computer soll Logisch handeln, also nicht rein zufällig drehen / Schießen. Beispiel: Nach 5 Schüssel wäre es unklug nicht zu drehen.
Es ist generell unklug, bevor man dran ist, nicht noch einmal zu drehen. So ist die Wahrscheinlichkeit nicht zu überleben 1/6, andernfalls wäre sie sogar 1/5, 1/4, 1/3 usw.

Hier meine Lösung:


using System;
using System.Collections.Generic;
using System.Threading;

namespace RussianRoulette
{
	public enum Choice
	{
		PullTrigger,
		MixAndPullTrigger
	}

	public enum PullTriggerResult
	{
		Shot,
		Fail
	}

	public abstract class Player
	{
		public string Name { get; set; }
		public abstract Choice GetChoice();
	}

	public class HumanPlayer : Player
	{
		public override Choice GetChoice()
		{
			Console.Write(this.Name+", möchtest du vor dem Abdrücken noch einmal die Trommel drehen (j/n)? ");
			char key = Console.ReadKey().KeyChar;
			Console.WriteLine();
			return (key=='j') ? Choice.MixAndPullTrigger : Choice.PullTrigger;
		}		
	}

	public class ComputerPlayer : Player
	{
		public override Choice GetChoice()
		{
			return Choice.MixAndPullTrigger;
		}
	}

	public class Revolver
	{
		private Random random = new Random();
		private int roundPosition;

		public void Mix()
		{
			this.roundPosition = random.Next(6)+1;
		}

		public PullTriggerResult PullTrigger()
		{
			return (--this.roundPosition==0) ? PullTriggerResult.Shot : PullTriggerResult.Fail;			
		}
	}

	public class Program
	{
		public static void Main()
		{
			List<Player> players = Program.GetPlayers();
			if (players.Count>0)
			{
				Console.WriteLine("Das Spiel beginnt:");
				Program.PlayGame(players);
				Console.WriteLine(players[0].Name+" hat das Spiel gewonnen.");
			}
			Console.ReadLine();
		}

		private static void PlayGame(List<Player> players)
		{
			Revolver revolver = new Revolver();
			revolver.Mix();
			int i = new Random().Next(players.Count);
			while (players.Count>1)
			{
				Console.WriteLine();
				Player currentPlayer = players[i];
				if (currentPlayer.GetChoice()==Choice.MixAndPullTrigger)
				{
					Console.WriteLine(currentPlayer.Name+" Dreht die Trommel.");
					revolver.Mix();
				}
				Thread.Sleep(1000);
				Console.WriteLine(currentPlayer.Name+" drückt ab und...");
				Thread.Sleep(1000);
				if (revolver.PullTrigger()== PullTriggerResult.Shot)
				{
					Console.WriteLine("... - PENG - spielt nicht mehr mit.");
					players.RemoveAt(i--);
				}
				else
					Console.WriteLine("...ist nochmal davon gekommen.");

				if (++i==players.Count)
					i = 0;
				Thread.Sleep(2000);
			}
		}
		
		private static List<Player> GetPlayers()
		{
			List<Player> result = new List<Player>();
			Console.WriteLine("Spieler wählen: 'h' für menschlichen Spieler; 'c' für Computer; sonstiges: Spiel beginnt.");
			while (true)
			{
				string playerHint = "Spieler "+(result.Count+1);
				Console.Write(playerHint+": ");
				char key = Console.ReadKey().KeyChar;
				if (key=='h')
				{
					Console.Write(" Name? ");
					result.Add(new HumanPlayer() { Name = Console.ReadLine() });
				}
				else if (key=='c')
				{
					Console.WriteLine(" Spieler "+playerHint);
					result.Add(new ComputerPlayer() { Name = playerHint });
				}
				else
					break;
			}
			return result;
		}
	}
}

Gruß,
dN!3L
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 386

beantworten | zitieren | melden

Sieht gut aus. Die Möglichkeit ein neues Spiel zu starten ohne alles neu eingeben zu müssen / das programm neu starten zu müssen wäre noch schön, aber war auch nicht explizit verlangt.

Schönes Spiel für zwischendurch ;)

Dann darfst du jetzt.
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Gegeben sei eine Auflistung natürlicher Zahlen. Diese Zahlen sollen nun so sortiert werden, dass jede Zahl den Abstand zu ihrem Zwilling darstellt. D.h., alle Einsen müssen nebeneinander stehen, zwischen zwei Zweien muss eine Zahl stehen, zwischen zwei Dreien müssen zwei Zahlen stehen.

Beispiel: Gegeben sei die Menge { 1,1,2,2,3,3,4,4 }. Eine der (sechs möglichen) Lösungen ist die Folge (1,1,4,2,3,2,4,3).

Schreibe eine Methode, die als Parameter eine Auflistung von natürlichen Zahlen erhält und eine Auflistung aller möglichen Folgen mit o.g. Sortierung (falls solche existieren) zurück gibt.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

die Aufgabe von dN!3L ist nicht schlecht und durchaus lösbar. Ich würde mich freuen, wenn ihr euch mal an die Lösung macht und die Ergebnisse hier postet.

Da dN!3L keine Vorgaben bezüglich der Performance gemacht hat, seid ihr in meinen Augen nicht gezwungen, einen möglichst effizienten Algorithmus abzuliefern.

herbivore
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo dN!3L, hallo zusammen,

nachdem sich keiner gefunden hat, der die Aufgabe gelöst hat, habe ich mich mal erbarmt. Eigentlich schade, denn die Aufgabe wäre sicher für viele eine gute Übung gewesen. Und so schwer war es nun auch nicht. Der Aufwand die Eingabeliste in eine praktikablere SortedList zu konvertieren, die als Keys die natürlichen Zahlen und als Values deren Anzahl enthält, ist fast größer als der eigentlichen rekursive Algorithmus zum Finden der Kombinationen, der auch keine Klippe darstellt, wenn man Snippets wie [Snippet] Alle Kombinationen von n Elementen (rekursiv) oder Anzahl und Berechnung möglicher Kombinationen und Permutationen als gedankliche Vorlage verwendet.


using System;
using System.Collections.Generic;
using System.Linq;

static class App
{
   public static void Main (string [] astrArg)
   {
      List <List <int>> listResults = SiblingSort (new List <int> { 1, 1, 2, 2, 3, 3, 4, 4 });
      foreach (List <int> list in listResults) {
         Console.Write ("{ ");
         if (list.Count > 0) {
            foreach (int i in list.Take (list.Count - 1)) {
               Console.Write ("{0}, ", i);
            }
            Console.Write ("{0} ", list [list.Count - 1]);
         }
         Console.WriteLine ("}");
      }
   }

   public static List <List <int>> SiblingSort (List <int> listInput)
   {
      List <List <int>> listResults = new List <List <int>> ();

      if (listInput.Count == 0) {
         listResults.Add (new List <int> ());
         return listResults;
      }

      listInput.Sort ();

      if (listInput [0] ≤ 0) {
         return listResults;
      }

      SortedList <int, int> slistInput = new SortedList <int, int> ();
      int prevValue = listInput [0];
      int count = 0;
      foreach (int i in listInput) {
         if (i == prevValue) {
            ++count;
            continue;
         }
         slistInput [prevValue] = count;
         prevValue = i;
         count = 1;
      }
      slistInput [prevValue] = count;

      SiblingSort (listResults, slistInput,
                   new HashSet <int> (), new int [listInput.Count]);

      return listResults;
   }

   private static void SiblingSort (List <List <int>>     listResults,
                                    SortedList <int, int> slistInput,
                                    HashSet <int>         usedNumbers,
                                    int []                workingArea)
   {
      foreach (KeyValuePair <int, int> kvp in slistInput) {

         if (usedNumbers.Contains (kvp.Key)) {
            continue;
         }

         int firstFreeIndex = Array.IndexOf (workingArea, 0);
         bool fits = true;

         for (int i = 0; i < kvp.Value; ++i) {
            int currIndex = firstFreeIndex + i * kvp.Key;
            if (currIndex ≥ workingArea.Length || workingArea [currIndex] != 0) {
               fits = false;
               break;
            }
            workingArea [currIndex] = kvp.Key;
         }

         if (fits) {
            if (usedNumbers.Count + 1 ≥ slistInput.Count) {
               listResults.Add (new List <int> (workingArea));
            } else {
               usedNumbers.Add (kvp.Key);
               SiblingSort (listResults, slistInput, usedNumbers, workingArea);
               usedNumbers.Remove (kvp.Key);
            }
         }

         for (int i = 0; i < kvp.Value; ++i) {
            int currIndex = firstFreeIndex + i * kvp.Key;
            if (currIndex ≥ workingArea.Length || workingArea [currIndex] != kvp.Key) {
               break;
            }
            workingArea [currIndex] = 0;
         }
      }
   }
}

herbivore
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Hallo herbivore,

wirklich interessante Lösung. Soweit ich gesehen habe und bis auf den Schönheitsfehler, dass du die Ergebnisse als Menge statt als Folge formatierst, würde ich sagen, dass deine Lösung korrekt ist.

Beste Grüße,
dN!3L
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo dN!3L,

Zitat
und bis auf den Schönheitsfehler, dass du die Ergebnisse als Menge statt als Folge formatierst
hehe, das ist keine Formatierung als Menge, sondern als C#-Listensyntax (Stichwort: Array-Initialisierer). :-) Abgesehen ist die Ausgabe nur eine Dreingabe und war in der Aufgabe nicht gefordert. :-) Und wenn wir schon pingelig sind, dann hätte es in der Aufgabenstellung auch "Gegeben sei die Multimenge { 1,1,2,2,3,3,4,4 }" heißen müssen. :-) Ok, genug der Spitzfindigkeiten.



Hallo zusammen,
die neue Ausgabe besteht darin, eine Methode zu schreiben, die ein IEnumerable <int> als Parameter bekommt und einen String zurückliefert, wobei der String die Folge der Elemente entsprechend dieser Regeln möglichst kompakt repräsentiert:

[LIST]
[*]Teilfolgen von drei oder mehr zusammenhängenden Elementen sollen nur durch deren erstes und deren letztes Element - getrennt von einem Bindestrich - dargestellt werden. Dahinter soll in runden Klammern und getrennt durch ein Leerzeichen die Länge der Teilfolge angegeben werden. Mit zusammenhängend ist eine möglichst lange Teilfolge gemeint, in der für alle Paare von aufeinanderfolgenden Elementen gilt, dass der zweite Wert gleich dem ersten Wert ist oder der zweite Wert um eins größer ist als der erste. Die Teilfolge 7,8,8,9,10 wäre also zusammenhängend und würde als "7-10 (5)" dargestellt werden. 

[*]Elemente, die nicht mit anderen Elementen zusammenhängen, sollen einzeln dargestellt werden. Die Teilfolge 1,3,2 ist nicht zusammenhängend und würde also als "1, 3, 2" dargestellt werden.

[*]Hängen genau zwei Elemente zusammen, so sollen diese durch ein Plus getrennt dargestellt werden. Die Teilfolge 7,8 würde also als "7+8" dargestellt.

[*]Alle sich so ergebenden Teile sollen durch ein Komma gefolgt von einem Leerzeichen getrennt dargestellt werden.

[*]Der gesamte String soll mit einer runden Klammer auf beginnen und mit einer runden Klammer zu enden.

[*]Leerzeichen sollen in dem String nur genau da erscheinen, wo die Regeln dies explizit angegeben.
[/LIST]

Beispiel: 1,2,4,5,6,6,7,6,5,1,0,-1 wird zu "(1+2, 4-7 (5), 6, 5, 1, 0, -1)"
Optionale Zusatzaufgabe: Wer möchte, kann eine zweite Methode schreiben oder die erste mit einem zusätzlichen boolschen Parameter ausstatten, so dass Teilfolgen zusätzlich auch dann als zusammenhängend betrachten, wenn in ihnen für alle Paare von aufeinanderfolgenden Elementen gilt, dass der zweite Wert gleich dem ersten Wert ist oder der zweite Wert um eins [I]kleiner[/I] ist als der erste.

Das Beispiel 1,2,4,5,6,6,7,6,5,1,0,-1 würde dann zu "(1+2, 4-7 (5), 6+5, 1--1 (3))".

Es gilt die zusätzliche Regel, dass von links beginnend immer möglichst lange Teilfolgen zusammengefasst werden. "(1+2, 4-6 (4), 7-5 (3), 1--1 (3))" wäre also keine korrekte Lösung. Da Teilfolgen in sich nur aufsteigend oder nur absteigend sein sollen, wäre "(1+2, 4-5 (7), 1--1 (3))" auch keine korrekte Lösung.

Viel Spaß!

herbivore
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

tada:

    public class Carnivore
    {
        private const char separator = ',';
        private const char open = '(';
        private const char close = ')';
        private const char space = ' ';
        private const char plus = '+';
        private const char minus = '-';

        public static string Herbivore(IEnumerable <int> input)
        {
            StringBuilder result = new StringBuilder();
            result.Append(open);

            int[] previous = {int.MaxValue};
            int[] sequencecount = {0};

            Action closeSequence = () =>
                                       {
                                           if (sequencecount[0] == 2)
                                           {
                                               result.Append(plus);
                                               result.Append(previous[0]);
                                           }
                                           else if (sequencecount[0] > 2)
                                           {
                                               result.Append(minus);
                                               result.Append(previous[0]);
                                               result.Append(space);
                                               result.Append(open);
                                               result.Append(sequencecount[0]);
                                               result.Append(close);
                                           }
                                       };

            foreach (int current in input)
            {
                // sequencebreak
                if ((previous[0] + 1 != current && current != previous[0]) || sequencecount[0] == 0)
                {
                    closeSequence();
                    // the current is the beginning of a new sequence
                    if (result.Length != 1)
                    {
                        result.Append(separator);
                        result.Append(space);
                    }
                    result.Append(current);
                    sequencecount[0] = 1;
                }
                else // sequence proceed
                {
                    sequencecount[0]++;
                }
                previous[0] = current;
            }
            closeSequence();
            result.Append(close);
            return result.ToString();
        }
    }
anmerkung: ohne zusatzaufgabe.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal am .
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo JAck30lena,

abgesehen von dem verschmerzbaren Wrap-Around (bei /unchecked oder Overflow bei /checked) bei

Carnivore.Herbivore (new int [] { int.MaxValue, int.MinValue })

ist die Lösung meiner Prüfung nach korrekt.

Die Lösung mit dem Lambda-Ausdruck gefällt mir gut, auch wenn es mit int? noch etwas eleganter als mit int[] gegangen wäre.

Du bist dran!

herbivore
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

vielen dank herbivore :-)

hier die neue aufgabe:
ergänze die methode, damit sie folgende regeln auf den parameter "input" anwendet:
1. Eine tote Zelle mit genau drei lebenden Nachbarn wird in der Folgegeneration neu geboren.
2. Lebende Zellen mit weniger als zwei lebenden Nachbarn sterben in der Folgegeneration an Einsamkeit.
3. Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt in der Folgegeneration lebend.
4. Lebende Zellen mit mehr als drei lebenden Nachbarn sterben in der Folgegeneration an Überbevölkerung.

definitionen: 
0 = leeres feld
# = lebende zelle
+ = tote zelle

[CSHARP]    public class SpielDesLebens
    {
        private event EventHandler<SpielfeldEventArgs> EpochCompleted;

        /// <summary>
        /// wird von extern aufgerufen
        /// </summary>
        /// <param name="input">das spielfeld</param>
        /// <param name="epochen">die anzahl der iterationen</param>
        public void Run(char[,] input, int epochen)
        {
            for (int currentEpoch = 0; currentEpoch < epochen; currentEpoch++)
            {
                // hier dein code

                // und das hier ist dann optional für die ausgabe
                EpochCompleted(this, new SpielfeldEventArgs {Spielfeld = input});
            }
        }

        public class SpielfeldEventArgs : EventArgs
        {
            public char[,] Spielfeld { get; set; }
        }
    }[/CSHARP]

optional:
erstelle eine schöne ausgabe für die konsole, die das spielfeld visualisiert und wo man ohne zutun in einem festen intervall die epochen visualisiert bekommt.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal am .
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo JAck30lena,

2 wichtige Fragen dazu:
- gelten diagonal angrenzende Felder auch Nachbarn?
- wenn nach einem Turnus eine Zelle stirbt, aber wenn sie noch leben würde, wäre es das Todeskriterium für eine Nachbarzelle, wie ist dieser Fall zu handhaben? Wird also ein Snapshot ausgewertet oder sterben die Zellen sequenziell und wer zuerst tot ist beeinflusst den Rest nicht mehr (bzw. wie eine tote Zelle)?

Gruß, MarsStein

EDIT: OK Frage 2 hat sich erledigt, es geht ja immer um die Folgegeneration, sollte mal vorher nachdenken...
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo MarsStein,

ich bin zwar nicht JAck30lena, aber die Aufgabe basiert ja auf Conways Spiel des Lebens. Deshalb ist davon auszugehen, dass alle acht Nachbarn eines Felds betrachtet werden.

herbivore
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,

is jetzt nix besonderes, hab einfach durchiteriert.
Ich bin auch mal davon ausgegeangen dass leere Felder besetzt werden wie tote Zellen in Regel Nr.1

Das müsste es tun:

  public class SpielDesLebens
  {
    private event EventHandler<SpielfeldEventArgs> EpochCompleted;

    public int RowCount{ get; set;}
    public int ColCount{ get; set;}

    /// <summary>
    /// wird von extern aufgerufen
    /// </summary>
    /// <param name="input">das spielfeld</param>
    /// <param name="epochen">die anzahl der iterationen</param>
    public void Run(char[,] input, int epochen)
    {
      RowCount = input.GetLength(0);
      ColCount = input.GetLength(1);
      EpochCompleted(this, new SpielfeldEventArgs {Spielfeld = input});
      for (int currentEpoch = 0; currentEpoch < epochen; currentEpoch++)
      {
        // hier dein code
        int livingNeighbours = 0;
        char[,] epochResult = new char[RowCount, ColCount];
        char state;
        for(int row = 0; row < RowCount; row++)
        {
          for(int col = 0; col < ColCount; col++)
          {
            livingNeighbours = 0;
            for(int rowCheck = row - 1; rowCheck < row + 2; rowCheck++)
            {
              for(int colCheck = col - 1; colCheck < col + 2; colCheck++)
              {
                if((rowCheck != row || colCheck != col) && 
                   (rowCheck ≥ 0) && (rowCheck < RowCount) &&
                   (colCheck ≥ 0) && (colCheck < ColCount) &&
                   (input[rowCheck,colCheck] == '#'))
                {
                  livingNeighbours ++;
                }
              }
            }
            state = input[row,col];
            switch(state)
            {
              case '#':
                if((livingNeighbours < 2) || (livingNeighbours > 3))
                {
                  state = '+';
                }
              break;
              case '0':
              case '+':
                if(livingNeighbours == 3)
                {
                  state = '#';
                }
                else
                {
                  state = '0';
                }
                break;
            }
            epochResult[row,col] = state;
          }
        }
        input = epochResult;
        // und das hier ist dann optional für die ausgabe
        Thread.Sleep(500);
        EpochCompleted(this, new SpielfeldEventArgs {Spielfeld = input});
      }
    }

    public class SpielfeldEventArgs : EventArgs
    {
        public char[,] Spielfeld { get; set; }
    }
    public static void Main()
    {
      char[,] input = new char[,]{ {'0','0','#','#','0','0','0','0','0','0'},
                                 {'0','#','0','#','0','0','0','#','0','#'},
                                 {'0','0','#','0','0','#','#','0','0','0'},
                                 {'0','#','0','#','#','#','0','#','0','#'},
                                 {'0','0','#','#','0','#','0','0','0','#'},
                                 {'0','0','0','0','#','#','#','#','0','0'},
                                 {'0','#','0','0','0','0','0','#','0','0'},
                                 {'0','#','0','#','#','0','0','0','#','0'},
                                 {'0','0','0','0','0','#','0','#','0','0'},
                                 {'0','#','0','0','#','0','0','0','0','0'} };
      SpielDesLebens spiel = new SpielDesLebens();
      spiel.EpochCompleted += (s,args) => 
      {
        Console.Clear();
        for(int row = 0; row < spiel.RowCount; row++)
        {
          for(int col = 0; col < spiel.ColCount; col++)
          {
            Console.Write(args.Spielfeld[row,col]);
          }
          Console.WriteLine();
        }
      };
      spiel.Run(input, 25);
      Console.Read();
      
    }
  }
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

schaut gut aus :-)
und meine tests tuns ;-)

du bist dran.