Thema "Betreff: Code Kata: Wonderland number" in CoDe SAS German

Code Kata: Wonderland number

AndreasMenrath — Wed, 14 Nov 2018 09:59:42 GMT

Danke an @CKothenschulte für die letzte Code Kata.

Ich habe mal etwas im Netz gestöbert und bin auf diese schöne Kata hier gestoßen: Wonderland number

Übersetzt lautet die Aufgabe wie folgt. Gesucht wird eine Zahl, die folgende Eigenschaften hat:

sie besteht aus 6 Ziffern
wenn man sie mit 2,3,4,5 oder 6 mutlipliziert, so hat die berechnete Zahl die gleichen Ziffern wie die ursprüngliche Zahl. Der einzige Unterschied besteht in der Position der Ziffern.

Viel Vergnügen bei der Suche nach der Lösung.Natürlich ist wie immer alles an SAS Mitteln erlaubt: Datastep, Makro, proc fcmp, proc lua, usw.

Wer seine Lösung vergleichen möchte oder zu ungeduldig ist, kann hier spicken:

data result;
keep i multiple:;
array multiples[6] $6;
array multiples_sorted[6] $6;
array digits[6] _temporary_;

do i=100000 to 999999 / 6; /* nach der Multiplizierung mit größtem Wert muss die Zahl immer noch 6 stellig sein. Daher größtmöglicher Wert geteilt durch 6 */
    multiples[1] = put(i     , 6.);
    multiples[2] = put(i * 2 , 6.);
    multiples[3] = put(i * 3 , 6.);
    multiples[4] = put(i * 4 , 6.);
    multiples[5] = put(i * 5 , 6.);
    multiples[6] = put(i * 6 , 6.);

    do multi=1 to 6;
      /* Sortierung aller Ziffern in aufsteigender Reihenfolge */
      do digpos=1 to 6;
        digits[digpos] = substr(multiples[multi], digpos,1);
      end;
      call sortn(of digits[*]);
      multiples_sorted[multi] = cats(of digits[*]);
    end;

    /* Vergleich ob alle sortierten Ziffern gleich sind */
    if multiples_sorted[1] = multiples_sorted[2] and
       multiples_sorted[1] = multiples_sorted[3] and
       multiples_sorted[1] = multiples_sorted[4] and
       multiples_sorted[1] = multiples_sorted[5] and
       multiples_sorted[1] = multiples_sorted[6]
    then output;
end;
run;

Betreff: Code Kata: Wonderland number

FreelanceReinh — Thu, 15 Nov 2018 12:49:32 GMT

Hallo @AndreasMenrath,

vielen Dank für die neue Aufgabe.

Hier mein Lösungsvorschlag:

data _null_;
array d[6];
n=100000;
d1=1;
do d2=0 to 6;
  do d3=0 to 9;
    do d4=0 to 9;
      do d5=0 to 9;
        do d6=0 to 9;
          e=0;
          do f=2 to 6 until(e);
            p=f*n;
            do _n_=1 to 6;
              z=mod(p,10);
              e=(z ~in d);
              if e then leave;
              p=(p-z)/10;
            end;
          end;
          if ~e then do;
            put 'Lösung: ' n;
            stop;
          end;
          n+1;
        end;
      end;
    end;
  end;
end;
run;

Typisches Log:

Lösung: 142857
NOTE: DATA statement used (Total process time):
      real time           0.01 seconds
      cpu time            0.01 seconds

Erläuterungen:

Die sechs Ziffern d1, ..., d6 der Lösungskandidaten n (von links nach rechts) werden zu einem Array d zusammengefasst. Ein sinnvoller Suchraum ist {100000, 100001, ..., 166666}, weil die Multiplikation größerer Zahlen mit 6 ein 7-stelliges Ergebnis liefern würde. Daher Startwert n=100000, d1=1 fix und d2 maximal 6 (letzteres formal bis 9 laufen zu lassen, hätte aber keine Nachteile).

