Optimale Alphabetisierung

30

Geben Sie bei einer Eingabezeichenfolge, die nur aus Buchstaben besteht, die Schrittgröße zurück, die die Mindestanzahl von Schritten ergibt, die erforderlich sind, um alle Buchstaben in der angegebenen Reihenfolge über ein umschließendes Alphabet zu lesen, beginnend bei einem beliebigen Buchstaben.

Nehmen Sie zum Beispiel das Wort dog. Wenn wir eine Schrittgröße von 1 verwenden, erhalten wir:

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

Für insgesamt 30 Schritte.

Wenn wir jedoch eine Schrittgröße von 11 verwenden, erhalten wir:

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

Für insgesamt 6 Schritte. Dies ist die minimale Anzahl von Schritten, daher ist das Rückgabeergebnis für dogdie Schrittgröße; 11.

Testfälle:

"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

Regeln

  • Die Eingabe ist eine nicht leere Zeichenfolge oder ein Array von Zeichen, die nur aus den Buchstaben abis bestehen z(Sie können zwischen Groß- und Kleinschreibung wählen).
  • Die Ausgabe kann 0-indiziert (dh der Bereich 0-25) oder 1-indiziert ( 1-26) sein.
  • Wenn es einen Gleichstand gibt, können Sie eine beliebige Schrittgröße oder alle davon ausgeben
  • Das ist , also gewinnt die niedrigste Anzahl von Bytes für jede Sprache!
Scherzen
quelle
Müssen wir mit leeren Eingaben umgehen?
Pizzapants184
1
Ich habe die Frage aktualisiert, um anzugeben, dass die Eingabe nicht leer sein wird
Jo King
Können wir Eingaben als Array von Zeichen annehmen?
Shaggy
@ Shaggy Sicher können Sie
Jo King
Gibt es einen Grund dafür, dass Buchstaben anstelle von Zahlen verwendet werden?
Weizen-Zauberer

Antworten:

6

Kohle , 41 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. 0-indiziert. Erläuterung:

Eβ

Überfliege die 26 Stufengrößen. (Eigentlich schleife ich hier über das Kleinbuchstaben und verwende die Indexvariable.)

Eθ∧μ

Durchlaufen Sie jedes Zeichen der Eingabe nach dem ersten.

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

Schleifen Sie 26-mal und generieren Sie die Zeichenfolge, indem Sie 26 Schritte bei der angegebenen Schrittgröße ausführen, beginnend mit dem vorherigen Zeichen der Eingabe (0-indiziert).

⌕...λ

Suchen Sie die Position des aktuellen Zeichens der Eingabe in dieser Zeichenfolge oder -1, falls nicht gefunden.

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

Nimm die Summe aller Positionen, es sei denn, eine wurde nicht gefunden. In diesem Fall verwende -1.

≔...θ

Speichern Sie die Summen.

⌊Φθ⊕ι

Finden Sie die minimale nicht negative Summe.

I⌕θ...

Finden Sie die erste Schrittweite mit dieser Summe und geben Sie sie aus.

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

Probieren Sie es online!

Dank Shaggy werden [...Array(26).keys()]9 Bytes eingespart.

tsh
quelle
144 Bytes
Shaggy
4

Jelly , 28 26 23 Bytes

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

Der Ausgang ist 0-indiziert. Die Eingabe ist ein Bytestring und kann in jedem Fall erfolgen, jedoch in Großbuchstaben viel schneller.

Die Eingabe eines einzelnen Buchstabens muss in einem speziellen Gehäuse erfolgen und kostet 2 Byte. ._.

Probieren Sie es online!

Beachten Sie, dass dies ein Brute-Force-Ansatz ist. Bei Eingaben mit vier oder mehr Buchstaben tritt bei TIO eine Zeitüberschreitung auf. Die Testsuite wird vorangestellt_39 für "Effizienz".

Wie es funktioniert

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

Gelee , 17 Bytes

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

Die Eingabe ist ein Bytestring für STDIN, die Ausgabe ist 1-indiziert.

Probieren Sie es online!

Wie es funktioniert

Ɠ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
quelle
4

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

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

Probieren Sie es online!

Kommentiert

ich2526s[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
quelle
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}}}

Probieren Sie es online!

0-indiziert. Nimmt die Eingabe als Array von Zeichen.

Dank ASCII-only für Golfideen im Wert von 12 Bytes.

