Laden...

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

Letzter Beitrag vor 3 Jahren 762 Posts 773.804 Views

Hallo TheBrainiac,

da du nur moderate 10% Kompression gefordert hast, hat sich mir sofort die Idee aufgedrängt, dass bei normalem Text das erste Bit meistens Null ist und daher eingespart werden kann, wenn man einfach immer nur die restlichen 7bit dicht an dich packt. So bekommt man je 8 Bytes in je 7 Bytes komprimiert, d.h. wenn es genau aufgeht eine Kompression von 12,5%. Da du Encoding.ASCII verwendest, ist das erste Bit sogar immer Null. Trotzdem habe ich den Fall implementiert, dass erste Bit manchmal auch Eins sein kann. In diesem Fall wird mit 0x7f eine Escapesequenz eingeleitet. Damit es keine Konflikte gibt, muss man auch 0x7f escapen, wenn es als normales Zeichen im Text auftaucht. Das alles macht der folgende Code:


public static byte[] Compress(byte[] input) {
   List <byte> result = new List <byte> ();
   int bitsLeft = 0;
   foreach (byte b in input) {
      if ((b & 0x80) == 0x80) {
         AddPacked (result, 0x7f, ref bitsLeft);
         AddPacked (result, (byte)(b & 0x7f), ref bitsLeft);
      } else if (b == 0x7f) {
         AddPacked (result, 0x7e, ref bitsLeft);
         AddPacked (result, 0x01, ref bitsLeft);
      } else if (b == 0x7e) {
         AddPacked (result, 0x7e, ref bitsLeft);
         AddPacked (result, 0x00, ref bitsLeft);
      } else {
         AddPacked (result, b, ref bitsLeft);
      }
   }
   if (bitsLeft == 7) {
      result [result.Count - 1] |= 0x7f;
   }
   return result.ToArray ();
}

private static void AddPacked (List <byte> list, byte b, ref int bitsLeft)
{
   try {
      if (bitsLeft == 0) {
         list.Add ((byte)(b << 1));
         return;
      }
      if (bitsLeft == 7) {
         list [list.Count - 1] |= b;
         return;
      }
      list [list.Count - 1] |= (byte)(b >> (7 - bitsLeft));
      list.Add ((byte)(b << (bitsLeft + 1)));
   }
   finally {
      bitsLeft = (bitsLeft + 1) % 8;
   }
}

public static byte[] Decompress(byte[] input) {
   List <byte> result = new List <byte> ();
   byte currByte;
   for (int bitOffset = 0;  bitOffset <= input.Length * 8 - 7;) {
      currByte = GetPacked (input, ref bitOffset);
      if (currByte == 0x7f) {
         if (bitOffset <= input.Length * 8 - 7) {
            result.Add ((byte)(GetPacked (input, ref bitOffset) | 0x80));
         }
         continue;
      }
      if (currByte == 0x7e) {
         if (GetPacked (input, ref bitOffset) == 0x00) {
            result.Add (0x7e);
            continue;
         }
         result.Add (0x7f);
         continue;
      }
      result.Add (currByte);
   }
   return result.ToArray ();
}

private static byte GetPacked (byte [] list, ref int bitOffset)
{
   try {
      int byteOffset = bitOffset / 8;
      if (bitOffset % 8 == 0) {
         return (byte)(list [byteOffset] >> 1);
      }
      if (bitOffset % 8 == 1) {
         return (byte)(list [byteOffset] & 0x7f);
      }
      return (byte)(((list [byteOffset]     << ((bitOffset % 8) - 1)) & 0x7f)
                   | (list [byteOffset + 1] >> (9 - (bitOffset % 8))));
   }
   finally {
      bitOffset += 7;
   }
}

Ausgabe für den vorgegebenen Teststring:

Uncompressed Length: 3941
Compressed Length: 3449
Decompressed Length: 3941
Compression Ratio: 12,4841%
Input equals output: True
Successful: True

Wenn du meine Lösung als richtig akzeptierst, dann trete ich schon jetzt das Recht, die nächste Aufgabe zu stellen, an gfoidl ab. Der hat nämlich schon was parat.

herbivore

Hallo Herbivore,

Hallo TheBrainiac,

deine Lösung ist korrekt.
...

Hier zum Vergleich noch, wie ich mir das vorgestellt hatte.
...

Ich halte beide Lösungen für relativ schwer lesbar. Wirklich korrekt sind sie auch nicht. Ein Kniffel ist immer auch ein FullHouse, das berücksichtigen beide Varianten nicht. Das lässt sich natürlich einfach korrigieren, steigert aber die Verständlichkeit des Codes nicht wirklich.

MfG,

N1ls

Hi, Herbivore.

Da deine Lösung richtig ist 👍, Bist du dran, aber da du diesen Part gfoidl überlassen hast --> gfoidl, du bist dran 😁

Gruß, Christian.

`There are 10 types of people in the world: Those, who think they understand the binary system Those who don't even have heard about it And those who understand "Every base is base 10"`

Hallo,

erstmal bedanke ich mich bei herbivore dafür dass er mir die nächste Aufgabe schenkt 😉

Die Aufgabe:


Prüfe ob ein beliebiger Polygonzug offen ist, d.h. keine geschlossene Kurve (~eine "Schleife") enthält. Siehe angehängtes Bild für einfache Beispiele.
Für die Eingaben der Punkte der Polygonzuges gilt zusätzlich die Einschränkung dass 3 aufeinander folgende Punkte nicht auf einer Geraden liegen dürfen. Eine Prüfung dessen ist nicht erforderlich, sondern die Einschränkung behandelt lediglich eine Grenzfall der Aufgabenstellung.

Gegeben sei folgender Code-Rumpf:
[csharp]
using System;
using System.Collections.Generic;

namespace Polygonzug
{
	public struct Punkt
	{
		public double X;
		public double Y;

		public Punkt(double x, double y)
		{
			X = x;
			Y = y;
		}
	}

	public class PolygonzugAufgabe
	{
		public bool IstOffen(IEnumerable<Punkt> punkte)
		{
			throw new NotImplementedException();
		}
	}
}
[/csharp] 

Ein einfacher Test um das Ergebnis validieren zu können:
[csharp]
using System.Collections.Generic;
using NUnit.Framework;

namespace Polygonzug
{
	[TestFixture]
	public class PolygonzugAufgabeTest
	{
		[Test]
		public void IstOffen_OffenerPolygonzug_ReturnsTrue()
		{
			PolygonzugAufgabe sut = new PolygonzugAufgabe();

			bool istOffen = sut.IstOffen(this.GeneriereOffenenPolygonzug());

			Assert.IsTrue(istOffen);
		}
		//---------------------------------------------------------------------
		[Test]
		public void IstOffen_GeschlossenerPolygonzug_ReturnsFalse()
		{
			PolygonzugAufgabe sut = new PolygonzugAufgabe();

			bool istOffen = sut.IstOffen(this.GeneriereGeschlossenenPolygonzug());

			Assert.IsFalse(istOffen);
		}
		//---------------------------------------------------------------------
		private IEnumerable<Punkt> GeneriereOffenenPolygonzug()
		{
			yield return new Punkt(0.0, -0.6);
			yield return new Punkt(2.2,  2.4);
			yield return new Punkt(5.4,  0.4);
			yield return new Punkt(1.6, -0.2);
			yield return new Punkt(3.0, -2.2);
			yield return new Punkt(1.0, -0.6);
			yield return new Punkt(0.2, -2.0);
			yield return new Punkt(1.2, -2.4);
		}
		//---------------------------------------------------------------------
		private IEnumerable<Punkt> GeneriereGeschlossenenPolygonzug()
		{
			yield return new Punkt(0.6, -1.7);
			yield return new Punkt(0.0,  0.5);
			yield return new Punkt(3.0,  0.9);
			yield return new Punkt(3.8, -0.9);
			yield return new Punkt(4.8,  0.7);
			yield return new Punkt(6.2, -0.3);
			yield return new Punkt(2.4, -2.1);
			yield return new Punkt(2.6,  2.1);
		}
	}
}
[/csharp]
Die Polygonzüge der Tests entsprechen nicht jenen des angehängtesn Bildes.

Es gelten die "üblichen" Bedingungen: Frameworks- / 3rd-Party-Klassen sind verboten!

Viel Spass bei der Aufgabe!

mfG Gü

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

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

Moin,

zur Lösung der Aufgabe von gfoidl brauche ich folgendes:

Eine Extension-Method die berechnet ob sich ein double-Wert in einem bestimmten Bereich findet:

public static class Extenstions
{
    public static bool IsBetween(this double value, double border1, double border2) {
        if (border1 < border2) return (value >= border1 && value <= border2);
        if (border1 > border2) return (value >= border2 && value <= border1);
        return value == border1;
    }
}

Dann einen Struct der einen Punkt darstellt:

public struct Punkt {
    
    public double X;
    public double Y;

    public Punkt(double x, double y) {
        X = x;
        Y = y;
    }
    
    public override bool Equals(object obj) {
        if (!(obj is Punkt)) return false;
        var andererPunkt = (Punkt)obj;
        return (X.Equals(andererPunkt.X) && Y.Equals(andererPunkt.Y));
    }

}

Einen Struct der eine Strecke abbildet und der Methoden enthält mit denen festgestellt werden kann ob eine Strecke eine andere schneidet oder ein direkter Nachbar einer anderen Strecke ist:

public struct Strecke {

    public Punkt P1;
    public Punkt P2;
    public double M;
    public double C;

    public Strecke(Punkt p1, Punkt p2) {
        P1 = p1;
        P2 = p2;
            
        // Steigung und Y-Achsenabschnitt berechnen
        M = (P2.Y - P1.Y) / (P2.X - P1.X);
        C = P1.Y - (M * P1.X);
        }

    public bool Schneidet(Strecke andereStrecke) {
        
        // X-Wert des Schnittpunktes berechnen und feststellen ob
        // der Punkt innerhalb der definierten Strecken liegt
        var schnittpunkt = (andereStrecke.C - C) / (M - andereStrecke.M);

        // Wenn sich für den Schnittpunkt gar nicht erst ein gültiger Wert
        // ergibt wird es wohl keinen geben
        if (double.IsInfinity(schnittpunkt) || double.IsNaN(schnittpunkt)) return false;

        // Wenn es einen Wert gibt muss geprüft werden ob er innerhalb einer
        // der angegeben Strecken liegt
        return schnittpunkt.IsBetween(P1.X, P2.X) &&  
               schnittpunkt.IsBetween(andereStrecke.P1.X, andereStrecke.P2.X);
    }

    public bool IstNachbar(Strecke andereStrecke) {
        return (P1.Equals(andereStrecke.P1) || P1.Equals(andereStrecke.P2)) || 
               (P2.Equals(andereStrecke.P1) || P2.Equals(andereStrecke.P2));
    }

    public override bool Equals(object obj) {
        if (!(obj is Strecke)) return false;
        var andereLinie = (Strecke)obj;
        return (P1.Equals(andereLinie.P1) && P2.Equals(andereLinie.P2));
    }

}

Und last but not least die von gfoidl vorgegebene Klasse die die Logik zur Überprüfung der einzelnen Polygonzüge enthält:


public class PolygonzugAufgabe {

    private readonly List<Strecke> _linien = new List<Strecke>();

    public bool IstOffen(IEnumerable<Punkt> punkte) {
        var punkteArray = punkte.ToArray();
        for (var i = 0; i < punkte.Count() - 1; i++)
            _linien.Add(new Strecke(punkteArray[i], punkteArray[i + 1]));

        return _linien.All(linie1 => !_linien.Any(linie2 => !linie1.IstNachbar(linie2) && 
                                                            !linie1.Equals(linie2) &&
                                                            linie1.Schneidet(linie2)));
    }

}

Das ganze in einen Kochtopf, kompilieren, testen, fertig. Ist vielleicht nicht immer unbedingt die eleganteste Lösung - aber sie funktioniert. 😃

Hallo Spontifixus,

die beiden Tests - die der Aufgabenstellung angehängt sind - wurden bestanden. Der Test für ein einfaches Quadrat wird aber nicht bestanden. Insofern ist die Aufgabe noch nicht gelöst, da ein beliebiger Polygonzug verlangt wurde 😉

Dennoch ein interessanter Ansatz.


[Test]
public void IstOffen_EinfacherGeschlossenerPolygonzug_ReturnsFalse()
{
	PolygonzugAufgabe sut = new PolygonzugAufgabe();

	bool istOffen = sut.IstOffen(this.GeneriereEinfachenGeschlossenenPolygonzug());

	Assert.IsFalse(istOffen);
}
//---------------------------------------------------------------------
private IEnumerable<Punkt> GeneriereEinfachenGeschlossenenPolygonzug()
{
	yield return new Punkt(0, 0);
	yield return new Punkt(1, 0);
	yield return new Punkt(1, 1);
	yield return new Punkt(0, 1);
	yield return new Punkt(0, 0);
}

mfG Gü

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

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

Stimmt auffallend. Werde ich noch korrigieren.

Mir ist gerade aufgefallen, dass laut Steigung eine parallele zur y-Achse nicht als Funktionsgraph gilt, die Steigung aber als Unendlich angesehen werden kann. Dann funktioniert natürlich meine Rechnung nicht mehr.
Ich hatte gehofft meine Lösung noch aufbohren zu können aber für Strecken parallel zur y-Achse taugt die wohl nichts...

Das hier beschriebene Steigungsproblem lässt aber den Hinweis von gfoidl unberührt - selbst wenn ich das Quadrat auf die Spitze stelle wird es nicht als geschlossen erkannt.

Lange Rede kurzer Sinn: Der hier vorgestellte Ansatz ist hervorragend als Exponat für das Museum der krankhaften Ideen auf Maximegalon geeignet, aber nicht als Lösungsansatz, der die von gfoidl gestellten Kriterien erfüllt.

Ich bin gespannt auf die Lösung!

Hallo,

in meiner Lösung verwende ich auch die Steigung. Die Parallele zur Ordinate handhabe ich da gesondert mit double.IsInfinity und wenn beide Strecken den selben (unendlichen) Wert für die Steigung haben so sind diese parallel.

Vllt. hilft dir das noch für deine Lösung - ich denke dass sich das noch leicht einbauen lässt.

Ich bin gespannt auf die Lösung!

Meine Lsg. hänge ich dann an 😉

mfG Gü

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

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

Hallo gfoidl,

da ich gerade ein bisschen auf der Leitung stehe habe ich mal recherchiert.
In diesem Dokument (Seite 9) steht eine geringfügig abweichende Definition von "geschlossen" und "offen".

Wäre dem so - würde folgende Implementierung der Klasse PolygonzugAufgabe Ausreichen:

public class PolygonzugAufgabe {
    public bool IstOffen(IEnumerable<Punkt> punkte)
    {
        return !punkte.Last().Equals(punkte.First());            
    }
}

Die Klassen für die Strecke, sowie die Extension-Methode wären dann nicht mehr nötig.

In deiner Aufgabenstellung geht es aber darum, das von den Strecken des Polygonzuges mindestens eine Fläche komplett umschlossen wird - auch wenn das Polygon selber (gemäß der o.g. Definition) als offen zu bezeichnen ist?

Viele Grüße,
Markus 😃

Hallo,

In deiner Aufgabenstellung geht es aber darum, das von den Strecken des Polygonzuges mindestens eine Fläche komplett umschlossen wird

Genau.

Bzgl. Definition hab ich auch nochmal geschaut. Bei meiner Aufgabe gehts demnach ob das Polygon überschlagen ist oder nicht. Ich finde aber dennoch dass die Aufgabenstellung klar ist 😉

mfG Gü

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

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

Diese lösung dürfte auch für quadrate und dreiecke gehen.

public class PolygonzugAufgabe
    {
        public static bool IstOffen(IEnumerable<Punkt> punkte)
        {
            //graden gleichsetzen (ok, ich hab ein cas benutzt):
            //sax+a*dax = sbx+b*dbx => a=(-sax+sbx+b*dbx)/dax
            //say+a*day = sby+b*dby => b=-(-say*dax+day*sax-day*sbx+sby*dax)/(-dbx*day+dby*dax)
            List<Punkt> liste = punkte.ToList();
            for (int ia = 1; ia < liste.Count; ia++)
            {
                double sax = liste[ia - 1].X;
                double say = liste[ia - 1].Y;
                double dax = liste[ia].X - sax;
                double day = liste[ia].Y - say;
                for (int ib = 1; ib < liste.Count; ib++)
                    if (Math.Abs(ia-ib)>1)//aneinanerhängende und identische schneiden sich nicht
                    {
                        double sbx = liste[ib - 1].X;
                        double sby = liste[ib - 1].Y;
                        double dbx = liste[ib].X - sbx;
                        double dby = liste[ib].Y - sby;
                        double b = -(-say * dax + day * sax - day * sbx + sby * dax) / (-dbx * day + dby * dax);
                        if (b <= 1 && b >= 0)
                        {
                            double a = (-sax + sbx + b * dbx) / dax;
                            if (a <= 1 && a >= 0)
                                return false;
                        }
                    }
            }
            return true;
        }
    }

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

