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

-**
-*-
*-*

и переставьте блок так, чтобы он *сформировал X, вот так:

*-*
-*-
*-*

Ввод: квадраты 3х3, как указано выше, они могут быть 3 строками, массивом или как вам угодно.

Вывод: Наименьшее количество ходов для перестановки в X. Каждое движение переворачивает 2 соприкасающихся символа, горизонтальных друг от друга, вертикальных друг от друга или диагональных друг от друга. Если это невозможно, верните любой невозможный вывод, например 999или -4242. 5наименьшее такое число.

Тестовые случаи:

1) Выход: 1

-**
-*-
*-*

2) Выход: -1

-*-
-*-
*-*

3) Выход: 3

---
-**
***

4) Выход: 0

*-*
-*-
*-*

Вы можете заменить пустые и непустые символы, но не забудьте указать, какие именно в вашем сообщении

Код Гольф

Помните, что это кодовый гольф, выигрывает самый короткий код!

Python 3 , 104 78 байт

lambda n:-(sum(n)!=5)or sum(n[1::2])+n[4]*(max(n,n[6:],n[::3],n[2::3])>=[1]*3)

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

Редактировать: применил предложения @Jonathan Allan и @ xnor, чтобы резко уменьшить количество байтов.

Входные данные представляют собой строковый список длиной 9 с нулями и единицами, из которых единицы - *s.

Вот некоторые наблюдения:

• Нам никогда не нужно перемещать звезды уже на правильные клетки. У любой неуместной звезды есть 5 окружающих клеток, которые нельзя заблокировать сразу (в противном случае ответ уже равен -1).
• Стоимость каждой неуместной звезды равна 1 или 2, и только 2, если она окружена тремя правильно расположенными звездами.
• Стоимость каждой неуместной звезды не зависит друг от друга.

Поэтому мы сначала проверяем, есть ли в строке пять единиц, а затем посчитаем эти вещи:

• Количество неуместных звездочек (= нечетных)
• Число звезд неуместными стоимости 2 (= ячеек на 0124, 0346, 2458, 4678будучи все из них)
  • Вычеркните n[4]единицу, и затем проверьте каждую экстракцию диапазона '111'.
  • Так как такая звезда не более одной, мы можем смело использовать maxвместо sum.

Желе , 26 байт

5ḶḤd3ạŒ!Ṁ€€ḅ1Ṃ
T’d3Ç-L=5Ɗ?

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

Возьмите плоский список в качестве входных данных.

Жаль, что у Jelly нет «многомерных истинных индексов» ... T€ṭ€"JẎтоже работает, но занимает еще 1 байт.

Алгоритм: есть 5 текущих позиций блоков и 5 целей (адресатов), алгоритм пробует каждую из 5! сопоставить и вывести минимальную сумму чебышевского расстояния [источник, пункт назначения].

Хаскелл , 176 132 126 104 байта

w=0:1:w
m a|sum a/=5=5|1>0=sum$[a!!4|3<-sum.map(a!!)<$>[[0,1,2],[0,3,6],[2,5,8],[6,7,8]]]++zipWith(*)a w

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

Принимает список целых чисел с 1 как непустой символ. Суммирует количество ненулевых квадратов с четным индексом, затем добавляет 1, если найден какой-либо из шаблонов двойного перемещения (центральный квадрат и крайний столбец / строка полностью заполнены). Я думаю, что последняя часть немного расточительна, возможно, она может быть значительно улучшена по сравнению с этим методом грубой силы. Возвращает 5 (невозможный вывод) для невозможного ввода.

Python 2 , 194 192 байта

from itertools import*
f=lambda l,k=0:-(sum(l)!=5)or[1,0]*4!=l[:-1]and k<4and-~min(f(l[:a]+[l[b]]+l[a+1:b]+[l[a]]+l[b+1:],k+1)for a,b in combinations(range(9),2)if max(b/3-a/3,abs(a%3-b%3))<2)

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

JavaScript (ES6), 123 байта

Принимает ввод как 9-битное целое число. Решает загадку, наивно применяя правила, которые, как доказано, не являются самым коротким подходом.

f=(n,k=b=-1)=>n^341?k>2?b:[3,6,9,10,17,18,20,34,36].map(m=>[1,8,8].map(M=>(x=n&(m*=M))&-x^x||f(n^m,k+1)))|b:!~b|k<b?b=k+1:b

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

комментарии

f = (                           // f = recursive function taking:
  n,                            //   n = input
  k =                           //   k = number of moves, initialized to -1
  b = -1                        //   b = best result so far, initialized to -1
) =>                            //
  n ^ 341 ?                     // if n does not match the target pattern:
    k > 2 ?                     //   if we've already done more than 3 moves:
      b                         //     we're not going to find a solution -> abort
    :                           //   else:
      [3,6,9,10,17,18,20,34,36] //     for each swap bitmask m
      .map(m =>                 //     and
      [1,8,8]                   //     for each multiplier M:
      .map(M =>                 //       apply the multiplier to m and
        (x = n & (m *= M))      //       apply the final bitmask to n -> this gives x
        & -x                    //       isolate the least significant bit of x
        ^ x ||                  //       if it's the only bit set,
        f(n ^ m, k + 1)         //       then swap the bits and make a recursive call
      )) | b                    //     end of both map() loops; return b
  :                             // else:
    !~b | k < b ? b = k + 1 : b //   this is a solution in k+1 moves: update b

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

Ниже приведены 9 битовых масок базового свопа и целевой шаблон. Верхний левый угол - самый важный бит.

000  000  001  001  010  010  010  100  100     101
011  110  001  010  001  010  100  010  100     010 (341)
(3)  (6)  (9)  (10) (17) (18) (20) (34) (36)    101

Желе , 26 байт

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ

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

Монадическая ссылка.

Как?

Вдохновленный ответом Bubbler на Python ; игра в гольф, чтобы удовлетворить Jelly ...

“ċȤ‘ḤB;U$=a¥;Ḋm2ƊẠ€SɓSn5Nȯ - Link: length 9 list of ones & zeros, X
“ċȤ‘                       - list of code-page indices     = [232,154]
    Ḥ                      - double                        = [464,308]
     B                     - to binary     = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0]]
        $                  - last two links as a monad:
       U                   -   upend       = [[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
      ;                    -   concatenate = [[1,1,1,0,1,0,0,0,0],[1,0,0,1,1,0,1,0,0],[0,0,0,0,1,0,1,1,1],[0,0,1,0,1,1,0,0,1]]
           ¥               - last two links as a dyad:
          a                -   logical AND (vectorises)
         =                 -   equal? (vectorises)
                Ɗ          - last three links as a monad:
             Ḋ             -   dequeue X (remove leftmost element)
               2           -   literal two
              m            -   modulo slice (keeps the "edge-elements") 
            ;              - concatenate
                 Ạ€        - all? for €ach (edge-elements: no-op
                           -                else: 1 for any cost-2 element 0 otherwise)
                   S       - sum
                    ɓ      - new dyadic chain ^that on the right; X on the left
                     S     - sum X
                       5   - literal five
                      n    - not equal?
                        N  - negate (-1 if not exactly 5 1s, 0 otherwise)
                         ȯ - logical OR with right

JavaScript, 85 байт

s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

Это порт регулярного выражения Bubbler .

Ввод в виде строки 0/1.

f=
s=>/^0*(10*){5}$/.test(s)*s.match(/(?=1.(..)*$|^1(..)?11.1|1.11(..)?1$)|$/g).length-1

document.write('<table>'+('<tr>'+'<td><label><input type=checkbox><span></span></label>'.repeat(3)).repeat(3)+'</table>');
document.write('Answer: <output id=o></output>');
U=()=>o.value=f(ii.map(i=>i.checked?1:0).join``);
ii=[...document.querySelectorAll('input')];
ii.forEach((i,p)=>{
i.checked=!(p%2);
i.oninput=U;
});
U()

label{display:block;position:relative;overflow:hidden;width:20px;height:20px;}
input{position:absolute;top:-200%;}
input~span{width:100%;height:100%;display:block;border:1px solid black;box-sizing:border-box;}
input:focus~span{border-color:red;}
input:checked~span{background:#ace;}

Stax , 23 22 байта

Ç╙╤Ü┤└åVτ┐├Y-²▼░█∩¡3ëâ

Запустите и отладьте его

Эта программа принимает массив [0, 1]входных данных и возвращает целое число ходов или пустую строку, если решение невозможно.

Рассмотрим это индексы для сетки

0 1 2
3 4 5
6 7 8

• Если нет точно 5 1 на входе с, то решения нет, поэтому мы не выводим.
• Центры каждой стороны неправильные позиции. Это индексы 1, 3, 5 и 7. Суммирование расстояния для каждого1 в этих позициях даст конечный результат.
• Для каждого 1в неправильном положении его расстояние равно 1 или 2. Это будет 2, если он окружен другими 1s. Например, если есть 1s в индексах [0, 1, 2, 4], то расстояние для неверного1 равно 2.

• Имея это в виду, рассмотрим этот псевдокод для получения расстояния, внесенного в результат по индексу 1.

  1. Прочитать 4 бита из индексов [1, 0, 2, 4]. Это ставит неправильную позицию в наиболее значимую позицию.
  2. Преобразуйте эти биты в число bот 0 до 15.
  3. Когда 0 <= b <= 7расстояние равно 0. Когда 8 <= b <= 14расстояние равно 1. Когда b == 15расстояние равно 2. Это можно рассчитать с помощью целочисленного деления на b * 2 / 15.

Таким образом, общее расстояние можно рассчитать, повторив этот процесс 4 раза и вращая сетку между ними.

1#5=4*  if the number of 1s is 5, then 4, else 0
D       repeat the rest of the program that many times
  x     push the value in the x register, which is initially the input
  3/    split into 3 rows
  rM    rotate 90 degrees
  $X    flatten back into single array, and save the "rotated" array in the X register
  A|2E  get the digits of 2^10 i.e. [1,0,2,4]
  @     read the bits from the current rotation at indices [1,0,2,4]
  :b    convert bits to integer
  H15/  double, then divide by 2
  +     add to running total

Запустите этот

Excel, 86 81 байт

=SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3))/(SUM(A1:C3)=5)

Старый: когда вывод «невозможно» был-1

=IF(SUM(A1:C3)=5,SUM(B1,A2,B3,C2)+B2*(AND(A1:A3)+AND(A1:C1)+AND(C1:C3)+AND(A3:C3)),-1)

Использует 1для заполненных и 0для пустых, ввод в диапазоне A1:C3. Возможно дальше играть в гольф, если мы можем вернуть значения, отличные от -1«невозможно». Возвращает#DIV/0! ошибку на невозможных сетках

Работает по той же логике, что и ответ Bubbler's Python .