На некоторых старых телефонах Nokia была вариация пятнадцати пазлов под названием «Вращение». В этом варианте вместо скольжения одной плитки за раз вы поворачивали четыре плитки за раз в одном направлении.

В этой игре вы начнете с такой доски:

4 9 2
3 5 7
8 1 6

И, повернув нижний левый блок дважды по часовой стрелке и верхний левый блок один раз по часовой стрелке, вы получите следующее:

4 9 2
8 3 7
1 5 6

4 9 2
1 8 7
3 5 6

1 4 2
8 9 7
3 5 6

и 1плитка будет в левом верхнем углу, где она должна быть. В конце концов, после нескольких ходов вы получите:

1 2 3
4 5 6
7 8 9

которая является "оригинальной" конфигурацией.

Ваша задача состоит в том, чтобы создать программу, которая будет принимать в качестве входных данных сетку чисел 3x3 от 1 до 9 (в любом формате, которую вы выберете) и возвращать в качестве выходной последовательности ходы, представляющие ходы, которые вы должны предпринять, чтобы вернуть доску обратно в исходное состояние. Конфигурация (опять же, в любом формате, который вы выберете). Под законными ходами понимается перемещение блока [верх / низ] - [влево / вправо] из 4 плиток [по часовой стрелке / против часовой стрелки].

Ваша программа должна быть в состоянии решить все возможные сетки 3х3 (все перестановки разрешимы).

Самый короткий код для этого выигрывает.

GolfScript, 39/83 байта

# Optimized for size:

{.4rand.p.2/+>`{?1420344440`=}+$..$>}do

# Optimized for speed:

6,(7++:t;~{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*

Скорость против размера

Оптимизированная по размеру версия случайным образом выбирает вращения по часовой стрелке, пока не будет достигнута нужная перестановка. Этого достаточно, поскольку вращение против часовой стрелки эквивалентно трем последовательным вращениям по часовой стрелке одного и того же квадрата.

Оптимизированная по скорости версия делает то же самое, за исключением следующего:

1. Если число 1 находится в верхнем левом углу, оно больше не поворачивает верхний левый квадрат.

2. Если число 9 находится в нижнем правом углу, оно больше не вращает нижний правый квадрат.

3. Шаги для изменения позиций 7 и 8 жестко закодированы, поэтому есть две позиции, которые позволяют разрывать петлю.

Помимо изменения алгоритма, оптимизированная по скорости версия выполняет вращение простым способом, тогда как оптимизированная по размеру версия использует встроенную сортировку GolfScript путем сопоставления. Он также жестко кодирует конечное состояние (для сравнения) вместо сортировки состояния в каждой итерации.

Оптимизированная по скорости версия требует меньше итераций, и каждая итерация намного быстрее сама по себе.

Ориентиры

Я использовал следующий код для рандомизации позиций чисел и выполнения тестовых прогонов, раскомментировав строку, соответствующую тестируемой версии:

[{[
    0:c;10,1>{;2 32?rand}$
    #{c):c;.4rand.2/+>`{?1420344440`=}+$..$>}do
    #6,(7++:t;{.(1=.@7=9=+4\-rand+..2/+@.@>:s^[3s=0s=2s=4s=1s=]+s|.)9<\t>|}do.$>30764`*
],c+}\~*]

$.0='Min: '\+puts .-1='Max: '\+puts ..{+}*\,/'Avg: '\+puts .,2/='Med: '\+

Выходные данные показывают минимальное и максимальное количество шагов, необходимых для упорядочения чисел, среднего значения и медианы всех прогонов, а также истекшее время в секундах:

$ TIME='\n%e s' time golfscript rotation-test-size.gs <<< 100
Min: 4652
Max: 2187030
Avg: 346668
Med: 216888

21500.10 s
$
$ TIME='\n%e s' time golfscript rotation-test-speed.gs <<< 1000
Min: 26
Max: 23963
Avg: 3036
Med: 2150

202.62 s

На моей машине (Intel Core i7-3770) среднее время выполнения оптимизированной по размеру версии составило 3,58 минуты. Среднее время выполнения оптимизированной по скорости версии составило 0,20 секунды. Таким образом, оптимизированная по скорости версия примерно в 1075 раз быстрее.

Оптимизированная по скорости версия дает в 114 раз меньше оборотов. Выполнение каждого поворота происходит в 9,4 раза медленнее, что в основном связано с тем, как обновляется состояние.

I / O

Выход состоит из 3-битных чисел. MSB установлен для вращения против часовой стрелки, средний бит установлен для нижних квадратов, а LSB установлен для правых квадратов. Таким образом, 0 (4) - верхний левый квадрат, 1 (5) - верхний правый, 2 (6) - нижний левый и 3 (7) - нижний правый.

Оптимизированная по скорости версия печатает все повороты в одну строку. Оптимизированная по размеру версия печатает один оборот на строку с последующим окончательным положением чисел.

Для версии с оптимизированной скоростью входные данные должны давать массив, содержащий цифры от 1 до 9 при оценке. Для версии с оптимизированным размером входные данные должны быть строкой без заключительного перевода строки; это не оценивается.

Пример работы:

$ echo -n '253169748' | golfscript rotation-size.gs
3
0
123456789
$ golfscript rotation-speed.gs <<< '[5 4 7 1 2 9 3 8 6]'
2210300121312212222212211121122211122221211111122211211222112230764

Оптимизированный по размеру код

{               #
  .             # Duplicate the state.
  4rand         # Push a randomly chosen integers between 0 and 3.
  .p            # Print that integer.
  .2/+          # Add 1 to it if it is grater than one. Possible results: 0, 1, 3, 4
  >`            # Slice the state at the above index.
  {             # Push a code block doing the following:
    ?           # Get the index of the element of the iteration in the sliced state.
    1420344440` # Push the string "14020344440".
    =           # Retrieve the element at the position of the computed index.
  }+            # Concatenate the code block with the sliced state.
  $             # Sort the state according to the above code block. See below.
  ..$>          # Push two copies of the state, sort the second and compare the arrays.
}do             # If the state is not sorted, repeat the loop.

Обновление состояния достигается следующим образом:

Вращение 2 дает целое число 3 после добавления 1. Если состояние «123456789», то разделение состояния дает «456789».

Прямо перед выполнением «$» самые верхние элементы стека:

[ 1 2 3 4 5 6 7 8 9 ] { [ 4 5 6 7 8 9 ] ? "1420344440" = }

«$» Выполняет блок один раз для каждого элемента массива, который будет отсортирован, после нажатия самого элемента.

Индекс 1 в «[4 5 6 7 8 9]» равен -1 (отсутствует), поэтому последний элемент «1420344440» помещается. Это дает 48, код ASCII, соответствующий символу 0. Для 2 и 3, 48 также выдвигается.

Целые числа, заданные для 4, 5, 6, 7, 8 и 9: 49, 52, 50, 48, 51 и 52.

После сортировки первым элементом состояния будет один из элементов, дающих 48; последний будет одним из тех, которые дают 52. Встроенный тип сортировки в целом нестабилен, но я эмпирически подтвердил, что в данном конкретном случае он стабилен.

Результат - «[1 2 3 7 4 6 8 5 9]», что соответствует вращению нижнего левого квадрата по часовой стрелке.

Оптимизированный по скорости код

6,(7++:t;       # Save [ 1 2 3 4 5 7 ] in variable “t” and discard it.
~               # Interpret the input string.
{               #
  :s            # Duplicate the current state.
  (1=           # Unshift the first element and push 1 if it is equal to 1 and 0 otherwise.
  .@            # Duplicate the boolean and rotate the unshifted array on top of it.
  7=9=          # Push 1 if the eighth element of “s” is equal to 9 and 0 otherwise.
  +4\-          # Add the booleans and subtract their sum from 4.
  rand          # Push a randomly chosen integers between 0 and the result from above.
  +.            # Add this integer to the first boolean and duplicate it for the output.
  .2/+          # Add 1 to the result if it is grater than one. Possible results: 0, 1, 3, 4
  @.            # Rotate the state on top of the stack and duplicate it.
  @>:s          # Slice the state at the integer from above and save the result in “s”.
  ^             # Compute the symmetric difference of state and sliced state.
  [             # Apply a clockwise rotation to the sliced array:
    3s=         # The fourth element becomes the first.
    0s=         # The first element becomes the second.
    2s=         # The third element remains the same.
    4s=         # The fifth element becomes the fourth.
    1s=         # The second element becomes the fifth.
  ]             # Collect the results into an array.
  +             # Concatenate with array of elements preceding the slice.
  s|            # Perform set union to add the remaining elements of “s”.
  .             # Duplicate the updated state.
  )9<           # Pop the last element; push 0 if it is equal to 9 and 1 otherwise.
  \t            # Swap the popped state on top and push [ 1 2 3 4 5 7 ].
  >             # Push 0 if the state begins with [ 1 2 3 4 5 6 ] and 1 otherwise.
  |             # Take the logical OR of the booleans.
}do             # If the resulting boolean is 1, repeat the loop.
.$              # Duplicate the state and sort it.
>30764`*        # If the state was not sorted, 7 and 8 are swapped, so push "30764".

Обратите внимание, что повороты 3, 0, 7, 6 и 4 меняют местами элементы в позициях 7 и 8, не изменяя положения остальных семи элементов.

Питон с Numpy - 158

from numpy import*
A=input()
while any(A.flat>range(1,10)):i,j,k=random.randint(0,2,3);A[i:i+2,j:j+2]=rot90(A[i:i+2,j:j+2],1+2*k);print"tb"[i]+"lr"[j]+"wc"[k]

Ввод должен быть в следующем формате:

array([[1,2,5],[4,3,6],[7,8,9]])

Каждая выходная строка представляет собой ход, закодированный в виде строк trwили, blcи должен читаться следующим образом:

• t: верх
• b: дно
• l: осталось
• r: право
• c: по часовой стрелке
• w: против часовой стрелки (виддершин)

Эта программа выполняет случайные перемещения, пока не будет достигнута целевая конфигурация. При приближенном предположении, что каждый ход имеет независимую вероятность 1/9! чтобы попасть в целевую конфигурацию¹, число вращений перед решением экспоненциально распределяется со средним (то есть, средним числом ходов), равным 9! ≈ 3,6 · 10⁵. Это в соответствии с коротким экспериментом (20 прогонов).

^{¹ 9! быть общее количество конфигураций.}

C ++ решение с наименьшим количеством ходов - сначала ширина (1847 символов)

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

Из предыдущего решения самым большим изменением было перемещение истории ключей из состояния платы (BS) в новый класс, который хранит историю на заданной глубине (DKH). Каждый раз, когда приложение делает ход, оно проверяет историю на этой глубине и на всех глубинах, прежде чем посмотреть, было ли оно когда-либо оценено, если так, то оно больше не будет добавлено в очередь. Похоже, это значительно уменьшает объем хранилища в очереди (удаляя всю эту историю из самого состояния платы) и, следовательно, в значительной степени уменьшает все глупые сокращения, которые я должен был сделать, чтобы не допустить исчерпания памяти в коде. Кроме того, он работает намного быстрее, так как копировать в очередь намного меньше.

Теперь это простой поиск в разных штатах. Плюс, как оказалось, я хочу изменить набор ключей (в настоящее время хранится как набор чисел в base-9, каждый из которых вычисляется с помощью BS :: key как представление платы base-9) на битовый набор имея 9! биты кажутся ненужными; хотя я узнал, как вычислить ключ в «системе факторных чисел», который можно было бы использовать для вычисления бита в наборе битов для проверки / переключения.

Итак, новейшее решение:

#include <iostream>
#include <list>
#include <set>
#include <vector>
using namespace std;
struct BS{
#define LPB(i) for(int*i=b;i-b<9;i++)
struct ROP{int t, d;};
typedef vector<ROP> SV;
typedef unsigned int KEY;
typedef set<KEY> KH;
BS(const int*d){const int*x=d;int*y=b;for(;x-d<9;x++,y++)*y=*x;}
BS(){LPB(i)*i=i-b+1;}
bool solved(){LPB(i)if(i-b+1!=*i)return 0;return 1;}
void rot(int t, int d){return rot((ROP){t,d});}
void rot(ROP r){rotb(r);s.push_back(r);}
bool undo(){if (s.empty())return false;ROP &u=s.back();u.d*=-1;rotb(u);s.pop_back();return true;}
SV &sol(){return s;}
KEY key(){KEY rv=0;LPB(i){rv*=9;rv+=*i-1;}return rv;}
int b[9];
SV s;
void rotb(ROP r){int c=r.t<2?r.t:r.t+1;int bi=(r.d>0?3:4)+c;const int*ri=r.d>0?(const int[]){0,1,4}:(const int[]){1,0,3};for(int i=0;i<3;i++)swap(b[bi],b[c+ri[i]]);}
};
ostream &operator<<(ostream &o, BS::ROP r){static const char *s[]={"tl","tr","bl","br"};o<<s[r.t]<<(r.d<0?"w":"c");return o;}
struct DKH{
~DKH(){for(HV::iterator i=h.begin();i<h.end();++i)if(*i!=NULL)delete *i;}
void add(int d,BS b){h.resize(d+1);if(h[d]==NULL)h[d]=new BS::KH();h[d]->insert(b.key());}
bool exists(BS &b){BS::KEY k=b.key();size_t d=min(b.sol().size(),h.size()-1);do if (h[d]->find(k)!=h[d]->end())return true;while(d--!=0);return false;}
typedef vector<BS::KH *> HV;HV h;
};
static bool solve(BS &b)
{
const BS::ROP v[8]={{0,-1},{0,1},{1,-1},{1,1},{2,-1},{2,1},{3,-1},{3,1}};
DKH h;h.add(0,b);
list<BS> q;q.push_back(b);
while (!q.empty())
{
BS qb=q.front();q.pop_front();
if (qb.solved()){b=qb;return true;}
int d=qb.sol().size()+1;
for (int m=0;m<8;++m){qb.rot(v[m]);if (!h.exists(qb)){h.add(d,qb);q.push_back(qb);}qb.undo();}
}
return false;
}
int main()
{
BS b((const int[]){4,9,2,3,5,7,8,1,6});
if (solve(b)){BS::SV s=b.sol();for(BS::SV::iterator i=s.begin();i!=s.end();++i)cout<<*i<<" ";cout<<endl;}
}

CJam - 39

l{4mr_o_1>+_@m<_[Z0Y4X]\f=\5>+m>__$>}g;

Еще один случайный решатель :)
Он принимает строку, например 492357816, и выводит (длинный) ряд цифр от 0 до 3, каждая из которых представляет вращение блока по часовой стрелке: 0 = верхний левый, 1 = верхний правый, 2 = нижний левый, 3 = нижний правый.

Краткое объяснение:

4mrгенерирует случайное число от 0 до 3,
_1>+увеличивает число, если оно больше 1 (таким образом, мы получаем 0, 1, 3 или 4 - начальные индексы 4 блоков),
m<поворачивает строку влево (например, 492357816 -> 923578164, а не вращение блока), чтобы привести блок во вращение в первой позиции,
[Z0Y4X]\f=выполняется вращение блока, которое влияет на первые 5 символов, например 12345 -> 41352;
X = 1, Y = 2, Z = 3, поэтому [Z0Y4X] на самом деле [3 0 2 4 1], и это индексы на основе 0 для повернутых тайлов,
5>копирует остальную часть строки,
m>поворачивает (измененную) строку обратно в право
__$>проверяет, отсортирована ли строка (это условие остановки)

Mathematica, 104 символа

Мы можем интерпретировать задачу на языке групп перестановок. Четыре поворота - это всего лишь четыре перестановки, которые генерируют симметрическую группу S ₉ , и задача состоит в том, чтобы просто написать перестановку как произведение генераторов. Mathematica имеет встроенную функцию для этого.

i={1,2,5,4};GroupElementToWord[PermutationGroup[Cycles/@({i}+#&/@i-1)],Input[]~FindPermutation~Range@9]

Пример:

Входные данные:

{4, 9, 2, 8, 3, 7, 1, 5, 6}

Выход:

{-2, -3, -4, 2, 4, 1, 4, -1, -2, 3, 2, -4, 3, 4, -3, -3, -4, -4, -2, -2, -3, -2, 3, -1}

• 1: верхний левый по часовой стрелке
• 2: верхний правый по часовой стрелке
• 3: справа внизу по часовой стрелке
• 4: внизу слева по часовой стрелке
• -1: верхний левый против часовой стрелки
• -2: верхний правый против часовой стрелки
• -3: внизу справа против часовой стрелки
• -4: внизу слева против часовой стрелки