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

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

Mitglieder
» Liste / Suche
» Wer ist online?

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

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

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

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hier noch ein Screenshot von der GUI:
Attachments
private Nachricht | Beiträge des Benutzers
Mao
myCSharp.de - Member



Dabei seit:
Beiträge: 14

beantworten | zitieren | melden

Hallo stes, hallo Forum,

ich wollte mal wieder was in C# machen und stolperte über diesen Thread (in dem schon echt interessante Aufgaben waren). Im Anhang ist meine Lösung für stes' Aufgabe. Auf das Kopieren des Quellcodes verzichte ich aufgrund der Länge (~180 Zeilen oder so) mal, er findet sich jedoch in der ZIP-Datei.

Sollte stes mit der Lösung einverstanden sein, kann gern jemand anderes die nächste Aufgabe stellen. =)


using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Reflection;
using System.IO;

namespace MouseBall {
    public partial class Form1 : Form {
        public const float BALL_RADIUS = 20;
        public const float KICK_POWER = -15;
        public const float GRAVITY = 0.7f;
        public const float MAX_SPEED = 15;

        // add/change fields as you please!
        private Image _ballImg;
        private PointF _ballPos;
        private PointF _speedVector;
        private int _score;
        private int _highscore;
        private bool _playing;
        private bool _newHighscore;

        public int Score {
            get {
                return _score;
            }
            private set {
                _score = value;
                // ggf. neue Highscore setzen
                if (value > Highscore) {
                    Highscore = value;
                }
         
            }
        }

        public int Highscore {
            get {
                return _highscore;
            }
            private set {
                _highscore = value;
                _newHighscore = true;
            }
        }

        public bool Playing {
            get {
                return _playing;
            }
            private set {
                _playing = value;

                if (value) {
                    _lblStartGame.Hide();
                    _timer.Start();
                }
                else {
                    _timer.Stop();
                    if (_newHighscore) {
                        ShowNewHighscore();
                    }
                    initBall();
                    _lblStartGame.Show();
                    Score = 0;
                    _speedVector = new PointF(0.0f, 0.0f);
                    _newHighscore = false;
                }
            }
        }

        public Form1() {
            InitializeComponent();
            _pnlGame.Paint += new PaintEventHandler(_pnlGame_Paint);
            _pnlGame.MouseClick += new MouseEventHandler(_pnlGame_MouseClick);

            this.initBall();

            // load and resize ball icon
            string s = Path.Combine(
                Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location),
                "soccer-ball.ico");
            _ballImg = new Bitmap(new Icon(s).ToBitmap());
            _ballImg = new Bitmap(_ballImg, new Size((int)BALL_RADIUS * 2, (int)BALL_RADIUS * 2));
        }

        private void initBall() {
            _ballPos = new PointF(_pnlGame.Width / 2, _pnlGame.Height - BALL_RADIUS);
            _speedVector = new PointF(0.0f, 0.0f);
        }

        private void _pnlGame_Paint(object sender, PaintEventArgs e) {
            Graphics g = e.Graphics;
            // paint middle line
            g.FillRectangle(
                Brushes.White,
                0,
                _pnlGame.Height / 2 - 2,
                _pnlGame.Width,
                4);
            // paint the ball
            g.DrawImage(_ballImg, _ballPos.X - BALL_RADIUS,
                _ballPos.Y - BALL_RADIUS);
        }

        void _pnlGame_MouseClick(object sender, MouseEventArgs e) {
            // Spiel ggf. starten
            if (!Playing) {
                Playing = true;
            }

            // Ball ist nur unterhalb der Mittellinie spielbar
            int centerLine = _pnlGame.Height / 2;
            if (e.Y ≥ centerLine) {
                float dX = e.X - _ballPos.X;
                float dY = e.Y - _ballPos.Y;
                float distSqr = dX * dX + dY * dY;
                // Ball angeklickt?
                if (distSqr ≤ BALL_RADIUS * BALL_RADIUS) {
                    _speedVector.Y = KICK_POWER;
                    _speedVector.X = 1.5f * KICK_POWER * dX / BALL_RADIUS;
                }
            }
        }

        private void _timer_Tick(object sender, EventArgs e) {
            _ballPos.Y += _speedVector.Y;
            _ballPos.X += _speedVector.X;
            // Fallgeschwindigkeit begrenzen (lässt sich sonst zu schwer treffen)
            _speedVector.Y = Math.Min(_speedVector.Y + GRAVITY, MAX_SPEED);

            CheckGameOver();
            DoCollisionChecks();
            DoScoring();

            _lblScore.Text = Score.ToString();
            _lblHighscore.Text = Highscore.ToString();
            _pnlGame.Invalidate();
        }

        private void DoScoring() {
            // Hat Ball Mittellinie gerade eben nach oben gekreuzt?
            int centerLine = _pnlGame.Height / 2;
            if ((_ballPos.Y < centerLine) && (_ballPos.Y - _speedVector.Y > centerLine)) {
                Score += 1;
            }
        }

        private void CheckGameOver() {
            // Ball unten? -> Spiel vorbei
            // Ball soll erst ganz verschwunden sein, ist so einfacher spielbar
            if (_ballPos.Y ≥ _pnlGame.Height + BALL_RADIUS) {
                Playing = false;
            }
        }

        private void DoCollisionChecks() {
            // Kollision mit oberem Spielfeldrand?
            if (_ballPos.Y ≤ BALL_RADIUS) {
                _ballPos.Y = BALL_RADIUS;
                _speedVector.Y *= -1;
            }

            // Linker Spielfeldrand?
            if (_ballPos.X ≤ BALL_RADIUS) {
                _ballPos.X = BALL_RADIUS;
                _speedVector.X *= -1;
            }

            // Rechter Spielfeldrand?
            if (_ballPos.X ≥ _pnlGame.Width - BALL_RADIUS) {
                _ballPos.X = _pnlGame.Width - BALL_RADIUS;
                _speedVector.X *= -1;
            }
        }

        private void ShowNewHighscore() {
            MessageBox.Show("Gratulation, das ist ein neuer Highscore!", "Gratulation",
                            MessageBoxButtons.OK, MessageBoxIcon.Information);
        }
    }
}


Viele Grüße!
Attachments

Moderationshinweis von michlG (10.11.2011 - 21:01:31):

So viel ist der code nun auch wieder nicht. ich hab den mal reinkopiert dann braucht nicht jeder extra den download machen.
Zusätzlich lass ich mal den Anhang dran

private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hallo Mao,

habe mir die Lösung angeschaut, funktioniert alles soweit ;)

Beim Öffnen in Visual Studio musste ich allerdings noch das Icon in den Debug-Ordner kopieren, als Anmerkung für alle, die sich das Projekt auch noch ansehen wollen..
Weiterhin sollte man den jetzt doch noch nachträglich eingefügten Sourcecode nicht in mein ursprüngliches Projekt reinkopieren, da in Mao's Projekt noch ein zusätzliches Label zum Einsatz kommt, kurz: Einfach das angehängte Projekt downloaden ^^

Ansonsten kann Mao, oder
Zitat von Mao
jemand anderes
die nächste Aufgabe stellen.

Gruß stes
private Nachricht | Beiträge des Benutzers
thetruedon
myCSharp.de - Member



Dabei seit:
Beiträge: 112

