Решите (Рубикс) карманный куб

16

Твое задание

... сделать то, что Брайан Фантана, очевидно, не смог, и решить кубик Рубика 2x2x2.

карманный кубик - ведущий

Расположение

- -   A B   - -   - -
- -   C D   - -   - -

E F   G H   I J   K L
M N   O P   Q R   S T

- -   U V   - -   - -
- -   W X   - -   - -

И будет передан вам через стандартный ввод или командную строку (ваш выбор - укажите в своем ответе) в формате:

ABCDEFGHIJKLMNOPQRSTUVWX

Обратите внимание, что AD составляет U-грань (вверх), EFMN составляет L-грань (слева), GHOP - F-грань (спереди), IJQR - R-грань (справа), KLST - B-лицо (спина) и UX составляют D-лицо (вниз).

Будет шесть уникальных символов, представляющих каждый цвет, но они могут различаться, поэтому подготовьтесь к любой комбинации из 6 символов ascii, которые будут использоваться для каждого цвета.

Характеристики

  • Ваш код должен выводить решение, используя только правую (R), верхнюю (U) и переднюю (F) грани, и должно использовать стандартные обозначения: R, R ', R2, U, U', U2, F, F ', F2. Вы можете найти больше информации здесь . Ограничение на подмножество RUF является стандартным для куба 2x2 (Совет: обрабатывайте нижний задний левый угол как фиксированное основание для работы).
  • Ваш код должен быть способен решить все возможные перестановки карманного куба.
  • Каждое решение должно занять менее 30 секунд.
  • Каждое решение должно быть менее 30 ходов.
  • Бонус -20% будет предоставлен для решений, всегда предоставляющих ответы менее чем за 20 ходов (пожалуйста, опубликуйте его в своем ответе, чтобы я мог тщательно его проверить)
  • Бонус -50% будет предоставлен за код, который всегда обеспечивает оптимальное решение. - Опять же, пожалуйста, рекламируйте в своем ответе
  • Решения не должны содержать два последовательных движения на одной и той же грани, потому что их можно легко объединить в одно движение.
  • Решения могут содержать один пробел - и только один пробел - между каждым ходом.
  • Вся последовательность решения, если необходимо, может содержаться в паре скобок, кавычек, фигурных скобок, скобок или вставок, но никакой другой посторонний вывод не допускается.
  • Пожалуйста, предоставьте кратко прокомментированную версию вашего кода или подробное объяснение вашего кода.
  • Нет использования внешних файлов. Это включает в себя Интернет, таблицы данных и библиотеки / пакеты, созданные для такого рода проблем.
  • Самый короткий код по количеству байтов выигрывает.
  • Победителя выбирают в среду (30 июля 2014 г.).
Кайл Маккормик
источник
20
У нас есть 2x2, 3x3 и 4x4 , но я все еще жду испытания 1x1, чтобы мой шанс проявить себя. У меня идеальный алгоритм!
Ручка двери
Вот решатель ~ 500 символов в K, который генерирует даже оптимальное (= самое короткое) решение: speedsolving.com/forum/…
Якуб
30 секунд должно хватить, чтобы перебить его с помощью Дейкстры: всего 3674160 позиций.
Питер Тейлор
2
1. Я предполагаю, что в выходных данных нет ограничений на пробелы. 2. Чтобы быть объективным, вы должны определить бонус для решений менее чем за 20 ходов, вместо того, чтобы оставить его как «дискреционный».
Уровень Река St
@steveverrill Исправлено. Также добавлена ​​спецификация пробелов. Благодарность!
Кайл Маккормик

Ответы:

11

Python 2.7: 544 байта -50% = 272 байта **

import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''}
m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)])
def z(d,h):
 t={}
 for s in d[0]:
  if s in d[1]:print d[h][s]+d[1-h][s];exit()
  n=[d[0][s],'']
  for k in r(3):
   for j in r(3):s=m(s,k);t[s]=n[h]+'RUF'[k]+" 2'"[(j,2-j)[h]]+n[1-h]
   s=m(s,k)
 d[0]=t;return d
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

Stackexchange заменяет вкладки несколькими пробелами. Так что техническая версия имеет 549 байтов. Просто замените первые два пробела в строках 6-10 на табулятор.

Идея, лежащая в основе моей программы: моей первой идеей был поиск в дыхании. Но это заняло слишком много времени. Около 2 минут для тяжелой (11 ходов оптимальной) схватки. Поэтому я решил подойти к проблеме с обеих сторон. Я использую два комплекта. Я генерирую последовательно все состояния с расстоянием 1,2,3, ... до скремблирования и сохраняю их в set1, и в то же время все состояния с расстоянием 1,2,3, ... до решенного состояния и сохраняю их в наборе 2. В первый раз, когда состояние находится в обоих наборах, мы нашли решение.