Anstatt einer Schleife do n=100000 to 166666; verwende ich geschachtelte Schleifen für die Ziffern d2 bis d6. Dadurch wird der Code zwar länger, aber – so jedenfalls die Absicht – effizienter, weil in dem Array d unmittelbar die Ziffern von n zur Verfügung stehen. Variable e dient als "Exit-Flag", um bei erkennbar ungeeigneten n die Überprüfungen vorzeitig abzubrechen. Vor Beginn der Tests für einen neuen Kandidaten wird sie auf 0 gesetzt. Der Faktor f läuft von 2 bis 6, aber eben mit der Option, im Fall e=1 vorzeitig auszusteigen. Die Ziffern z des Produkts p=f*n werden nacheinander von rechts nach links (also beginnend bei der Einerstelle) durchgegangen und daraufhin überprüft, ob sie im Array d vorkommen. Ist letzteres einmal nicht der Fall, wird e auf 1 gesetzt und die Prüfung des Kandidaten sofort abgebrochen (zunächst durch das LEAVE-Statement und danach durch die UNTIL-Bedingung).

Besteht ein Kandidat alle Tests, ist e=0 (mithin die IF-Bedingung ~e erfüllt), die Lösung wird ausgegeben und der Datastep mit STOP beendet. Ansonsten wird n um 1 inkrementiert (eine Berechnung n=1e5+1e4*d2+1e3*d3+100*d4+10*d5+d6; erübrigt sich) und die Schleifen für d2 bis d6 laufen entsprechend weiter.

Die (teilweise) Zerlegung der Produkte p in einzelne Ziffern erfolgt bewusst rein rechnerisch (Zehnerrest, Division durch 10), um zeitraubende Typumwandlungen und String-Operationen zu vermeiden. So bleibt alles numerisch (bis auf die Ausgabe 'Lösung: ').

Betreff: Code Kata: Wonderland number

AndreasMenrath — Thu, 15 Nov 2018 14:17:29 GMT

Danke @FreelanceReinh für ihre Lösung.

Aus meiner Sicht enthält der Code jedoch einen Bug, da nicht geprüft wird wie häufig eine Ziffer in dem Array vorkommt. Rein zufällig besteht die gesuchte Zahl aus 6 unterschiedlichen Ziffern, daher funktioniert der Code.

Würde eine Ziffer mehrfach vorkommen, würden falsche Ergebnisse ausgegeben werden, da z.B. die beiden Zahlen 112 sowie 122 von ihrem Algorithmus als gleich erkannt werden, obwohl es unmöglich ist durch ein Vertauschen der Ziffern aus der Zahl 112 die Zahl 122 zu machen.

Viele Grüße

Andreas Menrath

Betreff: Code Kata: Wonderland number

FreelanceReinh — Thu, 15 Nov 2018 19:41:26 GMT

Vielen Dank @AndreasMenrath für den guten Hinweis! Dass ich im Programm die Häufigkeiten nicht berücksichtigt habe, liegt vermutlich daran, dass ich die Lösungszahl zunächst mit Papier und Stift ermittelt und dabei bereits früh gesehen hatte, dass überhaupt nur eine Lösung mit sechs verschiedenen Ziffern in Frage kam.

Möglichkeit 1 ist also, diese mathematische Überlegung ebenso vorauszusetzen wie bereits die, dass die Lösung zwischen 100000 und 166666 liegen muss. Der Beweis ist schließlich recht einfach: Die Hunderttausenderziffern der sechs Produkte k*n (k=1, ..., 6), die ja nach Konstruktion des Suchbereichs zwischen 1 und 9 liegen, sind paarweise verschieden, weil f*n−(f−1)*n=n>=100000 für alle f=2, ..., 6 und n im Suchbereich. Nach Voraussetzung müssen sie sämtlich in der gesuchten 6-stelligen Zahl vorkommen.

Möglichkeit 2 ist freilich eine defensivere Programmierung, die auch die Häufigkeiten berücksichtigt:

data _null_;
array d[6];
array h[0:9] _temporary_;
n=100000;
d1=1;
do d2=0 to 6;
  do d3=0 to 9;
    do d4=0 to 9;
      do d5=0 to 9;
        do d6=0 to 9;
          e=0;
          do f=2 to 6 until(e);
            call missing(of h[*]);
            do i=1 to 6;
              h[d[i]]+1;
            end;
            p=f*n;
            do _n_=1 to 6;
              z=mod(p,10);
              h[z]+(-1);
              e=(h[z]<0);
              if e then leave;
              p=(p-z)/10;
            end;
          end;
          if ~e then do;
            put 'Lösung: ' n;
            stop;
          end;
          n+1;
        end;
      end;
    end;
  end;
