Sie sind nicht angemeldet.

  • Anmelden

Zahlenrätsel

Sheep

Erleuchteter

  • »Sheep« ist der Autor dieses Themas

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

1

19.10.2008, 02:31

Zahlenrätsel

Das Rätsel spielt auf einem 5x5 Brett, wobei jedes der 25 Felder mit einer Ziffer von 1 bis 4 zu besetzen ist. Für das Füllen gelten folgende Regeln:

1. Eine 1 darf man immer setzen.
2. Eine 2 darf man setzen, wenn eine 1 daneben steht.
3. Eine 3 darf man setzen, wenn eine 1 und eine 2 daneben steht.
4. Eine 4 darf man setzen, wenn eine 1, eine 2 und eine 3 daneben steht.
5. Als "daneben stehen" gilt horizontale (rechts, links) und vertikale (oben, unten) Nachbarschaft. Nein, diagonal ist nicht.

Ziel ist es, die Summe der Ziffern möglichst gross zu bekommen. Ein fix zusammengeklicktes Beispiel hängt an, die Summe ist dort 52.
»Sheep« hat folgende Datei angehängt:
  • rätsel.png (984 Byte - 706 mal heruntergeladen - zuletzt: 16.11.2023, 16:38)

GEC|Napo

Erleuchteter

Beiträge: 8 654

Wohnort: Köln

Beruf: GER

  • Nachricht senden

2

19.10.2008, 02:45

58 im ersten Versuch

1 3 4 1 3
3 2 2 4 2
4 1 1 3 1
2 4 3 2 3
1 3 2 1 2

GEC|Napo

Erleuchteter

Beiträge: 8 654

Wohnort: Köln

Beruf: GER

  • Nachricht senden

3

19.10.2008, 02:53

59 mit System, ist glaub ich schon das Maximum

2 4 1 4 2
1 3 2 3 1
2 4 1 4 2
1 3 2 3 1
2 4 1 4 2

Sheep

Erleuchteter

  • »Sheep« ist der Autor dieses Themas

Beiträge: 4 172

Beruf: GER

  • Nachricht senden

4

19.10.2008, 12:12

Wir kamen gestern auch nur auf 59, wobei es da auch nichtsymmetrische Varianten gibt. 64 ist auf jeden Fall eine Grenze, wenn man die Anzahl der notwendigen 1en, 2en und 3en anschaut...

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

5

13.11.2008, 01:40

Nachdem ich jetz ein paar Wochen immer mal wieder rumprogrammiert und Leute mit C2Q Rechnern geärgert hab, hatte ich eben wohl den richtigen Einfall für mein Lösungsprogramm:

2 4 1 3 1
1 3 4 2 4
4 2 4 1 3
3 1 3 3 2
2 1 2 4 1

=61

Wer n Fehler findet darf sich gerne melden ;)

Vielleicht geht auch noch mehr *deutlich betagten athlon64 3200+ mit C0-stepping streichel* :P

MaxPower

Erleuchteter

Beiträge: 7 452

  • Nachricht senden

6

13.11.2008, 09:57

Sind doch "nur" 25 hoch 4 Möglichkeiten, oder? Sollte man mit Brute Force ja knacken können.

Sind knapp unter 400.000 Möglichkeiten. DIe Gültigkeitsprüfung und die bewertung müssen effiyient programmiert sein, ich denke mal in reinem C is das deutlich unter einer Stunde zu schaffe, dass maximum zu finden

ma schauen, vielleicht hab ich Lust später das auszuprobieren, falls ich dazu zeit finde -.-

und dann nochmal in python und dann vergleichen ^^

Erg_Raider

Meister

Beiträge: 1 823

Wohnort: GER

  • Nachricht senden

7

13.11.2008, 10:42

hab ich grad nen denkfehler oder sollten es eher 4 hoch 25 möglichkeiten sein? (wenn man die randbedingungen erstmal ignoriert)

GEC|Napo

Erleuchteter

Beiträge: 8 654

Wohnort: Köln

Beruf: GER

  • Nachricht senden

8

13.11.2008, 12:02

Nein kein Denkfehler, du hast recht. 4^25 ist ne Menge! man könnte es verringern indem man anfängt mindestens 7 Einsen zu setzen.

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

  • Nachricht senden

9

13.11.2008, 12:29

selbst 4^15 = 2^30 wären noch enorm.
Glaube brute force ist nicht so das wahre. Algebraiker (??) oder jemand in optimization, diskrete Mathematik müsste da recht schnell auskunft geben können. Schätze mal wird nen NP hartes Problem sein.

GWC|lazy

Erleuchteter

Beiträge: 6 260

  • Nachricht senden

10

13.11.2008, 12:38

hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^

Yezariael

Erleuchteter

Beiträge: 5 157

Wohnort: ... da wars dunkel und kalt...

  • Nachricht senden

11

13.11.2008, 12:49

Zitat

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^


hier heisst er doch Pitt82 :P

MaxPower

Erleuchteter

Beiträge: 7 452

  • Nachricht senden

12

13.11.2008, 12:50

Zitat

Original von Erg_Raider
hab ich grad nen denkfehler oder sollten es eher 4 hoch 25 möglichkeiten sein? (wenn man die randbedingungen erstmal ignoriert)


nein ich hatte den Denkfehler (und noch keinen Kaffee zu diesem Zeitpunkt)


4 hoch 25 is natuerlich was anderes ^^

Das sind 1.125.899.906.842.624 Faelle

also 1.125 Trillionen wenn ich mich nicht verzaehlt habe

Der Quadcore wuerde gegenueber nem singlecore nur was bringen, wenn man 4 threads oder 4 prozesse fuer die berechnung benuzten wuerde

