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
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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



Dabei seit:
Beiträge: 46

beantworten | zitieren | melden

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

Avatar #avatar-3152.png


Dabei seit:
Beiträge: 832
Herkunft: /dev/null

beantworten | zitieren | melden

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"
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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ü
Attachments
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!"
private Nachricht | Beiträge des Benutzers
Spontifixus
myCSharp.de - Member

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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. :)
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

Stimmt auffallend. Werde ich noch korrigieren.
private Nachricht | Beiträge des Benutzers
Spontifixus
myCSharp.de - Member

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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.
Zitat
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!"
private Nachricht | Beiträge des Benutzers
Spontifixus
myCSharp.de - Member

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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 :)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Spontifixus am .
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

Hallo Floste,

super

Du bist dran.


mfG Gü
Attachments
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!"
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Stimmt genau, und bei der zeit kann man nicht meckern. Poste bitte mal deinen code.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

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

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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!"
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

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

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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 :D"
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
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Spontifixus am .
Attachments
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7559
Herkunft: Waidring

beantworten | zitieren | melden

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... :D

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

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

XAML-Texteditor

beantworten | zitieren | melden

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
  2. 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.
  3. Der Editor verfügt über einen Eingabebereich für den Text, der den gesamten Rest des Fensters einnimmt.

  4. 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ß :)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Spontifixus am .
private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

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

Avatar #avatar-3052.gif


Dabei seit:
Beiträge: 408
Herkunft: Hannover

beantworten | zitieren | melden

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

Avatar #avatar-3234.gif


Dabei seit:
Beiträge: 1732
Herkunft: Ein paar Bytes südlich von string

beantworten | zitieren | melden

Zitat von talla
...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?
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

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

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

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