Пишемо модель кубика Рубіка у 10 рядків JavaScript коду

💡 Усі статті, обговорення, новини про Front-end — в одному місці. Приєднуйтесь до Front-end спільноти!

Якось, ще на першому курсі вишу, вигадав собі задачку — написати солвер кубика Рубіка, хоча до того навіть не тримав ніколи його в руках... Солвер я написав, за пів року, з перервами, 99 рядків коду на C. Але то не так цікаво. Найцікавіша тут підзадача: як взагалі представити кубик Рубіка у комп’ютерній програмі? Перетворення матриць? Складна структура даних? Масиви, вектори, таблиці..? Насправді все доволі просто. Тож, пройшло 15 років — саме час згадати й описати один цікавий спосіб зрозуміло та покроково.

Що таке модель кубика Рубіка?

Модель, а точніше, мінімальна модель класичного кубика Рубіка — це структура даних, що відображає його стан, та одна функція (метод) оберту грані, тобто функція двох аргументів: номеру грані, та кількості обертів її на 90°.

Для класичного варіанту цього достатньо: все, що дозволено робити — це повертати грані (оберт середнього шару — те ж саме, що оберт двох паралельних йому граней в протилежну сторону), за годинниковою стрілкою чи проти — не має значення, поворот в одну сторону еквівалентно трьом в іншу.

Бажано, щоб моделлю було зручно і просто користуватись (якщо задача, наприклад, написати солвер), тобто: знаходити протилежну даній грань, кутові, середні, сусідні елементи прилеглих граней і таке інше.

Починаємо...

Перше, і найпростіше, що спадає на думку — пронумерувати елементи грані по колу (за годинниковою стрілкою):

По-перше, вже видно, як в цьому випадку виглядатиме структура даних: масив розмірністю 6✕9, тип — не важливий, ціле число, байт тощо (це наші кольори):

let cube = [...Array(6)].map((_, i) => Array(9).fill(i))
/*
[
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [1, 1, 1, 1, 1, 1, 1, 1, 1],
  ...
  [5, 5, 5, 5, 5, 5, 5, 5, 5]
]
*/

По-друге, легко знаходити елементи: всі кутові — це всі парні індекси (за виключенням останнього, восьмого), а всі елементи, що посередині ребра — це всі непарні. Це розподілення, на кутові та середні, часто використовується в алгоритмах збірки.

По-третє, найголовніше, оберт грані реалізується простим зміщенням значень вектора по два кроки: (0, 1, 2, ..., 6, 7, 8) ➞ (6, 7, 0, ..., 4, 5, 8) ➞ (4, 5, 6, ..., 2, 3, 8) і так далі.

Тут треба зауважити, що останній елемент (на грані — центральний) ми не переміщаємо.

Насправді можна взагалі не зберігати центральні елементи, оскільки вони незмінні, в цьому випадку кубик можна представити масивом 6✕8. Але це не завжди зручніше.

Тепер можна написати нашу першу ітерацію функції оберту грані:

let rotate = (f, t) => {
  while (t--) cube[f].unshift(...cube[f].splice(-3, 2))
}

де f — номер грані, t — кількість обертів на 90° за годинниковою стрілкою (нуль, або будь-яке натуральне число).

Прилеглі грані та суміжні елементи

Далі — цікавіше. Крім 8 власних елементів даної грані потрібно «обертати» 12 суміжних елементів чотирьох прилеглих граней. Наскільки це складно зробити?

Інтуїція підказує, що оскільки кубик Рубіка — симетрична річ, то можливо є така послідовність a, b, c, d індексів елементів на суміжних з даною гранях, яка була б однакова для кожної з граней?

Перевіримо. Нехай на грані за a слідує b (хоча можна спробувати й іншу букву). Нагадую, що нумеруємо за годинниковою стрілкою:

Тоді, можемо розставити індекси на суміжних з лівою гранях:

Ми бачимо, що на нижній грані «зустрілися» d та c. Тобто ми отримали наступну послідовність індексів на грані: a, b, d, c. Просто розставимо цю послідовність на всіх шести гранях (це можна зробити, тому що у нас вже з кожної сторони є хоча б по одній букві):

Фантастика! Все зійшлося. Кожна грань має одну і ту саму послідовність індексів власних елементів — a, b, d, c, та одну і ту саму послідовність індексів кутових елементів прилеглих граней — a, b, c, d.

Тобто, наш кубик складається з шести однакових фігур. Замість a підставляємо, наприклад, нуль. Фігура виглядатиме так:

а кожний наступний індекс на одиницю більше (звісно по модулю 8):

Виявляється, що треба зовсім небагато ускладнити нашу функцію оберту, а саме — зробити обмін значень трійок послідовних елементів між чотирма прилеглими гранями. Напишемо готову функцію:

let rotate = (f, t) => {
  while (t--) {
    cube[f].unshift(...cube[f].splice(-3, 2))
    for (let i = 3; i; i--)
      for (let j = 0; j < 3; j++)
        [ cube[M[f][i]][(N[i] + j) % 8], cube[M[f][i - 1]][(N[i - 1] + j) % 8] ] =
        [ cube[M[f][i - 1]][(N[i - 1] + j) % 8], cube[M[f][i]][(N[i] + j) % 8] ]
  }
}

де N — масив [0, 2, 6, 4] (тобто послідовність a, b, c, d), та M — масив 6✕4 номерів чотирьох прилеглих до кожної із шести граней.

Лишилось тільки пронумерувати грані та записати масив суміжності M.

Таблиця суміжних граней

Звичайно, можна пронумерувати грані будь-яким чином і записати у масив 6✕4. Але задача була зробити модель якомога коротшою. Можливо і тут вдасться знайти симетрію та замість масиву написати коротку функцію? Спробуємо.

Помітимо, що букви a знаходяться одна навпроти одної для всіх протилежних граней. Це підказує ідею — пронумерувати такі грані парами: 0–1, 2–3 і т. д. В цьому випадку, функція знаходження протилежної сторони — це функція одного оператора: f ^ 1.

Далі, відносно грані з номером 1 першу прилеглу грань (зі сторони букви a) іменуємо номером 2. Те саме робимо для протилежної — грані номер 3:

Тож маємо наступну таблицю суміжності граней:

Складемо рядки попарно:

Знайдемо різницю (по модулю 6) між парними рядками:

Отже бачимо, що ця таблиця має значну надлишковість, а це означає, що вона може бути стиснута, або навіть зведена до коротшої функції. Ось ця функція:

let side = (f, i) => ([5, 3, 4, 2][i] + f + (4 * i + 2) * (f & 1)) % 6

Нарешті, замінимо масив M у нашій функції оберту грані на функцію side і приведемо повний код програмної моделі кубика Рубіка:

let cube = [...Array(6)].map((_, i) => Array(9).fill(i))

let side = (f, i) => ([5, 3, 4, 2][i] + f + (4 * i + 2) * (f & 1)) % 6

let N = [0, 2, 6, 4]

let rotate = (f, t) => {
  while (t--) {
    cube[f].unshift(...cube[f].splice(-3, 2))
    for (let i = 3; i; i--)
      for (let j = 0; j < 3; j++)
        [ cube[side(f, i)][(N[i] + j) % 8], cube[side(f, i - 1)][(N[i - 1] + j) % 8] ] =
        [ cube[side(f, i - 1)][(N[i - 1] + j) % 8], cube[side(f, i)][(N[i] + j) % 8] ]
  }
}