Rätsel + Denksport Forum

[rushifell]

hallo an alle,
78 mal 151 mm stehen als fläche zur verfügung. diese soll euromünzen (von jeder sorte 3, siehe bild) aufnehmen. folgende frage: kann bei anderer anordnung eine weitere münze (egal welche sorte) aufgenommen werden? die striche zwischen den münzen symbolisieren die kontakte der münzen untereinander.

muenzsammelbox1.gif (456.65 KiB) 1320-mal betrachtet

[Otmar]

Hi Rushifell,

ich hab, mangels nötigen Kleingelds und mangels Münzbox, das ganze digital gemacht, und mit einer einfachen Methode, alle Münzen per Zufall in die Box geworfen und dann etwas "digital" gerüttelt, bis sie nicht mehr übereinanderlagen. Dabei konnte ich noch ein weiteres Eurostück zufügen:

In der ersten Tabelle siehst du Durchmesser, Positionen der Mittelpunkte und Abständer der Münzen zu den Rändern. Alles in mm. Die Euromünze mit 23.25mm Durchmesser ist vier mal vorhanden, alle anderen nur drei mal:

Mehr ->

Durchmesser   x         y     Abstände zu den vier Rändern
16.25,    8.126,    8.126    0.001,  134.750    0.001,   61.749
16.25,  121.831,   27.250  113.706,   21.044   19.125,   42.625
16.25,   47.456,   50.301   39.331,   95.419   42.176,   19.574
18.75,   37.253,   34.206   27.878,  104.372   24.831,   34.419
18.75,   73.154,   50.453   63.779,   68.471   41.078,   18.172
18.75,   24.780,   48.304   15.405,  116.845   38.929,   20.321
21.25,  110.054,   67.374   99.429,   30.321   56.749,    0.001
21.25,   51.711,   10.626   41.086,   88.664    0.001,   56.749
21.25,   83.185,   30.686   72.560,   57.190   20.061,   36.689
19.75,   81.279,   68.124   71.404,   59.846   58.249,    0.001
19.75,  104.085,   30.538   94.210,   37.040   20.663,   37.587
19.75,  116.962,    9.876  107.087,   24.163    0.001,   58.249
22.25,   73.593,   11.137   62.468,   66.282    0.012,   55.738
22.25,   11.126,   32.959    0.001,  128.750   21.834,   33.916
22.25,   95.882,   11.126   84.757,   43.993    0.001,   55.749
24.25,  138.875,   12.647  126.750,    0.000    0.522,   53.228
24.25,   94.662,   50.524   82.537,   44.213   38.399,   15.351
24.25,   12.126,   65.871    0.001,  126.750   53.746,    0.004
23.25,  139.375,   36.433  127.750,    0.000   24.808,   29.942
23.25,  118.407,   46.731  106.782,   20.968   35.106,   19.644
23.25,   59.359,   66.374   47.734,   80.016   54.749,    0.001
23.25,   35.974,   66.374   24.349,  103.401   54.749,    0.001
25.75,  138.125,   62.280  125.250,    0.000   49.405,    2.845
25.75,   59.465,   32.821   46.590,   78.660   19.946,   32.304
25.75,   28.356,   13.797   15.481,  109.769    0.922,   51.328

In der nächsten Tabelle sieht man die Abstände zwischen den verschiedenen Münzen, biginnend mit dem Abstand der ersten zur zweiten Münze in der ersten Zeile:

Mehr ->

.  99.052
.  41.419  61.615
.  21.597  67.364   1.557
.  60.091  36.424   8.199  20.657
.  25.994  81.808   5.263   0.073  29.672
.  99.148  23.067  46.135  60.001  20.595  67.380
.  24.907  53.313  21.153   7.660  25.233  26.313  60.140
.  59.627  20.048  22.009  26.067   2.167  41.004  24.225  16.073
.  76.611  39.578  20.232  36.327   0.199  40.625   8.285  44.156  16.987
.  80.542   0.048  41.978  47.683  17.537  62.020  16.817  35.531   0.400  24.214
.  90.851   0.043  62.408  64.090  40.463  80.621  37.413  44.755  19.173  48.560   4.597
.  46.287  31.608  27.835  22.544  18.819  40.852  45.273   0.138   0.025  36.504  15.141  22.387
.   5.764  91.603  21.007   5.657  43.949   0.041  82.994  24.575  50.345  57.474  71.991  87.325  43.919
.  68.558  11.300  43.038  42.509  24.923  59.735  36.257  22.424   1.570  37.840   0.074   0.117   0.039  65.274
. 110.577   2.194  78.620  82.384  54.319  98.036  39.102  64.437  35.788  57.969  17.121   0.087  42.049 106.104  19.769
.  76.114  15.525  26.956  38.183   0.007  48.417   0.073  35.873   0.168   0.111   0.096  24.364  21.418  62.113  16.167  33.969
.  37.634  96.055  18.359  18.923  41.446   0.150  75.190  45.214  56.543  47.190  76.513  96.854  59.055   9.677  76.811 113.220  59.701
. 114.517   0.052  73.209  81.146  46.688  94.207  20.377  69.133  34.233  44.677  14.279  13.251  47.728 105.546  27.569   0.041  23.131 106.860
.  97.093   0.030  51.291  61.115  24.405  72.640   0.019  53.592  16.455  21.350   0.118  15.384  34.480  85.412  19.382  16.007   0.296  84.241   0.110
.  57.825  53.962   0.251  18.033   0.066  18.016  28.454  34.021  20.661   0.489  35.811  59.186  34.292  35.928  43.480  72.215  14.947  23.487  62.184  38.979
.  44.814  74.601   0.003  11.194  19.446   0.257  51.837  35.678  36.932  23.839  55.463  77.248  44.081  18.892  58.745  92.333  37.041   0.104  84.398  61.491   0.135
. 119.828  17.634  70.456  82.456  43.788  91.953   5.029  77.175  39.876  34.395  23.793  33.766  58.340 106.340  42.341  24.639  20.025 101.050   1.377   0.611  54.371  77.733
.  35.970  41.614   0.208   0.005   0.073  15.733  37.763   0.011   0.316  18.749  21.928  39.157   1.881  24.340  18.390  56.932  14.398  32.735  55.491  36.061   9.054  16.459  58.245
.   0.010  73.438  20.199   0.014  35.634  12.442  74.199   0.069  33.871  53.094  54.807  65.943  21.315   1.769  43.579  85.524  50.798  29.544  88.803  71.384  36.538  28.627  94.249  10.715

[rushifell]

hallo otmar,
welche nester-software hast du dafür verwendet? welche version? wie waren deine eingabeparameter?

sieht aber aus, wie eine echte lösung. gratulation und vielen dank dafür. ich werde mal das ganze grafisch darstellen und eine andordnungsanalyse durchführen. melde mich. melde dich bitte.

gruss

[Otmar]

Hallo Rushifell,
ich hab da ein kleines Programm in C++ geschrieben. Es werden am Anfang alle Münzen in die Box an zufällige Orte geworfen und dann wird optimiert. Wenn es nicht klappt wird neu geworfen. Die Optimierung läuft ein bischen wie Brownsche Bewegung ab, da auch bei mimimaler Überlappung der Münzen eine Münze eine nicht zu unterschreitende Distanze verschoben wird. Und die Bewegung ist invers. D.h. je kleiner die Überlappung, desto größer die Bewegung. Bei ganz kleiner Überlappung springen die Münzen etwas. Je nach Größe etwa 264 bis 450 Mikrometer. Ich denke, dass das wichtig für den Erfolg der Optimierung ist. Ansonsten ist die Optimierung einem Newton Verfahren ähnlich.

