Execute a Markov algorithm: Difference between revisions
Content added Content deleted
m (added whitespace before the TOC (table of contents), added a ;Task: (bold) header and numerous other section headers, added whitespace and highlighting to the task's preamble, changed faux language entries into task preamble (bold) section headers.) |
(→{{header|Go}}: simplify code, include all input data) |
||
Line 1,574: | Line 1,574: | ||
import ( |
import ( |
||
"fmt" |
"fmt" |
||
"regexp" |
|||
"strings" |
"strings" |
||
) |
) |
||
Line 1,580: | Line 1,581: | ||
ruleSet, sample, output string |
ruleSet, sample, output string |
||
} |
} |
||
var testSet []testCase // initialized in separate source file |
|||
func main() { |
func main() { |
||
Line 1,587: | Line 1,586: | ||
var failures bool |
var failures bool |
||
for i, tc := range testSet { |
for i, tc := range testSet { |
||
if r := |
if r, ok := interpret(tc.ruleSet, tc.sample); !ok { |
||
fmt.Println("test", i+1, " |
fmt.Println("test", i+1, "invalid ruleset") |
||
failures = true |
|||
} else if r != tc.output { |
|||
fmt.Printf("test %d: got %q, want %q\n", i+1, r, tc.output) |
|||
failures = true |
failures = true |
||
} |
} |
||
Line 1,595: | Line 1,597: | ||
fmt.Println("no failures") |
fmt.Println("no failures") |
||
} |
} |
||
} |
|||
func interpret(ruleset, input string) (string, bool) { |
|||
if rules, ok := parse(ruleset); ok { |
|||
return run(rules, input), true |
|||
} |
|||
return "", false |
|||
} |
} |
||
Line 1,603: | Line 1,612: | ||
} |
} |
||
var ( |
|||
func ma(rs, s string) string { |
|||
rxSet = regexp.MustCompile(ruleSet) |
|||
// compile rules per task description |
|||
rxEle = regexp.MustCompile(ruleEle) |
|||
ruleSet = `(?m:^(?:` + ruleEle + `)*$)` |
|||
ruleEle = `(?:` + comment + `|` + ruleRe + `)\n+` |
|||
comment = `#.*` |
|||
ruleRe = `(.*)` + ws + `->` + ws + `([.])?(.*)` |
|||
ws = `[\t ]+` |
|||
) |
|||
func parse(rs string) ([]rule, bool) { |
|||
if !rxSet.MatchString(rs) { |
|||
return nil, false |
|||
} |
|||
x := rxEle.FindAllStringSubmatchIndex(rs, -1) |
|||
var rules []rule |
var rules []rule |
||
for _, |
for _, x := range x { |
||
if |
if x[2] > 0 { |
||
rules = append(rules, |
|||
rule{pat: rs[x[2]:x[3]], term: x[4] > 0, rep: rs[x[6]:x[7]]}) |
|||
} |
} |
||
a := strings.Index(line, "->") |
|||
if a == -1 { |
|||
fmt.Println("invalid rule:", line) |
|||
return "" |
|||
} |
|||
pat := line[:a] |
|||
for { |
|||
if pat == "" { |
|||
b := strings.Index(line[a+2:], "->") |
|||
if b == -1 { |
|||
fmt.Println("invalid rule:", line) |
|||
return "" |
|||
} |
|||
a += 2 + b |
|||
pat = line[:a] |
|||
continue |
|||
} |
|||
last := pat[len(pat)-1] |
|||
if last != ' ' && last != '\t' { |
|||
break |
|||
} |
|||
pat = pat[:len(pat)-1] |
|||
} |
|||
rep := line[a+2:] |
|||
for rep > "" && (rep[0] == ' ' || rep[0] == '\t') { |
|||
rep = rep[1:] |
|||
} |
|||
var term bool |
|||
if rep > "" && rep[0] == '.' { |
|||
term = true |
|||
rep = rep[1:] |
|||
} |
|||
rules = append(rules, rule{pat, rep, term}) |
|||
} |
} |
||
return rules, true |
|||
// execute algorithm per WP |
|||
} |
|||
for r := 0; r < len(rules); { |
|||
pat := rules[r].pat |
|||
if f := strings.Index(s, pat); f == -1 { |
|||
r++ |
|||
} else { |
|||
func run(rules []rule, s string) string { |
|||
s = s[:f] + rules[r].rep + s[f+len(pat):] |
|||
step1: |
|||
if rules[r].term { |
|||
for _, r := range rules { |
|||
if f := strings.Index(s, r.pat); f >= 0 { |
|||
s = s[:f] + r.rep + s[f+len(r.pat):] |
|||
if r.term { |
|||
return s |
|||
} |
} |
||
goto step1 |
|||
} |
} |
||
} |
} |
||
return s |
return s |
||
} |
|||
}</lang> |
|||
The rule set source file contains all the strings as literals, packaged into a data structure. It starts like this, |
|||
<lang go> |
|||
package main |
|||
// text all cut and paste from RC task page |
|||
func init() { |
|||
var testSet = []testCase{ |
|||
{`# This rules file is extracted from Wikipedia: |
|||
{ |
|||
`# This rules file is extracted from Wikipedia: |
|||
# http://en.wikipedia.org/wiki/Markov_Algorithm |
# http://en.wikipedia.org/wiki/Markov_Algorithm |
||
A -> apple |
A -> apple |
||
Line 1,675: | Line 1,660: | ||
T -> the |
T -> the |
||
the shop -> my brother |
the shop -> my brother |
||
a never used -> .terminating rule |
a never used -> .terminating rule |
||
`, |
|||
"I bought a B of As from T S.", |
|||
`I bought a B of As from T S.`, |
|||
`I bought a bag of apples from my brother.`, |
|||
{ |
|||
}, |
|||
`# Slightly modified from the rules on Wikipedia |
|||
{`# Slightly modified from the rules on Wikipedia |
|||
A -> apple |
A -> apple |
||
B -> bag |
B -> bag |
||
S -> .shop |
|||
... |
|||
T -> the |
|||
</lang> |
|||
the shop -> my brother |
|||
Compile both files, link, and run. Output: |
|||
a never used -> .terminating rule |
|||
`, |
|||
`I bought a B of As from T S.`, |
|||
`I bought a bag of apples from T shop.`, |
|||
}, |
|||
{`# 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 |
|||
`, |
|||
`I bought a B of As W my Bgage from T S.`, |
|||
`I bought a bag of apples with my money from T shop.`, |
|||
}, |
|||
{`### 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 |
|||
_+_ -> |
|||
`, |
|||
`_1111*11111_`, |
|||
`11111111111111111111`, |
|||
}, |
|||
{`# 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 |
|||
`, |
|||
`000000A000000`, |
|||
`00011H1111000`, |
|||
}, |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
<pre> |
||
validating 5 test cases |
validating 5 test cases |