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

Hallo,

so habe Fertig! 😁

Das ganze ist nichts anders als den Weg durch ein Labyrinth suchen.
Ich habe einen einfachen Backtracking-Algorithmus (Versuch und Irrtum) mit einem Stack als Ariadnefaden (um wieder herauszufeinden) dafür verwendet.
Er findet nicht den kürzesten Weg, sondern macht unnötig viele Umwege, aber der kürzeste Weg war ja nicht gefragt. 😉

Ich habe das ganze in eine eigen Klasse gesteckt damit es übersichtlicher ist, und habe auch nicht direkt auf dem Button Array gearbeitet, sonder mit einem eigenem, damit lässt sich leicher durch das Labyrinth laufen.

Hier die Methoden im Leveleditor:

private void canPacmanAccessToolStripMenuItem_Click(object sender, EventArgs e)
        {
            if (IsAccessable(startPoint[0], startPoint[1], cageField[0], cageField[1]))
                MessageBox.Show("YES! Pacman can access!");
            else
                MessageBox.Show("NO! Pacman can NOT access.");

        }
        
        private bool IsAccessable(int sourceX, int sourceY, int destX, int destY)
        {
            // Labyrinth aus dem Button Array erzugen
            Pathfinder.Field[,] labyrinth = new Pathfinder.Field[11,8];

            for (int i = 0; i < 11; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    Pathfinder.Field curField = new Pathfinder.Field();

                    int curPacmanField_X = i == 0 ? 1 : i * 2 + 1;
                    int curPacmanField_Y = j == 0 ? 1 : j * 2 + 1;

                    // Feld oben geschlossen?
                    if (pacmanField[curPacmanField_X, curPacmanField_Y - 1].BackColor == colorClosed)
                        curField.WallAbove = true;

                    // Feld rechts geschlossen?
                    if (pacmanField[curPacmanField_X + 1, curPacmanField_Y].BackColor == colorClosed)
                        curField.WallRight = true;

                    // Feld unten geschlossen?
                    if (pacmanField[curPacmanField_X, curPacmanField_Y + 1].BackColor == colorClosed)
                        curField.WallBelow = true;

                    // Feld links geschlossen?
                    if (pacmanField[curPacmanField_X - 1, curPacmanField_Y].BackColor == colorClosed)
                        curField.WallLeft = true;

                    labyrinth[i, j] = curField;
                }    
            }
            
            Pathfinder pathfinder = new Pathfinder(labyrinth, 11, 8);
          
            return pathfinder.CanReach(ToRealIndex(sourceX), ToRealIndex(sourceY), ToRealIndex(destX), ToRealIndex(destY));
        }

        private int ToRealIndex(int index)
        {
            return (int)(index / 2);
        }

Und meine Pathfinder-Klasse, die den eigentlichen Weg findet:

using System;
using System.Collections.Generic;

namespace pacman
{
    class Pathfinder
    {
        /// <summary>
        /// Ein Feld im Labyrinth
        /// </summary>
        public class Field
        {
            public bool WallAbove { get; set; }
            public bool WallRight { get; set; }
            public bool WallBelow { get; set; }
            public bool WallLeft { get; set; }

            public bool visited { get; set; }
        }

        /// <summary>
        /// Ein Punkt im Labyrinth, für den "Faden" benötigt
        /// </summary>
        class Point
        {
            public int X { get; set; }
            public int Y { get; set; }

            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }
        }

        /// <summary>
        /// Das Labyrinth als 2D-Array
        /// </summary>
        private Field[,] labyrinth;
        private int rows;
        private int colums;

        public Pathfinder(Field[,] labyrinth, int rows, int colums)
        {
            if (labyrinth.Length < 4 || labyrinth == null)
                throw new ArgumentException("No valid labyrinth");

            if (rows < 2 || colums < 2)
                throw new ArgumentException("Invalid row or colums count.");

            this.labyrinth = labyrinth;
            this.rows = rows - 1;
            this.colums = colums - 1;
        }

        private bool FieldAlreadyVisited(int x, int y)
        {
            // Oben raus, unten rein, rechts raus, links rein umd umgekehrt ;)
            if (x < 0)
                x = rows;
            
            if (x > rows)
                x = 0;

            if (y < 0)
                y = colums;

            if (y > colums)
                y = 0;

            return labyrinth[x, y].visited;
        }

        public bool CanReach(int startX, int startY, int targetX, int targetY)
        {
            if (startX > rows || startY > colums || startX < 0 || startY < 0)
                throw new ArgumentException("No valid start point.");

            if (targetX > rows || targetY > colums || targetX < 0 || targetY < 0)
                throw new ArgumentException("No valid target point.");

            if (startX == targetX && startY == targetY)
                throw new ArgumentException("Start and target are equal.");

            // Der Ariadnefaden um im Labyrinth wieder (aus Sackgasse) herauszufinden
            Stack<Point> ariadne = new Stack<Point>();

            // Startwerte setzten
            int curFieldX = startX;
            int curFieldY = startY;

            while (true)
            {
                // Ziel schon erreicht?
                if (curFieldX == targetX && curFieldY == targetY)
                    return true;

                // In das nächte Feld gehen, wenn keine Wand im Weg oder nicht schon besucht
                if (!labyrinth[curFieldX, curFieldY].WallAbove && !FieldAlreadyVisited(curFieldX, curFieldY - 1))
                {
                    if (curFieldY - 1 < 0)
                        curFieldY = colums;
                    else
                        curFieldY--;
                }
                else if (!labyrinth[curFieldX, curFieldY].WallRight && !FieldAlreadyVisited(curFieldX + 1, curFieldY)) 
                {
                    if (curFieldX + 1 > rows)
                        curFieldX = 0;
                    else
                        curFieldX++;
                }
                else if (!labyrinth[curFieldX, curFieldY].WallBelow && !FieldAlreadyVisited(curFieldX, curFieldY +1 )) 
                {
                    if (curFieldY + 1 > colums)
                        curFieldY = 0;
                    else
                        curFieldY++;
                }
                else if (!labyrinth[curFieldX, curFieldY].WallLeft && !FieldAlreadyVisited(curFieldX - 1, curFieldY))
                {                 
                    if (curFieldX - 1 < 0)
                        curFieldX = rows;
                    else
                        curFieldX--;
                }
                else // Sackgasse
                {
                    // Wieder am Startpunkt angelangt oder eingesperrt -> Kein Weg
                    if (ariadne.Count == 0)
                        return false;

                    // Ein Schritt zurück
                    Point prev = ariadne.Pop();
                    curFieldX = prev.X;
                    curFieldY = prev.Y;

                    continue;
                }

                // Aktuelles Feld als besucht markieren
                labyrinth[curFieldX, curFieldY].visited = true;
                
                // "Faden verlängern"
                ariadne.Push(new Point(curFieldX, curFieldY));
            }
        }

    }
}

Funktioniert 👍 -viel Spaß mit der nächsten Aufgabe 🙂

Da Scavenger eine Woche lang nichts gepostet hat, mach ich wieder was rein
(Falls es noch niemand gelöst hat kann er gerne jederzeit was andres reinstellen!)

Ich hätte gerne das 8-Damen Problem iterativ gelöst

Viel Spaß! 😉

//EDIT: Es muss nur eine Lösung gefunden werden nicht alle und die Ausgabe in eine Datei/auf die Konsole

Hier mein Vorschlag:

using System;
using System.Collections.Generic;

class AchtDamen
{
    const int brettGröße = 8;
    const int feldzahl = brettGröße * brettGröße;

    static void Main(string[] args)
    {
        int[] angriffszahlen = new int[brettGröße * brettGröße];
        int aktuellesFeld = 0;

        Stack<int> schritte = new Stack<int>();
        while (true)
        {
            if (aktuellesFeld < feldzahl)
            {
                if (angriffszahlen[aktuellesFeld] == 0)
                {
                    FürAlleErreichbarenFelder(aktuellesFeld % brettGröße, aktuellesFeld / brettGröße,
                        (x, y) =>
                        {
                            angriffszahlen[x + y * brettGröße]++;
                        });
                    schritte.Push(aktuellesFeld);
                    if (schritte.Count == 8)
                        break;

                    aktuellesFeld = 0;
                }
                else
                    aktuellesFeld++;
                continue;
            }
            if (schritte.Count > 0)
            {
                aktuellesFeld = schritte.Pop();
                FürAlleErreichbarenFelder(aktuellesFeld % brettGröße, aktuellesFeld / brettGröße,
                    (x, y) =>
                    {
                        angriffszahlen[x + y * brettGröße]--;
                    });
                aktuellesFeld++;
                continue;
            }
            Console.WriteLine("Keine Lösung gefunden!");
            Console.ReadLine();
            return;
        }
        char[] ausgabe = new char[feldzahl];
        for (int i = 0; i < ausgabe.Length; i++)
            ausgabe[i] = (((i + i / brettGröße) & 1) == 0) ? ' ' : 'ˆ';
        foreach (int schritt in schritte)
        {
            ausgabe[schritt] = 'Q';
        }

        Console.WriteLine("##########");
        for (int y = 0; y < brettGröße; y++)
        {
            Console.Write("#");
            for (int x = 0; x < brettGröße; x++)
                Console.Write(ausgabe[x + y * brettGröße]);
            Console.WriteLine("#");
        }
        Console.WriteLine("##########");
        Console.ReadLine();
    }

