Laden...

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

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.544 Views
49.485 Beiträge seit 2005
vor 12 Jahren

Hallo uNki,

vorne weg: Da nach Namenskonventionen keine Präfixe für Klassen verwendet werden sollen und außerdem alles andere englisch war, habe ich mir erlaubt, die Klasse CTermin in Appointment umzubenennen. Außerdem sei angemerkt, dass mein Code ohne Fehlerbehandlung ist, insbesondere ohne Berücksichtigung von Null-Referenzen.

Nette Aufgabe. Hier meine Lösung in 46 Zeilen (inkl. Leerzeilen und Zeilen, die nur geschweifte Klammern enthalten). Die Methode PlaceAppointments erwartet die Termine entsprechend der von dir genannten Kriterien sortiert.

public static void PlaceAppointments (List <Appointment> appointments)
{
   List <List <Appointment>> grid = new List <List <Appointment>> ();

   int horizontalIndex;
   foreach (Appointment appointment in appointments) {
      horizontalIndex = 0;
      foreach (List <Appointment> row in grid) {
         if (!Appointment.Overlapp (appointment, row)) {
            break;
         }
         ++horizontalIndex;
      }
      if (grid.Count <= horizontalIndex) {
         grid.Add (new List <Appointment> ());
      }
      grid [horizontalIndex].Add (appointment);
      appointment.HorizontalIndex = horizontalIndex;
   }

   foreach (Appointment appointment in appointments) {
      for (horizontalIndex = appointment.HorizontalIndex + 1; horizontalIndex < grid.Count; ++horizontalIndex) {
         if (Appointment.Overlapp (appointment, grid [horizontalIndex])) {
            break;
         }
      }
      appointment.Divider = (horizontalIndex - appointment.HorizontalIndex) / (double)grid.Count;
      appointment.Width   = (horizontalIndex - appointment.HorizontalIndex) * (100 / grid.Count);
   }
}

public static bool Overlapp (Appointment appointment1, Appointment appointment2)
{
   return appointment1.EndTime > appointment2.StartTime
       && appointment2.EndTime > appointment1.StartTime;
}

public static bool Overlapp (Appointment appointment, List <Appointment> appointments)
{
   foreach (Appointment comparativeAppointment in appointments) {
      if (Appointment.Overlapp (appointment, comparativeAppointment)) {
         return true;
      }
   }
   return false;
}

Wenn die Termine nicht sortiert sind, kann man sie mit List.Sort und folgendem Comparer sortieren:

public static int Compare (Appointment appointment1, Appointment appointment2)
{
   if (appointment1.StartTime == appointment2.StartTime) {
      if (appointment1.EndTime == appointment2.EndTime) {
         return 0;
      }
      if (appointment1.EndTime > appointment2.EndTime) {
         return -1;
      }
      return 1;
   }
   if (appointment1.StartTime > appointment2.StartTime) {
      return 1;
   }
   return -1;
}

Hier noch der Test für dein Beispiel:

public static void Main (string [] astrArg)
{
   List <Appointment> appointments = new List <Appointment> ();
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 15:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 14:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:30:00"), Convert.ToDateTime("16.02.2012 11:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 11:30:00"), Convert.ToDateTime("16.02.2012 12:00:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 14:30:00"), Convert.ToDateTime("16.02.2012 15:00:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 15:30:00"), Convert.ToDateTime("16.02.2012 16:00:00")));

   appointments.Sort (Appointment.Compare);

   Appointment.PlaceAppointments (appointments);

   foreach (Appointment appointment in appointments) {
      Console.WriteLine (appointment);
   }
}

Wobei dieser folgende ToString-Methode benötigt:

public override String ToString ()
{
   return "" + StartTime + " - " + EndTime + ": " + HorizontalIndex + ", " + Width + ", " + Divider;
}

herbivore

U
58 Beiträge seit 2011
vor 12 Jahren

korrekt.
46 zeilen... 8o
irre, ich brauche 200 🤔

aber ganz ehrlich.. habe auch nichts anderes von herbivore erwartet 👍

hier meine alternative lösung, bitte ausgrauen, wenn zuviel.

(Divider würde sich in meinem fall ergeben aus ownConflictDivider/maxConflictDivider)


    public void CalculateAppointmentPositions()
    {
        //appList sortieren
        AppointmentList.Sort((x, y) => x.Start.CompareTo(y.Start));

        //konfliktlisten erstellen
        //---------------------------------------------------------------------

        //temporäre conflictGroups löschen
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            conflictGroup.Clear();
        }

        //temporäre groupList löschen
        groupList.Clear();

        //temporäre ConflictApps der appointments löschen
        foreach (CAppointment app in AppointmentList)
        {
            app.ConflictApps.Clear();
        }

        foreach (CAppointment appToCheck in AppointmentList) //appList enthält ALLE apps, die auf dem screen sichtbar sind und ist nach startzeit sortiert
        {
            appToCheck.MaxConflictDivider = 1;
            //konfliktpartner von appToCheck ermitteln
            foreach (CAppointment appToCompare in AppointmentList)
            {
                if ((appToCompare != appToCheck))
                {
                    if ((appToCheck.End > appToCompare.Start) && (appToCheck.Start < appToCompare.End))
                    {
                        appToCheck.ConflictApps.Add(appToCompare);
                    }
                }
            }

            if (groupList.Count < 1) //wenn noch keine conflictGroup existiert (--> erstes zu prüfendes appointment in dem fall), neue gruppe erstellen und appToCheck hinzufügen
            {
                List<CAppointment> conflictGroup = new List<CAppointment>();
                conflictGroup.Add(appToCheck);
                groupList.Add(conflictGroup);
            }

            else
            {
                bool listFound = false;
                foreach (List<CAppointment> conflictGroup in groupList)
                {
                    foreach (CAppointment app in appToCheck.ConflictApps)
                    {
                        if (conflictGroup.Contains(app))
                        {
                            conflictGroup.Add(appToCheck);
                            listFound = true;
                            break;
                        }
                    }
                }

                if (listFound == false) //eine neue konfliktliste erstellen --> neue gruppe von appointments mit konflikten untereinander
                {
                    List<CAppointment> conflictGroup = new List<CAppointment>();
                    conflictGroup.Add(appToCheck);
                    groupList.Add(conflictGroup);
                }
            }

        }
        //konfliktlisten erstellt. alle appointments die miteinander konflikte haben, stehen jetzt jeweils in einer eigenen liste "conflictGroup"
        //---------------------------------------------------------------------

        foreach (CAppointment appToCheck in AppointmentList)
        {
            appToCheck.OwnConflictDivider = appToCheck.ConflictApps.Count + 1;
        }

        //maximalen conflictDivider feststellen
        //---------------------------------------------------------------------
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            if (conflictGroup.Count > 1)
            {
                List<int> dividers = new List<int>();

                foreach (CAppointment appToCheck in conflictGroup)
                {
                    appToCheck.MaxConflictDivider = 1;
                    foreach (CAppointment appToCompare in conflictGroup)
                    {
                        if ((appToCompare.Start.Date == appToCheck.Start.Date) && (appToCompare != appToCheck))
                        {
                            if ((appToCompare.Start.TimeOfDay <= appToCheck.Start.TimeOfDay) && (appToCompare.End.TimeOfDay > appToCheck.Start.TimeOfDay))
                                appToCheck.MaxConflictDivider++;
                        }
                    }
                    dividers.Add(appToCheck.MaxConflictDivider);
                }

                foreach (CAppointment app in conflictGroup)
                {
                    app.MaxConflictDivider = dividers.AsQueryable().Max();
                }
                dividers.Clear();
            }
        }
        //---------------------------------------------------------------------



        //horizontalen index der appointments ausgehend von ihrer startzeit ermitteln
        //---------------------------------------------------------------------
        List<List<CAppointment>> groupListSorted = new List<List<CAppointment>>();
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            groupListSorted.Add(conflictGroup.OrderBy(app => app.Start).ThenByDescending(app => app.End).ToList());
        }

        foreach (List<CAppointment> conflictGroup in groupListSorted)
        {
            foreach (CAppointment app in conflictGroup)
            {
                app.HorizontalIndex = 0;
            }

            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                horizontalIndexGroup.Clear();
            }
            horizontalIndexGroups.Clear();

            for (int j = 0; j < conflictGroup[0].MaxConflictDivider; j++)
            {
                List<CAppointment> xFactorGroup = new List<CAppointment>();
                horizontalIndexGroups.Add(xFactorGroup);
            }

            foreach (CAppointment appToCheck in conflictGroup)
            {
                foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
                {
                    bool containsConflictApp = false;
                    foreach (CAppointment conflictApp in appToCheck.ConflictApps)
                    {
                        if (horizontalIndexGroup.Contains(conflictApp))
                        {
                            containsConflictApp = true;
                            break;
                        }
                    }
                    if (containsConflictApp == false)
                    {
                        horizontalIndexGroup.Add(appToCheck);
                        break;
                    }

                }
            }
            //-----------------------------------------------------------------


            //eigenen conflictDivider ermitteln
            //-----------------------------------------------------------------
            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                foreach (CAppointment app in horizontalIndexGroup)
                {
                    app.HorizontalIndex = horizontalIndexGroups.IndexOf(horizontalIndexGroup);
                    app.OwnConflictDivider = app.MaxConflictDivider;

                        foreach (var conflictApp in app.ConflictApps)
                        {
                            if (conflictApp.HorizontalIndex == app.HorizontalIndex + 1)
                            {
                                app.OwnConflictDivider = conflictApp.OwnConflictDivider;
                                break;
                            }
                            else
                            {
                                app.OwnConflictDivider = app.MaxConflictDivider - app.ConflictApps.Count < 1 ? 1 : app.MaxConflictDivider - app.ConflictApps.Count;
                            }
                        }

                }
            }

            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                foreach (CAppointment app in horizontalIndexGroup)
                {
                    foreach (CAppointment conflictApp in app.ConflictApps)
                    {
                        for (int i = 0; i < app.MaxConflictDivider; i++)
                        {
                            if (conflictApp.HorizontalIndex == app.HorizontalIndex + i)
                            {
                                if (app.OwnConflictDivider > (conflictApp.HorizontalIndex - app.HorizontalIndex))
                                    app.OwnConflictDivider = (conflictApp.HorizontalIndex - app.HorizontalIndex);
                                break;
                            }
                        }
                    }
                }
            }
            //-----------------------------------------------------------------
        }

        //temporäre conflictGroups löschen
        foreach (List<CAppointment> conflictGroup in groupListSorted)
        {
            conflictGroup.Clear();
        }

        //temporäre groupListSorted löschen
        groupListSorted.Clear();
        //---------------------------------------------------------------------

        Invalidate();
    }

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo zusammen,

hier kommt meine neue Aufgabe:

Es geht darum, ein Array von beliebig vielen Elementen in linearer Zeit nach ihrer Kategorie zu sortieren. Damit das tatsächlich in linearer Zeit möglich ist, gibt es nur drei Kategorien. Die Elemente mit der Kategorie First sollen am Anfang des Arrays stehen, die der Kategorie Third am Ende und die der Kategorie Second dazwischen. Zur Implementierung darf kein zusätzliches Array (und auch keine andere Collection) verwendet werden. Die Signatur der zu schreibenden Methode lautet:

public static void Sort<T> (T [] items) where T : ICategorizable

Ihr könnt auf folgendem Code-Rahmen aufbauen:

using System;

static class App
{
   public static void Main ()
   {
      Element [] elements = new Element [] {
         new Element (Category.Second),
         new Element (Category.First),
         new Element (Category.Third),
         new Element (Category.Second),
         new Element (Category.Third),
         new Element (Category.First),
      };

      Sort (elements);

      foreach (Element element in elements) {
         Console.WriteLine (element);
      }
   }

   public static void Sort<T> (T [] items) where T : ICategorizable
   {
      // hier euer Code
   }

   public static void Swap <T> (T [] items, int i1, int i2)
   {
      T item = items [i1];
      items [i1] = items [i2];
      items [i2] = item;
   }
}

public enum Category {
   First,
   Second,
   Third
}

public interface ICategorizable
{
   Category Category { get; }
}

public class Element : ICategorizable
{
   public Element (Category category)
   {
      Category = category;
   }

   public Category Category { get; private set; }

   public override String ToString ()
   {
      return Category.ToString ();
   }
}

Das Array in der Main-Methode ist nur ein Beispiel. Die Methode soll in allen Fällen korrekt funktionieren. Fehlerbehandlung ist nicht erforderlich. Ihr könnt also davon ausgehen, dass der Parameter der Sort-Methode nicht null ist und dass keine anderen als die drei genannten Kategorien vorkommen können.

Viel Spaß und viel Erfolg!

herbivore

2.298 Beiträge seit 2010
vor 12 Jahren

Hallo, ich habe mich für ein einfaches Bubble-Sort entschieden. Da die Kategorien in einem enum vorliegen stellt dies auch garkein Problem dar.

Meine Sort-Methode:


public static void Sort<T>(T[] items) where T : ICategorizable
    {
        if(items == null)
              return;

        // a imple bubble sort should do the work.
         int runs = items.Length;
         do
         {
             for(int i = 0; i < runs-1; i++)
             {
                 if(items[i].Category > items[i+1].Category)
                 {
                     Swap<T>(items, i, i+1);
                 }
             }
             runs--;
         }while(runs > 0);
    }

Getestet habe ich es mit zufällig generierten Items, die demnach auch zufällige Kategorien hatten. Auch weitere Kategorien hinzufügen stellte kein Problem dar.

// Edit: Ich seh grad, dass das "in linearer Zeit" kursiv ist, hat das etwas zu sagen?

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

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

6.862 Beiträge seit 2003
vor 12 Jahren

Hallo,

Bubblesort ist nicht linear. Im schlimmsten Fall hat es quadratischen Aufwand, siehe z.B. auf der Wikipedia Seite zur Übersicht der Sortierverfahren.

Ist auch leicht erklärbar, da du ja die Laufvariable ändern musst bei Umsortierung und daher abhängig von der Vorsortierung sich die Anzahl der Durchläufe ändert und im Worstcase halt fast n² viele Durchläufe hast, bei n Elementen.

Auf der Übersichstseite sieht man auch, das man die Aufgabe nicht mit einem Standardsortieralgorithmus lösen kann, da keiner der aufgeführten im Worst Case linear ist.

Baka wa shinanakya naoranai.

Mein XING Profil.

D
96 Beiträge seit 2012
vor 12 Jahren

Erstmal hi 🙂

@inflames2k: Ja, das linear hat etwas zu bedeuten 😜

Hier ist meine Lösung:


public static void Sort<T>(T[] items) where T : ICategorizable
{
     Int32 start = 0;
     Int32 end = items.Length - 1;
     Int32 i = 0;

     while(i <= end)
     {
         T item = items[i];
         if (item.Category == Category.First && i > start)
             Swap(items, i, start++);
         else if (item.Category == Category.Third)
             Swap(items, i, end--);
         else
              i++;
     }
}

Ich möchte keine neue Aufgabe stellen bzw. es fällt mir keine ein, also kann jemand anderes gerne eine neue Aufgabe stellen 🙂

Hinweis von talla vor 12 Jahren

Neue Aufgaben darf man erst stellen wenn der Aufgabenposter die Korrektheit der Lösung bestätigt. Dies ist noch nicht erfolgt, also kann noch keine neue Aufgabe gestellt werden.

6.862 Beiträge seit 2003
vor 12 Jahren

Hallo,

die Lösung ist auch nicht linear. Besser als Bubblesort was den Worstcase angeht, aber trotzdem abhängig von der Anzahl der Vertauschungen und der Anzahl der Items und nicht nur von der Anzahl der Items (was bei Linearität der Fall sein muss).

Baka wa shinanakya naoranai.

Mein XING Profil.

2.298 Beiträge seit 2010
vor 12 Jahren

Dann muss ich nachliefern. 😃 Ich denke folgende Sortierung sollte Linear sein und ist meiner Meinung nach ausschließlich Abhängig von der Anzahl der Items.


    public static void Sort<T>(T[] items) where T : ICategorizable
    {
        for (int i = 0; i < items.Length-1; i++)
        {
            for (int j = i; j < items.Length; j++)
            {
                if (items[i].Category > items[j].Category)
                    Swap<T>(items, i, j);
            }
        }
    }

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

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

D
96 Beiträge seit 2012
vor 12 Jahren

Der worst-case meiner Methode ist 2n Schleifendurchläufe, wenn im Array nur Elemente der Category First sind, was ebenfalls in O(n) liegt und somit in linearer Zeit fertig wird. Hab den code noch mal angepasst damit es nun auch konstant ist mit genau n durchläufen.

public static void Sort<T>(T[] items) where T : ICategorizable
 {
      Int32 start = 0;
      Int32 end = items.Length - 1;
      Int32 i = 0;
 
     while(i <= end)
      {
          T item = items[i];
          if (item.Category == Category.First && i > start)
              Swap(items, i++, start++);
          else if (item.Category == Category.Third)
              Swap(items, i, end--);
          else
               i++;
      }
 }

Edit:
@inflames2k: Das ist immernoch keine lineare Zeit 😛
@ dN!3L: Da war ich ein Stück scheller 😛

2.891 Beiträge seit 2004
vor 12 Jahren

Ich habe auch was:


public static void Sort<T>(T[] items) where T : ICategorizable
{
	int idx = 0;
	for (int i=0;i<items.Length;i++)
		if (items[i].Category==Category.First)
			Swap(items,i,idx++);
	for (int i=0;i<items.Length;i++)
		if (items[i].Category==Category.Second)
			Swap(items,i,idx++);
}

BTW: Ich sehe nicht wirklich, warum die Lösung von DerKleineTomy nicht linear sein soll. In jedem Schleifendurchlauf wird entweder "i" größer oder "end" kleiner. Also insgesamt "items.Length" Durchläufe.

6.862 Beiträge seit 2003
vor 12 Jahren

BTW: Ich sehe nicht wirklich, warum die Lösung von DerKleineTomy nicht linear sein soll. In jedem Schleifendurchlauf wird entweder "i" größer oder "end" kleiner. Also insgesamt "items.Length" Durchläufe.

Nicht in der Ursprungsvariante. Dort konnte es passieren das ein Item getauscht wird von i auf end und umgekehrt, end um eins verkleinert wird und dann auf i das neue Item wiederum getauscht werden muss mit dem neuen end. Damit hast du dann eine Abhängigkeit von der Ordnung der Items in der Collection, und damit keine Linearität mehr, da die Ordnung bestimmt wieviele Schleifendurchläufe notwendig sind. Das ist bei 3 möglichen Werten natürlich nicht quadratischer Aufwand, aber auch nicht linearer Aufwand.

@DerKleineTomy
Ich habe mir erlaubt den Originalcode wieder herzustellen und deine neue Variante komplett im zweiten Post aufzuführen. Wenn du den ersten Post editiert, sieht man nur schlecht aus was sich meine Antwort bezogen hat.

Baka wa shinanakya naoranai.

Mein XING Profil.

67 Beiträge seit 2011
vor 12 Jahren

Hallo,

ich habe auch mal was gebastelt:

     public static void Sort<T>(T[] items) where T : ICategorizable
        {
            int t = 0;
            T merke = items[0];
            for (int i = 1; i < items.Length; i++)
			{
			     if (items[i].Category < merke.Category)
	             {
                     items[t] =items[i];
                     items[i] = items[t+1];
                     items[t+1] = merke;
                     t++;
	             }
			}
        }
49.485 Beiträge seit 2005
vor 12 Jahren

Hallo zusammen,

das war ja einiges los. Der Reihe nach:

Die erste Lösung von inflames2k ist - wie schon von talla gesagt - nicht linear. Das Lineare war ja gerade der Gag an der Aufgabe, weil dadurch - ebenfalls schon von talla gesagt - alle Standard-Verfahren ausscheiden und man daher eine eigene Lösung ersinnen sollte.

Die erste Lösung von DerKleineTomy ist korrekt, sowohl hinsichtlich der Sortierergebnisse als auch - im Gegensatz zu dem, was talla gesagt hat - hinsichtlich der Linearität. Bei jedem Schleifendurchlauf wird entweder i erhöht oder end vermindert oder start erhöht. Die Veränderung von i oder end bewirken eine direkte Verminderung der Anzahl der verbleibenden Schleifendurchläufe um eins. Die Veränderung von Start tut das nicht, aber damit der Fall überhaupt eintreten kann, muss start < i sein. Außerdem ist i immer kleiner gleich end und end ist immer kleiner gleich items.Length. Also kann start höchstens items.Length mal erhöht werden. Im Ergebnis gibt es also maximal 2 mal items.Length Schleifendurchläufe. Konstante Faktoren spielen für die Aufwandsklasse keine Rolle. Also ist die Anzahl der Schleifendurchläufe linear zur Länge des Eingabe-Arrays.

Die zweite Lösung von inflames2k ist - wie talla gesagt hat - nicht linear. Das sieht man schon an den zwei geschachtelten Schleifen jeweils (fast) über die Länge des Eingabe-Arrays. Das ist also quadratischer Aufwand.

Die zweite Lösung von DerKleineTomy ist hinsichtlich des Sortierergebnisses nicht korrekt. Es gibt Fälle, in denen ein Element mit einer eine höhere Kategorie vor einem Element mit niedrigerer Kategorie stehen bleibt.

Die Lösung von dN!3L ist korrekt, sowohl hinsichtlich der Sortierergebnisse als auch hinsichtlich der Linearität. Auch hier werden 2 * items.Length Schleifendurchläufe benötigt, aber konstante Faktoren spielen für die Aufwandsklasse - wie schon gesagt - keine Rolle.

Die Lösung von ModelViewPresenter ist zwar linear, sortiert aber nicht korrekt. Es wird immer nur nach der (zufälligen) Kategorie des ersten Elements unterschieden.

Jetzt kann ich es ja verraten: Die Aufgabe habe nicht ich mir ausgedacht, sondern sie ist als Dutch national flag problem mehr oder weniger bekannt (offensichtlich weniger 😃. Basierend auf dem Code aus dem Wikipedia-Artikel habe ich eine Lösung geschrieben, die mit genau items.Length Schleifendurchläufen auskommt, mit anderen Worten der konstante Faktor 1 ist. Bemerkenswert daran finde ich, dass man dort mal sinnvoll sowohl die Präfix- als auch die Postfix-Variante des Inkrement-Operators einsetzen kann.

public static void Sort<T> (T [] items) where T : ICategorizable
{
   int lowerBorder = -1;
   int upperBorder = items.Length;
   for (int currentIndex = 0; currentIndex < upperBorder;) {
      switch (items [currentIndex].Category) {
         case Category.First: {
            Swap (items, currentIndex++, ++lowerBorder);
            break;
         }
         case Category.Second: {
            ++currentIndex;
            break;
         }
         case Category.Third: {
            Swap (items, currentIndex, --upperBorder);
            break;
         }
      }
   }
}

Da DerKleineTomy auf das Aufgabenrecht verzichtet hat, spreche ich dieses dN!3L zu.

herbivore

2.891 Beiträge seit 2004
vor 12 Jahren

Neue Aufgabe:

Ziel ist es, eine Vigenère-Verschlüsselung zu knacken. Sie wurde seit 1586 dokumentiert und galt bis in das 19. Jahrhundert hinein als absolut sicher.

Hierbei handelt es sich um eine Verschiebechiffre, bei der ein mehrere Buchstaben langer Schlüssel verwendet wird.
Verschlüsselt werden nur Buchstaben aus dem Alphabet (A-Z). Das Alphabet wird durchnummeriert (A=0, Z=25; Groß-/Kleinschreibung wird ignoriert) und die Buchstaben des Klartextes entsprechend dem Wert des zugehörigen Schlüsselbuchstabens verschoben/rotiert. Ist der Schlüssel kürzer als der Klartext, so wird der Schlüssel entsprechend wiederholt. ROT13 kann z.B. als Sonderfall mit der Schlüssellänge 1 angesehen werden ("N").
Zeichen, die nicht zum Alphabet gehören (z.B. Satz- & Leerzeichen) werden bei der Ver-/Entschlüsselung nicht beachtet und führen auch nicht zu einer Fortschaltung zum nächsten Schlüsselbuchstaben. Entsprechende Methoden zum Ver-/Entschlüsseln habe ich unten bereit gestellt.

Das Brechen des Schlüssels unterteilt sich in zwei Schritte:1.Ermitteln der Schlüssellänge.
Hierfür müssen verschiedene Schlüssellängen analysiert werden. Dazu wird jeder Buchstabe im Chiffrat mit dem Buchstaben in einem bestimmten Abstand verglichen. Entspricht der Abstand der tatsächlichen Schlüssellänge, dann steigt die Häufigkeit, dass zwei Buchstaben mit diesem Abstand gleich sind.
Gesucht ist also eine Zuordnung von Abständen und der Häufigkeit, mit der im Chiffrat zwei Buchstaben in diesem Abstand gleich sind. In der grafischen Darstellung ergibt sich dann ein Kamm-Muster, wobei der Abstand der Zinken der Schlüssellänge entspricht.
Zur Vereinfachung: Untersucht man die Abstände 1-20, so entspricht die tatsächliche Schlüssellänge dem Abstand mit dem höchsten Häufigkeitswert.

1.Ermitteln der einzelnen Buchstaben des Schlüssels.
Die Schlüsselbuchstaben müssen einzeln ermittelt werden. Hierfür geht man wie beim Brechen einer einfachen Verschiebechiffre vor: Man ermittelt den häufigsten Buchstaben an der entsprechenden Schlüsselposition und wählt den Schlüsselbuchstaben so, dass ein häufiger Buchstabe des Klartextes zum jenem verschoben wird. Im Fall dieser Aufgabe (ein deutscher Text) entspricht der häufigste Buchstabe immer dem 'E'.


Schreibe ein C#-Programm, mit dessen Hilfe der Schlüssel ermittelt werden kann, der zum Chiffrieren des folgenden Textes verwendet wurde:
[frame]
Gxi ssouob hmpi pschxqzu oimv, "Leeva byqw ivos Gzfpguf? Kobib rvdvh gsxxrsvwx Q++ cygasb?" (yrtv IC crof Yeib crof liydvs Cdgepis oeqw mznsf Cwt frwcfjivia). Aiasbsifu ksbrtr Fjs gsqw hnt uspfpkg iopob, qiipf Gss sef Ciqr ypysusb.

Zfdkebaassgwcsoqrsc obfbbob pys hsksghi Jfwgo axx Rmsydfdarsynoivia wsfqzxgufb kofsia. Ksrog Lielnseu xwg güf ssbtr ofghsabxro Nkoqz frtcbnsgw tfswqbtx. Vdv yyscrgf pssgemrmgkowhi rjb Pbsix zjh Vszui rjbsb Tgerts yübntr, rt kooft nrecqr gtle wwsv sxrsbqvof, tmaf Goout dh csbehoia. Hsbkihs xpsbxht mpi awd Vxpsf swxsg Tepufkabmrsgdborlr xws VWHT rjb Qyaeygffgzwtp zjh oetliaewuof Vvngwykbxqnuwcx grlefwpob, bmg D++ kooft if bpsb kpletqvowcpvdv ssbuepisf.

M# (ojwtfgdbcrlro "Q grogt") vth rss hcfusaowviaf Gdborlr güf rss .CIG Dcawcc Pnouikut Vhohwws. R# ahsrs obiabstsx, ib wvdv bkvipbt wb nwt .RRU-Zoetoivuiaqsqyah swxnjjütfb. Gss zsrobsx (ich fpzzdsc hvfg uoztkrohzsqw ehdv) Qyrt iauksnsg ma Wwgeoa G++ besf Fwhynm Pocwr wpifssptr, vo rsx atmfusb Potpyfb wch R# nrecqr utivhbsdsg. Hn ews Mcbqbo Zoxujetf Fixhxqr fwbob Zieodixyi jüe wwsvs Uyalhwybtr ipb Q# nogwgfzzd, kxvq ewscs Aehgnsshjqtfpixu xr Xbdwdsa 2, Hvf .BSD-Zpysaswdibkrcibq, bpiuff jyfvifuszvh – kse bzzoa smrksbsutr Rmsaobii, qjs tüb rxi Fqfomvt G# ipb pogdrqffsb Pthrvhixu hmae.

Und nenne den Schlüssel 😃[/frame]

Etwas Code zum Ver- und Entschlüsseln mit der Vigenère-Methode:


private static readonly string validCharacters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

public static string Encrypt(string text,string key)
{
	return Vigenere(text,key,true);
}

public static string Decrypt(string text,string key)
{
	return Vigenere(text,key,false);
}

private static string Vigenere(string text,string key,bool encrypt)
{
	StringBuilder result = new StringBuilder(text.Length);

	int keyPosition = 0;
	foreach (char c in text)
		if (!validCharacters.Contains(Char.ToUpper(c).ToString()))
			result.Append(c);
		else
		{
			result.Append(VigenereDeCrypter.Rotate(c,key[keyPosition],encrypt));
			keyPosition = ++keyPosition % key.Length;
		}

	return result.ToString();
}

public static char Rotate(char input,char offset,bool encrypt)
{
	int charIndex = validCharacters.IndexOf(Char.ToUpper(input));
	int vigenereOffset = validCharacters.IndexOf(Char.ToUpper(offset));

	char result = (encrypt) ? validCharacters[(charIndex+vigenereOffset)%validCharacters.Length] : validCharacters[(charIndex-vigenereOffset+validCharacters.Length)%validCharacters.Length];
	return (Char.IsLower(input)) ? Char.ToLower(result) : result;
}

1.029 Beiträge seit 2010
vor 12 Jahren

Hallo,

die nachfolgende Lösung ist zwar bestimmt nicht das gelbe vom Ei - funktioniert jedoch für den gegebenen Text ganz wunderbar.
(Leider musste ich einen Wert "maxKeyLength" verwenden - bei Zulassung von Keys ≥ 32 lässt sich nämlich der Text zwar erahnen - das Ergebnis wäre jedoch inkorrekt - der Aufruf meiner Klasse erfolgte mit maxKeyLength=20)

Keylänge: 8
Key: OPENBOOK

Der verschlüsselte Text lautete:

Sie fragen sich bestimmt auch, "Warum noch eine Sprache? Warum nicht weiterhin C++ nutzen?" (oder VB oder Java oder welche Sprache auch immer Sie bevorzugen). Zumindest werden Sie sich das gefragt haben, bevor Sie das Buch kauften.

Programmiersprachen koennen auf gewisse Weise mit Elektrowerkzeugen verglichen werden. Jedes Werkzeug ist für einen bestimmten Zweck besonders geeignet. Ich koennte beispielsweise ein Brett mit Hilfe einer Fraese kürzen, es waere jedoch sehr viel einfacher, eine Saege zu benutzen. Genauso koennte ich mit Hilfe einer Programmiersprache wie LISP ein Computerspiel mit aufwendiger Grafikanimation schreiben, mit C++ waere es aber wahrscheinlich einfacher.

C# (ausgesprochen "C sharp") ist die systemeigene Sprache für die .NET Common Language Runtime. C# wurde entworfen, um sich nahtlos in die .NET-Laufzeitumgebung einzufügen. Sie koennen (und sollten dies gelegentlich auch) Code entweder in Visual C++ oder Visual Basic schreiben, in den meisten Faellen ist C# jedoch geeigneter. Da die Common Language Runtime einen Kernpunkt für viele Funktionen von C# darstellt, wird diese Laufzeitumgebung in Kapitel 2, Die .NET-Laufzeitumgebung, naeher vorgestellt – vor allem diejenigen Elemente, die für die Sprache C# von besonderer Bedeutung sind.

Der "Cracker" befindet sich im Anhang.

Leider bin ich nicht erfinderisch genug mir eine eigene Aufgabe auszudenken - wer will - gibt eine neue auf 😉

Liebe Grüße
Achim

EDIT: Aufruf beispielsweise folgendermaßen:

class Program
{
	static string inputFile = @"..\..\encrypted.txt";
	static int maxKeyLength = 20;

	[STAThread]
	static void Main(string[] args)
	{
		string encryptedText = null;
		using (StreamReader sr = new StreamReader(inputFile, System.Text.Encoding.Default))
		{
			encryptedText = sr.ReadToEnd();
		}

		Cracker cracker = new Cracker(encryptedText);
		int keyLength = cracker.GetKeyLength(maxKeyLength);
		string key = cracker.GetKey(keyLength);
		Console.WriteLine("KEYLENGTH: {0}", keyLength);
		Console.WriteLine("KEY:       {0}", key);
		Console.WriteLine();
		Console.WriteLine("Decrypted Text:\r\n{0}", DeCrypter.Decrypt(encryptedText, key));
		Clipboard.SetText(DeCrypter.Decrypt(encryptedText, key));

		Console.ReadLine();
	}
}
A
764 Beiträge seit 2007
vor 12 Jahren

Als maxKeyLength könntest du auch die Länge des zu entschlüsselnden Textes nehmen.

1.029 Beiträge seit 2010
vor 12 Jahren

Hi,

das war auch mein erster Versuch - dies führt allerdings leider dazu, dass nach dem auf Wikipedia und von dN!3L beschriebenen Verfahren ein Key mit Länge 120 rauskommt, der zwar den eigentlichen Text erahnen lässt - aber definitiv das falsche Ergebnis liefert.

Da es lt. Wikipedia unmöglich ist einen Key in der selben Länge des verschlüsselten Textes zu knacken bin ich auch bei dieser Lösung geblieben und
habe somit die Anzahl möglicher Keys in einem plausiblen (falls manuell festgelegt) Rahmen.

Zugegeben: Der Aufruf meiner Methoden sollte im Normalfall alle wahrscheinlichen Keys gemeinsam mit der daraus resultierenden Übersetzung liefern um dem User die Entscheidung zu überlassen 😉

LG
Achim

2.891 Beiträge seit 2004
vor 12 Jahren

Ui, das ging ja schnell. Richtige Lösung. Sehr schön.

das war auch mein erster Versuch - dies führt allerdings leider dazu, dass nach dem auf Wikipedia und von dN!3L beschriebenen Verfahren ein Key mit Länge 120 rauskommt, der zwar den eigentlichen Text erahnen lässt - aber definitiv das falsche Ergebnis liefert.

Deshalb der Hinweis, dass die Schlüssellänge der maximalen Häufigkeit im Bereich 1-20 entspricht. Wenn der Bereich etwas größer gewählt wird, muss aus dem erwähnten Kamm-Muster der Abstand der Zinken ermittelt werden (Grafik siehe Anhang). (Das Muster entsteht, weil ja als Schlüssel "KEY", "KEYKEY", "KEYKEYKEY" usw. verwendet werden können.

Dazu müssen erst alle Kandidaten für die Zinken ermittelt werden (alle Werte größer als der Mittelwert von Durchschnitt und Maximum klappt sehr gut) und dann der Abstand, der am häufigsten vorkommt, ermittelt werden.

@Taipi88: Sehr unkonventionelle Art zu Prüfen, ob zwei Zeichen gleich sind. 😉

Ich hätte noch eine andere Entschlüsselungsaufgabe in petto.

1.029 Beiträge seit 2010
vor 12 Jahren

Vielen Dank 😉

Da ich an Entschlüsselungsaufgaben durchweg Spaß habe würde ich mich
über eine weitere Aufgabe deinerseits freuen, welche ich dann auch hiermit an dich übergebe. (sofern du diese bereits stellen möchtest)

Liebe Grüße
Achim

2.891 Beiträge seit 2004
vor 12 Jahren

Sorry, hat etwas länger gedauert, aber hier ist die nächste Aufgabe:

Diesmal geht es um das Knacken einer Permutations-Chiffre. Der Verschlüsselung findet dadurch statt, dass die Reihenfolgen der Buchstaben des Klartextes verändert (Transposition). Historisch gesehen wurde diese Verschlüsselung das erste Mal 500 v.Chr. bei Skytale von Sparta dokumentiert.

Bespiel: Der Klartext ist "Hallo", der Schlüssel ist (3 0 4 5 1 2). Das bedeutet, dass als erstes der Buchstabe an zweiter Stelle genommen wird (Wert "0" ist an zweiter Position im Schlüssel), dann der Buchstabe an fünfter Stelle (Wert "1" an Position 5 im Schlüssel), als nächstes der Buchstabe an sechster Stelle, usw. Der verschlüsselte Text ist dann "aloHl".
Wenn der Schlüssel kürzer als der Klartext ist, wird der Schlüssel wiederholt und blockweise verschlüsselt. Für den letzten Block muss der Schlüssel meist verkürzt werden.

Ein einzelner Verschlüsselungsdurchlauf an sich ist nicht als kryptographisch sicher anzusehen. Die Verkettung von zwei hintereinander ausgeführten Verschlüsselungen gilt jedoch als kryptographisch sicher, falls die Schlüssel unterschiedliche Längen haben (die ausreichend lang sind). Diese als "Doppelwürfel" bezeichnete Chiffre wurde z.B. vom Geheimdienst der ehemaligen DDR für die Kommunikation mit ihren Agenten eingesetzt.

Vorgehen zum Knacken der Verschlüsselung:
Die einzig bekannte Analysetechnik ist das Ausprobieren verschiedener Schlüssellängen/Schlüssel und eine (automatische) Bewertung des entschlüsselten Textes. Hierfür kann man aufeinander folgender Buchstabenpaare/-folgen ermitteln und bewertet deren Wahrscheinlichkeit.

Die Herausforderung ist nun, eine gute Bewertungsfunktion zu finden. Hierfür können Besonderheiten der Formatierung (Groß-/Kleinschreibung, Satzzeichen) verwendet werden. Ebenso die Häufigkeiten von Buchstabenfolgen in Texten der Sprache.


Finde den (kürzesten) Schlüssel, mit dem der folgende (deutsche) Text nach dem Permutationschiffre-Verfahren verschlüsselt wurde:
[csharp]
eäu gli eurrnErAln(u edskhgcrsicperga relsxue rsrkg,beotaRü niz Rrdxoegg x pEeeerdnsi  I feti) nei akerZiintmo ed,tnteheed keci behBcrrns ie eugvng neoneZ Mnvo ntehktimnteece iisbl eHmeetfi mtcikyat et snsrhrtede ie nenlgR.RrsAä uuceedrlgük o nnvfleerdi alfSrne  wdro imtaguktcleVirnwne erf;dg efnsüunw aroPl r meiglatamenhpceriat rsexsmlmeIpen ienrietgR.nn rleregueuä küurc ödnesAeknelFa inksitl erre ii ne nedertrTwe uevtnhercsxedn nee, ed irwtdmtmt x edemiTrd e e srdMeeustu rgudueAsäk  rnrlcs eceihbildnggawrrVrie  asgoeD.gnPhuracwt e di at nhMcinetaga rgn s .oinsSbt tne sesplwi eöiiseem lac llö,tehigWrrnea irWsreu e ourhs elzesatitsumede ict,S nhui n egnnb nuuie da  e dn hne–eDfoncizeawdedls i hncBnee esdaungihtla  dweenshunbwian enA leezrdeh go itvpbinrzlxee ns seziü .mu EniBste epreeeiwsii eüdn s tErflnartilFl i tesaz shigeöldeMtc i kiriiolz epTemk,t guteezxnsdnrtee nrühfhr ueezcu.Ngu  naefehfdnbeüiyannltcaet ershknbuae nge fAnönAeäelr sur grnude ceuhcwanv küre nd reemeM,wtdu ö oevnnt rWngereeuzure ,eog znn o e dsnteeWjehr bgae nnnnzelzie o nüe. lssSsmu äse shbticlii speAnei iwser sesud,ee gbcdnrnaku egrniiebgeb  e eeaianMxn-(Zm eel)lanhazianlhece l eaebr ekcnndeZiiaikbnenmntonhoe "eWtr(rre)ö" eztme,i gSdbi tu   n nnugie dniemtfA.nn  deeudeD inkeWs eei öe snnaesayttiscm wetsrAl-i- saedMEhesmlav l drreo(n ee oivrT  )dle m@aSnre f-dep ü mVieengnsr  rdaret.nderew
[/csharp]

EDIT: Chiffrat korrigiert (mehrere Leerzeichen hintereinander wurden nicht angezeigt).

Da die letzte Verschlüsselungsaufgabe so gut und schnell geklappt hat, spare ich mir diesmal erst ein mal ein paar zusätzliche Hinweise (die ich aber bei Bedarf gern nachliefere) und gebe euch nur die Methoden zur Ver- und Entschlüsselung:


public static string Encrypt(string text,params int[] key)
{
	return Permute(text,key,true);
}

public static string Decrypt(string text,params int[] key)
{
	return Permute(text,key,false);
}

private static string Permute(string text,int[] key,bool useInvertedKey)
{
	StringBuilder stringBuilder = new StringBuilder(text.Length);

	int[] actualKey = (useInvertedKey) ? InvertKey(key) : key;
	for (int sequenceStart=0;sequenceStart<=text.Length-actualKey.Length;sequenceStart+=actualKey.Length)
		for (int sequenceOffset=0;sequenceOffset<actualKey.Length;sequenceOffset++)
			stringBuilder.Append(text[sequenceStart+actualKey[sequenceOffset]]);

	string remainingText = text.Substring(stringBuilder.Length);
	if (remainingText.Length>0)
	{
		int[] remainingKey = key.Where(value => value<remainingText.Length).ToArray();
		stringBuilder.Append(Permute(remainingText,remainingKey,useInvertedKey));
	}

	return stringBuilder.ToString();
}

private static int[] InvertKey(int[] key)
{
	return Enumerable.Range(0,key.Length).Select(i => Array.IndexOf(key,i)).ToArray();
}

1.029 Beiträge seit 2010
vor 12 Jahren

Hallo,

also ich hab mir das jetzt mal angeschaut - und denke ich brauche ein wenig Hilfe bzw. eher eine Info was die Machbarkeit angeht^^

Meine derzeitige Annahmen:

  1. Es ist erforderlich alle Permutationen zu berechnen (Brute-Force).
    (Das lese ich zumindest aus der von dir genannten Vorgehensweise...)
  2. Es handelt sich um einen Text, der mit einem Großbuchstaben begann.

Sollten beide Annahmen zutreffen stellt sich für mich ein kleines Problem, denn
der Key ist mindestens 14 Stellen (E an 14ter Stelle ist der erste Großbuchstabe) - das sind 87178291200 zu probierende Permutationen, wenn der Key exakt 14 Stellen hat. Da mein Programm aktuell 35-40k Berechnungen pro Sekunde schafft (ich prüfe noch nur auf Großbuchstaben am ersten Zeichen und Punkte am letzten Zeichen) würde das eine Berechnungsdauer von nunjaaaa... ca. 1 Monat ergeben 😉

Es wäre nett, wenn du eine der beiden Annahmen vernichtend in den Boden stampfst^^ (Je öfter ich deine Aufgabenstellung betrachte desto mehr lese ich BruteForce heraus...)

Liebe Grüße
Achim

2.891 Beiträge seit 2004
vor 12 Jahren

Es ist erforderlich alle Permutationen zu berechnen (Brute-Force). (Das lese ich zumindest aus der von dir genannten Vorgehensweise...) [...] (Je öfter ich deine Aufgabenstellung betrachte desto mehr lese ich BruteForce heraus...)

Ja, man muss ein BruteForce über die Schlüssellängen machen. Und ja, man muss auch ein BruteForce über die Schlüssel machen - der Trick ist allerdings, dass man das nicht über absolute Schlüsselpositionen macht, sondern über relative Schlüsselpositionen. Man probiert also nicht beispielsweise bei Länge 3 alle Schlüssel (1,2,3), (1,3,2), (2,1,3), (2,3,1), usw. aus, sondern nur, ob es möglich ist, dass Position 2 auf 1 folgt, 3 auf 2, 1 auf 3 usw. Anhand dieser Möglichkeiten generiert man dann danach die Schlüssel(kandidaten).

~~er Key ist mindestens 14 Stellen [...] würde das eine Berechnungsdauer von nunjaaaa... ca. 1 Monat ergeben
Jep, mindestens 14 Stellen. Meine Version schafft es in unter einer Sekunde.

2.891 Beiträge seit 2004
vor 12 Jahren

Da die Lösung der Aufgabe mittlerweile noch nicht weiter fortgeschritten ist, hier ein paar weitere Hilfen:

Das Problem lässt dich reduzieren auf die Analyse von Buchstabenpaaren, die im entschlüsselten Text entstehen. Dadurch muss man auch kein BruteForce über alle Schlüssel machen, sondern nur über mögliche relative Schlüsselpositionen.

Dazu erstellt man pro zu überprüfender Schlüssellänge eine quadratische Matrix mit Kantenlänge=Schlüssellänge und ermittelt für alle Paare, ob/wie wahrscheinlich es ist, dass diese beiden Positionen im Schlüssel nacheinander kommen.

Diese Matrix kann man dann zu einer binären Matrix degradieren (Position x folgt/folgt nicht auf y) und daraus die eigentlichen Schlüssel generieren.

Folgenden Programmrahmen gebe ich euch dazu:


public static void Main(string[] args)
{
	string text = @"...";

	var ratingFunctions = new Func<char,char,double>[]
	{
		// TODO: Bewertungsfunktion(en) für Buchstabenpaare
		// (firstChar,secondChar) => (true) ? 1 : 0,
		// (firstChar,secondChar) => (false) ? -1 : 0,
	};

	var keyKandidates = Enumerable.Range(1,30)
		.Select(length => GenerateKeyposBigramProbabilityMatrix(length,text,ratingFunctions))
		.SelectMany(matrix => GenerateKeys(matrix));

	foreach (int[] key in keyKandidates)
	{
		Debug.WriteLine(String.Join(",",key));
		Debug.WriteLine(Decrypt(text,key));
	}
}

private static double[,] GenerateKeyposBigramProbabilityMatrix(int keyLength,string text,IEnumerable<Func<char,char,double>> ratingFunctions)
{
	double[,] result = new double[keyLength,keyLength];

	// alle Varianten von aufeinanderfolgenden Schlüsselpositionen durchgehen
	for (int firstIdx=0;firstIdx<keyLength;firstIdx++)
		for (int secondIdx=0;secondIdx<keyLength;secondIdx++)
			if (firstIdx!=secondIdx)
			{
				// alle Buchstabenpaare für diese Schlüsselpositionen im Text suchen...
				for (int sequenceStart=0;sequenceStart<=text.Length-keyLength;sequenceStart+=keyLength)
				{
					char firstChar = text[sequenceStart+firstIdx];
					char secondChar = text[sequenceStart+secondIdx];
					// ... und bewerten
					foreach (var func in ratingFunctions)
						result[firstIdx,secondIdx] += func(firstChar,secondChar);
				}
			}

	return result;
}

private static IEnumerable<int[]> GenerateKeys(double[,] keyposBigramProbabilityMatrix)
{
   // TODO: Anhand der Wahrscheinlichkeitsmatrix die möglichen Schlüssel generieren
}

Tipp: Man kann die Buchstabenpaare anhand der Häufigkeit ihres Auftretens in der (deutschen) Sprache bewerten ("Bigramm-Wahrscheinlichkeiten") - sehr effektiv sind aber auch generische Bewertungsfunktionen, die z.B. das Auftreten von Satzzeichen analysieren.

309 Beiträge seit 2008
vor 12 Jahren

Gelöst!

Danke, den Wink mit dem Zaunpfahl (Stichwort "Matrix"), hab ich gebraucht. 😉

Ein regulärer Ausdruck (englisch regular expression, abgekürzt RegExp oder Regex) ist in der Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient. Reguläre Ausdrücke finden vor allem in der Softwareentwicklung Verwendung; für fast alle Programmiersprachen existieren Implementierungen. Reguläre Ausdrücke können als Filterkriterien in der Textsuche verwendet werden, indem der Text mit dem Muster des regulären Ausdrucks abgeglichen wird. Dieser Vorgang wird auch Pattern Matching genannt. So ist es beispielsweise möglich, alle Wörter aus einer Wortliste herauszusuchen, die mit S beginnen und auf D enden – ohne die dazwischenliegenden Buchstaben und wahlweise deren Anzahl explizit vorgeben zu müssen. Ein weiteres Beispiel für den Einsatz als Filter ist die Möglichkeit, komplizierte Textersetzungen durchzuführen. Neben den aufgeführten analytischen Aufgaben können reguläre Ausdrücke auch verwendet werden, um Mengen von Wörtern zu erzeugen, ohne jedes Wort einzeln angeben zu müssen. So lässt sich beispielsweise ein Ausdruck angeben, der bei einer gegebenen (Maximal-)Zeichenanzahl alle denkbaren Zeichenkombinationen ("Wörter") erzeugt, die mit S beginnen und mit D enden. Auf diese Weise können etwa systematisch E-Mail-Adressen (vor allem der Teil vor dem @) für den Spam-Versand generiert werden.

Schlüssel: 13 6 12 3 11 8 4 2 5 1 10 0 14 7 15 9

Den Code kann man sicherlich mit Linq eleganter lösen. 😁
Dafür zeigt er sofort den gesuchten Schlüssel an und erzeugt nicht nur Schlüsselkandidaten.
Recht flott ist das ganze auch noch, auf meinen altersschwachen Laptop braucht der Code für den o.g. Text knapp unter 500 ms.

Die Häufigkeitsanalyse der Buchstabenpaare ist simpel aber effektiv. Durch die Gewichtung kann man nachher in der Matrix sehr schön die statistischen "Ausreißer" nach oben, sprich gegen 0, herausfiltern. Das sind die gesuchten Schlüsselpositionen. Sollte es keine statistisch relevanten Ausreißer geben, sind also alle Werte für eine Position in etwa gleich, hat man entweder die letzte Position gefunden, oder die Schlüssellänge ist falsch.


static string cryptedText = "...";

 static void Main(string[] args)
 {

	 Stopwatch stopwatch = new Stopwatch();
	 stopwatch.Start();

	 var ratingFunctions = new List<Func<char, char, double>>
	  {
		  { new Func<char, char, double>(Bigram) }
	  };

	 for (int i = 0; i < 30; i++)
	 {
		 int[] key;
		 if (FindKey(out key, GenerateKeyposBigramProbabilityMatrix(i, cryptedText, ratingFunctions)))
		 {
			 stopwatch.Stop();
			 Console.WriteLine(Decrypt(cryptedText, key));
			 Console.Write("Schlüssel: ");
			 foreach (int k in key)
				 Console.Write(k + " ");
			 Console.WriteLine();
			 Console.WriteLine("Benötigte Rechenzeit: " + stopwatch.ElapsedMilliseconds + " ms");

			 break;
		 }
	 }

	 Console.ReadKey();
 }

 // Gewichtete Häufigkeit von Buchstabenpaaren
 static Dictionary<string, double> bigramFrequenzy = new Dictionary<string, double>()
 {
	 {"EN",    3.97},
	 {"ER",    3.93},
	 {"CH",    2.70},
	 {"EI",    2.15},
	 {"DE",    2.04},
	 {"IN",    2.03},
	 {"TE",    1.86},
	 {"IE",    1.66},
	 {"UN",    1.35},
	 {"GE",    1.31},
	 {"ES",    1.30},
	 {"ST",    1.29},
	 {"ND",    1.25},
	 {"BE",    1.16},
	 {"AN",    1.13},
	 {"RE",    1.13},
	 {"NE",    1.08},
	 {"HE",    1.04},
	 {"IC",    1.00},
	 {"DI",    0.99}
 };
 static double Bigram(char c1, char c2)
 {
	 string bigram = String.Concat(c1, c2).ToUpper();
	 foreach (KeyValuePair<string, double> freq in bigramFrequenzy)
	 {
		 if (bigram == freq.Key)
			 return freq.Value;
	 }

	 return -1;
 }

 private static double[,] GenerateKeyposBigramProbabilityMatrix(int keyLength, string text, IEnumerable<Func<char, char, double>> ratingFunctions)
 {
	// ...siehe oben
 }

 private static bool FindKey(out int[] key, double[,] keyposBigramProbabilityMatrix)
 {
	 int keyLength = (int)Math.Sqrt(keyposBigramProbabilityMatrix.Length);

	 // Schlüsselläbge von 1 übergehen
	 if (keyLength == 1)
	 {
		 key = null;
		 return false;
	 }

	 List<int[]> candidateKey = new List<int[]>();
	 int lastDigitInKey = 0;

	 for (int i = 0; i < keyLength; i++)
	 {
		 // Durchschitt der Möglichkeiten für Nachfolger für aktuelle Stelle berechnen
		 Dictionary<int[], double> probDigit = new Dictionary<int[], double>();
		 double average = 0;
		 double max = double.MinValue;
		 int digit = 0;
		 int child = 0;

		 for (int j = 0; j < keyLength; j++)
		 {
			 if (keyposBigramProbabilityMatrix[i, j] != 0)
			 {
				 average += keyposBigramProbabilityMatrix[i, j];

				 if (keyposBigramProbabilityMatrix[i, j] > max)
				 {
					 max = keyposBigramProbabilityMatrix[i, j];
					 digit = i;
					 child = j;
				 }
			 }
		 }

		 average /= keyLength - 1;

		 // Größter statistischer "Außreißer" -> Postition gefunden
		 if (max * 1.5 > average)
		 {
			 candidateKey.Add(new int[] {digit, child});
		 }
		 else // Kein Außreißer: letzte Position oder falsche Position
			 lastDigitInKey = i;
	 }


	 // Schlüssel gefunden, zusammensetzen
	 if (candidateKey.Count + 1 == keyLength)
	 {
		 key = new int[keyLength];
		 key[0] = lastDigitInKey;
		 int curDigit = lastDigitInKey;

		 for (int k = 1; k < keyLength; k++)
		 {
			 curDigit = FindNextDigit(curDigit, candidateKey);
			 key[k] = curDigit;
		 }

		 Array.Reverse(key);
		 return true;
	 }

	 key = null;
	 return false;
 }

 static int FindNextDigit(int i, List<int[]> probDigits)
 {
	 foreach (int[] digits in probDigits)
	 {
		 if (i == digits[1])
			 return digits[0];
	 }

	 return 0;
 }

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

2.891 Beiträge seit 2004
vor 12 Jahren

Und die nächste Aufgabe geht an: Scavanger. 😃

Hier meine Lösung:


var ratingFunctions = new Func<char,char,double>[]
{
	// Abwertung, wenn ein Großbuchstabe auf einen Kleinbuchstaben folgt
	(firstChar,secondChar) => (Char.IsLower(firstChar) && Char.IsUpper(secondChar)) ? -1 : 0,
	// Aufwertung, wenn ein Großbuchstabe auf ein Leerzeichen folgt
	(firstChar,secondChar) => (Char.IsWhiteSpace(firstChar) && Char.IsUpper(secondChar)) ? 1 : 0, 
};

// ...

private static IEnumerable<int[]> GenerateKeys(double[,] keyposBigramProbabilityMatrix)
{
	for (int i=0;i<keyposBigramProbabilityMatrix.GetLength(0);i++)
		foreach (int[] key in GenerateKeys(keyposBigramProbabilityMatrix,new[] { i }))
			yield return key;
}

private static IEnumerable<int[]> GenerateKeys(double[,] keyposBigramProbabilityMatrix,int[] keyPrefix)
{
	int length = keyposBigramProbabilityMatrix.GetLength(0);

	int firstIdx = keyPrefix.Last();
	for (int secondIdx=0;secondIdx<length;secondIdx++)
		if (!keyPrefix.Contains(secondIdx))
			if (keyposBigramProbabilityMatrix[firstIdx,secondIdx]>0)
			{
				int[] newPrefix = keyPrefix.Concat(new[] { secondIdx }).ToArray();

				if (newPrefix.Length==length)
					yield return newPrefix;
				else
					foreach (int[] key in GenerateKeys(keyposBigramProbabilityMatrix,newPrefix))
						yield return key;
			}
}

Was mir aufgefallen ist: Sobald man Bigrammwahrscheinlichkeiten mit ins Spiel bringt, bekommt man mehr Schlüsselkandidaten zurückgeliefert. Mit den beiden simplen von mir verwendeten Regeln bleibt bei ziemlich vielen Texten nur ein einziger Kandidat übrig (der dann auch der Schlüssel ist).

309 Beiträge seit 2008
vor 12 Jahren

OK,

mit fällt gerade nicht besseres ein als eine kleine Fingerübung:

Erstelle eine Implementierung eines Pseudozufallsgenerator in (max.) 1,5 Programmzeilen.
Wobei die "halbe" Programmzeile nur eine Variablendeklaration sein darf.
Die Methodensignatur zählt natürlich nicht.

Edit:
Noch ein paar Informationen (und auf 1,5 Zeilen angehoben, hab zu schnell gepostet und nicht nachgedacht. 😉)
Als Argumente soll mind. ein Seed angegeben werden. Gleichverteilung über den Werteberich sollte gegeben sein und der Wertbereich sollte einige Millionen groß sein.

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

D
81 Beiträge seit 2009
vor 12 Jahren

Ich hoffe es ist nicht zuviel Code 😕


        static long rnd = DateTime.Now.Ticks;

        static void Main(string[] args)
        {
            for (int i = 0; i < 10; i++)
            {
                Console.WriteLine(i + ": " + get_random);
            }
            Console.ReadLine();
        }

        static long get_random
        {
            get
            {
                rnd = (rnd * 110671L + 1263L) & 167215L;
                return rnd;
            }
        }

lg Daniel

309 Beiträge seit 2008
vor 12 Jahren

Ja, ist mir zu viel Code. :evil:

Außerdem erzeugt dein Generator keine gleich verteilten Zufallszahlen. Periodisch alle 16 Aufrufe kommt z.B. die 0.

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo,

hier meine Lösung als Einzeiler, eine zusätzlche Variable wird nicht benötigt 8)

    public static uint Rnd(uint seed, int idx)
    {
      return idx < 0 ? seed : (253 * Rnd(seed, idx - 1) + 3) % 16777216;
    }

Die Werte sind so gewählt, dass kein Überlauf stattfinden kann. Das hat den kleinen Nachteil, dass bei sehr kleinen Seed zunächt immer ein paar relativ kleine Zahlen kommen.

Der Wertebereich geht von 0 bis 16777216. Der Parameter idx gibt an, die wievielte Zufallszahl man zum übergebenen Seed erhalten möchte.
Aufgrund der Einschränkungen aus der Aufgabenstellung wird das mit der Rekursion bei mehrfachen Aufrufen mit steigendem Index zwar etwas Schlemiel the Painter-mäßig... trotzdem hier noch das Testprogramm für die Gleichverteilung:

    public static void Main()
    {
      uint res;
      uint seed = 5;
      int lesser = 0;
      int greater = 0;
      int inner = 0;
      int max = 16777216;
      int interval = 100000;
      int i = 0;
      while(i < 100000)
      {
        res = Rnd(seed, i);
        if(res < interval)
        {
          lesser++;
        }
        if(res > max -interval)
        {
          greater++;
        }
        if((res > max/2 -interval/2) && (res < max/2 + interval/2))
        {
          inner++;
        }
        Console.CursorLeft = 0;
        Console.Write("i:{0} lesser:{1} inner:{2} greater:{3}", i, lesser, inner, greater);
        i++;
      }
      Console.WriteLine("done");
      Console.Read();
    }

Gruß, MarsStein

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

309 Beiträge seit 2008
vor 12 Jahren

Perfekt gelöst! 👍

Noch meine Version in 1,5 Zeilen:


static long x;
static long randLCM(long seed)
{
        return (x = (526 * ( seed != 0 ? x = seed : x) + 121441) % 7441875);
}

Das ganze ist ein Linearer Kongruenzgenerator

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo zusammen,

hier also die neue Aufgabe, es geht mal wieder um Rekursion (diesmal mit erweiterten Abbruchbedingungen von aussen).

Implemetiert anhand des gegebenen Codes eine Erweiterungsmethode zu IEnumerable, die selbiges als Wurzelknoten eines Baumes auffasst und rekursiv durchsucht.

Finden sich also innerhalb des Wurzelobjekts weitere IEnumerables, müssen diese als Zweig ebenfalls vollständig durchlaufen werden, usw.
Jedes Objekt im Baum (egal ob Zweig oder Blatt) muss dabei an den Func-Delegaten, den die Erweiterungsmethode als Parameter erhält, übergeben werden. Dieser kann das Objekt auswerten und anhand seines Rückgabewertes aus der NodeResult-Enumeration über das weitere Verhalten des Suchlaufs entscheiden.
Was die einzelnen Werte aus NodeResult bewirken sollen, könnt Ihr den Codekommentaren entnehmen.

Fehlerbehandlung und Prüfungen auf null könnt Ihr Euch sparen.

Tipp: Die Tatsache, dass die Erweiterungsmethode selbst ein NodeResult zurückgibt, dürfte für den Aufrufer unerheblich sein, für die Implementierung aber nicht.

public enum NodeResult
{
  // normal weiterlaufen
  Continue,

  // Suchlauf abbrechen
  Exit,
  
  // im aktuellen Knoten enthaltene Objekte überspringen
  SkipContained,
  
  // Nachbarknoten des aktuellen Knotens überspringen
  SkipSiblings,

  // Kombination aus SkipContained und SkipSiblings
  SkipContainedAndSiblings,
}

public static class EnumerableSearchExtension
{
  public static NodeResult SearchAsTree(this IEnumerable root, Func<object, NodeResult> evaluateNode)
  {
    //*****************************
    //* hier eure Implementierung *
    //*****************************
  }
}

Die Aufgabe lässt sich bei normaler Schreibweise mit weniger als 30 Zeilen Code lösen (das ist aber nicht erforderlich).

Viel Spass dabei,
MarsStein

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

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo nochmal,

auf Hinweis von herbivore habe ich mal eine kleine Testklasse gebaut, zur Veranschaulichung der Aufgabenstellung - ihr könnt die Klasse auch direkt zum testen Eurer Implementierung verwenden. Sie implementiert verschiedene Methoden, die nacheinander an die zu schreibende Methode übergeben werden. Dabei werden die Vorkommen der im Wurzelobjekt vorhandenen Typen gezählt.
Je nach verwendeter Implementierung erhält man dabei unterschiedliche Ergebnisse, da die einzelnen Implementierungen das Verhalten der Hauptmethode beeinflussen:

class TypeCounter
{
  Dictionary<Type, int> typeDict = new Dictionary<Type, int>();
  
  public void Print(string head)
  {
    Console.WriteLine();
    Console.WriteLine(head);
    Console.WriteLine("------------------");
    foreach(Type key in typeDict.Keys)
    {
      Console.WriteLine("{0}: {1}", key, typeDict[key]);
    }
  }
  
  public NodeResult ReInit(object o)
  {
    typeDict[o.GetType()] = 0;
    return NodeResult.Continue;
  }
  
  public NodeResult ContinueAll(object o)
  {
    typeDict[o.GetType()] ++;
    return NodeResult.Continue;
  }
  
  public NodeResult ExitOnInt3(object o)
  {
    NodeResult res = ContinueAll(o);
    return 3.Equals(o) ? NodeResult.Exit :res;
  }
  
  public NodeResult SkipContainedOfIntArray(object o)
  {
    NodeResult res = ContinueAll(o);
    return o is int[] ? NodeResult.SkipContained : res;
  }
  
  public NodeResult SkipSiblingsOfCharR(object o)
  {
    NodeResult res = ContinueAll(o);
    return 'r'.Equals(o) ? NodeResult.SkipSiblings : res;
  }
  
  public NodeResult SkipContainedAndSiblingsOfCharArray(object o)
  {
    NodeResult res = ContinueAll(o);
    return o is char[] ? NodeResult.SkipContainedAndSiblings : res;
  }
  
  public static void Main()
  {
    object[] root = { 
      new object(),
      new int[] { 1, 2, 3, 4 },
      new object(),
      new char[] { 's', 't', 'r', 'i', 'n', 'g' },
      new object() 
    };
    
    TypeCounter tc = new TypeCounter();
    
    root.SearchAsTree(tc.ReInit);
    root.SearchAsTree(tc.ContinueAll);
    tc.Print("ContinueAll");
    
    root.SearchAsTree(tc.ReInit);
    root.SearchAsTree(tc.ExitOnInt3);
    tc.Print("ExitOnInt3");
    
    root.SearchAsTree(tc.ReInit);
    root.SearchAsTree(tc.SkipContainedOfIntArray);
    tc.Print("SkipContainedOfIntArray");
    
    root.SearchAsTree(tc.ReInit);
    root.SearchAsTree(tc.SkipSiblingsOfCharR);
    tc.Print("SkipSiblingsOfCharR");
    
    root.SearchAsTree(tc.ReInit);
    root.SearchAsTree(tc.SkipContainedAndSiblingsOfCharArray);
    tc.Print("SkipContainedAndSiblingsOfCharArray");
    
    Console.Read();
  }
}

Das Ergebnis sieht dann so aus:

ContinueAll
------------------
System.Object[]: 1
System.Object: 3
System.Int32[]: 1
System.Int32: 4
System.Char[]: 1
System.Char: 6

ExitOnInt3
------------------
System.Object[]: 1
System.Object: 1
System.Int32[]: 1
System.Int32: 3
System.Char[]: 0
System.Char: 0

SkipContainedOfIntArray
------------------
System.Object[]: 1
System.Object: 3
System.Int32[]: 1
System.Int32: 0
System.Char[]: 1
System.Char: 6

SkipSiblingsOfCharR
------------------
System.Object[]: 1
System.Object: 3
System.Int32[]: 1
System.Int32: 4
System.Char[]: 1
System.Char: 3

SkipContainedAndSiblingsOfCharArray
------------------
System.Object[]: 1
System.Object: 2
System.Int32[]: 1
System.Int32: 4
System.Char[]: 1
System.Char: 0

Eure Lösung wird auch akzeptiert, wenn jeweils die oberste Zeile (System.Object[]: 1) fehlt, das Root-Objekt selbst also nicht an den jeweiligen Delegaten übergeben wird.

Gruß, MarsStein

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

D
96 Beiträge seit 2012
vor 12 Jahren

So hab die Aufgabe gelöst, allerdings wird das Root-Objekt nicht an den Delegaten übergeben.


public static NodeResult SearchAsTree(this IEnumerable root, Func<object, NodeResult> evaluateNode)
        {
            Boolean skip = false;
            foreach (var child in root)
            {
                if (skip)
                {
                    //skip = false;
                    //continue;
                    break; // <-- Editiert!
                }
                NodeResult result = evaluateNode(child);

                if (result == NodeResult.Exit)
                    return NodeResult.Exit;

                if (result == NodeResult.SkipSiblings || result == NodeResult.SkipContainedAndSiblings)
                    skip = true;

                IEnumerable childNode = child as IEnumerable;
                if (childNode != null)
                {
                    if (result != NodeResult.SkipContained && result != NodeResult.SkipContainedAndSiblings)
                        if (childNode.SearchAsTree(evaluateNode) == NodeResult.Exit)
                            return NodeResult.Exit;
                }
            }

            return NodeResult.Continue;
        }

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo DerKleineTomy,

Deine Lösung ist fast richtig. Allerdings werden die Nachbarknoten bei SkipSiblings nicht alle übersprungen.

Bei Deiner Lösung ensteht:

SkipSiblingsOfCharR
------------------
System.Object: 3
System.Int32[]: 1
System.Int32: 4
System.Char[]: 1
System.Char: 5

Die letzte Zeile müsste aber lauten

System.Char: 3

Um das zu korrigieren, musst Du aber nur eine Zeile in Deinem Code ändern (kannst es ja oben reineditieren, und die Stelle nochmal kenntlich machen).

Gruß, MarsStein

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

D
96 Beiträge seit 2012
vor 12 Jahren

Hmm, irgendwie hab ich da wohl einen Denkfehler. Ich hoffe das kann mir jemand erklären:

  1. Wenn bei "string" die Elemente rechts und links vom 'r' übersprungen werden, müsste das Ergebnis doch 4 und nicht 3 sein oder?

  2. Da die Elemente der Reihe nach ausgewertet werden (vom 's' bis zum 'g') wird das 't' immer ausgewertet bevor bei 'r' SkipSiblings zurückgegeben wird oder gibt es da irgendeinen Kniff 🤔 Denn bereits bei 't' könnte SkipSiblings zurückgegeben werden und somit das 'r' übersprungen, was dann zur Folge hätte, dass ich das 't' vor dem 'r' auswerten muss.

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo DerKleineTomy,

  1. Wenn bei "string" die Elemente rechts und links vom 'r' übersprungen werden, müsste das Ergebnis doch 4 und nicht 3 sein oder?

Es geht bei der Aufgabe ja darum, dass man die Rekursion in der Hauptmethode mittels der Delegaten steuern kann, damit man nicht jedes Element durchsuchen muss, wenn man anhand eines Knotens bereits (im Delegaten) erkennen kann, dass einen z.B. der Inhalt oder auch die Nachbarknoten nicht mehr interessieren.

Es ist also so gemeint, dass man nur die folgenden Nachbarn überspringt, die vorhergehenden hat man ja ohnehin schon ausgewertet. Somit werden in der Testmethode 's', 't' und 'r' ausgewertet, und der Rest des char[] übersprungen => daher die 3.

Denn bereits bei 't' könnte SkipSiblings zurückgegeben werden Die Testmethode ist aber nunmal so geschrieben, dass sie bei 'r' SkipSiblings zurückgibt.
Wäre sie so geschrieben, dass beireits beim 't' SkipSiblings zurückgegeben würde, müsste das 'r' bereits übersprungen werden und das Ergebnis für char wäre 2.

Gruß, MarsStein

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

D
96 Beiträge seit 2012
vor 12 Jahren

Ah, jetzt versteht ichs 🙂. Hab gedacht NUR die aktuellen Nachbarn werden übersprungen 😁

Edit: Hab den Code editiert.

3.170 Beiträge seit 2006
vor 12 Jahren

Hallo DerKleineTomy,

jetzt passt es 👍
Du bist dran!

Gruß, MarsStein

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

D
96 Beiträge seit 2012
vor 12 Jahren

Die Aufgabe ist es einen nichtdeterministischen Kellerautomaten (Push Down Automaton) zu programmieren. Er funktioniert so:


1) Er besitzt einen Stack (dieser ist am Anfang leer)
2) Er besitzt beliebig viele Zustände (q0, q1, ..., qn)
  - Einen Startzustand
  - Mindestens einen Endzustand