Для этого мне нужны цвета решенного куба, которые не известны. Символы 13, 20 и 23 определяют цвет слева, сзади и вниз. Но этих трех цветов достаточно, чтобы представить куб. Я просто заменяю 3 других цвета пробелами и могу представить свое решенное состояние как «____ll____bbll____dddd».

Да, и для сокращения перестановок я использовал идею из /codegolf//a/34651/29577

Безголовая версия:

import sys

#define permutations for R,U,F
permutation = [[0,7,2,15,4,5,6,21,16,8,3,11,12,13,14,23,17,9,1,19,20,18,22,10],
            [2,0,3,1,6,7,8,9,10,11,4,5,12,13,14,15,16,17,18,19,20,21,22,23],
            [0,1,13,5,4,20,14,6,2,9,10,11,12,21,15,7,3,17,18,19,16,8,22,23]]

def applyMove(state, move):
    return ''.join([state[i] for i in permutation[move]])

scramble = sys.argv[1]
#remove up,front,rigth colors
scramble = ''.join([(' ', x)[x in scramble[12]+scramble[19]+scramble[22]] for x in scramble])
solved = ' '*4+scramble[12]*2+' '*4+scramble[19]*2+scramble[12]*2+' '*4+scramble[19]*2+scramble[22]*4

dict1 = {scramble: ''} #stores states with dist 0,1,2,... from the scramble
dict2 = {solved: ''} #stores states with dist 0,1,2,... from the solved state

moveName = 'RUF'
turnName = " 2'"

