Laden...

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

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.544 Views
6.911 Beiträge seit 2009
vor 7 Jahren

Hallo inflames2k,

nette Aufgabe 😃

Ich habs über eine (doppelt) verkettete Liste implementiert. Das Ein od. Andere mag besser gehen und die Tests könnte auch noch gründlicher sein, aber für diese Aufgabe reicht mir das 😉


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

namespace Inflames2K
{
    public class MyList<T> : IList<T>
    {
        private ListItem<T> _first;
        private ListItem<T> _last;
        private int         _count = 0;
        //---------------------------------------------------------------------
        public T this[int index]
        {
            get
            {
                ListItem<T> item = this.GetItemInternal(index);
                return item.Value;
            }
            set
            {
                ListItem<T> item = this.GetItemInternal(index);
                item.Value = value;
            }
        }
        //---------------------------------------------------------------------
        public int Count { get { return _count; } }
        //---------------------------------------------------------------------
        public bool IsReadOnly { get; } = false;
        //---------------------------------------------------------------------
        public void Add(T value)
        {
            // null as value is allowed -> consumer has to handle this
            ListItem<T> item = new ListItem<T>(value);

            if (_last != null)
            {
                _last.Next = item;
                item.Previous = _last;
                _last = item;
            }
            else
            {
                _last = item;
                item.Previous = _first;
            }

            if (_first == null)
                _first = item;

            _count++;
        }
        //---------------------------------------------------------------------
        public void Clear()
        {
            _first = null;
            _last = null;
            _count = 0;
        }
        //---------------------------------------------------------------------
        public bool Contains(T item) => this.IndexOf(item) >= 0;
        //---------------------------------------------------------------------
        public void CopyTo(T[] array, int arrayIndex)
        {
            ListItem<T> current = _first;

            while (current != null)
            {
                array[arrayIndex++] = current.Value;
                current = current.Next;
            }
        }
        //---------------------------------------------------------------------
        public IEnumerator<T> GetEnumerator()
        {
            return new MyListEnumerator<T>(_first);
        }
        //---------------------------------------------------------------------
        public int IndexOf(T item)
        {
            ListItem<T> current = _first;
            int index           = 0;

            while (current != null)
            {
                if (current.Value.Equals(item)) return index;
                index++;
                current = current.Next;
            }

            return -1;
        }
        //---------------------------------------------------------------------
        public void Insert(int index, T value)
        {
            if ((_count == 0 && index == 0) || (_count == index))
            {
                this.Add(value);
                return;
            }

            ListItem<T> item     = this.GetItemInternal(index);
            ListItem<T> toInsert = new ListItem<T>(value);

            item.Previous.Next = toInsert;
            toInsert.Previous  = item.Previous;
            item.Previous      = toInsert;
            toInsert.Next      = item;
            _count++;
        }
        //---------------------------------------------------------------------
        public bool Remove(T value)
        {
            int index = this.IndexOf(value);

            if (index < 0) return false;

            this.RemoveAt(index);

            return true;
        }
        //---------------------------------------------------------------------
        public void RemoveAt(int index)
        {
            ListItem<T> current = this.GetItemInternal(index);

            if (current == null) return;

            if (current.Previous == null)
                current.Next.Previous = null;
            else
            {
                current.Previous.Next = current.Next;

                if (current.Next != null)
                    current.Next.Previous = current.Previous;
            }

            if (current == _first) _first = current.Next;
            if (current == _last)  _last  = current.Previous;

            _count--;
        }
        //---------------------------------------------------------------------
        IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();
        //---------------------------------------------------------------------
        private ListItem<T> GetItemInternal(int index)
        {
            if (index < 0 || index >= _count) throw new ArgumentOutOfRangeException(nameof(index));

            ListItem<T> current = _first;

            for (int i = 0; i < index; ++i)
            {
                if (current?.Next == null) return null;
                current = current.Next;
            }

            return current;
        }
    }
}