3) Jeder Zustand kann beliebig viele Zustandsübergänge haben (Auch wieder zu sich selbst)
4) Ein Übergang hat 3 Parameter (input, onStack, output)
- input => Der momentan betrachtete Buchstabe
- onStack => Der Buchstabe auf dem Stack (keiner ist auch möglich)
- output => Die Buchstaben (also auch mehrere), die auf den Stack gelegt werden, wenn der Zustand gewechselt wird.
- Der Übergang ist möglich, wenn der aktuell betrachtete Buchstabe == <input> ist und auf dem Stack <onStack> liegt. Wird der Übergang benutzt, wird <output> auf den Stack gelegt
- Wenn <input> leer ist ("" oder null) kann der Übergang immer (!) benutzt werden. In diesem Fall wird <onStack> ignoriert und auch nichts vom Stack entfernt. <output> wird ganz normal auf den Stack gelegt. Dieser Übergang ist eine Epsilonübergang.
5) Eine Eingabe (Wort) ist gültig, wenn zu jedem Buchstaben im Wort ein Übergang gegangen wurde, der Stack leer ist und der momentane Zustand ein Endzustand ist
6) Es kann auch mehrere mögliche Zustandsübergänge geben. Wenn mindestens (!) einer das Wort als gültig ansieht, ist es gültig.

Hier ist eine Codevorgabe

public class PushDownAutomaton
    {
        private Stack<String> stack = new Stack<String>();
        public State StartState;
        public List<State> FinalStates = new List<State>();

        public Boolean CheckWord(List<String> word)
        {
            stack.Clear();
            return StartState.ChangeState(word, 0, stack, FinalStates);
        }

    }

    // =================
    public class State
    {
        public List<Transition> Transitions = new List<Transition>();

        // input => Wort
        // index => Der aktuelle Buchstabe im Wort
        // stack => Der Stack
        // finalStates => Die Endzustände
        // Gibt <true> zurück, wenn das Wort abgearbeitet ist, der Stack leer ist und der letzte Zustand ein Endzustand war
        public Boolean ChangeState(List<String> input, Int32 index, Stack<String> stack, List<State> finalStates)
        {
              // Hier kommt euer Code hin
        }

    }

    // =================
    public class Transition
    {
        public String Input;
        public String OnStack;
        public List<String> Output = new List<String>();
        public State NextState;

        public readonly Boolean IsEpsilon;

        public Transition(String input, String onStack, State nextState, params String[] output)
        {
            Input = input;
            OnStack = onStack;
            NextState = nextState;

            IsEpsilon = String.IsNullOrEmpty(input);

            if (output != null)
                Output.AddRange(output);

        }

        // Überprüft, ob alle Bedingungen für den Zustandswechsel erfüllt sind.
        public Boolean CheckConditions(String input, Stack<String> stack)
        {
            if (String.IsNullOrEmpty(Input)) // Epsilonübergang
                //return Peek(OnStack, stack); // FEHLER BEHOBEN!!!
                return true;
            else // Normaler Übergang
                return Input == input && Peek(OnStack, stack);
        }

        // Kleine Hilfsmethode 
        private static Boolean Peek(String str, Stack<String> stack)
        {
            // Auf dem Stack darf nichts liegen, wenn <str> leer ist
            if (String.IsNullOrEmpty(str))
                return stack.Count == 0;

            // Ist <str> nicht leer, dann muss <str> auf dem Stack liegen
            return stack.Count > 0 && stack.Peek() == str;
        }
    }

