Codegolf - Это Гамильтонов Цикл?

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

Правила

• Из блока \$(x,y)\$ за один шаг вы можете переместиться вправо(R) в \$(x,y+1)\$, влево(L) в \$(x,y-1)\$ ,up(U) до \$(x-1,y)\$ ,down(D) до \$(x+1,y)\$ при условии, что блок, к которому мы переходим, не пуст и находится внутри нашего блока
• Мы можем взять только одну монету за раз.
• Сразу после выполнения прыжка собираем 1 монету со своей новой позиции.
• Укажите маршрут в виде строки, например RLRRDULU...
• Вы должны собрать все монеты
• Если маршрут решения не существует, напечатайте/выведите -1
• Если существует несколько решений, вы можете предоставить любое

Каждый блок 1x1 может содержать до 69 монет.

Примеры:

 integer in each place denotes number of coins at each block

1 1 1
1 1 1         
1 2 1
here DDRUDRUULL and RRDDLUDLUU both are correct (there might be more but you can print any one of your choice)

2 4 4
2 1 3
1 2 3
here DDUURDDRUULRLRDDLRUULL is a valid answer

5 5 1
5 4 5
5 2 2
here DURLRLRLRDLDUDUDUDRLRURLRLRDUDUULL is a valid answer

2 4 2
2 1 1
1 1 2
here doesn't exist a valid solution for this case so output -1

29 7 6
8 5 4
4 28 3
here doesn't exist a valid solution for this case so output -1

4 3 5
5 4 5
3 5 2
here DUDURLRDLDRULRLRDLRLRRLRUUDUDUDUDULL is valid solution

18 8 33
16 4 38
10 28 25
here DUDUDUDUDUDUDUDUDUDUDURLRLRLRLRLRLRDLDUDURLRLRDLRLRLRLRLRLRLRLRRUUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRUULL is a valid solution

69 69 69
69 69 69 
69 69 69
here doesn't exist a valid solution for this case so output -1

7 5 9
21 10 68
15 3 56
here
DUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDRRLRLRUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUUDUDUDUDUDUDUDUDUDLRLRLRLRLRLUDUDUDUDUL is a valid solution

17 65 29
16 35 69 
19 68 56
here doesn't exist a valid solution for this case so output -1

 

Цель состоит в том, чтобы свести к минимуму ваш исходный код, а ответы оцениваются в байтах, но не стесняйтесь демонстрировать любой свой подход, я буду рад все это прочитать.

Изменить: Как уже упоминалось, мы начинаем с верхнего левого блока, поэтому количество монет в верхнем левом блоке, очевидно, не уменьшается при запуске игры. Кроме того, как уже упоминалось, монета в блоке может достигать 69, поэтому ваш код должен иметь возможность выдавать результат в разумные сроки (не более 60 секунд или тайм-аутов), вы можете протестировать свой код в последних трех примерах, не стесняйтесь спрашивать еще несколько примеров.

Обратите внимание, что обещано, что монеты существуют в каждой ячейке.

Изменить: освобожденный ввод-вывод, как предложено, возвращает список или строку, представляющую ходы, вы можете использовать 4 разных значения для L, R, U, D. Если решения нет, верните согласованное значение, отличное от любого решения.

#код-гольф #код-гольф #сетка #поиск пути #ограниченное время

Python NumPy, 245 байт

 
 
def f(A,d="RL",e="DU"):

for x in r_[:A[0]]:

B=A[c_[[2,8,6,0],[1,5,7,3]]]-1;p="";m=A[4];t=m==sum(diff(B));B[3,0]-=x

for b,c in B:q,r=d;y=min(c-x,b);p+=x*d+q+(u:=c-x-y)*e+y*d+q;x=b-y;d=e;e=r+q;m-=u;t&=y>-1<m

if t:return p
from numpy import*
 
 

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

Еще не очень играю в гольф; извинения. Это принимает плоский массив в качестве входных данных и возвращает путь или a = a1+a2 c = c1+c2 g = g1+g2 i = i1+i2 e = e1+e2+e3+e4 b = a2+e1+c1 f = c2+e2+i1 h = i2+e3+g1 d = g2+e4+a1 if there is none.

Как?

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

Если мы обозначим блоки

то мы ищем неотрицательное решение