NB. Script MONEYREC3.JS
NB. Version 3
NB. ............................................................
NB. Rekursiv: 
NB. MONEY=SEND+MORE
NB. 10652=9567+1085            NB. Maximum ohne doppelte Ziffern
NB. 11099=9900+1199            NB. Maximum mit doppelten Ziffern    
NB. ............................................................

to   =: [ + i.@>:@-~      NB. 2 to 6 => 2 3 4 5 6
check=: *./@:".@:}.      NB. drop first line and execute each line      
show =: (1!:2)&2          NB. show on screen  
fmt  =: (0 1 1)&":

define_globals=: 3 : 0
NB. defined global variables for  
NB. permute and permute_rec_pascal  
NB. the right argument y. is 'MONEY=SEND+MORE'
NB. the optional left argument is a boxed list with allowed values
(<0 to 9) define_globals y.
:
txt=: y.                           NB. 
variables=: /:~ (~.txt)-.'=*+-%^'  NB. extract variables and sort them
permutations=: (#variables)#0  NB. this is the global permutation variable
used  =: 10#0           NB. this boolean list indicates, if a digit is used
result=: ,:txt                 NB. initialize result as matrix with one row
max   =: # variables           NB. max is tally of variables 
permusets=: max $ x.           NB.  allowed values
to=: [ + i.@>:@-~          NB. 2 to 6 => 2 3 4 5 6
NB.      allowed values for S   E   N   D   M   0   R   Y
NB. permusets  =: to/each 1 9;0 9;0 9;0 9; 1 ;0 9;0 9;0 9  
NB. permusets  =: to/each 5 9;5 7;3 7;6 9; 1 ;0 2;6 9;0 3
getpermuset=: >@{&permusets    NB. get values for variable i

NB. find all indices of x. in y.
NB. result is a boxed list, each box contains all occurences 
NB. of each atom in x., a box may also be empty
NB.  inxin=: Decrement@nozero each@Box rowwise@:Transpose@Find"0 1 
inxin     =:(<:@(-.&0)&.>)@(<"1)@:|:@:(* >:@i.@#)@E."0 1  
partitions=: ;@:(# each)@] # i.@#@]

NB. boxed list with multiple indices of each variable in txt
NB. , e.g. E has 3 occurrences in txt
indices=: variables inxin txt    
blowup =: partitions indices       NB. how the boxed list is partitioned
indices=: ; indices                NB. indices is now a simple list

replace=: indices}&txt@(blowup&{)  NB. replace variables in txt by
text-digits
execute=: ".           NB. execute a text,e.g.: execute 56328=1234+5672'
textify=: -.&' '@":              NB. list of digits=>text 
                                 NB. and delete the blanks
empty  =: (0 0$0)"_              NB. returns empty matrix => no effect
quote  =: (''''&,)@(,&'''')      NB. append left and right singl quotes

NB. append a solution to global result
solution=: execute@:('result=: result,'&,)@quote  
testit=:(empty`solution@.execute)@:replace@:textify@:".@('permutations'"_)
permute =: testit`(] substitute"0 getpermuset)@. (max&>)
empty''                         NB. return empty result
)





NB. substitutes digits for i-th char and calls recursively permute
NB. x. substitute y. => value y. is written at postion x. (i) of
NB.  global list permutations (is b in original Pascal program)
NB. We are forced to use direct definition because of global assignments.
substitute=: 4 : 0
i=. x.                          NB. because   
if. -.y.{used do.
 permutations=: y. i}permutations NB. write digit to i-th pos of
permutations  
 used        =: 1 y.}used         NB. mark this digit as used
 permute i+1                      NB. !!! the recursive call !!!
 used=:0 y.}used                  NB. unuse digit y.
end.
empty''
)

NB. solve equatation using partly functional J style 
NB. e.g.: (0 to 9) solve_rec_j 'CC=BA+AB'

solve_rec_j=: 4 : 0
(boxopen x.) define_globals y.
permute  0 NB.<:#variables             NB. permute positions 7 to 0
(];<:@{.@$;check) result
)


NB. =====================================================================
NB. === Pascal-style loop-recursion of send+more=money problem ==========
NB. e.g. permute_rec_pascal 0  start is 0 because of 0-origin

permute_rec_pascal=: 3 : 0             NB. x. is i.th variable
i=. y.
vals=. getpermuset i                   NB. get all allowed digits for i
 whilst. 0~:#vals=.}.vals do.          NB. loop over all digits for i
    val=.{.vals                        NB. current value for variable
    if. -.val{used do.                 NB. exit if digit is already used
    permutations=: val i}permutations  NB. set i-th position to val
    used        =: 1 val}used          NB. mark this digit as used
      if. i < max-1 do.                NB. if not last variable, 
                                       NB. 0-origin!
      permute_rec_pascal i+1         NB.   recursive call 
      else.                          NB. else
      NB. replace variables in txt by digits => '10652=9567+1085'
      sol=. replace textify permutations 
      
          if. execute sol do.        NB. test if permutation is solution
          NB. show sol                NB. display number on screen
          result=:result,sol         NB. global result   
          end.                         
      end.                           NB. end if 
    used=: 0 val}used     NB. now we have all permuted=>free digit i    
    end.
 end.                                NB. end whilst
)


NB. solve equatation using pascal style recursion
NB. e.g.: (0 to 9) solve_rec_p 'CC=BA+AB'

solve_rec_p=: 4 : 0  
(boxopen x.) define_globals y.
permute_rec_pascal 0              NB. 
(];<:@{.@$;check) result
)


NB. verb to compare two vers
NB. eg.: fmt statistics each 'permute 0';'permute_rec_pascal 0' 

NB.=================================================================

statistics=:3 : 0
(<0 to 9) define_globals 'CCD=AB+BA'     NB. 'MONEY=SEND+MORE'
usedtime=:timex y. 
boo=. *./ ". }. result
description=.  ;: 'usedtime result'
fmt ('';y.), description,. usedtime;< (];<:@{.@$;check) result
)