Highlighter

beantworten | zitieren | melden

Hallo
weil sich ja jetzt nichts getan hat will ich eine neue Aufgabe stellen.

Zu schreiben ist eine Funktion, die in einer RichTextBox beim Hineinschreiben Syntax-Highlighting aktiviert.
Es sollten wenigstens folgende Wörter rot hervorgehoben werden:

if, else, while, for, int, bool, string, void, var, 42

Dazu soll darauf geachtet werden, dass die Funktion nicht länger als 15-20 Zeilen sein sollte.
Viel Spaß beim proggen =)

Der Don
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von thetruedon am .
Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Also ich finde das so Highlighting nicht mal eben so in 20 Zeilen gemacht werden kann.


[System.Runtime.InteropServices.DllImport("user32.dll")]
private extern static IntPtr SendMessage(IntPtr hWnd, int msg, IntPtr wp, IntPtr lp);

private void HighlightText()
{
    SendMessage(richTextBox1.Handle, 0xb, (IntPtr)0, IntPtr.Zero);
    int selectionStart = richTextBox1.SelectionStart;
    int selectionLength = richTextBox1.SelectionLength;
    richTextBox1.SelectAll();
    richTextBox1.SelectionColor = Color.Black;

    foreach (var keyword in Keywords)
    {
        foreach (int position in GetHighlightPositions(richTextBox1.Text, keyword.Key))
        {
            richTextBox1.Select(position, keyword.Key.Length);
            richTextBox1.SelectionColor = keyword.Value;
            richTextBox1.Select(position + keyword.Key.Length, 1);
            richTextBox1.SelectionColor = Color.Black;
        }
    }
    richTextBox1.Select(selectionStart, selectionLength);
    SendMessage(richTextBox1.Handle, 0xb, (IntPtr)1, IntPtr.Zero);
    richTextBox1.Invalidate();
}

private List<int> GetHighlightPositions(string text, string keyword)
{
    List<int> positions = new List<int>();
    int pos = 0, lastPos = 0;
    while (pos > -1 && lastPos < text.Length)
    {
        pos = text.IndexOfAny(Separators.ToArray(), lastPos);
        if (pos > -1)
        {
            if (pos - lastPos == keyword.Length)
            {
                if (text.Substring(lastPos, keyword.Length) == keyword)
                {
                    positions.Add(lastPos);
                }
            }
        }
        lastPos = pos + 1;
    }
    return positions;
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Alf Ator am .
Attachments
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo thetruedon,

für den Fall, dass die Lösung von Alf Ator nicht anerkannt wird, weil sie zu lang ist :-) hier meine Lösung innerhalb der Vorgaben: 14 Zeilen ohne Leerzeilen, 18 mit.

private const String keywordPattern
   = @"\b(?:if|else|while|for|int|bool|string|void|var|42)\b";

protected void HighlightText (Object sender, EventArgs e)
{
  int selectionStart  = _rtb.SelectionStart;
  int selectionLength = _rtb.SelectionLength;

  _rtb.SelectAll ();
  _rtb.SelectionColor = Color.Black;

  foreach (Match m in Regex.Matches (_rtb.Text, keywordPattern)) {
     _rtb.Select (m.Index, m.Length);
     _rtb.SelectionColor = Color.Red;
  }

  _rtb.Select (selectionStart, selectionLength);
}

Regex rules! :-)

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Sehr schön! Dann bist du jetzt auch dran, eine neue Aufgabe zu Posten =)
private Nachricht | Beiträge des Benutzers
thetruedon
myCSharp.de - Member



Dabei seit:
Beiträge: 112

beantworten | zitieren | melden

@Alf
OK der Ansatz ist zu erkennen, wobei natürlich die Keywords von mir gekonnt mal nicht verwendet wurden :D Aber am Ende hast du ja diese gefärbt also wenn keiner Einwände hat geht die Lösung klar.

@herbivore
Jap ziemlich genau so hab ich das ganze auch gelöst. *Thumbs up*
Kommt ein Mann in die Wirtschaft und sagt zum Wirt: 16 Bit!
Sagt der Wirt: Das ist ein Wort!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Community,

nachdem Alf Ator das Recht, eine Aufgabe zu stellen, an mich abgetreten hat (ich habe extra noch mal per PM nachgefragt), habe ich gleich eine Aufgabe, mit direktem Bezug zur vorigen. Wie man gesehen hat, ist die Lösung mit Regex viel kürzer und - wie ich finde - viel verständlicher, als die ohne.

Ich gebe zwar zu, dass Regex-Pattern zwar nicht immer leicht zu lesen sind (es ist einfacher, sie zu schreiben :-), aber ich behaupte, dass Regex-Pattern immer noch leichter zu lesen sind, als wenn man sie in normalem Code ausprogrammieren würde.

Hier kommt eure Chance mich zu widerlegen!

Ich habe einen typisches Regex-Pattern zum Erkennen von HTML-Tags (inkl. eines Attributs) geschrieben. (Dass es in bestimmten Situationen günstiger sein kann, einen HTML-Parser zu verwenden, ist mir klar, soll hier aber keine Rolle spielen. Für die Aufgabe darf jedenfalls keiner verwendet werden.)
[B]Die Aufgabe ist, eine Methode zu schreiben, die mit normalen (String-)Operation exakt das gleiche tut, wie der folgende Code:[/B]

[CSHARP]
public static bool GetTag (String input, out String tag, out String key, out String value)
{
   tag = key = value = "";
   Match m = Regex.Match (input, pattern, RegexOptions.IgnoreCase | RegexOptions.IgnorePatternWhitespace);
   if (m.Success) {
      tag = m.Groups ["tag"].Value;
      key = m.Groups ["key"].Value;
      value = m.Groups ["value"].Value;
      return true;
   }
   return false;
}
[/CSHARP]

[CSHARP]
private static String pattern = @"
<\s*(?<tag>beispiel)
(?:
   \s+(?<key>[a-z]+)
   \s*=\s*
   (?:
      '(?<value>[^'>]*)'
   |
      (?<value>[^'>\s]+)
   )
)?\s*>
";
[/CSHARP]
Der Pattern bedeutet also mit anderen Worten:

Zuerst kommt eine öffnende eckige Klammer, dann können beliebig viele Spaces folgen, dann folgt das Tag (Gruppe "tag"), bestehend aus der Zeichenfolge "beispiel", also b, e, i, s, p, i, e, l, wegen RegexOptions.IgnoreCase unabhängig von der Groß- und Kleinschreibung.
dann kommt optional ein Attribut, das wie folgt aufgebaut ist:
... zuerst kommen ein oder mehrere Spaces, dann der Attributname (Gruppe "key"), bestehend aus beliebigen Buchstaben (a-z/A-Z, ohne Umlaute),
... dann können beliebig viele Spaces folgen, dann kommt ein Gleichheitszeichen, dann können beliebig viele Spaces folgen,
... dann kommt der Attributwert (Gruppe "value"),
...... wobei dieser entweder aus beliebigen Zeichen, aber nicht Anführungszeichen und nicht schließende spitze Klammer, zwischen genau zwei Anführungszeichen besteht
...... oder aus beliebigen Zeichen, aber nicht Space, nicht Anführungszeichen und nicht schließende spitze Klammer,
danach können beliebig viele Spaces folgen und am Ende steht eine schließende eckige Klammer.

