Suponha que um dia você esteja vasculhando sua grande caixa de cabos e adaptadores de computador não utilizados (USB para USB mini, VGA para DVI etc.). Em todos os lugares, há cabos emaranhados que bagunçam bastante, e você quer saber se poderia simplificar as coisas, conectando todos os cabos em um único fio longo e depois enrolando-o.
A questão é: é possível conectar todos os seus cabos e adaptadores em uma linha longa como esta? Obviamente, nem sempre é possível, por exemplo, se você tivesse apenas dois cabos com plugues completamente diferentes, eles não poderiam ser conectados. Mas se você tiver um terceiro cabo que possa se conectar aos dois, poderá amarrar todos os seus cabos.
Você não se importa com o tipo de plugue nas extremidades do fio. Eles não precisam se conectar para formar um loop. Você só quer saber se é possível fazer o fio todo, e se for, como fazê-lo.
Desafio
Escreva um programa ou função que utilize uma cadeia de linhas múltiplas, onde cada linha representa um dos cabos que você possui. Um cabo é composto de um ou mais traços ( -), com um plugue em cada extremidade. Um plug é sempre um dos 8 caracteres ()[]{}<>.
Portanto, estes são alguns cabos válidos:
>->
(--[
}-{
<-----]
(---)
Mas estes não são:
-->
(--
)--
[{
---
Ao conectar cabos, apenas plugues do mesmo tipo de suporte podem ser conectados juntos.
Portanto, estas são algumas conexões de cabo válidas:
...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...
E estes são inválidos:
...---()---...
...---)(---...
...---{]---...
...---{[---...
...---><---...
...--->)---...
Se todos os cabos da entrada puderem ser reorganizados e conectados juntos em um fio longo, faça a saída desse fio para o padrão de saída em uma linha (com uma nova linha à direita opcional). Quando existem várias soluções, você pode escolher qualquer uma delas para a saída. Se não for possível criar um único fio, não produza nada (ou produza um texto vazio com uma nova linha à direita opcional).
Por exemplo, se a entrada for
[-->
{---]
>----{
a saída pode ser
[-->>----{{---]
onde todos os cabos estão amarrados juntos.
No entanto, se a entrada fosse
[-->
{---]
os cabos não podem ser conectados, portanto não haverá saída.
Observe que os cabos podem ser girados o tempo necessário para fazer as conexões. por exemplo, [-->e <--]são efetivamente o mesmo cabo, porque eles podem fazer o mesmo tipo de conexões. Algumas saídas podem depender da inversão dos cabos de entrada.
Por exemplo
(-[
}--]
poderia ter saída
(-[[--{
onde o segundo cabo é invertido, ou
}--]]-)
onde o primeiro cabo é invertido.
(Observe que, em geral, o lançamento de toda a saída é válido, pois é o mesmo que o lançamento inicial de cada cabo individualmente.)
É claro que os comprimentos dos cabos na saída devem corresponder aos comprimentos dos cabos de entrada correspondentes. Mas os cabos podem ser reordenados e girados o quanto você quiser, a fim de formar o fio todo. A entrada sempre conterá pelo menos um cabo.
O código mais curto em bytes vence.
Casos de teste
Casos com saída:
[-->
{---]
>----{
gives
[-->>----{{---]
or
[---}}----<<--]
(-[
}--]
gives
(-[[--{
or
}--]]-)
(-)
gives
(-)
[--{
gives
[--{
or
}--]
[-]
]-[
gives
[-]]-[
or
]-[[-]
[----->
)------------[
{--<
}---)
could give
[----->>--}}---))------------[
or
>--}}---))------------[[----->
or
}---))------------[[----->>--}
or
{--<<-----]]------------((---{
etc.
>-->
>->
>--->
could give
>-->>->>--->
or
>--->>-->>->
or
>->>-->>--->
or
<--<<---<<-<
etc.
(-]
]->
>-}
}-)
)-[
[-<
<-{
{-(
could give
(-]]->>-}}-))-[[-<<-{{-(
or
{-((-]]->>-}}-))-[[-<<-{
or
<-{{-((-]]->>-}}-))-[[->
etc.
Casos sem saída:
[-->
{---]
[-]
[-]
(-]
]->
}-)
>->
>-->
]---]
[-------------------]
]-------------------[
[-----------------]
[-----------------]
{--[
]--}
Respostas:
Ilegível , 3924 bytes
Esta é a primeira vez que implementei uma estrutura semelhante à pilha de chamadas no ilegível.
(A primeira versão disso tinha mais de 5300 bytes, apenas para dar uma idéia do quanto eu joguei isso.)
Explicação
Considere esta entrada de exemplo:
Durante a maior parte da execução, a fita é apresentada da seguinte maneira:
As células de 0 a 5 são locais para várias variáveis.
A célula 6 em diante contém todas as informações sobre o conjunto de cabos em sua caixa:
As células restantes após o "terminador zero" contêm a pilha. Cada "stackframe" é uma célula única que aponta para a primeira célula de um cabo (a célula "start plug"). No exemplo acima, quando o programa decidir que encontrou uma solução, a pilha conterá 6 (referente ao
>--{primeiro cabo) e 21 (referente ao{---]espelho do segundo cabo).O programa prossegue em três etapas principais:
O primeiro estágio (leia a entrada e gere a estrutura dos cabos) usa apenas as células # 1 (que chamarei
p) e # 2 (que chamareich) e opera em um loop while da seguinte maneira:Enquanto condição: incremente
pem 6, leia o próximo caractere (plug inicial) na célula*pe verifique se não é-1(EOF).Leia os caracteres subseqüentes
*(p+2)e conte-os*(p+1)até encontrar algo diferente de-(hífen). Nesse ponto,*(p+1)conterá o número de hífens (comprimento do cabo) e*(p+2)o último caractere não hífen (o plugue final). (Também copiamos os caracteres de hífen na célula nº 5 para que possamos acessar esse código ASCII posteriormente no estágio de saída.)Em um loop while, encontre o plugue do espelho e armazene-o em
*(p+3), depois aumentepem 2, até que*pseja zero. O loop fica assim no pseudocódigo:Esse loop sempre realiza duas iterações (o plugue inicial e o final) e armazena os resultados na quarta e sexta célula deste cabo. Agora, se você prestar atenção, percebe que a sexta célula é realmente o local correto para o plugue final espelhado, mas o plugue de início espelhado está na célula rotulada como “cabo original indicando booleano”. Isso é bom porque precisamos que essa célula seja um valor diferente de zero.
Como
pacaba de ser incrementado um total de 4, agora está apontando para a célula rotulada como "cabo indicador booleano em uso". Defina*(p+3)com o valor de*(p-1). Isso coloca o plugue de início espelhado no lugar certo.Leia (e descarte) mais um caractere (que esperamos ser uma nova linha, mas o programa não verifica isso).
pinicialmente começa em 0, mas é incrementado em 6 dentro da condição while, portanto, os dados do cabo começam na célula # 6.pé incrementado por 4 dentro do corpo do loop e, portanto, um total de 10 para cada cabo, exatamente o que precisamos.Durante a segunda fase, as células # 0-4 são ocupados por variáveis que eu vou chamar
a,p,q,m, enotdone. (A célula nº 5 ainda se lembra do código ASCII do hífen.)Para se preparar para o estágio 2, precisamos
*pvoltar para 0 (a célula denominada "terminador zero") para que ele possa atuar como o terminador da lista de cabos; também definimosq(que é o ponteiro da pilha) comop+1(ou seja, a célula após o "zero terminator"; é aqui que a pilha é iniciada);*qpara 1 (o primeiro item na pilha; por que 1 se tornará aparente mais tarde); enotdonepara 1. Tudo isso é feito em uma única declaração:O segundo estágio também é um loop while. Sua condição é simples
notdone. Em cada iteração desse loop while, qualquer uma das quatro coisas a seguir pode acontecer:*qpara outro cabo elegível (que marcamos prontamente como “em uso” junto com o seu gêmeo) e depois recursar (ou seja, criar um novo stackframe).*qporque não existe mais cabo elegível; portanto, precisamos voltar atrás (remova um quadro de pilha e marque o cabo anterior e seu gêmeo como não mais em uso).*qporque não existe mais cabo elegível e não podemos voltar atrás porque chegamos ao fundo da pilha. Isso significa que não há solução.O corpo do loop verifica cada uma dessas quatro condições nesta ordem. Aqui estão os detalhes:
Defina
mepcomo 1 e em um loop while, aumentepem 5 (iterando através dos cabos) e verifique se*(p+4)("em uso") está definido. Caso contrário, definamcomo 0. No final desse loop,minforma se todos os cabos estão em uso. Nesse caso, definanotdonecomo 0 para finalizar o loop principal. Caso contrário, continue na etapa 2 abaixo.Defina
pcomo*q(o cabo na parte superior da pilha) e em um loop while semelhante ao acima, aumentepem 5 para percorrer os cabos. A partir de*qgarante que consideramos apenas aqueles que ainda não consideramos antes; no entanto, lembre-se de que o valor inicial para um novo quadro de pilha é 1; portanto, o primeiro cabo observado é o da célula 6, que é realmente o primeiro cabo.Para cada cabo, precisamos verificar
*(p+4)se ele ainda não está em uso e também se*(q-1)é zero (o que significa que estamos no fundo da pilha, para que não haja restrições no plugue de partida) ou*p(no início do cabo) plugue) é igual a*(*(q-1)+2)(o plugue final do cabo logo abaixo na pilha). Verificamos a igualdade definindoapara*(*(q-1)+2)empara*p+1e, em seguida, diminuindo os dois em um loop while. A+1é porquemé decrementado no interior da condição enquanto, por isso, é diminuída uma vez que mais do quea. Seafor zero no final, os dois plugues são iguais.Portanto, se
*(q-1)foi zero ou a comparação de igualdade foi bem-sucedida, o cabo é elegível. Defina*qparapsubstituir o cabo na parte superior da pilha pelo novo; definamo mesmo para indicar que encontramos um cabo correspondente; e depois diminuap. Esse decréscimo é um pequeno truque para fazer com que o loop while (iterando pelos cabos) termine mais cedo; ele aumentarápnovamente em 5, levando-o para a célula que contém o sinalizador “em uso” deste cabo, e sabemos que é zero porque acabamos de verificar isso. Finalmente, após o loop while de iteração de cabo, verificamos semnão é zero.pNesse caso, encontramos um cabo correspondente e apontamos para a bandeira "em uso" desse cabo correspondente. Defina como 1 para marcar como em uso. Definir também*(*(p-1) ? p+5 : p-5)1 para marcar seu gêmeo como em uso. Por fim, incrementeqe defina o novo*qcomo 1 para criar um novo quadro de pilha.Se, após o loop while de iteração de cabo, acharmos
mzero, não há mais cabos correspondentes, portanto, precisamos voltar atrás. Decrementeqpara mover a pilha para baixo e verifique se ainda está apontando para um cabo (um valor diferente de zero). Nesse caso, marque esse cabo e seu conector duplo como não mais em uso. (Armazenamos o valor de*qinppara tornar essa expressão mais curta no código.)Se, após decrementar
q, descobrimos que ele aponta para um valor zero, então esse é o "zero terminator", o que significa que estamos com a pilha abaixo. Concluímos que não há solução. Definimosnotdonecomo 0 para finalizar o loop principal.O terceiro estágio é o estágio de saída. Há duas coisas que podem acontecer:
Convenientemente, se não houvesse solução,
pé zero porque o definimos como o valor de*qantes de verificar isso como zero; e se não era uma solução,pestá apontando para a “terminator zero”, porque só iterado através dos cabos, então agora nós podemos usarppara percorrer a pilha. Portanto, basta percorrer a pilha, produzindo para cada cabo o plugue de partida (*(*p)), os hífens (diminuindo*(*p+1)em um loop while; e usando o código ASCII do hífen armazenado na célula # 5) e o plugue final (*(*p+2)). Não importa que isso destrua as informações sobre o comprimento do cabo; não precisamos mais disso.fonte
CJam, 67
Experimente online
Nota: o link está usando o código mais recente do repositório (enviado, mas ainda não foi lançado), pois contém uma correção de bug.
Explicação:
O programa simplesmente tenta todas as permutações e todas as orientações dos cabos.
fonte
(-] ]-> >-} }-) )-[ [-< <-{ {-(.JavaScript (ES6), 206
Função recursiva
Mais legível
Teste
fonte
Javascript, 800 bytes
Longe de ser uma solução otimizada, mas aqui está um hack rápido em javascript (sem ecma5 sofisticado ou qualquer coisa, porque eu não sei).
Sem jogar, aqui está ... Tenho certeza de que pelo menos 2 loops são desnecessários aqui e que verificar se há uma entrada de elemento único no topo e uma correspondência de elemento único na parte inferior é fedido ... mas parece funcionar e processa as entradas de teste.
fonte
s.charAt(x)===s[x]Python 3, 217 bytes
( Demonstração em Ideone )
fonte
(-] ]-> >-} }-) )-[ [-< <-{ {-(?Lua, 477 bytes
Aceita cabos como argumentos de linha de comando
fonte
Python 3.5,
448432427424286311 bytes:( +25, pois houve um erro em que a saída pode ser maior do que deveria para algumas entradas )
Funciona perfeitamente!
exceto para entradas com 7 ou mais valores. Demora muito tempo para eles, provavelmente porque deve passar por todas essas permutações da entrada mais a entrada revertida . Vou tentar consertar isso se e quando puder, mas por enquanto, isso parece ser bom o suficiente.Tudo está bem agora! Se ao menos eu pudesse usar essetry-exceptbloco na compreensão da lista, ele poderia ser um pouco mais curto e parecer muito melhor. No entanto, ele agora trabalha para todos os casos de teste, e, melhor de tudo, ele usa nenhuma importações! :)Experimente online! (Ideona) (284 bytes aqui)
(Dica: para tentar, basta selecionar "bifurcação" e inserir suas opções, separadas por espaço e selecione "executar")
Explicação
Basicamente, o que está acontecendo é ...
Bé criada a partir da entrada, dividindo-a no espaço em branco em seus "cabos" componentes.Mé uma string que criei que, quando avaliada, retorna uma lista com base emBque contém todos os cabos, mas desta vez para trás .Mé finalmente concatenada consigoBmesma para criar uma lista,f, com todas as orientações possíveis dos "cabos".dé criada, que será inicializada com o primeiro valor (valorf[0]) def.dsão iterados e o último caractere de cada valor é comparado com o primeiro caractere de cada elementofe, quando uma correspondência é encontrada, esse caractere é exibido (ou removido) e retornado da listaf. Isso acontece até que aIndexErrorseja aumentado ou o comprimento da listadexcedaBe aNameErrorseja aumentado após a chamada paraE, os quais são manipulados e, em seguidad, o conteúdo da lista seja unido a uma string e retornado enquanto o comprimento da listadfor maior. igual ou igual ao comprimento da listaB. Caso contrário, uma string vazia é retornada (''), poisdnão possui o mesmo comprimento queBsignifica que todos os "cabos" na listaBnão pode ser unido em um "cordão" longo.fonte
<!-- language: lang-python -->. O que isso muda?