Skip to content

Instantly share code, notes, and snippets.

@jakubpetrik
Last active September 11, 2015 19:49
Show Gist options
  • Save jakubpetrik/d246bbbb2a627e6ed648 to your computer and use it in GitHub Desktop.
Save jakubpetrik/d246bbbb2a627e6ed648 to your computer and use it in GitHub Desktop.
Markov Algorithm in Swift 2.0
/**
http://rosettacode.org/wiki/Execute_a_Markov_algorithm
Create an interpreter for a Markov Algorithm. Rules have the syntax:
<ruleset> ::= ((<comment> | <rule>) <newline>+)*
<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. A ruleset consists of a sequence of rules, with optional comments.
*/
import Foundation
func setup(ruleset: String) -> [(String, String, Bool)] {
return ruleset.componentsSeparatedByCharactersInSet(NSCharacterSet.newlineCharacterSet())
.filter { $0.rangeOfString("^s*#", options: .RegularExpressionSearch) == nil }
.reduce([(String, String, Bool)]()) { rules, line in
let regex = try! NSRegularExpression(pattern: "^(.+)\\s+->\\s+(\\.?)(.*)$", options: .CaseInsensitive)
guard let match = regex.firstMatchInString(line, options: .Anchored, range: NSMakeRange(0, line.characters.count)) else { return rules }
return rules + [(
(line as NSString).substringWithRange(match.rangeAtIndex(1)),
(line as NSString).substringWithRange(match.rangeAtIndex(3)),
(line as NSString).substringWithRange(match.rangeAtIndex(2)) != ""
)]
}
}
func markov(ruleset: String, var input: String) -> String {
let rules = setup(ruleset)
var terminate = false
while !terminate {
guard let i = rules.indexOf ({
if let range = input.rangeOfString($0.0) {
input.replaceRange(range, with: $0.1)
return true
}
return false
}) else { break }
terminate = rules[i].2
}
return input
}
let tests: [(ruleset: String, input: String)] = [
("# This rules file is extracted from Wikipedia:\n# http://en.wikipedia.org/wiki/Markov_Algorithm\nA -> apple\nB -> bag\nS -> shop\nT -> the\nthe shop -> my brother\na never used -> .terminating rule", "I bought a B of As from T S."),
("# Slightly modified from the rules on Wikipedia\nA -> apple\nB -> bag\nS -> .shop\nT -> the\nthe shop -> my brother\na never used -> .terminating rule", "I bought a B of As from T S."),
("# BNF Syntax testing rules\nA -> apple\nWWWW -> with\nBgage -> ->.*\nB -> bag\n->.* -> money\nW -> WW\nS -> .shop\nT -> the\nthe shop -> my brother\na never used -> .terminating rule", "I bought a B of As W my Bgage from T S."),
("### Unary Multiplication Engine, for testing Markov Algorithm implementations\n### By Donal Fellows.\n# Unary addition engine\n_+1 -> _1+\n1+1 -> 11+\n# Pass for converting from the splitting of multiplication into ordinary\n# addition\n1! -> !1\n,! -> !+\n_! -> _\n# Unary multiplication by duplicating left side, right side times\n1*1 -> x,@y\n1x -> xX\nX, -> 1,1\nX1 -> 1X\n_x -> _X\n,x -> ,X\ny1 -> 1y\ny_ -> _\n# Next phase of applying\n1@1 -> x,@y\n1@_ -> @_\n,@_ -> !_\n++ -> +\n# Termination cleanup for addition\n_1 -> 1\n1+_ -> 1\n_+_ ->", "_1111*11111_"),
("# Turing machine: three-state busy beaver\n#\n# state A, symbol 0 => write 1, move right, new state B\nA0 -> 1B\n# state A, symbol 1 => write 1, move left, new state C\n0A1 -> C01\n1A1 -> C11\n# state B, symbol 0 => write 1, move left, new state A\n0B0 -> A01\n1B0 -> A11\n# state B, symbol 1 => write 1, move right, new state B\nB1 -> 1B\n# state C, symbol 0 => write 1, move left, new state B\n0C0 -> B01\n1C0 -> B11\n# state C, symbol 1 => write 1, move left, halt\n0C1 -> H01\n1C1 -> H11", "000000A000000")
]
for (index, test) in tests.enumerate() {
print("\(index + 1):", markov(test.ruleset, input: test.input))
}
/* sample output
1: I bought a bag of apples from my brother.
2: I bought a bag of apples from T shop.
3: I bought a bag of apples with my money from T shop.
4: 11111111111111111111
5: 00011H1111000
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment