Execute a Markov algorithm: Difference between revisions
Content added Content deleted
(Add source for Rust) |
|||
Line 2,696: | Line 2,696: | ||
Under the rules of left 4 registers, under the word has 8 character cells, the alphabet of the digits from 1 to 8. Rules are placed in "123,456", where "123" is a fragment, and "456" is to be replaced, in the registers of the РA to РD. The number of rules is stored in Р0, the initial word is in Р9. Number triggered rule is the last digit registration Р4 (0 to 3), if no rule did not work, the indicator 0, otherwise the current word to be processed. In РE is stored 10. |
Under the rules of left 4 registers, under the word has 8 character cells, the alphabet of the digits from 1 to 8. Rules are placed in "123,456", where "123" is a fragment, and "456" is to be replaced, in the registers of the РA to РD. The number of rules is stored in Р0, the initial word is in Р9. Number triggered rule is the last digit registration Р4 (0 to 3), if no rule did not work, the indicator 0, otherwise the current word to be processed. In РE is stored 10. |
||
=={{header|Nim}}== |
|||
<lang Nim>import strutils, strscans |
|||
type Rule = object |
|||
pattern: string # Input pattern. |
|||
replacement: string # Replacement string (may be empty). |
|||
terminating: bool # "true" if terminating rule. |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func parse(rules: string): seq[Rule] = |
|||
## Parse a rule set to build a sequence of rules. |
|||
var linecount = 0 |
|||
for line in rules.splitLines(): |
|||
inc linecount |
|||
if line.startsWith('#'): continue |
|||
if line.strip.len == 0: continue |
|||
# Scan the line. |
|||
var pat, rep: string |
|||
var terminating = false |
|||
if not line.scanf("$+ -> $*", pat, rep): |
|||
raise newException(ValueError, "Invalid rule at line " & $linecount) |
|||
if rep.startsWith('.'): |
|||
# Terminating rule. |
|||
rep = rep[1..^1] |
|||
terminating = true |
|||
result.add(Rule(pattern: pat, replacement: rep, terminating: terminating)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func apply(text: string; rules: seq[Rule]): string = |
|||
## Apply a set of rules to a text and return the result. |
|||
result = text |
|||
var changed = true |
|||
while changed: |
|||
changed = false |
|||
# Try to apply the rules in sequence. |
|||
for rule in rules: |
|||
if result.find(rule.pattern) >= 0: |
|||
# Found a rule to apply. |
|||
result = result.replace(rule.pattern, rule.replacement) |
|||
if rule.terminating: return |
|||
changed = true |
|||
break |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
const SampleTexts = ["I bought a B of As from T S.", |
|||
"I bought a B of As from T S.", |
|||
"I bought a B of As W my Bgage from T S.", |
|||
"_1111*11111_", |
|||
"000000A000000"] |
|||
const Rulesets = [ |
|||
#................................................ |
|||
"""# This rules file is extracted from Wikipedia: |
|||
# http://en.wikipedia.org/wiki/Markov_Algorithm |
|||
A -> apple |
|||
B -> bag |
|||
S -> shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""", |
|||
#................................................ |
|||
"""# Slightly modified from the rules on Wikipedia |
|||
A -> apple |
|||
B -> bag |
|||
S -> .shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""", |
|||
#................................................ |
|||
"""# BNF Syntax testing rules |
|||
A -> apple |
|||
WWWW -> with |
|||
Bgage -> ->.* |
|||
B -> bag |
|||
->.* -> money |
|||
W -> WW |
|||
S -> .shop |
|||
T -> the |
|||
the shop -> my brother |
|||
a never used -> .terminating rule""", |
|||
#................................................ |
|||
"""### Unary Multiplication Engine, for testing Markov Algorithm implementations |
|||
### By Donal Fellows. |
|||
# Unary addition engine |
|||
_+1 -> _1+ |
|||
1+1 -> 11+ |
|||
# Pass for converting from the splitting of multiplication into ordinary |
|||
# addition |
|||
1! -> !1 |
|||
,! -> !+ |
|||
_! -> _ |
|||
# Unary multiplication by duplicating left side, right side times |
|||
1*1 -> x,@y |
|||
1x -> xX |
|||
X, -> 1,1 |
|||
X1 -> 1X |
|||
_x -> _X |
|||
,x -> ,X |
|||
y1 -> 1y |
|||
y_ -> _ |
|||
# Next phase of applying |
|||
1@1 -> x,@y |
|||
1@_ -> @_ |
|||
,@_ -> !_ |
|||
++ -> + |
|||
# Termination cleanup for addition |
|||
_1 -> 1 |
|||
1+_ -> 1 |
|||
_+_ -> """, |
|||
#................................................ |
|||
"""# Turing machine: three-state busy beaver |
|||
# |
|||
# state A, symbol 0 => write 1, move right, new state B |
|||
A0 -> 1B |
|||
# state A, symbol 1 => write 1, move left, new state C |
|||
0A1 -> C01 |
|||
1A1 -> C11 |
|||
# state B, symbol 0 => write 1, move left, new state A |
|||
0B0 -> A01 |
|||
1B0 -> A11 |
|||
# state B, symbol 1 => write 1, move right, new state B |
|||
B1 -> 1B |
|||
# state C, symbol 0 => write 1, move left, new state B |
|||
0C0 -> B01 |
|||
1C0 -> B11 |
|||
# state C, symbol 1 => write 1, move left, halt |
|||
0C1 -> H01 |
|||
1C1 -> H11""" |
|||
] |
|||
for n, ruleset in RuleSets: |
|||
let rules = ruleset.parse() |
|||
echo SampleTexts[n].apply(rules)</lang> |
|||
{{out}} |
|||
<pre>I bought a bag of apples from my brother. |
|||
I bought a bag of apples from T shop. |
|||
I bought a bag of apples with my money from T shop. |
|||
11111111111111111111 |
|||
00011H1111000</pre> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |