Laden...

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

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.545 Views
2.298 Beiträge seit 2010
vor 10 Jahren

Ja war mein Fehler, hatte ich jedoch korrigiert. - Aber ich seh, da fehlt dennoch noch etwas.

Die korrigierte Variante noch einmal:


static string GetMembers(Type type)
{
    string sMemberInfos = string.Empty;
    foreach (string sMember in GetMembers(type, string.Empty))
        sMemberInfos += String.Concat(sMember, Environment.NewLine);

   return sMemberInfos;
}

static List<string> GetMembers(Type type, string sMemberCallPath)
{
    // list to temporary hold the callpaths
    List<string> callPaths = new List<string>();

    if (sMemberCallPath != string.Empty)
        sMemberCallPath += ".";

    // filter all types of namespace System
    if (type.FullName.StartsWith("System"))
        return new List<string>();

    MemberInfo[] members = type.GetMembers();

    foreach (MemberInfo member in members)
    {
        switch (member.MemberType)
        {
            case MemberTypes.Field:
                FieldInfo finfo = member as FieldInfo;
                if(!callPaths.Contains(String.Concat(sMemberCallPath,finfo.Name)))
                    callPaths.Add(String.Concat(sMemberCallPath,finfo.Name));
                if (finfo.IsPublic)
                    callPaths.AddRange(GetMembers(finfo.FieldType, String.Concat(sMemberCallPath, member.Name)));
                break;
            case MemberTypes.Property:
                PropertyInfo pinfo = member as PropertyInfo;
                if (!callPaths.Contains(String.Concat(sMemberCallPath, pinfo.Name)))
                    callPaths.Add(String.Concat(sMemberCallPath, pinfo.Name));
                    callPaths.AddRange(GetMembers(pinfo.PropertyType, String.Concat(sMemberCallPath, member.Name)));
                break;
            case MemberTypes.Method:
                string sMemberName = member.Name;
                if (member.Name.StartsWith("Get") || member.Name.StartsWith("Set"))
                    sMemberName = member.Name.Remove(0, 3);
                else if (member.Name.StartsWith("get_") || member.Name.StartsWith("set_"))
                    sMemberName = member.Name.Remove(0, 4);
                if(!callPaths.Contains(String.Concat(sMemberCallPath, sMemberName)))
                    callPaths.Add(String.Concat(sMemberCallPath, sMemberName));
                break;
        }
    }

    callPaths.Sort();

    return callPaths; ;
}

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

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

2.921 Beiträge seit 2005
vor 10 Jahren

@inflames2k:

Ich sehe die Aufgabe als gelöst an,
für die entsprechenden Entities im vorgegebenen Modell wurde alles ausgegeben wie erwartet.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

2.298 Beiträge seit 2010
vor 10 Jahren

Da mir auf die schnelle keine Frage einfällt, geb ich die nächste Frage für alle anderen frei. 😉

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

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

P
660 Beiträge seit 2008
vor 10 Jahren

Hallo zusammen

Im Anhang befindet sich eine geheime Nachricht. Wie lautet sie?

Als Info noch:*Die grafik ist selbsterstellt (Per Code natürlich) *Mein Code ist 16 zeilen Lang (ohne Optimierungen) *Die Grafik wurde nicht in Schwarz/Weiss bzw. Graustufen konvertiert

Wenn noch Infos fehlen oder etwas unklar ist, einfach melden.

Viel Spass!

MfG
ProGamer*Der Sinn Des Lebens Ist Es, Den Sinn Des Lebens Zu Finden! *"Wenn Unrecht zu Recht wird dann wird Widerstand zur Pflicht." *"Ignorance simplifies ANY problem." *"Stoppt die Piraterie der Musikindustrie"

2.891 Beiträge seit 2004
vor 10 Jahren

Im Anhang befindet sich eine geheime Nachricht. Wie lautet sie?

"HELLO WORLD". Sieht man aber quasi schon 😃 Und validiert mit der Pipette aus Paint.NET und der ASCII-Tabelle.

Was willst du als Lösung? Nur die Nachricht? Code, der die Nachricht dekodiert? Oder den Ursprungscode, der das Bild erzeugt?

P
660 Beiträge seit 2008
vor 10 Jahren

Nur die Nachricht?

hast du schon gesagt.

Code, der die Nachricht dekodiert? Oder den Ursprungscode, der das Bild erzeugt?

Wenns geht beides, ansonsten poste ich meinen Code 😉

hmm, war wohl zu einfach was? XD
wie auch immer du bist dran.

EDIT:

Da leider noch kein Code gepostet wurde, werde ich natürlich meinen nicht vorenthalten.
(Die 16 Zeilen Code bezogen sich auf das auslesen (der gesamte Code ist nicht Optimiert!))


	public class Program
	{
		private const string Path = @"C:\Temp\SecretMessage.jpg";

		static void Main( string[] args )
		{
			CreateBitmap(Path, 32, new char[] { 'H', 'E', 'L', 'L', 'O', ' ', 'W', 'O', 'R', 'L', 'D' });

			Console.WriteLine(ReadBitmap(Path, 32));

			Console.ReadKey();
		}


		private static void CreateBitmap( string path, int pixelHeightAndWidth, char[] message )
		{
			var tmpBitmapWidth = message.Length * pixelHeightAndWidth;
			var tmpBitmapHeight = pixelHeightAndWidth;

			using ( var bmp = new Bitmap( tmpBitmapWidth, tmpBitmapHeight ) )
			{
				var tmpOffsetWidth = 0;
				foreach ( var t in message )
				{
					for ( var x = tmpOffsetWidth; x < ( tmpOffsetWidth + pixelHeightAndWidth ); x++ )
					{
						for ( var y = 0; y < tmpBitmapHeight; y++ )
						{
							var tmpColor = Color.FromArgb( 255, t, t, t );
							bmp.SetPixel( x, y, tmpColor );
						}

					}
					tmpOffsetWidth += pixelHeightAndWidth;
				}
				bmp.Save( path );
			}
		}

		private static string ReadBitmap( string path, int pixelHeightAndWidth )
		{
			var tmpRes = new StringBuilder();

			using (var FS = new FileStream(path, FileMode.Open,FileAccess.Read,FileShare.Read))
			{
				using ( var bmp = new Bitmap( FS ) )
				{
					for ( int x = 0; x < bmp.Width; x += pixelHeightAndWidth )
					{
						tmpRes.Append((char)bmp.GetPixel(x, 1).R);
					}
				}
			}

			return tmpRes.ToString();
		}
	}

MfG
ProGamer*Der Sinn Des Lebens Ist Es, Den Sinn Des Lebens Zu Finden! *"Wenn Unrecht zu Recht wird dann wird Widerstand zur Pflicht." *"Ignorance simplifies ANY problem." *"Stoppt die Piraterie der Musikindustrie"

309 Beiträge seit 2008
vor 10 Jahren

