43 квинтиллионных перестановок

16

Мы можем представить кубик Рубика в виде сети следующим образом (при решении):

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

Каждая буква представляет соответствующий цвет ( Wбелый, Gзеленый и т. Д.)

Это было показано , что существует ровно 43,252,003,274,489,+856,000 (~ 43 нониллион) различных перестановок , что кубик Рубика может быть в.

Ваша задача - взять целое число от 1 до 43,252,003,274,489,+856,000 и вывести соответствующую перестановку, как показано выше. Вы можете выбрать порядок упорядочения перестановок, но должен быть показан алгоритм, который вы используете, чтобы сгенерировать уникальную и правильную перестановку для каждого возможного ввода.

Неверные правила перестановки

Взято с этой страницы

Начнем с того, что центр каждой грани 3х3 должен оставаться неизменным, поскольку центральный квадрат кубика Рубика не может вращаться. Весь куб можно вращать, меняя положение лица, но это не влияет на сеть куба.

Если мы скажем, что каждая перестановка имеет четность, основанную на четности числа перестановок для достижения этой перестановки, мы можем сказать,

  • Каждая угловая часть имеет три возможных направления. Он может быть ориентирован правильно (0), по часовой стрелке (1) или против часовой стрелки (2). Сумма угловых ориентаций всегда остается делимой на 3

  • Каждое допустимое вращение на кубике Рубика всегда переворачивает четное число ребер, поэтому не может быть только одна часть, ориентированная неправильно.

  • Учитывая перестановку всех углов и ребер, общая четность должна быть четной, что означает, что каждый допустимый ход всегда выполняет эквивалент четного числа свопов (игнорируя ориентацию)

Например, следующие три сети являются недействительными выходами:

   WWW
   WWW
   WWW
GGGWWWBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   YYY
   YYY
   YYY

(Too many whites/not enough reds)

   WRW
   WRW
   WRW
GGGRWRBBBOOO
GGGWRRBBBOOO
YYGRWROOOBBB
   YYY
   GGY
   YYY

(There are two red/green center squares and no white/yellow center squares.
 In all valid permutations, the center squares are all different colours)

   WWW
   WWW
   WWW
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBOYOO
   YYY
   YYY
   YYB

(The yellow/orange/blue corner is rotated into an impossible permutation)

правила

  • Вы должны доказать, как вы хотите, что алгоритм действителен. Вам не нужно перечислять каждую перестановку, если вы доказываете правильность своего алгоритма.
  • 143,252,003,274,489,+856,000
    • 253-1253-1
    • 27,946,105,037,114,+827,095
  • Вы должны включить какое-то подтверждение действительности в свой ответ. Это доказательство может подтвердить правильность любого принятого метода доказательства, за исключением перечисления всех возможностей.
  • Вы можете использовать альтернативный метод ввода, если хотите, если:
    • Вход ограничен
    • Каждый вход соответствует уникальному выходу
    • Вы четко объясняете формат ввода и как он соответствует каждому выходу
  • Вы можете изменить символы, используемые для использования 6 различных символов ASCII, между 33 ( !) и 126 ( ~) вместоWGRBOY
  • Вы можете выводить любым способом, каким пожелаете, при условии, что он образует четкое представление куба, в котором могут быть показаны все 6 граней, включая любую действительную сеть куба, строку с одной подкладкой или 3D-рендеринг. Если вы не уверены в конкретном формате, не стесняйтесь спрашивать в комментариях.

Это поэтому выигрывает самый короткий код в байтах на каждом языке.

Пример допустимых выходов

   YYY
   YYY
   YYY
GGGRRRBBBOOO
GGGRRRBBBOOO
GGGRRRBBBOOO
   WWW
   WWW
   WWW

(The `W` and `Y` faces have been swapped)

   ZZZ
   +++
   +}}
