- 18 dec 2009
- Markov Algorithm
Contents
Origin
Bron asked for a tacit solution of Rosetta problem.
Here a solution is presented.
Prerequisites
From replace in Essays/Substring Replacement I first built
rplf=: 4 : 0 NB. replace first; x and y are interchanged compared with replace
'p q'=. x
j=. p (#@] (]`($@0:)@.=) 1 i.~E.) y
if. ''-:j do. y return. end.
d=. p-&#q
k=. (j+(0>.-d)*i.#j)+/i.#q
select. *d
case. 1 do. (0 (j+/(#q)+i.d)}1$~#y) # q k}y
case. 0 do. q k}y
case. _1 do. q k} (0 (d{."1 k)}1$~(#y)+(#j)*|d) #^:_1 y
end.
)but this could be done (simpler? and) tacitly by
rplf=:[: ; [ {:@[`(#@] -.~ ] i. ,&.>@{.@[)`]} ]</.~ [:(# i.@#) #@] ([ ]`[@.(= {.) ] , (- +/)) #@>@{.@[ ,~ 1 i.~ >@{.@[ E. ]
NB. replaces in y the first occurrence of ,>{.x by >{:x(since my 26" monitor my oneliners grow longer.)
Test cases
From Rosetta problem
Ruleset1=: 0 : 0 A -> apple B -> bag S -> shop T -> the the shop -> my brother a never used -> .terminating rule ) String1=: 'I bought a B of As from T S.' Result1=: 'I bought a bag of apples from my brother.' Ruleset2=: 0 : 0 A -> apple B -> bag S -> .shop T -> the the shop -> my brother a never used -> .terminating rule ) String2=: 'I bought a B of As from T S.' Result2=: 'I bought a bag of apples from T shop.' Ruleset3=: 0 : 0 A -> apple WWWW -> with Bgage -> ->.* B -> bag ->.* -> money W -> WW S -> .shop T -> the the shop -> my brother a never used -> .terminating rule ) String3=: 'I bought a B of As W my Bgage from T S.' Result3=: 'I bought a bag of apples with my money from T shop.' Ruleset4=: 0 : 0 _+1 -> _1+ 1+1 -> 11+ 1! -> !1 ,! -> !+ _! -> _ 1*1 -> x,@y 1x -> xX X, -> 1,1 X1 -> 1X _x -> _X ,x -> ,X y1 -> 1y y_ -> _ 1@1 -> x,@y 1@_ -> @_ ,@_ -> !_ ++ -> + _1 -> 1 1+_ -> 1 _+_ -> ) String4=: '_1111*11111_' Result4=: '11111111111111111111' Ruleset5=: 0 : 0 A0 -> 1B 0A1 -> C01 1A1 -> C11 0B0 -> A01 1B0 -> A11 B1 -> 1B 0C0 -> B01 1C0 -> B11 0C1 -> H01 1C1 -> H11 ) String5=: '000000A000000' Result5=: '00011H1111000' Ruleset=:Ruleset1;Ruleset2;Ruleset3;Ruleset4;Ruleset5 Strings=:String1;String2;String3;String4;String5 Results=:Result1;Result2;Result3;Result4;Result5
Solution
The main verb has the form 'x V0 ^:_ y' where x is the ruleset and y is the string.
Here V0 looks for the first match and executes the replacement in the form 'V1/ x JOIN y' .
JOIN glues the reverse of x to y , such that the rules are applied in the approperiate order.
It goes without saying that one has to keep some status infomation with the string.
Layout of nouns
A rule is an item of the ruleset and has the form 'k; pattern; replacement' , where k=0 if the rule is a terminator and k=1 otherwise.
The string y is extended to 'p;q;y' where
p=0 iff (and only if) the string is terminated,
p=1 iff is not yet processed within V1 and
p=2 iff is already processed within V1 .
q=1 if the rule applied did not alter the stringa and q=0 otherwise.
Initializing
The rules are given in the form
Ruleset1=: 0 : 0 A -> apple B -> bag S -> shop T -> the the shop -> my brother a never used -> .terminating rule )
The verb initrls brings the ruleset in the right form and initstr does so with the string.
replace is from Essays/Substring Replacement.
initrls=: 3 : 0
((1;[,])`(0;(,}.&.>))@.('.'={.@>@]))/("1) _2[\". ''')',~'(''',(}: y replace ' -> ' ;''';''') replace LF;'''),','('''
)
initstr=: 3 : '1;1;y'
initrls Ruleset1
+-+------------+----------------+
|1|A |apple |
+-+------------+----------------+
|1|B |bag |
+-+------------+----------------+
|1|S |shop |
+-+------------+----------------+
|1|T |the |
+-+------------+----------------+
|1|the shop |my brother |
+-+------------+----------------+
|0|a never used|terminating rule|
+-+------------+----------------+
Housekeeping
After every execution of V0 one has p=2 and this has to be reset to p=1 for the next execution, This is done in JOIN which becomes
jn=: |.@[ , (0 <&.> {.@])`0:`]} NB. joins |.x and y; resets {.y to <1 if 0<>{.y
(initrls Ruleset1) jn initstr String1
+-+------------+----------------------------+
|0|a never used|terminating rule |
+-+------------+----------------------------+
|1|the shop |my brother |
+-+------------+----------------------------+
|1|T |the |
+-+------------+----------------------------+
|1|S |shop |
+-+------------+----------------------------+
|1|B |bag |
+-+------------+----------------------------+
|1|A |apple |
+-+------------+----------------------------+
|1|1 |I bought a B of As from T S.|
+-+------------+----------------------------+V1 in 'V1/ x jn y' is only to be executed if p=1 , so '2|p' times.
Apart from that, only the first pattern found has to be replaced, reason why rplf , see Prerequisites, is used.
Moreover, one has to determine whether a match was found and this is done by 'y -: x V1 y' . Altogether we get
rnr=: ] (>@{.@[ ; (>@{:@[ -: ]) ; ]) }.@[ rplf^:((2 | >@{.@])`(>@{:@])) ] NB. replace / no replace
NB. no replace if 0 2 e.>{.y
NB. output is ({.y);(no replace done); {:y replaced or not Based on the nature of the rule, terminating or not, and the first 2 indicators of the output of rnr , the final status of the string has to be determined.
sts=: (2 *&.> {.@[)`(0 { ])@.([: > 1 { ])`0:`]} NB. determines new statusand concluding V1 and V0 become
ma=:[: ({.@[ sts rnr)/ jn
MA=:[: ;@{: ma^:_
Testing
Results -: (initrls&.> Ruleset) MA&.> initstr&.> Strings 1
Explicit
The excplicit solution in the above way is much easier to comprehend
MAex=:4 : 0
z=. y
z0=. ''
tx=. # x NB. tx = tally x
nt=. 1 NB. nt = not terminated
while. nt *. z0 ~:&< z do. NB. while not terminated and string is changed
nr=. 1 NB. nr = no replacement yet
k =. 0 NB. k = index in x
z0=. z
while. (nr=1) *. k<tx do. NB. while not replaced and not all rules applied
z1=. (}.k { x) rplf z NB. first occurence of pattern of k{x is replaced
if. z1 ~:&< z do. NB. if string is changed
nr=. 2 NB. nr = replacement executed
z =. z1
nt=. >{.k { x NB. nt agrees with rule applied
end.
k=. k+1
end.
end.
z
)
Results -: (initrls&.> Ruleset) MAex&.> Strings
1
Collected definitions
rplf=:[: ; [ {:@[`(#@] -.~ ] i. ,&.>@{.@[)`]} ]</.~ [:(# i.@#) #@] ([ ]`[@.(= {.) ] , (- +/)) #@>@{.@[ ,~ 1 i.~ >@{.@[ E. ]
NB. replaces in y the first occurrence of ,>{.x by >{:x
initrls=: 3 : 0
((1;[,])`(0;(,}.&.>))@.('.'={.@>@]))/("1) _2[\". ''')',~'(''',(}: y replace ' -> ' ;''';''') replace LF;'''),','('''
)
NB. needed to bring the ruleset in the proper form.
initstr=: 3 : '1;1;y'
NB. idem for the string
jn=: |.@[ , (0 <&.> {.@])`0:`]}
NB. joins |.x and y; resets {.y to <1 if 0<>{.y
rnr=: ] (>@{.@[ ; (>@{:@[ -: ]) ; ]) }.@[ rplf^:((2 | >@{.@])`(>@{:@])) ]
NB. replace / no replace
NB. no replace if 0 2 e.>{.y
NB. output is ({.y);(no replace done); {:y replaced or not
sts=: (2 *&.> {.@[)`(0 { ])@.([: > 1 { ])`0:`]}
NB. determines new status
ma=:[: ({.@[ sts rnr)/ jn
MA=:[: ;@{: ma^:_
MAex=:4 : 0 NB. explicit
z=. y
z0=. ''
tx=. # x NB. tx = tally x
nt=. 1 NB. nt = not terminated
while. nt *. z0 ~:&< z do. NB. while not terminated and string is changed
nr=. 1 NB. nr = no replacement yet
k =. 0 NB. k = index in x
z0=. z
while. (nr=1) *. k<tx do. NB. while not replaced and not all rules applied
z1=. (}.k { x) rplf z NB. first occurence of pattern of k{x is replaced
if. z1 ~:&< z do. NB. if string is changed
nr=. 2 NB. nr = replacement executed
z =. z1
nt=. >{.k { x NB. nt agrees with rule applied
end.
k=. k+1
end.
end.
z
)