"Spaces" sind z.B. alle White-Spaces-Zeichen, die auf \s passen. "Anführungszeichen" sind einfache Anführungszeichen, damit diese problemlos innerhalb von String-Literalen verwendet werden können. Die verbale Beschreibung dient ohnehin nur dazu, den Einstieg zu erleichtern; maßgeblich in allen Detailfragen und Zweifelsfällen ist der Regex-Pattern.

Achtet darauf, dass alle optionalen Teile und alle möglichen Alternativen berücksichtigt werden. Wo Spaces steht "dann können beliebig viele Spaces folgen", können sie vorhanden sein oder fehlen. Achtet anderseits darauf, dass nichts akzeptiert wird, was nicht erlaubt ist. Einfach bei den Anführungszeichen zu splitten und den Text dazwischen zu nehmen, reicht nicht, denn <beispiel 'value'=key> ist nicht erlaubt. Auch sind an vielen Stellen nur Leerzeichen erlaubt, nicht beliebige Zeichen. <beispiel : key='value'> und <beispiel key='value' nochirgendwas> würden also keinen Treffer liefern.

Ich habe den Pattern extra in mehrere Zeilen aufgeteilt, damit er lesbarer wird. Dank RegexOptions.IgnorePatternWhitespace geht das problemlos und erhöht die Lesbarkeit ziemlich. Dadurch hat er 10 Zeilen. Ich würde tippen, dass es keine native Lösung gibt, die mit weniger als 20-30 Zeilen auskommt, selbst wenn man Leerzeilen und Zeilen, die nur eine Klammer enthalten, nicht mitzählt, vorausgesetzt, jede Anweisung steht auf einer eigenen Zeile. Ich hätte zwar eine Idee, wie mit der man Anzahl der nötigen Zeilen drücken kann, doch die will ich noch nicht verraten.

Jetzt habe ich viel geschrieben. Entscheidet selbst, ob es euch hilft. Die Aufgabe ist jedenfalls in einem Satz und etwas Code beschrieben, siehe Kasten. Die Aufgabe gilt als nicht gelöst, wenn es mir oder jemand anderem gelingt, mindestens einen Input zu finden, bei dem eure Methode eine andere Rückgabe hat als meine. Andernfalls ist sie gelöst.

Zu guter Letzt noch ein paar Beispiele, mit denen ihr beiden Methoden (eure und meine) füttern könnt, um die gröbsten Schnitzer selbst zu finden.


private static String [] examples = new String [] {
"<beispiel key='value'>",
"<beispiel  key= value >",
"<BeiSpiel  Key= Value >",
"<beispiel  key= val>ue >",
"<beispiel  key ='val>ue'>",
"<beispiel  key ='val<ue'>",
"<beispiel> key ='value'>",
@"<
   beispiel  key
= value
>",
" <  beispiel   a     =      'a, b, c'       >       ",
"abc<beispiel key='value'>def",
"<beispiele key='value'>",
"<beispielkey=value>",
"<beispiel k,e,y='value'>",
"<beispiel : key='value'>",
"<beispiel key='value' nochirgendwas>",
"<beispiel 'key'=value>",
"<beispiel 'key'='value'>"
"<beispiel < key ='value'>>",
};

Viele Spaß und viel Erfolg!

herbivore

PS: Aufgrund eines Hinweises von dN!3L, habe ich mich entschlossen, die Bedingungen für eine korrekte Lösung etwas abzuschwächen: Wenn der input null ist, muss eure Methode nicht das gleiche tun wie meine. Meine wirft eine ArgumentNullException. Jede andere Exception, insbesondere eine NullReferenceException, ist auch ok. Exakt die gleiche Exceptions zu werfen wäre gar nicht möglich, weil im Stacktrace meiner das für euch "verbotene" Regex.Match auftaucht. :-)
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

@herbivore: Nachträglich einfach noch ein return true in die Referenzimplementierung einfügen, tztzt...

Folgende Methode gibt (für die gegebenen Beispiele) das gleiche wie der Referenzcode zurück:


public static bool GetTag2(String input,out String tag,out String key,out String value)
{
	for (int start = input.IndexOf('<');start≥0;start = input.IndexOf('<',start+1))
	{
		tag = key = value = "";

		int end = input.IndexOf('>',start);
		if (end>0)
		{
			string current = input.Substring(start+1,end-start-1).Trim();

			tag = current.Substring(0,Math.Min(current.Length,8));
			if (String.Compare(tag,"beispiel",true)==0)
			{
				if (current.Length>8 && !Char.IsWhiteSpace(current[8]))
					continue;

				if (tag.Length==current.Length)
					return true;

				int equalIndex = current.IndexOf('=');
				if (equalIndex>0)
				{
					key = current.Substring(8,equalIndex-8).Trim();
					value = current.Substring(equalIndex+1).Trim();

					if (key.All(c => (Char.ToLower(c)≥'a' && Char.ToLower(c)≤'z')))
					{
						if (value.StartsWith("'") && value.EndsWith("'"))
						{
							value = value.Substring(1,value.Length-2);
							if (!value.Contains("'"))
								return true;
						}
						else if (!value.Contains("'") && !value.Any(c => Char.IsWhiteSpace(c)))
							return true;
					}
				}
			}
		}
	}

	tag = key = value = "";
	return false;
}
EDIT: Code verkürzt.
EDIT2: Fehler beseitigt.
EDIT3: Den komplett richtigen Code gibt's hier.
Dieser Beitrag wurde 7 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo dN!3L,

sieht schon mal nicht schlecht aus. Und durch die mehrfache Verwendung von Trim auch kürzer als ich dachte. Trotzdem bestätigt der Code mich in meiner Meinung, dass schwieriger zu erkennen und verstehen ist, was der ausprogrammierte Code macht als der Pattern (vorausgesetzt natürlich man kennt Regex). Und schwerer zu warten scheint solcher Code auch zu sein, wie mir aufgefallen ist. Wenn ich im Pattern "beispiel" durch "example" ersetze, ist der Fall gegessen. Du müsstest deine Indexberechungen anpassen (7 statt 8). Ok, das könnte man zwar durch eine Variable im wahrsten Sinne des Wortes variabel machen, aber vermutlich wird man an sowas bei ersten Anlauf oft nicht denken.

Wie dem aber auch sei, der Code ist zwar dicht dran, aber noch nicht ganz korrekt. Damit meine ich nicht, dass IsLetterOrDigit eine andere Zeichenmenge repräsentiert als das (zugegeben auch nachträglich geänderte) [a-z]. Das ist gebongt. Willst du selber suchen (du braucht nicht den ganzen Code neu zu posten, sondern nur die geänderte Zeile) oder (bitte per PM) einen Tipp?

Solange kann dir natürlich noch jemand anders mit seine eigenen Lösung zuvorkommen. :-)