Hallo Floste,

super 👍

Du bist dran.

mfG Gü

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

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

Ok: nächste aufgabe:

Schreibe ein programm, das alle zahlen findet, die die ziffern von 1 bis 9 jeweils exakt einmal enthalten. Es sind also alle kombinationen aus {1,2,3,4,5,6,7,8,9} gesucht. Jede dieser zahlen soll exakt einmal gefunden werden (keine doppelten):

123456789
123456798
123456879
123456897
123456978
123456987
123457689

...

987654321

Von diesen zahlen soll die 111.111te ausgegeben werden. (Dazu müssen die zahlen nach größe sortiert sein.)

Am besten soll es unter einer sekunde dauern, ich aktzeptiere aber auch langsamere lösungen. Meine zeit ist bei 0,013sec

Damit mir auch keiner die zahl direkt hinter der gesuchten liefert: Zaunpfahlproblem

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

Hallo Floste,

stimmt 381496527?

Zeit nicht messbar. ~2000 Ticks der Stopwatch 😉

mfG Gü

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

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

Stimmt genau, und bei der zeit kann man nicht meckern. Poste bitte mal deinen code.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

Hallo,

sollte stimmen, hab ich auch 😉 Aber ich verzichte auf posten der Lösung (gefragt war ja das Programm, oder nur die Lösung?) weil mir grad keine neue Aufgabe einfällt gg

Aber poste mal deine Frequency der Stopwatch - ohne die ist die Tickangabe wenig hilfreich weil die ja abhängig vom Hardwaretimer ist.
Aber selbst mit diesen Angaben ist die Ausführungszeit ja von der Hardware abhängig. Deshalb könnte man höchsten auf ner Referenzmaschine vergleichen.

Meine Lösung liegt auch im unteren Millisekundenbereich auf nem 2 Jahre alten Notebook.

Baka wa shinanakya naoranai.

Mein XING Profil.

Hallo,

die Frequency der Stopwatch ist auf meinem 2 Jahre alten Laptop 3.579.545

Die Lösung ist eigentlich relativ einfach wenn die richtige Datenstruktur verwendet wird. Andernfalls lässt sich mMn kein vernüftiger Algorithmus entwickeln.

Hier hab ich die möglichen Permutationen der Ziffern als Baum dargestellt. Die Wurzel des Baums hat alle Ziffern der gegebenen Menge. Jedes Kind davon hat dann alle anderen Ziffern außer diejenigen welche im Pfad schon berücksichtigt sind. Es gibt also soviele Ebenen im Baum bis am Ende nur Blätter mit einer Ziffer übrigbleiben.
Auf diese Idee ein wenig Mathe angewandt so kann das "Bucket" berechnet werden indem der rekursive Abbau des Baums fortgesetzt wird.

Als Code schaut dann so aus:


static void Main(string[] args)
{
	int targetIndex = 111111 - 1;
	List<int> digits = Enumerable.Range(1, 9).ToList();
	List<int> solution = new List<int>();
	Permutation(digits, targetIndex, solution);
	solution.ForEach(i => Console.Write(i));
	Console.ReadKey();
}
//---------------------------------------------------------------------
private static void Permutation(List<int> digits, int index, List<int> solution)
{
	int n = digits.Count;

	if (n == 1)
	{
		solution.Add(digits[0]);
		return;
	}

	int treeBucketSize = Factorial(n - 1);
	int splitIndex = index / treeBucketSize;
	int splitDigit = digits[splitIndex];
	digits.RemoveAt(splitIndex);
	solution.Add(splitDigit);
	Permutation(digits, index - treeBucketSize * splitIndex, solution);
}
//---------------------------------------------------------------------
private static int Factorial(int n)
{
	if (n <= 1) return 1;
	if (n == 2) return 2;
	return Factorial(n - 1) * n;
}

Für die nächste Aufgabe fällt mir auch nichts ein -> ich gebe somit das Spiel frei. D.h. der schnellste Aufgabensteller ist dran 😉

mfG Gü

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

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

Hallo,

ich hab doch eine Aufgabe 😉

Dazu eine kurze Geschichte:


Antonia denkt sich 2 ganze Zahlen aus dem Intervall [1; 1000].
Sie nennt Berta das Produkt ihrer beiden Zahlen, Christina nennt sie die Summe und Daniela die Differenz.

Berta sagt zu den anderen: "Ich kann die Lösung nicht nennen".
Christina antwortet: "Das wusste ich  :D"
Darauf Berta: "Dann weiß ich jetzt die Lösung."
Christina entgegnet: "Dann weiß ich sie jetzt auch."
Daniela sagt: "Ich nicht, aber ich habe eine Vermutung, was eine der beiden Zahlen wahrscheinlich ist."
Berta sagt: "Ich weiß, was du vermutest, aber das ist falsch."
Daniela: "Dann kenne ich jetzt auch die Lösung." 

Wie lauten Antonias Zahlen?

mfG Gü

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

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

Moin,

ich hab lange nachgedacht und bin zu keinem Ergebnis gekommen und hab schließlich gegoogelt. Das Ding ist tatsächlich mit einigem Hirnschmalz und ein paar Zeilen Code zu lösen. Faszinierend... 😃

Viele Grüße,
Markus 😃

Hallo,

ist das nicht eher nen mathematisches bzw. logisches Problem? Ich seh da nicht die Herausforderung irgendwas programmtechnisch entwickeln zu müssen, da der Code nur die Implementierung der Formeln wäre. Oder seh ich das falsch?

Baka wa shinanakya naoranai.

Mein XING Profil.

Hallo talla,

es ist ein mathematisches Problem das sich aber nur mit Hilfe von Programmierung lösen lässt. Formeln zur Lösung gibt es nicht wirklich (zumindest keine geschlossene Formel). Die Lösung hängt viel mehr von den verwendeten Datenstrukturen die für das Programm verwendet werden ab.

mfG Gü

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

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

Hier ist sie nun die Lösung - auch wenn der Gehirnschmalz dahinter nicht von mir kommt, die Implementierung ist von mir. 😉

Damit wir im weiteren Verlauf einfach und übersichtlich arbeiten können brauchen wir zwei kleine Extras. Zum einen eine Extension-Method die aus einer IEnumerable von IGroupings wieder eine flache Liste macht:

public static class Extensions {
    
    public static List<TOut> ToFlatList<TOut>(this IEnumerable<IGrouping<int, TOut>> grouping) {

        var newList = new List<TOut>();
        foreach (var group in grouping)
            newList.AddRange(group);
        return newList;

    }

}

Als nächstes brauchen wir noch eine Datenstruktur die Zahlenpaare sowie deren Produkte, Summen und Differenzen halten kann:

private struct CalculationInfo {

    public int X;
    public int Y;

    public int Product;
    public int Sum;
    public int Difference;

    public override string ToString() {
        return string.Format("CalculationInfo: X={0}, Y={1}, Product={2}, Sum={3}, Difference={4}", X, Y, Product, Sum, Difference);
    }

}

Bis hierhin war's einfach. 😁

Für die Lösung des Rätsels brauchen wir eine Liste mit den Faktoren und Summanden. Sowohl Multiplikation als auch Addition sind Kommutativ (Das Zahlenpaar (X,Y) ist für die Lösung der Aufgabe identisch zum Paar (Y,X)). Zwar ist die Subtraktion nicht kommutativ, trotzdem kann man aufgrund der Aufgabenstellung davon ausgehen, dass der Betrag der Differenz interessant ist, denn Daniela erwähnt nichts von einer positiven oder negativen Zahl. Von daher können wir um unnötigen Rechenaufwand zu vermeiden für die Lösung auf Zahlenpaare zurückgreifen, bei denen die zweite Zahl größer oder gleich der ersten ist.

var workingList = new List<CalculationInfo>();
for (var x = 1; x <= 1000; x++)
    for (var y = x; y <= 1000; y++)
            workingList.Add(new CalculationInfo {
                X = x,
                Y = y,
                Product = x * y,
                Sum = x + y,
                Difference = Math.Abs(x - y)
            });

