Entwickler-Ecke

Ankündigungen - Adventsgewinnspiel 2008 - Tipps/Lösung zu Gewinnspiel 3


Christian S. - Mo 15.12.08 01:54
Titel: Adventsgewinnspiel 2008 - Tipps/Lösung zu Gewinnspiel 3
Hallo!

Da es in der Shoutbox eine kleine Diskussion zum Abgabeformat gegeben hat, hier nicht gerade ein Tipp, sondern eine Klarstellung. Für das im Rätsel gegebene Beispiel sähe die Abgabe so aus:

Quelltext
1:
A,D,E                    


Viele Grüße
Christian


Klabautermann - Mi 17.12.08 22:05

Hallo,

für diejenigen unter euch die mit der Aufgabe dieser Woche noch ihre Probleme haben hier ein kleiner Hinweis:



Viel Spaß beim weiter Programmieren!


Narses - Mo 22.12.08 01:07

Moin!

Die Lösung des Gewinnspiels ist auf mehrere Arten möglich. Wer nicht faul ist, kann´s sogar nur mit einem Blatt Papier und Stift rauskriegen. Deshalb geben wir mal einfach nur die Lösung an: ;)

Quelltext
1:
A,B,C,G,H,K,L,N,O,S,U,Y                    

cu
Narses


Wolle92 - Mo 22.12.08 01:11

Gut, immerhin richtig, und falls jemand noch andere Unit-Listen basteln will und das ausprobieren will, hier mein Script:
http://eicke92.ei.ohost.de/zirkulaere_referenzen.php


Tilman - Mo 22.12.08 01:12

user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Die Lösung des Gewinnspiels ist auf mehrere Arten möglich. Wer nicht faul ist, kann´s sogar nur mit einem Blatt Papier und Stift rauskriegen.

Stimmt, ich muss aber zugeben dass ich bis ich da sgemerkt habe es schon rekursiv implementiert hatte.


Xentar - Mo 22.12.08 01:16

Hab's händisch in einer Textdatei gelöst. ;)
War sogar gar nicht mal soo schwer, 20 Minuten oder so.


Arne K. - Mo 22.12.08 01:18

user profile iconWolle92 hat folgendes geschrieben Zum zitierten Posting springen:
Gut, immerhin richtig, und falls jemand noch andere Unit-Listen basteln will und das ausprobieren will, hier mein Script:
http://eicke92.ei.ohost.de/zirkulaere_referenzen.php

Also ist deine Lösung richtig, immerhin! Dein Programm ist aber trotzdem fehlerhaft ;-)
Es findet nämlich auch Verweise in Units, die keine Verweise enthalten.

Deine Lösung bei D z.B.:
D => A => C => L => E => K => I => K => R => U => A => H => G => R => O => N => G => O => B => N => V => S => Y => E =>

An der Stelle K => R ist (u.A.) ein Fehler, denn die Unit R referenziert nicht die Unit U. Sie referenziert selbst gar keine Unit, wie es die Aufgabenstellung klärt. Dadurch kamen auch deine utopisch langen Ketten zustande, über die ich mich so gewundert habe ;-)


Wolle92 - Mo 22.12.08 01:22

stimmt, ich hab die rücksprünge in der rekursion nicht beachtet, hab aber keine Lust, das noch zu ändern...


Regan - Mo 22.12.08 01:25

user profile iconXentar hat folgendes geschrieben Zum zitierten Posting springen:
Hab's händisch in einer Textdatei gelöst. ;)
War sogar gar nicht mal soo schwer, 20 Minuten oder so.

Ich habs in einem Entwurf-Formular hier in der EE gelöst, undzwar in 15 Minuten :P .


jaenicke - Mo 22.12.08 01:54

Ja, dann poste ich auch natürlich wieder mein Lösungsprogramm, ich finde die rekursive Variante immer noch am elegantesten, deshalb poste ich mal die.
Grundsätzlich ist das Problem bei der Geschwindigkeit das Auslesen des Memoinhalts. Das dauert im Vergleich zum Algorithmus ewig (Weil nicht TStringList sondern TMemoStrings als Klasse Verwendung findet, und die ist leider relativ langsam.). :D
Zeitaufwand der ersten Version vielleicht 10-15 Minuten, dann noch etwas mehr für den Rest.


Tilman - Mo 22.12.08 02:17

Ich poste mal nur den Screenshot meines Programms, machen tun die ja doch alle das gleiche, aber ich habe bei meinem Angegeben dass es immer den kürzesten String ausgeben soll, daher zum Vegrleich.

"Easy" startete übrigens die einfache Variante, mit der man es auch auf Papier hätte lösen können, die andern Buttons beziehen sich nur auf das Konsolen Fenster um da einige Sachen auszugeben.


jaenicke - Mo 22.12.08 03:24

Ja, bei mir wird nur die erste zirkuläre Referenz einer Unit ausgegeben, alle weiteren werden nicht mehr gesucht. (Was man aber sehr einfach ändern könnte, indem man die Abbrüche entfernt.)

Zunächst hatte die erste Version noch ca. 1 ms gebraucht, und da hab ich dann ein wenig Pointerspielerei betrieben. Trotzdem komme ich auf 140 Mikrosekunden, wenn ich jedesmal aus dem Memo auslese oder auf 40 Mikrosekunden, wenn ich aus einer TStringList jedesmal lese. Das ist auch in dem eben geposteten Programm drin, aber ich kanns ja auch mal direkt posten:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
type
  PStrings = ^TStrings;

function TfrmMain.GetCircularReferences(uLines: PStrings): string;
var
  UnitData, CurPointer, Visited: PBoolean;
  function CheckCircular(uChar, uCheck: Integer): Boolean;
  var
    i: Integer;
  begin
    Result := False;
    if PBoolean(Integer(Visited) + uCheck)^ then
      Exit;
    PBoolean(Integer(Visited) + uCheck)^ := True;
    for i := 65 to 90 do
      if PBoolean(Integer(UnitData) + uCheck * 90 + i)^
        and ((uChar = i) or CheckCircular(uChar, i)) then
      begin
        Result := True;
        Exit;
      end;
  end;
var
  i, j, LineCount: Integer;
  Line: string;
  Chars: PByte;
begin
  Result := '';
  GetMem(UnitData, 8100);
  FillMemory(UnitData, 81000);
  LineCount := uLines^.Count;
  GetMem(Chars, LineCount);
  for i := 0 to LineCount - 1 do
  begin
    Line := uLines^[i];
    Chars^ := Ord(Line[1]);
    CurPointer := PBoolean(Integer(UnitData) + Chars^ * 90);
    Inc(Chars);
    j := 3;
    while j <= Length(Line) do
    begin
      PBoolean(Integer(CurPointer) + Ord(Line[j]))^ := True;
      Inc(j, 2);
    end;
  end;
  Dec(Chars, LineCount);

  GetMem(Visited, 90);
  for i := 0 to LineCount - 1 do
  begin
    CurPointer := PBoolean(Integer(UnitData) + Chars^ * 90);
    for j := 65 to 90 do
      if PBoolean(Integer(CurPointer) + j)^ then
      begin
        FillMemory(Visited, 900);
        if (j = Chars^) or CheckCircular(Chars^, j) then
        begin
          Result := Result + Chr(Chars^) + ',';
          Break;
        end;
      end;
    Inc(Chars);
  end;
  FreeMem(Visited, 90);
  Dec(Chars, LineCount);

  FreeMem(Chars, LineCount);
  FreeMem(UnitData, 8100);

  if Length(Result) > 0 then
    Result := Copy(Result, 1, Length(Result) - 1)
  else
    Result := 'keine Funde';
end;
Wobei das PStrings gar nicht nötig wäre, es ist ja ohnehin ein Objekt, aber so passt es zum Rest. :D


Hidden - Mo 22.12.08 09:00

Hi :)

Ja, es lies sich definitiv leichter mit Stift und Papier lösen. Dummerweise habe ich mich dabei vertan und die unit S falsch weggestrichen :( Ansonsten stimmt meine Lösung überein.

Was lernt man daraus: Vor dem Absenden doppelt prüfen :dunce:

mfG,


jaenicke - Mo 22.12.08 09:20

user profile iconHidden hat folgendes geschrieben Zum zitierten Posting springen:
Ja, es lies sich definitiv leichter mit Stift und Papier lösen. Dummerweise habe ich mich dabei vertan und die unit S falsch weggestrichen
Naja, vom Zeitaufwand her ist es etwa identisch. Der Unterschied ist eben, dass es bei einem Programm keine Fehler gibt.
Und ich hab die erste Version einfach runtergeschrieben, kompiliert und funktionierte, wie gesagt, vielleicht 10 Minuten (unterbrochen durch Posts und so, also in Realtime etwas mehr). :D

Wenn man dann nicht noch hergeht und die Lösung schöner und dann auch noch performanter macht hält sich der Aufwand ziemlich in Grenzen. :D


Gausi - Mo 22.12.08 09:33

Ich möchte hier mal eine andere Methode vorstellen, das Problem zu lösen. Die bisherigen basieren ja auf einer Tiefen- oder Breitensuche durch den Graphen. Ich bestimme die die "Transitive Hülle" des Graphen und gebe am Ende die Schleifen (u,u) aus. Ist zwar nicht die theoretisch eleganteste Möglichkeit, aber sehr übersichtlich implementierbar:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
type
  TAdjazenzMatrix = Array['A'..'Z''A'..'Z'of Integer;

var Namen : Array[1..22of String = (
    'ARCHER','BLAKE','CYLONS','DALEK','FARGO','GKAR','HUGO','JANEWY','KIRK','LUKE','MCKAY',
    'NOG','OBIVAN','PICARD','QUARK','SYLAR','TEALC','UHURA','WHO','XENA','YAR','ZAPHOD');

A: TAdjazenzMatrix;

procedure InitMatrix;
var i, j: Char;
    n, l, iName: Integer;
begin
    for i := 'A' to 'Z' do
      for j := 'A' to 'Z' do
        A[i,j] := 0;

    for n := 1 to 22 do
    begin
        l := length(Namen[n]);
        for iName := 2 to l do
          A[Namen[n][1], Namen[n][iName] ] := 1;
    end;
end;

procedure TransitiveHull;
var k,i,j: Char;
begin
   for k := 'A' to 'Z' do
     for i := 'A' to 'Z' do
       for j := 'A' to 'Z' do
       begin
           if (A[i,j] = 0and (A[i,k]=1and (A[k,j] = 1then
               A[i,j] := 1
       end;
end;

function GetCircles: String;
var c: Char;
begin
  result := '';
  for c := 'A' to 'Z' do
      if A[c,c] = 1 then
          result := result + c + ',';
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
    InitMatrix;
    TransitiveHull;
    Edit1.Text := GetCircles;
end;
Und es ist auch ohne Tricks sehr schnell. :D


jaenicke - Mo 22.12.08 09:37

Ja, so ähnlich sah meine nicht rekursive Variante auch aus, allerdings war die nicht so schnell, weshalb ich die wieder verworfen habe.
Wenn ich mir das so ansehe habe ich es mir dabei unnötig kompliziert gemacht, deine Version ist einfacher. :(
Eigentlich ist es ja auch klar so. Naja, hinterher ist man immer schlauer. :D


GTA-Place - Mo 22.12.08 10:05

War einfach zu lösen: Erstmal in einer einfachen Schleife alle Units rausgeworfen, die nie aufgerufen werden oder die es nicht gibt. Musste man mehrmals durchjagen, dann waren glaub weniger als 10 Units übrig. K:K streicht man weg. Und dann denkt man an Mathematik und fängt mit Ersetzen an. Hab ich zum Beispiel A:R,C,H,R (R war glaub auch nicht dabei, bin mir grad nicht sicher), dann ersetzt man überall (das geht im Texteditor per Hand ;-) ) in den anderen Strings das A durch A,R,C,H (das A muss dabei bleiben). Und schon hat man am Ende einen langen String, aus dem man per Schleife alle doppelten Einträge entfernt, dann noch sortiert und fertig.


AdrianK - Mo 22.12.08 11:25

Juhu! Habs auch richtig...
Die Aufgabe habe ich gelöst, indem ich die ganze Unitliste in einen Graphen geschrieben habe (hatte zufälliger Weise am selben Tag den MSDN Webcast über die Graphentheorie gesehen... :)) und dann mittels Breitensuche die Kanten des Graphen so lange verfolgte bis ich alle Knoten besucht hatte, oder wieder "zurückgekommen" bin -> Zirkuläre Referenz :)

@Edit: Bin ich denn der einzige der's mit C# gemacht hat?


baka0815 - Mo 22.12.08 12:52

Ich hatte es als Konsolenversion gebaut, aber den Quellcode hab' ich nicht mehr gespeichert. Weiß also noch nicht, ob ich's richtig habe. :D


AdrianK - Mo 22.12.08 12:56

meine Lösung ist auch ne Konsolenversion...


Boldar - Mo 22.12.08 14:56

mmhz ich habe StarUML dafür missbraucht und dasals "Aktivitätendiagramm" geschrieben, also die Units als nodes und die Referenzen als edges... und dann solange die gelöscht, wo keine hinführen oder keine Wegführen, bis halt das Übrigblieb!!!


baka0815 - Di 23.12.08 10:27

Zitat:
Diese Frage hast Du richtig beantwortet.

Juhu, trotzdem nix gewonnen. :(

Ich hab's so gemacht, dass ich die Liste rekursiv durchgegangen bin. Die, die ich schon geprüft habe, habe ich mir gemerkt und beim wiederholten auftreten nicht beachtet.
Wenn innerhalb der Rekursion dann das Ursprüngliche aufgetreten ist, war klar, dass es eine Schleife ist.


Heiko - Di 23.12.08 12:16

So habe ichs auch gemacht, nur irgendwie vergisst er die Hälfte... und bisher ka wieso :?!?:


C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
<?php

$inp = array(
  "A"=>"R,C,H,E,R",
  "B"=>"L,A,K,E",
  "C"=>"Y,L,O,N,S",
  "D"=>"A,L,E,K",
  "F"=>"A,R,G,O",
  "G"=>"K,A,R",
  "H"=>"U,G,O",
  "J"=>"A,N,E,W,Y",
  "K"=>"I,R,K",
  "L"=>"U,K,E",
  "M"=>"C,K,A,Y",
  "N"=>"O,G",
  "O"=>"B,I,V,A,N",
  "P"=>"I,C,A,R,D",
  "Q"=>"U,A,R,K",
  "S"=>"Y,L,A,R",
  "T"=>"E,A,L,C",
  "U"=>"H,U,R,A",
  "W"=>"H,O",
  "X"=>"E,N,A",
  "Y"=>"A,R",
  "Z"=>"A,P,H,O,D"
);

function TestCircle($start, $stop)
{
  global $inp;
  if (!array_key_exists($start, $inp))
  {
    return false;
  }
  foreach ($inp[$start] as $val)
  {
    if (in_array($val, $stop))
    {
      if ($val == $stop[0])
      {
        echo $val.",";
      }
      return true;
    }
    $new = $stop;
    $new[] = $val;
    if (TestCircle($val, $new)) return true;
  }
  return false;
}

foreach ($inp as $key => $val)
{
  $inp[$key] = split(",", $val);
}

foreach ($inp as $key => $val)
{
  TestCircle($key, array($key));
}
?>


Yogu - Di 23.12.08 12:51

Hallo,

jetzt hab ich das dritte Rätsel richtig gelöst, aber immer noch nichts gewonnen. Langsam glaub ich, da ist was faul :evil:

Jetzt, wo ich so eure Progrämmchen sehe, glaube ich ernsthaft, ich hab was falsch gemacht. Meine Lösung ist zwar richtig, aber ich mein Zirkuswichtel erstellt ein Log mit 23784 Zeilen, die ausschließlich mit "Crawl for" und "Found" beginnen. Er findet jeden Buchstabe im Durchschnitt 1254 mal :shock:

Wenn ihr einen eher langsamen Rechner habt, würde ich empfehlen, das Log erstmal zu deaktivieren, da das direkt in die ListBox schreibt und daher nicht besonders performant ist. Ohne Log schafft er es bei mir aber in ca. 7 Millisekunden.


jfheins - So 04.01.09 15:05

user profile iconAdrianK hat folgendes geschrieben Zum zitierten Posting springen:
@Edit: Bin ich denn der einzige der's mit C# gemacht hat?


Nein, ich auch ;)

Anbei mein Lösungsprogramm, es gibt alle Zirkulärewn Referenzen im Memo aus - das macht das ganze aber bei sehr vielen Units etwas langsam ...