    private static void FürAlleErreichbarenFelder(int xStart, int yStart, Action<int, int> aktion)
    {
        aktion(xStart, yStart);
        int x, y;

        for (x = 0; x < brettGröße; x++)//quer
        {
            if (x != xStart)
                aktion(x, yStart);
        }

        for (y = 0; y < brettGröße; y++)//senkrecht
        {
            if (y != yStart)
                aktion(xStart, y);
        }

        x = xStart; y = yStart;//links oben
        while (x > 0 && y > 0)
            aktion(--x, --y);

        x = xStart; y = yStart;//rechts unten
        while (x < brettGröße - 1 && y < brettGröße - 1)
            aktion(++x, ++y);

        x = xStart; y = yStart;//links unten
        while (x > 0 && y < brettGröße - 1)
            aktion(--x, ++y);

        x = xStart; y = yStart;//rechts oben
        while (x < brettGröße - 1 && y > 0)
            aktion(++x, --y);
    }
}

Ich hab auch schon eine aufgabe der Kategorie

Kopf -> Tisch!

(Obwohl: Diesesmal ist es nur halb so lang^^)

Scheint zu funktionieren, falls jemand nen Fehler findet kann er sich gerne melden 😛
Viel Spaß mit der nächsten Aufgabe ^^

Im Anhang ist eine .net exe. Es soll eine Eingabe gefunden werden, die zu folgender Ausgabe führt: richtig

Wie letztes mal:
1.) Es ist nicht ganz so offensichtlich, wie es den Anschein hat.
2.) Es gibt eine Lösung!!!!

Wie man unschwer erkennen kann, ist es diesesmal sehr wenig Code, also auch weniger Platz um etwas zu verstecken. Wissen um die Eigenheiten der Clr und Msil sollte zur Lösung sehr nützlich sein.

Also: Fröhliches "wtf?!"

(Wenn jemand sich wundert, kann er gerne seinen Kommentar abgeben 😄)

Mir fehlt es eindeutig am Wissen.. 😃
Keine Ahnung inwiefern der GC eine Rolle spielt.
Ebenfalls frage ich mich ob der QWORD eine Rolle spielt ( den String den man daraus bekommt hilft mir auch nicht weiter :S )

Yeah! Ein echtes wtf!

Wie viel verwirrung ein par Zeilen Code stiften können. 8)

Lösung:

1337!

Wie ich darauf gekommen bin:

Das ulong Wert 15481342765760561 was damit zu tun hat und wird war klar (durch das Sequenzielle Layout der Klasse und dem Hack mit dem IL Keyword newslot in der ToString-Methode, überdeckt der Wert des Feldes, dessen Bytefolge dann als String ausgewertet wird, scheinbar das im Stack), also hab ich einfach mal die Bitfolge des Wertes in einen String konvertiert

string s = Encoding.Unicode.GetString(BitConverter.GetBytes(15481342765760561ul));

Das ist aber nicht die Lösung. Irgendwann hab ich dann den Speicherbereich des Prozesses ausgelesen und festgestellt das hinter dem 1337 noch ein "!" steht.
So wie ich das verstehe überschriebt der Bytewert des Feldes den Speicherbereich des Strings nicht ganz und das "!" des Strings (wtf?!) bleibt erhalten.

@Floste:
Ich glaub Langsam hab ich hab ich deine "IL-Masche" raus. 😉

P.S. Der GC hat damit nichts zu tun, ich hab mal spaßeshalber das "GC.KeepAlive" raus gepachet: Das Ergebnis bleibt das gleiche. Das "wtf?!.ToString()" bleibt natürlich.

1337!

😉

Aber chic, dass du einfach Methoden als fremde Instanzmethoden ausgeben kannst, war mir garnich klar... aber wenigstens peverify meckert rum.

Mit dieser Methode fummelst du dann quasi in fremden Objekte rum. Genauer gesagt im übergebenen String an der Stelle, wo bei dir @ulong steht. Und dort ist genau bei einem String (hinter der Länge) der eigentliche Content. Und so überschreibst du dann die ersten 4 Unicode Zeichen. Aus "wtf?!" wird damit "1337!"
Und dank String-Internalisierung wird auch bei späterem "wtf?!" der selbe, manipulierte String, verwendet.
Soweit meine Theorie, jedenfalls kommt richtig raus 😉
Warum ist das GC.KeepAlive nötig? Würde er sonst nicht internalisieren?

beste Grüße und danke für das schöne Rätsel. Ich denk schon über das nächste nach 😃
zommi

//Edit: Arggg... ein µ zu langsam 😉 Dann is Scavanger dran!

😁 Erstaunlich, dass ihr beiden jeweils um 0:24 bzw 25 antwortet, und beide richtig^^
Und Zommis Frage:

Warum ist das GC.KeepAlive nötig? Würde er sonst nicht internalisieren? wurde auchnoch beantwortet, bevor sie gestellt wurde 👍

Habt ihr euch wirklich nicht abgesproochen?

Ich hab mich wenigstens gut amüsiert heute moren, aber genug der String-Theorie, der nächste ist dran!

Nein, ich hatte die Lösung schon früher, wollte aber das spanische Pokalfinale nicht verpassen, dann hab ich's schnell noch danach gepostet, gerade noch rechtzeitig. 😉

O.K. nun wieder was algorithmisches:

Einen Programm zum Primzahltest, aber ich hätte gerne nicht das einundelfzigste Sieb des Eratosthenes sondern einen Probabilistischen Algorithmus

Viel Spass.

Hier mal mein Vorschlag (Miller-Rabin Methode):

Meine Klasse:

public class MillerRabin
    {

        int w; // Zeugen
        int zahl;
        string bin;
        int t;

        public MillerRabin(int zahl, int durchlaeufe)
        {
            if (zahl % 2 == 0 || durchlaeufe < 1 || zahl < 2)
            {
                throw new ArgumentException();
            }
            w = durchlaeufe;
            this.zahl = zahl;
        }

        //Startet den Algorithmus
        public bool Start()
        {
             if (zahl != 0)
             {
             return miller_rabin(zahl, w);
             }
             throw new ArgumentException();
        }

        //Hauptmethode
        private bool miller_rabin(int n, int s)
        {
            int r;
            bool prime = true;
            Random rand = new Random();
            for (w = 1; w < s + 1; w++)
            {
                r = rand.Next(2, n);
                if (witness(r, n))
                {
                    prime = false;
                    break;
                }
            }
            return prime;
        }

        // Konvertiert eine Zahl zu einem Binärstring
        private void IntToBinary(int B)
        {
            bin = Convert.ToString(B, 2);
        }


       private int modular_exponentiation(int a, int u, int n)
        {

            int c = 0;
            int d = 1;

            // Sei {b[0],b[1],...,b[k-1],b[k]} die binäre Darstellung von b
            if (w == 1) IntToBinary(u);
            // Da für alle Zeugen gleich, nur einmal berechnen

            for (int i = 0; i < bin.Length; i++)
            {

                c *= 2;
                d = (int)Math.Pow(d, 2) % n;

                if (bin[i] == '1')
                {
                    c += 1;
                    d = (d * a) % n;
                }
            }

            return d;
        }

        private bool witness(int a, int n)
        {
            int N_1 = n - 1;

            if (w == 1) while ((N_1 / (int)(Math.Pow(2, t)) % 2) == 0) t++;
            // Da für alle Zeugen gleich, nur einmal berechnen

            int u = N_1 / (int)Math.Pow(2, t);

            int x0;
            int x1 = modular_exponentiation(a, u, n); 

            for (int i = 1; i < t + 1; i++)
            {
                x0 = x1;
                x1 = (int)Math.Pow(x0, 2) % n;
                if (x1 == 1 && x0 != 1 && x0 != N_1)
                    return true;
            }
            return x1 != 1;
        }
    }

Und hier noch meine Main:

        static void Main(string[] args)
        {
            while (true)
            {
                Console.Write("Zahl eingeben (ungültige Eingabe für Abbruch!): ");
                string input = Console.ReadLine();
                int zahl;
                if (!int.TryParse(input, out zahl) || zahl < 1 || zahl % 2 == 0)
                {
                    Console.WriteLine("Ungültige Eingabe! Zahl muss größer 0 sein und ungerade sein!");
                    Console.ReadLine();
                    return;
                }
                if (zahl < 4)
                {
                    Console.WriteLine("Zahl ist prim!");
                }
                else
                {
                    MillerRabin mr = new MillerRabin(zahl, 20);

                    Console.WriteLine("Zahl ist{0} prim!", mr.Start() ? "" : " nicht");
                }
            }
        }