Hab hier mal den Quellcode und falls du es mit einen anderen C++ Compiler als ich übersetzt, habe ich die Zufallsfunktion gleich mit implementiert, so dass du die Berechnungen auch 1:1 in einer anderen Sprache programmieren könntest. Ach so "int" ist bei mir noch 32 Bit breit.

Mehr ->

struct SPack
{
   SPack() 
   {
      r32 = 1; // Zufallszahlengenerator initialisieren
      // Länge und Breite der Box und Münzdurchmesser sind in 1/4 mm angeben.
      double dHight = 312; 
      double dWidth = 604;
      double adDiameter[8]={65,75,85,79,89,97,93,103};
      int    aiCount[8]   ={ 3, 3, 3, 3, 3, 3, 4,  3};
      struct SCircle
      {
         double dx, dy, dRadius;
      } aCircle[25];
      for(int iLoop = 1;;iLoop++) // Endlosschleife für viele Lösungen
      {
         // initialer Münzwurf
         for (int i=0, k=0; i < 8; i++) for (int j=0; j < aiCount[i]; j++, k++)
         {
            aCircle[k].dRadius = adDiameter[i]/2 + 0.002; // 0.5 Mikrometer Reserve für Rundungsfehler
            aCircle[k].dx = aCircle[k].dRadius + fmod(rand1()+.5, dWidth - 2 * aCircle[k].dRadius); 
            aCircle[k].dy = aCircle[k].dRadius + fmod(rand1()+.5, dHight - 2 * aCircle[k].dRadius); 
         }
         // Bis zu 10000 kleine Optimierungen an diesem Wurf
         for (int iTrials=0 ; iTrials < 10000; iTrials++)
         {
            // Für jede liegende Münze eine kleine Verschiebung berechnen, wenn sie nicht frei liegt.
            double dMaxOverlap = 0;
            for (int k = 0; k < 25; k++)
            {
               double   dxSum = 0, dySum = 0, dOverlap = 0;
               for (int l = 0; l < 25; l++) if (l!=k)
               {
                  // Differenzen bezogen auf Mittelpunkte
                  double dxDiff = aCircle[k].dx - aCircle[l].dx;
                  double dyDiff = aCircle[k].dy - aCircle[l].dy;
                  double dDistance = sqrt(dxDiff*dxDiff+dyDiff*dyDiff);
                  double dRadiusPart = aCircle[k].dRadius + aCircle[l].dRadius;
                  // teste Überlappung
                  if (dDistance < dRadiusPart)
                  {
                     // Gewichtete Summe für Differenzen bezogen auf Mittelpunkte bilden. 
                     dxSum += dxDiff * (dRadiusPart/(dDistance + 30));
                     dySum += dyDiff * (dRadiusPart/(dDistance + 30));
                     dOverlap += dRadiusPart - dDistance;
                  }
               }
               SetMax(dMaxOverlap, dOverlap);
               // Kleine Verschiebung der Münze. Anteil je Überlappung ist am 
               // Anfang klein und Ende größer, je nach Münzpaar von 264 bis 450 Mikrometer.
               aCircle[k].dx += dxSum/100;
               aCircle[k].dy += dySum/100;
               // Münze zurück in Box. Ohne Überlappung passiert hier nichts.
               SetMax(aCircle[k].dx, aCircle[k].dRadius);
               SetMin(aCircle[k].dx, dWidth-aCircle[k].dRadius);
               SetMax(aCircle[k].dy, aCircle[k].dRadius);
               SetMin(aCircle[k].dy, dHight-aCircle[k].dRadius);
            }
            if (dMaxOverlap == 0)
            {
               // Ausgabe der Lösung
               break;
            }
         }
      } 
   }
   void SetMin(double &r, double d) {if (r > d) r = d;}
   void SetMax(double &r, double d) {if (r < d) r = d;}
   int rand1(void) 
   {         
      r32 = r32 * 0x343fd + 0x269EC3;
      return (r32 >> 16) & 0x7fff; 
   } 
   int r32;

} Pack;

