@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
*/
