Execute a Markov algorithm: Difference between revisions

{{trans|Nim}}

String pattern

String replacement

L(ruleset) RuleSets

V rules = parse(ruleset)

{{out}}

=={{header|Ada}}==

markov.ads:

package Markov is

Entries : Entry_Array (1 .. Length);

end record;

markov.adb:

function Parse (S : String_Array) return Ruleset is

end Apply;

test_markov.adb:

with Ada.Text_IO.Unbounded_IO;

with Ada.Strings.Unbounded;

end;

end;

Output (rulesX contains the ruleset of above examples and testX the example text):

=={{header|APL}}==

{{works with|Dyalog APL}}

trim←{(~(∧\∨⌽∘(∧\)∘⌽)⍵∊⎕UCS 9 32)/⍵}

rules←(~rules∊⎕UCS 10 13)⊆rules←80 ¯1 ⎕MAP ⍺

}

rules apply ⍵

{{out}}

<pre> 'f:\ruleset1.mkv' markov 'I bought a B of As from T S.'

=={{header|AutoHotkey}}==

; Markov Algorithm.ahk

; by wolf_II

=={{header|BBC BASIC}}==

PRINT FNmarkov("ruleset2.txt", "I bought a B of As from T S.")

PRINT FNmarkov("ruleset3.txt", "I bought a B of As W my Bgage from T S.")

UNTIL EOF#rules% OR done%

CLOSE #rules%

'''Output:'''

<pre>

=={{header|Bracmat}}==

Save the following text to a file "markov.bra":

markov=

{

& ok

| failure;

Test:

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

return 0;

text: I bought a B of As from T S.

markoved: I bought a bag of apples from my brother.

text: 000000A000000

markoved: 00011H1111000

=={{header|C++}}==

Note: Non-use of <code>iswhite</code> is intentional, since depending on the locale, other chars besides space and tab might be detected by that function.

#include <cstdlib>

#include <iostream>

std::cout << output << "\n";

=={{header|CLU}}==

rule = struct[from, to: string, term: bool]

rep = array[rule]

when invalid(s: string): stream$putl(eo, "Parse error: " || s)

end

{{out}}

<pre>$ ./markov ruleset1.mkv "I bought a B of As from T S."

=={{header|Common Lisp}}==

I should mention that this uses the regular expression machinery present in Allegro Lisp but not Common Lisp generally (though there are public domain Lisp libraries).

(defclass markov ()

((rules :initarg :rules :initform nil :accessor rules)))

(setf ret (adjust rule-info ret))

(if (terminal (car rule-info)) (return ret))

Testing:

*rules1*

"# This rules file is extracted from Wikipedia:

00011H1111000

NIL

=={{header|Cowgol}}==

include "strings.coh";

include "malloc.coh";

print(ApplyRules(ReadFile(fname), &patbuf[0]));

{{out}}

<pre>$ ./markov.386 ruleset1.mkv "I bought a B of As from T S."

=={{header|D}}==

{{trans|Perl}}

import std.stdio, std.file, std.regex, std.string, std.range,

std.functional;

writefln("%s\n%s\n", origTest, test);

}

{{out}}

<pre>I bought a B of As from T S.

=={{header|Déjà Vu}}==

This implementation expect the initial text on the command line and the ruleset on STDIN.

]

for line in text:

not (markov-tick) rules

=={{header|EchoLisp}}==