end;
run;

Neu im Programm ist eine Häufigkeitstabelle in Gestalt des temporären Arrays h, das die Anzahl der Nullen eines Lösungskandidaten in h[0], die Anzahl der Einsen in h[1] usw. speichern wird. Die Tabelle wird jeweils zu Beginn der Überprüfung eines Produkts f*n initialisiert: zunächst auf missing (um ab dem zweiten Durchlauf der "do f=..."-Schleife alte, veränderte Häufigkeiten zu löschen) und anschließend auf die Ziffernhäufigkeiten des aktuellen Kandidaten n. (Dass die Array-Elemente für nicht vorkommende Ziffern missing bleiben, stört nicht.) Die Häufigkeit einer im Produkt f*n vorgefundenen Ziffer z wird in der Tabelle durch Dekrementierung von h[z] um 1 reduziert. (Man beachte, dass "h[z]+(-1)" auch für h[z]=. problemlos funktioniert und mehrfache Dekrementierungen desselben Array-Elements vorkommen können.) Das Kriterium für das Setzen der Ausstiegs-Flag e lautet nun h[z]<0, d. h., im Produkt f*n wurde eine Ziffer häufiger gefunden, als sie in n vorkommt. Zu bedenken ist allerdings noch der mögliche Fall, dass im Produkt eine Ziffer z seltener vorkommt als in n. Dann bleibt h[z]>0, während doch am Ende der "do _n_=..."-Schleife h[k]=0 oder h[k]=. für alle k=0, ..., 9 erfüllt sein muss, damit die Ziffern des Produkts als eine bloße Permutation der Ziffern von n zu erkennen sind. Da aber die Summe der Häufigkeiten h[k] (k=0, ...,9) zu Beginn dieser Schleife gleich 6 war (siehe die sechs Inkrementierungen um +1 nach dem CALL MISSING) und nach vollständigem Durchlauf der Schleife (also ohne vorzeitigen Ausstieg wegen e=1) auch 6 Dekrementierungen um 1 erfolgt sind, kann am Ende der Schleife keine positive Häufigkeit h[z] in der Tabelle stehen bleiben, ohne dass es an anderer Stelle zu einer negativen Häufigkeit und damit zum vorzeitigen Ausstieg gekommen wäre. Daher ist kein zusätzliches Kriterium am Ende der Schleife erforderlich.

Die Laufzeit des modifizierten Programms betrug bei einigen Durchläufen weiterhin 0.01 s, tendierte jedoch häufiger zu 0.03 s.

Betreff: Code Kata: Wonderland number

jh_ti_bw — Fri, 16 Nov 2018 18:23:47 GMT

@AndreasMenrath Vielen Dank für die Kata.

@FreelanceReinh

Ich finde schon, dass man Überlegungen, die man sich zum Problem gemacht hat, in den Code einfließen lassen kann. Man muss es nur dokumentieren, damit andere (und später man selber) nicht glauben es gäbe da noch Logiklücken

Ohne Vorüberlegungen sähe meine Lösung so aus:

/* Brute Force */
/* einzige Optimierung Wertebereichseinschränkung auf 6 stellige Produkte 0.06 s 2496767 loops*/
Data _NULL_;
    limit = int(1000000/6);
    do i = 100000 to limit;
        loops + 1;
         zahl = put(i,6.);
         do j = 2 to 6;
            loops + 1;
            Produkt = put(i * j, 6.);
            do k = 1 to 6;
                loops + 1;
                do l = 1 to 6;
                    loops + 1;
                    if substr(zahl, k, 1) = substr(produkt, l, 1) then do;
                        substr(produkt,l, 1) = " ";
                        leave;
                    end;
                end;
            end;
            if lengthn(Produkt) > 0 then goto nextnumber;
         end;
        put "wonderland number: " i;
nextnumber:
    end;
    put loops=;
run;

/*
wonderland number: 142857
loops=2496767
NOTE: DATA statement used (Total process time):
      real time           0.06 seconds
      cpu time            0.06 seconds
*/

