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);
}
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.
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
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 😉
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
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
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.
Alles klar herbivore, funktioniert super. Dann stell mal die nächste Aufgabe 😉
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
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
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
}
Das ist noch nicht die abschließende Lösung der Aufgabe, weiter geht es auf der nächsten Seite.
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
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?
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
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
}
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
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:
Optional, nicht erforderlich für die Lösung:
Viel Spaß, ich freu mich auf das Programm 😉
Edit:
Ja natürlich muss man immer auch schießen. 😛
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
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.
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
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
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
Hallo dN!3L,
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 _Multi_menge { 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
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.
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
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.
Hallo JAck30lena,
2 wichtige Fragen dazu:
Gruß, MarsStein
EDIT: OK Frage 2 hat sich erledigt, es geht ja immer um die Folgegeneration, sollte mal vorher nachdenken...
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
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
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();
}
}
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Hallo,
bleiben wir mit der nächsten Aufgabe mal beim Thema char[ , ] 🙂
Gegeben sei folgende Methodensignatur:
int FindRoute(char[,])
Implementiert die Methode so, daß ein Weg aus einem übergebenen Labyrinth gefunden wird. Dabei gilt:
'#': Wand
' ': möglicher Weg
Füllt den gefundenen Weg im übergebenen Array mit '+'-Zeichen aus.
Edit: Rückgabewert soll die Länge des gefundenen Weges sein.
Ihr könnt außerdem von folgenden Startbedingungen ausgehen:
Das Labyrinth ist immer vollständig mit einer Wand umrahmt, die eine Startöffnung in der ersten Zeile und einer Zielöffnung in der letzten Zeile aufweist. Dabei existiert mindestens ein Weg vom Start zum Ziel.
Es muss nicht der kürzeste Weg gefunden werden, bei mehreren Möglichkeiten reicht es, eine davon zu finden.
Eine Ausgabe auf der Konsole ist auch in dieser Aufgabe optional.
Beispiel:
################+#############
# # # ### #+# # #
# # # ######+# # ####### #
# # #####++++++# # # # #
# # # +###### # ##### # #
# # # # # #+# # # #
# # # # # #+###### ##### # # #
# # # # # #++++++# #+++# # # #
# # # # # ######+# #+#+##### #
# # # # ### # #+# #+#+ #
# # # # # #+++++#+## ####
# ### ######## #######+# #
# # +# # ###
# # ##################+# # # #
# # #++++++++++++++++++# # # #
# # #+################## # # #
# # #+# #
#####+########################
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Hallo..
private static int FindRoute(char[,] map)
{
for (int column = 0; column < map.GetLength(1); column++)
{
int wayLenght = GetWayLength(map, 0, column, 1);
if (wayLenght > 0)
return wayLenght;
}
return 0;
}
private static int GetWayLength(char[,] map, int line, int column, int wayLength)
{
//Oberer Rand überschritten
if (line == -1)
return -1;
//Linker Rand überschritten
if (column == -1)
return -1;
//Rechter Rand überschritten
if (column >= map.GetLength(1))
return -1;
if (map[line, column] == ' ')
{
map[line, column] = '+';
if (line + 1 == map.GetLength(0))
//Auf der letzten Zeile angelangt
return wayLength;
else
{
int rightNeighbor = GetWayLength(map, line, column + 1, wayLength + 1);
int bottomNeighbor = GetWayLength(map, line + 1, column, wayLength + 1);
int leftNeighbor = GetWayLength(map, line, column - 1, wayLength + 1);
int topNeighbor = GetWayLength(map, line - 1, column, wayLength + 1);
if (rightNeighbor > 0)
return rightNeighbor;
if (bottomNeighbor > 0)
return bottomNeighbor;
if (leftNeighbor > 0)
return leftNeighbor;
if (topNeighbor > 0)
return topNeighbor;
else
{
//Sackgasse
//Bisher gegangener Weg löschen bzw. aktuelle Position wieder löschen
map[line, column] = ' ';
return -1;
}
}
}
else
{
return -1;
}
}
Wenn es zwei Wege gibt, werden zwar beide eingezeichnet, die Länge wird allerdings nur von einem zurückgegeben.
Gruss
using Skill
Hallo edsplash,
Wenn es zwei Wege gibt, werden zwar beide eingezeichnet
Nicht wenn 2 Wege zum selben Ausgang führen. Kann auch eigentlich nicht, weil nach dem ersten Fund der Ausgang blockiert ist.
Deine Lösung findet aber problemlos mehrere Ausgänge 😁
Die Kriterien der Aufgabenstellung sind also aus meiner Sicht erfüllt 👍
Damit wärst Du dann dran.
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Hallo Zusammen
Hier die neue Aufgabe:
Es geht um die Berechnung von Pi mit Hilfe des Monte Carlo Algorithmus.
Zu implementieren ist folgendes Interface:
interface IMonteCarloPi
{
int CircleRadius { get; set; }
double Calculate(int iterations);
}
Die Methode Calculate berechnet Pi. Der Parameter iterations gibt an wie viel mal iteriert werden soll. Das Property CircleRadius ist dazu gedacht, die Genauigkeit zu erhöhen: Statt mit dem Einheitskreis zu arbeiten (Radius = 1) kann man einen grösseren Radius einstellen und so ein genaueres Resultat erhalten.
Gruss
using Skill
public class MonteCarloPI : IMonteCarloPi
{
Random random = new Random();
int m_Radius = 0;
public int CircleRadius
{
get
{
return m_Radius;
}
set
{
m_Radius = value;
}
}
public double Calculate(int iterations)
{
double x = 0, y = 0;
int unter = 0;
for (int i = 0; i < iterations; i++)
{
x = random.NextDouble()+ random.Next(0,m_Radius);
y = random.NextDouble() + random.Next(0, m_Radius);
if(((x*x)+(y*y))<=(long)m_Radius*m_Radius))
unter++;
}
return (((double)unter / iterations) * 4);
}
}
war aber bestimmt anders gedacht oder?^^
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Erm nö, eigentlich nicht 😉
Nur scheint die Berechnung bei grossen Zahlen für CircleRadius zunehmend nicht mehr zu stimmen. Verwendet man z.b. int.MaxValue gibt es 0.
using Skill
Hallo edsplash,
wieso soll eigentlich die Berechnung mit einem größeren Radius genauer sein als mit 1?
Die Zufallszahlen werden ja ohnehin über NextDouble() gezogen und die Multiplikation mit einem int erhöht ja nicht die "Auflösung"...
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Hallo MarsStein
Wenn man es einfach mit dieser Zahl multipliziert wird das natürlich nichts. Man könnte aber z.b. Next(0, CircleRadius) verwenden: Da wird das Ergebnis natürlich zunehmend ungenau, wenn CircleRadius kleiner wird.
An und für sich ist der Double allerdings genauer als ein Int32. Ich könnte mir aber vorstellen, dass die Operation mit Ganzzahlen schneller geht als mit Gleitkommazahlen, getestet habe ich das allerdings nicht.
Gruss
using Skill
zählt meine lösung oder wärs besser wenn man ne lösung für alle zahlen entwickelt?^^
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Ich hätte eigentlich ganz gerne noch eine komplette Lösung 😉
Du darfst Dir aber gerne bereits eine neue Aufgabe überlegen.
using Skill
so.. hab den radius² auf long gecastet.. jetzt kann man auch int.MaxValue nutzen 😉
neue aufgabe
Schreiben Sie ein Programm, das mit Hilfe von Backtracking eine gültige Lösung für beliebige Sudoku ermittelt, falls eine solche existiert. Die Lösung kann direkt in das Sudoku eingetragen werden.
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Halllo prakti08,
ich will ja kein Spielverderber sein, aber
random.Next(0,m_Radius-1)
//und
(long)m_Radius*m_Radius
hier machst Du - abgesehen davon, daß Radius 1 nicht mehr funktioniert, auch noch den systematischen Fehler, die Koordinaten mit (m_Radius-1) zu ermitteln und den Abstand mit (m_Radius) zu prüfen
Da der zweite Parameter von Rand.Next() bereits exklusiv ist, kannst Du dir die -1 aber auch sparen.
Genau genommen müsste IMHO da sogar eine +1 hin (eben wegen exklusiv)...
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
warum sollte 1 nicht funktionieren?
selbst wenn der radius 1 ist bekommt man ne zahl zwischen 0 und 1 als zufallszahl..
wegen nextDouble
das exklusiv habe ich überlesen.. hab das -1 weggemacht..
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Hallo
Bei int.MaxValue kommt immer noch 0 raus. Es geht ja nicht darum, ob int.MaxValue rein passt, sondern darum, ob die Genauigkeit mit grösseren Werten für CircleRadius erhöht wird. Und das ist momentan so nicht gegeben.
Gruss
using Skill
...
seltsam das es bei mir funktioniert?!
siehe Anhang
habe die variablen iteration und radius in der überwachung.
habe einige minuten gewartet und das war das ergebnis!
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Hm.. komisch! Muss mir das morgen nochmal anschauen.
Erachte die Aufgabe aber als gelöst 😉
using Skill
da ich drauf angesprochen wurde und meine aufgabe wohl weiter oben untergegangen ist poste ich sie nochmal..
Schreiben Sie ein Programm, das mit Hilfe von Backtracking eine gültige Lösung für beliebige Sudoku ermittelt, falls eine solche existiert. Die Lösung kann direkt in das Sudoku eingetragen werden.
Edit: Das Sudoku liegt in Form eines 2Dim Arrays vor
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Meine Lösung für die Soduku Aufgabe. Ich hoffe sie ist ungefähr dem genehm was du wolltest. Ich hab sie mit drei verschiedenen Sudokus verschiedener Schwierigkeitsgrade getestet und sie lieferte immer (ein) richtiges bzw das richtige Ergebnis in unter 300ms(Kann beim Deuggen abweichen). Bei der Eingabe von einem Sudoku, welches(wie bei meiner Lösung standartmäßig) mit Nullen gefüllt ist braucht sie 12 ms um eine oft im Internet als Beispielsudoku gesehene Lösung zu produzieren(ausprobieren;)). Die Klasse Sudoku wurde dabei Immutable gehalten(für die verwendete Rekursion recht praktisch:))
Zu sagen ist, dass man darauf achten sollte immer nur Mehrdimensionale Array mit wenigstens 9*9 Zahlen zu übergeben, anderes wird nicht abgefangen. Der restliche Code sollte nicht zu schnell zusammenbrechen(auch wenn bestimmte Teile nicht oft getestet wurde, da sie letztenendes nicht für die Gesamtlösung verwendet werden). Die entscheidenden Methoden sind die unteren 6(bis 9) welche auch ein wenig kommentiert sind(eher spärlich). Zu sagen ist, das eigentlich alles Null-basiert ist. Der Rest findet sich beim durschauen.
Benutzung:
class Program
{
static void Main(string[] args)
{
Sudoku s = new Sudoku(
new int[9, 9] {
{0,8,0,4,0,0,2,0,9},
{0,5,9,0,8,0,0,0,3},
{0,0,0,0,0,9,0,0,7},
{8,2,0,0,1,0,0,0,0},
{5,0,0,0,7,0,0,0,6},
{0,0,0,0,4,0,0,2,5},
{3,0,0,7,0,0,0,0,0},
{9,0,0,0,2,0,3,7,0},
{7,0,5,0,0,8,0,9,0}}
);
/*Sudoku s = new Sudoku(
new int[9, 9] {
{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,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}}
);*/
s.drawToConsole();
Sudoku solution = new Sudoku();
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
solution = s.findSolution();
stopWatch.Stop();
Console.WriteLine("Zeit: " + stopWatch.ElapsedMilliseconds + "ms");
solution.drawToConsole();
Console.ReadLine();
}
}
Eigentlicher Code:
class Sudoku
{
private int[,] m_content;
public Sudoku()
{
m_content = new int[9, 9];
for (int row = 0; row < 9; row++)
{
for (int column = 0; column < 9; column++)
{
m_content[row, column] = 0;
}
}
}
public Sudoku(int[,] content)
{
m_content = new int[9, 9];
for (int row = 0; row < 9; row++)
{
for (int column = 0; column < 9; column++)
{
m_content[row, column] = content[row, column];
}
}
}
public void drawToConsole()
{
for (int row = 0; row < 9; row++)
{
if (row % 3 == 0)
{
Console.WriteLine("-------------");
}
for (int column = 0; column < 9; column++)
{
if (column % 3 == 0) Console.Write("|");
Console.Write(m_content[row, column]);
}
Console.WriteLine("|");
}
Console.WriteLine("-------------");
}
public int[,] toArray()
{
return m_content;
}
private bool isRowValid(int row)
{
List<int> numbers = new List<int>();
for (int column = 0; column < 9; column++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
return true;
}
private bool isColumnValid(int column)
{
List<int> numbers = new List<int>();
for (int row = 0; row < 9; row++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
return true;
}
/// <summary>
/// Zero based!
/// </summary>
/// <param name="box">Box numbers from top-left to bottom right in each row from left to right</param>
/// <returns></returns>
private bool isBoxValid(int box)
{
List<int> numbers = new List<int>();
int boxRow = box <= 2 ? 0 : box <= 5 ? 1 : 2;
int boxColumn = box % 3;
for (int row = boxRow * 3; row < boxRow * 3 + 3; row++)
{
for (int column = boxColumn * 3; column < boxColumn * 3 + 3; column++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
}
return true;
}
public bool isValid()
{
for (int i = 0; i < 9; i++)
{
if (!(isRowValid(i) && isColumnValid(i) && isBoxValid(i)))
{
Console.WriteLine((!isRowValid(i) ? "Row " : "") + (!isColumnValid(i) ? "Column " : "") + (!isBoxValid(i) ? "Box " : "") + i.ToString());
return false;
}
}
return true;
}
private bool isNumberValidAt(int row, int column, int value)
{
Sudoku s = insertNumberAt(row, column, value);
int box = (row < 3 ? 0 : (row < 6 ? 1 : 2)) * 3 + (column < 3 ? 0 : (column < 6 ? 1 : 2));
return s.isRowValid(row) && s.isColumnValid(column) && s.isBoxValid(box);
}
private List<int> getValidNumbersAt(int row, int column)
{
List<int> validNumbers = new List<int>();
Sudoku s;
for (int i = 1; i <= 9; i++)
{
s = insertNumberAt(row, column, i);
int box = (row < 3 ? 0 : (row < 6 ? 1 : 2)) * 3 + (column < 3 ? 0 : (column < 6 ? 1 : 2));
if (s.isRowValid(row) && s.isColumnValid(column) && s.isBoxValid(box))
{
validNumbers.Add(i);
}
}
return validNumbers;
}
public Sudoku insertNumberAt(int row, int column, int value)
{
int[,] newContent = m_content;
newContent[row, column] = value;
return new Sudoku(newContent);
}
public Sudoku findSolution()
{
// If the incoming Sudoku is already wrong dont jump into the solution algorithm
if (isValid())
{
Sudoku s = findSolution(0, 0);
return s == null ? new Sudoku() : s;
}
else
{
return new Sudoku();
}
}
private Sudoku findSolution(int row, int column)
{
// If ready...
if (row == 9)
return this;
// If row changed
if (column == 9)
column = 0;
if (m_content[row, column] == 0)
{
foreach (int i in getValidNumbersAt(row, column))
{
// Check next field
Sudoku s = (insertNumberAt(row, column, i).findSolution(column + 1 == 9 ? row + 1 : row, column + 1));
// If something comes back the solution was found!
if (s != null) return s;
}
return null;
}
else
{
return new Sudoku(m_content).findSolution(column + 1 == 9 ? row + 1 : row, column + 1);
}
}
}
habs grade überflogen, sieht schonmal ganz gut aus..
allerdings wünsche ich mir eine lösung die auch größere Sudokus akzeptiert..
bsp 12er statt 9er
wenn du diesen punkt noch umsetzt kannst du die nächste aufgabe stellen 😉
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.