Eu tenho uma caixa de música com manivela que pode tocar uma série de quatro notas. Quando eu giro a manivela, ela puxa uma das quatro cordas, dependendo da posição da manivela e da direção da curva. Quando a manivela é virada para o norte, a caixa (com suas cordas numeradas de 1 a 4) fica assim:
1 | 2
|
O
4 3
A partir daí, eu posso girar a manivela no sentido horário para puxar a corda # 2 e apontar a manivela para o leste:
1 2
O---
4 3
Como alternativa, eu também poderia ter girado a manivela no sentido anti-horário do norte para tocar a corda nº 1 e terminar com uma manivela apontando para oeste:
1 2
---O
4 3
A qualquer momento, a caixa pode tocar uma das duas notas: a próxima nota disponível no sentido horário ou a próxima nota no sentido anti-horário.
Desafio
Seu desafio é escrever um programa ou função que aceite uma seqüência de valores de notas não vazia (ou seja, números 1
até 4
) e determinar se é possível reproduzir essa sequência de notas na caixa de música. Produza um resultado verdadeiro ou falso para indicar a capacidade de reprodução ou não da entrada.
Algumas notas:
A entrada não faz suposições sobre a posição inicial inicial. As entradas
214
(começando no leste e movendo-se estritamente no sentido anti-horário) e234
(começando no norte e movendo-se estritamente no sentido horário) e ambas válidas.A manivela pode se mover livremente em qualquer direção após cada nota. Uma série da mesma nota é possível (por exemplo,
33333
) movendo-se para frente e para trás através de uma corda. A série1221441
é perfeitamente reproduzível (começando no oeste, movendo-se duas etapas no sentido horário, depois três etapas no sentido anti-horário e depois duas etapas no sentido horário).
Amostras
Alguns true
casos:
1
1234
1221
3333
143332
22234
2234
22214
1221441
41233
Alguns false
casos:
13 (note 3 is never available after note 1)
1224 (after `122`, the crank must be north, so 4 is not playable)
121 (after `12` the crank is east; 1 is not playable)
12221 (as above, after `1222` the crank is east)
43221
fonte
Respostas:
Pitão,
3027 bytesAqui está a ideia:
A manivela está sempre em uma posição meio inteiro
c
. Em cada etapa, refletimos sobre uma nota de posição inteiran
, definindoc = 2*n-c
. Sen
for válido,c
altera em ± 1 mod 8. Sen
for inválido,c
altera em ± 3 mod 8. Reduzimos cumulativamente a entrada para coletar todos os valores dec
e depois verificamos se todas as notas eram válidas. Fazemos isso para todos os valores iniciais dec
, porque é mais curto do que verificar apenas os adjacentes à primeira nota.Formatado:
Conjunto de teste .
fonte
CJam,
3431 bytesFiz isso no meu telefone, então terei que apresentar uma explicação mais tarde.A saída não é vazia, se for verdade.Experimente online | Suíte de teste
Explicação
O novo código muda um pouco o layout:
Os números pares correspondem às posições das cordas e os números ímpares correspondem às posições da manivela.
Aqui está o que acontece:
A pilha é impressa automaticamente no final. Quaisquer possíveis posições que terminam será na saída, por exemplo, para a entrada
1
, a saída é31
, o que significa que a manivela pode extremidade virada quer para a esquerda ou para cima.Se apenas CJam tivesse filtro com parâmetro extra ...
Edit: Reverter temporariamente enquanto eu me convencer de que este byte de 29 bytes funciona:
fonte
Haskell,
93 8887 bytesIsso avalia uma função anônima que pega uma string e retorna um booleano. Conjunto de teste aqui.
Explicação
A idéia é que o lambda à direita mapeie um número
a
para[[a,a+1],[a+1,a]]
, os dois possíveis "movimentos" que acionam a manivela sobre esse número, de acordo com o seguinte diagrama:Na principal função anônima, primeiro fazemos
mapM((...).read.pure)
, que converte cada caractere em um número inteiro, aplica o lambda acima a ele e escolhe um dos dois movimentos, retornando a lista de todas as seqüências de movimentos resultantes. Em seguida, verificamos se alguma dessas seqüências tem a propriedade de que o segundo número de cada movimento seja igual ao primeiro número do próximo módulo 4, o que significa que é uma sequência fisicamente possível. Para fazer isso,zip
cada um de nós move a sequência com elatail
, verifica a condiçãoall
dos pares e verifica se aany
sequência é avaliada comoTrue
.fonte
Retina, 50 bytes
Eu acho que isso funciona?
Experimente aqui.
fonte
Retina ,
127109 bytesIsso imprime
0
ou1
, consequentemente.Experimente online! (Esta é uma versão ligeiramente modificada que marca todas as correspondências na entrada em vez de imprimir
0
ou1
.)Eu tentei criar um algoritmo elegante, mas minhas primeiras tentativas não foram capazes de contornar o retorno e a implementação do retorno é irritante ... então usei uma linguagem que faz o retorno para mim, onde eu só preciso codificar um solução válida. Infelizmente, a codificação é bastante detalhada e redundante ... Tenho certeza que isso pode ser reduzido.
Enquanto tento descobrir algo mais limpo, se alguém quiser entender como isso funciona, aqui está uma versão um pouco mais legível:
E aqui está uma dica:
fonte
MATL ,
5755 bytesIsso usa a versão atual (10.2.1) , que é anterior a esse desafio.
EDIT (17 de janeiro de 2017): devido a alterações no idioma,
v
precisa ser substituído por&v
etL3$)
porY)
(além disso, algumas outras melhorias podem ser feitas). O link a seguir inclui essas duas modificaçõesExperimente online!
Explicação
Isso se baseia em duas das minhas ferramentas favoritas para o código de golfe: força bruta e convolução .
O código define o caminho seguido pela manivela em termos de coordenadas
0.5
,1.5
etc. Cada número indica a posição da manivela entre as notas. O código primeiro cria uma matriz de caminhos com todos os caminhos possíveis que começam com a primeira nota da sequência de entrada. Cada caminho é uma coluna nessa matriz. Este é o componente de força bruta .A partir dessa matriz de caminho, é obtida uma matriz de notas , onde cada coluna é uma sequência realizável de notas tocadas. Por exemplo, o movimento da posição
0.5
para1.5
produz uma nota1
. Isso consiste em tomar a média entre as posições e depois aplicar uma operação do módulo 4. A média de execução ao longo de cada coluna é feita com uma convolução 2D .Finalmente, o programa verifica se alguma coluna da matriz de notas coincide com a entrada.
fonte
Pyth, 43
Suíte de teste
Provavelmente isso é muito jogável, e também não é o algoritmo ideal para o golfe (espero que enumerar todos os caminhos seja mais curto?) ... De qualquer forma, se você encontrar algum erro no algoritmo, informe-me, acho que deve funcionar, mas já estive errado antes!
Vou explicar meu algoritmo usando a entrada de exemplo de
1221
. Este primeiro programa mapeia os dígitos contra os seus sucessores, assim:[[1,2],[2,2],[2,1]]
. Em seguida, ele recebe suas diferenças mod4
(Pyth obtém o resultado que coincide com o sinal do argumento direito de%
, então isso é sempre positivo):[3,0,1]
. Em seguida, os resultados estão divididos sobre0
e ter2
subtraído de cada um deles:[[1],[-1]]
.Agora que a configuração está concluída, criamos uma lista
[-1,1,-1...]
e sua negação[1,-1,...]
, ambas do mesmo tamanho que a matriz resultante de antes. Em seguida, para cada uma dessas listas, execute a subtração definida entre os elementos da lista e a lista gerada na etapa anterior. Então, se um dos resultados contiver apenas listas vazias, produziremos true.fonte
1221221
e1221441
?1221221
é falso e1221441
dá verdade geral, mas se eu entendo que você quer o resultado após essa etapa no algoritmo? Se for esse o caso, ele fornece: de[3, 0, 1, 3, 0, 1]
para[[3], [1, 3], [1]]
e[3, 0, 1, 1, 0, 3]
para[[3], [1, 1], [3]]
. Deixe-me saber se você quer algo mais explicou :)[[1], [-1, 1], [-1]]
e a[[1], [-1, -1], [1]]
partir daqui, você pode ver que o primeiro não tem listas que alternam entre-1
e1
enquanto a outra lista, dando o resultado final. O algoritmo é um pouco obtuso, mas basicamente é o mapeamento das mudanças de direção para0
e direção de+/-1
, em seguida, verificando se nenhum salto é feito e as direções fazem sentido.Matlab,
279180 bytesUma solução bastante preguiçosa, mas a mais curta que consegui encontrar. Criei uma matriz especial: quando você codifica o estado do arrancador e a última string a ser arrancada, ele retorna um vetor, que codifica a nova posição do arrancador e se a arrancada anterior era possível. Agora, passamos por todas as notas das duas possíveis posições iniciais e vemos se uma delas resulta em uma melodia tocável. Provavelmente pode ser jogado muito mais.
Fonte expandida e explicada:
fonte
ES6,
104100 bytesEditar: salvou 4 bytes graças a @DigitalTrauma.
Esta é uma reescrita completa, pois minha abordagem anterior foi falha.
Começo reduzindo todas as execuções de dígitos para 1 ou 2, dependendo da existência de um número ímpar ou par na execução. Em seguida, procuro todas as combinações ilegais:
13|24|31|42
(lados opostos)3[24]{2}1
como3221
e3441
são ilegais4xx2
,1xx3
e2xx4
ondex
é um dos dígitos ausentes(.).\1
como coisas121
ilegais (111
foi reduzida para1
mais cedo)Se não houver pares ou "triplos" ilegais, toda a cadeia é legal (a prova por indução é deixada como exercício, porque aqui é tarde da noite).
Tentei simplificar
3[24]{2}1|1[24]{2}3
usando uma afirmação negativa, mas acabou sendo mais longa.fonte
f("1122") => true
@DigitalTraumaf("1221221")
gera a resposta errada, então terei que repensar.[24][24]
para(2|4)\1
mas eu não tinha testado adequadamente. Me desculpe por isso.[24][24]
para[24]{2}
?JavaScript (ES6), 80 bytes
Explicação
i%4
é a posição atual da manivela:Recuado e Comentado
Teste
fonte
|
funciona neste caso?(x.map(...),v)
. Funciona porque a matriz para a qual osmap
retornos são convertidos0
e0|v == v
.Lua ,
146 142 108 162 159 149 144 135 132 118113 bytesRetorna verdadeiro ou falso, considerando uma sequência de números entre 1 e 4. (Não processa dados ou números fora do intervalo.
Simplesmente rastreia qual foi o último movimento e verifica se esse movimento é uma reversão do último movimento (IE, 121 ou 12221) ou se a distância em movimento é maior do que possível.
EDIT 1 :
Salvo 6 bytes. Esqueci que
if (int) then
retorna true se int for diferente de zero.Portanto:
muda para:
Também salvou alguns bytes reestruturando.
EDIT 2 :
Estou lentamente descobrindo isso. Estive lendo a documentação aqui: http://www.lua.org/pil/ E uma das páginas mais úteis para o golfe é http://www.lua.org/pil/3.3.html
Em particular, isso é muito útil:
O que isso significa para mim é que posso prosseguir e remover minha declaração para q ( que foi inicialmente definida como 0 ), pois ela será considerada "falsa" até ser definida. Então, guardo mais alguns bytes com isso.
Outra coisa que vale a pena mencionar, embora eu não a use, é que se você deseja trocar valores em Lua, você pode simplesmente fazer isso
a,b=b,a
sem a necessidade de uma variável temporária.EDIT 3
Então, através de alguma reconstrução inteligente e de uma nova função, eu tenho a contagem de bytes em mais 9.
Melhor modo para receber entrada
Se você precisar ler uma lista de números e executar operações neles, um de cada vez, poderá usar:
Quando comparado à sua alternativa usando string: sub, você pode ver o valor do golfe (ou uso geral):
Reestruturar funções ou seqüências de caracteres
Segunda coisa, se você possui várias declarações em uma linha e um dos valores é uma função ou se possui uma condição na qual você compara um número ao resultado de uma função como esta:
reestruturando-o para que os parênteses de fechamento sejam o último caractere na condição ou declaração, você pode cortar um caractere assim:
Retornar condições que são iguais a Verdadeiro ou Falso em vez de 'Verdadeiro' ou 'Falso'
Encontrei uma maneira meio divertida de reduzir ainda mais minha contagem de bytes. Se você precisar retornar verdadeiro ou falso, poderá retornar uma declaração que seja igual a verdadeiro ou falso que tenha menos caracteres que "verdadeiro" ou "falso".
Por exemplo, compare:
Para:
fonte
121
deve gerar false.MATL, 49 bytes (não concorrentes 1 )
1. A resposta (ab) usa a indexação menos rigorosa das versões mais recentes do MATL e não teria funcionado no momento em que esse desafio foi lançado.
Experimente online! .
Eu vi esse desafio no Best of PPCG 2016 e percebi que isso poderia usar meu operador favorito :
Ou,
diff
no MATLAB / Octave (usarei livremente a terminologia MATLAB / Octave na minha explicação, pois é mais fácil ler para humanos). Este comando calcula a diferença entre elementos em um vetor ou, nesse caso, em uma matriz de caracteres.Para esse problema, as diferenças exibem um padrão interessante. Observe que
Para o padrão de diferença (ignorando a
1-4
transição por enquanto), isso significa queEu implementei isso, para cada matriz, encontrando o primeiro zero. Eu aparei o zero e multipliquei todos os elementos depois dele
-1
. Para o resultado final, isso significa que todos os elementos devem ter o mesmo sinal. Obviamente, há a pequena questão da-3
igualdade+1
e2
não é permitida em geral. Resolvi isso tomando a união do conjunto com o resultado[1 -3]
e verificando se o tamanho é 2 (ou seja, nenhum elemento não permitido 'entrou' no conjunto por meio da união). Repita para[-1 3]
e verifique se um (ou ambos, no caso de uma entrada de 1 comprimento) é verdadeiro.fonte
M
, da última vez que tentei, funcionou de maneira diferente do esperado, então eu o ignorei por enquanto. É correto dizer que precisa ser3M
porque, então, recebo a entrada de não)
, não:
mas deq
(pulandow
como não é uma função normal )?w
é ignorado porque não é uma função normal. As funções normais que não aceitam entradas também seriam ignoradasPython (3.5)
160151150 bytesUma solução recursiva
Ungolfed sem lambda
Giro toda a caixa em vez da manivela. A posição da manivela está entre o primeiro e o segundo caracteres da cadeia c. Preciso testar todas as posições iniciais da manivela.
Truque usar para girar a corda
A maneira usual de rotacionar uma string em python (
s[i:]+s[:i]
) também precisa repetir o índice e a string. Nesse caso, duplico a string e recorte os primeiros caracteres.Casos de teste
fonte
3"[i:]) for
.Python 2 , 65 bytes
Experimente online!
fonte
JavaScript (ES2015),
1109515 bytes salvos por Neil! Versão original não destruída:
Testes: https://jsbin.com/cuqicajuko/1/edit?js,console
fonte
(s,d)=>(h=s[0],t=s.slice(1),g=t[0],!g||(d?g==h?p(t,-d):g%4==(h-d)%4&&p(t,d):p(s,1)||p(s,-1)))
Código de máquina de Turing, 395 bytes
Experimente online!
Esta é basicamente uma abordagem baseada em estado:
a
,b
,c
, Ed
são "estados indecisos" que ocorrem apenas no inícioN
,E
,S
, EW
são os "estados decidiram", obviamente, de pé paraN
Orth,E
ast,S
outh, eW
est.fonte
Terça, 203 bytes
Não consigo pensar em como jogar golfe tão longe.
Se a sequência de notas for possível, a saída será finalizada; caso contrário, a saída estará vazia.
fonte
Prolog (SWI) , 117 bytes
Define um predicado
p
que obtém êxito nas entradas reproduzíveis (fornecidas como uma lista de números inteiros) e falha nas que não são reproduzíveis. Experimente online!Explicação
a
define uma relação de adjacência entre a notaN
e a posição da manivelaP
. Nós definimos posição p para ser entre notas p e p + 1 . Assim, uma posição é adjacente à notaN
seN
(P=N
); ouN=1,P=4
); ou!
) e a posição é igual aN-1
(P is N-1
).m
pega uma lista de notas e tenta gerar uma lista de posições que tocarão essas notas.A
é a nota que acabou de ser tocada,B
é a nota a ser tocada;X
é a posição atual da manivela,Y
é a próxima posição da manivela. Um movimento é válido sea(A,X)
);a(B,X)
);a(B,Y)
); eX\=Y
).Se tudo isso acontecer, recorra. Se conseguirmos chegar a qualquer nota (
m([_],_)
), a sequência de notas é reproduzível.Para esta pergunta, apenas nos importamos se existe uma sequência de movimentos, por isso, definimos
p
chamarm
e descartar a lista gerada de posições de manivela.Veja uma versão não destruída e verifique todos os casos de teste aqui .
fonte