0123456789012345678901234567890123456789012345678901234567890123456789012345_80|
-----------------------------------------------------------------------
J typische Loesung fuer das SEND+MORE=MONEY Problem aus PC NEWS 49,
Sept. 1996, Seite 55, Karl Stipek: "Rekursion in Pascal, C und BASIC"
von Joachim Hoffmann, JoHo@magnet.at
-----------------------------------------------------------------------
In J ist es sinnvoller

 SEND
 MORE
 ----
MONEY

als homogenes Gleichungssystem, mit G,H,I,J als Uebertraege zu schreiben:

   S  E  N D  M  O R  Y   G   H   I   J   

1  0  1  0 1  0  0 0 _1 _10   0   0   0  (D+E  )=Y+10*G => 0=D+E  -Y-10*G
2  0 _1  1 0  0  0 1  0   1 _10   0   0  (N+R+G)=E+10*H => 0=N+R+G-E-10*H
3  0  1 _1 0  0  1 0  0   0   1 _10   0  (E+O+H)=N+10*I => 0=E+O+H-N-10*I
4  1  0  0 0  1 _1 0  0   0   0   1 _10  (S+M+I)=O+10*J => 0=S+M+I-0+10*J
5  0  0  0 0 _1  0 0  0   0   0   0   1       J =M      => 0=J-M    

Damit man in diesem unterbestimmten Geichungssystem die unabhaengigen
Variablen von den abhaengigen unterscheiden kann, normiert man es mittels
Gauss'scher Elimination. 
Die fuehrenden Einser in jeder Zeile zeigen auf die unabhaengigen (SENOM),
DRY und GHIJ sind die abhaengigen. 

   unabhaengig       abhaengig (vom Programmierer)   
   S E  N  O M   D R  Y  G   H   I   J 

1  1 0  0 _1 1   0 0  0  0   0   1 _10
2  0 1 _1  1 0   0 0  0  0   1 _10   0
3  0 0  1  0 0   1 1 _1 _9 _10   0   0
4  0 0  0  1 0   0 1  0  1  _9 _10   0
5  0 0  0  0 1   0 0  0  0   0   0  _1

Indem fuer die abhaengigen Variablen Werte ausgewaehlt und in das 
Glsys. eingesetzt werden, koennen die unabhaengigen bestimmt werden.
Der Vorteil dieser Methode ist, dass die moeglichen Kombinationen
auf ein Minimum eingeschraenkt werden. DRY koennen jeweils Werte von
0 bis 9 einnehmen, aber GHIJ jeweils nur 0 oder 1.
Es sind daher  16000=(10^3)*(4^2) Moeglichkeiten zu ueberpruefen, im 
Gegensatz zu 3628794=(!10)-(!10-7) unter der Beruecksichtigung, dass
M=1 ist, wovon hier keine Gebrauch gemacht wird.
Ein weiterer Vorteil dieser Loesung ist, dass man ALLE moeglichen
Loesungen geliefert bekommt. Die Loesungen, bei denen keine Ziffer
zweimal verwendet wird, koennen leicht selektiert werden.

     result=: SOLVE''
                            NB. nimm die letzten 10 Zeilen
    _10 TAKE OPEN 2 FROM result 
09221=8229+0992
09332=8339+0993
09443=8449+0994
09554=8559+0995
09665=8669+0996
09776=8779+0997
09887=8889+0998
09998=8999+0999
00109=0019+0090
10109=9019+1090
                            NB. fuehre die letzten 10 Zeilen aus
   EXECUTE _10 TAKE OPEN 2 FROM result 
1 1 1 1 1 1 1 1 1 1

   OPEN _1 FROM result      NB. Oeffne die letzte Schachtel
10652=9567+1085             NB. Maximum ohne doppelte Ziffern
11099=9900+1199             NB. Maximum mit doppelten Ziffern
 

   OPEN COUNT each result   NB. zaehle die Elemente jeder Schachtel
  25    NB. Loesungen ohne doppelte Ziffern
1130    NB. Loesungen mit doppelten Ziffern
   2    NB. ist die Abzahl der Maxima, trivial


NB. ==== Beginn der Skript-Datei MatMoney.JS ===========================