;; rule := (pattern replacement [#t terminal])

(define (task i-string RS)

(markov i-string (parse-rules RS)))

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

<p>Using Partial Active Pattern to simplify pattern matching.</p>

open System.IO

open System.Text.RegularExpressions

|> run

|> printfn "%s"

{{out}}

<pre>H:\RosettaCode\ExecMarkovAlgo>echo I bought a B of As from T S. | Fsharp\RosettaCode\bin\Debug\RosettaCode.exe m1

=={{header|Go}}==

import (

`00011H1111000`,

},

{{out}}

<pre>

=={{header|Groovy}}==

def ruleMap = [:]

rules.eachLine { line ->

text

}]

The test code is below (with the markov rulesets 2..5 elided):

[withInput: { text ->

[hasOutput: { expected ->

def ruleset5 = markovInterpreterFor("""...""")

{{out}}

<pre>

This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.

import Data.Maybe (catMaybes)

import Control.Monad

then let new = reverse before ++ to ++ drop (length from) ahead

in if terminating then new else f rules new

=={{header|Icon}} and {{header|Unicon}}==

rules := loadRules(open(A[1],"r"))

every write(line := !&input, " -> ",apply(rules, line))

if (s == line) | \r.term then return s else line := s

}

Sample runs using above rule sets and test strings:

=={{header|J}}==

markovLexer =: verb define

end.

y

# This rules file is extracted from Wikipedia:

# http://en.wikipedia.org/wiki/Markov_Algorithm

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

I bought a bag of apples from my brother.

'''Discussion''': The J implementation correctly processes all the rulesets. More details are available on the [[Talk:Markov Algorithm#explicit_vs_tacit|the talk page]].

{{trans|D}}

{{works with|Java|7}}

import java.nio.charset.StandardCharsets;

import java.nio.file.Files;

return rules;

}

Output:

=={{header|JavaScript}}==

* Take a ruleset and return a function which takes a string to which the rules

* should be applied.

console.log(markov(ruleset3)('I bought a B of As W my Bgage from T S.'));

console.log(markov(ruleset4)('_1111*11111_'));

Output:

<pre>I bought a bag of apples from my brother.

'''Preliminaries'''

def deregex:

reduce ("\\\\", "\\*", "\\^", "\\?", "\\+", "\\.", "\\!", "\\{", "\\}", "\\[", "\\]", "\\$", "\\|",

def rules: $markov_rules | readRules;

"^ *(?<period>[.]?) *(?<rule>.*)" as $pattern

| reduce $rules[] as $rule ([];

| " \(.)\n=>\(applyRules( parseRules( $rules[$ix] ) ))\n" ;

{{out}}

'''Module''':

struct MarkovRule{F,T}

end

'''Main''':

let rulesets = @.("data/markovrules0" * string(1:5) * ".txt"),

println("Transformed:\n", MarkovAlgos.apply(ruletest[i], rules))

end

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

import java.io.File

println("$origTest\n$test\n")

}

{{out}}

=={{header|Lua}}==

function normalize(str)

local result = str:gsub("(%p)", "%%%1")

do_markov(grammar3, text2, 'I bought a bag of apples with my money from T shop.')

do_markov(grammar4, text3, '11111111111111111111')

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Module[{terminating = False, output = text,

rules = StringCases[

output = StringReplace[output, rule[[1]] -> rule[[2]]];

If[! rule[[3]], terminating = False]; Break[]], {rule, rules}]];

Example:

#

# state A, symbol 0 => write 1, move right, new state B

# state C, symbol 1 => write 1, move left, halt

0C1 -> H01

Output:

<pre>"00011H1111000"</pre>

=={{header|МК-61/52}}==

КИП4 [x] П7 Вx {x} П8

ИП8 ИПE * П8 {x} x=0 08

ИП3 ИПE / [x] П3

x=0 22

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}}==

type Rule = object

for n, ruleset in RuleSets:

let rules = ruleset.parse()

{{out}}

I'm not familiar with string processing, or parsing, so there are probably better ways to express this in OCaml. One might be with the mikmatch library which allows pattern-matching with regexps. Here I've only used the OCaml stdlib...

let try_finally x f g =

try let res = f x in g x; res

print_endline (run rules (input_line stdin));

translate ()

With the above compiled to an executable 'markov', and the five rule-sets in files, strings are accepted on stdin for translation:

This program expects a source file as an argument and uses the standard input and output devices for the algorithm's I/O.

open my $source, '<', $ARGV[0] or die "I couldn't open \"$ARGV[0]\" for reading. ($!.)\n";

my @rules;

and ($terminating ? last OUTER : redo OUTER);}}

=={{header|Phix}}==

<span style="color: #008080;">procedure</span> <span style="color: #000000;">markov</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">rules</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">input</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">subs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">reps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>

"""</span>

<span style="color: #000000;">markov</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ruleset5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"000000A000000"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"00011H1111000"</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|PHP}}==

function markov($text, $ruleset) {

foreach ($conf AS $id => $rule) {

echo 'Ruleset ', $id, ' : ', markov($rule['text'], $rule['rule']), PHP_EOL;

{{out}}

=={{header|PicoLisp}}==

(use (@A @Z R)

(let Rules

(T (= "." (cadr (setq R @)))

(append @A (cddr R) @Z) )

Output:

<pre>: (markov "r1" "I bought a B of As from T S.")

Module lambda can be found there : http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/lambda.pl

:- use_module(library(lambda)).

replacement([X | R]) --> [X], {X \= '\n'}, replacement(R).

replacement([]) --> [].

Code to test :

:- use_module(library(lambda)).

writeln(B),

writeln(R).

Output :

<pre> ?- markov.

=={{header|PureBasic}}==

The GUI used here allows a ruleset to be loaded from a text file or manually added one rule at a time. Symbol input can be tested anytime by selecting 'Interpret'.

pattern.s

replacement.s

EndSelect

Until isDone

Sample output from loading Ruleset 1 and interpreting a symbol:

<pre>Comment: "# This rules file is extracted from Wikipedia:"

The example gains flexibility by not being tied to specific files. The functions may be imported into other programs which then can provide textual input from their sources without the need to pass 'file handles' around.

def extractreplacements(grammar):

== '11111111111111111111'

assert replace(text4, extractreplacements(grammar5)) \

=={{header|Racket}}==

The <tt>Markov-algorithm</tt> for a set of rules returns a function which maps from a string to string and can be used as a first-class object. Rules are represented by abstract data structures.

#lang racket

(let loop ([x x0] [fx (f x0)])

(if (equal? x fx) fx (loop fx (f fx)))))

Example of use:

> (define MA

(Markov-algorithm

> (MA "I bought a B of As from T S.")

"I bought a bag of apples from T shop."

===The source reader===

To read from a file just replace <tt>with-input-from-string</tt> ==> <tt>with-input-from-file</tt>.

;; the reader

(define (read-rules source)

(define (read-Markov-algorithm source)

(apply Markov-algorithm (read-rules source)))

Examples:

(define R3 (read-Markov-algorithm "

# BNF Syntax testing rules

0C1 -> H01

1C1 -> H11"))

> (R3 "I bought a B of As W my Bgage from T S.")

"I bought a bag of apples with my money from T shop."

> (R5 "000000A000000")

"00011H1111000"

=={{header|Raku}}==

Add --verbose to see the replacements step-by-step.

token TOP {

^ [^^ [<rule> | <comment>] $$ [\n|$]]* $

say "starting with: $start_value";

say run(:$ruleset, :$start_value, :$verbose);

=={{header|REXX}}==

Code was added to the REXX example to optionally list the contents of the ruleset and/or the Markov entries.

<br>Also, blank lines in the ruleset were treated as comments.

parse arg low high . /*allows which ruleset to process. */

if low=='' | low=="," then low=1 /*Not specified? Then use the default.*/

@.r=linein(rFID); if tellR then say 'ruleSet' ?"."left(r,4) '───►' @.r

end /*r*/ /* [↑] read and maybe echo the rule. */

Some older REXXes don't have a &nbsp; '''changestr''' &nbsp; BIF, so one is included here &nbsp; ──► &nbsp; [[CHANGESTR.REX]].

<br><br>

=={{header|Ruby}}==

{{works with|Ruby|1.8.7}}

ruleset.each_line.inject([]) do |rules, line|

if line =~ /^\s*#/

end

input_data

'''Test:'''

# This rules file is extracted from Wikipedia:

# http://en.wikipedia.org/wiki/Markov_Algorithm

EOS

{{out}}

=={{header|Rust}}==

#[derive(Clone, Debug)]

}

}

=={{header|Scala}}==

{{works with|Scala|2.8}}

object MarkovAlgorithm {

println(algorithm(args(1)))

}

Script-style, and more concise:

if (argv.size != 2 ) error("Syntax: MarkovAlgorithm inputFile inputPattern")

println(argv(1))

Sample outputs:

The following implementation uses several string-related procedures provided by SRFI-13 [http://srfi.schemers.org/srfi-13/srfi-13.html].

(define split-into-lines

(lambda (str)

rules))

(loop (cdr remaining) result)))))))

=={{header|SequenceL}}==

import <Utilities/Sequence.sl>;

replaceSubString(str, original, new, n + 1);

=={{header|SNOBOL4}}==

Note that the run-time data is immediately after the "end" label. This works with CSNOBOL4, on a Unix (or Unix-like) platform.

The Markov rules are actually compiled into the program after parsing, and are then directly executed (self-modifying code).

#!/bin/sh

exec "snobol4" "-r" "$0" "$@"

000000A000000

END

=={{header|Swift}}==

{{trans|Ruby}}

func setup(ruleset: String) -> [(String, String, Bool)] {

}

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.5}}

if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}

lassign $argv ruleFile inputFile outputFile

puts $out $line

}

In the case where there are no terminating rules and no overlapping issues, the following is an alternative:

if {$argc < 3} {error "usage: $argv0 ruleFile inputFile outputFile"}

lassign $argv ruleFile inputFile outputFile

}

puts $out $data

=={{header|VBScript}}==

====Implementation====

class markovparser

end function

end class

=====Invocation=====

dim m1

set m1 = new markovparser

m5.ruleset = fso.opentextfile("busybeaver.tur").readall

wscript.echo m5.apply("000000A000000")

=====Output=====

I bought a bag of apples from my brother.

I bought a bag of apples from T shop.

11111111111111111111

00011H1111000

=={{header|Wren}}==

{{libheader|Wren-ioutil}}

{{libheader|wren-pattern}}

import "/pattern" for Pattern

System.print("%(origTest)\n%(test)\n")

ix = ix + 1

{{out}}

=={{header|zkl}}==

if(vm.numArgs>1) lines=vm.arglist; // lines or object

ks:=L(); vs:=L();

}while(go);

text

"# http://en.wikipedia.org/wiki/Markov_Algorithm",

"A\t->\tapple", "B -> bag", "S -> shop", "T -> the",

"the shop -> my brother", "a never used -> .terminating rule");

ruleSet.println();

{{out}}

<pre>

I bought a bag of apples from my brother.

</pre>

T("# Slightly modified from the rules on Wikipedia",

"A -> apple", "B -> bag", "S -> .shop", "T -> the",

"W -> WW", "S -> .shop", "T -> the",

"the shop -> my brother", "a never used -> .terminating rule") :

{{out}}

<pre>

</pre>

For the next two tasks, read the rule set from a file.

{{out}}

<pre>