Eine lange Schleife über alle Werte aus dem Zahlenbereich und anschließend eine dreifach verschachtelte Schleife über zwei Strings, um zu prüfen ob die Ziffern alle gleich sind.

Ich habe allerdings auch vorher die Lösung auf Papier gesucht und habe mir folgende Bedingungen überlegt:

    Alle Produkte müssen 6 stellige Zahlen sein ==> Wertebereich der Zahl = 100000 - 166666
    ==> erste Ziffer eine 1
    Keine Ziffer kann doppelt vorkommen, da die Wertebereiche der ersten Ziffer der Produkte nicht überlappen
    ==> Die 0 kommt in der Zahl nicht vor, da die erste Ziffer der Zahl und der Produkte keine 0 sein kann
    Alle Produkte müssen den Teilbarkeitsregeln ihrer Faktoren genügen
    ==> Die Quersumme der Zahl muss durch 3 teilbar sein (Faktor 3)
    ==> Die Zahl muss die Ziffer 5 enthalten (Faktor 5)
    ==> Die letzte Ziffer muss ungerade sein, aber keine 1 (schon belegt) und keine 5 (0 in den Produkten bei Faktor (2, 4, 6))

Data _NULL_;
    
    /* der erste Startwert wurde so gewählt, das die Zahl durch 3 teilbar ist, aber nicht durch 6 */
    /* der by Schritt von 6 behält dann die Bedingung bei */
    /* keine Ziffer kommt doppelt vor, keine Ziffer 0 und eine Ziffer 5 */

    do i = 123459 to 166666 by 6;
        loops + 1;
        if mod(i, 10) not in (3, 7, 9) then continue;
        zahl = put(i, 6.);
        if     index(zahl, "0") then continue; 
        if not index(zahl, "5") then continue;

        /* Jede Zahl nur einmal ?*/
        /* die 1 ist schon gesetzt als erste Ziffer */
        zahlen = "23456789";
        do j = 2 to 6;
            loops + 1;
            pos = index(zahlen,substr(zahl,j,1));
            if pos then substr(zahlen,pos,1) = " ";  /* Ziffer aus dem Vorrat nehmen */
            else goto nextnumber;                    /* Ziffer schon verwendet */
        end;
        
        /* Prüfen auf Bedingung in den Produkten */
        /* jetzt vereinfacht, da keine doppelten mehr vorkommen können */; 
        do j = 2 to 6;
            loops + 1;
            Produkt = put(i * j, 6.);
            if lengthn(compress(zahl,produkt)) ne 0 then goto nextnumber;
        end;
        
        /* Wenn man hier ankommt sind die Bedingungen erfüllt */
        put "wonderland number: " i;
 nextnumber:
    end;
    put loops=;
run;

/*
wonderland number: 142857
loops=13283
NOTE: DATA statement used (Total process time):
      real time           0.00 seconds
      cpu time            0.00 seconds
*/

Die Zahl der Loops ist deutlich heruntergegangen. Ich habe für die Prüfungen der Bedingungen extra Strings genommen, da Stringoperationen auf kurze Strings in SAS sehr schnell sind und einem viel coden ersparen.

Zeitlich ist da nicht mehr viel rauszuholen, auch wenn ab zu eine Zeit von 0.01 s erschien

Weitere Überlegungen zeigen einem dass der Wertebereich weiter eingeschränkt werden kann und die letzte Ziffer eine 7 sein muss

    Die Wertebereiche der ersten Ziffer der Produkte liegt bei Faktor
    -   4 in (4, 5, 6)
    -   5 in (5, 6, 7, 😎
    bei allen anderen Faktoren wird die 5 in der ersten Ziffer nicht erreicht

    Für Faktor 5 ergibt sich ein Wertebereich 100000 - 120000, damit die Bedingung Ziffer 5 ist enthalten erfüllt ist
    Die Kombination der möglichen Ziffern ist 123456 und 123457
    123457 ist nicht durch 3 teilbar
    123456 ist die kleinste darstellbare Zahl und schon außerhalb des Wertebereichs

    Für Faktor 4 ergibt sich ein Wertebereich 125000 - 149999
    Folgende erste Ziffern ergeben
    a) 123567 Quersumme 24 Wertebereich 125000 - 133333
    b) 124568 Quersumme 26 nicht durch 3 teilbar
    c) 124578 Quersumme 27 Wertebereich 140000 - 149999

