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

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

Mitglieder
» Liste / Suche
» Wer ist online?

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

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

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

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

Zitat von dN!3L
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.
private Nachricht | Beiträge des Benutzers
ModelViewPresenter
myCSharp.de - Member

Avatar #avatar-3375.jpg


Dabei seit:
Beiträge: 69

beantworten | zitieren | melden

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++;
	             }
			}
        }
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

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
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

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.

  2. 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'.
  3. 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;
    }
    
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Taipi88
myCSharp.de - Member

Avatar #avatar-3220.jpg


Dabei seit:
Beiträge: 1044
Herkunft: Mainz

beantworten | zitieren | melden

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:
Zitat
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();
	}
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Taipi88 am .
Attachments
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 637

beantworten | zitieren | melden

Als maxKeyLength könntest du auch die Länge des zu entschlüsselnden Textes nehmen.
private Nachricht | Beiträge des Benutzers
Taipi88
myCSharp.de - Member

Avatar #avatar-3220.jpg


Dabei seit:
Beiträge: 1044
Herkunft: Mainz

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Ui, das ging ja schnell. Richtige Lösung. Sehr schön.
Zitat von Taipi88
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.
Attachments
private Nachricht | Beiträge des Benutzers
Taipi88
myCSharp.de - Member

Avatar #avatar-3220.jpg


Dabei seit:
Beiträge: 1044
Herkunft: Mainz

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Taipi88 am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

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 [email protected] 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();
}
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Taipi88
myCSharp.de - Member

Avatar #avatar-3220.jpg


Dabei seit:
Beiträge: 1044
Herkunft: Mainz

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Taipi88
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).
Zitat von Taipi88
er Key ist mindestens 14 Stellen [...] würde das eine Berechnungsdauer von nunjaaaa... ca. 1 Monat ergeben[/quote]
Jep, mindestens 14 Stellen. Meine Version schafft es in unter einer Sekunde.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

Gelöst!

Danke, den Wink mit dem Zaunpfahl (Stichwort "Matrix"), hab ich gebraucht.
Zitat
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));}}
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

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).
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Scavanger am .

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));}}
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

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));}}
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo,

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
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

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));}}
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo 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
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo 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
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

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;
        }
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von DerKleineTomy am .
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo 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
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo DerKleineTomy,
Zitat
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.
Zitat
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
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

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

Edit: Hab den Code editiert.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von DerKleineTomy am .
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


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

beantworten | zitieren | melden

Hallo DerKleineTomy,

jetzt passt es
Du bist dran!

Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

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 :P. Es sind nicht mal 30 Zeilen Code nötig
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von DerKleineTomy am .
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von DerKleineTomy am .
private Nachricht | Beiträge des Benutzers
Entwickelt mit ♥ und ASP.NET Core. Version 0.1.332+27ed306318 vom Uhr. Betrieben auf Azure App Service (debian.10-x64 mit .NET 5.0.9)
Copyright 2003-2021 myCSharp.de - Alle Rechte vorbehalten. Benutzerinhalte unterliegen cc-by-sa 4.0