Hallo,

hmm, ich ringe mit mir... 🙁

Prinzipiell richtig, aber nur für Zahlen < 46337 für größere Zahlen schlägt dein Test fehl, größere werden immer als keine Primzahl erkannt.

Bitte nochmal nachbessern.

Danke 🙂

Ich denke das liegt daran, dass ab den darauf folgenden Zahlen ein Überlauft passiert. Zumindest wenn ich mir das im Debugger ansehe wird x1 negativ.

//EDIT: Hab das jetzt mit einer BigInt-Klasse probiert -> funktioniert einwandfrei

Im Anhang hab ich jetzt noch das Projekt mit BigInt angehängt - hoffe diesmal passt alles 😃

Schaut gut aus, du bist dran!

Das ist natürlich die Ideal-Lösung, auch wenn es hier natürlich eine Grenze gibt bei der ein Überlauf satt findet, das soll jetzt aber egal sei.
Mir hätte es im übrigen gereicht wenn die die Grenzen überprüft hättest. 😁

Hehe, ok - werd ich mir merken 😛

Okay, um wieder mal das Spiel hervorzuheben hätte ich gerne ein "GameOfLife" mti einer schönen grafischen Ausgabe
Hier noch zwei Links:
Game of Life - Deutsch
Conway's Game of Life - English

Falls Fragen auftreten stehe ich gerne zur Verfügung!
Viel Spass! 😃

So, hier ist meine Lösung. Ich habe allerdings keine neue Idee, d.h. jeder kann eine neue Aufgabe stellen(sofern mein Code als richtig befunden wird).

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

namespace ConwaysGameOfLife
{
  class Program
  {
    public bool Abort { get; set; }
    private bool[,] map;
    private int amount, sleeptime;
    private Thread t;

    static void Main(string[] args)
    {
      Program p = new Program();
      p.Start();
      Console.ReadLine();
      p.Abort = true;
    }

    public void Start()
    {
      do {
        Console.WriteLine("Bitte geben Sie die Zeit in ms zwischen den Generationen an.");
      } while (!Int32.TryParse(Console.ReadLine(), out sleeptime)
        || sleeptime < 1);
      do {
        Console.WriteLine("Bitte geben Sie die Anzahl der Felder ein.");
      } while (!Int32.TryParse(Console.ReadLine(), out amount)
        || amount < 1 || amount > 39);

      map = new bool[amount, amount];

      Console.WriteLine("Wollen Sie die Felder selbst befüllen? (J/N)");
      if (Console.ReadLine().Equals("J", StringComparison.OrdinalIgnoreCase))
      {
        ReadCells();
      }
      else
      {
        RandomizeCells();
      }

      t = new Thread(new ThreadStart(Run));
      t.Start();
    }
    
    private void Run()
    {
      while (!Abort)
      {
        PrintMap();
        try
        {
          Thread.Sleep(sleeptime);
        }
        catch (Exception) { }
        CalculateLife();
      }
    }

    private void ReadCells()
    {
      Console.WriteLine("Bitte geben Sie die lebenden Zellen im Format 'x,y' an.");
      string line;
      do
      {
        line = Console.ReadLine();
        string[] elements = line.Split(',');
        if (elements.GetLength(0) == 2)
        {
          int x, y;
          if (Int32.TryParse(elements[0], out y)
            && Int32.TryParse(elements[1], out x))
          {
            if (x >= 0 && x < amount
              && y >= 0 && y < amount)
            {
              map[x, y] = true;
            }
            else
            {
              Console.WriteLine("Bitte geben Sie eine Zahl im gültigen Bereich ein.");
            }
          }
          else
          {
            Console.WriteLine("Bitte geben Sie eine Zahl ein.");
          }
        }
        else
        {
          Console.WriteLine("Bitte geben Sie die lebenden Zellen im Format 'x,y' an.");
        }
      } while (line != "");
    }

    private void RandomizeCells()
    {
      Random random = new Random();
      for (int i = 0; i < amount; ++i)
      {
        for (int j = 0; j < amount; ++j)
        {
          map[i, j] = random.Next(2) == 0;
        }
      }
    }

    private void PrintMap()
    {
      Console.Clear();
      for (int i = 0; i < map.GetLength(0); i++)
      {
        Console.WriteLine(new string('-', amount * 2 + 1));
        for (int j = 0; j < map.GetLength(1); j++)
        {
          Console.Write('|');
          Console.Write(map[i,j] ? (char)2 : ' ');
        }
        Console.WriteLine('|');
      }
      Console.Write(new string('-', amount * 2 + 1));
    }

    private void CalculateLife()
    {
      bool[,] newGen = new bool[amount, amount];

      for (int i = 0; i < amount; ++i)
      {
        for (int j = 0; j < amount; ++j)
        {
          int neighbors = GetNeighbors(i, j);
          if (neighbors < 2)
          {
            newGen[i, j] = false;
          }
          if (neighbors == 3)
          {
            newGen[i, j] = true;
          }
          if (neighbors == 2 && map[i, j])
          {
            newGen[i, j] = true;
          }
          if (neighbors > 3)
          {
            newGen[i, j] = false;
          }
        }
      }

      map = newGen;
    }

    private int GetNeighbors(int x, int y)
    {
      int count = 0;

      if (x != 0)
      {
        if (y != 0)
        {
          count += map[x - 1, y - 1] ? 1 : 0;
        }
        if (y != amount - 1)
        {
          count += map[x - 1, y + 1] ? 1 : 0;
        }
        count += map[x - 1, y] ? 1 : 0;
      }
      if (x != amount - 1)
      {
        if (y != 0)
        {
          count += map[x + 1, y - 1] ? 1 : 0;
        }
        if (y != amount - 1)
        {
          count += map[x + 1, y + 1] ? 1 : 0;
        }
        count += map[x + 1, y] ? 1 : 0;
      }
      if (y != 0)
      {
        count += map[x, y - 1] ? 1 : 0;
      }
      if (y != amount - 1)
      {
        count += map[x, y + 1] ? 1 : 0;
      }

      return count;
    }
  }
}

edit: 12x12 deswegen, da man ansonsten scrollen muss, was imho recht nervig ist. Ich habe jetzt 39x39 genommen, da das die maximale Anzahl für die Breite ist.
Zufälliges Befüllen habe ich jetzt ebenfalls implementiert.
Die logischen Bedingungen für die Begrenzungen waren ebenfalls falsch.

Mach doch bitte noch eine Standardintialisierung hinzu , bzw. zufälliges Befüllen der Felder. Eventuell noch die Grenzen etwas erhöhen - 12x12 ist mir irgendwie zu klein 😛

Wegen deinem Platzproblem kannst du dich damit mal spielen:

Console.WindowHeight
Console.WindowWidth 

Das Prog funktioinert auf den ersten Blick - du bist dran 👍

Ich hab mir mal ne Aufgabe ausgedacht. Sie ist auf jeden Fall lösbar und das mit einer überschaubaren Zahl an Codezeilen. Ziel ist es, eigenen Code einzufügen, sodass Gelöst auf der Console ausgegeben wird.

using System;
using System.Runtime.InteropServices;

class Program
{
    static void Main(string[] args)
    {
        string ShouldBe = "This String";
        string IsAtStart= "R4nd0om data or somthing nobody cares about....";
        IntPtr buffer = Marshal.StringToHGlobalUni(IsAtStart);
        int hash = ShouldBe.GetHashCode();//Doppelte Prüfung hält besser

        WriteToBuffer(buffer, ShouldBe);

        string newString = Marshal.PtrToStringUni(buffer);
        Marshal.FreeHGlobal(buffer);

        if (newString == ShouldBe && newString.GetHashCode() == hash)
            Console.WriteLine("Gelöst");
        else
            Console.WriteLine("Nicht gelöst, in \"buffer\" steht: "+newString);
        Console.ReadLine();
    }

    //Hinter dem Ende dieses Kommentars darf der Code geändert werden.
    //Der nachfolgende vorgegebene Code ist als Hinweis gedacht und darf gelöscht/bearbeitet werden.
    //Folgende Ausdrücke dürfen dabei NICHT verwendet werden:
    //unsafe, Marshal, DllImport, extern, Reflection, GetType, typeof, Type, Program, Console, Main

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        //TODO
    }

        //TODO

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        //TODO
    }
}

Hi Floste,