using System.Diagnostics;

namespace Inflames2K
{
    [DebuggerDisplay("Value = {Value}")]
    public class ListItem<T>
    {
        public T Value              { get; set; }
        public ListItem<T> Previous { get; set; }
        public ListItem<T> Next     { get; set; }
        //---------------------------------------------------------------------
        public ListItem(T value)
        {
            // null as value is allowed -> consumer has to handle this
            this.Value = value;
        }
    }
}


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

namespace Inflames2K
{
    internal class MyListEnumerator<T> : IEnumerator<T>
    {
        private ListItem<T> _first;
        private ListItem<T> _current;
        //---------------------------------------------------------------------
        public MyListEnumerator(ListItem<T> first)
        {
            if (first == null) throw new System.ArgumentNullException(nameof(first));

            _first = first;
        }
        //---------------------------------------------------------------------
        public T Current           { get { return _current != null ? _current.Value : default(T); } }
        object IEnumerator.Current { get { return this.Current; } }
        //---------------------------------------------------------------------
        public bool MoveNext()
        {
            if (_current==null)
            {
                _current = _first;
                return true;
            }

            if (_current.Next == null) return false;

            _current = _current.Next;

            return true;
        }
        //---------------------------------------------------------------------
        public void Reset()
        {
            _current = null;
        }
        //---------------------------------------------------------------------
        public void Dispose()
        {
            // nothing to do
        }
    }
}

Angehängt noch das komplette Projekt inkl. der (rudimentären) Tests.

mfG Gü

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

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

2.298 Beiträge seit 2010
vor 7 Jahren

Hallo,

zuallererst die paar spartanischen Unittests die ich dafür erstellt habe:


 [TestClass()]
    public class ListTests
    {
        [TestMethod()]
        public void AddTest()
        {
            int expectedCount = 10;

            IList<string> collection = new List<string>();
            for (int i = 0; i < expectedCount; i++)
                collection.Add((i + 1).ToString());


            Assert.IsTrue(collection.Count == expectedCount, "Expected count does not match.");
            Assert.IsTrue(collection[5].Equals("6"), "Value on index 5 does not match!");
        }

        [TestMethod()]
        public void ClearTest()
        {
            int expectedCount = 0;

            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());
            Assert.IsTrue(collection.Count == 10, "Expected count does not match.");
            
            collection.Clear();
            
            Assert.IsTrue(collection.Count == expectedCount, "Expected count does not match.");

            bool bFailed = false;
            try
            {
                foreach (var item in collection)
                    Console.WriteLine(item);
            }
            catch(Exception ex)
            {
                bFailed = true;
            }

            Assert.IsFalse(bFailed, "Enumerate empty list failed!");
        }

        [TestMethod()]
        public void ContainsTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());
            Assert.IsTrue(collection.Count == 10, "Expected count does not match.");

        
            Assert.IsTrue(collection.Contains("5"), "Item not in list but should be!");
            Assert.IsFalse(collection.Contains("50"), "Item in list but should not be!");
        }

        [TestMethod()]
        public void GetEnumeratorTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());

            bool bFailed = false;
            try
            {
                foreach (var item in collection)
                    Console.WriteLine(item);
            }
            catch
            {
                bFailed = true;
            }

            Assert.IsFalse(bFailed);
        }

        [TestMethod()]
        public void IndexOfTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());

            Assert.AreEqual(0, collection.IndexOf("1"));
            Assert.AreEqual(1, collection.IndexOf("2"));
            Assert.AreEqual(2, collection.IndexOf("3"));
            Assert.AreEqual(3, collection.IndexOf("4"));
            Assert.AreEqual(4, collection.IndexOf("5"));
        }

        [TestMethod()]
        public void RemoveTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());

            collection.Remove("5");
            Assert.IsTrue(collection.Count == 9, "Number of entries does not match!");

            collection.Remove("50");
            Assert.IsTrue(collection.Count == 9, "Number of entries does not match!");
        }

        [TestMethod()]
        public void InsertAtTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());

            int expected = 5;
            collection.Insert(5, "Hallo Welt");
            Assert.IsTrue(collection.IndexOf("Hallo Welt") == expected, "Not inserted at right index!");

            bool bFalled = false;
            try
            {
                collection.Insert(50, "Test");
            }
            catch
            {
                bFalled = true;
            }

            Assert.IsTrue(bFalled, "Item inserted but should not!");
        }

        [TestMethod()]
        public void RemoveAtTest()
        {
            IList<string> collection = new List<string>();
            for (int i = 0; i < 10; i++)
                collection.Add((i + 1).ToString());

            collection.RemoveAt(0);
            Assert.IsTrue(collection.Count == 9, "Number of entries does not match!");
            Assert.IsFalse(collection.Contains("1"), "Is in list but should not!");

            bool bFailed = false;
            try
            {
                collection.RemoveAt(19);
            }
            catch(Exception ex)
            {
                bFailed = true;
            }

            Assert.IsTrue(bFailed, "Didn't fail but should!");
        }
    }

