Nós amamos nossos quebra-cabeças estranhos, nós britânicos

16

Em alguns jornais britânicos, há um jogo conhecido como Hidato . É um pouco parecido com o Sudoku , embora em vez de ter de 1 a 9 em linha e em bloco, trata-se de colocar números para que eles se conectem em ordem, desde 01o mais alto até o mais alto, para que todos estejam tocando horizontalmente, diagonalmente ou verticalmente .

As entradas conterão várias linhas separadas por \n, contendo blocos separados por um espaço, que você pode assumir com dois caracteres de largura. Cada bloco será um número, um espaço em branco a ser preenchido (indicado por --) ou uma parede que não pode ter números em ( XX).

Sua saída deve corresponder à fornecida, embora com blocos vazios fornecidos com números. Observe que pode não haver uma solução única, ou mesmo a existência de uma solução - algumas podem render múltiplas devido à sua ambiguidade, como o Sudoku, e outras podem ser literalmente insolúveis, nesse caso, você deve fornecer uma saída falsey , mas você pode assumir que as entradas estão formatadas como abaixo.

Use um cabeçalho padrão Language: XX bytes. Feliz golfe!

Exemplos

Entradas 01 XX 03, 01 -- 04, 01 --, etc todos devem retornar algo Falsey .

Entrada:

01 -- --
-- XX 05

Resultado:

01 03 04
02 XX 05

Entrada:

-- 33 35 -- -- XX XX XX    
-- -- 24 22 -- XX XX XX      
-- -- -- 21 -- -- XX XX
-- 26 -- 13 40 11 XX XX
27 -- -- -- 09 -- 01 XX
XX XX -- -- 18 -- -- XX
XX XX XX XX -- 07 -- --
XX XX XX XX XX XX 05 --

Resultado:

32 33 35 36 37 XX XX XX
31 34 24 22 38 XX XX XX
30 25 23 21 12 39 XX XX
29 26 20 13 40 11 XX XX
27 28 14 19 09 10 01 XX
XX XX 15 16 18 08 02 XX
XX XX XX XX 17 07 06 03
XX XX XX XX XX XX 05 04

Entrada:

XX XX XX XX -- 53 XX XX XX XX
XX XX XX XX -- -- XX XX XX XX
XX XX 56 -- -- -- 30 -- XX XX
XX XX -- -- -- -- -- -- XX XX
XX -- -- 20 22 -- -- -- -- XX
XX 13 -- 23 47 -- 41 -- 34 XX
-- -- 11 18 -- -- -- 42 35 37
-- -- -- -- 05 03 01 -- -- --
XX XX XX XX -- -- XX XX XX XX
XX XX XX XX 07 -- XX XX XX XX

Resultado:

XX XX XX XX 52 53 XX XX XX XX
XX XX XX XX 54 51 XX XX XX XX
XX XX 56 55 28 50 30 31 XX XX
XX XX 26 27 21 29 49 32 XX XX
XX 25 24 20 22 48 45 44 33 XX
XX 13 19 23 47 46 41 43 34 XX
14 12 11 18 04 02 40 42 35 37
15 16 17 10 05 03 01 39 38 36
XX XX XX XX 09 06 XX XX XX XX
XX XX XX XX 07 08 XX XX XX XX
Mia yun Ruse
fonte
Certificando-me de que entendo: Dada uma grade com algumas células não passíveis de caminhar, encontre um caminho hamiltoniano que se encaixe nas células pré-cheias?
Geobits 04/08/2015
@AmiRuse Wow. Isso parece complicado. (Claro, isso é proveniente de uma pessoa que odeia a edição de fotos.) É meio bom saber de outra pessoa aqui que tem um personagem VG como seu logotipo. : O
kirbyfan64sos
Podemos ver uma solução para o exemplo? Mais exemplos também serão úteis.
Kade
Brilhante :). Você também pode ter um desafio gerador de mais tarde
Beta Decay
3
O método de entrada poderia ser simplificado? Talvez use uma matriz 2D de números inteiros, e tenha -1uma parede e 0fique em branco? Isso facilitaria o foco no verdadeiro desafio do quebra-cabeça e, portanto, não há complexidade em preencher números com zeros ou cadeias de análise.
mbomb007

Respostas:

1

JavaScript (Node.js) , 482 bytes

Esta é uma solução de força bruta, começa em 01e verifica todas as células vizinhas, verificando se há células vazias ( --) ou o número desejado e seguindo o caminho para a conclusão ou impossibilidade. Se o número desejado existir e não for um vizinho, atalhos para esta solução. Leva alguns segundos para a maior grade.

Provavelmente isso não é particularmente interessante, mas pensei em tentar uma solução antes de analisar as respostas vinculadas ao Código Rosetta e gostei de enfrentar um desafio um pouco mais difícil!

Encontra todas as soluções quando existem muitas . O corpo é uma função que aceita uma matriz bidimensional e o rodapé processa a entrada no formato desejado e retorna o resultado também no formato desejado. É um prazer fornecer mais informações (e uma implementação menos eficiente, se houver interesse).

f=a=>{F=(D,n,j)=>[Z=[].concat(...D),z=Z.indexOf(j),z>-1&&[x=z%w,y=z/w|0],z>-1&&[[x-1,y-1],[x,y-1],[x+1,y-1],[x-1,y],[x+1,y],[x-1,y+1],[x,y+1],[x+1,y+1]]][n];C=q=>q.map(Q=>Q.slice());w=a[0][L='length'];l=F(a,0).filter(c=>c!='XX')[L];R=[];r=(s,d)=>{let n=`0${+s+1}`.slice(-2);N=F(d,2,n);n>l?R.push(C(d)):~F(d,1,s)?(p=F(d,3,s),p.filter(P=>P==N+'')[L]?r(n,C(d)):!~F(d,1,n)?p.map(I=>{[x,y]=I,(x<0||x>w-1||y<0||y>d[L]-1)||d[y][x]=='--'&&(D=C(d),r(D[y][x]=n,D))}):0):0};r('01',a);return R}

Experimente online!

Dom Hastings
fonte