herbivore
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von herbivore
Und schwerer zu warten scheint solcher Code auch zu sein, wie mir aufgefallen ist. Wenn ich im Pattern "beispiel" durch "example" ersetze, ist der Fall gegessen. Du müsstest deine Indexberechungen anpassen (7 statt 8). Ok, das könnte man zwar durch eine Variable im wahrsten Sinne des Wortes variabel machen, aber vermutlich wird man an sowas bei ersten Anlauf oft nicht denken.
Die verwenden Konstanten sind allerdings "Opfer" meiner premature optimization (um Zeilen zu sparen). Im Normalfall hätte das auch gleich "im ersten Anlauf" genau so gemacht - und hätte mir auch den zusätzlichen Aufwand, die Buchstaben selbst zu zählen, erspart. :)
Zitat von herbivore
Wie dem aber auch sei, der Code ist zwar dicht dran, aber noch nicht ganz korrekt. Damit meine ich nicht, dass IsLetterOrDigit eine andere Zeichenmenge repräsentiert als das (zugegeben auch nachträglich geänderte) [a-z]. Das ist gebongt.
Der Fall, der nicht ging, war <beispiel key= va lue >. Da wurde fälschlicherweise "va lue" als korrekt erkannt. Um das zu beheben, habe ich einfach in der viertletzten Codezeile ein && !value.Any(c => Char.IsWhiteSpace(c)) angefügt.
Um das [a-z] umzusetzen, habe ich key.All(c => Char.IsLetterOrDigit(c)) durch key.All(c => (Char.ToLower(c)≥'a' && Char.ToLower(c)≤'z')) ersetzt.
Zitat von herbivore
Trotzdem bestätigt der Code mich in meiner Meinung, dass schwieriger zu erkennen und verstehen ist, was der ausprogrammierte Code macht als der Pattern.
Naja, dein Vorteil ist, dass du das Pattern selbst geschrieben hast und somit besser "siehst", was gemacht wird. Bei der Nur-Stringoperationen-Variante bin wiederum ich unobjektiv, da der Code von mir ist. Soo kompliziert finde ich es nicht.
Wie dem auch sein: Die Nur-Stringoperationen-Lösung profitiert allerdings stark von einigen Besonderheiten des Patterns. So kann man z.B. davon ausgehen, dass eine geschlossene Klammer ">" immer das Ende des (potentiellen) Matches anzeigt (und nicht z.B. noch in value erlaubt sind). Ebenso gibt es klare Trenner für den Anfang (<) und zwischen Key und Value, wobei die Trenner innerhalb andere Elemente ebenso nicht vorkommen dürfen.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo dN!3L,

ich habe leider im geänderten Code noch eine kleine Abweichung gefunden. Nochmal bei der Attributwerten ohne Anführungszeichen. Sollte aber auch nicht schwer zu beheben sein. Einen Tipp gibt es bei Bedarf wieder per PM. Jetzt will ich aber mal so fair sein, dich in Erwartung dieser letzten kleinen Fehlerbehebung schon zum Sieger zu küren.
Zitat
Die verwenden Konstanten sind allerdings "Opfer" meiner premature optimization (um Zeilen zu sparen). Im Normalfall hätte das auch gleich "im ersten Anlauf" genau so gemacht
Für einen realistischen Vergleich wäre Code, der die spätere Wartung berücksichtigt, sicher besser gewesen. In der Praxis nützt es ja nichts zu sagen, hey, mein Code ist so wenig wie möglich länger als der Pattern, wenn der Code dadurch unnötig schwerer zu warten ist. In der Praxis wäre der Code also wohl noch ein bisschen länger.

Da hätte man - um den Preis einer zusätzlichen Anweisung - vermutlich auch die Bedingung in if (end>0) ... negiert und dann ein break gemacht, denn wenn keine schließende Klammern mehr gefunden wird, gibt es keinen Match, egal wieviel öffnende noch kommen.

Für die Aufgabe im Rahmen des Programmierspiels ist es natürlich legitim, Zeilen zu sparen, zumal ich ja selbst den Fokus auf die Zeilenanzahl gelegt habe. Anderseits lag mir auch ein realistischer Vergleich am Herzen. Der ist aber nach diesen Anmerkungen sicher möglich.
Zitat
Naja, dein Vorteil ist, dass du das Pattern selbst geschrieben hast und somit besser "siehst", was gemacht wird. Bei der Nur-Stringoperationen-Variante bin wiederum ich unobjektiv, da der Code von mir ist. Soo kompliziert finde ich es nicht.
Natürlich ist es für einen realistischen Vergleich wichtig, dass jemand, der den Vergleich anstellt, weder den Pattern noch den ausprogrammierten Code geschrieben hat - aber genau das ist ja bei allen Lesern des Threads der Fall.

Natürlich ist dein Code nicht "soo kompliziert". Trotzdem bleibe ich bei meiner Behauptung, dass es im Vergleich zu einem Regex-Pattern schwerer zu erfassen ist, was ausprogrammierter Code macht, der das gleiche wie der Pattern tut. Jeder Leser kann sich anhand dieses Beispiel nun ein eigenes Urteil bilden - ausreichende Regex-Kenntnise vorausgesetzt.
Zitat
Die Nur-Stringoperationen-Lösung profitiert allerdings stark von einigen Besonderheiten des Patterns.
Richtig, ich ärgere mich jetzt wirklich, dass ich in Attributwerten in Anführungsstrichen keine schließenden spitzen Klammern erlaubt habe. Ich denke, das hätte den Code nochmal wesentlich schwieriger gemacht. Anderseits ist es mir auch wieder recht, weil es ja einen Blick auf die schlechtere Wartbarkeit des ausprogrammieten Codes wirft, wenn eine kleine Änderung am Pattern zu einer großen Änderung am ausprogrammierten Code führt.