erste Ziffer 1

a) letzte Ziffer 3 oder 7 ==> 3 geht nicht wegen Faktor 3 (9 nicht enthalten im Set), 7 geht nicht wegen Faktor 2 (4 nicht enthalten im Set)

c) letzte Ziffer 7
   zweite Ziffer 4

Data _NULL_;
    /* 
        Startwert war der erste Wert, bei dem
        - keine 0 vorkam
        - eine 5 vorkam
        - durch 3 teilbar war
        - ersten zwei Ziffern 14 waren
        - letzte Ziffer 7
        - keine Zahl doppelt vorkam
        
        die Schrittweite von 30 gewährleistet die Bedingungen Teilbarkeit durch 3 und letzte Ziffer 7

        dass er dann auch die anderen Bedingungen erfüllte war Zufall
     */
    do i = 142587 to 149853 by 30;
        loops + 1;
        zahl = put(i,6.);
        if Index(zahl, "0" )   then continue;
        if not Index(zahl,"5") then continue;
        
        /* drei Ziffern sind schon festgelegt und brauchen nicht mehr geprüft werden */
        /* der Zahlenbereich der anderen Ziffern ist deutlich geschrumpft */
        zahlen = "258";
        do j = 3 to 5;
            loops + 1;
            pos = index(zahlen,substr(zahl,j,1));
            if pos then substr(zahlen,pos,1) = " ";
            else goto nextnumber;
         end;       

         do j = 2 to 6;
            loops + 1;
            Produkt = put(i * j, 6.);
            if lengthn(compress(zahl,produkt)) ne 0 then goto nextnumber;
         end;
        put "wonderland number: " i;
nextnumber:
    end;
    put loops=;
run;
/*
wonderland number: 142857
loops=364
NOTE: DATA statement used (Total process time):
      real time           0.00 seconds
      cpu time            0.00 seconds
*/

Die Zahl der Loops ist jetzt auf 364 heruntergegangen.

und weil es eine Kata ist gibts auch noch eine SQL-Lösung, die wie ich finde deutlich weniger Erläuterungen braucht, aber in der Laufzeit zurückfällt.

   data t1;
        do i = 2, 3, 4, 5, 6, 7, 8, 9;
            output;
        end;
    run;
    data t2;
        do i = 3, 7, 9;
            output;
        end;
    run;
    Proc sql noprint;
        select
            cats("1", z2.i, z3.i, z4.i, z5.i, z6.i)      as wonderlandNumber
        ,   input (calculated wonderlandNumber, 6.)      as Zahl
        into :wonderlandNumber001 - :wonderlandNumber999
        , :zahl
        from t1 as z2, t1 as z3, t1 as z4, t1 as z5, t2 as z6
        where 
            z2.i NE z3.i AND z2.i NE z4.i AND z2.i NE Z5.i AND z2.i NE z6.i
        AND z3.i NE z4.i AND z3.i NE z5.i AND z2.i NE z6.i
        AND z4.i NE z5.i AND z4.i NE z6.i
        AND z5.i NE z6.i
        AND calculated Zahl BETWEEN 100000 AND 166666                   /* Betrachtungen zu den möglichen Gültigkeitsbereichen             */
        AND ( (z2.i EQ 5) OR (z3.i EQ 5) OR (z4.i EQ 5) OR (z5.i EQ 5) )   /* 5 muss enthalten sein, aber nicht an erster, zweiter oder letzter Stelle */
        AND Mod(sum(1, z2.i, z3.i, z4.i, z5.i, z6.i),3) EQ 0            /* Teilbarkeitsregeln 3 Quersumme muss durch 3 teilbar sein        */
        AND Lengthn(compress(put(calculated Zahl * 2, 6.), calculated wonderlandNumber)) = 0   /* Faktor 2 */
        AND Lengthn(compress(put(calculated Zahl * 3, 6.), calculated wonderlandNumber)) = 0   /* Faktor 3 */
        AND Lengthn(compress(put(calculated Zahl * 4, 6.), calculated wonderlandNumber)) = 0   /* Faktor 4 */
        AND Lengthn(compress(put(calculated Zahl * 5, 6.), calculated wonderlandNumber)) = 0   /* Faktor 5 */
        AND Lengthn(compress(put(calculated Zahl * 6, 6.), calculated wonderlandNumber)) = 0   /* Faktor 6 */
      ;
   
      %put &=SQLOBS.; 
      %put &=wonderlandNumber001;
 
      %put &=SQLOOPS;
      
   
      drop table t1, t2;
      
    quit;
