• 18 dec 2009
• Markov Algorithm

# 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 status`

and 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
)```