Ich überlasse es den Lesern als Aufgabe außer Konkurrenz, Code zu schreiben, der das gleiche tut, wie der obige Pattern, nur dass in '(?<value>[^'>]*)' die schließende spitze Klammer weggelassen wird, also '(?<value>[^']*)'. Ich vermute, diese kleine Änderung würde starken Einfluss auf den ausprogrammierten Code haben, ihn vielleicht sogar komplett umwerfen.

herbivore
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

So, mein aktueller Code. Ein Regex-"+" ist halt was anderes, als ein "*"...
Außerdem habe ich die magischen Konstanten ersetzt und das von herbivore vorgeschlagene break eingebaut. Wenn ich den Aufwand der ganzen Nacharbeiten noch mit dazurechne, sind reguläre Ausdrücke eindeutig einfacher erstellt und man findet Fehler schneller...


public static bool GetTag2(string input,out string tag,out string key,out string value)
{
	for (int start = input.IndexOf('<');start≥0;start = input.IndexOf('<',start+1))
	{
		tag = key = value = "";

		int end = input.IndexOf('>',start);
		if (end<0) break;
		string current = input.Substring(start+1,end-start-1).Trim();

		string tagLiteral = "beispiel";
		tag = current.Substring(0,Math.Min(current.Length,tagLiteral.Length));
		if (String.Compare(tag,tagLiteral,true)==0)
		{
			if (current.Length>tagLiteral.Length && !Char.IsWhiteSpace(current[tagLiteral.Length]))
				continue;

			if (tag.Length==current.Length)
				return true;

			int equalIndex = current.IndexOf('=');
			if (equalIndex>0)
			{
				key = current.Substring(tagLiteral.Length,equalIndex-tagLiteral.Length).Trim();
				value = current.Substring(equalIndex+1).Trim();

				if (key.All(c => (Char.ToLower(c)≥'a' && Char.ToLower(c)≤'z')))
				{
					if (value.StartsWith("'") && value.EndsWith("'"))
					{
						value = value.Substring(1,value.Length-2);
						if (!value.Contains("'"))
							return true;
					}
					else if (value.Length≥1 && !value.Contains("'") && !value.Any(c => Char.IsWhiteSpace(c)))
						return true;
				}
			}
		}
	}

	tag = key = value = "";
	return false;
}
Zitat von herbivore
Richtig, ich ärgere mich jetzt wirklich, dass ich in Attributwerten in Anführungsstrichen keine schließenden spitzen Klammern erlaubt habe. Ich denke, das hätte den Code nochmal wesentlich schwieriger gemacht. [...] Ich vermute, diese kleine Änderung würde starken Einfluss auf den ausprogrammierten Code haben, ihn vielleicht sogar komplett umwerfen.
Einfach nach dem string current = ... folgenden Block einfügen:


if (current.Count(c => c=='\'')==1)
{
	end = input.IndexOf('>',input.IndexOf('\'',end));
	current = input.Substring(start+1,end-start-1).Trim();
}
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zum Thema Lesbarkeit von Code vs. Pattern: Es vielen ja öfter die Worte "wer Regex lesen kann". Joshua Flanagan hat eine Fluent API entwickelt, mit der man Patterns für reguläre Ausdrücke erstellen kann. So kann z.B. das Pattern "\d{,3}" mithilfe von Pattern.With.Digit.Repeat.AtMost(3) oder das Pattern "[^\s]" mittels Pattern.With.NegatedSet(Pattern.With.WhiteSpace) erzeugen.

Nun wäre doch einmal interessant, ob der von herbivore verwendete reguläre Ausdruck auch etwas lesbarer erzeugt werden kann.
Erzeuge das [url]oben verwendete Pattern[/url] mithilfe der [url]Readable Regular Expressions API[/url]. Es muss nicht exakt so aussehen (kann es z.B. aufgrund der Leerzeichen auch gar nicht), aber es muss semantisch übereinstimmen. 
Bsp. kann folgendes Pattern mithilfe dieser API erzeugt werden: [tt]<\s*(?<tag>beispiel)(?:\s+(?<key>[a-z]+)\s*=\s*(?:('(?<value>[^'>]*)'|(?<value>[^'>\s]+))))?\s*>[/tt]

Um den Implementierungsaufwand etwas zu minimieren, habe ich ein VS-Projekt mit den nötigen Verweisen und einem Codegerüst angehängt.
Die Aufgabe sollte nicht allzu schwer zu lösen sein. Mit einigen Zeilenumbrüchen für Formatierungszwecke habe ich etwa 15 Zeilen benötigt.

dN!3L
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von dN!3L am .
Attachments
private Nachricht | Beiträge des Benutzers
pdelvo
myCSharp.de - Member

Avatar #avatar-3354.png


Dabei seit:
Beiträge: 1407

beantworten | zitieren | melden

Meine Lösung:

         public static string Pattern2
        {
            get
            {
                // TODO: Pattern fluent deklarieren
                return Pattern.With.Literal("<").WhiteSpace.Repeat.ZeroOrMore.NamedGroup("tag", Pattern.With.Literal("beispiel"))
                    .Group(
                    Pattern.With.WhiteSpace.Repeat.OneOrMore.NamedGroup("key", Pattern.With.Set(Pattern.With.Word).Repeat.OneOrMore)
                    .WhiteSpace.Repeat.ZeroOrMore.Literal("=").WhiteSpace.Repeat.ZeroOrMore
                     .Group(Pattern.With.Choice.Either(
                        Pattern.With.Literal("'").NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'>")).Repeat.ZeroOrMore).Literal("'")
                ,
                Pattern.With.NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'>").WhiteSpace).Repeat.OneOrMore)
                )
                ).Repeat.Optional).Repeat.Optional.WhiteSpace.Repeat.ZeroOrMore.Literal(">");

            }
        }

Die tests laufen alle durch, allerdings finde ich da den ganz normalen regulären ausdruck einfacher zu lesen
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Das Pattern von pdelvo stimmt nicht komplett semantisch mit dem geforderten überein. So gibt beispielsweise Abweichungen bei den Eingaben <beispiel köy=value> (für die Attributschlüssel sind Umlaute nicht erlaubt) und <beispiel key=> (Attributwert entweder in Anführungszeichen oder mindestens ein Zeichen).

Hier ist meine Lösung, die das oben genannte Pattern <\s*(?<tag>beispiel)(?:\s+(?<key>[a-z]+)\s*=\s*(?:('(?<value>[^'>]*)'|(?<value>[^'>\s]+))))?\s*> erzeugt:


return Pattern.With
    .Literal("<").WhiteSpace.Repeat.ZeroOrMore
    .NamedGroup("tag",Pattern.With.Literal("beispiel"))
    .Phrase(Pattern.With
        .WhiteSpace.Repeat.OneOrMore
        .NamedGroup("key",Pattern.With.Set(Range.Of('a','z')).Repeat.OneOrMore)
        .WhiteSpace.Repeat.ZeroOrMore
        .Literal("=")
        .WhiteSpace.Repeat.ZeroOrMore
        .Phrase(Pattern.With.Choice.Either
        (
            Pattern.With.Literal("'").NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'").Literal(">")).Repeat.ZeroOrMore).Literal("'"),
            Pattern.With.NamedGroup("value", Pattern.With.NegatedSet(Pattern.With.Literal("'").Literal(">").WhiteSpace).Repeat.OneOrMore)
        ))
    ).Repeat.Optional
    .WhiteSpace.Repeat.ZeroOrMore
    .Literal(">");

Da sich pdelvo bisher noch nicht wieder gemeldet hat, steht es jedem frei, eine neue Aufgabe zu stellen.
private Nachricht | Beiträge des Benutzers
uNki
myCSharp.de - Member



Dabei seit:
Beiträge: 61

beantworten | zitieren | melden

da ich selbst einige nachmittage daran gesessen habe, und man im netz nicht viel dazu findet, bin ich gespannt wie ihr das löst:

es geht darum, termine in einem kalender (typischer office kalender z.b.) so anzuordnen, dass sie sich grafisch nicht überdecken, aber dennoch den vorhandenen platz sinnvoll ausnutzen. bild siehe anhang.

gegeben sei dazu jetzt folgende klasse, die einen termin darstellt:



class CTermin
{
    //wieviel Platz braucht der Termin im Kalender? Divider = 1/3 --> Termin.Width = 1/3 * Breite des Tages in Pixeln
    public double Divider { get; set; }

    //an welcher Stelle beginnt der Termin im Kalender? HorizontalIndex = 0 --> ganz am Anfang, HorizontalIndex = 1 --> an 2. Stelle
    public int HorizontalIndex { get; set; }

    //Start- und Endzeit 
    public DateTime StartTime { get; set; }
    public DateTime EndTime { get; set; }

    //Breite in Pixeln
    public int Width { get; set; }

    public CTermin(DateTime start, DateTime end)
    {
        StartTime = start;
        EndTime = end;
    }
}



sowie eine liste von terminen, die ihr selbst füllen könnt:


List<CTermin> termine = new List<CTermin>();


eure aufgabe ist es, eine funktion/methode zu schreiben, die diese liste so bearbeitet, dass die werte für Divider, HorizontalIndex und Width korrekt gesetzt werden, um diese termine anhand dieser angaben wie im bild unten zeichnen zu können.

