Dada uma sequência de entrada que consiste apenas em letras, retorne o tamanho da etapa que resulta na quantidade mínima de etapas necessárias para visitar todas as letras em ordem sobre um alfabeto de agrupamento, iniciando em qualquer letra.
Por exemplo, pegue a palavra dog
. Se usarmos um tamanho de etapa 1, terminamos com:
defghijklmnopqrstuvwxyzabcdefg Alphabet
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
defghijklmnopqrstuvwxyzabcdefg Visited letters
d o g Needed letters
Para um total de 30 etapas.
No entanto, se usarmos um tamanho de etapa 11, obteremos:
defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg
^ ^ ^ ^ ^ ^
d o z k v g Visited letters
d o g Needed letters
Para um total de 6 etapas. Essa é a quantidade mínima de etapas, portanto, o resultado do retorno dog
é o tamanho da etapa; 11
.
Casos de teste:
"dog" -> 11
"age" -> 6
"apple" -> 19
"alphabet" -> 9
"aaaaaaa" -> 0 for 0 indexed, 26 for 1 indexed
"abcdefga" -> 1 or 9
"aba" -> Any odd number except for 13
"ppcg" -> 15
"codegolf" -> 15
"testcase" -> 9
"z" -> Any number
"joking" -> 19
Regras
- A entrada será uma string ou matriz de caracteres não vazia, consistindo apenas nas letras
a
paraz
(você pode escolher entre maiúsculas ou minúsculas) - A saída pode ser 0 indexada (ou seja, o intervalo
0-25
) ou 1 indexada (1-26
) - Se houver um empate, você pode imprimir qualquer tamanho de etapa ou todos eles
- Isso é código-golfe , então a menor quantidade de bytes para cada idioma vence!
Respostas:
Carvão , 41 bytes
Experimente online! Link é a versão detalhada do código. Indexado a 0. Explicação:
Passe pelos 26 tamanhos de etapa. (Na verdade, faço um loop sobre o alfabeto minúsculo aqui e uso a variável index.)
Faça um loop sobre cada caractere da entrada após o primeiro.
Faça um loop 26 vezes e gere a sequência de caracteres resultante, executando 26 etapas no tamanho de etapa especificado, começando (indexado 0) com o caractere anterior da entrada.
Encontre a posição do caractere atual da entrada nessa sequência ou -1 se não for encontrado.
Tome a soma de todas as posições, a menos que uma não tenha sido encontrada; nesse caso, use -1.
Salve as somas.
Encontre a soma mínima não negativa.
Encontre o tamanho do primeiro passo com essa soma e faça a saída.
fonte
JavaScript, 143 bytes
Experimente online!
Graças a Shaggy, o uso
[...Array(26).keys()]
salva 9 bytes.fonte
Geléia ,
282623 bytesA saída é indexada em 0. A entrada é uma cadeia de bytes e pode ser, de qualquer forma, mas maiúscula é muito mais rápida.
A entrada de letra única deve ser especificada e custa 2 bytes. ._.
Experimente online!
Observe que essa é uma abordagem de força bruta; as entradas com quatro ou mais letras atingem o tempo limite no TIO. O conjunto de testes inclui
_39
"eficiência".Como funciona
fonte
Geléia , 17 bytes
A entrada é um bytestring em STDIN, a saída é indexada em 1.
Experimente online!
Como funciona
fonte
JavaScript (Node.js) ,
123 121 116114 bytesExperimente online!
Comentado
s[k++ >> 5]
fonte
Ruby ,
12111411210810289 bytesExperimente online!
Indexado a 0. Recebe a entrada como uma matriz de caracteres.
Graças ao ASCII-only para idéias de golfe com valor de 12 bytes.
fonte
p,=*s
truque, mas não tenho tanta certeza sobre a robustez teórica de uma solução com uma pontuação de penalidade codificada ... Então, mudei a constante para infinito (embora seu valor permita outros 2 bytes de diferença) )Python 2 ,
230222216194169 bytesExperimente online!
-22 bytes de tsh
-39 bytes de Jo King
Versão mais antiga com explicação:
Experimente online!
Isso seria mais curto em um idioma com um número primo de letras (não precisaria doEsse envio agora usafloat('inf')
tratamento de loops infinitos). Na verdade, esse envio ainda seria necessário para lidar com cadeias de caracteres como "aaa".26*len(s)
como limite superior, o que interrompe loops infinitos.Esse envio é indexado em 0 (retorna valores de 0 a 25, inclusive).
f
pega uma sequência (n maiúscula) e retorna a opção Alfabeto ótimot
é uma função auxiliar que pega a sequência de caracteres e o passo de um alfabeto e retorna o número de saltos necessários para finalizar a sequência (ou,26*len(s)
se impossível).fonte
while a!=A(c)and S<len(s)*26:
e você pode removerif a==i:return float('inf')
, poislen(s)*26
é o limite superior de qualquer resposta.Vermelho , 197 bytes
Experimente online!
fonte
05AB1E (legado) ,
332726 bytesUsa a versão herdada porque parece haver um erro quando você deseja modificar / usar o resultado após um mapa aninhado na nova versão 05AB1E.
Saída indexada em 0.
Experimente online ou verifique todos os casos de teste .
Explicação:
fonte
Python 3 ,
191178162 bytesObrigado a todos por todas as suas dicas! isso parece muito mais parecido com o golfe.
Experimente online!
E meu código original, se alguém estiver interessado.
Transforma a palavra em uma lista de valores ASCII e itera pelos tamanhos de etapa de 0 a 25, verificando quantas etapas são necessárias para esgotar a lista (existe um limite para interromper loops infinitos).
O número de etapas é adicionado à lista a .
Após o loop for grande, o índice do menor valor em a é impresso. Isso é igual ao valor de i (o tamanho da etapa) para a iteração do loop, QED.
fonte
range(26)
basta - você não precisa especificar o início, pois 0 é o padrão;a.append(n)
poderia sera+=[n]
; a primeira linha seria mais curta como mapaw=list(map(ord,input()))
(na verdade, com seu algoritmo atual, no Py2 você também pode deixar olist(...)
invólucro); evitar quebras de espaçamento / linha adicionais, tanto quanto possível (por exemplo, há necessidade de novas linhas em Oneliners:if p>122:p-=26
)n>99
parece suspeito, é uma constante arbitrária para romper o loop inifinito? Então provavelmente deve ser algo como 26 * len (w), como você nunca sabe, quão grande será a entrada.list(...)
no Py3 e também de um extraif
: 165 bytes . Além disso, dê uma olhada neste tópico de dicas , tenho certeza de que você melhorará bastante suas habilidades usando conselhos de lá!while p!=c and n>len(w)*26:
e se livrar dessa última declaração if por -8 bytes.n+=1
ep+=i
em linhas separadas paran+=1;p+=i
uma.