du hast zwar wahrscheinlich an etwas komplett anderes gedacht 😉
Aber hier meine Lösung, die statt Marshal.Copy einfach Bitmap und SetPixel nutzt:

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        //TODO
    }

    //TODO

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        byte[] shouldBeBytes = System.Text.Encoding.Unicode.GetBytes(ShouldBe);
        int pixels = shouldBeBytes.Length / 4 + 1; // +1 for some trailing EndOfString-Zeroes
        int[] colorValues = new int[pixels];
        Buffer.BlockCopy(shouldBeBytes, 0, colorValues, 0, shouldBeBytes.Length);

        using (var b = new System.Drawing.Bitmap(pixels, 1, pixels * 4, System.Drawing.Imaging.PixelFormat.Format32bppArgb, buffer))
        {
            for (int i = 0; i < pixels; i++)
            {
                b.SetPixel(i, 0, System.Drawing.Color.FromArgb(colorValues[i]));
            }
        }
    }

beste Grüße
zommi

Hi,

vollständigkeitshalber noch das, woran Flotse wohl eher dachte:

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        [FieldOffset(0)]
        public IntPtrContainer A;

        [FieldOffset(0)]
        public CharacterContainer B;
    }

    
    [StructLayout(LayoutKind.Sequential)]
    class IntPtrContainer
    {
        public IntPtr IntPtr;
    }
    
    [StructLayout(LayoutKind.Sequential)]
    class CharacterContainer
    {
        public SingleCharacter SingleCharacter; 
    }
    
    class SingleCharacter
    {
        public char Char;
    }

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        for (int i = 0; i < ShouldBe.Length; i++)
        {
            WriteCharacter(buffer + i * sizeof(char), ShouldBe[i]);
        }
        WriteCharacter(buffer + ShouldBe.Length * sizeof(char), '\u0000');
    }

    private static void WriteCharacter(IntPtr buffer, char character)
    {
        SomeStruct s = new SomeStruct();
        s.A = new IntPtrContainer() {IntPtr = buffer - IntPtr.Size}; // skip SyncBlock of object
        s.B.SingleCharacter.Char = character;
    }

abermals beste Grüße
zommi

Das erste Snippet hat mich schmunzeln lassen. Aber gut, ich hatte solche Lösungen aber nicht ausgeschlossen^^
👍, Du bist dran...

Was mir grade noch auffällt: Da is nicht der Syncblock (der is ein IntPtr davor, sic), sondern die Typenangabe, aber das ist in diesem Falle egal^^

Ich habe wieder etwas ausgegraben:

Ein string-search Algorithmus á la Boyer-Moore: http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus

Da in dem Artikel ein Beispielcode in C existiert könnte man sich auch die Zeit nehmen und diesen zu überarbeiten - doch würde ich eine eigene Implementation bevorzugen

Hallo zusammen,

Da hier seit langem nichts mehr los ist, würde ich gerne eine Aufgabe stellen.

Erstelle einen Algorithmus welches den Ostersonntag eines Jahres ermittelt.

Wem das zu einfach war kann ja mal versuchen noch folgende Tage zu ermitteln:

KarFreitag
OsterMontag
ChristiHimmelfahrt
PfingstSonntag
PfingstMontag
Fronleichnam

Viel spaß beim lösen!

Ich werde hier die Lösung meiner Aufgabe zeigen [SCNR]da es für die meisten hier zu schwer zu sein scheint[/SCNR] (Bitte nicht ernst nehmen ^^).

Der Code ist nicht Optimal aber dafür einige Jahre alt...

public class Feiertage
    {

        public const int GruenDonnerstag = -3;
        public const int KarFreitag = -2;
        public const int OsterMontag = 1;
        public const int ChristiHimmelfahrt = 39;
        public const int PfingstSonntag = 49;
        public const int PfingstMontag = 50;
        public const int Fronleichnam = 60;

        public string GetOsterSonntag(int Jahr)
        {
            float Saekularzahl = 0;
            float Mondschaltung = 0;
            float Sonnenschaltung = 0;
            float Mondparameter = 0;
            float ErsterVollmond = 0;
            float KorrekturGroeße = 0;
            float Ostergrenze = 0;
            float ErsterSonntag = 0;
            float Entfernung = 0;
            float Sonntag = 0;
            DateTime Date;
                        
            Saekularzahl = Jahr / 100;
            Mondschaltung = 15 + (3 * Saekularzahl + 3) / 4 - (8 * Saekularzahl + 13) / 25;
            Sonnenschaltung = 2 - (3 * Saekularzahl + 3) / 4;
            Mondparameter = Jahr % 19;
            ErsterVollmond = (19 * Mondparameter + Mondschaltung) % 30;
            KorrekturGroeße = ErsterVollmond / 29 + (ErsterVollmond / 28 - ErsterVollmond / 29) * (Mondparameter / 11);
            Ostergrenze = 22 + ErsterVollmond - KorrekturGroeße;
            ErsterSonntag = 7 - (Jahr + Jahr / 4 + Sonnenschaltung) % 7;
            Entfernung = 7 - (Ostergrenze - ErsterSonntag) % 7;
            Sonntag = Ostergrenze + Entfernung;

            Sonntag = Convert.ToInt32(Math.Floor(Sonntag));

            if (Sonntag > 31)
            {
                Sonntag -= 31;
                Date = Convert.ToDateTime(Sonntag + ".04." + Jahr);
            }
            else
            {
                Date = Convert.ToDateTime(Sonntag + ".03." + Jahr);
            }

            return Date.ToShortDateString();
        }
        
        public Dictionary<string, string> GetBeweglicheFeiertage(DateTime OsterSonntag)
        { 
            DateTime[] BewegFeier = new DateTime[7];

            Dictionary<string, string> Dic = new Dictionary<string, string>();

            //Dic.Add("GruenDonnerstag", OsterSonntag.AddDays(GruenDonnerstag));
            Dic.Add("KarFreitag", OsterSonntag.AddDays(KarFreitag).ToShortDateString());
            Dic.Add("OsterMontag", OsterSonntag.AddDays(OsterMontag).ToShortDateString());
            Dic.Add("ChristiHimmelfahrt", OsterSonntag.AddDays(ChristiHimmelfahrt).ToShortDateString());
            Dic.Add("PfingstSonntag", OsterSonntag.AddDays(PfingstSonntag).ToShortDateString());
            Dic.Add("PfingstMontag", OsterSonntag.AddDays(PfingstMontag).ToShortDateString());
            Dic.Add("Fronleichnam", OsterSonntag.AddDays(Fronleichnam).ToShortDateString());

            return Dic;

        }
		
		public Dictionary<string, string> GetBeweglicheFeiertage(string OsterSonntag)
		{
			return GetBeweglicheFeiertage( Convert.ToDateTime(OsterSonntag) );
		}
		
	}

Für mehr Infos einfach hier reinschauen --> OsterFormel (Wobei man das nicht als Formel bezeichnen kann...)

Hallo Community,

nachdem die letzte Aufgabe ohne "Sieger" beantworte wurde, erlaube ich mir, eine neue Aufgabe zu stellen.

Schreibe eine Methode RemoveDuplicates, die ein String-Array als Parameter bekommt und eine List<String> zurückliefert, in der im Ergebnis alle doppelten/mehrfachen Zeilen entfernt sind. Es soll jeweils das erste Auftreten einer Zeile 1:1 übernommen und [I]alle[/I] späteren Wiederholungen der gleichen Zeile verworfen werden.

Damit es nicht zu einfach wird, soll die Methoden folgende Optionen verarbeiten können, die beliebig kombinierbar sind.

[csharp]
[Flags]
enum RemoveDuplicatesOptions
{
   IgnoreCase                  = 0x01,
   IgnoreLeadingTrailingSpace  = 0x02,
   IgnoreSpaceChange           = 0x04,
   IgnoreAllSpace              = 0x08,
   RemoveBlankLines            = 0x10,
   KeepBlankLines              = 0x20
}
[/csharp]

[B]IgnoreCase:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur in der Groß-Kleinschreibung unterscheiden. Beispiel:
[pre]
"Hallo World!"
"hAll0 worlD!"
"HALLO WORLD!"
[/pre]

[B]IgnoreLeadingTrailingSpace:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur darin unterscheiden, ob, welche oder wieviele Spaces am Anfang und am Ende vorhanden sind. Beispiel:
[pre]
"Hallo World!"
"Hallo World!   "
" Hallo World!"
"\t\tHallo World!\t"
[/pre]

[B]IgnoreSpaceChange:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur durch die Art oder Anzahl aufeinander folgender Spaces unterscheiden. Das gilt auch für Zeilenanfang und Ende. Egal, ob ein oder mehr Spaces. Beispiel:
[pre]
"Hallo World!"
"Hallo\tWorld!"
"Hallo    World!"
[/pre]

[B]IgnoreAllSpace:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur durch das Spacing unterscheiden. Egal, ob null, ein oder mehr Spaces. Beispiel:
[pre]
"HalloWorld!"
"Hallo World!"
"HalloW orld!"
" Hallo   World!\t\t"
[/pre]