Ich hoffe die ganzen Erklärungen schrecken euch nicht ab 😛. Es sind nicht mal 30 Zeilen Code nötig ⚠

D
96 Beiträge seit 2012
vor 12 Jahren

Weil es anscheinend nicht voran geht und Herbivore mich gebeten hat ein paar Sachen zu klären:

  1. Warum bekommt ChangeState eine List<String> und keinen normalen String:
    Ich wollte die Freiheit lassen, "Buchstaben" zu benutzen, die mehr als einen Zeichen lang sind. Wer will kann gerne einen normalen String nutzen und die einzelnen Chars durchgehen.

  2. Endzustände sind wie alle anderen Zustände zu behandeln. Der einzige Unterschied ist, dass nach abarbeiten des Wortes der letzte Zustand ein Endzustand sein muss, damit das Wort als gültig angesehen werden kann (zusammen mit der Bedingung, dass der Stack leer sein muss).

  3. Bei der Codevorgabe habe ich an eine rekursive Implementierung von ChangeState gedacht.

Tipp: Bei "Epsilonübergängen", also Übergängen die unabhängig von den Bedingungen immer (!) möglich sind, dürft ihr nicht zum nächsten Buchstaben weiter gehen. Der aktuelle Buchstabe wird sozusagen nicht verbraucht.

