Abjad Alfabet Optimal

30

Diberikan string input yang hanya terdiri dari huruf-huruf, kembalikan ukuran langkah yang menghasilkan jumlah langkah minimum yang diperlukan untuk mengunjungi semua huruf dalam urutan di atas alfabet pembungkus, mulai dari huruf apa pun.

Misalnya, ambil kata dog,. Jika kita menggunakan ukuran langkah 1, kita berakhir dengan:

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

Untuk total 30 langkah.

Namun, jika kita menggunakan ukuran langkah 11, kita mendapatkan:

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

Untuk total 6 langkah. Ini adalah jumlah minimum langkah, jadi hasil pengembalian dogadalah ukuran langkah; 11.

Kasus uji:

"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

Aturan

  • Input akan berupa string atau array karakter yang tidak kosong yang hanya terdiri dari huruf-huruf auntuk z(Anda dapat memilih antara huruf besar atau kecil)
  • Output dapat diindeks 0 (yaitu kisaran 0-25) atau 1 diindeks ( 1-26)
  • Jika ada dasi, Anda dapat menampilkan ukuran langkah apa pun atau semuanya
  • Ini adalah , sehingga jumlah byte terendah untuk setiap bahasa menang!
Jo King
sumber
Apakah kita perlu menangani input kosong?
pizzapants184
1
@ pizzapants184 Tidak. Saya telah memperbarui pertanyaan untuk menentukan bahwa inputnya akan kosong
Jo King
Bisakah kita mengambil input sebagai array karakter?
Shaggy
@Shaggy Tentu Anda bisa
Jo King
Apakah ada alasan mengapa ini menggunakan huruf dan bukan angka?
Wheat Wizard

Jawaban:

6

Arang , 41 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Diindeks 0. Penjelasan:

Eβ

Ulangi ukuran 26 langkah. (Sebenarnya saya mengulang alfabet huruf kecil di sini dan menggunakan variabel indeks.)

Eθ∧μ

Ulangi setiap karakter input setelah yang pertama.

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

Ulangi 26 kali dan hasilkan string karakter yang dihasilkan dengan mengambil 26 langkah pada ukuran langkah awal yang diberikan (0-diindeks) dengan karakter input sebelumnya.

⌕...λ

Temukan posisi karakter saat ini dari input dalam string itu, atau -1 jika tidak ditemukan.

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

Ambil jumlah semua posisi, kecuali ada yang tidak ditemukan, dalam hal ini gunakan -1.

≔...θ

Simpan jumlahnya.

⌊Φθ⊕ι

Temukan jumlah minimum non-negatif.

I⌕θ...

Temukan ukuran langkah pertama dengan jumlah itu dan outputkan.

Neil
sumber
5

JavaScript, 143 byte

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

Cobalah online!

Terima kasih kepada Shaggy, menggunakan [...Array(26).keys()]menghemat 9 byte.

tsh
sumber
144 byte
Shaggy
4

Jelly , 28 26 23 byte

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

Output diindeks 0. Input adalah bytestring dan dapat dalam hal apapun, tetapi huruf besar jauh lebih cepat.

Masukan satu huruf harus dibuat khusus dan biayanya 2 byte. ._.

Cobalah online!

Perhatikan bahwa ini adalah pendekatan brute-force; input dengan empat atau lebih huruf akan habis pada TIO. Rangkaian uji coba _39 untuk "efisiensi".

Bagaimana itu bekerja

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

Jelly , 17 byte

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

Input adalah bytestring pada STDIN, output 1-diindeks.

Cobalah online!

Bagaimana itu bekerja

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

Cobalah online!

Berkomentar

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

Ruby , 121 114 112 108 102 89 byte

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

Cobalah online!

Diindeks 0. Mengambil input sebagai array karakter.

Berkat ASCII-only untuk ide-ide golf yang bernilai 12 byte.

Kirill L.
sumber
:( close (didasarkan dari solusi python)
ASCII-satunya
100 , mungkin bisa bermain golf sedikit lebih banyak
hanya ASCII
91
ASCII
Ide bagus, -1 lebih byte oleh p,=*strik, tapi saya tidak begitu yakin tentang kekuatan teoritis dari solusi dengan skor penalti hardcoded ... Jadi, saya mengubah konstanta ke infinity (walaupun nilai Anda akan memungkinkan untuk 2 byte lagi off) ).
Kirill L.
Hanya 2 byte, tidak buruk
ASCII
3