Kirill L.
quelle
:( close (basierend auf Python-Lösung)
Nur ASCII
100 , wahrscheinlich kann einiges mehr golfen werden
ASCII
91
Nur ASCII
Tolle Idee, -1 Byte mehr pro p,=*sTrick, aber ich bin mir nicht so sicher über die theoretische Robustheit einer Lösung mit einer hartcodierten Strafpunktzahl ... Also habe ich die Konstante auf unendlich geändert (obwohl Ihr Wert noch 2 Byte weniger zulässt) ).
Kirill L.
Nur 2 Bytes, nicht schlecht
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))

Probieren Sie es online!

-22 Bytes von tsh

-39 Bytes von Jo King

Ältere Version mit Erklärung:

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

Probieren Sie es online!

Dies wäre in einer Sprache mit einer Primzahl von Buchstaben kürzer (würde keine float('inf')Behandlung von Endlosschleifen erfordern ). Tatsächlich würde diese Übermittlung immer noch die für die Verarbeitung von Zeichenfolgen wie "aaa" benötigen. Diese Vorlage verwendet jetzt26*len(s) als Obergrenze verwendet, wodurch Endlosschleifen gestoppt werden.

Diese Einreichung ist 0-indiziert (gibt Werte von 0 bis einschließlich 25 zurück).

f Nimmt einen String (n in Großbuchstaben) und gibt den optimalen Alphabetschritt zurück

tist eine Hilfsfunktion, die die Zeichenfolge und ein schrittweises Alphabet verwendet und die Anzahl der zum Beenden der Zeichenfolge erforderlichen Sprünge zurückgibt (oder 26*len(s)wenn dies nicht möglich ist).

Pizzapants184
quelle
2
Verwenden while a!=A(c)and S<len(s)*26:Sie und Sie können entfernen if a==i:return float('inf'), da len(s)*26die Obergrenze jeder Antwort ist.
tsh
165
Nur ASCII
155
Nur ASCII
1
112
Nur ASCII
2

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

Probieren Sie es online!

Galen Ivanov
quelle
2

05AB1E (Legacy) , 33 27 26 Byte

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

Verwendet die ältere Version, da es einen Fehler zu geben scheint, wenn Sie das Ergebnis nach einer verschachtelten Karte in der neuen Version 05AB1E ändern / verwenden möchten.

0-indizierte Ausgabe.

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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

Python 3 , 191 178 162 Bytes

Danke an alle für all eure Tipps! das sieht viel mehr nach Golf aus.

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

Probieren Sie es online!

Und mein Originalcode, wenn jemand interessiert ist.

Wandelt das Wort in eine Liste von ASCII-Werten um und durchläuft dann die Schrittgrößen 0 bis 25, wobei überprüft wird, wie viele Schritte erforderlich sind, um die Liste zu erschöpfen (es gibt eine Obergrenze, um Endlosschleifen zu stoppen).

Die Anzahl der Schritte wird der Liste hinzugefügt. A .

Nach der großen for-Schleife wird der Index des kleinsten Werts in a gedruckt. Dies ist gleich dem Wert von i (der Schrittgröße) für die Iteration der Schleife QED.

Terjerber
quelle
1
Hallo und Willkommen bei PPCG! Für den Anfang stimmt Ihre Anzahl der geposteten Bytes nicht mit der von TIO überein :) Nun, für ein paar kurze Hinweise: range(26)ist genug - Sie müssen den Start nicht angeben, da 0 die Standardeinstellung ist; a.append(n)könnte sein a+=[n]; Die erste Zeile wäre kürzer als die Karte w=list(map(ord,input()))(tatsächlich könnten Sie mit Ihrem aktuellen Algorithmus in Py2 auch den Zeilenumbruch fallen lassen list(...)). vermeiden zusätzliche Abstand / Zeilenumbrüche so weit wie möglich (zB keine Notwendigkeit für neue Zeilen in oneliners: if p>122:p-=26)
Kirill L.
1
Das n>99sieht auch verdächtig aus, ist das eine willkürliche Konstante, die aus der Endlosschleife ausbricht? Dann sollte es wohl so etwas wie 26 * len (w) sein, da man nie weiß, wie groß die Eingabe sein wird.
Kirill L.
1
list(...)Übrigens kann man das in Py3 noch loswerden und auch eins extra if: 165 Bytes . Werfen Sie auch einen Blick auf dieses Thema mit den Tipps . Ich bin sicher, dass Sie Ihre Fähigkeiten mit den Ratschlägen von dort erheblich verbessern werden!
Kirill L.
1
Ich bin kein Python-Experte, aber ich denke, Sie können diese while p!=c and n>len(w)*26:letzte if-Anweisung für -8 Bytes entfernen.
Spitemaster
2
Obwohl es schrecklich aussieht und gegen alles geht, was Python ist, können Sie es ändern n+=1und p+=iin separaten Zeilen n+=1;p+=iauf eine setzen.
nedla2004