Ich werde nachher etwas Test-Code posten, damit ihr eure Implementierung testen könnt.

Außerdem hab ich bei der Code-Vorgabe noch ein paar Kommentare eingefügt.

D
96 Beiträge seit 2012
vor 12 Jahren

Leider hab ich einen Fehler im vorgegebenen Code gefunden, zumindest stimmt es nicht mit der Beschreibung überein. Ich korrigiere den Fehler und mache die Stelle kenntlich. Hoffe niemand hat sich daran den Kopf zerbrochen 😦

Hier sind drei Test-Automaten:


        // Gleich viele "a" wie "b"
        private static PushDownAutomaton GleichVieleAundB()
        {
            PushDownAutomaton automat = new PushDownAutomaton();
            State startUndEndZustand = new State();

            // (eingabe, stack, ausgabe)
            // Wichtig zu beachten: Das was auf dem Stack liegt wird vom Stack genommen!
            Transition a_1 = new Transition("a", null, startUndEndZustand, "a"); // (a, leer, a) => a auf den Stack legen
            Transition a_2 = new Transition("a", "a", startUndEndZustand, "a", "a"); // (a, a, aa) => a verdoppeln (1 a wird zu 2 a)
            Transition a_3 = new Transition("a", "b", startUndEndZustand, null); // (a, b, nichts) => b vom Stack nehmen
            Transition b_1 = new Transition("b", null, startUndEndZustand, "b"); // (b, leer, b) => b auf den Stack legen
            Transition b_2 = new Transition("b", "b", startUndEndZustand, "b", "b"); // (b, b, bb) => b verdoppeln
            Transition b_3 = new Transition("b", "a", startUndEndZustand, null); // (b, a, nichts) => a vom Stack nehmen

            startUndEndZustand.Transitions.AddRange(new Transition[] 
            {
                a_1, a_2, a_3, b_1, b_2, b_3
            });

            automat.FinalStates.Add(startUndEndZustand);
            automat.StartState = startUndEndZustand;

            return automat;
        }

        // Es gibt mehrere mögliche Übergänge.
        // Anzahl von a = (2 + 4k) => 2, 6, 10, 14, ...
        // Ein etwas komplizierter Automat
        private static PushDownAutomaton MehrereÜbergänge()
        {
            PushDownAutomaton automat = new PushDownAutomaton();
            State startZustand = new State();
            State endZustand = new State();

            // (eingabe, stack, ausgabe)
            Transition start_1 = new Transition("a", null, startZustand, "a"); // (a, leer, a)
            Transition start_2 = new Transition("a", "a", startZustand, "a", "a"); // (a, a, aa)
            Transition start_3 = new Transition("a", "a", endZustand, null); // (a, a, nichts)

            Transition end_1 = new Transition("a", null, endZustand, "a"); // (a, leer, a)
            Transition end_2 = new Transition("a", "a", endZustand, "a", "a"); // (a, a, aa)
            Transition end_3 = new Transition("a", "a", startZustand, null); // (a, a, nichts)

            startZustand.Transitions.AddRange(new Transition[] 
            {
                start_1, start_2, start_3
            });

            endZustand.Transitions.AddRange(new Transition[] 
            {
                end_1, end_2, end_3
            });

            automat.FinalStates.Add(endZustand);
            automat.StartState = startZustand;

            return automat;
        }

        // Gerade Anzahl an a
        private static PushDownAutomaton EpsilonÜbergänge()
        {
            PushDownAutomaton automat = new PushDownAutomaton();
            State startZustand = new State();
            State endZustand = new State();

            // (eingabe, stack, ausgabe)
            Transition start_1 = new Transition("a", null, startZustand, "a"); // (a, leer, a)
            Transition start_2 = new Transition("a", "a", startZustand, "a", "a"); // (a, a, aa)
            Transition start_3 = new Transition(null, null, endZustand, null); // Epsilonübergang

            Transition end = new Transition("a", "a", endZustand, null); // (a, a, nichts)

            startZustand.Transitions.AddRange(new Transition[] 
            {
                start_1, start_2, start_3
            });

            endZustand.Transitions.AddRange(new Transition[] 
            {
                end
            });

            automat.FinalStates.Add(endZustand);
            automat.StartState = startZustand;

            return automat;
        }

        public static void Main(String[] args)
        {
            PushDownAutomaton automat = GleichVieleAundB();


            while (true)
            {
                String input = Console.ReadLine();
                List<String> word = new List<String>();
                foreach (Char c in input)
                    word.Add(c.ToString());

                Console.WriteLine(automat.CheckWord(word));
            }
        }
D
96 Beiträge seit 2012
vor 12 Jahren

Da wohl keiner Lust hatte die Aufgabe zu lösen, poste ich meine Lösung. Somit ist das Programmierspiel wieder freigegeben (so wie es auch im ersten Post beschrieben ist, da keine Antwort innerhalb einer Woche kam).

        // input => Wort
        // index => Der aktuelle Buchstabe im Wort
        // stack => Der Stack
        // finalStates => Die Endzustände
        // Gibt <true> zurück, wenn das Wort abgearbeitet ist, der Stack leer ist und der letzte Zustand ein Endzustand war
        public Boolean ChangeState(List<String> input, Int32 index, Stack<String> stack, List<State> finalStates)
        {
            // Wenn das Wort abgearbeitet ist, nichts mehr auf dem Stack liegt und der momentane Zustand ein Endzustand ist...
            if (index >= input.Count && stack.Count == 0 && finalStates.Contains(this))
                return true; // Dann wurde das Wort erkannt

            // Alle Übergänge durchgehen
            foreach (var transition in Transitions)
            {
                // Wenn das Wort abgearbeitet ist, sind nur noch Epsilonübergänge erlaubt, andernfalls muss die Bedingung überprüft werden
                Boolean condition = index >= input.Count ? transition.IsEpsilon : transition.CheckConditions(input[index], stack);
                if (condition)
                {
                    String element = null;
                    // Den Stack ändern, außer bei Epsilonübergängen und leeren Stacks
                    if (stack.Count > 0 && !transition.IsEpsilon)
                        element = stack.Pop();

                    // Den Output vom Übergang auf den Stack legen
                    foreach (String str in transition.Output)
                        stack.Push(str);
                    // ------------

                    // Zum nächsten Zustand wechseln. Wenn es ein Epsilonübergang war, darf nicht zum nächsten Element im Wort gesprungen werden!
                    if (transition.NextState.ChangeState(input, index + (transition.IsEpsilon ? 0 : 1), stack, finalStates))
                        return true;

                    // Alle Änderungen auf dem Stack rückgängig machen
                    for (Int32 i = 0; i < transition.Output.Count; i++)
                        stack.Pop();

                    if (element != null)
                        stack.Push(element);
                    // ------------
                }
            }

            // Alle Übergange wurden geprüft und keiner hat zum Ziel geführt
            return false;
        }
4 Beiträge seit 2012
vor 12 Jahren

Hallo Leute,

da die Letzte Aufgabe nicht gelöst wurde, nach 10 Tagen die Lösung vom Aufgabensteller selbst gepostet wurde, dieser darauf verzichtet hat erneut eine Aufgabe zu stellen ...

Somit ist das Programmierspiel wieder freigegeben ... und seit 5 Tagen keine neue Aufgabe mehr gestellt wurde, versuche ich es jetzt einmal mit einer neuen Aufgabe. Insofern niemand was dagegen hat.

Also:

Aufgabe:
Vervollständigen Sie, die im Test-Code definierte Methode so, dass diese eine [URL]Mandelbrot-Menge[/URL] (Apfelmännchen) zeichnet.

Rahmenbedingungen:
- Die Mandelbrot-Menge soll Einfarbig (frontColor) und mit einer Hintergrundfarbe (backColor) gezeichnet werden.
- Die Parameter "section -Left -Top -Right -Bottom" geben den Ausschnitt in der Mandelbrot-Menge an, der gezeichnet werden soll.
- Der Parameter "deep" gibt die maximale Anzahl Iterationen pro Pixel an.

Test-Code:

using System;
using System.Windows.Forms;
using System.Drawing;

namespace Fractals
{

	/// <summary>
	/// Stellt ein Fenster dar, dass ein Mandelbrot Apfelmännchen Fraktal anzeigt.
	/// </summary>
	public class MandelbrotForm : Form
	{

		//Mandelbrot PictureBox
		PictureBox mandelbrotPicture;

		/// <summary>
		/// Erstellt ein neues Mandelbrot Fenster.
		/// </summary>
		public MandelbrotForm()
		{
			//Fenster Parameter festlegen
			this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedDialog;
			this.StartPosition = FormStartPosition.CenterScreen;
			this.Size = new Size(900, 600);

			//Image Control erstellen
			mandelbrotPicture = new PictureBox();
			mandelbrotPicture.Dock = DockStyle.Fill;
			this.Controls.Add(mandelbrotPicture);

			//Fenster anzeigen
			this.Show();

			//Image mit dem Mandelbrot Fraktal erstellen
			Bitmap mandelbrot = new Bitmap(this.Size.Width, this.Size.Height);
			using (Graphics gfx = Graphics.FromImage(mandelbrot))
			{
				Mandelbrot.DrawMandelbrot(
						gfx,
						Color.OrangeRed,
						Color.LightBlue,
						-2.0, -1.0, 1.0, 1.0,															//Ganzes Apfelmännchen
						//0.3184375, -0.0557421875, 0.34533203125, -0.0355712890625,					//Ausschnitt
						//0.32155833984375, -0.6327984375, 0.422811767578125, -0.55685836669921875,		//Ausschnitt
						100);
			}
			mandelbrotPicture.Image = mandelbrot;
		}

	}


	/// <summary>
	/// Stellt eine Klasse zum Zeichnen von Mandelbrot Apfelmännchen Fraktalen dar.
	/// </summary>
	public static class Mandelbrot
	{

		/// <summary>
		/// Zeichnet ein Mandelbrot Apfelmännchen.
		/// </summary>
		/// <param name="gfx">Grafikausgabe.</param>
		/// <param name="frontColor">Farbton, der für das Zeichnen verwendet werden soll.</param>
		/// <param name="backColor">Hintergrundfarbe.</param>
		/// <param name="sectionLeft">Gibt den linken Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
		/// <param name="sectionTop">Gibt den oberen Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
		/// <param name="sectionRight">Gibt den rechten Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
		/// <param name="sectionBottom">Gibt den unteren Rand des Ausschnitts an, der von dem Apfelmännchen gezeichnet werden soll.</param>
		/// <param name="deep">Gibt die maximale Anzahl Iterationen an.</param>
		public static void DrawMandelbrot(Graphics gfx, Color frontColor, Color backColor, double sectionLeft, double sectionTop, double sectionRight, double sectionBottom, int deep)
		{
			//Erstellen Sie Ihren Code hier.
		}
	}
}

Viel Spaß und Gruß Stalky13

Ps. Fraktale sind Awsome 😄

Edit:
Da es nicht voran zu gehen scheint, hier ein Tipp: In dem Wikipediabeitrag findet ihr die nötigen Informationen zur Lösung ganz unten. Ihr müsst also nicht den ganzen Beitrag lesen, sondern nur einen kleinen Teil am Ende.
Meine Version besteht aus 20 Zeilen Code (ohne Klammern und Kommentare).

Hinweis von herbivore vor 11 Jahren

Zu dieser Aufgabe gibt es eine (etwas verspätete) Lösung von Quadsoft weiter unten.

Aus großer Macht folgt große Verantwortung!

111 Beiträge seit 2011
vor 11 Jahren

Offenbar kommt keiner drauf also möchte ich eine neue kleine Aufgabe stellen.

Um etwas das Verständnis in Sachen "Wie rechnet mein Rechner?" eigentlich zu festigen würde ich gern folgende Funktion sehen:
Ich übergebe 3 Bit (2 die ich addieren will und den Übertrag von der vorherigen Rechnung)

(Um Große zahlen zu berechnen wird jede Operation auf Additionen zurückgeführt die die Recheneinheit dann berechnen kann. (Wie das geht steht bestimmt irgendwo auf Wikipedia und co.) Dabei werden immer 2 Bit miteinander addiert und ggf. ein Übertrag der vorherigen Stelle)){gray}

Ziel ist es ganz einfach eine Funktion zu schreiben der man 3 Bit (0 oder 1) übergibt.
Zahl1, Zahl2 und den Übertag.

Die Funktion gibt dann die Summe aus und zwar als string in Binärschreibweise.
Dazu will ich noch wissen wie sich das nennt was ihr da Programmiert habt.

Zur Info:
bei 3 Bit die Man addiert kann nur 00, 01, 10 oder 11 herauskommen von daher kann man das von mir aus auch mit einer switch Anweisung machen oder so um sich das umrechnen von dezimal in dual zu sparen.

Wichtig ist dass ich die Ergebnisse von
0 und 0 Übertrag 0
0 und 0 Übertrag 1
0 und 1 Übertrag 0
0 und 1 Übertrag 1
1 und 0 Übertrag 0
1 und 0 Übertrag 1
1 und 1 Übertrag 0
1 und 1 Übertrag 1
bekomme

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

309 Beiträge seit 2008
vor 11 Jahren

static string VollAddierer(string x, string y, string cin)
{
    bool x_B, y_B, cin_B;

    if (!ParseBit(x, out x_B))
        throw new ArgumentException("x");

    if (!ParseBit(y, out y_B))
        throw new ArgumentException("y");

    if (!ParseBit(cin, out cin_B))
        throw new ArgumentException("cin");

    bool cout = (y_B & cin_B) | (x_B & cin_B) | (x_B & y_B);
    bool s = x_B ^ y_B ^ cin_B;

    return (cout ? "1" : "0") + (s ? "1" : "0");
}

static bool ParseBit(string value, out bool result)
{
    if (bool.TryParse(value, out result))
        return true;
    else if (value == "1")
    {
        result = true;
        return true;
    }
    else if (value == "0")
    {
        result = false;
        return true;
    }

    result = false;
    return false;
}

Das ganze nennt sich Volladdierer

Aber warum Strings? 🤔

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

111 Beiträge seit 2011
vor 11 Jahren

hiho die antwort ist richtig ich wollte grade noch sagen weil ich darauf hingewiesen wurde bitte auch strings als parameter. aber das hast du ja schon gemacht. warum strings? tja warum strings? ich wollt halt nicht klassisch bool oder zahlen nutzen 😉 aber ist auch nebensächlich das wichtige ist dass die idee verstanden wurde wie ein rechner rechnet du bist dran scavanger

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

2.891 Beiträge seit 2004
vor 11 Jahren

Da seit über einem Monat keine neue Aufgabe gestellt wurde, mache ich das mal:


Gesucht ist eine Methode [tt]TElement PickRandom(IEnumerable<TElement> source)[/tt], die ein zufälliges Element aus einer Auflistung zurückgeben soll.

Folgende Bedingungen müssen allerdings erfüllt sein:
[list]
[*]Die Auflistung darf nur ein einziges Mal durchlaufen werden.
[*]Die Auflistung darf nicht zwischengespeichert werden.
[*]Die Wahrscheinlichkeit, ausgewählt zu werden, muss für alle Elemente der Auflistung gleich sein.
[/list]

Falls die Auflistung keine Elemente enthält, sollte eine Ausnahme ausgelöst werden.

76 Beiträge seit 2008
vor 11 Jahren

private static Random m_objRand;

public TElement PickRandom (IEnumerable<TElement> source) {
    if (m_objRand == null)  m_objRand = new Random();
    int iCount = source.Count<TElement>();
    if (iCount == 0) throw new Exception("COUNT darf nicht 0 sein.");
    int iIndex = 0;
    int iRandomObjectIndex = m_objRand.Next(0, source.Count<TElement>());
    foreach (TElement obj in source) {
        if (iIndex == iRandomObjectIndex) {
            return obj;
        } // if end
        iIndex++;
    } // foreach end
    return null;
}

Ich denke, die Antwort ist zu "einfach" oder? 😄

D
96 Beiträge seit 2012
vor 11 Jahren

Ich denke deine Lösung zählt nicht, da die Count() Methode die Liste einmal durchläuft und du deshalb insgesamt 3 Durchläufe hast.

76 Beiträge seit 2008
vor 11 Jahren

Okay... source.Count<TElement>() als 2. Parameter in new Random sollte eh iCount werden - aber das tut ja nichts zur Sache. 2 sind's trotzdem 😄

// Edit
Schwierige Sache. Ich habe eine 2. Idee gehabt: Erst OrderBy Random (1 Durchlauf) - und dann das erste Element [0] durch ToList() returnen. Bei Fehler eben throw Excption - aber ich denke: ToList() läuft die IEnumerable ein zweites Mal durch. Oder?

Würde so aussehen:

    public class TElement { public int Index = 0; }

    internal class Program {
        private static Random m_objRand;

        private static void Main () {
            List<TElement> source = new List<TElement>();
            source.Add(new TElement() { Index = 0 });
            source.Add(new TElement() { Index = 1 });
            source.Add(new TElement() { Index = 2 });
            source.Add(new TElement() { Index = 3 });
            source.Add(new TElement() { Index = 4 });
            for (int i = 0; i < 2; i++) {
                TElement rand = PickRandom(source);
                Console.WriteLine(rand.Index);
            } // for end
        }

        
        public static TElement PickRandom (IEnumerable<TElement> source) {
            if (m_objRand == null) m_objRand = new Random();
            try {
                return source.OrderBy(obj => m_objRand.Next()).First();
            } // try end
            catch {
                throw new Exception();
            }
        }
    }

// Edit 2: Hab die Lösung! Man benötigt nicht "ToList()" - man kann auf die Methode First() zurückgreifen 😃

Grüße
Dennis Z.