jsfiddle n-ary gray codes toy

gray_code_toy.js

const unindent = (strings, ...values) => {
  // Quick and not so dirty unindented template strings.
  // Handles tabs very roughly if they are present.
  // The very first line is always left as is if not entirely whitespace,
  // and removed otherwise.

  const matchLine = line => {
    const {groups} =
      /^(?<line>(?<indent>[\t ]*)(?<nonws>[^\n]*)\n?)(?<tail>.*)$/s.exec(line);
    return {
      line: groups.line,
      indent: groups.indent.length,
      hasNonWS: !!groups.nonws,
      hasNewline: groups.line.endsWith('\n'),
      tail: groups.tail,
    };
  };

  const shortestIndent = (() => {
    const [SKIP, LINE_START] = ['SKIP', 'LINE_START'];

    let state = {tag: SKIP};
    let indent = Infinity;
    for (let str of strings) {
      if (state.tag === LINE_START) {
        indent = Math.min(indent, state.indent);
        state = {tag: SKIP};
      }

      while (str) {
        const match = matchLine(str);
        switch (state.tag) {
          case SKIP:
            if (match.hasNewline) {
              state = {tag: LINE_START, indent: 0};
            }
            break;

          case LINE_START:
            // Known invariant here: state.indent === 0
            state = {tag: LINE_START, indent: match.indent};
            if (match.hasNonWS) {
              indent = Math.min(indent, match.indent);
              state = {tag: SKIP};
            }
            if (match.hasNewline) {
              state = {tag: LINE_START, indent: 0};
            }
            break;
        }
        str = match.tail;
      }
    }
    return indent === Infinity ? 0 : indent;
  })();

  const fixedStrings = (() => {
    const [START, SKIP, LINE_START] = ['START', 'SKIP', 'LINE_START'];
    let state = START;
    const result = [];
    for (let str of strings) {
      const builder = [];

      while (str) {
        const match = matchLine(str);
        switch (state) {
          case START:
            if (!match.hasNewline || match.hasNonWS) {
              builder.push(match.line);
            }
            state = match.hasNewline ? LINE_START : SKIP;
            break;

          case SKIP:
            builder.push(match.line);
            if (match.hasNewline) state = LINE_START;
            break;

          case LINE_START:
            if (match.line.length <= shortestIndent && match.hasNewline) {
              builder.push('\n');
            } else {
              builder.push(match.line.substring(shortestIndent));
            }
            if (!match.hasNewline) state = SKIP;
            break;
        }
        str = match.tail;
      }
      result.push(builder.join(''));
    }
    return result;
  })();

  return String.raw({raw: fixedStrings}, ...values);
};

const nats = function*() {
  let i = 0; while (true) yield i++;
};

const zip = function*(...iterators) {
  while (true) {
    const items = Array(iterators.length);
    for (const [i, it] of iterators.entries()) {
      const item = it.next();
      if (item.done) return;
      items[i] = item.value;
    }
    yield items;
  }
};

const take = function*(n, iterator) {
  // FIXME: This careless implementation will always discard one extra item from
  // the iterator.
  let i = 0;
  for (const item of iterator) {
    if (i++ >= n) return;
    yield item;
  }
};

const reverse = reversible => ({
  ...reversible,
  fwd: reversible.bwd,
  bwd: reversible.fwd,
});

const mk_base = size => ({
  size,
  fwd: function*() {
    for (let i = 0; i < size; ++i) yield i.toString(size);
  },
  bwd: function*() {
    for (let i = size - 1; i >= 0; --i) yield i.toString(size);
  },
});

const initial = {
  fwd: () => [''],
  bwd: () => [''],
};

const iterate = (accumulated, base) => {
  const fwd = function*(fast_forward = false) {
    let suffix_toggle = accumulated;
    let it = base.fwd();
    if (fast_forward) {
      it.next();
      suffix_toggle = reverse(suffix_toggle);
    }

    for (const prefix of it) {
      for (const suffix of suffix_toggle.fwd()) {
        yield prefix + suffix;
      }
      suffix_toggle = reverse(suffix_toggle);
    }
  };

  return {
    fast_forward: () => fwd(true),
    fwd,
    bwd: function*() {
      let suffix_toggle = base.size % 2 == 0 ? accumulated : reverse(accumulated);
      for (const prefix of base.bwd()) {
        for (const suffix of suffix_toggle.fwd()) {
          yield prefix + suffix;
        }
        suffix_toggle = reverse(suffix_toggle);
      }
    },
  };
};

const gray = function*(base_size) {
  const base = mk_base(base_size);
  let accumulator = iterate(initial, base);
  yield* accumulator.fwd();
  while (true) {
    accumulator = iterate(accumulator, base);
    yield* accumulator.fast_forward();
  }
};

const base_from = function*(base, from) {
  for (let i = 0; i < base; ++i) {
    yield ((i + from) % base).toString(base);
  }
};

const alt_base = (size, from=0) => function*() {
  yield* base_from(size, from);
  return alt_base(size, (from + size - 1) % size);
};

const alt_iterate = function*(accumulated, base, skip_init=true) {
  const base_iter = base();
  if (skip_init) {
    // Skip the first digit from base, since it was already traversed
    base_iter.next();
  }
  let base_current = base_iter.next()
  while (!base_current.done) {
    const accumulated_iter = accumulated();
    let accumulated_current = accumulated_iter.next();
    while (!accumulated_current.done) {
      yield base_current.value + accumulated_current.value;
      accumulated_current = accumulated_iter.next();
    }
    accumulated = accumulated_current.value;
    base_current = base_iter.next();
  }
  return () => alt_iterate(accumulated, base_current.value, false);
};

const alt_gray = function*(base_size) {
  const base = alt_base(base_size);
  let accumulator_iter = base();
  while (true) {
    let accumulator_current = accumulator_iter.next();
    while (!accumulator_current.done) {
      yield accumulator_current.value;
      accumulator_current = accumulator_iter.next();
    }
    accumulator_iter = alt_iterate(accumulator_current.value, base);
  }
};

const sleep = delay => new Promise(resolve => setTimeout(resolve, delay));

// HTML setup: <pre id="output"></pre>
// `gray` implements the rather classical (binary- or not) reflected gray code
// `alt_gray` implements another gray code that is cyclic even in odd bases,
// it's probably been invented before, I don't know its name though.
(async() => {
  const output = document.getElementById("output");
  const base = 3, min_digits = 4;
  for (const [i, g, a] of zip(nats(), gray(base), alt_gray(base))) {
    output.innerText = unindent`
      base${base}: ${i.toString(base).padStart(min_digits, '0')}
      gray${base}: ${g.padStart(min_digits, '0')}
      altg${base}: ${a.padStart(min_digits, '0')}
    `;
    await sleep(50);
  }
})();