Paso óptimo del alfabeto

30

Dada una cadena de entrada que consta de solo letras, devuelve el tamaño de paso que da como resultado la cantidad mínima de pasos necesarios para visitar todas las letras en orden sobre un alfabeto de ajuste, comenzando en cualquier letra.

Por ejemplo, tomar la palabra, dog. Si usamos un tamaño de paso de 1, terminamos con:

defghijklmnopqrstuvwxyzabcdefg   Alphabet
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
defghijklmnopqrstuvwxyzabcdefg   Visited letters
d          o                 g   Needed letters

Para un total de 30 pasos.

Sin embargo, si usamos un tamaño de paso de 11, obtenemos:

defghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg
^          ^          ^          ^          ^          ^
d          o          z          k          v          g   Visited letters
d          o                                           g   Needed letters

Para un total de 6 pasos. Esta es la cantidad mínima de pasos, por lo que el resultado de retorno doges el tamaño del paso; 11.

Casos de prueba:

"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

Reglas

  • La entrada será una cadena o matriz de caracteres no vacía que constará solo de las letras aa z(puede elegir entre mayúsculas o minúsculas)
  • La salida puede ser 0 indexada (es decir, el rango 0-25) o 1 indexada ( 1-26)
  • Si hay un empate, puede generar cualquier tamaño de paso o todos
  • Este es el , por lo que gana la menor cantidad de bytes para cada idioma.
Jo King
fuente
¿Necesitamos manejar entradas vacías?
pizzapants184
1
@ pizzapants184 No. He actualizado la pregunta para especificar que la entrada no estará vacía
Jo King
¿Podemos tomar la entrada como una matriz de caracteres?
Shaggy
@Shaggy Claro que puedes
Jo King
¿Hay alguna razón por la que esto usa letras en lugar de números?
Wheat Wizard

Respuestas:

6

Carbón , 41 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. 0 indexado. Explicación:

Eβ

Pase sobre los 26 pasos. (En realidad, hago un bucle sobre el alfabeto en minúsculas aquí y uso la variable de índice).

Eθ∧μ

Pase sobre cada carácter de la entrada después del primero.

⭆β§β⁺⌕β§θ⊖μ×κξ

Realice un bucle 26 veces y genere la cadena de caracteres resultante al realizar 26 pasos en el tamaño de paso dado que comienza (indexado en 0) con el carácter anterior de la entrada.

⌕...λ

Encuentre la posición del carácter actual de la entrada en esa cadena, o -1 si no se encuentra.

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

Tome la suma de todas las posiciones, a menos que no se encuentre una, en cuyo caso use -1.

≔...θ

Ahorre las sumas.

⌊Φθ⊕ι

Encuentra la suma mínima no negativa.

I⌕θ...

Encuentre el tamaño del primer paso con esa suma y suéltelo.

Neil
fuente
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

Pruébalo en línea!

Gracias a Shaggy, el uso [...Array(26).keys()]guarda 9 bytes.

tsh
fuente
144 bytes
Shaggy
4

Jalea , 28 26 23 bytes

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

La salida está indexada en 0. La entrada es una cadena de bytes y puede ser en cualquier caso, pero en mayúsculas es mucho más rápido.

La entrada de una sola letra tiene que estar en mayúsculas especiales y cuesta 2 bytes. ._.

Pruébalo en línea!

Tenga en cuenta que este es un enfoque de fuerza bruta; las entradas con cuatro o más letras caducarán en TIO. El conjunto de pruebas pretende _39 "eficiencia".

Cómo 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
fuente
4

Jalea , 17 bytes

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

La entrada es una cadena de bytes en STDIN, la salida está indexada en 1.

Pruébalo en línea!

Cómo 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
fuente
4

JavaScript (Node.js) ,  123121116114  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))

Pruébalo en línea!

Comentado

i2526s[k++ >> 5]g32×LL

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
fuente
4

Rubí , 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}}}

Pruébalo en línea!

0 indexado. Toma la entrada como una matriz de caracteres.

Gracias a ASCII-only por ideas de golf de 12 bytes.

