Gere todas as chaves de comprimento n

16

Uma sequência de chaves é definida como uma sequência que consiste nos caracteres *()[]nos quais as chaves correspondem corretamente:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

Esta é uma cadeia de chaves válida:

((())***[]**)****[(())*]*

Mas estes não são:

)(
**(**[*](**)
**([*)]**

Sua tarefa é escrever um programa (ou função) que, dado um número inteiro positivo n, aceite um número como entrada e produza (ou retorne) todas as cadeias de comprimento válidas n.

Especificações

  • Você pode imprimir as strings em qualquer ordem.
  • Você pode produzir como uma lista ou uma sequência separada por um caractere diferente.
  • Seu programa deve manipular 0 corretamente. Existe uma possível string de comprimento 0, que é a string vazia "".
  • Isso é , então a resposta mais curta e válida - medida em bytes - vence.

Casos de teste

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
Esolanging Fruit
fonte
3
O número de entradas na saída é A025235
Gabriel Benamy 30/11
@GabrielBenamy Ah. Fiquei me perguntando se isso já havia sido visto antes. Interessante.
Esolanging Fruit
2
Qual é a condição vencedora? Eu assumo o programa mais curto (código de golfe).
Zgarb
Relacionado.
Martin Ender
1
Como todo mundo está assumindo que isso é código de golfe, vou marcar o desafio de acordo (como de outra forma tornaria todas as respostas existentes um pouco inúteis). Se você pretendeu um critério de vitória diferente, considere postar um novo desafio.
Martin Ender

Respostas:

3

Gelatina, 29 bytes

-3 bytes graças a @JonathanAllan

Por favor , avise-me se houver algum problema / bugs / erro ou bytes que eu possa derrubar!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Experimente online!

As soluções anteriores que eu tinha:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Explicação (Minha melhor tentativa de descrição):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter
Zacharý
fonte
Você pode salvar três bytes usando filtering ( “[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ)
Jonathan Allan
15

Prolog, 69 bytes

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

Uma das propriedades mais interessantes do Prolog é que, em muitos casos, ele é capaz de executar um programa para trás; por exemplo, em vez de testar para ver se algo é verdadeiro, você pode gerar todas as soluções verdadeiras e, em vez de verificar o comprimento de uma string, pode gerar todas as strings com um determinado comprimento. (Outra propriedade interessante do Prolog é que ela requer espaço em branco após o final de cada definição de predicado, e uma nova linha pode ser inserida tão barata quanto um espaço; assim, mesmo os programas de golfe geralmente são legíveis.)

O item acima define um predicado (o equivalente a uma função) bque testa para verificar se uma string tem um determinado comprimento e é uma "string entre chaves", conforme definido na pergunta. Especificamente, isso é feito através do suporte de gramática / regex / correspondência de padrões do Prolog, que fornece um pouco de açúcar agradável para definir esse tipo de expressão (aparentemente isso é padrão / portátil, mas eu não sabia disso enquanto escrevia a resposta originalmente e, portanto, assumimos que a resposta funcionaria apenas em uma implementação do Prolog; parece que funciona em todas as implementações que cumprem os padrões). O programa pode ser traduzido para o inglês diretamente; as duas primeiras linhas dizem "an s é uma string vazia, ou e seguido de an é um asterisco, ou entre parênteses, ou um s ; um e s seguido por um nulo " corda." s entre colchetes ". A terceira linha pode ser interpretada como" O b de N pode ser A se A for uma lista com comprimento N e A for um s

Tomei alguns cuidados para escrever s(e, portanto b), de modo que elas coincidam com cada "string cinta" em exatamente uma maneira (que é a razão que tanto se etem que existir, em vez de agrupá-los em um predicado). Isso os torna totalmente reversíveis; portanto, bpode ser usado para gerar todas as "strings" de um determinado comprimento, além de testar se uma string é uma string de um determinado comprimento (também pode ser usada uma terceira maneira, para descobrir o comprimento de uma cinta) , mas esse é quase certamente o seu modo de operação menos útil). A implementação é recursiva, por exemplo, para gerar um s , o código gerará todos os e s possíveis que não excedam o comprimento exigido da saída e anexará todos os s possíveiss que cabem no espaço restante a eles; como especifiquei antecipadamente o comprimento do argumento (em b ), o mecanismo do Prolog sabe que não pode gerar uma saída maior que o comprimento especificado, o que permite que a recursão seja encerrada.

Aqui está um exemplo do programa em operação:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

fonte
parece que deve haver algum custo para a sintaxe necessária para especificar se você deseja executar o programa "para frente" ou "para trás". perl paga 1 byte para cada bit de esse tipo de coisa
Sparr
Bem, você pode estabelecer que os argumentos no final são sempre o valor de retorno e, em seguida, reverter a ordem dos argumentos para especificar em que direção você está executando o programa. É bastante comum que os idiomas do golfe descubram o que deveriam fazer em parte, analisando se eles receberam alguma contribuição, e esse é um princípio comparável. Em geral, porém, é difícil criar regras que se apliquem a todos os idiomas possíveis; executar built-in como lengthe de appendqualquer maneira é uma parte fundamental da linguagem, e as funções do usuário geralmente fazem o mesmo.
Ah, hmm. Supus que houvesse alguma indicação em seu exemplo que desencadeou o comportamento em questão.
Sparr
Não, é inteiramente devido a quais argumentos são dados. No programa acima, eu escrevo length(A,N); if Né dado e Anão é (o que acontecerá se o predicado for usado da maneira solicitada no programa), lengthgerará uma lista Acomposta por Nelementos desconhecidos. Usar lengthpara medir o comprimento de uma lista é provavelmente mais comumente usado (embora usá-lo "para trás" seja bastante comum na programação do Prolog). A maioria dos predicados acaba funcionando da mesma maneira (a única razão pela qual eles não o fazem é se tentar revertê-los construiria um loop infinito, o que é bastante comum).
1
@ ais523 -->e DCGs em geral são o Prolog ISO padrão .
Fatalize
5

Haskell, 101 94 bytes

7 bytes salvos pelo Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Quase simples, seguindo a definição, mas com o "" caso movido.

Usar:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(O segundo cálculo leva menos de um segundo em uma máquina lenta.)

Eu também gostaria de compartilhar o resultado de outra abordagem que surgiu quando pensava em gerar funções. Ele define uma lista b de listas de seqüências de caracteres que b!!ncontêm todas as chaves de comprimento n. Da mesma forma, u!!ncontém todos os átomos do tamanho n-1. Uma coisa boa é que o código não está usando números. Não é completamente golfed: ue ipoderia ser embutido, e certamente perde algumas outras oportunidades de golfe. Infelizmente, não parece que possa ser menor do que a primeira versão, mas calcula length $ b !! 10ainda mais rápido.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)
Peneiradores cristãos
fonte
Salve dois bytes com b$n-keb$n-2 . Além disso, na linha final, você pode fazer a:b<-["()","[]"]e retornar a:s++b.
Zgarb
Ah, eu queria usar, ["()","[]"]mas não conseguia ver como melhorar o tamanho do código. Obrigado!
Christian Sievers
4

Mathematica, 116 bytes

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Explicação

Characters@"*([)]"

Encontre os caracteres da string "*([)]", dando o List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Encontre as tuplas da lista acima com o comprimento n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Função booleana sem nome para descobrir se a tupla está equilibrada:

#/."*"->Nothing

Exclua tudo "*"na entrada.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Exclua repetidamente todas as ocorrências consecutivas de "("e ")"ou "["e "]"até que a entrada não seja alterada.

... =={}

Verifique se o resultado está vazio List.

Select[ ... , ... ]

Encontre as tuplas que são fornecidas Truequando a função booleana é aplicada.

#<>""&/@

Converta cada um Listdos caracteres em Strings.

JungHwan Min
fonte
2
Um tanto inesperadamente, {x=a___,"(",")",y=b___}|{x,"[","]",y}parece funcionar.
Martin Ender
4

Python 2, 128 bytes

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Dane-se as expressões regulares recursivas - estamos usando o analisador do Python! Para verificar se, por exemplo,*(**[])* é uma cadeia de chaves, fazemos o seguinte:

  1. Faça uma string como "*", (0,"*","*", [0,0] ,0) ,"*", onde cada segundo caractere de quatro é um caractere das chaves, e os caracteres restantes são colados para tornar essa uma possível expressão em Python.

  2. eval isto.

  3. Se isso não gerar um erro, imprima s[1::4] (os caracteres da cadeia de caracteres).

Os caracteres de cola são escolhidos para que a string que eu crie seja uma expressão Python válida se, e somente se, tirar cada segundo caractere em cada quatro produzir uma string de chave válida.

Lynn
fonte
2

PHP, 149 bytes

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Usa o bom e velho método gerar todos os possíveis e, em seguida, filtrar. Use como:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4
user59178
fonte
1

Python, 134 bytes

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Função sem nome que retorna uma lista de cadeias de comprimento válidas n.
Forma todas as ntuplas de comprimento dos caracteres *()[], une-as em seqüências de caracteres usando map(''.join,...)e filtros para aqueles que têm colchetes balanceados removendo os "pares" "*"e "()", "[]"por sua nvez, e verificando se o resultado é uma sequência vazia (os ntempos são um exagero, especialmente para "*"mas é golfista).

Jonathan Allan
fonte
1

Retina , 78 bytes

A contagem de bytes assume a codificação ISO 8859-1.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

Experimente online!

Explicação

Estou gerando todas as sequências possíveis de comprimento 5 e depois filtro as inválidas.

.+
$*

Isso converte a entrada em unário, usando 1como dígito.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

Isso repetidamente ( +) substitui o primeiro ( 1) em cada linha ( %) de forma que ele faça cinco cópias da linha, uma para cada caractere possível. Isso é feito usando as substituições de prefixo e sufixo $`e$' para construir o restante de cada linha.

Esse loop é interrompido quando não há mais 1s para substituir. Neste ponto, temos todas as seqüências de comprimento possíveis N, uma em cada linha.

%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

Esses dois estágios são executados para cada linha separadamente ( %). O primeiro estágio simplesmente duplica a linha, com a ;para separar as duas cópias.

O segundo estágio é outro loop ( +), que remove repetidamente [], ()ou *da primeira cópia da string, ou remove um ponto-e-vírgula no início da linha (que só é possível depois que a string desapareceu completamente).

A`;

Seqüências de caracteres válidas são aquelas que não têm mais um ponto e vírgula na frente delas, então simplesmente descartamos todas as linhas ( A) que contêm um ponto e vírgula.

Martin Ender
fonte
Eu tentei onliny com a entrada 5: ok. Com a entrada de 6 Eu tenho uma página de erro
edc65
@ edc65 Funciona para mim, mas é claro que essa abordagem não é exatamente eficiente, por isso leva alguns segundos. Que tipo de página de erro você quer dizer?
Martin Ender
Entrada 5: resposta em 3 segundos. Entrada 6: após 7 segundos, dentro da caixa Saída, recebo a fonte html do que provavelmente é uma página de erro do meu proxy. Se é um tempo limite, então é um período muito curto de tempo limite ... Eu estava tentando conseguir um caso de teste para a direita para a entrada 6, como eu a minha resposta parece ok até de entrada 5, mas errado para 6 ou mais
edc65
@ edc65 Demora definitivamente mais de 7 segundos e o tempo limite do TIO é de um minuto. Nunca vi o erro que você descreve; vale a pena mencioná-lo no bate-papo do TIO (ou se você preferir no Gitter ou no GitHub ). Quanto à saída de referência, aqui é o que eu recebo para a entrada 6: pastebin.com/WmmPPmrc (entrada 7 leva mais de um minuto.)
Martin Ender
1

Python 3.5, 146 bytes

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

Muito longo em comparação com outras respostas, mas a mais curta que pude encontrar atualmente. Ele está na forma de uma função lambda anônima e, portanto, deve ser chamado no formato

print(<Function Name>(<Integer>))

Saídas um Python conjunto de unordered sequências representando todas as sequências de chaves possíveis do comprimento da entrada.

Por exemplo, supondo que a função acima seja nomeada G, a chamada G(3)resultaria na seguinte saída:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

Experimente Online! (Ideona)


No entanto, se, como eu, você não é realmente um fã de simplificar as coisas usando built-ins, então aqui é a minha própria originais resposta não usando qualquer bibliotecas externas para encontrar permutações, e atualmente em pé em um colossal 288 237 bytes :

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

Novamente, como a resposta da concorrência, esta está na forma de uma função lambda e, portanto, também deve ser chamada no formato

print(<Function Name>(<Integer>))

E gera uma lista Python de seqüências não ordenadas, representando todas as chaves do comprimento da entrada. Por exemplo, se o lambda fosse chamado como G(3), desta vez a saída seria a seguinte:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Além disso, este também é muito mais rápido que minha outra resposta, sendo capaz de encontrar todas as chaves de comprimento 11em cerca de 115 segundos , as de duração 10em cerca de 19 segundos , as de duração 9em cerca de 4 segundos e as de duração 8em cerca de 0,73 segundos na minha máquina, enquanto minha resposta concorrente leva muito mais que 115 segundos para uma entrada de 6.

Experimente Online! (Ideona)

R. Kap
fonte
0

05AB1E, 23 bytes

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Alguns desses recursos podem ter sido implementados após a publicação da pergunta. Todas as sugestões são bem-vindas!

Experimente online!

Quão?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string
Zacharý
fonte
Eu não sei 05AB1E, mas não poderia *também estar na matriz de remoção? E o õQcheque poderia ser substituído por algo como NÃO?
Esolanging Fruit
A primeira sugestão não salvará nenhum bytes: '*м„()„[]‚õ:vs „()„[]‚'*«õ:(não testado), pois não há comando para concatenar 3 valores AFAIK. O segundo não funcionará, pois não existe um NOT que funcionaria assim em uma string, o AFAIK. (Onde AFAIK representa "tanto quanto eu sei")
Zachary