(das schema mit Divider, HorizontalIndex und Width ist meine idee, ich denke wir bleiben für diese aufgabe dabei, denn so kann ich es am schnellsten überprüfen)

anforderungen, die schon aus dem bild hervorgehen:

- termine dürfen sich nicht überlagern
- je "früher" die startzeit, desto weiter links steht der termin
- je länger die dauer des termins, desto weiter links steht der termin
- der platz muss voll ausgenutzt werden (war für mich der schwerste part, habe ich selbst erst am wochenende fertig bekommen ^^)


die lösungen/werte für Divider, HorizontalIndex und Width für das beispiel im bild wären unter der annahme, dass die tagesbreite 100px ist wie folgt (meine zeichenroutine ermittelt automatisch eine "größte teilbare" tagesbreite für in diesem falle 3 termine nebeneinander --> 96px)

blau: 1/3, 0, 32
grün: 1/3, 1, 32
braun: 1/3, 2, 32
rot: 1/3, 2, 32
orange: 2/3, 1, 64
gelb: 1/1, 0, 96


bin gespannt :)

(ich brauche mehr als 50 zeilen, aber ich bin mir sicher, dass mein code nicht der effizienteste ist.. ist über mehrere wochen gewachsen)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von uNki am .
Attachments
private Nachricht | Beiträge des Benutzers
deerhunter
myCSharp.de - Member



Dabei seit:
Beiträge: 92

beantworten | zitieren | melden

Na, da bin ich aber mal auf Lösungen gespannt. Mal schauen, ob mir eine clevere Idee kommt, wie man die Aufgabe lösen kann - vielleicht beim Joggen oder Duschen ;-)

Edit: Ach ja, es wäre schön, wenn du ein paar Beispieldaten geben könntest, so dass man sich gleich auf die Problemlösung stürzen kann.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von deerhunter am .
private Nachricht | Beiträge des Benutzers
uNki
myCSharp.de - Member



Dabei seit:
Beiträge: 61

beantworten | zitieren | melden

dann vielleicht direkt die daten für das beispiel im bild:

blau: 09:00 - 15:30 uhr
grün: 09:00 - 14:30 uhr
braun: 09:30 - 11:30 uhr
rot: 11:30 - 12:00 uhr
orange: 14:30 - 15:00 uhr
gelb: 15:30 - 16 uhr

breite eines tages: 96px (durch 3 teilbar für unser beispiel)



termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 15:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 14:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 09:30:00"), Convert.ToDateTime("16.02.2012 11:30:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 11:30:00"), Convert.ToDateTime("16.02.2012 12:00:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 14:30:00"), Convert.ToDateTime("16.02.2012 15:00:00")));
termine.Add(new CTermin(Convert.ToDateTime("16.02.2012 15:30:00"), Convert.ToDateTime("16.02.2012 16:00:00")));

EDIT:

nur zur erinnerung, es geht nicht darum, die zeichenroutine etc umzusetzen!
nur eine funktion, die die 3 werte Divider, HorizontalIndex und Width berechnet!

klasse CTermin wurde um ctor ergänzt
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von uNki am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo uNki,

vorne weg: Da nach Namenskonventionen keine Präfixe für Klassen verwendet werden sollen und außerdem alles andere englisch war, habe ich mir erlaubt, die Klasse CTermin in Appointment umzubenennen. Außerdem sei angemerkt, dass mein Code ohne Fehlerbehandlung ist, insbesondere ohne Berücksichtigung von Null-Referenzen.

Nette Aufgabe. Hier meine Lösung in 46 Zeilen (inkl. Leerzeilen und Zeilen, die nur geschweifte Klammern enthalten). Die Methode PlaceAppointments erwartet die Termine entsprechend der von dir genannten Kriterien sortiert.

public static void PlaceAppointments (List <Appointment> appointments)
{
   List <List <Appointment>> grid = new List <List <Appointment>> ();

   int horizontalIndex;
   foreach (Appointment appointment in appointments) {
      horizontalIndex = 0;
      foreach (List <Appointment> row in grid) {
         if (!Appointment.Overlapp (appointment, row)) {
            break;
         }
         ++horizontalIndex;
      }
      if (grid.Count ≤ horizontalIndex) {
         grid.Add (new List <Appointment> ());
      }
      grid [horizontalIndex].Add (appointment);
      appointment.HorizontalIndex = horizontalIndex;
   }

   foreach (Appointment appointment in appointments) {
      for (horizontalIndex = appointment.HorizontalIndex + 1; horizontalIndex < grid.Count; ++horizontalIndex) {
         if (Appointment.Overlapp (appointment, grid [horizontalIndex])) {
            break;
         }
      }
      appointment.Divider = (horizontalIndex - appointment.HorizontalIndex) / (double)grid.Count;
      appointment.Width   = (horizontalIndex - appointment.HorizontalIndex) * (100 / grid.Count);
   }
}

public static bool Overlapp (Appointment appointment1, Appointment appointment2)
{
   return appointment1.EndTime > appointment2.StartTime
       && appointment2.EndTime > appointment1.StartTime;
}

public static bool Overlapp (Appointment appointment, List <Appointment> appointments)
{
   foreach (Appointment comparativeAppointment in appointments) {
      if (Appointment.Overlapp (appointment, comparativeAppointment)) {
         return true;
      }
   }
   return false;
}

Wenn die Termine nicht sortiert sind, kann man sie mit List.Sort und folgendem Comparer sortieren:

public static int Compare (Appointment appointment1, Appointment appointment2)
{
   if (appointment1.StartTime == appointment2.StartTime) {
      if (appointment1.EndTime == appointment2.EndTime) {
         return 0;
      }
      if (appointment1.EndTime > appointment2.EndTime) {
         return -1;
      }
      return 1;
   }
   if (appointment1.StartTime > appointment2.StartTime) {
      return 1;
   }
   return -1;
}

Hier noch der Test für dein Beispiel:

public static void Main (string [] astrArg)
{
   List <Appointment> appointments = new List <Appointment> ();
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 15:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:00:00"), Convert.ToDateTime("16.02.2012 14:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 09:30:00"), Convert.ToDateTime("16.02.2012 11:30:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 11:30:00"), Convert.ToDateTime("16.02.2012 12:00:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 14:30:00"), Convert.ToDateTime("16.02.2012 15:00:00")));
   appointments.Add(new Appointment(Convert.ToDateTime("16.02.2012 15:30:00"), Convert.ToDateTime("16.02.2012 16:00:00")));

   appointments.Sort (Appointment.Compare);

   Appointment.PlaceAppointments (appointments);

   foreach (Appointment appointment in appointments) {
      Console.WriteLine (appointment);
   }
}

Wobei dieser folgende ToString-Methode benötigt:

public override String ToString ()
{
   return "" + StartTime + " - " + EndTime + ": " + HorizontalIndex + ", " + Width + ", " + Divider;
}

herbivore
private Nachricht | Beiträge des Benutzers
uNki
myCSharp.de - Member



Dabei seit:
Beiträge: 61

beantworten | zitieren | melden

korrekt.
46 zeilen... 8o
irre, ich brauche 200

aber ganz ehrlich.. habe auch nichts anderes von herbivore erwartet


hier meine alternative lösung, bitte ausgrauen, wenn zuviel.

(Divider würde sich in meinem fall ergeben aus ownConflictDivider/maxConflictDivider)


    public void CalculateAppointmentPositions()
    {
        //appList sortieren
        AppointmentList.Sort((x, y) => x.Start.CompareTo(y.Start));

        //konfliktlisten erstellen
        //---------------------------------------------------------------------

        //temporäre conflictGroups löschen
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            conflictGroup.Clear();
        }

        //temporäre groupList löschen
        groupList.Clear();

        //temporäre ConflictApps der appointments löschen
        foreach (CAppointment app in AppointmentList)
        {
            app.ConflictApps.Clear();
        }

        foreach (CAppointment appToCheck in AppointmentList) //appList enthält ALLE apps, die auf dem screen sichtbar sind und ist nach startzeit sortiert
        {
            appToCheck.MaxConflictDivider = 1;
            //konfliktpartner von appToCheck ermitteln
            foreach (CAppointment appToCompare in AppointmentList)
            {
                if ((appToCompare != appToCheck))
                {
                    if ((appToCheck.End > appToCompare.Start) && (appToCheck.Start < appToCompare.End))
                    {
                        appToCheck.ConflictApps.Add(appToCompare);
                    }
                }
            }

            if (groupList.Count < 1) //wenn noch keine conflictGroup existiert (--> erstes zu prüfendes appointment in dem fall), neue gruppe erstellen und appToCheck hinzufügen
            {
                List<CAppointment> conflictGroup = new List<CAppointment>();
                conflictGroup.Add(appToCheck);
                groupList.Add(conflictGroup);
            }

            else
            {
                bool listFound = false;
                foreach (List<CAppointment> conflictGroup in groupList)
                {
                    foreach (CAppointment app in appToCheck.ConflictApps)
                    {
                        if (conflictGroup.Contains(app))
                        {
                            conflictGroup.Add(appToCheck);
                            listFound = true;
                            break;
                        }
                    }
                }

                if (listFound == false) //eine neue konfliktliste erstellen --> neue gruppe von appointments mit konflikten untereinander
                {
                    List<CAppointment> conflictGroup = new List<CAppointment>();
                    conflictGroup.Add(appToCheck);
                    groupList.Add(conflictGroup);
                }
            }

        }
        //konfliktlisten erstellt. alle appointments die miteinander konflikte haben, stehen jetzt jeweils in einer eigenen liste "conflictGroup"
        //---------------------------------------------------------------------

        foreach (CAppointment appToCheck in AppointmentList)
        {
            appToCheck.OwnConflictDivider = appToCheck.ConflictApps.Count + 1;
        }

        //maximalen conflictDivider feststellen
        //---------------------------------------------------------------------
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            if (conflictGroup.Count > 1)
            {
                List<int> dividers = new List<int>();

                foreach (CAppointment appToCheck in conflictGroup)
                {
                    appToCheck.MaxConflictDivider = 1;
                    foreach (CAppointment appToCompare in conflictGroup)
                    {
                        if ((appToCompare.Start.Date == appToCheck.Start.Date) && (appToCompare != appToCheck))
                        {
                            if ((appToCompare.Start.TimeOfDay ≤ appToCheck.Start.TimeOfDay) && (appToCompare.End.TimeOfDay > appToCheck.Start.TimeOfDay))
                                appToCheck.MaxConflictDivider++;
                        }
                    }
                    dividers.Add(appToCheck.MaxConflictDivider);
                }

                foreach (CAppointment app in conflictGroup)
                {
                    app.MaxConflictDivider = dividers.AsQueryable().Max();
                }
                dividers.Clear();
            }
        }
        //---------------------------------------------------------------------



        //horizontalen index der appointments ausgehend von ihrer startzeit ermitteln
        //---------------------------------------------------------------------
        List<List<CAppointment>> groupListSorted = new List<List<CAppointment>>();
        foreach (List<CAppointment> conflictGroup in groupList)
        {
            groupListSorted.Add(conflictGroup.OrderBy(app => app.Start).ThenByDescending(app => app.End).ToList());
        }

        foreach (List<CAppointment> conflictGroup in groupListSorted)
        {
            foreach (CAppointment app in conflictGroup)
            {
                app.HorizontalIndex = 0;
            }

            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                horizontalIndexGroup.Clear();
            }
            horizontalIndexGroups.Clear();

            for (int j = 0; j < conflictGroup[0].MaxConflictDivider; j++)
            {
                List<CAppointment> xFactorGroup = new List<CAppointment>();
                horizontalIndexGroups.Add(xFactorGroup);
            }

            foreach (CAppointment appToCheck in conflictGroup)
            {
                foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
                {
                    bool containsConflictApp = false;
                    foreach (CAppointment conflictApp in appToCheck.ConflictApps)
                    {
                        if (horizontalIndexGroup.Contains(conflictApp))
                        {
                            containsConflictApp = true;
                            break;
                        }
                    }
                    if (containsConflictApp == false)
                    {
                        horizontalIndexGroup.Add(appToCheck);
                        break;
                    }

                }
            }
            //-----------------------------------------------------------------


            //eigenen conflictDivider ermitteln
            //-----------------------------------------------------------------
            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                foreach (CAppointment app in horizontalIndexGroup)
                {
                    app.HorizontalIndex = horizontalIndexGroups.IndexOf(horizontalIndexGroup);
                    app.OwnConflictDivider = app.MaxConflictDivider;

                        foreach (var conflictApp in app.ConflictApps)
                        {
                            if (conflictApp.HorizontalIndex == app.HorizontalIndex + 1)
                            {
                                app.OwnConflictDivider = conflictApp.OwnConflictDivider;
                                break;
                            }
                            else
                            {
                                app.OwnConflictDivider = app.MaxConflictDivider - app.ConflictApps.Count < 1 ? 1 : app.MaxConflictDivider - app.ConflictApps.Count;
                            }
                        }

                }
            }

            foreach (List<CAppointment> horizontalIndexGroup in horizontalIndexGroups)
            {
                foreach (CAppointment app in horizontalIndexGroup)
                {
                    foreach (CAppointment conflictApp in app.ConflictApps)
                    {
                        for (int i = 0; i < app.MaxConflictDivider; i++)
                        {
                            if (conflictApp.HorizontalIndex == app.HorizontalIndex + i)
                            {
                                if (app.OwnConflictDivider > (conflictApp.HorizontalIndex - app.HorizontalIndex))
                                    app.OwnConflictDivider = (conflictApp.HorizontalIndex - app.HorizontalIndex);
                                break;
                            }
                        }
                    }
                }
            }
            //-----------------------------------------------------------------
        }

        //temporäre conflictGroups löschen
        foreach (List<CAppointment> conflictGroup in groupListSorted)
        {
            conflictGroup.Clear();
        }

        //temporäre groupListSorted löschen
        groupListSorted.Clear();
        //---------------------------------------------------------------------

        Invalidate();
    }
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von uNki am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

hier kommt meine neue Aufgabe:

Es geht darum, ein Array von beliebig vielen Elementen in linearer Zeit nach ihrer Kategorie zu sortieren. Damit das tatsächlich in linearer Zeit möglich ist, gibt es nur drei Kategorien. Die Elemente mit der Kategorie First sollen am Anfang des Arrays stehen, die der Kategorie Third am Ende und die der Kategorie Second dazwischen. Zur Implementierung darf kein zusätzliches Array (und auch keine andere Collection) verwendet werden. Die Signatur der zu schreibenden Methode lautet:

public static void Sort<T> (T [] items) where T : ICategorizable

Ihr könnt auf folgendem Code-Rahmen aufbauen:

using System;

static class App
{
   public static void Main ()
   {
      Element [] elements = new Element [] {
         new Element (Category.Second),
         new Element (Category.First),
         new Element (Category.Third),
         new Element (Category.Second),
         new Element (Category.Third),
         new Element (Category.First),
      };

      Sort (elements);

      foreach (Element element in elements) {
         Console.WriteLine (element);
      }
   }

   public static void Sort<T> (T [] items) where T : ICategorizable
   {
      // hier euer Code
   }

   public static void Swap <T> (T [] items, int i1, int i2)
   {
      T item = items [i1];
      items [i1] = items [i2];
      items [i2] = item;
   }
}

public enum Category {
   First,
   Second,
   Third
}

public interface ICategorizable
{
   Category Category { get; }
}

public class Element : ICategorizable
{
   public Element (Category category)
   {
      Category = category;
   }

   public Category Category { get; private set; }

   public override String ToString ()
   {
      return Category.ToString ();
   }
}

Das Array in der Main-Methode ist nur ein Beispiel. Die Methode soll in allen Fällen korrekt funktionieren. Fehlerbehandlung ist nicht erforderlich. Ihr könnt also davon ausgehen, dass der Parameter der Sort-Methode nicht null ist und dass keine anderen als die drei genannten Kategorien vorkommen können.

Viel Spaß und viel Erfolg!

herbivore
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2340

beantworten | zitieren | melden

Hallo, ich habe mich für ein einfaches Bubble-Sort entschieden. Da die Kategorien in einem enum vorliegen stellt dies auch garkein Problem dar.

Meine Sort-Methode:


public static void Sort<T>(T[] items) where T : ICategorizable
    {
        if(items == null)
              return;

        // a imple bubble sort should do the work.
         int runs = items.Length;
         do
         {
             for(int i = 0; i < runs-1; i++)
             {
                 if(items[i].Category > items[i+1].Category)
                 {
                     Swap<T>(items, i, i+1);
                 }
             }
             runs--;
         }while(runs > 0);
    }

Getestet habe ich es mit zufällig generierten Items, die demnach auch zufällige Kategorien hatten. Auch weitere Kategorien hinzufügen stellte kein Problem dar.

// Edit: Ich seh grad, dass das "in linearer Zeit" kursiv ist, hat das etwas zu sagen?
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von inflames2k am .
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

Hallo,

Bubblesort ist nicht linear. Im schlimmsten Fall hat es quadratischen Aufwand, siehe z.B. auf der Wikipedia Seite zur Übersicht der Sortierverfahren.

Ist auch leicht erklärbar, da du ja die Laufvariable ändern musst bei Umsortierung und daher abhängig von der Vorsortierung sich die Anzahl der Durchläufe ändert und im Worstcase halt fast n² viele Durchläufe hast, bei n Elementen.

Auf der Übersichstseite sieht man auch, das man die Aufgabe nicht mit einem Standardsortieralgorithmus lösen kann, da keiner der aufgeführten im Worst Case linear ist.
Baka wa shinanakya naoranai.

Mein XING Profil.
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

Erstmal hi

@inflames2k: Ja, das linear hat etwas zu bedeuten

Hier ist meine Lösung:


public static void Sort<T>(T[] items) where T : ICategorizable
{
     Int32 start = 0;
     Int32 end = items.Length - 1;
     Int32 i = 0;

     while(i ≤ end)
     {
         T item = items[i];
         if (item.Category == Category.First && i > start)
             Swap(items, i, start++);
         else if (item.Category == Category.Third)
             Swap(items, i, end--);
         else
              i++;
     }
}

Ich möchte keine neue Aufgabe stellen bzw. es fällt mir keine ein, also kann jemand anderes gerne eine neue Aufgabe stellen
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von DerKleineTomy am .

Moderationshinweis von talla (17.02.2012 - 20:36:47):

Neue Aufgaben darf man erst stellen wenn der Aufgabenposter die Korrektheit der Lösung bestätigt. Dies ist noch nicht erfolgt, also kann noch keine neue Aufgabe gestellt werden.

private Nachricht | Beiträge des Benutzers
talla
myCSharp.de - Experte

Avatar #avatar-3214.jpg


Dabei seit:
Beiträge: 7290
Herkunft: Esslingen

beantworten | zitieren | melden

Hallo,

die Lösung ist auch nicht linear. Besser als Bubblesort was den Worstcase angeht, aber trotzdem abhängig von der Anzahl der Vertauschungen und der Anzahl der Items und nicht nur von der Anzahl der Items (was bei Linearität der Fall sein muss).
Baka wa shinanakya naoranai.

Mein XING Profil.
private Nachricht | Beiträge des Benutzers
inflames2k
myCSharp.de - Experte

Avatar #AARsmmPEUMee0tQa2JoB.png


Dabei seit:
Beiträge: 2340

beantworten | zitieren | melden

Dann muss ich nachliefern. :) Ich denke folgende Sortierung sollte Linear sein und ist meiner Meinung nach ausschließlich Abhängig von der Anzahl der Items.


    public static void Sort<T>(T[] items) where T : ICategorizable
    {
        for (int i = 0; i < items.Length-1; i++)
        {
            for (int j = i; j < items.Length; j++)
            {
                if (items[i].Category > items[j].Category)
                    Swap<T>(items, i, j);
            }
        }
    }
Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager | Spielkartenbibliothek
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

Der worst-case meiner Methode ist 2n Schleifendurchläufe, wenn im Array nur Elemente der Category First sind, was ebenfalls in O(n) liegt und somit in linearer Zeit fertig wird. Hab den code noch mal angepasst damit es nun auch konstant ist mit genau n durchläufen.

public static void Sort<T>(T[] items) where T : ICategorizable
 {
      Int32 start = 0;
      Int32 end = items.Length - 1;
      Int32 i = 0;
 
     while(i ≤ end)
      {
          T item = items[i];
          if (item.Category == Category.First && i > start)
              Swap(items, i++, start++);
          else if (item.Category == Category.Third)
              Swap(items, i, end--);
          else
               i++;
      }
 }

Edit:
@inflames2k: Das ist immernoch keine lineare Zeit :P
@ dN!3L: Da war ich ein Stück scheller :P
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von DerKleineTomy am .
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Ich habe auch was:


public static void Sort<T>(T[] items) where T : ICategorizable
{
	int idx = 0;
	for (int i=0;i<items.Length;i++)
		if (items[i].Category==Category.First)
			Swap(items,i,idx++);
	for (int i=0;i<items.Length;i++)
		if (items[i].Category==Category.Second)
			Swap(items,i,idx++);
}

BTW: Ich sehe nicht wirklich, warum die Lösung von DerKleineTomy nicht linear sein soll. In jedem Schleifendurchlauf wird entweder "i" größer oder "end" kleiner. Also insgesamt "items.Length" Durchläufe.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers