Ligue as letras

10

Inspirado por este joguinho .

Desafio

Dada como entrada a posição inicial de uma grade (sempre 5x5), assim:

-ABCD
-A---
---C-
---BD
--E-E

Você precisa conectar as letras (mesmas letras todas juntas), removendo todos os -espaços vazios . As letras serão sempre A,B,C,D and E.

Cada par de letras deve ser conectado por uma única linha não ramificada que possa dobrar em ângulos retos (usando a mesma letra para representar a linha).

É garantido que a entrada tenha cada letra inicial exatamente 2 vezes e sempre terá todas as letras iniciais AE.

A entrada pode ser lida no stdin, ou em uma única string como arg para alguma função, ou mesmo em um array / matriz / lista de caracteres, a maneira mais conveniente para a sua linguagem de codificação.

Uma vez que este é o código, o código mais curto em bytes ganha!

Exemplo

Não há apenas uma solução para cada problema, mas as regras se aplicam a todos (sem espaço vazio e sem letras separadas). E a entrada é garantida para ter pelo menos uma saída correta.

Vamos começar a conectar as letras A:

AABCD
AA---
AA-C-
AA-BD
AAE-E

Agora, conectando as letras B:

AABCD
AAB--
AABC-
AABBD
AAE-E

Agora, conectando as letras C:

AABCD
AABC-
AABC-
AABBD
AAE-E

Agora, conectando as letras D:

AABCD
AABCD
AABCD
AABBD
AAE-E

E, finalmente, as letras E:

AABCD
AABCD
AABCD
AABBD
AAEEE

Outras amostras

input:
E--E-
BB-C-
AD---
---C-
AD---

output:
EEEEE
BBECE
ADECE
ADECE
ADEEE

input:
A----
---B-
-C-C-
-D-D-
BE-EA

output:
AAAAA
BBBBA
BCCCA
BDDDA
BEEEA
code-golf removido
fonte
@ Sp3000 não é um dup, pois esse desafio tem uma garantia de entrada correta.
Nathan Merrill
É garantido que a entrada tenha cada letra inicial exatamente 2 vezes? Sempre terá todas as letras iniciais A-E?
Ton Hospel
11
@ NathanMerrill que parece uma diferença bastante pequena. Não consigo imaginar que a verificação da solvabilidade ocuparia a maior parte do código.
Martin Ender
11
@ MartinBüttner no meu desafio, a verificação da resolubilidade é o desafio, sem necessidade de conexão. Embora os dois desafios tenham semelhanças, eles se sentem drasticamente diferentes em minha mente.
Nathan Merrill
4
Uma das minhas técnicas favoritas para algumas perguntas como essa é usar números aleatórios para preencher posições para evitar retroceder e parar se eu encontrar uma solução. Isso funciona apenas se uma solução é garantida; caso contrário, o programa pode ser executado para sempre (se uma solução for garantida, você poderá escrever o código com freqüência, para que tempos de execução longos se tornem exponencialmente mais improváveis ​​por períodos mais longos). Para esta técnica, as perguntas são muito diferentes.
Ton Hospel 15/03/16

Respostas:

4

Perl, 130 128 127 bytes

Inclui +4 para -n0(o programa não funciona na linha de comando, portanto, o -espaço também é contado)

Ligue com a entrada em STDIN:

perl -n0 connectletters.pl
E--E-
BB-C-
AD---
---C-
AD---

Teminate com ^Dou ^Zou o que fecha STDIN no seu sistema

connectletters.pl:

/-/?map{$_="$`$_$'";s%\pL%$_="$`0$'";1while do{s/[$&-](.{5}|)0|0(.{5}|)[$&-]/0$+0/s};/$&/||$&%eg;!/1/&&do$0}A..E:exit!print
Ton Hospel
fonte