Codegolf - Нанизывание Жемчужного Ожерелья

Обзор

Жемчуг (или Масю) это логическая игра, в которую играют по сетке. На сетке размещены черные и белые жемчужины. Цель состоит в том, чтобы сформировать одинарный, замкнутый контур который проходит через каждую жемчужину, используя только сегменты прямых линий и прямые углы.

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

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

Пример головоломки из Википедии (и ее решение):

Ваша цель — решить заданную головоломку. Если существует несколько возможных решений, не имеет значения, какое из них вы предложите.

Вход

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

 
 
 
 
 
 
 
 
 
 .....w.b.w..
ww..b...b...
.w.....b....
...wbww..b.b
....b.......
w.w.........
..w......b.b
.....bb.....
.....b.....w
w.ww..b.....
...w......w.
b..w.....b..
 
 
 
 
 
 
 
 
 
 

.wb..b ...... ..b... w.ww.. ...... b....b 0 0 2 0 2 2 4 2 4 1 3 1 3 0 5 0 5 5 3 5 3 4 4 4 4 3 1 3 1 4 2 4 2 5 0 5 0 2 1 2 1 1 0 1 is a white pearl, ... w.. ..b 0 0 1 0 2 0 2 1 2 2 1 2 0 2 0 1 это черная жемчужина, и Paste grid input here<br><input id="grid" type="textarea" size="80" oninput='drawGrid()' /><br><br>Paste path output here<br><input id="coords" type="textarea" size="80" oninput='drawCoords()' /><br><br><div id="output"></div> is an empty cell.

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

Выход

Выходные данные — это строка координат, представляющая путь. Левый верхний угол сетки svg{position: absolute;left: 50px;} , upper right is function draw(){document.getElementById("output").innerHTML=gridSVG+pathSVG}function drawCoords(){coords=document.getElementById("coords").value;var e=prefix+'<path fill="none" d="';if(nums=coords.match(/[^\s]+/g),!(nums.length<2)){for(e+="M "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),i=2;i<nums.length;i+=2)e+=" L "+(nums[i]*scale+offset)+" "+(nums[i+1]*scale+offset);e+=" L "+(nums[0]*scale+offset)+" "+(nums[1]*scale+offset),e+='" stroke="black" stroke-width="2"/>'+suffix,pathSVG=e,draw()}}function drawPath(){path=document.getElementById("path").value;var e=prefix+'<path fill="none" d="'+path+'" stroke="black" stroke-width="2"/>'+suffix;pathSVG=e,draw()}function drawGrid(){grid=document.getElementById("grid").value;var e=prefix;for(lines=grid.match(/[^\s]+/g),width=lines[0].length*scale,height=lines.length*scale,i=0;i<=lines.length;i++)e+='<path stroke="gray" d="M 0 '+i*scale+" L "+width+" "+i*scale+'"/>',e+='<path stroke="gray" d="M '+i*scale+" 0 L "+i*scale+" "+height+'"/>';for(j=0;j<lines.length;j++)for(line=lines[j],i=0;i<line.length;i++)"w"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="white"/>'),"b"==line.charAt(i)&&(e+='<circle cx="'+(i*scale+offset)+'" cy="'+(j*scale+offset)+'" r="'+.8*offset+'" stroke="black" fill="black"/>');e+=suffix,gridSVG=e,draw()}var prefix='<svg height="400" width="400">',suffix="</svg>",scale=30,offset=scale/2,pathSVG="",gridSVG=""; , где н это ширина сетки.

Путь — это просто серия упорядоченных координат:

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

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

или

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

Фрагмент

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

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

Эти тестовые примеры показывают один возможный результат для каждого входа (кроме последнего, который показан нерешенным). Могут быть и другие допустимые пути: вы можете пойти по часовой стрелке или против часовой стрелки, начать с другой точки и т. д. Решения должны позволять решать тестовые случаи за секунды/минуты/часы, а не за дни/недели/эоны.

#код-гольф #головоломка-решатель #сетка

Питон - 1669 г.

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

Пример вывода для последнего тестового примера:

 
 
 
 
 
 b={}s={0,0,0}R=table.insert Z=unpack for l in io.lines()do w=#l for i=1,w do
c=({b=1,w=2,['.']=3})[l:sub(i,i)]R(b,c)s[c]=s[c]+1 end end h=#b/w for e=0,w*h-1
do function g(p,d,X,t)local function G(I,r)T={Z(t)}a=b[I+1]T[a]=T[a]+1
P={Z(p)}D={Z(d)}R(P,I%w)R(P,I/w-I/w%1)R(D,r)l=#D for U=2,#p,2 do if
I==p[U-1]+w*p[U]then return end end if I==e then if T[1]==s[1]and T[2]==s[2]then
for k=1,l do K=D[k]M=D[(k-2)%l+1]N=D[k%l+1]O=D[(k+1)%l+1]if({K==N or K~=M or
N~=O,K~=N or(K==M and N==O)})[b[1+P[2*k-1]+w*P[2*k]]]then return end end
os.exit(print(table.concat(P,' ')))end else g(P,D,I,T)end end _=X%w<w-1 and
G(X+1,1)_=X/w-X/w%1<h-1 and G(X+w,2)_=X%w>0 and G(X-1,3)_=X/w-X/w%1>0 and
G(X-w,4)end g({},{},e,{0,0,0})end
 
 
 
 
 
 

Код:

Негольфед:

С, 590 640 760 880 963 1018

Грубая сила для этого достаточно быстра. Тест 12x12 выполняется менее 10 мс. Зная это, можно было бы выбрать какой-нибудь язык, более подходящий для игры в гольф.

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

W - 2 define sets the limit on the board dimensions. The actual limit is smaller W поскольку я использую дополнительные строки для границ, чтобы избежать проверки границ.

Тест мне.

Вот более сложный тестовый пример:

Мне повезло, что мой код находит решение довольно рано (<5 минут), но полный поиск занимает гораздо больше времени (67 минут).

Луа, 830 810 765 752 739 729 710

Плата1 и плата2 работает нормально, но на плате3 требуется некоторое время.

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