マジックストリング（魔法の文字列）問題をJavaScriptで解く方法

マジックストリングの問題概要

マジックストリング（魔法の文字列）とは、「1」と「2」だけから構成され、次の性質を持つ特別な文字列です。

この文字列が「マジック（魔法）」と呼ばれるのは、連続する「1」や「2」のかたまり（グループ）ごとの出現回数をつなぎ合わせると、元の文字列そのものが再現されるからです。

文字列 str の最初の部分は次のようになっています。

str = "1221121221221121122……"

str 内の連続した「1」「2」をそれぞれグループに分けると、次のようになります。

1 22 11 2 1 22 1 22 11 2 11 22 ……

さらに、各グループにおける「1」または「2」の出現回数を取り出すと、

1 2 2 1 1 2 1 2 2 1 2 2 ……

となり、この出現回数の並びがまさに元の文字列そのものになっていることが分かります。これがマジックストリングの不思議な性質です。

求められること

整数 num が入力として与えられます。そのうえで、マジックストリング str の先頭 num 文字の中に「1」がいくつ含まれているかを返す関数を実装します。

たとえば、関数への入力が次の場合を考えてみましょう。

const num = 6;

このとき、期待される出力は次のとおりです。

const output = 3;

出力の解説

マジックストリングの最初の6文字は「122112」です。これには「1」がちょうど3つ含まれているため、答えとして 3 を返します。

JavaScriptでの実装例

この問題は、あらかじめ用意したシード文字列をもとに、文字列ポインタを読み進めながら末尾へ文字を追記していくことで効率よく解けます。実際のコードは以下のとおりです。

const num = 6;
const magicalString = (num = 1) => {
    let ind = 12;
    let str = '1221121221221121122';
    while(str.length < num){
        const end = str.substring(str.length - 1) === '2' ? '1' : '2';
        str = parseInt(str.substring(ind, ind + 1)) === 2 ? str + end + end : str + end;
        ind++;
    };
    return (str.substring(0, num).match(/1/g)||[]).length;
};
console.log(magicalString(num));

コードのポイント

• シード文字列： 十分な長さの初期文字列「1221121221221121122」を用意し、そこから生成を続けます。
• 文字の交互追加： 現在の末尾の文字が「2」なら次は「1」を、「1」なら次は「2」を追加候補とすることで、「1」「2」が必ず交互に現れるようにしています。
• 自己参照的な個数決定： ポインタ ind の位置にある数字を読み、「2」なら追加候補を2回、「1」なら1回だけ文字列の末尾へ追記します。これにより、出現回数の並びが文字列自身と一致する性質が保たれます。
• カウント： 最後に、先頭 num 文字を正規表現 /1/g で抽出し、「1」の個数を返します。

実行結果

コンソールには次のように出力されます。

3