Python 2 , 230 222 216 194 169 byte

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

Cobalah online!

-22 byte dari tsh

-39 byte dari Jo King

Versi lebih lama dengan penjelasan:

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

Cobalah online!

Ini akan lebih pendek dalam bahasa dengan jumlah huruf utama (tidak perlu float('inf')penanganan loop tak terbatas). Sebenarnya, pengajuan ini masih perlu untuk menangani string seperti "aaa". Kiriman ini sekarang digunakan 26*len(s)sebagai batas atas, yang menghentikan loop tak terbatas.

Kiriman ini diindeks 0 (mengembalikan nilai dari 0 hingga 25 inklusif).

f mengambil string (n huruf besar) dan mengembalikan Optimal Alphabet Stepping

tadalah fungsi pembantu yang mengambil string dan alfabet melangkah dan mengembalikan jumlah hop yang diperlukan untuk menyelesaikan string (atau 26*len(s)jika tidak mungkin).

pizzapants184
sumber
2
Gunakan while a!=A(c)and S<len(s)*26:dan Anda dapat menghapus if a==i:return float('inf'), karena len(s)*26ada batas atas jawaban apa pun.
tsh
165
ASCII
155
ASCII
1
112
ASCII
2

Merah , 197 byte

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]

Cobalah online!

Galen Ivanov
sumber
2

05AB1E (warisan) , 33 27 26 byte

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

Menggunakan versi lawas karena sepertinya ada bug ketika Anda ingin memodifikasi / menggunakan hasilnya setelah peta bersarang di versi 05AB1E baru ..

Output terindeks 0.

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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

Python 3 , 191 178 162 byte

Terima kasih semuanya atas semua tips Anda! ini terlihat seperti 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)))

Cobalah online!

Dan kode asli saya kalau ada yang tertarik.

Ubah kata menjadi daftar nilai ASCII, lalu beralih melalui ukuran langkah 0 hingga 25, memeriksa berapa langkah yang diperlukan untuk mengeluarkan daftar (ada langit-langit untuk menghentikan loop tak terbatas).

Jumlah langkah ditambahkan ke daftar a .

Setelah big for loop, indeks nilai terkecil dalam a dicetak. Ini sama dengan nilai i (ukuran langkah) untuk iterasi loop, QED.

Terjerber
sumber
1
Hai & Selamat Datang di PPCG! Sebagai permulaan, jumlah byte yang Anda posting tidak cocok dengan pada TIO :) Sekarang, untuk beberapa petunjuk cepat: range(26)sudah cukup - Anda tidak perlu menentukan awal, karena 0 adalah default; a.append(n)bisa jadi a+=[n]; baris pertama akan lebih pendek sebagai peta w=list(map(ord,input())), (sebenarnya dengan algoritma Anda saat ini, di Py2 Anda juga bisa menjatuhkan list(...)pembungkus); hindari spasi ekstra / jeda baris sebanyak mungkin (mis., tidak perlu baris baru di oneliners :) if p>122:p-=26)
Kirill L.
1
Juga, yang n>99terlihat mencurigakan, apakah konstanta yang sewenang-wenang untuk keluar dari loop yang tidak terbatas? Maka mungkin harus seperti 26 * len (w), karena Anda tidak pernah tahu, seberapa besar inputnya.
Kirill L.
1
BTW, Anda masih bisa menyingkirkan itu list(...)di Py3 dan juga satu tambahan if: 165 byte . Juga, lihat topik tips ini , saya yakin Anda akan sangat meningkatkan keterampilan Anda menggunakan saran dari sana!
Kirill L.
1
Saya bukan ahli python, tapi saya pikir Anda bisa melakukan while p!=c and n>len(w)*26:dan menyingkirkan yang terakhir jika pernyataan untuk -8 byte.
Spitemaster
2
Meskipun terlihat mengerikan dan bertentangan dengan semua Python, Anda dapat mengubah n+=1dan p+=ipada baris yang terpisah menjadi n+=1;p+=isatu.
nedla2004