Kirill L.
fuente
:( cerrar (basado en la solución de Python)
solo ASCII
100 , probablemente se puede jugar un poco más de golf
solo ASCII
91
Solo ASCII
Gran idea, -1 byte más por p,=*struco, pero no estoy tan seguro de la solidez teórica de una solución con un puntaje de penalización codificado ... Entonces, cambié la constante al infinito (aunque su valor permitiría otros 2 bytes de descuento) )
Kirill L.
Solo 2 bytes, no está mal
solo ASCII el
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))

Pruébalo en línea!

-22 bytes desde tsh

-39 bytes de Jo King

Versión anterior con explicación:

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))

Pruébalo en línea!

Esto sería más corto en un idioma con un número primo de letras (no necesitaría el float('inf')manejo de bucles infinitos). En realidad, este envío aún lo necesitaría para manejar cadenas como "aaa". Este envío ahora se utiliza 26*len(s)como límite superior, lo que detiene los bucles infinitos.

Este envío está indexado en 0 (devuelve valores de 0 a 25 inclusive).

f toma una cadena (n mayúscula) y devuelve el paso del alfabeto óptimo

tes una función auxiliar que toma la secuencia y un paso alfabético y devuelve el número de saltos necesarios para finalizar la secuencia (o 26*len(s)si es imposible).

pizzapants184
fuente
2
Use while a!=A(c)and S<len(s)*26:y puede eliminar if a==i:return float('inf'), ya que len(s)*26es el límite superior de cualquier respuesta.
tsh
165
Solo ASCII el
155
Solo ASCII el
1
112
Solo ASCII
2

Rojo , 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]

Pruébalo en línea!

Galen Ivanov
fuente
2

05AB1E (heredado) , 33 27 26 bytes

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

Utiliza la versión heredada porque parece haber un error cuando desea modificar / usar el resultado después de un mapa anidado en la nueva versión 05AB1E.

Salida indexada a 0.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Ç                        # 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
fuente
2

Python 3 , 191 178 162 bytes

¡Gracias a todos por todos sus consejos! Esto se ve mucho más parecido al golf.

*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)))

Pruébalo en línea!

Y mi código original si alguien está interesado.

Convierte la palabra en una lista de valores ASCII, luego recorre los pasos del 0 al 25, verificando cuántos pasos se necesitan para agotar la lista (hay un límite máximo para detener los bucles infinitos).

El número de pasos se agrega a la lista a .

Después del bucle grande for, se imprime el índice del valor más pequeño en a . Esto es igual al valor de i (el tamaño del paso) para esa iteración del bucle, QED.

Terjerber
fuente
1
Hola y bienvenido a PPCG! Para empezar, su recuento de bytes publicado no coincide con eso en TIO :) Ahora, para un par de sugerencias rápidas: range(26)es suficiente: no necesita especificar el inicio, ya que 0 es el valor predeterminado; a.append(n)podría ser a+=[n]; la primera línea sería más corta como mapa w=list(map(ord,input()))(en realidad con su algoritmo actual, en Py2 también podría soltar el ajuste list(...)); evitar saltos de separación / de línea adicionales tanto como sea posible (por ejemplo, no hay necesidad de nuevas líneas en oneliners: if p>122:p-=26)
Kirill L.
1
Además, eso n>99parece sospechoso, ¿es esa una constante arbitraria para salir del bucle infinito? Entonces, probablemente debería ser algo así como 26 * len (w), como nunca se sabe, qué tan grande será la entrada.
Kirill L.
1
Por cierto, aún puedes deshacerte de eso list(...)en Py3 y también de un extra if: 165 bytes . Además, eche un vistazo a este tema de consejos , ¡estoy seguro de que mejorará en gran medida sus habilidades con los consejos de allí!
Kirill L.
1
No soy un experto en python, pero creo que puedes hacerlo while p!=c and n>len(w)*26:y deshacerte de esa última sentencia if para -8 bytes.
Spitemaster
2
Aunque se ve terrible y va en contra de todo lo que es Python, puede cambiar n+=1y p+=ien líneas separadas a n+=1;p+=iuna.
nedla2004