+[[}77ZZ7bbb
bb[}[[7}}+Z7
bb[}++[}}+Z7
   7bb
   [7Z
   [7Z

(To start with, the colours have been mapped W -> +, G -> b, R -> [, B -> }, O -> Z and Y -> 7.
 Then, the moves L, R, U and F' have been applied, in that order.
 Notice that each centre square is different, and corresponds to the same colour as in the mapping)
Кэрд
источник
В третьем неверном примере дело не только в том, что угол находится в недопустимой конфигурации, угол r / y / o является невозможным углом из-за того, что r и o находятся напротив друг друга
fəˈnɛtɪk
Исправлен третий неверный пример (CC @ fəˈnɛtɪk)
Джонатан Аллан
Та же проблема была и во втором неверном примере, но я этого не заметил. Это имеет меньшее значение, потому что цвета все равно перепутаны
fəˈnɛtɪk
(a1,a2,a3,a4)a18!a237a312!/2a4211
1
@ Shaggy Да, строка в одну строку
хороша

Ответы:

13

Древесный уголь , 334 297 байт

Nθ≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θF⪪”B"↷:μêKO″KW#})”³«J⌕α§ι⁰I§ι¹§ι²»≔⁰ω≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δF²«Fδ«≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυFLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»≧÷Lκε»≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ≔θζ≔ηε

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

Nθ

Введите целое число в переменную q.

≔׳﹪θ²¹⁸⁷ε≧⁺﹪±Σ⍘峦³ε≧÷²¹⁸⁷θ

Разделите qна 3⁷, положив остаток в e. Затем, считая eчисло в базе 3, eдобавьте суффикс к цифре, чтобы ее цифры (в базе 3) складывались в кратное число 3. Это позволяет eопределить повороты углов.

≔⁴⁰³²⁰δ≔﹪θδζ≧÷δθ

Разделите qна 8!, Положив остаток z. (8! Временно сохраняется dдля сохранения байта.) Это позволяет zопределить положение углов.

≔⊗﹪θ²⁰⁴⁸η≧⁺﹪Σ⍘粦²η≧÷²⁰⁴⁸θ

Разделите qна 2¹¹, положив остаток в h. Затем, считая hчисло в базе 2, hдобавьте суффикс к цифре, чтобы ее цифры (в базе 2) складывались в кратное число 2. Это позволяет hопределить перевороты ребер.

F⪪”B"↷:μêKO″KW#})”³

Зацикливание на строковом представлении центров.

«J⌕α§ι⁰I§ι¹§ι²»

Перепрыгните в положение каждого центра и распечатайте его.

≔⁰ω

Отслеживайте соотношение угловых положений в переменной w.

≔⪪”A‽}y≔W⊞≦≦⧴!O×➙⟧ï!Y9⁺`↙1δQ1ξzT”⁶υ

Создайте массив угловых позиций.

≔⪪”{➙∧⊙ηr⸿ξd⊕÷M→¡$≧”³δ

Создайте массив угловых цветов.

F²«

Цикл дважды, один раз для углов, один раз для краев, именуемый в дальнейшем «кубиками».

Fδ«

Цикл по массиву цветов куба.

≔§υ⎇⁼Lυ⊗ιωζδ≧÷Lυζ≧⁺⌕υδω≔Φυ¬⁼λδυ

Извлечь следующую позицию куба z, обновив паритет в w. Используйте это соотношение для последнего, но одного ребра. Это гарантирует, что сумма четности ребер и углов будет четной.

FLκ«J⌕α§δ⊗⁺λεI§δ⊕⊗⁺λε§κλ»

Напечатайте куб в этой позиции, скорректированный для следующего поворота или переверните в зависимости от ситуации.

≧÷Lκε»

Уберите вращение или переверните с e.

≔⪪”A‽}R›K<≡^μ≡⟦σD⎚+πη±t¿e∧L⸿~↑�w”⁴υ

Создайте массив позиций ребер. Это будет использоваться второй раз в цикле.

≔⪪”{➙∧⊙ηr⸿ξe'→↑Þ³№¹”²δ

Создайте массив краевых цветов.

≔θζ≔ηε

Перезапись угловой переменных zи eс соответствующим краевым переменными qи hтак, чтобы края переставляются и перевернутыми во втором проходе цикла.

Нил
источник
Посоветуйте себе: если в Charcoal есть что-то 330 байтов, не пытайтесь сделать это на PHP!
Ночь2
@ Night2 К сожалению, 334 из-за ошибки (неправильный расчет четности).
Нил
8

Рубин , 570 408 байт

->g,h{z=[]
c=a="\x19)!$'%\x177\x1F495.)@7g~yp"
20.times{|i|z<<a[k=g%r=12+i/12*8-i];a[k]="";g/=r}
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18,2])
h+=h+("%b"%(h%2048)).sum%2
j=0
b="023451"
20.times{|i|b<<("%0*o"%[r=2+i/12,z[i].ord-20]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s["<QTWZo;MP[ngD@RS^k=GVUpaJ8XYdsAFE?CN7LK9IHl_`jh]reftbc"[i].ord-55]=b[i]}
s}

