Passo ideal do alfabeto

30

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 apara z(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 é , então a menor quantidade de bytes para cada idioma vence!
Brincadeira
fonte
Precisamos lidar com entrada vazia?
pizzapants184
1
@ pizzapants184 Não. Atualizei a pergunta para especificar que a entrada não ficará vazia #
Jo King
Podemos considerar a entrada como uma matriz de caracteres?
Shaggy
@Shaggy Claro que você pode
Jo King
Existe uma razão para isso usar letras em vez de números?
Assistente de trigo

Respostas:

6

Carvão , 41 bytes

≔EEβEθ∧μ⌕⭆β§β⁺⌕β§θ⊖μ×κξλ⎇⊕⌊ιΣι⌊ιθI⌕θ⌊Φθ⊕ι

Experimente online! Link é a versão detalhada do código. Indexado a 0. Explicação:

Eβ

Passe pelos 26 tamanhos de etapa. (Na verdade, faço um loop sobre o alfabeto minúsculo aqui e uso a variável index.)

Eθ∧μ

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.

E...⎇⊕⌊ιΣι⌊ι

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.

I⌕θ...

Encontre o tamanho do primeiro passo com essa soma e faça a saída.

Neil
fonte
5

JavaScript, 143 bytes

w=>(a=[...Array(26).keys(m=1/0)]).map(s=>~[...w].map(c=>(t+=a.find(v=>!p|(u(c,36)+~v*s-u(p,36))%26==0),p=c),p=t=0,u=parseInt)+t<m&&(m=t,n=s))|n

Experimente online!

Graças a Shaggy, o uso [...Array(26).keys()]salva 9 bytes.

tsh
fonte
144 bytes
Shaggy
4

Geléia , 28 26 23 bytes

S;þḅ26ŒpṢƑƇIŻ€S:g/ƊÞḢg/

A 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

S;þḅ26ŒpṢƑƇIŻ€S:g/ƊÞḢg/  Main link. Argument: b (bytestring)

S                        Take the sum (s) of the code points in b.
 ;þ                      Concatenate table; for each k in [1, ..., s] and each c in
                         b, yield [k, c], grouping by c.
   ḅ26                   Unbase 26; map [k, c] to (26k + c).
      Œp                 Take the Cartesian product.
        ṢƑƇ              Comb by fixed sort; keep only increasing lists.
           I             Increments; take the forward differences of each list.
            Ż€           Prepend a 0 to each list.
                         I returns empty lists for single-letter input, so this is
                         required to keep g/ (reduce by GCD) from crashing.
                   Þ     Sort the lists by the link to the left.
              S:g/Ɗ      Divide the sum by the GCD.
                    Ḣ    Head; extract the first, smallest element.
                     g/  Compute the GCD.
Dennis
fonte
4

Geléia , 17 bytes

ƓI%
26×þ%iþÇo!SỤḢ

A entrada é um bytestring em STDIN, a saída é indexada em 1.

Experimente online!

Como funciona

ƓI%            Helper link. Argument: m (26 when called)

Ɠ              Read a line from STDIN and eval it as Python code.
 I             Increments; take all forward differences.
  %            Take the differences modulo m.


26×þ%iþÇoSSỤḢ  Main link. No arguments.

26             Set the argument and the return value to 26.
  ×þ           Create the multiplication table of [1, ..., 26] by [1, ..., 26].
    %          Take all products modulo 26.
       Ç       Call the helper link with argument 26.
     iþ        Find the index of each integer to the right in each list to the left,
               grouping by the lists.
        o!     Replace zero indices (element not found) with 26!.
               This works for strings up to 25! = 15511210043330985984000000 chars,
               which exceeds Python's 9223372036854775807 character limit on x64.
          S    Take the sum of each column.
           Ụ   Sort the indices by their corresponding values.
            Ḣ  Head; extract the first index, which corresponds to the minimal value.
Dennis
fonte
4

JavaScript (Node.js) ,  123 121 116  114 bytes

s=>(i=26,F=m=>i--?F((g=x=>s[p]?s[k++>>5]?j=1+g(x+i,p+=b[p]==x%26+97):m:0)(b[p=k=0]+7)>m?m:(r=i,j)):r)(b=Buffer(s))

Experimente online!

Comentado

Eu2526s[k++ >> 5]g32.×eueu

s => (                        // main function taking the string s
  i = 26,                     // i = current step, initialized to 26
  F = m =>                    // F = recursive function taking the current minimum m
    i-- ?                     // decrement i; if i was not equal to 0:
      F(                      //   do a recursive call to F:
        (g = x =>             //     g = recursive function taking a character ID x
          s[p] ?              //       if there's still at least one letter to match:
            s[k++ >> 5] ?     //         if we've done less than 32 * s.length iterations:
              j = 1 + g(      //           add 1 to the final result and add the result of
                x + i,        //             a recursive call to g with x = x + i
                p += b[p] ==  //             increment p if
                  x % 26 + 97 //             the current letter is matching
              )               //           end of recursive call to g
            :                 //         else (we've done too many iterations):
              m               //           stop recursion and yield the current minimum
          :                   //       else (all letters have been matched):
            0                 //         stop recursion and yield 0
        )(                    //     initial call to g with p = k = 0
          b[p = k = 0] + 7    //     and x = ID of 1st letter
        ) > m ?               //     if the result is not better than the current minimum:
          m                   //       leave m unchanged
        :                     //     else:
          (r = i, j)          //       update m to j and r to i
      )                       //   end of recursive call to F
    :                         // else (i = 0):
      r                       //   stop recursion and return the final result r
)(b = Buffer(s))              // initial call to F with m = b = list of ASCII codes of s
Arnauld
fonte
4

Ruby , 121 114 112 108 102 89 bytes

->s{(r=0..25).min_by{|l|p,=s;s.sum{|c|t=r.find{|i|(p.ord-c.ord+i*l)%26<1}||1/0.0;p=c;t}}}

Experimente 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.

Kirill L.
fonte
:( close (solução baseada em python)
somente ASCII
100 , provavelmente pode ser jogado um pouco mais
somente ASCII
91
somente ASCII
Ótima idéia, -1 mais byte por p,=*struque, 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) )
Kirill L.
Apenas 2 bytes, não é ruim
apenas ASCII
3

Python 2 , 230 222 216 194 169 bytes

def t(s,l,S=0):
 a=ord(s[0])
 for c in s[1:]:
	while a-ord(c)and S<len(s)*26:S+=1;a=(a-65+l)%26+65
 return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))

Experimente online!

-22 bytes de tsh

-39 bytes de Jo King

Versão mais antiga com explicação:

A=map(chr,range(65,91)).index
def t(s,l,S=0):
 a=A(s[0]) 
 for c in s[1:]:
	while a!=A(c)and S<len(s)*26:
	 S+=1;a+=l;a%=26
 return S
def f(s):T=[t(s,l)for l in range(26)];return T.index(min(T))

Experimente online!

Isso seria mais curto em um idioma com um número primo de letras (não precisaria do float('inf') tratamento de loops infinitos). Na verdade, esse envio ainda seria necessário para lidar com cadeias de caracteres como "aaa". Esse envio agora usa 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 ótimo

té 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).

pizzapants184
fonte
2
Use while a!=A(c)and S<len(s)*26:e você pode remover if a==i:return float('inf'), pois len(s)*26é o limite superior de qualquer resposta.
tsh
165
somente ASCII
método alternativo, 166
somente ASCII
155
somente ASCII
1
112
somente ASCII
2

Vermelho , 197 bytes

func[s][a: collect[repeat n 26[keep #"`"+ n]]m: p: 99 a: append/dup a a m
u: find a s/1 repeat n 26[v: extract u n
d: 0 foreach c s[until[(v/(d: d + 1) = c)or(d > length? v)]]if d < m[m: d p: n]]p]

Experimente online!

Galen Ivanov
fonte
2

05AB1E (legado) , 33 27 26 bytes

Ç¥ε₂%U₂L<©ε®*₂%Xk'-žm:]øOWk

Usa 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:

Ç                        # ASCII values of the (implicit) input
 ¥                       # Deltas (differences between each pair)
  ε                      # Map each delta to:
   ₂%                    #  Take modulo-26 of the delta
     U                   #  Pop and store it in variable `X`
      L<                #  Push a list in the range [0,25]
         ©               #  Store it in the register (without popping)
          ε              #  Map each `y` to:
           ®*            #   Multiply each `y` by the list [0,25] of the register
             ₂%          #   And take modulo-26
                         #   (We now have a list of size 26 in steps of `y` modulo-26)
               Xk        #   Get the index of `X` in this inner list (-1 if not found)
                 '-₄:   '#   Replace the minus sign with "1000"
                         #   (so -1 becomes 10001; others remain unchanged) 
]                        # Close both maps
 ø                       # Zip; swapping rows/columns
  O                      # Sum each
   W                     # Get the smallest one (without popping the list)
    k                    # Get the index of this smallest value in the list
                         # (and output the result implicitly)
Kevin Cruijssen
fonte
2

Python 3 , 191 178 162 bytes

Obrigado a todos por todas as suas dicas! isso parece muito mais parecido com o golfe.

*w,=map(ord,input())
a=[]
for i in range(26):
 n=1;p=w[0]
 for c in w:
  while n<len(w)*26and p!=c:
   n+=1;p+=i;
   if p>122:p-=26
 a+=[n]
print(a.index(min(a)))

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.

Terjerber
fonte
1
Oi e bem-vindo ao PPCG! Para iniciantes, sua contagem de bytes publicada não corresponde à do TIO :) Agora, para algumas dicas rápidas: range(26)basta - você não precisa especificar o início, pois 0 é o padrão; a.append(n)poderia ser a+=[n]; a primeira linha seria mais curta como mapa w=list(map(ord,input()))(na verdade, com seu algoritmo atual, no Py2 você também pode deixar o list(...)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)
Kirill L.
1
Além disso, isso n>99parece 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.
precisa
1
BTW, você ainda pode se livrar disso list(...)no Py3 e também de um extra if: 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á!
precisa
1
Eu não sou um especialista em python, mas acho que você pode fazer while p!=c and n>len(w)*26:e se livrar dessa última declaração if por -8 bytes.
Spitemaster
2
Embora pareça terrível e vá contra tudo o que o Python é, você pode alterar n+=1e p+=iem linhas separadas para n+=1;p+=iuma.
nedla2004