[B]RemoveBlankLines[/B] bzw. [B]KeepBlankLines[/B] entfernen bzw. erhalten alle Leerzeilen. Werden beide gleichzeitig angegeben, wird nur RemoveBlankLines berücksichtigt. Was als Leerzeile angesehen wird, hängt von davon ab, ob mindestens eine von den Space-Optionen gesetzt ist (alle Zeilen, die gar keine Zeichen oder nur Spaces enthalten) oder keine davon gesetzt ist (alle Zeilen, die überhaupt keine Zeichen enthalten).

Die Signatur der Methode, sieht also so aus:

[csharp]public static List<String> RemoveDuplicates (String [] lines, RemoveDuplicatesOptions options)[/csharp]

Die Methode sollte auch bei einer Million Input Zeilen noch zügig arbeiten. Das wird vermutlich nur der Fall sein, wenn ihr es schafft, den Aufwand linear (also bei O(n)) zu halten.

Im PS gibts noch zwei Tipps. Tut euch den Gefallen und probiert es erstmal selber, ohne die Tipps zu lesen.

Viel Spaß und viel Erfolg!

herbivore

PS: Wie gesagt solltet ihr euch selbst den Gefallen tun und es erstmal selber versuchen, ohne gleich die Tipps zu lesen. Schluss jetzt. Stopp! Als Parametertyp kann man statt String [] besser IEnumerable<String> verwenden. Das wird hiermit ausdrücklich erlaubt und empfohlen. Es wird außerdem erlaubt, die Methode als Erweiterungsmethode von IEnumerable<String> zu definieren. Nochmal stopp! Zur Lösung der Aufgabe sind keine Indexzugriffe erforderlich. Nochmal stopp! Bei der Implementierung wird ein HashSet bzw. ein Dictionary gute Dienste leisten und kann bei richtiger Verwendung dafür sorgen, dass der Aufwand der Methode wie gewünscht im Schnitt linear ist.

Hier meine Lösung zu herbivores Aufgabe:

public class RemoveDublicatesComparer : IEqualityComparer<string>
{
    RemoveDublicates.RemoveDuplicatesOptions options = new RemoveDublicates.RemoveDuplicatesOptions();

    public RemoveDublicatesComparer(RemoveDublicates.RemoveDuplicatesOptions options)
    {
        this.options = options;
    }

    public bool Equals(string x, string y)
    {
        string tempx = "";
        string tempy = "";
        bool isMatch = false;

        isMatch = Regex.IsMatch(x, y);

        if(options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreCase) && !isMatch)
        {
            isMatch = Regex.IsMatch(x, y, RegexOptions.IgnoreCase);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace) && !isMatch)
        {
            tempx = Regex.Replace(x, "^[ \t]+|[ \t]+$", "");
            tempy = Regex.Replace(y, "^[ \t]+|[ \t]+$", "");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreSpaceChange) && !isMatch)
        {
            tempx = Regex.Replace(x, "[ \t]*", " ");
            tempy = Regex.Replace(y, "[ \t]*", " ");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreAllSpace) && !isMatch)
        {
            tempx = Regex.Replace(x, "[ \t]*", "");
            tempy = Regex.Replace(y, "[ \t]*", "");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        return isMatch;
    }

    public int GetHashCode(string obj)
    {
        throw new NotImplementedException();
    }
}

public class RemoveDublicates
{
    [Flags]
    public enum RemoveDuplicatesOptions
    {
        IgnoreCase = 0x01,
        IgnoreLeadingTrailingSpace = 0x02,
        IgnoreSpaceChange = 0x04,
        IgnoreAllSpace = 0x08,
        RemoveBlankLines = 0x10,
        KeepBlankLines = 0x20
    }

    public static List<String> RemoveDuplicates(String[] lines, RemoveDuplicatesOptions options)
    {
        List<String> resultStringList = new List<string>();
        RemoveDublicatesComparer comparer = new RemoveDublicatesComparer(options);

        foreach (string line in lines)
        {
            if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.RemoveBlankLines) && comparer.Equals("", line))
                continue;

            if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.KeepBlankLines) && comparer.Equals("", line))
            {
                resultStringList.Add(line);
                continue;
            }
            if (!resultStringList.Contains(line, comparer))
            {
                resultStringList.Add(line);
            }
        }

        return resultStringList;
    }
}

Sehr intressante Aufgabe. Habe viel dabei gelernt. Zerreisst mich bitte in der Luft, damit ich noch mehr lernen kann (Stichwort: Coding Horror)

Viele Grüße

PS: Das komplette Test-Programm gibts auf Anfrage

edit: Ok, Datei angehängt. 😁

Hallo Alf Ator,

die Richtung ist schon mal nicht schlecht. Gut gefällt mir, dass du durch den Comparer die Komplexität geschickt verteilt hast. Leider habe ich noch ein paar Fehler gefunden. Deshalb sehe ich die die Aufgabe noch nicht als gelöst an.

Bei Regex.IsMatch(x, y) wird x als Regex-Pattern interpretiert. Eine Eingabezeile muss aber kein gültiger Pattern sein. Dann knallt es. Aber selbst wenn die Zeile ein gültiger Pattern ist, sagt das matchen nicht, ob die Zeilen gleich sind. Wäre x z.B. ".*", dann würde das auf beliebige y passen. String.Compare wäre wohl eher, was du suchst.

Auch bei den Regex-Operationen danach, stimmt nicht alles. Regex.Replace(x, "[ \t]*", " ") geht zwar in die richtige Richtung, aber bei einem Pattern, der durch * auch die Länge null akzeptiert, muss man immer aufpassen, weil er an jeder Stelle passt, auch da, wo keine Leerzeichen sind. Dadurch wäre auch "Hallo World" und "HalloWorld" gleich.

Hast du es wirklich mal mit einer Million Zeilen probiert? Sowie ich das sehe, müsste das ziemlich lange dauern. Wenn es mit einer Million doch zügig geht, probier es mal mit 10 Millionen Zeilen. Ich vermute, dass wird nicht ca. 10 sondern ca. 100 Mal solange dauern. Das liegt daran, dass List.Contains eine O(n)-Operation ist, die jedes Mal innerhalb einer Schleife über n Elemente aufgerufen wird. Das ergibt am Ende O(n^2). Mit dem Tipp im PS kommt man an eine Contains-Operation, die einen Aufwand von nur O(1) hat. Damit erreicht man am Ende das gewünschte O(n).

Und leider rächt sich sogar der an sich elegante Comparer, weil er für jedes Zeilenpaar aufgerufen wird. Damit wird jede einzelne Zeile n-fach neu aufbereitet (also z.B. die Leerzeichen entfernt). Es wäre schöner, wenn jede Zeile nur einmal aufbereitet werden müsste (und das kann man tatsächlich realisieren). Den Comparer ersetzt mal also besser durch eine Zeilenaufbereitungsmethode.

Dass du fast überall Dublicates statt Duplicates geschrieben hast, wäre zu verschmerzen gewesen. 😃

Also auf zu einem weiteren oder neuen Versuch. Von dir oder von jemand anderem.

herbivore

So, mein zweiter Versuch:

public class RemoveDuplicates
{
    [Flags]
    public enum RemoveDuplicatesOptions
    {
        IgnoreCase = 0x01,
        IgnoreLeadingTrailingSpace = 0x02,
        IgnoreSpaceChange = 0x04,
        IgnoreAllSpace = 0x08,
        RemoveBlankLines = 0x10,
        KeepBlankLines = 0x20
    }

    public static List<String> Remove(List<String> inputStringList, RemoveDuplicatesOptions removeDuplicatesOptions)
    {
        HashSet<String> hash = new HashSet<string>();
        foreach (string line in inputStringList)
        {
            // evt. sollen Blanklines entfernt werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.RemoveBlankLines) && (ProcessString(line, removeDuplicatesOptions).Equals(""))) continue;

            // evt. sollen Blanklines erhalten werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.KeepBlankLines) && (ProcessString(line, removeDuplicatesOptions).Equals("")))
            {
                hash.Add(line);
                continue;
            }
            hash.Add(ProcessString(line, removeDuplicatesOptions));
        }
        return hash.ToList<string>();
    }

    public static string ProcessString(string x, RemoveDuplicatesOptions options)
    {
        string tempx = x;

        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreCase))
        {
            tempx = tempx.ToLower();
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace))
        {
            tempx = tempx.TrimStart(" \t".ToCharArray());
            tempx = tempx.TrimEnd(" \t".ToCharArray());
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreSpaceChange))
        {
            tempx = System.Text.RegularExpressions.Regex.Replace(tempx, "[ \t]+", " ");
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreAllSpace))
        {
            tempx = System.Text.RegularExpressions.Regex.Replace(tempx, "[ \t]+", "");
        }
        return tempx;
    }
}

Hallo Alf Ator,

du bist wieder näher dran. Und darüber, dass die Blankline-Abfragen in dem Fall, dass eine Leerzeile ein oder mehrere Spaces enthält und zusätzlich zu einem Blankline-Flag nur das Flag IgnoreSpaceChange gesetzt ist, nicht richtig funktionieren, weil ProcessString für diese Zeilen (in sich korrekt, aber für die Abfrage nunmal unpassend) " " und nicht "" liefert, hätte ich sogar hinweggesehen.

Doch was nützt KeepBlankLines, wenn du dabei HashSet.Add verwendest, welche doppelte Zeilen eben nicht doppelt hinzufügt? Hier bräuchtest du List.Add.

Die größten Auswirkungen hat aber der Fehler, dass du HashSet.ToList zurückgibst, denn darin sind ja (an sich korrekt, aber für die Rückgabe nunmal unpassend) die aufbereiteten Zeilen und nicht die Originalzeilen. Da wundert mich schon ein bisschen, dass das beim Testen nicht aufgefallen ist. Meiner Ansicht nach brauchst du eine Liste und ein Hashset.

Dass du eine Zeile immer noch bis zu dreimal aufbereitest, tut der Linearität zwar keinen Abbruch (konstanter Faktor). Schöner wärs aber, wenn du das vermeiden würdest. Und tempx kannst du dir eigentlich komplett sparen. Spätestens da sind wir aber endgültig bei den Stilfragen angekommen.

Im Sinne des Dazulernens sind solche Iterationen vermutlich nicht schlecht. Dadurch steigt allerdings die Gefahr, dass dir doch noch jemand zuvorkommt. Auf die Idee, dass man durch diese Aufgabe viel lernen kann, sind bestimmt schon andere gekommen. 😃

herbivore

Hallo herbivore, du lässt mir ja kein gutes Haar 😁

du bist wieder näher dran. Und darüber, dass die Blankline-Abfragen in dem Fall, dass eine Leerzeile ein oder mehrere Spaces enthält und zusätzlich zu einem Blankline-Flag nur das Flag IgnoreSpaceChange gesetzt ist, nicht richtig funktionieren, weil ProcessString für diese Zeilen (in sich korrekt, aber für die Abfrage nunmal unpassend) " " und nicht "" liefert, hätte ich sogar hinweggesehen.

Ist " " eine Blankline? Und wie schauts mit "\t" aus oder " \t \t"; Hier habe ich mich für den einfachsten Weg entschieden und definiert das nur "" = Blankline ist.

Doch was nützt KeepBlankLines, wenn du dabei HashSet.Add verwendest, welche doppelte Zeilen eben nicht doppelt hinzufügt? Hier bräuchtest du List.Add.

Da hast du mich eiskalt erwischt. Das war mir natürlich bewusst, aber ich hatte noch keine Lösung gefunden. Ich hätte eine Liste anlegen können und die Blanklines hinzufügen können und später dann das HashSet hinzufügen. Das würde aber die Reihenfolge durcheinander bringen. Oder ich füge jedesmal wenn ein String ins HashSet passt diesen String (oder dann das Original) in die List ein.

Die größten Auswirkungen hat aber der Fehler, dass du HashSet.ToList zurückgibst, denn darin sind ja (an sich korrekt, aber für die Rückgabe nunmal unpassend) die aufbereiteten Zeilen und nicht die Originalzeilen. Da wundert mich schon ein bisschen, dass das beim Testen nicht aufgefallen ist. Meiner Ansicht nach brauchst du eine Liste und ein Hashset.

Das ist mir natürlich aufgefallen. Die Frage ist halt, in welcher Form ein String zurückgegeben werden muss. In der Form, wie er als erstes aufgefunden wurde? Es gibt ja auch noch die Duplikate, die evt. andere Schreibweisen haben. Auch hier hab ich's mir einfach gemacht und angenommen, dass ein aufbereiteter String zurückgegeben werden kann.

Dass du eine Zeile immer noch bis zu dreimal aufbereitest, tut der Linearität zwar keinen Abbruch (konstanter Faktor). Schöner wärs aber, wenn du das vermeiden würdest. Und tempx kannst du dir eigentlich komplett sparen. Spätestens da sind wir aber endgültig bei den Stilfragen angekommen.

Find ich auch unschön so. X(

Im Sinne des Dazulernens sind solche Iterationen vermutlich nicht schlecht. Dadurch steigt allerdings die Gefahr, dass dir doch noch jemand zuvorkommt. Auf die Idee, dass man durch diese Aufgabe viel lernen kann, sind bestimmt schon andere gekommen. 🙂

Einen habe ich hier schon in der Streckbank..

Hallo Alf Ator,

Ist " " eine Blankline? Und wie schauts mit "\t" aus oder " \t \t";

Sind alles Blanklines, wenn und nur wenn mindestens eine der Space-Optionen gesetzt ist. Was unter welchen Umständen als Blankline betrachtet werden soll, steht in der Aufgabe. 😃

Hier habe ich mich für den einfachsten Weg entschieden und definiert das nur "" = Blankline ist.

Nö, da du vor dem Abfragen auf "" die Zeile aufbereitest (ProcessLine), wird auch bei dir (bis auf die von mir beschriebene Ausnahme vollkommen korrekt) viel mehr als nur "" als Blankline betrachtet.

Das würde aber die Reihenfolge durcheinander bringen.

Wie schon gesagt, brauchst du wohl sowohl eine Liste als auch ein HashSet. Die Liste um die zu übernehmenden Zeilen zu sammeln und das HashSet für die Prüfung auf doppelte/mehrfache Zeilen.

In der Form, wie er als erstes aufgefunden wurde?

Ja, und genau so steht es auch in der Aufgabe. 😃

Das ist mir natürlich aufgefallen.

Du solltest eine Lösung nur dann posten, wenn du selber davon ausgehst, dass sie korrekt ist.

herbivore

Du solltest eine Lösung nur dann posten, wenn du selber davon ausgehst, dass sie korrekt ist.

Sorry X(

public static List<String> Remove(List<String> inputStringList, RemoveDuplicatesOptions removeDuplicatesOptions)
{
    List<String> resultList = new List<string>();
    HashSet<String> hash = new HashSet<string>();
    string tmp = "";
    foreach (string line in inputStringList)
    {
        tmp = ProcessString(line, removeDuplicatesOptions);
        if (tmp.Equals("") || tmp.Equals(" "))
        {
            // evt. sollen Blanklines entfernt werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.RemoveBlankLines))
                continue;
            // evt. sollen Blanklines erhalten werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.KeepBlankLines))
            {
                resultList.Add(line);
                continue;
            }
        }
        if (hash.Add(tmp)) resultList.Add(line);
    }
    return resultList;
}

public static string ProcessString(string x, RemoveDuplicatesOptions options)
{
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreCase))
    {
        x = x.ToLower();
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace))
    {
        x = x.TrimStart(" \t".ToCharArray());
        x = x.TrimEnd(" \t".ToCharArray());
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreSpaceChange))
    {
        x = System.Text.RegularExpressions.Regex.Replace(x, "[ \t]+", " ");
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreAllSpace))
    {
        x = System.Text.RegularExpressions.Regex.Replace(x, "[ \t]+", "");
    }
    return x;
}

Ich hab jetzt versucht, alles bisherige zu beachten. Diesmal passt alles 8)

Hallo Alf Ator,

Diesmal passt alles

fast alles. 😃 Die Behandlung von BlankLines stimmt immer noch nicht ganz. Wenn z.B. keine Space-Option gesetzt ist, wird eine Zeile, die von vornherein nur ein einzelnes Blank enthält, fälschlicherweise trotzdem als Leerzeile erkannt. Statt " " in der Abfrage zu berücksichtigen, wäre es aus meiner Sicht eine korrekte Lösung, wenn du in ProcessString am Ende des Then-Teil der Abfrage auf IgnoreSpaceChange abfragst, ob das Ergebnis ein einzelnes Leerzeichen ist und wenn ja, x auf den leeren String setzt. Also

if (x == " ") {
   x = "";
}

Ich akzeptiere die Lösung trotzdem als korrekt. Du bist dran, die nächste Aufgabe zu stellen.

herbivore

fast alles. 🙂

Arrrrghhh 👅

Ich akzeptiere die Lösung trotzdem als korrekt. Du bist dran, die nächste Aufgabe zu stellen.

Puh! Das war aber auch ne knackige Aufgabe.

Eine Frage hab ich noch dazu:

Als Parametertyp kann man statt String [] besser IEnumerable<String> verwenden. Das wird hiermit ausdrücklich erlaubt und empfohlen. Es wird außerdem erlaubt, die Methode als Erweiterungsmethode von IEnumerable<String> zu definieren.

Was hattest du dabei denn im Hinterkopf? Eine eigene Liste implementieren, die die Funktion RemoveDuplicates anbietet?

So, ich werde mir mal Gedanken über eine neue Aufgabe machen. 🤔

Hallo Alf Ator,

