Execute a Markov algorithm

This page uses content from Wikipedia. The original article was at Markov_algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Execute a Markov algorithm
You are encouraged to solve this task according to the task description, using any language you may know.

Create an interpreter for a Markov Algorithm. Rules have the syntax:

<comment> ::= # {<any character>}
<rule> ::= <pattern> <whitespace> -> <whitespace> [.] <replacement>
<whitespace> ::= (<tab> | <space>) [<whitespace>]

There is one rule per line. If there is a . present before the <replacement>, then this is a terminating rule in which case the interpreter must halt execution.

There are two tests you can make:

# 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

If you input "I bought a B of As from T S." this code should output "I bought a bag of apples from my brother."
If you use these set of rules:

# Slightly modified from the rules on Wikipedia
A -> apple
B -> bag
S -> .shop
T -> the
the shop -> my brother
a never used -> .terminating rule

If you input "I bought a B of As from T S." this code should output "I bought a bag of apples from T shop." This one tests that terminating rules work.

Ruby

Works with: Ruby version 1.8.7

<lang Ruby>raise "Please input an input code file, an input data file, and an output file." if ARGV.size < 3

rules = File.readlines(ARGV[0]).inject([]) do |rules, line|

 if line =~ /^\s*#/
   rules
 elsif line =~ /^(.+)\s+->\s+(\.?)(.*)$/
   rules << [$1, $3, $2 != ""]
 else
   raise "Syntax error: #{line}"
 end

end

File.open(ARGV[2], "w") do |file|

 file.write(File.read(ARGV[1]).tap { |input_data|
   while (matched = rules.find { |match, replace, term|
     input_data[match] and input_data.sub!(match, replace)
   }) and !matched[2]
   end
 })

end</lang>

Tcl

Works with: Tcl version 8.5

<lang tcl>package require Tcl 8.5 if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"} lassign $argv ruleFile inputFile outputFile

1. 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 equal "." $to] [string length $from]

   } else {

error "Syntax error: \"$line\""

   }

}

1. 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 stop fl} $rules { # If we match the 'from' pattern... if {[set idx [string first $from $line]] < 0} { continue }

# 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 if {$stop} { set any 0 break } else { set any 1 } }

   }

   # Output the processed line
   puts $out $line

} close $out</lang>

J

This example is incorrect. Please fix the code and remove this message. Details: Quick & dirty solution, see discussion of gaps

Solution:<lang j>require'strings regex'

NB. Lex a Markov program markovLexer =: verb define rules =. LF cut TAB&=`(,:&' ')}y rules =. a: -.~ (dltb@:{.~ i:&'#')&.> rules 0 _1 {"1 '\s+->\s+' (rxmatches rxcut ])S:0 rules )

NB. Given ruleset and target string, output NB. result. markov =: markovLexer@[ stringreplace^:_ ]

NB. Same as above, but output all intermediate NB. evaluations markovDebug =: markovLexer@[ stringreplace^:a: ]</lang>

Example:<lang j> m1 =. noun define # 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 )

  m1 markov 'I bought a B of As from T S.' 

I bought a bag of apples from my brother.

  m1 markovDebug '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 the shop. I bought a bag of apples from my brother.</lang> Discussion: This solution implemented in 20 seconds and doesn't fully implement a Markov algorithm. More details on the talk page.