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:
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:
- An Weihnachten sehe ich die ganze Verwandschaft wieder. Mein Vater ist da, er freut sich bestimmt mich, seinen Sohn, wieder zu sehen. Und mein Opa ist auch da. Der freut sich auch meinen Vater, seinen Sohn, wieder zu sehen.
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
Tilman - Mo 22.12.08 01:12
Narses hat folgendes geschrieben : |
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
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
Xentar hat folgendes geschrieben : |
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, 8100, 0); 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, 90, 0); 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
Hidden hat folgendes geschrieben : |
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..22] of 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] = 0) and (A[i,k]=1) and (A[k,j] = 1) then 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
AdrianK hat folgendes geschrieben : |
@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 ...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!