Was hattest du dabei denn im Hinterkopf?

IEnumerable<String> ist die beste Wahl, weil die Methode damit am universellsten wird, egal in welcher konkreten Collection (Array, List, LinkedList, ...) die Eingabedaten vorliegen. Als Erweiterungsmethode von IEnumerable<String> kann man die Methode zudem (wiederum für beliebige Collections) sehr elegant aufrufen.

Der Grund, warum ich nicht gleich IEnumerable<String> vorgegeben habe, war, dass ich wollte, dass jeder möglichst von alleine darauf kommt, dass Indexzugriffe auf die Eingabedaten gar nicht erforderlich sind. Hätte ich statt String [], wo Indexzugriffe möglich sind, gleich IEnumerable<String> vorgegeben, wäre man gar nicht erst in die (trügerische) Versuchung gekommen, Indexzugriffe zu verwenden.

herbivore

Neue Aufgabe:

• zwei MovingObjects erstellen (Ship & Asteroid)
• ein 3. MovingObject erstellen, dass vom Schiff aus, den Asteroiden trifft
• der vorgegebene Code darf beliebig verändert werden
• Viel Spaß!

public class MovingObject
{
    public int x, y;    // Position
    public int r;       // Radius
    public int dx, dy;  // Bewegungsrichtung

    public MovingObject(int x, int y, int r, int dx, int dy)
    {
        this.x = x;
        this.y = y;
        this.r = r;
        this.dx = dx;
        this.dy = dy;
    }

    public static MovingObject GenerateRandomObject()
    {
        System.Threading.Thread.Sleep(156);
        Random rnd = new Random(DateTime.Now.Millisecond);
        return new MovingObject(rnd.Next(0, 10), rnd.Next(0, 10),
                                rnd.Next(1, 4), rnd.Next(0, 10),
                                rnd.Next(0, 10));
    }
}

Hallo,

ich verstehe deine Angabe leider noch nicht so ganz, aber eins weiß ich bestimmt:

Deklariere das Random Objekt irgendwo und erzeuge nur eine Instanz davon, da ansonsten ziemlich oft gleiche Werte als Ergebnis kommen 😉

Hallo Alf Ator,

zusätzlich zu Daniel B.s Hinweis: wenn der Code beliebig verändert werden kann dann ersetzt ich GenerateRandomObject durch etwas was bekannte Positionen für die Objekte zurückgibt und die Aufgabe ist schon gelöst.
Selbst wenn das ein wenig strenger wäre würde ich beim Random ein bekanntes Seed übergeben und somit kann ich die Positionen auch errechnen.

Ich denke du solltest die Aufgabe nachbessern.
Ich könnte für die Aufgabe aber auch den Code posten - dann wärs gelöst, aber das soll ja nicht das Ziel der Übung sein.

mfG Gü

Ich hab hier mal eine kleine Grafische darstellung gemacht, für die die es brauchen (so wie ich 😛) :

  public partial class DrawBoard : Form
    {
        public MovingObject ship;
        public MovingObject ast;
        public MovingObject shot;

        public DrawBoard(MovingObject a, MovingObject b) : this(a, b, null)
        {
        }

        public DrawBoard(MovingObject a, MovingObject b, MovingObject c)
        {
            InitializeComponent();
            ship = a;
            ast = b;
            shot = c;
            Timer t = new Timer();
            t.Interval = 500;
            t.Tick += new EventHandler(t_Tick);
            t.Start();
        }

        void t_Tick(object sender, EventArgs e)
        {
            if (ship != null)
            {
                ship.Move();
            }
            if (ast != null)
            {
                ast.Move();
            }
            if (shot != null)
            {
                shot.Move();
            }
            this.Invalidate();
            if (shot.x == ast.x && shot.y == ast.y)
            {
                MessageBox.Show("TREFFER!");
            }
        }

        protected override void OnPaint(PaintEventArgs e)
        {
            Graphics draw = e.Graphics;
            {//DrawGraph
                    Pen gray = new Pen(Brushes.Gray, 1F);
                    int max = 200; // constant     |
                    int abstand = 50; // constant  > change for graphstyle
                    for (int i = 0; i < max; i++)
                    {
                        draw.DrawLine(gray, new Point(i * abstand, 0), new Point(i * abstand, max * abstand));
                        draw.DrawLine(gray, new Point(0, i * abstand), new Point(max * abstand, i * abstand));
                        draw.DrawString((i * abstand).ToString() + "px", new Font(FontFamily.GenericSansSerif, 7F), Brushes.Black, new PointF(abstand * i, 0));
                        draw.DrawString((i * abstand).ToString() + "px", new Font(FontFamily.GenericSansSerif, 7F), Brushes.Black, new PointF(0, abstand * i));
                    }
            } //End DrawGraph
            //Draw the Objects
            if (ship != null)
            {
                Pen black = new Pen(Brushes.Black, 2F);
                draw.DrawEllipse(black, ship.x * 40, ship.y * 40, ship.r * 10, ship.r * 10);
            }
            if (ast != null)
            {
                Pen blue = new Pen(Brushes.Blue, 2F);
                draw.DrawEllipse(blue, ast.x * 40, ast.y * 40, ast.r * 10, ast.r * 10);
            }
            if (shot != null)
            {
                Pen green = new Pen(Brushes.Green, 1.5F);
                draw.DrawEllipse(green, shot.x * 40, shot.y * 40, shot.r * 10, shot.r * 10);
            }
            //Draw line for movement
            Pen red = new Pen(Brushes.Red, 1F);
            draw.DrawLine(red, new Point(ship.x * 40, ship.y * 40), new Point(ship.dx * 40, ship.dy * 40));
            draw.DrawLine(red, new Point(ast.x * 40,ast.y * 40), new Point(ast.dx * 40, ast.dy * 40));
            draw.DrawLine(red, new Point(shot.x * 40, shot.y * 40), new Point(shot.dx * 40, shot.dy * 40));
        }
        

        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.SuspendLayout();
            // 
            // DrawBoard
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(365, 262);
            this.Name = "DrawBoard";
            this.Text = "DrawBoard";
            this.ResumeLayout(false);

        }

        #endregion
    }

OK, hab das ganze denk ich jetzt mal verstanden, fehlt nur noch die Berechnung - aber das ist nur noch Kopfsache und wenn ich Zeit dafür finde ^^

[DrawBoard updated]

@Alf Ator
Ist es ausreichend wenn man sieht dass die Objekte kolidieren oder muss man auch eine Kollisionserkennung einbauen?

Ich lade jetzt einfach mal meine derzeitige Lösung hoch.
Vielleicht ist es ja schon ausreichend 😛 (hab das als .rar hochgeladen da ich es irgendwie unnütz finde 4 .cs Dateien zu posten) [Programm update]

Nachricht von Alf Ator vom 22.07.2011 15:03
RE: Programmier spiel

Da du jetzt grundsätzlich triffst, gilt die Aufgabe als gelöst, und du darfst dir eine neue Aufgabe ausdenken 🙂

Endlich 8)

OK-neue Aufgabe ...

ich hätte gerne eine Klasse die mit Binärzahlen rechnet (es sollen die 4 Grundrechnungsarten implementiert werden). (Einmal mit operator overloading und einmal als Methode [ebenfalls alle 4] um beispielsweise eine int-Zahl hinzu zu addieren [ binary.add(123) ])
Als Konstruktor kann man entweder die Binärzahl als string übergeben oder eine int-Zahl die dann in eine Binärzahl umgerechnet wird. Intern wird alles bitweise gerechnet!
Jedes Bit soll einzeln via Index gesetzt werden können bzw abgerufen werden (Die Zahl darf ebenfalls nicht als normale int-Zahl vorhanden sein sondern im Binär-Format).
Man soll ebenfalls die Zahl mit ToInt() als Integer Zahl bekommen können.
Viel Spaß!

Hallo zusammen,

hier meine Lösung der Aufgabe von Daniel:

Zunächst die Klasse zur Darstellung von Binärzahlen:
(Achtung: Die Klasse ist relativ lang geworden, daher habe ich sie zusätzlich als Anhang hinzugefügt; der eingefügte Code lässt sich ja zum Glück minimieren ^^)

using System;

namespace Binary
{
    public struct BinaryNumber
    {
        public const int BIT_QUANTITY = 8;

        public bool this[int i]
        {
            get { return Bits[i]; }
            set { Bits[i] = value; }
        }
        /// <summary>
        /// least significant bit
        /// </summary>
        public bool LSB
        {
            get { return Bits[0]; }
        }
        /// <summary>
        /// most significant bt
        /// </summary>
        public bool MSB
        {
            get { return Bits[Bits.Length - 1]; }
        }

        private bool[] bits;
        public bool[] Bits
        {
            get { return bits; }
            set { bits = value; }
        }

        #region constructors