welche sprache war das denn?

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

  • Nachricht senden

13

13.11.2008, 13:01

Dieses Problem lässt sich doch super parallelisieren.

Wenn ihr den entscheidenden Teil eures Codes postet, kann ich vielleicht noch ein paar Tipps geben, wie man noch durch die richtige Programmiertechnik Geschwindigkeit rausholen kann.

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

14

13.11.2008, 13:30

Zitat

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^


Ja ich sollte das mit Stunden einfach weglassen .. das is mittlerweile eigentlich nur noch ne Art normierter Geschwindigkeitsindex (er berücksichtigt nämlich nich wenn das Programm ungültige Kombinationen überspringt). Ich würd die verbleibende Zeit ja gern genauer angeben, aber das is die performanceeinbußen die ich dafür hab nich wert.

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

15

13.11.2008, 14:27

Zitat

Original von MaxPower
welche sprache war das denn?


C (Win32) - Threads sind es atm 12 (11 und 12 werden schnell verworfen, weil sie am Start ungültige Kombinationen haben) auf Dauer sind also noch 10 Threads - genug für einen Quadcore ;)

Wenn du nix zutun hast Worf:

Hmpf .. beim durchlesen hier den Fehler gefunden :D

Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von »pitt82« (13.11.2008, 14:40)

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

  • Nachricht senden

16

13.11.2008, 14:56

Naja, ging mr eher um allgemeine Rezepte. Poste mal nen kurzen Ausschnitt, einfach nur die Schleifen.

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

17

13.11.2008, 15:12

Sowas? :D

Quellcode

 
1
2

	for(j=0;j<25;j++)
		neu.feld[j]=1;

sylence

Administrator

Beiträge: 1 863

Wohnort: Dresden

Beruf: GER

  • Nachricht senden

18

13.11.2008, 15:15

Her mit dem Code. Wenn er sich auch unter nem GNU/Linux kompilieren lässt und nicht zu lange rechnet, würd ichs mal auf nem aktuellen System mit 2 Xeon Quadcores austesten.

GWC|lazy

Erleuchteter

Beiträge: 6 260

  • Nachricht senden

19

13.11.2008, 15:32

Zitat

Original von Yezariael

Zitat

Original von GWC|lazy
hm also firebirds brute force programm was ich gestern auf meinem quadcore laufen lassen hab hätte noch ~2800 stunden gebraucht, so überzeugt bin ich davon jetzt nicht ^^


hier heisst er doch Pitt82 :P


lol echt? das wusst ich gar nich :D

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

20

13.11.2008, 15:49

Zitat

Original von sylence
.. Wenn er sich auch unter nem GNU/Linux kompilieren lässt ..


Lässt er sich leider nicht. (process.h, pthread.h)

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

  • Nachricht senden

21

13.11.2008, 15:50

Zitat

Original von pitt82
Sowas? :D

Quellcode

 
1
2

	for(j=0;j<25;j++)
		neu.feld[j]=1;

Genau.
Natürlich noch vorher was mit nem kleinen Kommentar, was die Funktionsweise des programms deutlich macht. Letzlich hat man ja nur einige Schleifen und Bedingungen und merkt sich die maximale Kombination sowie die maximale Summe.
Denke bei der Art wie man die Schleifen setzt bzw. die Komination aus Schleifen und Abfragen macht kann man sicher 1-2, wenn nicht mehr, Größenordnungen rausholen.

Weiß aber sicher jeder Informatiker besser, was da zu machen ist - kann man ja aber hier drin diskutieren.

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

22

13.11.2008, 20:38

Hat sich imho erledigt - is jetz in <4h durchgelaufen und hat nix größeres als 61 gefunden 8)

MaxPower

Erleuchteter

Beiträge: 7 452

  • Nachricht senden

23

13.11.2008, 21:13

Kannst du den Quellcode ma posten?

Nach welche Strategie hast du die Threads aufgeteilt?

pitt82

Meister

Beiträge: 2 114

  • Nachricht senden

24

13.11.2008, 21:41

Hab die komplette Visual Studio Solution mal gepackt ..

Für die die das nich haben:
main() findet man in der \59_new\59_new\59_new.cpp

Die wichtigsten Dateien daneben sind:
threads.cpp
error_check.cpp

Threads hab ich so eingeteilt, dass jeder einen Teil der Kombinationen bekommt. Wenn man die 25 Felder wie Stellen einer Zahl betrachtet, dann ist oben links a^0;a^1;.. bis unten rechts a^23;a^24. Die Start/Zielwerte der Threads unterscheiden sich dann auf den stellen 23 und 24.
Hatte zuerst versucht die Threads bei der Überprüfung des arrays einzusetzen, aber das war wahnsinnig langsam und ich hätte - damit es wirklich effektiv gewesen wäre - Threads auf gleicher Augenhöhe sich gegenseitig abschießen lassen müssen.

Da es kein Gemeinschaftsprojekt ist musst du auf ausführliche Kommentierung aber leider verzichten ;)
»pitt82« hat folgende Datei angehängt:
  • 59_new.rar (3,67 MB - 42 mal heruntergeladen - zuletzt: 15.11.2023, 22:08)

AtroX_Worf

Erleuchteter

Beiträge: 11 465

Wohnort: Hamburg

Beruf: GER

  • Nachricht senden

25

21.11.2008, 13:48

ganz nett umgesetzt, hatte gerade mal nen Blick drauf geworfen.

WW_Asmodean

Meister

Beiträge: 2 551

Wohnort: Regensburg

Beruf: GER

  • Nachricht senden

26

21.11.2008, 13:55

yo yo yo ... nur so ...

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »WW_Asmodean« (21.11.2008, 13:55)