for i in range(6):
    tmp = {}
    for state in dict1:
        if state in dict2:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict1[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveString + moveName[move] + turnName[turn]
            state = applyMove(state, move)
    dict1 = tmp
    tmp = {}
    for state in dict2:
        if state in dict1:
            #solution found
            print dict1[state] + dict2[state]
            exit()
        moveString = dict2[state]
        #do all 9 moves
        for move in range(3):
            for turn in range(3):
                state = applyMove(state, move)
                tmp[state] = moveName[move] + turnName[2 - turn] + moveString
            state = applyMove(state, move)
    dict2 = tmp

Я очень доволен результатом, потому что я новичок в Python. Это одна из моих первых программ на Python.

изменить: через полгода: 427 - 50% = 213,5

Получил немного больше опыта в Python и в гольф. Поэтому я пересмотрел свой оригинальный код и смог сохранить более 100 символов.

import sys;o=''.join;a=sys.argv[1];d=[{o((' ',x)[x in a[12]+a[19]+a[22]]for x in a):[]},{' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:[]}]
for h in[0,1]*6:
 for s,x in d[h].items():
  for y in range(12):
   d[h][s]=x+[y-[1,-1,1,3][h*y%4]];
   if s in d[1-h]:print o('RUF'[x/4]+" 2'"[x%4]for x in d[0][s]+d[1][s][::-1]);exit()
   s=o(s[ord(c)-97]for c in'acahabcdnpbfegefhugiovjgqkciljdeklflmmmnnvoopxphrqdjrrbsstttuuqsviwwwkxx'[y/4::3])

Я в основном использую точно такой же подход. Самое большое изменение в том, что я больше не определяю функцию. Вместо того

def z(d,h):
 for s in d[0]:
  if s in d[1]:...
while 1:v,w=z([v,w],0);w,v=z([w,v],1)

я могу сделать

for h in[0,1]*6:
 for s in d[h]:
  if s in d[1-h]:...

Также я немного изменил ход лямды. Сначала сокращаем, а затем напрямую интегрируем код, поскольку вызов функции появляется только один раз.

Я сохраняю для каждого состояния список чисел от 0 до 11, чтобы представлять ходы, вместо строки, содержащей ходы. Числа конвертируются в самом конце.

Также я объединил два цикла for 'for k in r(3):for j in r(3):в один for y in r(12). Поэтому я тоже должен делать ходы U4, R4, F4. Конечно, такой шаг не появляется в кратчайшем решении, поэтому " 2'"[x%4]работает. (Если x % 4 == 3будет исключение индекса вне диапазона)

Это также немного быстрее, так как я ищу запись во втором сете ранее. Около 0,5 секунды для решения 11 ходов.

Jakube
источник
2
Проголосовал за использование двунаправленной BFS - мой любимый алгоритм поиска (рядом с IDA *). Если время позволит, я опробую его через несколько часов на оптимальность. Кроме того, я не осознавал, что вам не нужны цвета U / R / F для решения головоломки. Красиво сделано!
Кайл Маккормик,
Пройдено по 20 тестов для правильности и оптимальности.
Кайл Маккормик
очень приятно .. помогли мне реализовать быстрее чем за 24! однонаправленные BFS в
JS
на самом деле '____ll____bbll____dddd' должно быть '____ll____bbll____bbdddd'
RE60K
7

C 366 - оптимальный бонус 50% = 183

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};r=20;f(int m,int n){int e,i,j;for(i=4;i--;){for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;for(e=0,j=68;j<76;j++) e+= (c[j]!=c[j+8]) + (c[j]!=c[j^1]);i&&e&&e<45-m*2&m<r?f(m+2,(n+1)%3),f(m+2,(n+2)%3):e||(puts(c),r=m);}}main(){scanf("%s",c+64);f(0,2),f(0,1),f(0,0);}

Используя рекурсию, программа выполняет поиск по дереву глубиной до 11 шагов (максимальная длина оптимального солютона согласно http://en.wikipedia.org/wiki/Pocket_Cube и странице, упомянутой ниже) и когда она находит решение он печатает его (длиной до 22 символов, отслеживается аргументом функцииm .) Используемый порядок является своего рода словарным порядком, где все маршруты, начинающиеся с U, U2, U ', ищутся до того, как будут найдены любые маршруты, начинающиеся с R или F. Таким образом, он не обязательно сначала находит оптимальное решение.

Когда решение печатается, rделается равным, mчто гарантирует, что впоследствии будут напечатаны только равные или более короткие решения. Размещение r=m-2стоит дополнительно 2 символа, но обеспечивает печать только одного решения каждой найденной длины (вплоть до оптимального). Если вы хотите, чтобы оно ТОЛЬКО показывало оптимальное решение, лучшее найденное решение должно быть сохранено в переменной, а оптимальное решение должно быть напечатано в конце программы (это будет стоить около 15 дополнительных символов).

входные данные считываются в массив c[]с индекса 64 и далее. Это необходимо для использования букв алфавита в подвижной таблице. Символы @через Wиспользуются вместо A через X в вопросе, потому что необходимо начать с четного числа, чтобы сделать тест для решения решений. c['Z']также используется для временного хранения, потому что для выполнения 4-кратного поворота требуется всего 5 назначений. Поскольку первая часть c[]не используется, она доступна для хранения решения (которое заканчивается нулевым байтом, как и все строки Си).

for(i..)проходит последовательность из четырех четвертей лица, указанного n.

Первый for(j..)выполняет фактическую замену в соответствии с таблицей t[].

Чтобы проверить, решен ли куб, необходимо проверить только четыре боковые грани. Части URF и DFR можно различить даже при удаленных наклейках U и D, потому что одна часть читает XRF по часовой стрелке, а другая XFR. Если две части взаимозаменяемы так, что U показывает на нижней грани, и наоборот, цвет F будет отображаться на правой грани, и наоборот.

Вторая for(j..)подсчитывает количество несоответствий на четырех боковых гранях. Например, для передней грани сравниваются G & O, H & P и G & H (дважды). Если e== 0, куб решается. Если e<9 или e<13, может быть возможно решить куб за следующий ход или 2 хода соответственно. Иначе определенно невозможно решить куб за это количество ходов. Чтобы сэкономить время, эта эвристика используется для обрезки дерева поиска и предотвращения потери времени на многих ветвях глубины 10 или 11, которые будут безуспешными. Выражается в формуле, это становится e<45-m*2.

Код без правил

char c[99],t[3][26]={"ZGONFZCPTEZBHUMZ","ZIQPHZRUGAZJWOCZ","ZACB@ZJHFDZKIGEZ"};
r=20;                                                       //All moves are output as 2 characters. The index of the last move of the longest solution (11 moves) shall be 20.

f(int m,int n){                                             //perform a cycle through four 1/4 turns of the face specified in n. The index of the move reported in the solution is m.
  int e,i,j;                                                //e is for counting mismatches. i loops through the four 1/4 turns. j performs other functions.
  for(i=4;i--;){

    for(j=15;j--;)c[t[n][j+1]]=c[t[n][j]];                  //A 1/4 turn is performed as three 4-sticker rotations of the type z=a;a=b;b=c;c=d;d=z using the data in the movetable t[][]

    c[m]="FRU"[n],c[m+1]="4'2 "[i],c[m+2]=0;                //Write to the output in c[] the face to be turned and the number of 1/4 turns. Terminate with a zero byte to overwrite any longer solution that may have been found before. 

    for(e=0,j=68;j<76;j++)e+=(c[j]!=c[j+8])+(c[j]!=c[j^1]); //Compare each sticker of the top row of the side faces (64+4 through 64+11) with the stickers below and beside it. Count the number of mismatches.

    i && e && e<45-m*2 & m<r?                               //if the number of 1/4turns is not 4 AND the cube is not solved AND the heuristic (as described in the text) is good AND a shorter solution has not already been found,
      f(m+2,(n+1)%3), f(m+2,(n+2)%3):                       //deepen the search to another faceturn of the other two faces. 
      e||(puts(c),r=m);                                     //otherwise, if a solution has been found, print the solution and reduce the value of r to the new max solution length.
  } 
}

main(){
  scanf("%s",c+64);                                         //scan in the current cube state to c[] at index 64.
  f(0,2),f(0,1),f(0,0);                                     //call f() three times to search for solutions beginning with U R and F.
}

Производительность

Программа была протестирована с шаблонами с 1 по 13 на http://www.jaapsch.net/puzzles/cube2.htm

Следующие результаты дают время на моей машине, чтобы найти ВСЕ оптимальные решения (для любопытных.) Также для более сложных позиций, время дается для упомянутой выше 2-байтовой модификации, которая находит только одно оптимальное решение. Для этого даются сроки как для поиска первого решения, так и для завершения программы. Указанные решения (которые обычно отличаются от решений, полученных путем обращения генераторов на связанной странице) были проверены с помощью онлайн-симулятора кубов.

U 4 (1 move) horizontal flags (not mirror symmetric)
1 solution 1 sec

U2 (1 move) 4 horizontal flags (mirror symmetric)
1 solution 1 sec

F2 R2 F2 (3 moves) 4 vertical flags  
UUUULRBFRLFBLRBFRLFBDDDD 2 solutions 1 sec

U2 F2 R2 U2 (4 moves) Supertwist; 6 flags
DDUURRBFRRFBLLBFLLFBUUDD 3 solutions 1 sec

U F2 U2 R2 U (5 moves) 4 vertical flags, 2 checkerboards
UDDULBRFRFLBLBRFRFLBUDDU 2 solutions 1 sec

R2 F2 R2 U2 (4 moves) 4 checkerboards
UUUURLFBLRBFLRBFRLFBDDDD 4 solutions 1 sec

R U2 R' F2 R U' R2 U F2 U' (10 moves) Cube in cube
FFFUDDRFRULLLDRRUULBBBDB 18 solutions 26 sec; 1 solution U F2U'R2U R'F2R U2R' 1,13 sec 

R F U' R2 U F' R U F2 R2 (10 moves) Cube in cube 2
DDDUFFLFRBRRLFLLBBRBUUDU 8 solutions 28 sec; 1 solution R F U'R2U F'R U F2R2 12,21 sec 

U R F2 U R F2 R U F' R (10 moves)3-Cycle
UFFULDRFRULBLLFRURBBDBDD 45 solutions 26 sec; 1 solution U R'F U'F'R'F2U R F2 8,14 sec 

U R U' R2 U' R' F' U F2 R F' (11 moves) Column turn
UUUDLLFRFRBBLLFRFRBBDUDD many solutions 29 sec; 1 solution U R U'F U2R F'R'F'U2F' 3,27 sec 

F' U R' F2 U' R F U R2 U R' (11 moves)Corner swap
UUUURLFBLRBFLLFFRRBBDDDD 29 sec 24 solutions; 1 solution R U'F R U'R2U'F'R'U F2 12,28 sec

U F2 U' (3 moves) Zig-zag 
UDUDLLFRFFLBLBRRFRBBUUDD 1 solution 1 sec 

U' F2 U2 R2 U' F2 U2 R2 U' (9 moves) 2 Checkerboards, 4 L
DUUDLLFBRRBFLRFFRLBBUDDU 8 solutions 13 sec; 1 solution U F2U2R2U R2U2F2U' 1,5 sec
Уровень реки St
источник
Звучит хорошо. Я бы хотел увидеть здесь соревнование.
Кайл Маккормик
@KyleMcCormick Моя программа наконец-то закончена и работает хорошо, но я вижу, что вы устали ждать и приняли другой ответ. Это намного лучше, чем мой пост 2 дня назад, в котором была ошибка (лица поворачиваются не в ту сторону). Кроме того, применение эвристики к 2 уровням улучшило скорость. Это все еще выводит несколько решений, но последнее решение гарантированно будет оптимальным (больше о возможных изменениях вывода в тексте.) Это намного короче, чем другое представление. Если у вас есть какие-либо проблемы с форматом вывода, дайте мне знать.
Уровень Река St
358 байт через базовые гольфы.
MD XF