How to resolve the algorithm Execute a Markov algorithm step by step in the Tcl programming language
How to resolve the algorithm Execute a Markov algorithm step by step in the Tcl programming language
Table of Contents
Problem Statement
Create an interpreter for a Markov Algorithm.
Rules have the syntax:
There is one rule per line.
If there is a . (period) present before the
Rulesets Use the following tests on entries:
Sample text of: Should generate the output:
A test of the terminating rule Sample text of: Should generate:
This tests for correct substitution order and may trap simple regexp based replacement routines if special regexp characters are not escaped. Sample text of: Should generate:
This tests for correct order of scanning of rules, and may trap replacement routines that scan in the wrong order. It implements a general unary multiplication engine. (Note that the input expression must be placed within underscores in this implementation.) Sample text of: should generate the output:
A simple Turing machine, implementing a three-state busy beaver. The tape consists of 0s and 1s, the states are A, B, C and H (for Halt), and the head position is indicated by writing the state letter before the character where the head is. All parts of the initial tape the machine operates on have to be given in the input. Besides demonstrating that the Markov algorithm is Turing-complete, it also made me catch a bug in the C++ implementation which wasn't caught by the first four rulesets. This ruleset should turn into
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Execute a Markov algorithm step by step in the Tcl programming language
Source code in the tcl programming language
package require Tcl 8.5
if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}
lassign $argv ruleFile inputFile outputFile
# Read the file of rules
set rules {}
set f [open $ruleFile]
foreach line [split [read $f] \n[close $f]] {
if {[string match "#*" $line] || $line eq ""} continue
if {[regexp {^(.+)\s+->\s+(\.?)(.*)$} $line -> from final to]} {
lappend rules $from $to [string compare "." $final] [string length $from]
} else {
error "Syntax error: \"$line\""
}
}
# Apply the rules
set f [open $inputFile]
set out [open $outputFile w]
foreach line [split [read $f] \n[close $f]] {
set any 1
while {$any} {
set any 0
foreach {from to more fl} $rules {
# If we match the 'from' pattern...
if {[set idx [string first $from $line]] >= 0} {
# Change for the 'to' replacement
set line [string replace $line $idx [expr {$idx+$fl-1}] $to]
# Stop if we terminate, otherwise note that we've more work to do
set any $more
break; # Restart search for rules to apply
}
}
#DEBUG# puts $line
}
# Output the processed line
puts $out $line
}
close $out
package require Tcl 8.5
if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}
lassign $argv ruleFile inputFile outputFile
# Read the file of rules
set rules {}
set f [open $ruleFile]
foreach line [split [read $f] \n[close $f]] {
if {[string match "#*" $line] || $line eq ""} continue
if {[regexp {^(.+)\s+->\s+(.*)$} $line -> from to]} {
dict set rules $from $to
} else {
error "Syntax error: \"$line\""
}
}
# Apply the rules in a simplistic manner
set in [open $inputFile]
set out [open $outputFile w]
set data [read $in]
close $in
while 1 {
set newData [string map $rules $data]
if {$newData eq $data} break
set data $newData
}
puts $out $data
close $out
You may also check:How to resolve the algorithm Number reversal game step by step in the Perl programming language
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the dc programming language
You may also check:How to resolve the algorithm Loops/Nested step by step in the C# programming language
You may also check:How to resolve the algorithm Function definition step by step in the МК-61/52 programming language
You may also check:How to resolve the algorithm Hailstone sequence step by step in the Io programming language