@gfoidl:
Das ist eine nette Lösung. Vorallem der Gedanke mit der doppelt verketteten Liste. Ich habe es mit einer einfach verketteten umgesetzt. Die doppelt verkettete hat natürlich vorteile.

Da Exception Handling nicht explizit gefordert war, dennoch der Hinweis für dich: gehe ich eine leere Liste mit foreach durch, kommt es zu einer NullReferenceException, da der Root Knoten ja null ist. Ansonsten gefällt mir deine Lösung um Welten besser als meine.

Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |

3.170 Beiträge seit 2006
vor 7 Jahren

Hallo zusammen,

ich hatte das gestern abend als einfach verkettete Liste implementiert - effizient ist sowas natürlich nicht, vor allem beim Index-Zugriffen.
Mein Ansatz war aber ein völlig anderer, deshalb poste ich es auch noch nachträglich.
Gü hat natürlich das Recht der ersten richtigen Lösung.

Linq-Extensions waren nicht verboten, oder?

public class List<T> : IList<T>
{
    class ListNode
    {
        public ListNode(T val, ListNode next = null)
        {
            Value = val;
            Next = next;
        }
        
        public T Value { get; }
        public ListNode Next { get; set; }
    }

    ListNode _root = new ListNode(default(T));

    public int Count { get; private set; }

    public T this[int index]
    {
        get
        {
            if (index >= Count)
                throw new IndexOutOfRangeException();

            return GetNodes().Skip(index).First().Value;
        }
    }

    public IEnumerator<T> GetEnumerator() => GetNodes().Select(n => n.Value).GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public void Add(T item) => InsertAt(Count, item);

    public bool Contains(T item) => GetNodes().Any(n => object.Equals(n.Value, item));

    public void Clear()
    {
        _root.Next = null;
        Count = 0;
    }

    public int IndexOf(T item)
    {
        int idx = GetNodes().TakeWhile(n => !object.Equals(n.Value, item)).Count();
        return (idx == Count) ? -1 : idx;
    }

    public void InsertAt(int index, T item)
    {
        if((index > Count) || (index < 0))
            throw new ArgumentOutOfRangeException(nameof(index));

        var node = GetNodes(true).Skip(index).First();
        node.Next = new ListNode(item, node.Next);
        Count++;
    }

    public bool Remove(T item)
    {
        var node = GetNodes(true)
                    .SkipWhile(n => (n.Next == null) || !object.Equals(n.Next.Value, item))
                    .FirstOrDefault();
        if (node == null)
            return false;

        node.Next = node.Next.Next;
        Count--;
        return true;
    }

    public void RemoveAt(int index)
    {
        if((index >= Count) || (index < 0))
            throw new ArgumentOutOfRangeException(nameof(index));

        var node = GetNodes(true).Skip(index).First();
        node.Next = node.Next.Next;
        Count--;
    }

    IEnumerable<ListNode> GetNodes(bool includeRoot = false)
    {
        var node = _root;
        if (includeRoot)
            yield return node;
        while ((node = node.Next) != null)
            yield return node;
    }
}

Getestet habe ich ebenfalls nur rudimentär, da hat soweit alles funktioniert...

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

6.911 Beiträge seit 2009
vor 7 Jahren

Hallo inflames2k,

gehe ich eine leere Liste mit foreach durch, kommt es zu einer NullReferenceException, da der Root Knoten ja null ist

Ganz ausgereift war die Implementierung noch nicht 😉
herbivore hat mir dankenswerterweise auch ein paar Anmerkungen geschickt. Ich hab diese noch teilweise in https://github.com/gfoidl/myCSharp-Programmierspiel-MyList eingebaut.

Hallo MarsStein,

Gü hat natürlich das Recht der ersten richtigen Lösung.

Mir fällt keine neue Aufgabe ein, daher trete ich dieses Recht gerne an dich ab.

mfG Gü

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

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

2.298 Beiträge seit 2010
vor 7 Jahren

Ich scheine wohl der einzige zu sein, der Denkfaul ist. - Meine Count-Property geht die Liste durch und zählt die Einträge. Eure Variante ist natürlich sauberer und vorallem Performance-Schonender. 😁

Dennoch hier noch meine Lösung:

 
    public class ListItem<T>
    {
        public ListItem<T> Next { get; set; }
        public T Value { get; set; }
    }

    public class List<T> : IList<T>
    {
        private ListItem<T> _root;

        public T this[int index]
        {
            get
            {
                ListItem<T> item = this.GetItemAt(index);
                if (item == null)
                    return default(T);
                else
                    return item.Value;               
            }
        }

        /// <summary>
        /// Method to get the items 
        /// </summary>
        public int Count
        {
            get
            {
                int count = 0;

                if (_root != null)
                {
                    ListItem<T> item = _root;
                    do
                    {
                        count++;
                        item = item.Next;
                    } while (item != null);
                }

                return count;
            }
        }

        /// <summary>
        /// Method to add an item
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.Insert(this.Count, item);           
        }

        public void Clear()
        {
            this._root = null;
        }
              
        public bool Contains(T item)
        {
            return this.IndexOf(item) >= 0;
        }

        public IEnumerator<T> GetEnumerator()
        {
            if (this._root != null)
            {
                ListItem<T> innerItem = this._root;
                do
                {
                    yield return innerItem.Value;
                    innerItem = innerItem.Next;
                } while (innerItem != null);
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public int IndexOf(T item)
        {
            int index = 0;

            if (this._root != null)
            {
                ListItem<T> innerItem = this._root;

                do
                {
                    if (innerItem.Value.Equals(item))
                        return index;

                    innerItem = innerItem.Next;
                    index++;
                } while (innerItem != null);
            }
            return -1;
        }
        
        public bool Remove(T item)
        {
            bool bRemoved = false;

            if (this.IndexOf(item) < 0 || this._root == null)
                return true;

            ListItem<T> innerItem = this._root;

            do
            {
               if(innerItem.Next.Value.Equals(item))
               {
                    innerItem.Next = innerItem.Next.Next;
                    bRemoved = true;                    
               }
               innerItem = innerItem.Next;  
            } while (innerItem != null && !bRemoved);

            return bRemoved;
        }

        public void Insert(int index, T item)
        {
            if (index < 0 || index > this.Count)
                throw new IndexOutOfRangeException();

            ListItem<T> newItem = new ListItem<T>();
            newItem.Value = item;
            if (index == 0)
            {
                newItem.Next = this._root;
                this._root = newItem;
            }
            else
            {
                ListItem<T> innerItem = this.GetItemAt(index - 1);
                newItem.Next = innerItem.Next;
                innerItem.Next = newItem;
            }
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index > this.Count - 1)
                throw new IndexOutOfRangeException();

            if(index == 0)            
                _root = _root.Next;            
            else if(this._root != null)
            {
                ListItem<T> innerItem = this.GetItemAt(index - 1);
                innerItem.Next = innerItem.Next.Next;
            }
        }
        
        private ListItem<T> GetItemAt(int index)
        {
            ListItem<T> item = null;
            int resIndex = 0;

            if (this._root != null)
            {
                if (index < 0 || index > this.Count - 1)
                    throw new IndexOutOfRangeException();

                ListItem<T> innerItem = this._root;
                do
                {
                    if (resIndex == index)
                        item = innerItem;
                    innerItem = innerItem.Next;
                    resIndex++;
                } while (innerItem != null && item == null);

            }

            return item;
        }
    }

Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |

3.170 Beiträge seit 2006
vor 6 Jahren

Hallo zusammen,

Mir fällt keine neue Aufgabe ein, daher trete ich dieses Recht gerne an dich ab.

Ist ja schon etwas länger her. Hier also nochmal eine Aufgabe, was ganz kurzes.

Gegeben ist folgende Methode:

        static void DoSomething<T>(T input)
        {
            Console.WriteLine(input.ToString());
            Console.WriteLine(input.GetHashCode());
            Console.WriteLine(input.Equals(default(T)));
            try
            {
                Console.WriteLine(input.GetType());
            }
            catch(NullReferenceException)
            {
                Console.WriteLine("NullReferenceException caught");
            }
        }

Aufgabe: Die Methode soll so aufgerufen werden, dass innerhalb des catch-Blocks die Zeile "NullReferenceException caught" ausgegeben wird. Die Methode darf dabei nicht verändert werden.

Viel Spaß beim knobeln!

MarsStein

EDIT: MrSparkle hat mich freundlicherweise darauf hingewiesen, dass die Lösung sehr leicht im Internet zu finden ist - das ist hier nicht das Ziel. Denkt lieber selbst drüber nach, und nehmt euch selbst und anderen nicht den Spaß an der Sache - es ist auch wirklich nicht besonders schwierig 😉

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

709 Beiträge seit 2008
vor 6 Jahren

Guten Morgen,

hier ist meine Lösung:

DoSomething<int?>(null);
3.170 Beiträge seit 2006
vor 6 Jahren

Hallo pinki,

die Lösung ist korrekt - du bist dran und darfst die nächste Aufgabe stellen 👍

Kurz zur Erklärung: Man braucht ja einen Typen der null und doch nicht null ist. Genau das liefert ein Nullable<T>. Hat dieses keinen Wert, wird es beim Boxing zu object tatsächlich null.
Alle anderen hier aufgerufenen Funktionen sind virtual, und beim Aufruf muss kein Boxing stattfinden - bis auf GetType, das nur in object implementiert und nich virtual ist. Deshalb verhält sich dieser spezielle Aufruf anders.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

709 Beiträge seit 2008
vor 6 Jahren

Hallo zusammen,
mir fällt leider keine schöne Aufgabe ein.
Falls jemand eine tolle Aufgabe hat, kann diese von mir aus gerne statt meiner Aufgabe gestellt werden. =)

T
708 Beiträge seit 2008
vor 3 Jahren

Hallo zusammen,

durch Zufall bin ich auf einen Ordner aus meiner Ausbildung von 2008 gestoßen.

Dort war es Aufgabe das "verflixte Flugzeugspiel" umzusetzen.
Meine Lösung damals sollte natürlich auch eine automatische Auflösung beinhalten, die äußerst mäßig funktioniert hat...


Den Code möchte heutzutage auch niemand mehr sehen 😁

Aufgabe ist es, dass alle Karten in einem 3x3 Raster so sortiert & gedreht werden, dass an den Stoßkanten je eine Flugzeugspitze und ein Heck in der selben Farbe anliegen.

Dazu habe ich kurzum eine minimalistische WPF-Anwendung erstellt.
Per Drag&Drop können die Karten getauscht, per Rechtsklick um 90° gedreht werden.

In der Klasse "Game.cs" wird in der Solve()-Methode losprogrammiert:

public static void Solve()
{
    //Add Solution here:
    for (int i = 1; i < Cards.Count; i++)
    {
        var j = 0;
        if (i == 3 || i == 6)
            while (!Cards[i].ContainsCounterpart(Cards[i - 3].BottomPlane) && i+j < Cards.Count)
                Cards.Swap(i, i + j++);
        else
            while (!Cards[i].ContainsCounterpart(Cards[i - 1].RightPlane) && i + j < Cards.Count)
                Cards.Swap(i, i + j++);
    }

    for (int i = 1; i < Cards.Count; i++)
        if (i == 3 || i == 6)
        {
            if (Cards[i].ContainsCounterpart(Cards[i - 3].BottomPlane))
                while (!Cards[i].TopPlane.Fits(Cards[i - 3].BottomPlane))
                    Cards[i].RotatePlanesRight();
        }
        else
            if (Cards[i].ContainsCounterpart(Cards[i - 1].RightPlane))
            while (!Cards[i].LeftPlane.Fits(Cards[i - 1].RightPlane))
                Cards[i].RotatePlanesRight();            
}

(Exemplarische Herangehensweise)

Die Liste der Karten besteht aus 4 Flugzeugen, die wiederum angeben welche Farbe sie besitzen und ob es sich um die Front oder das Heck handelt.
Man kann sie über Top,Left,Right & Bottom oder im Uhrzeigersinn Planes[0]-Planes[3] erreichen.

Zur Hilfe gibt es die Methoden*ContainsCounterpart - Ob ein passendes Flugzeugteil auf der Karte enthalten ist *Swap - Tauscht eine Karte mit einer anderen *RotatePlanesRight - Dreht die Karte um 90° *Fits - Ob das Flugzeug zu einem anderen passt

Leider kann ich nur ein Bild oder ein ZIP hochladen. Daher ist die Solution im nächsten Beitrag: Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

PS: Das Projekt ist absichtlich so minimal gehalten wie möglich. Also bitte sonderlich auf die Codequalität achten. Oder mangelndes MVVM 👅

T
708 Beiträge seit 2008
vor 3 Jahren

Die Aufgabe ist auf der vorigen Seite zu finden.

Hier nun die Solution des Flugzeug-Spiels.

Viel Erfolg!

PS: aktuell habe ich 14 mögliche Lösungen und finde die 1. nach 479 Durchläufen.
Allerdings habe ich noch eine Unzulänglichkeit im Code, für die ich noch keine elegante Lösung gefunden habe.

Stand jetzt: ca. 70 Zeilen Code, inkl. Leerzeilen und Kommentaren.

T
708 Beiträge seit 2008
vor 3 Jahren

Nach dem immensen Feedback stelle ich die Lösung und den Weg dorthin mal bereit.

Die 9 Karten können auf 362880 verschiedene Arten angeordnet werden.
Also erstellen wir uns eine Liste mit allen Möglichen Sortierungen der Karten:


static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Diese Möglichkeiten gehen wir nun alle* durch:


private static Card[] _cardTemp;
public static void Solve()
{
    //Add Solution here:    
    IEnumerable<IEnumerable<int>> permutations = GetPermutations(Enumerable.Range(0, 9), 9);    

    //Create a copy for easier sorting/rollback per permutation
    _cardTemp = new Card[Cards.Count];
    Array.Copy(Cards.ToArray(), _cardTemp, Cards.Count);

    foreach (var permutation in permutations)    
    {
        //Skip all excluded entries
        //if (IsBlacklisted(permutation))
        //    continue;
        if (CheckSolution(permutation))
            return;    
      }
}

