オフラインリアルタイムどう書くE23に参加しました

オフラインリアルタイムどう書くE23
問題

アルゴリズム系の勉強会に参加したのは初めてで大変勉強になりました。
制限時間内に解けなかった & みなさんの解説も半分くらいしか理解できなくてくやしかったので動くまで実装してみました。

配列にすべての結果を展開して調べる

function transform(src, commands, index = 0) {
  // state 0: -, 1: ／, 2: ＼
  const rules = {
    a: [0, 1, 2, 0],
    b: [0, 1, 0, 2, 0]
  }

  let result = [];
  src.forEach((state) => {
    rules[commands[index]].forEach((transition) => {
      result.push((state + transition) % 3);
    });
  });

  // recursive
  if (commands[index + 1]) {
    result = transform(result, commands, index + 1);
  }

  return result;
};

function solve(input) {
  const [target, commands] = input.split(',');
  const states = transform([0], commands);

  if (states.length < target) return 'x';
  return ['0', '+', '-'][states[target -1]];
}

この方法だと配列の要素数が増えすぎて、61問目以降 ATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory というエラーが出てしまいました。

実行時間は１〜６０までで 5006.676ms かかってました。

解説を参考に実装

解説
問題を作成した方の解説を参考に傾きを知りたい線分のみ計算するよう下記のように実装しました。

const rules = {
  a: [0, 1, 2, 0],
  b: [0, 1, 0, 2, 0]
};

function checkState(targetPos, commands) {
  let curPos = targetPos;
  let state = 0;
  let count = 1;

  commands.split('').reverse().forEach((command) => {
    let index = (curPos % rules[command].length) - 1;
    if (index < 0) index = rules[command].length - 1;

    state += rules[command][index];
    curPos = Math.ceil(curPos / rules[command].length);
    count *= rules[command].length;
  });

  return count < targetPos ? 3 : state % 3;
}

function solve(input) {
  return ['0', '+', '-', 'x'][checkState(...input.split(','))];
}

与えられたルール(ex. ab) の後ろの傾きから順に足していくようにしました。

6,abというinputが与えられた場合
bのときの線分は[01020][01020]...といった感じに5x個になるので、対象の線分(6番目)は6 % 5 => 1番目という風に導きました。
aの対象の線分は6 / 5（bのlength）を繰り上げて2、2 % 4(aのlength) =>2番目と導きます。
b [01020]の1番目 => 0
a [0120]の２番目 => 1
を合わせた状態1が対象の線分の傾きになります。

実行速度

ひとつの線分の傾きしか計算しなくなったので66問すべての実行時間は1.762msになりました。

余談

速度が速くなったので、６７問目に300桁のルールを与えてみました

test( "1000000000000000000000000000000000000000000,babbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbabbabbbbbbab", "+" );

実行速度にばらつきはありますが1.947ms前後で計算できてました。

上記の実装はgithubにあげました。