Mist zu langsam.... X(

Aber deine Encode Methode ist doch arg umständlich...

Hier ausser Konkurrenz meine in 8 Zeilen:


static Bitmap Encode(int height, string message)
{
    int width = message.Length * height;
    Bitmap bitmap = new Bitmap(width, height);
    using (Graphics g = Graphics.FromImage(bitmap))
    {
        for (int i = 0, j = 0; i < width; i += height, j++)
            g.FillRectangle(new SolidBrush(Color.FromArgb(255, message[j], message[j], message[j])), new Rectangle(i, 0, height, height));
    }
    return bitmap;
}

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

2.891 Beiträge seit 2004
vor 10 Jahren

Dann die neue Aufgabe:


Der folgende Code (sic!)...
[csharp]
using System;

static class Program
{
	static void Main()
	{
		var limit = 10;
		limit = "five";
		for (var x=0;x<limit;x++)
		{
			Console.WriteLine(x);
			Console.WriteLine("The current value of x is {0}",x);
		}
	}
}
[/csharp]
...soll folgende Ausgabe erzeugen:
[frame]
[FONT]0
The current value of x is zero
1
The current value of x is one
2
The current value of x is two
3
The current value of x is three
4
The current value of x is four[/FONT]

Wie geht das?[/frame]

6.911 Beiträge seit 2009
vor 10 Jahren

Hallo dN!3L,

mit Roslyn Code daraus erstellen mit dem es funktioniert. Also einen Typen verwenden, indem implizite Casts von int und string möglich sind und ToString entsprechend überschrieben ist.

Gut dass du nur gefragt "wie" das geht, und nicht "wie genau", denn das weiß ich nicht 😉

mfG Gü

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

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

2.921 Beiträge seit 2005
vor 10 Jahren

Ist das auch Absicht:


var limit = 10;
limit = "five";

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

2.891 Beiträge seit 2004
vor 10 Jahren

Ist das auch Absicht

Das ist alles Absicht. 😃
Kompiliert auch mit dem ganz normalen C#-Compiler.

5.941 Beiträge seit 2005
vor 10 Jahren

Hallo

Kompiliert bei mir nicht:> Fehlermeldung:

Cannot implicitly convert type 'string' to 'int'

In Zeile:


limit = "five";

"soll", also eine Änderung machen, dann läuft es meinst du.

Gruss Peter

--
Microsoft MVP - Visual Developer ASP / ASP.NET, Switzerland 2007 - 2011

2.891 Beiträge seit 2004
vor 10 Jahren

Hallo zusammen,

der Code der Main-Methode von oben (ich habe noch die Methoden- und Klassendefinition hinzugefügt) soll nicht geändert werden. Code außerhalb der Main-Methode hinzuzufügen ist erlaubt.
So für sich allein kompiliert der Code auch nicht - was ist also nötig, damit der Code erstens kompiliert und zweitens die gewünschte Ausgabe liefert?

1.361 Beiträge seit 2007
vor 10 Jahren

I present... class var 😄

using System;

static class Program
{
    static void Main()
    {
        var limit = 10;
        limit = "five";
        for (var x=0;x<limit;x++)
        {
            Console.WriteLine(x);
            Console.WriteLine("The current value of x is {0}",x);
        }
    }
}

// new code here

class var
{
    static string[] words = { "zero", "one", "two", "three", "four", "five"};
    int val {get; set;}
    public static implicit operator var(int n){ return new var(){val=n}; }
    public static implicit operator var(string s) { return Array.IndexOf(words, s); }
    public static implicit operator int(var v) { return v.val; }
    public static bool operator <(var a, var b) { return a.val < b.val; }
    public static bool operator >(var a, var b){ return b < a; }
    public static var operator ++(var v) { v.val++; return v; }
    override public string ToString() { return words[val]; }
}

Herrlich, dass so etwas funktioniert 😃
(getestet unter OSX mit Mono)

beste Grüße
zommi

D
96 Beiträge seit 2012
vor 10 Jahren

Super Aufgabe. Ohne in eine bestimmte Definition in der C# Spezifikation zu gucken, hätte ich wohl etwas länger daran geknabbert 😃. Die Lösung poste ich allerdings nicht, da ich zu einem keine Aufgabe habe und zum anderen den Spaß an der Aufgabe nicht vermasseln möchte 😃

Edit: Da war jemand mit der Lösung etwas schneller.

2.891 Beiträge seit 2004
vor 10 Jahren

I present... class var 😄

Genau! Der Trick ist, dass var eine Klasse ist. Die Möglichkeit, verschiedene Typen zuweisen zu können, bekommt man dann durch implizite Operatoren. Und das Verhalten bei Console.WriteLine ebenso (plus Hilfe von der Overload Resolution).
Siehe auch Jon Skeet: Abusing C# on Vimeo. zommi ist dran 👍

1.361 Beiträge seit 2007
vor 10 Jahren

Hier meine neue Aufgabe:

Welches 3-buchstabige ASCII-Wort beginnt mit der 787471. Binärstelle des Nachkomma-Anteils von Pi? [COLOR]
(Also ab dem 787471. Bit bei Pi, wenn man Pi im binären System aufschreibt)

Wegen Nachfrage noch einmal umschrieben:
Pi_10 = 3,141592653...
Pi_2 = 11,00100100001...

Die 6te dezimale Nachkommastelle ist eine 2.
Die 6te binäre Nachkommastelle ist eine 1.

Fasse nun die binären Nachkommstellen beginnend ab 787471. bis einschließlich 787494. als ASCII-Zeichenfolge auf. (Das sind 24 Bits, also 3 Bytes)[/COLOR]

beste Grüße
zommi

//Prüf-Möglichkeit:
Wenn man 1 Million Mal MD5 auf das gesuchte Wort anwendet (also auch immer wieder MD5 auf den resultierenden ASCII-Hash-String selbst), ergibt sich:

182C3950020DBE5969AF859ADF93BBD4

//Hinweis: Mit "Wort" meine ich ganz abstrakt 3 Buchstaben. Ist nicht unbedingt ein Wort im Wörterbuch-Sinne

1.361 Beiträge seit 2007
vor 10 Jahren

Weil mir die folgende Aufgabe auch noch sehr gefiel, und vielleicht den weniger Formel-affinen besser gefällt, hier noch eine Alternativ-Aufgabe, die sich aus Implementierungsfrage zu Uri, HttpUrl und HttpServer ergab:

Gegeben sei eine HTTP-URL.
Extrahiere die Subdomain(s), Basis-Domain und die Domain-Endung.

[pre]http://www.mycsharp.de                                => (www) (mycsharp) (de)
http://de.wikipedia.org/wiki/Uniform_Resource_Locator => (de) (wikipedia) (org)
http://google.co.uk/                                  => () (google) (co.uk)
http://de.mail.yahoo.com/                             => (de.mail) (yahoo) (com)
...[/pre]


Die Alte (obigen) Aufgabe läuft auch weiter. Ihr könnt euch aussuchen, welche ihr bearbeiten wollt.
Zu der Pi-Aufgabe noch ein Tipp: "Bailey-Borwein-Plouffe". Mein zugehöriges Programm ist unter 50 Codezeilen, also machbar 😉

Beste Grüße
zommi

309 Beiträge seit 2008
vor 10 Jahren

Hmm..

Zur Pi Aufgabe:

Ich glaube die Lösung ist:

"mib" 8) 8)

Code folgt, das ist nur "manuell" ermittelt. :evil:

Bin mir aber nicht sicher, da ich bei MD5 ins Schleudern komme. 🤔