*Alle Möglichkeiten? Besser nicht, möchte man da denken!
Also habe ich eine Blacklist geschaffen, die bekannte, nicht funktionierende Kombinationen überspringt.
Nehmen wir an, die Kombination der Karten 1235.... kann nicht funktionieren, weil Karte 3 und 5 keine passenden Teile haben (egal wie man sie dreht), speichert man eben diese Kombination ab.
Nun kann man prüfen ob die aktuelle Permutation in der Blacklist vorkommt und für alle folgenden Kombinationen rausspringen...

Preoptimization is root of all evil!
Hier lernt man am lebenden Objekt, dass dieser Spruch nach wie vor Gültigkeit besitzt!
Was passierte: Der Durchlauf bis zum ersten Treffer hat statt 1,3 Sekunden auf einmal 3 Sekunden gedauert.
Die Blacklist wuchs immer weiter an und speicherte 2 bis 8 stellige Permutationen.
Aufgrund der variablen Breite, erfolgt die Suche durch die Blacklist mit StartsWith(), was bekanntlich nicht sonderlich performant ist.
Also wurde alles mehr gebremst, als dass es geholfen hat. Auch "Optimierungen" auf ein Dictionary mit fester Breite hat nach wie vor für Verzögerungen gesorgt.
Tatsächlich ist es schneller alle Kombinationen durchzugehen, als bestimmte auszuschließen.

Also weiter im Takt!
In der CheckSolution() prüfe ich Karte für Karte ob es einen "Match" geben kann.

Dafür gibt es die IsHit() Methode. Die nimmt die Flugzeugnummer entgegen und prüft dieses gegen das vorige Flugzeug. Als weiteren Parameter kann man übergeben ob nur die Möglichkeit besteht (Also das passende Gegenstück lediglich enthalten ist) oder dieses auch schon korrekt gedreht ist und anliegt.


private static bool IsHit(int planeNo, bool onlyPossibility = false)
{
    switch (planeNo)
    {
        case 0:
            return true;
        case 8:
        case 7:
        case 5:
        case 4:
            return onlyPossibility?
                Cards[planeNo].ContainsCounterpart(Cards[planeNo - 3].BottomPlane) && Cards[planeNo].ContainsCounterpart(Cards[planeNo - 1].RightPlane):
                Cards[planeNo].TopPlane.Fits(Cards[planeNo - 3].BottomPlane) && Cards[planeNo].LeftPlane.Fits(Cards[planeNo - 1].RightPlane);
        case 2:
        case 1:
            return onlyPossibility ?
                Cards[planeNo].ContainsCounterpart(Cards[planeNo - 1].RightPlane) :
                Cards[planeNo].LeftPlane.Fits(Cards[planeNo - 1].RightPlane);
        case 3:
        case 6:
            return onlyPossibility ?
                Cards[planeNo].ContainsCounterpart(Cards[planeNo - 3].BottomPlane) :
                Cards[planeNo].TopPlane.Fits(Cards[planeNo - 3].BottomPlane);
        default:
            return false;
    }
}

Das bringt uns zum nächsten Helfer, der eine Karte so lange dreht, bis sie korrekt anliegt. Oder mit false herausspringt:


private static bool TurnPlane(int planeNo)
{
    if (planeNo == 0 || IsHit(planeNo))
        return true;            
    for (int rotation = 0; rotation < 3; rotation++)
    {
        Cards[planeNo].RotatePlanesRight();
        if (IsHit(planeNo))
            return true;
    }
    return false;
}

Das Ganze nun noch zusammenstricken.
Dabei gibt es allerdings noch **zwei **Eigenheiten:


private static bool CheckSolution(IEnumerable<int> permutation)
{
    //Change all cards, one by one
    for (int i = 0; i < Cards.Count; i++)
    {
        int perm = permutation.ElementAt(i);
        Cards[i] = _cardTemp[perm];                

        // If card [1] does not fit to [0], rotate [0] until it works
        if (i == 1 && !IsHit(i, true))
            for (int rotation = 0; rotation < 3; rotation++)
            {
                Cards[0].RotatePlanesRight();
                if (IsHit(i, true))
                    break;
            }
        //If first two cards still do not fit!
        if (i == 1 && !IsHit(i, true))
        {
            //Blacklist(permutation, i);
            return false;
        }

        //Now turn until the plane fits on all edges or blacklist it
        if (!TurnPlane(i))
        {            
            //Blacklist(permutation, i);
            break;
        }
        //If we made it until here, all cards fit!
        if (i == Cards.Count - 1)
            return true;
    }
    return false;
}

Und zwar ist es wichtig, dass schon die erste Karte so gedreht wird, dass sie zur zweiten Karte passen kann.
Ansonsten kann man die Kombination bereits verlassen.

Anschließend schnappt man sich die nächste Karte und dreht so lange daran herum, bis diese passt.
Oder bricht entsprechend ab.
Bei der 9. Karte angelangt, ist das Rätsel gelöst! Oder?

Nein, natürlich nicht! Denn so erhält man nicht alle 16 Lösungen.
Es gibt Kartenpaare, die mehr als eine Kombination enthalten. Wenn nun Variante 1 nicht funktioniert, wird zur nächsten Permutation gesprungen. Damit hätte man die potentielle Lösung ignoriert.

Daher kam noch dieser Code dazu:


//Now turn until the plane fits on all edges or blacklist it
if (!TurnPlane(i))
{
    //Check if there is a better way, turning the first card more over
    //(There might be [definitely are] more combinations with first & second card)
    if (i >= 1)
    {
        bool anotherPossibility = true;
        //Turn first card max 3 times to find a second match
        for (int rotation = 0; rotation < 3; rotation++)
        {
            anotherPossibility = true;
            Cards[0].RotatePlanesRight();
            for (int j = 1; j <= i; j++)
            {
                if (!TurnPlane(j))
                {
                    anotherPossibility = false;
                    break;
                }
            }
            if (anotherPossibility)
                break;
        }
        if (anotherPossibility)
        {
            i = 0;
            continue;
        }
    }
    //Blacklist(permutation, i);
    break;
}

Gibt es innerhalb der drei Drehversuche noch einen weiteren Match, so wird einfach der Counter i wieder auf 0 gesetzt.
Somit geht diese Permutation nochmals ins Rennen!

Mein unrepräsentatives Ergebnis, wenn man alle Möglichkeiten durchlaufen lässt:


1:	024658137	1,3719574s	Attempts: 4750
2:	062731854	0,1125595s	Attempts: 19959
3:	078536412	0,0506084s	Attempts: 26483
4:	160352784	0,1687565s	Attempts: 46273
5:	168352704	0,024541s	Attempts: 49306
6:	214635078	0,0997753s	Attempts: 58739
7:	214635870	6,77E-05s	Attempts: 58744
8:	407253861	0,4984146s	Attempts: 117594
9:	450137268	0,104993s	Attempts: 130416
10:	458137260	0,031965s	Attempts: 134889
11:	487253061	0,0901648s	Attempts: 145112
12:	731056428	0,6187311s	Attempts: 212564
13:	731856420	0,0051159s	Attempts: 213197
14:	824650137	0,2260807s	Attempts: 236826
15:	862731054	0,1372636s	Attempts: 252055
16:	870536412	0,0283649s	Attempts: 254831
Total: 3,6389175s

Die Performance hängt natürlich stark am verwendeten Rechner und Debug/Release-Mode.

Die Programmierung ist wahrlich kein Hexenwerk. Die Eigenheiten und Fallstricke zu erkennen war aber echt interessant.
Und für mich persönlich ein schöner Ausbruch aus der Alltagsprogrammierung 🙂