NB.
NB.
NB.  Matrix Loesung fuer SEND+MORE=MONEY Problem
NB.  - Version 3
NB.  - Datum: Freitag, 11.10.96
NB.  - Noch zu tun: * Variablen selektieren
NB.                 * Gleichungssystem automatisch generieren
NB.                 * Gauss Eliminator
NB.                 

PAIRS    =: ,@,.         NB. Paaren= aufreihen nach annaehen  
TEXTYFY  =: NOT&' '@:":         NB. ohne_Leerzeichen nach deaktivieren

NB. nur Zeilen mit ausschliessl. positiven Ziffern selektieren
PositiveDigits=: AND/@(0&<: AND <:&9)rowwise COPY RIGHT 

X   =: +/ . *                       NB. Matrizenprodukt= summe . mal
f   =: {:@] * {.@] { [              NB. Hilfsverb zum Mult. von Matrizenzeilen
F   =: [: +/ (1:,{:@]) * (}:@] { [) NB. Hilfsverb zum Mult. von Matrizenzeilen          
g   =: {.@]                         NB. Hv.: erstes Element aus Rechts         
TAU =: E1=: <@] C. [                NB. AusTAUschen von Matrizenzeilen
MUL =: E2=: f`g`[}                  NB. MULtiplizieren einer Zeile mit Konstante
AMU =: E3=: F`g`[}                  NB. Zeile(1) + Zeike(2)*Konstante(3)
NB. ChangeCOlumns, Spalten einer Matrix vertauschen
CCO =: (BOX@RIGHT C. i.@{:@$@[) FROM rowwise LEFT 


NB. ............................................................................
NB. Jetzt kommt das wichtigste:
NB. SOLVE ist das Hauptprogramm, das wichtigste Verb in SOLVE ist TRY.

SOLVE=: 3 : 0
txt =: 'MONEY=SEND+MORE'
cols=: 'SENDMORYGHIJ'
    NB. Eingabe des Gleichungssystems als geschachtelte Liste
    NB. sollte eigentlich automatisch aus txt generiert werden 
mat =: 0 0 0 1 0; 1 _1 1 0 0; 0 1 _1 0 0; 1 0 0 0 0; 0 0 0 1 _1 
mat =: mat,0 0 1 _1 0; 0 1 0 0 0; _1 0 0 0 0; _10 1 0 0 0; 0 _10 1 0 0
mat =: mat,0 0 _10 1 0; 0 0 0 _10 1
mat =: TRANSPOSE OPEN mat     NB. geschachtelte Liste oeffnen=> Matrix

NB. "haendisches" Normieren der Matrix, Gausssche Elimination
mat =: TAU&3 4  AMU&3 2 _1  AMU&3 1 _1  AMU&2 3 1  TAU&1 2  TAU&0 3  mat
mat =: CCO&5 3  TAU&3 4     MUL&4 _1    MUL&3 _1  mat
cols=: (<5 3)C. cols          NB. Vertausche Variable(column) 5. mit 3.

dep  =: 5 CDROP  mat          NB. Abhaengiger Teil des Gleichungsystems
indep=: 5 CTAKE  mat          NB. Unabhaengiger Teil des Gleichungsystems(5x5)
TRY  =: %.&indep@:(-@(dep&X)) NB. Verb TRY setzt abhaengige Vars. ein (dep&X),
                              NB. Rechnet die unabh. Variablen (%.&indep) aus
                              NB. %. ist der Gleichungsloeser
all2p4=: ANTIBASE2 i. 2^4     NB. GHIJ: Alle Komb. von 0 1 in 4-er Gruppen 
                              NB. #: uebersetzt 0 1 2...14 15 ins Binaersystem
all2  =: ,/ ,"0/~ i.10        NB.  RY: alle Ziffern-Arrangements in 2-er Gruppen
all3  =: ,/ all2 ,"1 0/ i.10  NB. DRY: alle Ziffern-Arrangements in 2-er Gruppen
all   =: ,/ all3 ,"1/ all2p4  NB. Alle 1600 Kombiantionen der abhaengigen Variabeln
                              NB. Das wichtigste kommt jetzt:
res=: TRY"1  all              NB. Einsetzen und unabhaengige Vars. bestimmen
                              NB. 1600x5 Matrix mit allen Loesungen fuer die 
                              NB. unabhaengigen


NB. Jetzt werden die Zeilen die nur positive Ziffern enthalten selektiert
NB. Als Ergebnis erhaelt man alle Kombinationen fuer alle acht Buchstaben 
res0 =: PositiveDigits res ,. 3{."1 all

res  =: TEXTYFY"1 res0       NB. Zahlen in Texte ohne Leerzeichen umwandeln
chars=: _4 DROP cols         NB. Ohne Hilsvariablen GHIJ
res  =: chars PAIRS"1 res    NB. Buchstaben-Zahlen-Paare fuer's austauschen
res  =: res charsub"1 txt    NB. Ersetzen der Buchstaben durch Zahlen

NB. Wenn Kernmenge gleich der Urmenge, dann keine doppelten Ziffern
boo=. (COUNT@NUB MATCH COUNT)rowwise res0  NB. bool'sche Liste als Maske
uniques=. boo COPY res               NB. Loesungen ohne doppelte Ziffern
doubles=. ((NOT boo)COPY res)        NB. Loesungen mit doppelten Ziffern

NB. selektiert groesste Loesung aus Matrix mit den Loesungen in den Zeilen
MAXIMUM=. (RIGHT INDEXOF MAX)@:EXECUTE@(5&CTAKE)  FROM  RIGHT

result=. uniques ( LEFT ; RIGHT ; MAXIMUM@LEFT ,: MAXIMUM@RIGHT) doubles   

NB. Das Ergebnis ist eine geschachtelte Liste mit 3 Schachteln
NB.  1.) Loesungen ohne doppelte Ziffern 
NB.   2.) Loesungen mit doppelten Ziffern
NB.    3.) die maximalen Loesungen aus 1.) und 2.)
)
NB.............................................................................

NB. Aufruf des Hauptverbs SOLVE mit leerem Argument

NB. result=: SOLVE''

NB. The End
NB.                                                            JoHo

NB. ........... Anhang mit Hilfsverben ..............................
NB. charsub ist ein standard Hilfsverb zum Ersetzen
NB. von Buchstaben in einem Text
charsub=:  3 : 0
NB. characterpairs charsub data
NB. For example:
NB.    '-_$ ' charsub '$123 -456 -789'
NB.  123 _456 _789
NB. Use <rplc> for arbitrary string replacement.
:
'ft'=. ((#x.)$0 1)<@,&a./.x.
t {~ f i. y.
)


NB.  Hier werden Namen fuer die Symbole der J Stammverben vergeben,
NB.  um den Code fuer den Anfaenger leserfreundlich zu gestalten.

LEFT   =: [     NB. Identitaetsverb: Ergebnis ist linkes  Argument
RIGHT  =: ]     NB. Identitaetsverb: Ergebnis ist rechtes Argument
COUNT  =: #     NB. Anzahl der Elemente im rechten Argument
COPY   =: #     NB. Einser in links nehmen entsprechende Elemente aus rechts
FROM   =: {     NB. Index links aus Array rechts
 TAKE  =: {.    NB. Nehmen
 DROP  =: }.    NB. n Elemente loeschen  
CTAKE  =: {."1   NB. ColumnTake=Spalten nehmen
CDROP  =: }."1   NB. ColumnDrop=Spalten loeschen  
NOT    =: -.    NB. logisch NICHT
AND    =: *.    NB. logisch UND
NUB    =: ~.    NB. Kernmenge= keine Doppelten= nur Unikate
MATCH  =: -:    NB. Test auf Identitaet
LINK   =: ;     NB. Zwei Nomen verbinden => geschachtelte Liste
OPEN   =: >     NB. oeffnet geschachtelte Liste zur Matrix
BOX    =: <     NB. schachtelt sein rechtes Argument
MAX    =: >./    NB. Maximum einer Liste
INDEXOF  =: i.    NB. Indizes von rechts in links
ANTIBASE2=: #:    NB. konvertiert Dezimalzahl in Binaerzahl
TRANSPOSE=: |:    NB. Zeilen mit Spalten vertauschen=Transponieren
rowwise  =: "1     NB. Adverb: etwas zeilenweise anwenden
EXECUTE  =: ".      NB. Ausfueren (eines Textes)