Brechnest du die MD5 Summe 1 Mio mal jeweils vom HEX-String oder direkt vom Byte-Array? ?(

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

1.361 Beiträge seit 2007
vor 10 Jahren

Wie hast du es manuell gemacht?

Brechnest du die MD5 Summe 1 Mio mal jeweils vom HEX-String oder direkt vom Byte-Array? verwirrt

Ein einzelnes MD5-Hashing sieht bei mir so aus:
String -> ASCII Byte-Array -> MD5 Byte-Array -> String mit großbuchstaben HEX-Werten (ohne Bindestriche oder so)

Und das eben jetzt mehrfach.

beste Grüße
zommi

309 Beiträge seit 2008
vor 10 Jahren

Wie hast du es manuell gemacht?

Naja, zumindest ohne selber Code zu schreiben.

Zuerst hab ich mit dem originalen C-Programm von David H. Bailey (BBP Code Directory) mir die entsprechende HEX Postion berechnen lassen, dann mit Hilfe eines Online-Converters zuerst nach Binär und dann nach ASCII Konvertiert.

Ein einzelnes MD5-Hashing sieht bei mir so aus:
String -> ASCII Byte-Array -> MD5 Byte-Array -> String mit großbuchstaben HEX-Werten (ohne Bindestriche oder so)

8o
Danke ich hatte den String in Kleinbuchstaben. Hätte auch gut selber drauf kommen können/müssen. Kopf->Tisch

Hier der Code:
Ist genau wie die "manuelle" Vorgehensweise. Nicht sonderlich elegant (geht sicher auch ohne das HEX/Binär String konvertiere) und mehr als 50 Zeilen aber es funktioniert!


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;

namespace BBP
{
    class Program
    {
        static void Main(string[] args)
        {
            const string testHash = "182C3950020DBE5969AF859ADF93BBD4";
            double pid, s1, s2, s3, s4;

            // Vorherige "Hex-Nachkommastelle" zur gesuchten Position finden
            int id = 787471 / 4; // 196867;

            // Hex-Nachkommastellen berechnen
            s1 = BBP.Series(1, id);
            s2 = BBP.Series(4, id);
            s3 = BBP.Series(5, id);
            s4 = BBP.Series(6, id); 
            pid = 4 * s1 - 2 * s2 - s3 - s4;
            pid = pid - (int)pid + 1;
            string hex = BBP.Ihex(pid);

            // In Binärstring umwandeln und Bit-Position korrigieren
            string bin = HexToBinString(hex).Substring(787471 % 4 - 1);
            // In Bytes umwandeln 
            byte[] bytes = BinStringToByte(bin);
            // und ASCII decodieren
            string word = Encoding.ASCII.GetString(bytes, 0, 3);
            Console.WriteLine("Wort: {0}", word);

            // Testen
            MD5 md5 = MD5.Create();
            string hash = word;
            for (int i = 0; i < 1000000; i++)
                hash = GetMd5Hash(md5, hash);

            Console.WriteLine("Hash: {0}", hash);
            Console.WriteLine("Test-Hash: {0}", testHash);
            Console.WriteLine("Hashes are{0} equal!", hash != testHash ? " not" : "");
            
            Console.ReadLine();
        }

        // Hilfsmethoden

        static string GetMd5Hash(MD5 md5Hash, string input)
        {

            byte[] data = md5Hash.ComputeHash(Encoding.ASCII.GetBytes(input));
            StringBuilder sBuilder = new StringBuilder();
            for (int i = 0; i < data.Length; i++)
                sBuilder.Append(data[i].ToString("X2"));

            return sBuilder.ToString();
        }

        static byte[] BinStringToByte(string binstring)
        {
            var bytesAsStrings =
                                binstring.Select((c, i) => new { Char = c, Index = i })
                                     .GroupBy(x => x.Index / 8)
                                     .Select(g => new string(g.Select(x => x.Char).ToArray()));

            return bytesAsStrings.Select(s => Convert.ToByte(s, 2)).ToArray();
        }

        static string HexToBinString(string hexstring)
        {
            return String.Join(String.Empty,
                        hexstring.Select(
                        c => Convert.ToString(Convert.ToInt32(c.ToString(), 16), 2).PadLeft(4, '0')));
        }
    }

    /// <summary>
    /// "Quick and dirty" Port des orginalen C Codes von David H. Bailey 
    /// </summary>
    static class BBP
    {
        public static string Ihex(double x)
        {
            int i;
            double y;
            StringBuilder sb = new StringBuilder();
            string hx = "0123456789ABCDEF";

            y = Math.Abs(x);
            for (i = 0; i < 16; i++)
            {
                y = 16 * (y - Math.Floor(y));
                sb.Append(hx[(int)y]);
            }
            return sb.ToString();
        }

        /// <summary>
        /// This routine evaluates the series  sum_k 16^(id-k)/(8*k+m) 
        /// using the modular exponentiation technique
        /// </summary>
        /// <param name="m"></param>
        /// <param name="id"></param>
        /// <returns></returns>
        public static double Series(int m, int id)
        {
            int k;
            double ak, p, s, t;
            double eps = 1e-17;

            s = 0;
            /*  Sum the series up to id. */
            for (k = 0; k < id; k++)
            {
                ak = 8 * k + m;
                p = id - k;
                t = Expm(p, ak);
                s = s + t / ak;
                s = s - (int)s;
            }

            /*  Compute a few terms where k >= id. */
            for (k = id; k <= id + 100; k++)
            {
                ak = 8 * k + m;
                t = Math.Pow(16, (double)(id - k)) / ak;
                if (t < eps) break;
                s = s + t;
                s = s - (int)s;
            }
            return s;
        }
        /// <summary>
        /// expm = 16^p mod ak.  This routine uses the left-to-right binary 
        /// exponentiation scheme
        /// </summary>
        /// <param name="p"></param>
        /// <param name="ak"></param>
        /// <returns></returns>
        private static double Expm(double p, double ak)
        {
            int i, j;
            double p1, pt, r;
            int ntp = 25;
            double[] tp = new double[ntp];
            int tp1 = 0;

            /*  If this is the first call to expm, fill the power of two table tp. */
            if (tp1 == 0)
            {
                tp1 = 1;
                tp[0] = 1;

                for (i = 1; i < ntp; i++) 
                    tp[i] = 2 * tp[i - 1];
            }

            if (ak == 1) 
                return 0;

            /*  Find the greatest power of two less than or equal to p. */
            for (i = 0; i < ntp; i++) if (tp[i] > p) break;

            pt = tp[i - 1];
            p1 = p;
            r = 1;

            /*  Perform binary exponentiation algorithm modulo ak. */
            for (j = 1; j <= i; j++)
            {
                if (p1 >= pt)
                {
                    r = 16 * r;
                    r = r - (int)(r / ak) * ak;
                    p1 = p1 - pt;
                }
                pt = 0.5 * pt;
                if (pt >= 1)
                {
                    r = r * r;
                    r = r - (int)(r / ak) * ak;
                }
            }

            return r;
        }
    }
}

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

1.361 Beiträge seit 2007
vor 10 Jahren

Schaut gut aus!
Du bist dran.

PS: Um Bit-Positionen zu korrigieren, gibt es Bit-Shift-Operationen, statt über binäre Strings zu gehen 😉

3.170 Beiträge seit 2006
vor 9 Jahren

Hallo zusammen,

ich möchte den Thread mal wieder aufwecken, und habe dazu folgende Aufgabe:

[b]Schreibt eine Methode, die aus einem in UTF-8 codierten Stream die Startposition des Textzeichens an einer an einer übergebenen Position ermittelt![/b]

Die Signatur der Methode sei
[csharp]long FindStartOfUTF8Sequence(Stream stream, long position, ref int sequenceLength)[/csharp]
[list]
[*]Der Rückgabewert der Methode ist Position in [TT]stream[/TT], an der das Textzeichen beginnt, das auch die Position [TT]position[/TT] enthält. 
[*]In [tt]sequenceLength[/tt] wird zusätzlich die Länge (in Bytes) des Textzeichens ausgegeben.
[*]Die Methode wirft eine Exception, wenn kein passendes Startbyte gefunden wird.
[/list] 

Zusätzlich gilt:*Ihr könnt davon ausgehen, dass der Stream Suchvorgänge (Seek) unterstützt. *Es ist nicht nötig, das Textzeichen zu lesen. *Der Parameter sequenceLength wird bewusst mit ref übergeben, damit Ihr die Methode leichter rekursiv schreiben könnt (aber nicht müsst). Beim Aufruf von aussen macht es nur Sinn, hier 0 zu übergeben. Einen anderen Fall braucht Ihr nicht zu berücksichtigen! *Ihr braucht keine Fehlerbehandlung außer der in der Aufgabenstellung genannten Exception zu machen.

Sinn und Zweck des ganzen:
Die Funktionalität bildet die Grundlage dafür, in UTF-8 codierten Texten rückwärts zu lesen.
Die Aufgabe kann aber auch dazu beitragen, die Struktur von UTF-8 (und generell die Thematik Encoding) besser kennen und verstehen zu lernen.

Viel Spaß, MarsStein

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

189 Beiträge seit 2014
vor 9 Jahren

Hallo MarsStein,

ich habe folgende Lösung gefunden:

class StreamConverter
    {
        public long FindStartOfUTF8Sequence(Stream stream, long position, ref int sequenceLength)
        {
            Byte actualByte = 0;
            
            BinaryReader reader = new BinaryReader(stream);
            stream.Position = position;
            actualByte = reader.ReadByte();

            if (actualByte >= 0 && actualByte < 128) // 1 Byte Header
	        {
		         sequenceLength = 1;
	        }
            else if (actualByte>= 128 && actualByte < 192) // Fogebyte Header
	        {
		         position = FindStartOfUTF8Sequence(stream, position-1, ref sequenceLength); // geht solange ein Zeichen weiter, bis Start-Header gefunden
	        }        
            else if (actualByte >= 194 && actualByte < 224) // 2 Byte Header
            {
                sequenceLength = testChar(stream, sequenceLength, reader, 2);
            }
            else if (actualByte >= 224 && actualByte < 240) // 3 Byte Header
            {
                    sequenceLength = testChar(stream, sequenceLength, reader, 3);
            }
            else if ( actualByte >= 240 && actualByte <= 244) // 4 Byte Header
            {
                sequenceLength = testChar(stream, sequenceLength, reader, 4);
            }
            else // Fange alle anderen Faelle ab: Nicht definierte Wertebereich-Luecke, Wertebereichende
            {
                throw new IOException("Nicht im Wertebereich!");
            }

            return position;
        }

        // Prueft, ob angegebene Anzahl an Folgebytes vorhanden
        private static int testChar(Stream stream, int sequenceLength, BinaryReader reader, int testRange)
        {
            for (int i = 1; i < testRange; i++)
            {
                byte actualByte = reader.ReadByte();
                if (actualByte < 128 || actualByte >= 192)
                {
                    throw new IOException("Fehler im Stream!");
                }
            }
            
            sequenceLength = testRange;
            return sequenceLength;
        }

Ich habe noch nicht komplett durchgetestet, aber es sollte eigentlich der Aufgabenstellung genügen.

Ezio

3.170 Beiträge seit 2006
vor 9 Jahren

Hallo Ezio,

Ich habe noch nicht komplett durchgetestet, aber es sollte eigentlich der Aufgabenstellung genügen.

Fast. Wenn ich es richtig sehe fängst Du noch den Fall nicht ab, dass zuvor schon mehr Folgebytes gelesen wurden, als das Startbyte zulässt (wenn Du z.B. schon 2 Folgebytes hattest, aber dann auf einen 2 Byte Header triffst -> das wäre dann auch kein passendes Startbyte)

Ansonsten passt alles.

Gruß, MarsStein

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

189 Beiträge seit 2014
vor 9 Jahren

So, jetzt hatte ich wieder Zeit mich mit dem Thema zu beschäftigen. Folgende Änderungen sind notwendig:

if (actualByte >= 0 && actualByte < 128) // 1 Byte Header
	        {
                sequenceLength = testChar(stream, sequenceLength, reader, 1);// Aenderung hier!
	        } 

-> um einen Test auf eine nachfolgenden Folgebyte-Header durchzuführen, der ja nicht erlaubt ist.


private static int testChar(Stream stream, int sequenceLength, BinaryReader reader, int testRange)
        {
            for (int i = 1; i <= testRange; i++) //Aenderung hier!
            {
                byte actualByte = reader.ReadByte();
                if ((i==testRange) ^ (actualByte < 128 || actualByte >= 192)) //Aenderung hier!
                {
                    throw new IOException("Fehler im Stream!");
                }
            }
            
            sequenceLength = testRange;
            return sequenceLength;
        }

Die erste Änderung bewirkt, dass das nächste Byte nach der laut Headerbyte abgeschlossenen Folge auch getestet wird.
Die zweite Änderung prüft, ob die Folge an der angegebenen Stelle abgeschlossen ist, also ob vor Folgeende immer Folgeheader kommen bzw. nach Folgeende ein Startheader kommt.

Ezio

49.485 Beiträge seit 2005
vor 9 Jahren

Hallo zusammen,

nachdem MarsStein seit seinem letzten Beitrag in diesem Thread gar nicht mehr im Forum war, weiß ich natürlich nicht, ob die Lösung von Ezio den Segen von MarsStein finden würde. Ich hatte MarsStein jedoch vorher eine eigene Lösung außer Konkurrenz per PM geschickt. An dieser Lösung hatte ihm eine Kleinigkeit gefehlt, nämlich, dass meine Methode keine Exception warf, wenn kein passendes Startbyte gefunden wurde. Das habe ich korrigiert und von dieser zweiten Lösung hat MarsStein bestätigt, dass sie passt.

Die Lösung habe ich rein mit Blick auf die Anforderungen der Aufgabe geschrieben. Sie nimmt also insbesondere keine weitergehenden Konsistenzprüfungen vor. Für den praktischen Einsatz sollte man sie also noch robuster machen.

Um die laufende Aufgabe zu einem Abschluss zu bringen, poste ich meine beiden Lösungen (die erst Variante erfüllt, wie gesagt wie Aufgabe nicht ganz, ist dafür aber etwas minimalistischer und liefert bei korrektem UTF-8 trotzdem die richtige Position) und gebe das Programmierspiel wieder frei, so dass Ezio oder jemand anderes eine neue Aufgabe stellen kann.

static long FindStartOfUTF8Sequence (Stream stream, long position, ref int sequenceLength)
{
   byte curr;
   do {
      stream.Position = position--;
      int result = stream.ReadByte ();
      if (result == -1) {
         throw new Exception ();
      }
      curr = (byte)result;
   } while ((curr & 0xC0) == 0x80);

   if ((curr & 0xC0) == 0xC0) {
      sequenceLength = 2;
      for (byte mask = 0x20; (curr & mask) != 0; mask >>= 1) {
         ++sequenceLength;
      }
   } else {
      sequenceLength = 1;
   }

   return position+1;
}

static long FindStartOfUTF8Sequence (Stream stream, long position, ref int sequenceLength)
{
   byte curr;
   int numBytesFound = 0;
   do {
      stream.Position = position--;
      int result = stream.ReadByte ();
      if (result == -1) {
         throw new Exception ();
      }
      curr = (byte)result;
      ++numBytesFound;
   } while ((curr & 0xC0) == 0x80);

   if ((curr & 0xC0) == 0xC0) {
      sequenceLength = 2;
      for (byte mask = 0x20; (curr & mask) != 0; mask >>= 1) {
         ++sequenceLength;
      }
   } else {
      sequenceLength = 1;
   }

   if (numBytesFound > sequenceLength) {
      throw new Exception ();
   }

   return position+1;
}

herbivore

Gelöschter Account
vor 9 Jahren
Enumrator richtiig substituiert

Okay herbivore hat die nächste Frage freibegeben und daher bin ich so frei:

EDIT: Ich habe den vorherigen Text entfernt, da dieser nicht genau das wiedergegeben hat worum es mir ging.

Die Aufgabe:

Es gilt eine Klasse zu erstellen die IEnumerable oder IEnumerable<T> implementiert, jedoch ist in der Implementierung der Schnittstelle die Verwendung von yield nicht erlaubt. Ferner, ist natürlich auch die Weiterleitung bestehender Enumeratoren nicht Teil der Lösung. Es geht bewusst darum den Enumerator von Hand zu erstellen. Optimal beantwortet wäre eine Lösung die beim ersten Aufruf des Enumerators nicht die gesamte Ergebnissmenge abfragt sondern immer nur die notwendige Teilmenge abruft. (Das ist aber mit einfachem Beispielcode allerdings schlecht darstellbar, wäre aber ein Bonus)

1.361 Beiträge seit 2007
vor 9 Jahren

Hi Sebastian,

kannst du noch ein paar Dinge erklären?

  • Worüber soll denn iteriert/enumeriert werden? Über ein Zahlen-Intervall, über eine List<T>, über einen gekapselten anderen IEnumerator?

  • Was genau meinst du mit der positiven Ergebnissmenge? Und wie kann ein Enumerator mehrfache Sachen zurückliefern?

beste Grüße
zommi

Gelöschter Account
vor 9 Jahren

@zoomi
Ich habe mein Posting soeben nochmal angepasst. Sofern ich es schon wieder versiebt habe, schick mir bitte ganz schnell eine Privatnachricht.

Edit[Nachtrag da ich gebeten wurde die Fragen nochmal detailierter zu beantworten]:

Worüber iteriert wird ist uns an der Stelle relativ egal. Es geht hier nicht so sehr um das worüber sondern um das wie und das warum. Ich würde das gerne näher beschreiben aber dann würde ich spoilern.

Ich gebe mal ne Quizfrage dazu. Von den folgenden 2 yield Fantasie-Codebeispielen ist nur ein Beispiel richtig. Beide Beispiele werden in einem Proof-Of-Concept problemlos durchlaufen aber ein Beispiel ruft unaufgefordert mehr Ergebnisse ab als es soll. (Einen solchen Code würde niemand mit IQ über Zimmertemperatur schreiben, ich will nur die Fallstricke verdeutlichen)

Beispiel 1:

public IEnumerator<string> GetEnumerator()
{
    List<string> list = new List<string>();
    list.Add("1"); list.Add("2"); list.Add("3");
    bool isMoveNextAvailable = true;
    int i = 0;
    while(isMoveNextAvailable )
    {
        string item = list[i];
        i++;
        isMoveNextAvailable = list.Count < i;
        yield return item;
    }
}

Beispiel 2:


public IEnumerator<string> GetEnumerator()
 {
    List<string> list = new List<string>();
    list.Add("1"); list.Add("2"); list.Add("3");
    bool isMoveNextAvailable = true;
    int i = 0;
    while(isMoveNextAvailable )
    {
        string item = list[i];
        i++;
        yield return item;
        isMoveNextAvailable = list.Count < i;
    }
}

Mir geht es einfach nur darum yield zu entzaubern 😃 Meine direkte Frage nach dem händischen Enumerator sollte ein Anstoss sein um die Magie von yield zusammen aufzulösen. Ich gebe zu ich hab mir das IL Ergebniss von yield nie wirklich angeschaut...

Hinweis von herbivore vor 9 Jahren

Um Enumerator-Aufgabe zu einem halbwegs sauberen Abschluss zu bringen, noch folgende Anmerkungen:

Ich gebe zu ich hab mir das IL Ergebniss von yield nie wirklich angeschaut...

Das hättest du mal tun sollen. 😃 Dann sieht man, dass beide Enumeratoren exakt genauso viele Ergebnisse abrufen. Keine der beiden Versionen ruft mehr Ergebnisse ab als sie soll, schon gar nicht unaufgefordert. Dadurch dass in der Bedingung mutmaßlich der falsche Vergleichsoperator verwende wird (list.Count < i statt list.Count > i) werden sogar zu wenige Ergebnisse abgerufen.

Der Unterschied zwischen beiden Varianten ist lediglich, zu welchem Zeitpunkt die Instanzvariable isMoveNextAvailable der compilergenerierten Enumerator-Klasse gesetzt wird. Sie wird aber auf jeden Fall gesetzt bevor sie (erneut) abgefragt wird. Daher sind auch die abgerufenen und die gelieferten Ergebnisse vollkommen gleich.

Steht die Bedingung hinter dem yield return und wird außerdem die Enumeration (z.B. durch ein break im foreach) vorzeitig abgebrochen, spart man sich gegenüber der anderen Variante einmal die Auswertung der Bedingung. Das ist performance-mäßig aber vollkommen irrelevant.

Hier noch eine - nach meinem Verständnis der eigentlichen Aufgabe - korrekte Lösung:


using System;
using System.Collections.Generic;

static class App
{
   public static void Main (String [] args)
   {
      foreach (String s in new A()) {
         Console.WriteLine (s);
      }
   }
}

public class A : IEnumerable<String>
{
   private List<String> _list = new List<String> () { "1", "2", "3" };

   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
   {
      return GetEnumerator();
   }

   public IEnumerator<String> GetEnumerator()
   {
      return new AEnumerator (_list);
   }
}

public class AEnumerator : IEnumerator<String>
{
   private List <String> _list;
   private int           _currentIndex;

   public AEnumerator (List <String> list)
   {
      _list = list;
      Reset ();
   }

   Object System.Collections.IEnumerator.Current
   {
      get {
         return _list;
      }
   }

   public String Current
   {
      get {
         return _list [_currentIndex];
      }
   }

   public bool MoveNext ()
   {
      if (_currentIndex < _list.Count) {
         ++_currentIndex;
      }
      return _currentIndex < _list.Count;
   }

   public void Reset ()
   {
      _currentIndex = -1;
   }

   public void Dispose ()
   {
      // nothing to do
   }
}

189 Beiträge seit 2014
vor 9 Jahren

Hallo zusammen,
um dem Thread mal wieder etwas Leben einzuhauchen, eine Aufgabe von mir.
Ich weiß, dass es diese Aufgabe anders herum schon gab (2. Aufgabe oder so) und hoffe, dass es diese Richtung noch nicht gab.


[B]Aufgabe:[/B]
Erstelle eine möglichst kurze Methode zur Umwandlung einer Zahl von der römischen Darstellung in einen Integer.

[B]Bedingungen:[/B]
[list]
[*] Signatur der Methode: [csharp]int RomToInt(char[] romanNumber)[/csharp]
[*] Maximal 47 Zeilen (Leerzeilen zur Formatierung werden nicht mitgezählt; 1 Statement pro Zeile; Klammern dürfen - wo möglich - weggelassen werden)
[*] nur einfache Datentypen verwenden, keine Listen etc.
[*] Als römisch Ziffern-Zeichen sind I, V, X, L, C, D, M zu erwarten. Andernfalls ist eine Exception zu werfen.
[*] [EDIT] Natürlich ist die Subtraktionsregel zu beachten ;-)
[/list]

Viel Spaß!

Ezio

1.361 Beiträge seit 2007
vor 9 Jahren

Let's try

static int RomToInt(char[] x) {
  int last=0, result=0;
  for (int i=x.Length-1; i>=0; i--) {
    if (!"IVXLCDM".Contains(x[i].ToString()))
      throw new System.ArgumentException();
    int current = (int)((x[i]\*(x[i]\*(x[i]\*(x[i]\*(x[i]\*(134149L*x[i]-61251763)+11624806957)-1173838830541)+66515437336342)-2005476756276328)+25136183219933184)/5896800);
    last = System.Math.Abs(-result + (result += current*(current<last?-1:+1)));
  }
  return result;
}

//Edit: hier noch eine etwas weniger obfuskierte Variante:

static int RomToInt(char[] x) {
  int last=0, result=0;
  for (int i=x.Length-1; i>=0; i--) {
    char c = x[i];
    if (!"IVXLCDM".Contains(c.ToString()))
      throw new System.ArgumentException();
    int current = (c=='M'?1000:c=='D'?500:c=='C'?100:c=='L'?50:c=='X'?10:c=='V'?5:1);
    result += current * (current<last ? -1 : +1);
    last = current;
  }
  return result;
}

beste Grüße
zommi

189 Beiträge seit 2014
vor 9 Jahren

Hallo zommi,

wow ist das eine kurze und clevere Lösung.
Bei mir hat's alle Tests bestanden.

Glückwunsch! Damit wärst du an der Reihe.

Ezio

3.170 Beiträge seit 2006
vor 7 Jahren

Hallo zusammen,

das Programmierspiel ist ja fast schon in Vergessenheit geraten... hier trotzdem nochmal eine kleine Aufgabe zum Grübeln.

Gegeben ist folgende statische Methode:
[csharp]
public static void Loop(int min, int max, Action<int> action)
{
    if (min > max)
        throw new ArgumentException("min must be lesser than or equal max");

    checked
    {
        for (int i = min /*hier Euer übriger Schleifenkopf*/)
            action(i);
    }
}
[/csharp]
Die Grenzen [tt]min[/tt] und [tt]max[/tt] sind beide inklusive.

Die Methode soll für jeden [tt]int[/tt] im übergebenen Bereich einmal die übergebene [tt]action[/tt] ausführen (wenn [tt]min == max[/tt] darf die Action also nur einmal ausgeführt werden).

[B]Füllt den Schleifenkopf der [tt]for[/tt]-Schleife so, dass alle Eingaben von [tt]int.MinValue[/tt] bis [tt]int.MaxValue[/tt] korrekt verarbeitet werden.

Es darf nur der Schleifenkopf (innerhalb der Klammern, wo der Kommentar steht) verändert werden!![/B]


Beachtet, dass die Schleife in einem checked-Block steht, Überläufe also nicht erlaubt sind.

Viele Spaß damit
MarsStein

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

49.485 Beiträge seit 2005
vor 7 Jahren

Hallo MarsStein, hallo zusammen,

das ist ja lustig. Ich hatte mir vor nicht mal einem Monat auch eine neue Aufgabe fürs Programmierspiel überlegt, aber leider noch nicht die Zeit gefunden, sie auszuformulieren. Insofern habe zumindest ich das Programmierspiel auch nicht vergessen.

Die einfachste und gleichzeitig am wenigsten fehleranfällige Lösung für das Problem des (möglichen) Überlaufs der Schleifenvariable, wäre long statt int dafür zu verwenden. Beim Aufruf der Action würde man diese (gefahrlos) auf int zurück-casten.

Wären die Parameter der Loop-Methode (und der Typ-Parameter des Action-Delegaten) longs, dann könnte man bei der Schleifenvariable nach dem eben beschrieben Prinzip einfach und sicher auf decimal ausweichen.

So wie deine Aufgabe formuliert ist - man also nur die Stelle mit dem Kommentar durch Code ersetzen und damit den Typ der Schleifenvariable nicht verändern darf -, muss man wohl eine zusätzliche (Schleifen-)Variable verwenden. Vermutlich ist das auch der Grund, warum du nach der Initialisierung der Schleifenvariable kein Semikolon gesetzt hat, sondern in der Lösung wohl ein Komma folgen wird.

Ich habe eine solche Lösung. Ich poste diese jedoch (noch) nicht, weil ich denke, dass die Aufgabe eine gute Übung für (etwas geübtere) Anfänger ist.

herbivore

PS (geschrieben, nachdem die Lösungen der Aufgabe gepostet wurden):
Wenn man beliebige Codeänderungen zulässt, gibt es weitere einfache und sichere Lösungen, um einen Überlauf der Schleifenvariable zu vermeiden, ohne dazu auf einen "größeren" Datentyp auszuweichen. Vorweggeschickt sei, dass durch die Abfrage am Anfang der Loop-Methode sichergestellt ist, mindestens ein Aufruf der Aktion erfolgt.

Daher kann man die for-Schleife um einen Durchlauf verkürzen (i < max statt i <= max) und anschließend die Aktion explizit für den Maximalwert aufrufen (bei dieser Lösung tritt ein Überlauf gar nicht erst ein):


for (int i = min; i < max; ++i) {
   action (i);
}
action (max);

Bei der folgenden Lösung kommt es zu einem Überlauf - weshalb man checked auch weglassen oder sogar in unchecked ändern muss -, welcher aber nach dieser Änderung keine negativen Auswirkungen hat:


int i = min;
do {
   action(i);
} while (i++ < max);

3.003 Beiträge seit 2006
vor 7 Jahren

@herbivore, funktioniert deine Methode für Loop(int.MaxValue, int.MaxValue, Console.WriteLine); ? Das ist momentan der Punkt, wo ich aufgegeben habe, Rest war relativ geradeaus...

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

49.485 Beiträge seit 2005
vor 7 Jahren

Hallo LaTino,

jetzt schon 😃

Oder anders gesagt: Den Fall hatte ich wirklich nicht bedacht, aber zumindest bei meinem Ansatz war es straightforward, diesen Fall noch einzubauen.

herbivore

2.298 Beiträge seit 2010
vor 7 Jahren

Nach langem überlegen habe ich auch eine Lösung, die m.E. nach funktioniert. - Bin mal gespannt, wie die erste gepostete Lösung im Vergleich zu meiner aussieht.

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

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

3.170 Beiträge seit 2006
vor 7 Jahren

Hallo zusammen,

@herbivore: Allen Deinen Aussagen zu der Aufgabe stimme ich vollumfänglich zu 😃

@all: herbivores Ansatz mit einer zweiten Schleifenvariable ist auch schon der wichtigste Tipp.
Hier noch einer:
Die Variable, gegen die die Bedingung geprüft wird, ist nicht unbedingt die, die inkrementiert wird. Bei meiner eigenen Lösung würde ich theoretisch bei der zweiten Variablen mit einem bool auskommen, das ist allerdings syntaktisch nicht möglich.

Gruß, MarsStein

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

179 Beiträge seit 2006
vor 7 Jahren

Hallo,

es gibt auch eine einfache Variante, die ohne zusätzliche Variable auskommt & bei den Grenzfällen funktioniert.

Mangels einer Idee zu einer Aufgabe werde ich diese aber erst nach der Lösung posten

Christian

3.003 Beiträge seit 2006
vor 7 Jahren

Pff. Also wenn hier keiner mit der Lösung rausrückt, mach ich das halt.


public static class LoopChallenge
{
    public static void Loop(int min, int max, Action<int> action)
    {
        if (min > max) throw new ArgumentException("min must be lesser than or equal max");

        checked
        {
            for (int i = min, j = 1; j > 0; j = i == int.MaxValue || ++i > max ? 0 : 1)
            {
                action(i);

            }
        }
    }
}

using NUnit.Framework;

namespace ClassLibrary1.Test
{
    [TestFixture]
    public class ChallengeTests
    {
        private int _firstValue;
        private int _lastValue;
        private int _count;
        private bool _testStarted;

        [SetUp]
        public void Setup()
        {
            _testStarted = (_firstValue = _lastValue = _count = 0) == 1;
        }

        [Test]
        [TestCase(int.MinValue, int.MinValue + 2, 3)]
        [TestCase(int.MaxValue - 2, int.MaxValue, 3)]
        [TestCase(int.MinValue, int.MinValue, 1)]
        [TestCase(int.MaxValue, int.MaxValue, 1)]
        [TestCase(-5,5,11)]
        public void ChallengeTest(int start, int end, int expectedCount)
        {
            LoopChallenge.Loop(start, end, PerformTest);

            Assert.AreEqual(start, _firstValue, "Beginn inkorrekt");
            Assert.AreEqual(end, _lastValue, "Ende inkorrekt");
            Assert.AreEqual(expectedCount, _count, "Anzahl inkorrekt");
        }

        private void PerformTest(int i)
        {
            if (!_testStarted) _firstValue = i;
            _testStarted = true;
            _lastValue = i;
            _count++;
        }
    }
}

Code-Teile zum Auf- und zuklappen im Forum wärn cool 😉.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

3.170 Beiträge seit 2006
vor 7 Jahren

Hallo,

LaTino hat's richtig gelöst und ist somit an der Reihe 😃

Hier noch mal meine eigene Lösung:

checked
{
    for (int i = min, end = 0; end == 0; end = (max == i) ? 1 : (++i - i))
        action(i);
}

Das Feature gibt es doch - hab es seinerzeit selbst hier für's Forum implementiert... Wenn Du Javascript erlaubst, gibt es neben dem Titel "C#-Code" so ein "-" zum zu- bzw. "+" zum wieder aufklappen 😃

Gruß, MarsStein

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

179 Beiträge seit 2006
vor 7 Jahren

Dann hier noch wie versprochen die Lösung ohne zusätzliche Variable:


public static void Loop(int min, int max, Action<int> action)
{
    if (min > max)
        throw new ArgumentException("min must be lesser than or equal max");

    checked
    {
        for (int i = min; i <= max; max = (i == int.MaxValue ? max-1 : max), i = (i == int.MaxValue ? i : i+1))
            action(i);
    }
}

Beim oberen Grenzfall wird einfach max dekrementiert anstatt i zu inkrementieren, damit kann die Bedingung
i ≤ max ausgewertet werden ohne Überläufe zu verursachen.

Noch kürzer ginge es so:
for (int i = min; i ≤ max; min=(i == int.MaxValue ? max-- : i++)), aber da braucht man doch wieder (in diesem Fall min) als dummy-Variable, da C# hier nur assignment, call, increment, decrement zulässt.

Christian

Edit:
Danke an Herbivore, der die letzte Variante noch optimiert hat:

for (int i = min; i <= max; i=(i == int.MaxValue ? max-- : i+1))  

oder vielleicht noch besser so, damit der Normalfall vorne steht:

for (int i = min; i <= max; i=(i < int.MaxValue ? i+1 : max--))  
  

Durch das Postdecrement von max wird im Fall i == int.MaxValue an i wieder int.MaxValue zugewiesen - i behält also bei der letzten Reinitialisierung wie gewünscht seinen (maximalen) Wert -, weil der Fall i == int.MaxValue nur eintreten kann, wenn max (ursprünglich) int.MaxValue ist.

Wenn du magst, kannst du deinen Beitrag editieren und diese Variante(n) der Vollständigkeit halber mit aufnehmen. Ich selbst werde keine Antwort schreiben, da ja schon die neue Aufgabe da ist.

Die folgende auch denkbare Variante würde ich dagegen nicht verwenden, da Inkrementoperator und Zuweisung hier doppeltgemoppelt wären:

for (int i = min; i <= max; i=(i < int.MaxValue ? ++i : max--))  
3.003 Beiträge seit 2006
vor 7 Jahren

@dechavue, schöne Idee, Hut ab 😃

Meine Aufgabe ist, glaube ich, etwas leichter. Ich mochte an dem Problem, dass mir schon beim drüber nachdenken immer weitere Optimierungen eingefallen sind - bin also gespannt, was euch noch so einfällt und wie effizient es wird 😉. Hab jetzt nicht alles durchgeschaut und hoffe, das gab's noch nicht.

**Aufgabe: Implementiere eine Methode mit der Signatur


public abstract IEnumerable<Point> GetIntegralPointsOn(PointF centre, float radius);

, die für einen beliebigen Kreis mit dem Mittelpunkt centre und dem Radius radius alle Punkte zurückgibt, die ganzzahlige Koordinaten besitzen und exakt auf dem Kreis liegen.**

Bedingungen:

  • falls delta-Vergleiche benötigt werden, darf delta maximal ein Tausendstel des Radius sein

_Bonuspunkte:

  • System.Math wird nicht verwendet
  • Rekursion (nur, weil's geht, vermutlich ist es langsamer 😉 )
  • keine Verwendung einer IList/ICollection (arbeiten mit yield return)
  • Implementierung für beliebig viele Dimensionen (Kreis, Kugel, Glome, Hyperspheres...)_

LaTino, (der geschludert hat und jetzt erstmal den Test dafür baut hust

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

49.485 Beiträge seit 2005
vor 7 Jahren

Hallo LaTino,

kann sein, dass du darauf hinaus willst, dass bei der Implementierung der gewünschten Methode der Bresenham-Algorithmus in der Variante für Kreise verwendet werden kann oder sogar soll?

Und kannst du noch motivieren, wo zu man die fertig implementierte Methode brauchen bzw. einsetzen kann? So wie ich es sehe wird für viele Parameter der Rückgabewert ein leeres IEnumerable<Point> sein.

herbivore

3.003 Beiträge seit 2006
vor 7 Jahren

Gerne. Also, um den Bresenham ging es gar nicht - ich hatte vor Jahren die Anforderung, für beliebige Polygone festzustellen, welche Punkte, die eine bestimmte Bedingung erfüllen, auf diesem (und optional in diesem) Polygon liegen. Das war im Rahmen einer Geofencing-Anwendung - die Aufgabe ist ein (sehr spezieller) Unterfall davon. Die eigentliche Aufgabe ist auch weniger das Implementieren eines fertigen Algorithmus, sondern die Suche nach dem passenden Algorithmus.
Eine weitere Anwendung ist mein ganz privates kleines Spielzeug, das im Spiel "Elite: Dangerous" u.a. ein 3D-Routing macht, für das dieser Algorithmus eine Hilfe ist. Bei > 100.000.000.000 Routenpunkten muss man gewisse Abschätzungen treffen, wenn man in endlicher Zeit eine akzeptable Lösung haben will 😉.


- die Anzahl der Punkte auf dem Kreis ist unendlich, die Anzahl der ganzzahligen "Gitterpunkte" eines Quadrats, das man über den Kreis liegt, ist dagegen endlich. (Schon das allein reicht aus für eine - allerdings nicht sehr effiziente - Lösung.)

- für eine beliebige Gerade in x-Richtung (x -n = 0), die zwischen dem Minimum-X und Maximum-X des Kreises liegt, existieren immer mindestens ein, meistens zwei Schnittpunkte mit dem Kreis. Mit Hilfe der Kreisgleichung und der Lösung für quadratische Gleichungen erhält man eine sehr einfache Gleichung für die zwei Schnittpunkte in Abhängigkeit von x.

(insb. für Leute, die ohne System.Math auskommen möchten:)
- Quadratwurzeln lassen sich mit dem Algorithmus von Heron in wenigen Schritten auf eine gewünschte Präzision genau abschätzen. Der lässt sich rekursiv implementieren.

Das ganze klingt vielleicht aufwändiger, als es ist. Meine Lösung hat ~20 loc und arbeitet mit O(n), wobei sich das noch verbessern ließe, dann aber schnell kompliziert wird.

Aber es geht auch mehr darum, eine Lösung für ein Problem zu finden, für das eben noch kein fertiger Algorithmus existiert.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

49.485 Beiträge seit 2005
vor 7 Jahren

Hallo LaTino,

danke, dadurch wird es schon etwas klarer.

Gehe ich recht in der Annahme, dass es sich bei den Werten für den Radius des Kreises in der Praxis um relativ große Werte geht, also sagen wir > 1000 oder sogar noch wesentlich größer?

Und dass man deshalb nicht einfach für alle ganzzahligen X-Werte ausprobiert, ob auch der zugehörige Y-Wert (bzw. die zugehörigen Y-Werte) ganzzahlig ist.

Es also letztlich darum geht, einen Algorithmus zu finden, der direkt - zumindest schnell - die ganzzahligen Werte-Paare findet, ohne wild rumzuprobieren?

herbivore

3.003 Beiträge seit 2006
vor 7 Jahren

Wenn wild herumprobieren zu einer vollständigen Lösung führt - wieso nicht 😉.

In der Praxis möchte man schon gern so ein, zwei Ergebnisse - die Wahrscheinlichkeit wird höher, je größer der Kreisradius ist, ja. Wobei meine Tests jetzt auch nur mit Radien zwischen 10 und 500 arbeiten, auch kriegt man so zwischen 0 und 50 Ergebnissen.

Es also letztlich darum geht, einen Algorithmus zu finden, der direkt - zumindest schnell - die ganzzahligen Werte-Paare findet, ohne wild rumzuprobieren?

Genau. Gibt nicht nur den einen Weg, und m.E. auch nicht den "besten". Für ganzzahlige Mittelpunkte zB könnte man einen völlig anderen, effizienteren Algorithmus implementieren (ich versuche selber gerade, ob dieser Weg auch für "krumme" Mittelpunkte praktikabel ist).

Ich fand eine Aufgabe a lá "implementiere eine Padé-Approximation in C#" zu langweilig. Kochen nach Rezept ist weniger unterhaltsam als ohne 😉.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

3.003 Beiträge seit 2006
vor 7 Jahren

War nicht so der Brüller, die Aufgabe 😉

Nach den Regeln kann die nächste Aufgabe frei gestellt werden.

LaTino

Der Vollständigkeit halber:
Nachfolgende Lösung hatte mir MarsStein geschickt - sie tut, hat aber noch einige Problemchen mit dem Runden. Nichts, was dramatisch wäre.



public static IEnumerable<Point> GetIntegralPointsOn(PointF centre, float radius)
        {
            float epsilon = radius / 1000;
            int currentX = (int)(centre.X + radius);
            while(currentX + epsilon >= centre.X - radius)
            {
                var deltaY = Math.Sqrt(Math.Pow(radius, 2) - Math.Pow(currentX - centre.X, 2));

                var y = centre.Y + deltaY;
                var yRounded = (int)Math.Round(y);
                if(Math.Abs(y - yRounded) < epsilon)
                    yield return new Point(currentX, yRounded);

                if((Math.Abs(deltaY) > epsilon))
                {
                    y = centre.Y - deltaY;
                    yRounded = (int)Math.Round(y);
                    if(Math.Abs(y - yRounded) < epsilon)
                        yield return new Point(currentX, yRounded);
                }

                --currentX;
            }
        }

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

2.298 Beiträge seit 2010
vor 7 Jahren

Hallo,

da lange Zeit keine Aufgabe mehr gestellt wurde habe ich eine, die ich heute vor langer Weile als Fingerübung selbst mal ausprogrammiert habe. Sie sollte eigentlich relativ einfach lösbar sein und ihr findet mit Sicherheit auch bessere Lösungen als ich.

Aufgabe: Implementiere eine Listen-Klasse, die das folgende Interface implementiert:


public interface IList<T> : IEnumerable<T>
{
    T this[int index] { get; }
    int Count { get; }
    void Add(T item);
    void Insert(int index, T item);
    void Clear();
    bool Contains(T item);
    IEnumerator<T> GetEnumerator();
    int IndexOf(T item);
    bool Remove(T item);    
    void RemoveAt(int index);   
}

Dabei sind folgende Regeln zu beachten:
Es dürfen weder Arrays noch Collections / Collectionähnliche / Dictionaries / Dictionary-ähnliche Klassen aus dem Framework verwendet werden.

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

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