Function Implementations
find_rule(input)
function find_rule(input) {
if (!input || input.length === 0) return { prefix: "", repetend: "" };
let minLength = Infinity;
let bestPrefix = input;
let bestRepetend = "";
// Check all possible divisions of the input string
for (let i = 0; i <= input.length; i++) {
const prefix = input.slice(0, i);
const remaining = input.slice(i);
// Find the longest possible repeating pattern in remaining
for (let j = 1; j <= remaining.length; j++) {
const candidate = remaining.slice(0, j);
let valid = true;
// Check if the entire remaining matches repetitions of candidate
for (let k = 0; k < remaining.length; k += j) {
const chunk = remaining.slice(k, k + j);
if (chunk !== candidate.slice(0, chunk.length)) {
valid = false;
break;
}
}
if (valid) {
const totalLength = prefix.length + candidate.length;
if (totalLength < minLength ||
(totalLength === minLength && candidate.length > bestRepetend.length) ||
(totalLength === minLength && candidate.length === bestRepetend.length && candidate < bestRepetend)) {
minLength = totalLength;
bestPrefix = prefix;
bestRepetend = candidate;
}
}
}
}
return { prefix: bestPrefix, repetend: bestRepetend };
}
rule_size(input)
function rule_size(input) {
const { prefix, repetend } = find_rule(input);
return [prefix.length + repetend.length, repetend.length];
}
rule_next_token(input)
function rule_next_token(input) {
const { repetend } = find_rule(input);
if (!repetend) return 'a';
return repetend[0];
}
rule_anti_next_token(input)
function rule_anti_next_token(input) {
const next = rule_next_token(input);
return next === 'a' ? 'b' : 'a';
}
main_function(N)
function main_function(N) {
let result = "";
for (let i = 0; i < N; i++) {
result += rule_anti_next_token(result);
}
return result;
}
Output for N=10: "bbabababab"
DeepSite - 🧬 Remix