        public BinaryNumber(int fromInt)
        {
            bits = new bool[BIT_QUANTITY];
            if (fromInt > pow2(BIT_QUANTITY-1)-1 || fromInt < -pow2(BIT_QUANTITY-1))
                throw new ArgumentOutOfRangeException();
            else
            {
                if (fromInt >= 0)
                    Bits = convertInt(fromInt);
                else if (fromInt < 0)
                {
                    Bits = convertInt(-fromInt);
                    Bits = this.Neg().Bits;
                }
            }

        }

        public BinaryNumber(string fromString)
        {
            bits = new bool[BIT_QUANTITY];
            if (fromString.Length != BIT_QUANTITY)
                throw new ArgumentException();
            for (int n = 0; n < BIT_QUANTITY; n++)
            {
                Bits[n] = (fromString[BIT_QUANTITY - 1 - n] == '1');
            }
        }

        #endregion

        private bool[] convertInt(int x)
        {
            bool[] buffer = new bool[BIT_QUANTITY];
            for (int i = 0; i < buffer.Length; i++)
            {
                int pot = (int)Math.Pow(2, i);
                buffer[i] = ((x & pot) == pot);
            }
            return buffer;
        }

        private int pow2(int e)
        {
            return (e == 0) ? 1 : (2 << e - 1);
        }

        #region calculations

        public BinaryNumber Neg()
        {
            BinaryNumber b = new BinaryNumber(0);
            for (int n = 0; n < Bits.Length; n++)
            {
                b.Bits[n] = !Bits[n];
            }
            return b.Add(1);
        }

        public BinaryNumber Abs()
        {
            return MSB ? this.Neg() : this;
        }

        public BinaryNumber Add(BinaryNumber b)
        {
            BinaryNumber newB = new BinaryNumber(0);
            bool carry = false;
            for (int i = 0; i < newB.Bits.Length; i++)
            {
                newB.Bits[i] = Bits[i] ^ b.Bits[i] ^ carry;
                carry = (Bits[i] & b.Bits[i]) | (Bits[i] & carry) | (b.Bits[i] & carry);
            }
            return newB;
        }

        public BinaryNumber Add(int i)
        {
            return this.Add(new BinaryNumber(i));
        }

        public BinaryNumber Subtract(int i)
        {
            return this.Subtract(new BinaryNumber(i));
        }

        public BinaryNumber Subtract(BinaryNumber b)
        {
            return this.Add(b.Neg());
        }

        public BinaryNumber Multiply(BinaryNumber b)
        {
            if (b == 1)
                return this;
            else
                return this + this.Multiply(b - 1);
        }

        public BinaryNumber Multiply(int b)
        {
            return this.Multiply(new BinaryNumber(b));
        }

        public BinaryNumber Divide(BinaryNumber b)
        {
            if (b == 0)
                throw new DivideByZeroException();
            if (!MSB && !b.MSB)
            {
                // positive number
                if (this < b)
                    return new BinaryNumber(0);
                else
                    return (this - b).Divide(b) + 1;
            }
            else if (MSB && b.MSB)
            {
                return this.Abs().Divide(b.Abs());
            }
            else
            {
                // negative number
                return this.Abs().Divide(b.Abs()).Neg();
            }
        }

        public BinaryNumber Divide(int i)
        {
            if (this < new BinaryNumber(i))
                return new BinaryNumber(0);
            else
                return new BinaryNumber(1) + (this - new BinaryNumber(i)).Divide(i);
        }
        
        #endregion

        #region operator overloads

        public static BinaryNumber operator +(BinaryNumber a, BinaryNumber b)
        {
            return a.Add(b);
        }

        public static BinaryNumber operator +(BinaryNumber a, int b)
        {
            return a.Add(b);
        }

        public static BinaryNumber operator -(BinaryNumber a, BinaryNumber b)
        {
            return a.Subtract(b);
        }

        public static BinaryNumber operator -(BinaryNumber a, int b)
        {
            return a.Subtract(b);
        }

        public static BinaryNumber operator *(BinaryNumber a, int b)
        {
            return a.Multiply(b);
        }

        public static BinaryNumber operator *(BinaryNumber a, BinaryNumber b)
        {
            return a.Multiply(b);
        }

        public static BinaryNumber operator /(BinaryNumber a, BinaryNumber b)
        {
            return a.Divide(b);
        }

        public static BinaryNumber operator /(BinaryNumber a, int b)
        {
            return a.Divide(new BinaryNumber(b));
        }

        public static bool operator ==(BinaryNumber a, BinaryNumber b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(BinaryNumber a, BinaryNumber b)
        {
            return !a.Equals(b);
        }

        public static bool operator >(BinaryNumber a, BinaryNumber b)
        {
            return a.isBigger(b);
        }

        public static bool operator <(BinaryNumber a, BinaryNumber b)
        {
            return b.isBigger(a);
        }

        public static bool operator ==(BinaryNumber a, int b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(BinaryNumber a, int b)
        {
            return !a.Equals(b);
        }

        public static bool operator >(BinaryNumber a, int b)
        {
            return a.isBigger(b);
        }

        public static bool operator <(BinaryNumber a, int b)
        {
            return !a.isBigger(b) && (a != b);
        }

        #endregion

        #region converting methods
        public override string ToString()
        {
            string buffer = "";
            for (int n = Bits.Length-1; n >= 0; n--)
            {
                buffer += Bits[n] ? "1" : "0";
            }
            return buffer;
        }

        public int ToInt()
        {
            int i = 0;
            bool[] bits = null;
            int sign = 0;
            if (Bits[Bits.Length - 1])
            {
                sign = -1;
                bits = this.Neg().Bits;
            }
            else
            {
                sign = 1;
                bits = this.Bits;
            }
            for (int n = 0; n < bits.Length; n++)
            {
                if (bits[n])
                    i += pow2(n);
            }
            return i*sign;
        }
        #endregion

        public override bool Equals(object obj)
        {
            if (obj is BinaryNumber)
            {
                BinaryNumber comp = (BinaryNumber)obj;
                for (int n = 0; n < Bits.Length; n++)
                {
                    if (Bits[n] != comp.Bits[n])
                    {
                        return false;
                    }
                }
                return true;
            }
            else if (obj is int)
            {
                return Equals(new BinaryNumber((int)obj));
            }
            else
            {
                return false;
            }
        }

        public bool isBigger(BinaryNumber b)
        {
            for (int n = Bits.Length - 1; n >= 0; n--)
            {
                if (Bits[n] == b.Bits[n])
                {
                    continue;
                }
                else if (Bits[n] && !b.Bits[n])
                {
                    return true;
                }
                else if (!Bits[n] && b.Bits[n])
                {
                    return false;
                }
            }
            // numbers are equal
            return false;
        }

        public bool isBigger(int b)
        {
            return isBigger(new BinaryNumber(b));
        }
    }
}

Zum Testen der drei Grundrechenarten hier ein kleines Hauptprogramm für die Konsole:

using System;

namespace Binary
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                // input
                Console.Write("Zahl 1: ");
                int a = Convert.ToInt32(Console.ReadLine());
                Console.Write("Zahl 2: ");
                int b = Convert.ToInt32(Console.ReadLine());

                // converting to binary numbers
                BinaryNumber bin1 = new BinaryNumber(a);
                BinaryNumber bin2 = new BinaryNumber(b);

                // output
                Console.WriteLine("Summe:\t\t{0}", (bin1 + bin2).ToInt());
                Console.WriteLine("Differenz:\t{0}", (bin1 - bin2).ToInt());
                Console.WriteLine("Produkt:\t{0}", (bin1 * bin2).ToInt());
                Console.WriteLine("Quotient:\t{0}", (bin1 / bin2).ToInt());

                Console.ReadLine();
                Console.Clear();
            }
        }
    }
}

Kleine Beschreibung:

Die Binärzahlen werden durch ein Array aus mehreren bools dargestellt. Mit der Konstanten BIT_QUANTITY wird festgelegt, aus wie vielen Bits die Binärzahl besteht. WICHTIG: Ich bin grundsätzlich von einer Zahl MIT Vorzeichen ausgegangen, daher führen z. B. 4 Bits zu einem Zahlenbereich von 1000 (- 8) bis 0111 (7).

Weitere Anmerkung: Die pow2-Methode, an einigen Stellen zur Berechnung von 2er-Potenzen genutzt, habe ich anstelle der Math.Pow-Funktion verwendet:

        private int pow2(int e)
        {
            return (e == 0) ? 1 : (2 << e - 1);
        }

ist gleichbedeutend mit

Math.Pow(2, e)

Habe das so implementiert da in der Aufgabenstellung stand man solle intern alles bitweise ausrechnen, bei höheren Werten für die BIT_QUANTITY führt das allerdings zu StackOverflowExceptions; im Zweifelsfall also ggf. durch die Pow-Funktion aus der Math-Klasse ersetzen 😉

Funktioniert - du bist drann 👍