Попробуйте онлайн!

Оригинальная версия, с массивами магических чисел вместо волшебных строк

->g,h{z=[]
a=[05,025,015,020,023,021,03,043,013,040,045,041,   032,025,054,043,0123,0152,0145,0134]
#PERMUTE
20.times{|i|r=12+i/12*8-i;z<<a.delete_at(g%r);g/=r}
c=1
19.times{|i|z[0..i].map{|j|j>z[i+1]&&c=!c}}
c||(z[19],z[18]=z[18],z[19])
#ROTATE
h+=h+(h%2048).to_s(2).sum%2
j=0
b="023451"
20.times{|i|r=2+i/12;b<<("%0*o"%[r,z[i]]*2)[h%r+i/19*j%3,r];j-=r/3*h;h/=r}
#DISPLAY
s=(t="...
"*3)+(?.*12+$/)*3+t
54.times{|i|s[
[5,26,29,32,35,56,
4,22,25,36,55,48, 
13,9,27,28,39,52,
6,16,31,30,57,42,
19,1,33,34,45,60,
10,15,14,8,12,23,0,21,20,2,18,17,
53,40,41,51,49,38,59,46,47,61,43,44][i]]=b[i]}
s}

Попробуйте онлайн!

Анонимная функция, которая в своем текущем виде принимает два целых числа, что, по-видимому, разрешено: «вы можете выбрать альтернативный метод ввода». Первая - это перестановка в диапазоне от 0 до, 12!*8!/2 - 1а вторая - ориентация фигур в диапазоне от 0 до 2**11 * 3*7 - 1. Выход в разрешенном состоянии является следующей строкой:

000
000
000
222333444555
222333444555
222333444555
111
111
111

Дальнейший гольф

Осталось сохранить еще примерно 10 символов, изменив формат вывода на следующую форму. Но это уменьшит читабельность, поэтому я не буду делать это в настоящее время

      #########
      #########
      #########
#########
#########
#########

объяснение

перестановка

Внутри решенное состояние представлено серией восьмеричных чисел в массиве a. Входные данные gделятся на числа 12..1с модулем, используемым для выбора и удаления ребра aи его размещения z. Когда это сделано, остаются только углы a, поэтому gделится на числа 8..1с модулем, используемым для удаления угла aи помещения его вz .

Поскольку для определения порядка двух последних углов недостаточно информации, значение gбудет разделено на ноль к моменту их достижения, поэтому они всегда будут добавляться кz в исходном порядке. Затем выполняется проверка, чтобы определить, является ли общая перестановка четной или нечетной, и, если необходимо, последние два угла меняются местами, чтобы сделать перестановку четной.

ориентация

Существуют различные способы определения правильности ориентации угла или кромки, если они не находятся в определенном месте. Для целей этого ответа угол рассматривается в правильной ориентации, если он показан 0или 1на верхней или нижней грани. Поэтому поворот верхней или нижней грани не меняет ориентацию угла. Вращение других граней меняет ориентацию, но таким образом, что общая сумма четности остается неизменной. Края рассматриваются в правильной ориентации, если они показывают a 2или 4вперед / назад или a 3или 5влево / вправо. Это означает, что вращение вершины или низа на четверть оборота переворачивает четыре ребра, но вращение других граней оставляет статус переворота неизменным.

Вход содержит явную информацию для всех, кроме первого ребра и последнего угла. 11 младших разрядов h%2048суммируются, а модуль используется для определения ориентации первого ребра. hумножается на 2 путем добавления его к себе, а значение для ориентации первого ребра добавляется как младший значащий бит. Ориентация последнего угла определяется путем постепенного вычитания ориентации других углов j. Для самого последнего угла (где i/19= 1) j%3добавляется значение h(которое будет уменьшено до нуля), и это определяет ориентацию последнего угла.

Строка bпоставляется с инициализацией текста для центров граней. hделится в 2двенадцать раз, затем в 3восемь раз, с модулями, используемыми для определения ориентации кусков. В каждом случае число in zпреобразуется в строку с соответствующим количеством цифр (2 или 3), а затем строка дублируется. Это позволяет извлечь из строки правильное вращение цифр, найденное по модулю, путем индексации и добавления кb

дисплей

Наконец, необработанные стикеры копируются bв более понятный для человека формат с sиспользованием магических чисел в индексной таблице.

Уровень реки St
источник