Markov = {
const algorithm = structure => (start, rules, options={}) => {
const normalized_union_rules = rules.map(rule_or_set => Array.isArray(rule_or_set) ? rule_or_set : [rule_or_set]);
let {step_limit, filter_matches} = Object.assign({
step_limit: 1000,
filter_matches: ({rule, match}) => true,
}, options);
let result = [start];
let clean_rules = 0;
while (step_limit && clean_rules < rules.length) {
const last = result[result.length - 1];
const matches = normalized_union_rules[clean_rules].flatMap(
rule => [...structure.matches(last, rule)].map(
match => ({rule, match})
)
).filter(filter_matches);
if (matches.length === 0) {
clean_rules++;
} else {
step_limit--;
clean_rules = 0;
let overlaps = 0;
let acc = last;
const touched_nodes = {};
while (overlaps < 10) {
let _match = null;
let weight_sum = 0;
for (let m of matches)
weight_sum += m.rule.weight_frac || 1;
weight_sum *= Math.random();
for (let m of matches) {
weight_sum -= m.rule.weight_frac || 1;
if (weight_sum <= 0) {
_match = m;
break;
}
}
if (_match === null)
throw "Weighted random method failure. weird float bug?";
const match = _match;
let touches = false;
const matchnodes = structure.matchnodes(match.match);
for (let nodename of matchnodes)
touches = touches || touched_nodes[nodename];
if (touches) {
overlaps++;
break; // while(overlaps < ...
}
for (let nodename of matchnodes)
touched_nodes[nodename] = true;
acc = structure.apply(acc, match.rule, match.match);
}
result.push(acc);
}
}
return result;
};
// Strings: variable length sequences of code points
const string_ops = {
matches: function* (str, rule) {
let i = str.indexOf(rule.from);
while (i !== -1) {
yield i;
i = str.indexOf(rule.from, i + 1);
}
},
matchnodes: match => [0], // Because length changes, just make everything overlap
apply: (last, rule, match) => `${last.slice(0, match)}${rule.to}${last.slice(match + rule.from.length)}`,
};
// Fixed Graphs: Arbitrary graphs structures where the only changing thing is the node states, not connectivity.
const fixed_graph_ops = {
matches: function*(graph, rule) {
function* rec(graph, first_key, rule_from) {
if (graph[first_key].state !== rule_from[0])
return;
if (rule_from.length === 1) {
yield [];
return;
}
for (let neighbor of graph[first_key].edges)
for (let m of rec(graph, neighbor, rule_from.slice(1)))
yield [neighbor, ...m];
}
if (rule.from.length !== rule.to.length) throw `Expected ${rule.from} to be the same length as ${rule.to}`;
for (let k in graph)
for (let m of rec(graph, k, rule.from))
yield [k, ...m];
},
matchnodes: match => match,
apply: (last, rule, match) => {
const result = JSON.parse(JSON.stringify(last));
match.forEach((key, index) => {result[key].state = rule.to[index];});
return result;
},
};
return {
algorithm,
string: algorithm(string_ops),
string_ops,
fixed_graph: algorithm(fixed_graph_ops),
fixed_graph_ops,
};
}