Bei der oben angegebenen Lösung hat es iLoop = 4750 gebraucht, bis eine Konfiguration für die vierfach gelegte Ein-Euro Münze gefunden wurde. Wenn man
int aiCount[8] ={ 3, 3, 3, 3, 3, 3, 3, 4};
verwendet, also das 2 Euro Stück vier mal haben möchte, schafft das Programm eine Lösung nach iLoop = 60789 Zufallswürfen. Da hat mein Rechner ein paar Stunden dafür gebraucht. Hier sind die Ergebnisse, Durchmesser und Position des Mittelpunktes, alles in Millimeter:

Mehr ->

16.25  27.987874  29.295346
16.25 104.287436  53.797836
16.25  28.288604  69.874500
18.75 113.881791  68.624500
18.75 124.829555  30.757740
18.75 141.624500  43.747716
21.25  85.145353  49.213692
21.25  72.590210  67.374500
21.25 122.864679  50.735302
19.75  64.524583  48.427695
19.75  93.121936  68.124500
19.75  74.638942  31.391812
22.25  30.488882  49.683383
22.25  11.125500  61.100002
22.25  11.125500  38.664932
24.25 113.059888  12.125500
24.25  47.739879  33.904920
24.25 101.905913  33.678188
23.25  36.890472  11.625500
23.25  13.326284  11.625500
23.25 139.374500  66.374500
25.75 138.124500  12.892971
25.75  48.931806  65.124500
25.75  61.387240  12.875500
25.75  87.941636  12.875500

Oder als einfache Grafik in der die vier mal gelegte 2 Euro Münze hellblau ist:

Mehr ->

Münzen 4 x 2Euro.png (35.41 KiB) 1261-mal betrachtet

[rushifell]

hallo otmar,
hast du den code für das problem geschrieben oder hattest du einen ähnlichen an dieses problem angepasst? auf welchem system mit welchem compiler hattest du den code übersetzt? .. und wieso ist dein int doppelt breit? egal...

also ich bin sicher kein fachmann. aber ich kann mal locker erkennen, dass die komplexität der aufgabe und deine echte lösung für wesentlich mehr taugt, als für ein en-passant-rätsel. was zum teufel machst du beruflich? schreib eine autonesting software und werde reich damit! wenn ich mir ansehe, was die anderen softwareschmieden für ihre mittelklassigen produkte verlangen, prophezeihe ich dir einen aufstieg in den pop-olymp der cad-branche.

mag auch sein, dass die gepostete funktion kein "kunstwerk" darstellt. aber der grosse wert liegt wohl eher im sauberen algorytmischen umsetzen auf das problem bezogen. ich bin sicher nicht leicht zu beeindrucken. aber du hast es geschafft: applaus (tosend)

gruss

[Otmar]

hast du den code für das problem geschrieben.

Ja, klar. Bisher hatte ich noch keine solchen Optimierungen gemacht. Allerdings weiss ich, dass Probleme dieser Art NP vollständig sind und deshalb das etwas spielerische Herangehen durchaus gute Ergebnisse liefern kann.

auf welchem system mit welchem compiler hattest du den code übersetzt?

Ist ein älterere C++ Kompiler. Ich hab dafür meinen alten 32 Bit Windows XP Rechner genommen.

.. und wieso ist dein int doppelt breit?

32 Bit war in den letzten 10 Jahren für "int" üblich. Im Moment kommt aber der 64 Bit "int" Wert. Ich hab die Integer Breite nur genannt, wegen der Portierbarkeit, weil ich dachte, dass die verwendete rand1() Funktion mit größeren "int" Breiten anders arbeitet. Aber das ist nicht der Fall und deshalb war der Hinweis auch nicht wichtig.

aber du hast es geschafft: applaus