Berta sagt zu den anderen: "Ich kann die Lösung nicht nennen".
Was verannlasst Berta zu dieser Aussage? Antonia hat Berta das Produkt zweier Zahlen genannt. Wäre das Produkt kleiner als Tausend und eine Primzahl, dann würde Berta die Lösung kennen, denn dann kämen nur zwei Zahlen in Betracht: Die eins und das Produkt selber.
Berta würde die Lösung ebenfalls kennen, wenn die genannte Zahl größer als 1000 und das Produkt zweier Primzahlen wäre - denn dann würde die Lösung mit der eins nicht mehr greifen.
Die Zahl 5055 zum Beispiel ist in der Primfaktorenzerlegung 3 x 5 x 337. Soll das Produkt durch zwei Zahlen im Bereich von 1 bis 1000 dargestellt werden geht das nur als 15 x 337, denn sowohl bei 3 x 1685 als auch bei 5 x 1011 ist der zweite Faktor größer als 1000.
Wirklich aussagekräftig ist die Aussage von Berta also nicht, denn wir haben ja schon festgestellt, dass wir mit Primzahlen nicht weiterkommen.
Was wir aber wissen, ist, dass das Produkt, das Antonia Berta zugeflüstert hat mehrfach vorkommen muss, denn ansonsten wüsste Berta ja bereits was die Lösung wäre.
Diese Erkenntnis könnten wir jetzt ausnutzen um die Menge der verfügbaren Zahlenpaare einzugrenzen - tun wir aber nicht.

Christina antwortet: "Das wusste ich 😄"
Da scheint sich Christina ja ganz schön sicher zu sein. Dieser Hinweis ist - nunja - herausfordernd platziert. Den Christina wusste eigentlich schon von Anfang an, dass Berta die Lösung nicht kennen kann.
Was heißt das genau? Christina sieht eine Zahl, die man nur so aus zwei Summanden zusammensetzen kann, dass für alle Paare der Summanden gilt was zuvor bereits gesagt wurde. Kennt Christina zum Beispiel die Zahl 18, könnte die Lösung 1 + 17 sein. 17 ist allerdings eine Primzahl und deswegen könnte Berta die Lösung kennen. Also könnte im Falle der 18 Christina nicht schon vorher wissen das Berta die Lösung nicht kennt. Damit scheidet die 18 aus, und mit ihr alle Paare von Zahlen die addiert 18 ergeben.
Was lernen wir? Die Information das Christina weiß, dass Berta die Lösung nicht kennt ist viel Wertvoller als das Geständnis von Berta keine Ahnung zu haben.
Wir können jetzt aus unserer Arbeitsliste alle die Datensätze streichen bei denen eine oder mehrere Kombinationen von Summanden existieren mit denen man bei Kenntnis des Produktes auf die Lösung kommen würde.
Im Klartext heißt das: Wir suchen alle eindeutigen Produkte aus der Arbeitsliste, holen uns die dazugehörigen Summen und entfernen anschließend alle Werte mit diesen Summen aus der Arbeitsliste. Im Code sieht das dann so aus:

var sumsByUniqueProducts = workingList.GroupBy(value => value.Product)
                                      .Where(item => item.Count() == 1)
                                      .ToFlatList()
                                      .GroupBy(value => value.Sum)
                                      .Select(value => value.Key)
                                      .ToArray();
workingList = workingList.Where(workingItem => !sumsByUniqueProducts.Contains(workingItem.Sum)).ToList();

Damit enthält die Worklist jetzt statt 500500 nur noch 27596 Einträge.

Darauf Berta: "Dann weiß ich jetzt die Lösung."
Dieser Hinweis ist deutlich einfacher auszuwerten als die vorhergehenden. Wir wissen jetzt, dass das Produkt der gesuchten Zahlen nur noch einmal in der Arbeitsliste vorkommt. Das wiederum erlaubt es uns alle einträge aus der Arbeitsliste zu entfernen, deren Produkt mehr als einmal in der Liste auftaucht.

workingList = workingList.GroupBy(value => value.Product)
                         .Where(item => item.Count() == 1)
                         .ToFlatList();

Die Arbeitsliste enthält jetzt noch 6984 Einträge.

Christina entgegnet: "Dann weiß ich sie jetzt auch."
Dieser Hinweis enthält eine ähnliche Annahme wie der vorangegangene von Berta. Nur das sich die Annahme hier auf die Summen und nicht auf die Produkte bezieht. Wir können also damit Fortfahren alle Einträge aus der Liste zu entfernen deren Summe mehr als einmal in der Liste auftaucht.

workingList = workingList.GroupBy(value => value.Sum)
                         .Where(item => item.Count() == 1)
                         .ToFlatList();

Jetzt bleiben noch niedliche 27 EInträge übrig.

Daniela sagt: "Ich nicht, aber ich habe eine Vermutung, was eine der beiden Zahlen wahrscheinlich ist."
Aus diesem Hinweis kann man zwei Schlussfolgerungen ziehen. Einerseits weist er darauf hin, dass in der Menge der Zahlenpaare aus denen man Danielas Differenz bilden könnte ein Wert häufiger vorhanden ist als andere.
Es gibt allerdings noch eine weitere Schlussfolgerung: Danielas Differenz ist in der Arbeitstabelle mehr als einmal vorhanden, denn sonst wüsste Sie das Ergebnis ja jetzt auch.
Genau genommen müssen für die infragekommende Differenz mehr als zwei Einträge vorhanden sein, denn sonst kann nicht einer der Werte häufiger vorhanden sein als alle anderen.

workingList = workingList.GroupBy(value => value.Difference)
                         .Where(item => item.Count() > 2)
                         .ToFlatList();

Unsere Arbeitsliste enthält jetzt noch genau 6 Einträge.

Berta sagt: "Ich weiß, was du vermutest, aber das ist falsch."
Von so einer Aussage lässt sich Daniela allerdings nicht unterkriegen. Wir wissen jetzt dass einer der Werte bei zwei Datensätzen der Arbeitsliste auftauchen muss. Das Ergebnis dieser Datensätze ist also die Differenz. Dazu zählen wir die Datensätze bei denen der doppelte Wert vorkommt und entfernen anschließend alle Datensätze die die dort berechnete Differenz nicht enthalten aus der Arbeitsliste.

var occurrences = new Dictionary<int, int>();
foreach (var difference in workingList) {
    if (!occurrences.ContainsKey(difference.X))
        occurrences.Add(difference.X, 0);
    occurrences[difference.X]++;
    if (!occurrences.ContainsKey(difference.Y))
        occurrences.Add(difference.Y, 0);
    occurrences[difference.Y]++;
}
var wrongNumber = occurrences.Where(item => item.Value == occurrences.Values.Max())
                             .First()
                             .Key;
workingList = workingList.Where(item => item.X != wrongNumber && 
                                        item.Y != wrongNumber)
                         .ToList();

Wir erhalten eine Liste mit drei Werten. Jetzt ist auch Daniela stolz wie Oskar:

Daniela: "Dann kenne ich jetzt auch die Lösung."
Jetzt weiß auch Daniela dass ihre Differenz in der Arbeitsliste nur noch ein einziges Mal enthalten ist und kann so die überflüssigen Datensätze ausschließen:

workingList = workingList.GroupBy(value => value.Difference)
                         .Where(item => item.Count() == 1)
                         .ToFlatList();

Und endlich, endlich kennen auch wir den gesuchten Datensatz:

CalculationInfo: X=64, Y=73, Product=4672, Sum=137, Difference=9

Den Code habe ich nochmal als kompilierbare Datei an diesen Beitrag angehängt. Vielen Dank an fairymail.de für die Denkarbeit hinter der Lösung 😉

Hallo Spontifixus,

somit bist du mit der nächsten Aufgabe dran.

Hätte ich damals bei der Mathe-Prüfung auch schon das WWW verwenden dürfen... 😄

mfG Gü

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

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

XAML-Texteditor

Die nächste Aufgabe braucht keine Logik - und zwar im wahrsten Sinne des Wortes:
Erstelle einen kleinen Texteditor ausschließlich in XAML. Für den Editor sind folgende Anforderungen definiert:
1.Der Editor besteht aus genau einem Fenster 1.Der Editor hat direkt unter dem Fenstertitel eine Menüleiste mit einem Menü beschriftet mit "Editor". Darin Menüpunkte Rückgängig, Wiederherstellen, Kopieren, Ausschneiden und Einfügen, die jeweils auch über die Windows-üblichen Tastenkürzel ansprechbar sein müssen und in der jeweils eingestellten Sprache des Betriebssystems beschriftet sein sollen. Zusätzlich sollen die Tastenkürzel im Menü angezeigt werden. Die Menüpunkte dürfen nur aktiviert werden, wenn die entsprechende Aktion verfügbar ist. 1.Der Editor verfügt über einen Eingabebereich für den Text, der den gesamten Rest des Fensters einnimmt.

Der Code zur Lösung ist nicht als Dateianhang, sondern inline im Beitrag zu posten. Es gilt je kürzer desto besser - Trotzdem sollte das XAML natürlich wie üblich formatiert sein.

EDIT: Natürlich darf das C#-Projekt weitere notwendige Dateien wie z.B. die App.xaml enthalten.

Viel Spaß 😃

Hallo,

die Aufgabe find ich nett 🙂 Hab sie auch gelöst, aber lass gerne Anderen den Vortritt. Ich find an der Aufgabe gut das sie auch für Einsteiger gut lösbar ist wenn man sich bissle in WPF eingelesen hat und nen recht mächtiges Feature von WPF verdeutlicht. 👍

Baka wa shinanakya naoranai.

Mein XING Profil.

Moin moin,

wenn die bisherige Aufgabe nicht gelöst wurde, kann nach bisherigen Regeln dieses Threads jeder eine neue Aufgabe stellen.

Die Lösung für meine Aufgabe wäre ein 14 Zeilen langer XAML-Schnipsel gewesen:

<Window xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation">
    <DockPanel>
        <Menu DockPanel.Dock="Top">
            <MenuItem Header="Editor">
                <MenuItem Command="Undo" />
                <MenuItem Command="Redo" />
                <MenuItem Command="Cut" />
                <MenuItem Command="Copy" />
                <MenuItem Command="Paste" />
            </MenuItem>
        </Menu>
        <RichTextBox />
    </DockPanel>
</Window>

Wenn talla eine Aufgabe hat - darf er aber gerne weitermachen 😉

Viele Grüße,
Markus 😃

...und nen recht mächtiges Feature von WPF verdeutlicht.

Nur der Vollständigkeit halber: Welches Feature davon meinst du? Die beliebige Control-Verschachtelung, das Menu, die integrierte Interaktion der Menüpunkte mit dem Editor, der Editor an sich?

Hallo JunkyXL,

ich lege meine Hand dafür ins Feuer, dass talla von Commands gesprochen hat 😃.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

Genau 😃 Ohne die ist die die Aufgabe in der Kürze nicht lösbar. Vor allem die Komfortfunktionen wie De/aktivieren der Menüpunkte, richtige Lokalisierung, KeyBindings usw. sind recht länglich auszuprogrammieren wenn man das von Hand macht. ( Okay, hinter den Commands bzw. CommandTargets mit der Logik, liegt natürlich ne Menge Code, aber der ist in dem Beispiel ja nicht sichtbar und das ergibt dann ein kurzes Stück XAML was nen halber Editor ist.)
Die Schachtelungsmöglichkeiten der Controls in WPF wird hier gar nicht so arg deutlich find ich, da es in Windows Forms ähnlich aussehen könnte mit einem LayoutContainer und verschiedenen Children. Auch das MenuItems in ein Menu gesteckt werden scheint nicht besonders. Wenn man weiß das man auch beliebig anderes Zeug ins Menu packen kann, oder nen Menu als Child von nem Button packen kann gG, dann wird der Unterschied zu Windows Forms deutlich.

Hab das Angebot eine Aufgabe stellen zu dürfen gar nicht gesehen gehabt, aber ich überleg mir was bis morgen. Falls ich bis Morgen Mittag (26.10.2010 - 12.00 Uhr) nichts geschrieben habe darf gerne jemand anderes eine Aufgabe stellen.

Baka wa shinanakya naoranai.

Mein XING Profil.

Hallo,

Falls ich bis Morgen Mittag (26.10.2010 - 12.00 Uhr) nichts geschrieben habe darf gerne jemand anderes eine Aufgabe stellen.

Ich bin mal so frei 😉

Folgende Aufgabe:


Erstelle einen Cache zudem Objekte hinzugefügt werden können. Die Objekte sollen per Schlüssel abgerufen werden können (also so wie ein Dictionary<TKey, TValue>).

Für jedes Objekt im Cache soll ein Ablaufdatum angeben werden können, so dass beim Zugriff niemals ein abgelaufenes Objekt zurückgegeben wird. Dabei soll es zwei Arten des Ablaufsdatum geben:
[list]
[*]absoluter Ablauf, d.h. sobald das Objekt dem Cache zugeführt wurde beginnt der Ablaufzähler -> AbsoluteExpiration
[*]Zugriff-Ablauf, d.h. wenn seit dem Hinzufügen zum Cache nicht binnen des Intervalls auf das Objekt (über den Key) zugegriffen wird läuft es ab -> AccessExpiration
[/list]

Es gelten die "üblichen" Bedingungen: Frameworks- / 3rd-Party-Klassen sind verboten! Auch die in .net enthaltenen Caches sind nicht erlaubt - selbst machen ist angesagt ;-)

Viel Spass bei der Aufgabe!

mfG Gü

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

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

Hallo,

da die Aufgabe nicht gelöst wurde stell ich meine Lösung rein und gegebe das Spiel somit explizit frei.


using System;

namespace SimpleCache
{
	public sealed class CacheItem
	{
		public object Item      { get; private set; }
		public DateTime TimeOut { get; private set; }
		//---------------------------------------------------------------------
		public CacheItem(object item, TimeSpan timeSpanForTimeOut)
		{
			this.Item    = item;
			this.TimeOut = DateTime.Now + timeSpanForTimeOut;
		}
	}
}


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

namespace SimpleCache
{
	public sealed class Cache : IDisposable
	{
		private const int scavengerIntervall = 10 * 60 * 1000;
		private readonly Dictionary<string, CacheItem> _cachedItems;
		private readonly Timer  _timer;
		private readonly object _syncRoot = new object();
		//---------------------------------------------------------------------
		public Cache()
		{
			_cachedItems = new Dictionary<string, CacheItem>();

			_timer = new Timer(
				this.Scavenge,
				null,
				scavengerIntervall,
				scavengerIntervall);
		}
		//---------------------------------------------------------------------
		public void Add(string key, object item, TimeSpan timeSpanForTimeOut)
		{
			CacheItem cacheItem = new CacheItem(item, timeSpanForTimeOut);

			lock (_syncRoot)
				_cachedItems[key] = cacheItem;
		}
		//---------------------------------------------------------------------
		public object GetItem(string key)
		{
			CacheItem cacheItem = null;
			lock (_syncRoot)
			{
				if (!_cachedItems.ContainsKey(key)) return null;
				cacheItem = _cachedItems[key];
			}

			if (cacheItem.TimeOut > DateTime.Now)
			{
				lock (_syncRoot)
					_cachedItems.Remove(key);

				return null;
			}

			return cacheItem.Item;
		}
		//---------------------------------------------------------------------
		private void Scavenge(object state)
		{
			DateTime now = DateTime.Now;

			lock (_syncRoot)
			{
				var outdatedKeys = _cachedItems
					.Where(kvp   => kvp.Value.TimeOut > now)
					.Select(kvp  => kvp.Key);

				foreach (string key in outdatedKeys)
					_cachedItems.Remove(key);
			}
		}
		//---------------------------------------------------------------------
		#region IDisposable Members
		private bool _isDisposed = false;
		//---------------------------------------------------------------------
		private void Dispose(bool disposing)
		{
			if (!_isDisposed)
			{
				if (disposing)
					if (_timer != null)
						_timer.Dispose();

				_isDisposed = true;
			}
		}
		//---------------------------------------------------------------------
		public void Dispose()
		{
			this.Dispose(true);
			GC.SuppressFinalize(this);
		}
		#endregion
	}
}

Ab .net 4.0 wäre statt dem Dictionary ein ConcurrentDictionary zu verwenden da dadurch der explizite Lock entfallen kann.

mfG Gü

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

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

Ich hab mir mal ne aufgabe ausgedacht. Wenn man die vorgegebenen zeilen nicht mitzählt, kann man sie in 15 zeilen lösen.

Es ist ohne das wörtchen unsafe und ohne die klasse Marshal lösbar. Wer es nicht ohne hinbekommt, kann es aber trotzdem benutzen.

Aufgabe: Füge dort, wo die fragezeichen stehen code ein, der bewirkt, dass das programm folgendes ausgibt:

method:A, Class:ClassA, filedA:1337
method:B, Class:ClassA, filedB:1337

     class Aufgabe
    {

        class ClassA
        {
            public int fieldA;
            public void Test()
            {
                Console.WriteLine("method:A, Class:" + this.GetType().Name + ", fieldA:" + this.fieldA);
            }
        }

        class ClassB
        {
            public int fieldB;
            public void Test()
            {
                Console.WriteLine("method:B, Class:" + this.GetType().Name + ", fieldB:" + this.fieldB);
            }
        }


        static void Main()
        {
            ClassA a = new ClassA();
            ClassB b = Magic(a);
            a.fieldA = 1337;
            a.Test();
            b.Test();
            Console.ReadLine();
        }

        private static ClassB Magic(ClassA a)
        {

        ??????


    }

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

Da mich jemand per pm gefragt hat:
Ich habe die schließende klammer hinter "Magic" bewusst weggelassen, um zu zeigen, das man auch hinter die Methode noch etwas schreiben kann.

Noch ein Tipp zum Googeln: LayoutKind.Explicit

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

Hey,

ich ergänze folgenden Code: (nutzt .NET 4.0 Featur für named parameters)

    return (new BrutalCastContainer{BRef=null, ObjectRef=a}).BRef;
}
        
[StructLayout(LayoutKind.Explicit)]
struct BrutalCastContainer
{
    [FieldOffset(0)]
    public object ObjectRef;
    [FieldOffset(0)]
    public ClassB BRef;
}

Insgesamt also:

using System;
using System.Runtime.InteropServices;

class Aufgabe
    {

        class ClassA
        {
            public int fieldA;
            public void Test()
            {
                Console.WriteLine("method:A, Class:" + this.GetType().Name + ", fieldA:" + this.fieldA);
            }
        }

        class ClassB
        {
            public int fieldB = 0;
            public void Test()
            {
                Console.WriteLine("method:B, Class:" + this.GetType().Name + ", fieldB:" + this.fieldB);
            }
        }


        static void Main()
        {
            ClassA a = new ClassA();
            ClassB b = Magic(a);
            a.fieldA = 1337;
            a.Test();
            b.Test();
            Console.ReadLine();
        }

        // Start Magic-Code 
        private static ClassB Magic(ClassA a)
        {
		    return (new BrutalCastContainer{BRef=null, ObjectRef=a}).BRef;
		}
        
        [StructLayout(LayoutKind.Explicit)]
        struct BrutalCastContainer
        {
            [FieldOffset(0)]
            public object ObjectRef;
            [FieldOffset(0)]
            public ClassB BRef;
        }
        // End Magic-Code 
    }

beste Grüße
zommi

Ich grübel schonmal über ne neue Aufgabe...

Passt, du bist dran.

ich ergänze folgenden Code: (nutzt .NET 4.0 Featur für named parameters)

dein code geht mit .net 3

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

So,

dann mal ne kleine Geschichte:


Die drei globalisierten Bankräuber Alice, Bob und Carl sind seit ihrem letzten Streifzug ziemlich zerstritten. Da alle drei in unterschiedlichen Ländern wohnen, läuft ihre Kommunikations komplett über das Internet.

Als es um die Planung der Beute-Aufteilung zwischen Alice und Bob für den nächsten Deal geht, traut keiner dem anderen. Da macht Carl den Vorschlag, dass sie doch beide einen verbindlichen Vertrag eingehen, der die Aufteilung regelt. [Damit man seinen Teil der gestohlenen Beute auch gerichtlich einklagen kann 😉]

Carl bietet sich als Vermittler an, fertigt die Verträge aus und schickt sie Alice und Bob. Doch Carl will Alice und Bob noch ein wenig ärgern, und so möchte er den beiden jeweils unterschiedliche Verträge zusenden:

Hiermit beschliessen Alice und Bob die Aufteilung der Beute. Alice bekommt 80 Prozent und Bob den Rest.

Doch Alice und Bob vertrauen prinzipiell auch Carl nicht und vermuten bereits, dass er ihnen einen Streich spielen will. Deshalb einigen sie sich darauf, dass sie zuvor ihre Vertragstexte abgleichen. Da sie mal etwas von Digitalen Signaturen gehört haben, wollen sie diese nutzen und so meinen sie, dass es genügen sollte, die Hash-Werte der Vertragstexte zu vergleichen.

Da sie nur 4 Bytes für ihre Hashfunktion verschwenden möchten, überlegen sie sich ein cleveres Verfahren: Alice schlug vor, zunächst das MD5-Verfahren zu nutzen und einfach die ersten 4 Bytes zu nehmen. Bob wendet ein, dass damit ja die restlichen 12 Bytes des MD5-Wertes völlig unberücktsichtigt bleiben. Da kommt Alice wiederum die Idee einfach auf den MD5-Hash nochmal MD5 anzuwenden, um alle Bytes zu verwenden und von diesem neuen Hash die ersten 4 Bytes zu nehmen. Bob findet diesen Einfall brillant und so einigen sie sich auf:

SpecialHash(message) = First4Bytes(MD5(MD5(message))

(Message ist ASCII-kodiert)

Carl hat das mitbekommen, und so muss er zwei neue Vertragstexte anfertigen, die immernoch den beiden obigen ähneln, aber den selben Hash-Wert besitzen:

SpecialHash(SpecialTextForAlice) = SpecialHash(SpecialTextForBob)

Dabei bedeutet "ähneln", dass in den obigen Texten an beliebig vielen Stellen die [B]Leerzeichen [/B]durch [B]doppelte Leerzeichen[/B] ersetzt werden dürfen.

Damit wären also folgende Sätze ähnlich:

```
Das ist ein Satz.
Das ist ein Satz.
Das ist ein Satz.
Das ist ein Satz.


Hilf Carl mit einem C#-Programm dabei, zwei zu den obigen Vertragstexten ähnliche zu finden, die den selben Hash-Wert besitzen!

Viel Spaß beim Lesen und Implementieren ! 😃

beste Grüße
zommi

Hi nochma,

als typischer Stakeholder hab ich natürlich vergessen, die nichtfunktionalen Anforderungen zu spezifizieren 😉

Das Programm soll solch eine Kollision innerhalb weniger Sekunden finden! (vielleicht eine, oder auch zwei)

beste Grüße
zommi

Hi,

ich habs mal versucht aber als C# Neuling schaff ich Sekundenzeiten allerdings nicht. Ich bin mir nichtmal sicher ob es stimmt. Ich brauch ca. 2,5min für den Vergleich aller 4.294.967.296 Möglichkeiten und finden ca. nach 1,5min das erste und einzige Ergebnis.

Achja ich hab das nur versucht schnell hinzubekommen und nicht wirklich auf Form und speziell Zeilenlänge geachtet. Sorry.


    class BeuteTeilen
    {
        public BeuteTeilen()
        {
            Stopwatch stopWatch = new Stopwatch();
            string vertragAlice = "Hiermit beschliessen Alice und Bob die Aufteilung der Beute." +
                                  " Alice bekommt 80 Prozent und Bob den Rest.";
            string vertragBob = "Hiermit beschliessen Alice und Bob die Aufteilung der Beute." +
                                " Bob bekommt 80 Prozent und Alice den Rest.";
            string[] splittedAlice = vertragAlice.Split(' ');
            string[] splittedBob = vertragBob.Split(' ');
            int variations = Convert.ToInt32(Math.Pow(2,splittedAlice.Length - 1));
            byte[] SpecialHashAlice = new byte[variations];
            byte[][] SpecialHashBob = new byte[variations][];

            for (int i = 0; i < variations; ++i)
                SpecialHashBob[i] = SpecialHash(SpecialText(splittedBob, i));

            stopWatch.Start();
            for (int i = 0; i < variations; ++i)
            {
                SpecialHashAlice = SpecialHash(SpecialText(splittedAlice, i));
                for (int j = 0; j < variations; ++j)
                {
                    if (VergleicheInhalte(SpecialHashAlice,SpecialHashBob[j]))
                    {
                        Console.WriteLine("__________________________________________________");
                        Console.WriteLine("Result nach: " + stopWatch.Elapsed.ToString());
                        Console.WriteLine("Alice: " + SpecialText(splittedAlice, i));
                        Console.WriteLine("Hash: " + System.BitConverter.ToString(SpecialHashAlice));
                        Console.WriteLine("---------------------------------------");
                        Console.WriteLine("Bob: " + SpecialText(splittedBob, j));
                        Console.WriteLine("Hash: " + System.BitConverter.ToString(SpecialHashBob[j]));
                    }
                }
            }
            Console.WriteLine("__________________________________________________");
            Console.WriteLine("Alles durchprobiert nach: " + stopWatch.Elapsed.ToString());
            stopWatch.Stop();
            Console.ReadLine();
        }
        //---------------------------------------------------------------------
        bool VergleicheInhalte(byte[] val1, byte[] val2)
        {
            if (val1[0] != val2[0] || val1[1] != val2[1] || val1[2] != val2[2] || val1[3] != val2[3])
            {
                return false;
            }
            else
                return true;
        }
        //---------------------------------------------------------------------
        string SpecialText(string[] splittedOrginal, int variation)
        {
            StringBuilder sbHelper = new StringBuilder();
            string asBinary = Convert.ToString(variation, 2).PadLeft(16, '0');

            for (int i = 0; i < splittedOrginal.Length - 1; ++i)
            {
                sbHelper.Append(splittedOrginal[i]);
                if (asBinary[i] == '1')
                    sbHelper.Append("  ");
                else
                    sbHelper.Append(" ");
            }
            sbHelper.Append(splittedOrginal[splittedOrginal.Length - 1]);
            return sbHelper.ToString();
        }
        //---------------------------------------------------------------------
        static byte[] SpecialHash(string message)
        {
            byte[] result = GetMD5Hash(GetMD5Hash(Encoding.Default.GetBytes(message)));
            return new byte[] { result[0], result[1], result[2], result[3] };
        }
        //---------------------------------------------------------------------
        static byte[] GetMD5Hash(byte[] BytesToHash)
        {
            return new MD5CryptoServiceProvider().ComputeHash(BytesToHash);
        }
    }

Meine Lösung war dann:


Result nach: 00:01:38.462238
Alice: Hiermit  beschliessen Alice und  Bob die  Aufteilung  der  Beute. Alice bekommt 80  Prozent  und Bob den  Rest.
Hash:A3-D5-6C-0A
------------------------------------------------
Bob: Hiermit beschliessen  Alice  und  Bob die Aufteilung der Beute.  Bob bekommt 80  Prozent  und Alice den  Rest.
Hash:A3-D5-6C-0A

Schaut aber gut aus! 👍

Carl dankt dir ! 😉

Wegen Performance:
*Konvertiere die 4-Byte langen Byte[]-Arrays in einen Int32 (mit dem BitConverter) Verwende zwei Dictionaries, oder zwei HashSets anstatt den einfachen Arrays. So kannst du auf Kollisionen dank der schnellen Contains-Methode in insgesamt O(n+m) suchen anstatt wie bei dir (wegen der verschachtelten Schleife) in O(nm) *...

Diese beiden Punkte sollten schon reichen um nen ausreichenden Speedup zu gewährleisten.

Mein Referenzprogramm sah so aus:

static void Main(string[] args)
{
    string originTextForAlice = "Hiermit beschliessen Alice und Bob die Aufteilung der Beute. Alice bekommt 80 Prozent und Bob den Rest.";
    string originTextForBob = "Hiermit beschliessen Alice und Bob die Aufteilung der Beute. Bob bekommt 80 Prozent und Alice den Rest.";

    string finalTextForAlice = "", finalTextForBob = "";

    HashSet<uint> hashesAlice = new HashSet<uint>();
    HashSet<uint> hashesBob = new HashSet<uint>();

    IEnumerator<string> textsAlice = AllModifiedTexts(originTextForAlice).GetEnumerator();
    IEnumerator<string> textsBob = AllModifiedTexts(originTextForBob).GetEnumerator();

    while (textsAlice.MoveNext() && textsBob.MoveNext())
    {
        string textForAlice = textsAlice.Current;
        string textForBob = textsBob.Current;

        uint hashAlice = SpecialHash(textForAlice);
        uint hashBob = SpecialHash(textForBob);

        if (hashesAlice.Contains(hashBob))
        {
            finalTextForBob = textForBob;
            finalTextForAlice = AllModifiedTexts(originTextForAlice).First(s => SpecialHash(s) == hashBob);
            break;
        }

        if (hashesBob.Contains(hashAlice))
        {
            finalTextForAlice = textForAlice;
            finalTextForBob = AllModifiedTexts(originTextForBob).First(s => SpecialHash(s) == hashAlice);
            break;
        }

        hashesAlice.Add(hashAlice);
        hashesBob.Add(hashBob);
    }

    Console.WriteLine("{0}: {1}", SpecialHash(finalTextForAlice), finalTextForAlice);
    Console.WriteLine("{0}: {1}", SpecialHash(finalTextForBob), finalTextForBob);
}

static MD5CryptoServiceProvider md5Hasher = new MD5CryptoServiceProvider();

//---------------------------------------------------------------------
static uint SpecialHash(string s)
{
    return BitConverter.ToUInt32(MD5(MD5(ASCIIEncoding.ASCII.GetBytes(s))), 0);
}

//---------------------------------------------------------------------
static byte[] MD5(byte[] message)
{
    return md5Hasher.ComputeHash(message);
}

//---------------------------------------------------------------------
static IEnumerable<string> AllModifiedTexts(string s)
{
    return JoinWithOneOrTwoSpaces(s.Split(' '));
}

//---------------------------------------------------------------------
static IEnumerable<string> JoinWithOneOrTwoSpaces(IEnumerable<string> words)
{
    if (words.Count() == 1)
        yield return words.Single();
    else
        foreach (string suffix in JoinWithOneOrTwoSpaces(words.Skip(1)))
        {
            yield return words.First() + " " + suffix;
            yield return words.First() + "  " + suffix;
        }
} 

Aber wie dem auch sei, deine Lösung tuts, damit du bist nun dran ! 🙂

Juhu. Und danke für die Hinweise.
Aber ich würde die Aufgabenstellung gerne erstmal abgeben. Ich werd zwar mal überlegen ob mir was einfällt, was nicht zu einfach für euch alle ist aber ich will das hier nicht allzulang blockieren. Grade weil ichs auch zum Üben gut find 😄

Na gut, dann bringe ich einmal eine kleine mathematische Aufgabe. (Die ich diese Woche in Haskell lösen musste.)

Gegeben sei ein ungerichteter Graph als Adjazenzliste dessen Knoten vier verschiedene Farben annehmen können. (blau, gelb, rot und grün).

Ziel ist es einen gegebenen Graphen falls möglich so einzufärben dass jeder Knoten eine andere Farbe hat als seine Nachbarn wobei Nachbar als mit einer Kante verbundener Nachbar definiert ist.


enum NodeColor 
{
  blue,
  yellow,
  red,
  green
}

class Node
{
  public int NodenID { get; set; }

  public NodeColor Color { get; set; }

  public ICollection<int> Neighbours { get; set; } // die IDs
}

wobei eure Methode der Form sein soll:


ICollection<Node> getColoredGraph(ICollection<Node> preColoredGraph);

Falls der Graph nicht einfärbar ist, soll Null zurückgegeben werden ansonsten der eingefärbte Graph.

Edit: Wäre natürlich schön, wenn ihr keinen naiven Ansatz verwendet.

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl

So da ja 1 Woche vergangen ist, und laut den Regeln dann jeder eine neue Aufgabe bringen darf, möchte ich mal etwas dazu beitragen 😉

Es soll eine Klasse entworfen werden, die den Wochentag eines Datum berechnen kann. Das Datum darf nicht als ein DateTime übergeben werden. Als Hilfe kann der Artikel Wochentagsberechnung verwendet werden.

Die Aufgabe richtet sich an die Anfänger hier im Forum. Mit ein bisschen lesen und nachdenken, ist diese Aufgabe gut lösbar.

Folgenden Beispiel Code stelle ich zur verfügung:


    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Bitte geben Sie ein Datum ein (dd.mm.YYYY): ");
            string inputDatum = Console.ReadLine();
            string[] splittedDatum = inputDatum.Split(new Char[] { '.' });

            Wochentag wochentag = new Wochentag();
            Int32 tag = wochentag.GetWochentag(Int32.Parse(splittedDatum[0]), Int32.Parse(splittedDatum[1]), Int32.Parse(splittedDatum[2]));
            
            Wochentage wt = (Wochentage)tag;
            Console.WriteLine("Der Wochentag lautet: {0}", wt);
            
            Console.ReadLine();
        }
    }

Das passende Enum dazu:


    enum Wochentage
    {
        Sonntag = 0,
        Montag = 1,
        Dienstag = 2,
        Mittwoch = 3,
        Donnerstag = 4,
        Freitag = 5,
        Samstag = 6
    }

Und noch der Methoden Rumpf:


    class Wochentag
    {
        public Int32 GetWochentag(Int32 tag, Int32 monat, Int32 jahr)
        {
            return ...
        }
    }

Wünsche allen viel freude beim lösen.

Grüße Stephan

Ich war mal so frei die Aufgabe zu lösen, wenn auch eventuell nicht perfekt.

Meine Klasse Wochentag sieht wie folgt aus:


class Wochentag
{
	Int32[] monthNumbers = new Int32[] { 0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 };

		public Int32 GetWochentag(Int32 tag, Int32 monat, Int32 jahr)
        {
			Int32 day = tag % 7;
			Int32 yearHundred = 0;
			if (jahr > 99)
			{
				String year = jahr.ToString();
				jahr = Convert.ToInt32(year.Substring(2));
				// here we must decide...
				if(year.Length == 4)
					yearHundred = Convert.ToInt32(year.Substring(0, 2));
				else
					yearHundred = Convert.ToInt32(year.Substring(0, 1));
			}
			bool bSchaltJahr = IsSchaltJahr(jahr);
			jahr = (jahr + (jahr / 4)) % 7;
			yearHundred = (3 - (yearHundred % 4)) * 2;

			Int32 correct = 0;
			if(bSchaltJahr)
				correct = 6;

			tag = (day + yearHundred + jahr + correct + monthNumbers[monat-1]) % 7;

			return tag;
        }

		private bool IsSchaltJahr(Int32 year)
		{
			bool isIt = false;

			Int32 tempForeYear = year - 1;
			year = (year + (year / 4)) % 7;
			tempForeYear = (tempForeYear + (tempForeYear / 4)) %7;
			if (year - tempForeYear == 2)
				isIt = true;
			return isIt;
		}
}

Eine Aufgabe habe ich momentan nicht. - Sollte jemandem eine einfallen, kann er diese gern stellen. 😃

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

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

Hey,

ja ich bin auchmal wieder da^^

dann mach ich einfach mal das nächste Rätsel und hoffe mal, dass es noch nicht gestellt wurde. Die Aufgabe ist es eine Klasse zu schreiben, die eine Liste von, sagen wir mal strings, darstellt. Implementieren sollt ihr die Methoden: Add, RemoveAt, Insert und Clear. Natürlich sind jegliche Collections verboten, sonst ist das ja keine Aufgabe. ist auch relativ einfach zu Lösen und es gibt nicht nur "die" Lösung. Wie ihr das macht ist wurscht.

lg pdelvo

Hinweis von talla vor 13 Jahren

Beachtet bitte das der Aufgabensteller die Lösung auch absegnet und für richtig befindet! Nicht einfach ne neue Aufgabe Stellen nur weil jemand gepostet hat das er eine Lösung hat ohne das deren Korrektheit überprüft wurde.

Hinweis von winSharp93 vor 13 Jahren

Auf Hinweis von herbivore nochmals zur Klarstellung: Die Lösung mag zwar einfach sein, ist aber aufgrund von Einschränkungen (Verwendung von Rekursion, O(N) Aufwand für Einfügeoperationen, ...) nicht für produktiven Einsatz geeignet. Da gibt es bessere Listen u.a. in der FCL.


public sealed class LinkedList<T>
{
    private Node<T> _first;

    public int Count
    {
        get
        {
            return this._first.CountFollowing();
        }
    }
    public T this[int index]
    {
        get
        {
            Node<T> node = this._first.GetNodeAt(index + 1);

            return node.Item;
        }
    }

    public LinkedList()
    {
        this._first = new Node<T>();
    }

    public void Add(T item)
    {
        this._first.AppendAtEnd(item);
    }
    public void Insert(T item, int index)
    {
        Node<T> node = this._first.GetNodeAt(index);

        node.Append(item);
    }
    public void RemoveAt(int index)
    {
        Node<T> previousNode = this._first.GetNodeAt(index);
        previousNode.DropFollowing();
    }
    public void Clear()
    {
        this._first = new Node<T>();
    }
}

internal class Node<T>
{
    public T Item
    {
        get;
        private set;
    }
    public Node<T> Next
    {
        get;
        private set;
    }
    public bool IsLast
    {
        get
        {
            return this.Next == null;
        }
    }

    public Node()
    {
    }
    private Node(T item)
    {
        this.Item = item;
    }

    public void AppendAtEnd(T item)
    {
        if (this.IsLast)
            this.Next = new Node<T>(item);
        else
            this.Next.AppendAtEnd(item);
    }
    public void Append(T item)
    {
        Node<T> oldNext = this.Next;
        this.Next = new Node<T>(item);
        this.Next.Next = oldNext;
    }
    public int CountFollowing()
    {
        if (this.IsLast)
            return 0;

        return this.Next.CountFollowing() + 1;
    }
    public Node<T> GetNodeAt(int index)
    {
        if (index == 0)
            return this;

        if (this.IsLast)
            throw new ArgumentOutOfRangeException();

        return this.Next.GetNodeAt(index - 1);
    }
    public void DropFollowing()
    {
        if (this.IsLast)
            throw new InvalidOperationException();

        this.Next = this.Next.Next;
    }
}

Testcode:


LinkedList<string> list = new LinkedList<string>();

Console.WriteLine("Count {0}", list.Count);

list.Add("Hallo");
Console.WriteLine("Count {0}; list[0]: {1}", list.Count, list[0]);

list.Add(" ");
Console.WriteLine("Count {0}", list.Count);

list.Add("Welt");
Console.WriteLine("Count {0}", list.Count);

for (int i = 0; i < list.Count; i++)
    Console.Write(list[i]);
Console.WriteLine();

list.RemoveAt(1);
Console.WriteLine("Count {0}", list.Count);

for (int i = 0; i < list.Count; i++)
    Console.Write(list[i]);
Console.WriteLine();

list.Insert("-", 1);
for (int i = 0; i < list.Count; i++)
    Console.Write(list[i]);
Console.WriteLine();

list.Clear();
Console.WriteLine("Count {0}", list.Count);

Console.ReadKey();

Nachdem ja kein Einspruch gegen meine Lösung erfolgte und ich gebeten wurde, eine neue Aufgabe zu stellen - hier ist sie 😉 :
Ergänzt den obigen Code für die Liste um eine Reverse Methode.

Hallo,

Hier eine einfache Reverse-Methode:

    public void Reverse()
    {
      Node<T> node = _first.Next;
      Clear();
      while(node != null)
      {
        _first.Append(node.Item);
        node = node.Next;
      }
    }

Da der Zugriff auf Next schreibgeschützt ist, und keine Append/Remove-Methoden für Nodes vorhanden sind, erschien es mir als einfachste Variante, die Liste zu leeren und die Items in umgekehrter Reihenfolge neu anzufügen. Alles andere bedarf IMHO außer der zusätzlichen Methode noch weiterer Änderungen.

Gruß, MarsStein

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

Gut, gut 🙂
Du bist dran!

Hallo,

hier die neue Aufgabe, eher ein Appetithäppchen für zwischendurch, das sich in ein paar Zeilen lösen lässt 🙂

Zeigt anhand folgendem Beispiel, daß man mit .NET das Prinzip der Kapselung ziemlich einfach aushebeln kann.
Erstellt hierzu innerhalb der Methode CreateForbiddenObject ein Objekt der Klasse MyNested, welches beim Aufruf seiner ToString()-Methode den an CreateForbiddenObject übergebenen String ausgibt.
Es darf nur die Methode CreateForbiddenObject bearbeitet werden, MyClass und MyNested müssen unangetastet bleiben.

Die Ausgabe müsste also etwa so aussehen:

MyClass+MyNested: nichts ist unmöglich!

Gegeben ist dazu folgender Code:

class MyClass
{
  private class MyNested
  {
    private string name = null;
    
    private MyNested() { }

    public override string ToString() { return name; }
  }
}

class Program
{
  public static void Main(string[] args)
  {
    object o = CreateForbiddenObject("nichts ist unmöglich!");
    Console.WriteLine("{0}: {1}", o.GetType().FullName, o);
    Console.Read();
  }

  static object CreateForbiddenObject(string name)
  {
    // hier den nötigen Code einfügen
  }
}

Viel Spaß, MarsStein

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