/*
SQLOBS=1
WONDERLANDNUMBER001=142857
SQLOOPS=1960

NOTE: Table WORK.T1 has been dropped.
NOTE: Table WORK.T2 has been dropped.

NOTE: PROCEDURE SQL used (Total process time):
      real time           0.01 seconds
      cpu time            0.01 seconds
*/

Betreff: Code Kata: Wonderland number

mfab — Sun, 18 Nov 2018 21:34:21 GMT

Vielen Dank für diese tolle Code-Kata.

Ich habe mal eine Lösung mit zwei Hash-Objekten erstellt.

- ausgehend vom Suchraum 100000 bis 166666 aufgrund der Aufgabenstellung

- in einem Loop über den Suchraum: Zerlegung der Zahl in Ziffern und Hinzufügen der Ziffern zu einem Hash-Objekt

- in einem Loop über die Multiplikatoren: Zerlegung der Vergleichszahlen (mit 2, 3, 4, 5, 6 multipliziert) in Ziffern und hinzufügen zu einem zweiten Hash-Objekt

-- Abgleich der Hash-Objekte und weitere Verarbeitung (Löschen des zweiten Hash-Objekts oder Abbruch des Vergleichs oder Ausgabe)


data test (keep = i);

 /* Deklarieren von zwei Hash-Objekten für Abgleich
    Multidata = yes, damit jede Ziffer ggf. mehrfach an Hash.Objekt hinzugefügt wird */
 if _n_ = 1 then do;
   declare hash heins(multidata: "yes");
   rc = heins.defineKey('zahl');
   rc = heins.defineDone();
   
   declare hash hzwei(multidata: "yes");
   rc = hzwei.defineKey('zahl');
   rc = hzwei.defineDone();
 end;
  
  /* loop über mögliche Werte mit gegebenen Bedingungen:
     - Zahl ist 6 stellig => daher von 100000
     - Zahl ist 6 stellig und Anzahl Ziffern muss bei Multiplikation mit 6 übereinstimmen
       => daher bis 166666, ansonsten erfolgt ein Überlauf in eine 7-stellige Zahl
          (alternativ bis 999999 durchlaufen; ebenfalls recht performant) */
  do i = 100000 to 166666;
    
    /* Zahl in einzelne Ziffern zerlegen und dem ersten Hash-Objekt hinzufügen */
    do j = 0 to 5;
      zahl = int(mod(i/(10**j),10));
      rc = heins.add();
    end;
  
    /* loop für zweite Zahl, jeweils "mal 2", "mal 3", ... "mal 6" */
    do k = 2 to 6;
        zwei = i * k;
        /* multiplizierte Zahl in Ziffern zerlegen und diese dem zweiten Hash-Objekt hinzufügen */
	    do j = 0 to 5;
	      zahl = int(mod(zwei/(10**j),10));
	      rc = hzwei.add();
	    end;
	    
	    /* Prüfung, ob Hash-Objekte gleich sind (somit Ziffern der beiden Zahlen identisch) */
	    rc = heins.equals(hash: 'hzwei', result: equal);
	    if not equal then leave; /* wenn Ziffern nicht übereinstimmen gleich den Loop verlassen */
	                      else
	                        do;
	                          rc = hzwei.clear(); /* wenn Ziffern übereinstimmen, Hash für nächste Zahl leeren */
	                          if k = 6 then do;   /* wenn auch die Zahl "mal 6" in Ziffern übereinstimmt Ausgabe der Zahl */
	                                          output;
	                                          put "Ergebnis: " i;
	                                        end;
	                        end;
	end;
	/* Hash-Objekte leeren für nächstes i */
    rc = heins.clear();
    rc = hzwei.clear();
  end; /* loop i */

run;

Herzliche Grüße

Michael