SAS Code Kata: Pandigitale Zahlen

[CKothenschulte]

Hallo zusammen,

kurz vor dem Wochenende möchte ich gerne eine (ältere) Idee von Herrn @AndreasMenrath wieder aufgreifen:
Es ist mal wieder Zeit für eine Code Kata!

Zu erstellen ist eine SAS-Tabelle, die alle pandigitalen Zahlen enthält.

Eine pandigitale Zahl zeichnet folgende Merkmale aus:
- Sie ist 10-stellig.
- Jede Ziffer (0 bis 9) ist einmal enthalten.
- Die erste Stelle muss größer gleich 1 sein.

Spoiler:
- Jede pandigitale Zahl hat die Quersumme 45.
- Es gibt 3.265.920 pandigitale Zahlen.

Beispiel: 9876541023

Ich habe 2 (1/2) Lösungen erstellt (Vorerst folgt lediglich das Log.):
Lösung 1:

 NOTE: The data set WORK.PANDIGITAL has 3265920 observations and 2 variables.
 NOTE: DATA statement used (Total process time):
       real time           2:04.17
       cpu time            2:04.02

Lösung 1b (Optimierung von Lösung 1):

 NOTE: The data set WORK.PANDIGITAL has 3265920 observations and 2 variables.
 NOTE: DATA statement used (Total process time):
       real time           0.96 seconds
       cpu time            0.99 seconds

Lösung 2:

NOTE: The data set WORK.PANDIGITAL has 3265920 observations and 2 variables.
NOTE: DATA statement used (Total process time):
      real time           39:13.16
      cpu time            39:10.53

(Eine so lange Laufzeit hatte ich nicht erwartet.)

Ich bin gespannt auf (weitere) Lösungen und Ideen/Ansätze!

Insbesondere die Performance finde ich interessant.

Meine Lösungen werde ich dann in ein paar Tagen posten.

[FreelanceReinh]

Hallo @CKothenschulte,

vielen Dank für die Aufgabe.

Eine mögliche Lösung:

data pandig;
array x[0:9] _temporary_ (0:9);
do _n_=1 to 3628800;
  call allperm(_n_, of x[*]);
  if x[9] then do;
    z=x[0]+10*x[1]+100*x[2]+1e3*x[3]+1e4*x[4]+1e5*x[5]+1e6*x[6]+1e7*x[7]+1e8*x[8]+1e9*x[9];
    output;
  end;
end;
run;

NOTE: The data set WORK.PANDIG has 3265920 observations and 1 variables.
NOTE: DATA statement used (Total process time):
      real time           0.29 seconds
      cpu time            0.29 seconds

Die Performance hängt freilich auch von der Hardware ab.

Nachtrag:

Die obige Lösung leistet es sich, 10 % der 3,6 Mio. durchlaufenen Permutationen (nämlich die mit führender Null) zu verwerfen und zu diesem Zweck auch noch 3,6 Mio. IF-Abfragen durchzuführen. Das alles lässt sich vermeiden, indem man die erste Ziffer von 1 bis 9 laufen lässt und jeweils nur die übrigen neun Ziffern permutiert (9*9! = 9*362880 = 3265920).

data pandig(drop=i);
array x[0:8] _temporary_;
do i=1 to 9;
  do _n_=0 to i-1, i+1 to 9;
    x[_n_-(_n_>i)]=_n_;
  end;
  do _n_=1 to 362880;
    call allperm(_n_, of x[*]);
    z=x[0]+10*x[1]+100*x[2]+1e3*x[3]+1e4*x[4]+1e5*x[5]+1e6*x[6]+1e7*x[7]+1e8*x[8]+1e9*i;
    output;
  end;
end;
run;

Die Laufzeit verkürzt sich dadurch jedoch allenfalls marginal.

[AndreasMenrath]

@CKothenschulte: sehr schöne Idee für eine Code Kata. Mir sind damals leider die interessanten Probleme ausgegangen.

Aber wie ich sehe findet die Community weitere Probleme und noch bessere Lösungen. Besten Dank an @FreelanceReinh für die Vorstellung seiner ausgezeichneten Lösung!

[CKothenschulte]

Hallo @FreelanceReinh,

Danke für die tolle Lösung!

Ich bin begeistert. Für mich enthält sie drei wesentliche Punkte:

• Die Schreibweise (z.B.) 1e3 für 1.000 hatte ich vergessen. Nun habe ich sie wieder präsent!
• Öfter mal Arrays nutzen! Ich merke selber, dass ich immer andere Lösungen suche/finde, da mir Arrays in SAS nicht so geläufig sind.
• ALLPERM kann ich noch nicht.

Meine Lösungen spielen definitiv eine Liga tiefer!

Als ich mir die Aufgabe ausgedacht habe, ging es darum, eine übersichtliche Aufgabe für unsere Azubis zu finden, um sie an Schleifen heran zu führen.

Meine erste einfache Lösung geht alle 9.000.000.000 Zahlen durch und prüft zum Schluss die Bedingungen ab.

data PANDIGITAL (drop=a b c d e f g h i j);
/* Pandigital: 10 Stellen mit allen 10 Ziffern (0 bis 9) */
  do a=1 to 9; /* 1.  Stelle keine führende Null, da sonst nur 9 Stellen */
  do b=0 to 9; /* 2.  Stelle */
  do c=0 to 9; /* 3.  Stelle */
  do d=0 to 9; /* 4.  Stelle */
  do e=0 to 9; /* 5.  Stelle */
  do f=0 to 9; /* 6.  Stelle */
  do g=0 to 9; /* 7.  Stelle */
  do h=0 to 9; /* 8.  Stelle */
  do i=0 to 9; /* 9.  Stelle */
  do j=0 to 9; /* 10. Stelle */
    if a ne b and a ne c and a ne d and a ne e and a ne f and a ne g and a ne h and a ne i and a ne j and
       b ne c and b ne d and b ne e and b ne f and b ne g and b ne h and b ne i and b ne j and
       c ne d and c ne e and c ne f and c ne g and c ne h and c ne i and c ne j and
       d ne e and d ne f and d ne g and d ne h and d ne i and d ne j and
       e ne f and e ne g and e ne h and e ne i and e ne j and
       f ne g and f ne h and f ne i and f ne j and
       g ne h and g ne i and g ne j and
       h ne i and h ne j and
       i ne j then do; /* alle Stellen unterschiedlich */
      /* Zusammenbau der Zahl: abcdefghij */
      Ausgabe = a * 1000000000 + b * 100000000 + c * 10000000 + d * 1000000 + e * 100000 + f * 10000 + g * 1000 + h * 100 + i * 10 + j;
      Durch9 = mod(Ausgabe,9); /* immer 0 => alle durch 9 teilbar */
      output;  /* Anzahl: 3.265.920 */
    end;
  end;
  end;
  end;
  end;
  end;
  end;
  end;
  end;
  end;
  end;
run;

Deutlich schneller geht es, wenn man die folgenden Schleifen nur noch durchläuft, wenn es noch mögliche Lösungen gibt.

data PANDIGITAL (drop=a b c d e f g h i j);
/* Pandigital: 10 Stellen mit allen 10 Ziffern (0 bis 9) */
  do a=1 to 9; /* 1.  Stelle keine führende Null, da sonst nur 9 Stellen */
  do b=0 to 9; /* 2.  Stelle */
  if a ne b then
  do c=0 to 9; /* 3.  Stelle */
  if b ne c and a ne c then
  do d=0 to 9; /* 4.  Stelle */
  if c ne d and b ne d and a ne d then
  do e=0 to 9; /* 5.  Stelle */
  if d ne e and c ne e and b ne e and a ne e then
  do f=0 to 9; /* 6.  Stelle */
  if e ne f and d ne f and c ne f and b ne f and a ne f then
  do g=0 to 9; /* 7.  Stelle */
  if f ne g and e ne g and d ne g and c ne g and b ne g and a ne g then
  do h=0 to 9; /* 8.  Stelle */
  if g ne h and f ne h and e ne h and d ne h and c ne h and b ne h and a ne h then
  do i=0 to 9; /* 9.  Stelle */
  if h ne i and g ne i and f ne i and e ne i and d ne i and c ne i and b ne i and a ne i then
  do j=0 to 9; /* 10. Stelle */
    if i ne j and h ne j and g ne j and f ne j and e ne j and d ne j and c ne j and b ne j and a ne j then do;
      Ausgabe = a * 1000000000 + b * 100000000 + c * 10000000 + d * 1000000 + e * 100000 + f * 10000 + g * 1000 + h * 100 + i * 10 + j;
      Durch9 = mod(Ausgabe,9); /* wenn 0 => durch 9 teilbar */
      output;  /* Anzahl: 3.265.920 */
    end;
  end; /* 10. Stelle */
  end; /* 9. Stelle */
  end; /* 8. Stelle */
  end; /* 7. Stelle */
  end; /* 6. Stelle */
  end; /* 5. Stelle */
  end; /* 4. Stelle */
  end; /* 3. Stelle */
  end; /* 2. Stelle */
  end; /* 1. Stelle */
run;

Und dann habe ich nochmal ausprobiert, wie es mit STRING-Funktionen klappt.

data PANDIGITAL (drop=a);
/* Pandigital: 10 Stellen mit allen 10 Ziffern (0 bis 9) */
  do Ausgabe=1023456789 to 9876543210;
   a = put(Ausgabe,10.);
    if min(find(a,'0'),find(a,'1'),find(a,'2'),find(a,'3'),find(a,'4'),
       find(a,'5'),find(a,'6'),find(a,'7'),find(a,'8'),find(a,'9')) ne 0 then
    do; /* alle Stellen unterschiedlich */
      /* Zusammenbau der Zahl: abcdefghij */
      Durch9 = mod(Ausgabe,9); /* immer 0 => alle durch 9 teilbar */
      output;  /* Anzahl: 3.265.920 */
    end;
  end;
run;

Hier benötigt SAS aber deutlich mehr CPU-Zeit, siehe oben.

Also, hoffentlich gibt es bald mal wieder neue Rätsel/Aufgaben!

[FreelanceReinh]

Hallo @CKothenschulte,

freut mich, dass meine Lösung hilfreich war.

Wenn die Verarbeitung von Strings nicht so viel länger dauern würde als die von Zahlen, hätte ich gern die (trotz Exponentialschreibweise) etwas umständlich erscheinende Summe durch einen Aufruf der CATS-Funktion ersetzt. Aber die nachfolgende Codevariante, die die Ziffernkombinationen in eine Character-Variable schreibt, lief ca. fünf- bis sechsmal so lang wie das Original:

data pandigc;
length z $10;
array x[0:9] _temporary_ (0:9);
do _n_=1 to 3628800;
  call allperm(_n_, of x[*]);
  if x[9] then do;
    z=cats(of x[*]);
    output;
  end;
end;
run;