Tampaknya ada kegemaran yang sedang berlangsung tentang orang-orang yang dengan susah payah mempelajari tata letak keyboard baru seperti Dvorak atau Neo karena itu seharusnya membuat mereka lebih produktif. Saya berpendapat bahwa mengganti tata letak keyboard adalah ide yang buruk, karena itu bisa memakan waktu berbulan-bulan untuk mempercepat, dan ketika Anda akhirnya 5% lebih cepat daripada yang lain, Anda kacau jika Anda perlu mengetik pada komputer yang tidak milikmu sendiri.

Juga, semua orang ini lupa di mana hambatan sebenarnya dalam komunikasi modern terletak - tombol telepon.

Beginilah tampilan keypad telepon rata-rata Anda:

Huruf 'r' adalah huruf ketiga pada tombol 7; jadi jika Anda mengetik huruf 'r' di ponsel, Anda akan menekan tombol 7 tiga kali, untuk 's Anda akan menekannya 4 kali, dan untuk' a 'Anda akan menekan tombol 2 sekali.

Mempertimbangkan hal ini, menempatkan 'e' setelah 'd' mungkin merupakan keputusan yang buruk - 'e' adalah huruf yang paling umum digunakan dalam alfabet bahasa Inggris, jadi, jika Anda memberi label tombol 3 "EDF" dan bukan "DEF", Anda akan menghemat cukup banyak penekanan tombol.

Selain itu, Anda mungkin pernah mengalami sendiri bahwa mengetik 2 huruf yang menggunakan tombol yang sama adalah gangguan - jika Anda ingin menulis "TU", Anda tidak bisa menekan 8 tiga kali, karena itu akan menghasilkan 'V'. Jadi biasanya Anda akan menulis 'T', lalu tekan spasi, lalu tekan backspace, dan kemudian menulis 'U', yang sama dengan 5 penekanan tombol, bukan 3.

TL; DR

Diberikan dua aturan ini:

• Sebuah huruf diketik dengan menekan tombol n kali, di mana n adalah posisi di mana huruf berada pada label tombol
• Menulis dua huruf yang diketik menggunakan tombol yang sama membutuhkan tambahan menekan 2 tombol

Apa tata letak keyboard telepon yang membutuhkan paling sedikit penekanan tombol, mengingat teks tertentu? Anda hanya harus menggunakan tombol 2-9, 1 dan 0 yang dicadangkan untuk simbol khusus.

Memasukkan

Teks yang Anda harus temukan tata letaknya yang optimal disediakan melalui stdin. Anda tidak perlu menangani apa pun selain huruf kecil dan dapat mengasumsikan bahwa input hanya terdiri dari itu. Anda juga dapat mengasumsikan bahwa teks input cukup besar dan setiap huruf ada di sana setidaknya satu kali, jika itu membantu.

Keluaran

Saya tidak ingin menempatkan terlalu banyak kendala pada output, karena kadang-kadang memberikan beberapa keunggulan bahasa daripada yang lain; jadi bagaimanapun bahasa Anda menunjukkan array baik-baik saja, atau Anda dapat memisahkan setiap label dengan baris baru.

Mungkin ada beberapa kemungkinan tata letak optimal, Anda dapat mencetak salah satunya. Berikut ini contoh sederhana:

>> echo "jackdawslovemybigsphinxofquartz" | foo.sh
ojpt
avhz
cen
skm
dyf
wbq
ixu
lgr

Poin Bonus

-35 jika algoritma Anda tidak memaksa semua tata letak yang mungkin (Saya melihat `permutasi 'Haskell di sini)

-3 jika kode Anda pas di dalam pesan teks (140 karakter) dan Anda memposting gambar yang Anda kirim kode ke teman.

Ini adalah tantangan pertama saya di StackExchange. Saya akan senang mendengar apakah Anda menyukainya, atau ada tanggapan lain tentang itu!

Perl, 333

$_=<>;$c{$&}++while/./g;@c=sort{$c{$b}<=>$c{$a}}keys%c;$d{$&.$1}++while/.(?=(.))/g;sub f{my$x=shift;if(my$c=pop@$x){for(grep!$_[$_],0..7){my@y = @_;$y[$_]=$c;f([@$x],@y)}}else{for(0..7){$z=$_[$_];$c+=$d{$z.$_}+$d{$_.$z}for@{$a[$_]}}$c<$m?($m=$c,@n=@_):1}}while(@c){$m= ~0;f[splice@c,0,8];push@{$a[$_]},$n[$_]for 0..7}print@$_,$/for@a

Berikut adalah upaya untuk mengoptimalkan aturan # 2. Setelah komentar saya, di atas, dan sebagai pengganti jawaban yang memperhitungkan aturan itu (lih. Pertanyaan tingkat tinggi), saya berpikir bahwa saya berutang usaha di sini ...

Solusi yang tidak dioptimalkan untuk aturan # 2 dapat menghasilkan output yang sangat jauh dari optimal. Saya memeriksa teks bahasa Inggris alami yang panjang ("Alice in Wonderland", sebenarnya), pra-diproses (hanya huruf kecil), dan misalnya skrip Perl dari jawaban OJW, hasilnya adalah

2: ermx
3: tdfz
4: alp
5: oub
6: ick
7: nwv
8: hgj
9: syq

er sendirian reruntuhan itu, ditambah beberapa pasangan lain seharusnya tidak pernah berakhir pada kunci yang sama ...

Btw, zxqjvkbpfmygwculdrshnioateadalah huruf yang diurutkan, frekuensi naik, dari teks itu.

Jika kita mencoba menyelesaikannya dengan cara mudah (berharap untuk -35 bonus, mungkin) dan menempatkan huruf satu per satu, memilih kunci yang tersedia dengan jumlah pasangan minimal, kita dapat mengakhiri dengan misalnya:

slbx
hdmz
nrf
iuj
ogv
awk
tcp
eyq

Saya tidak memposting kode untuk solusi (salah) ini di sini. Misalnya, perhatikan, clebih sering daripada wdan ditempatkan terlebih dahulu. tc( ct) pasangan jelas lebih jarang dari ac( ca) - 43 + 235 melawan 202 + 355. Tapi kemudian wberakhir dengan a- 598 + 88. Kita berakhir dengan pasangan awdan tc(total 964), meskipun akan lebih baik acdan tw(total 635). Dll ..

Jadi, algoritma berikutnya mencoba untuk memeriksa masing-masing 8 huruf yang tersisa (atau 2, jika terakhir) paling sering terhadap huruf yang sudah ada di keypad, dan untuk menempatkannya sehingga jumlah pasangan menjadi minimal.

$_=<>;                          # Read STDIN.
$c{$&}++while/./g;              # Count letters (%c hash).
@c=sort{$c{$b}<=>$c{$a}}keys%c; # Sort them by frequency, ascending
$d{$&.$1}++while/.(?=(.))/g;    # (@c array), and count pairs (%d hash).

                                # Next is recursive sub that does the job.
                                # Some CPAN module for permutations
                                # would probably do better...
                                # Arguments are reference to array of what's 
                                # left un-placed of current 8-pack of letters,
sub f{                          # and 8 element list of placed letters
    my$x=shift;                 # (or undefs).
    if(my$c=pop@$x){            # Pop a letter from 8-pack (if anything left),
        for(grep!$_[$_],0..7){  # try placing it on each available key, and 
            my@y = @_;          # call sub again passing updated arguments.
            $y[$_]=$c;
            f([@$x],@y)
        }
    }else{                      # If, OTOH, 8-pack is exhausted, find sum of
        for(0..7){              # pairs count of current permutation (@_) and 
            $z=$_[$_];          # letters placed in previous rounds (8-packs).
                                # @a is "array of arrays" - note, we didn't 
                                # have to initialize it. First "8-pack" will
                                # be placed on empty keypad "automatically".
                                # We re-use undefined (i.e. 0) $c.

            $c+=$d{$z.$_}+$d{$_.$z}for@{$a[$_]}
        }
        $c<$m                   # Is sum for current placement minimal?
            ?($m=$c,@n=@_)      # Then remember this minimum and placement.
            :1
    }
}

while(@c){
    $m= ~0;                         # Initialize "minimum" with large enough 
    f[splice@c,0,8];                # number, then call sub with each 8-pack
                                    # (and empty list of placed letters 
                                    # from current round). On return,
                                    # @n will have optimal arrangement.
    push@{$a[$_]},$n[$_]for 0..7    # Then place it permanently on keypad.
}
print@$_,$/for@a                    # Show us what you've done.

Hasilnya adalah:

sdfz
hlmx
nrv
iyp
ogk
acq
twb
euj

Saya tidak suka acpasangan (Kucing menjadi salah satu karakter, setelah semua), tapi tetap penempatan huruf yang optimal untuk bahasa Inggris, jika kode saya tidak salah. Bukan upaya 'bermain golf', hanya beberapa solusi kerja, jelek atau tidak.

Python3, saatnya Montecarlo!

Untuk mengatasi masalah ini, pertama-tama saya menghitung berapa "klik" yang Anda butuhkan dengan keyboard default (awal:) abc,def,ghi,jkl,mno,pqrs,tuv,wxyz. Kemudian saya memodifikasi keyboard ini dan melihat apakah lebih murah (teks ditulis dengan lebih sedikit klik). Jika keyboard ini lebih murah, maka itu menjadi yang default. Saya mengulangi proses 1Mkali ini.

Untuk mengubah keyboard, pertama-tama saya memutuskan berapa banyak perubahan yang harus dilakukan (jumlah maksimum perubahan adalah jumlah total huruf di keyboard). Kemudian, untuk setiap saklar, saya memilih dua tombol dan dua posisi dan saya mentransfer karakter dari posisi pertama ke yang kedua.

Jumlah maksimum sakelar per waktu adalah jumlah huruf di keyboard karena itu adalah jumlah minimum perubahan yang Anda perlukan untuk beralih dari dua keyboard lengkap yang berbeda. (Saya ingin selalu memungkinkan untuk beralih dari satu keyboard ke keyboard lainnya)

Output dari echo "jackdawslovemybigsphinxofquartz" | python .\myscript.pyadalah:

61 ['anb', 'sef', 'hjc', 'iykl', 'odm', 'qgr', 'tuxv', 'wpz']

Di mana 61jumlah tombol ditekan untuk menulis pesan yang diberikan.

Karakter (tanpa spasi dan tidak ada komentar): 577

Saya tahu ini panjang tapi saya benar-benar baru dalam hal ini.

from random import *
S=['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
def P(L): # perform a switch of the keys of the keyboard:to switch from a given keyboard to another, the maximum number of exchanges is the number of the keys.
    R=randint
    N = len(''.join(L))
    W = randint(1,N)   # decide how many switches to perform
    EL = list(L)
    for i in range(0,W):
        B1=R(0,len(EL)-1)   # decide what buttons are considered in the switch
        B2=R(0,len(EL)-1)
        if len(EL[B1])==0: continue   
        P1=R(0,len(EL[B1])-1)       # decide what letter to switch and where
        if len(EL[B2])==0: P2=0
        else:   P2=R(0,len(EL[B2])-1)
        C1 = EL[B1][P1]     
        EL[B1]=EL[B1].replace(C1,'')
        EL[B2]=EL[B2][:P2]+C1+EL[B2][P2:]
    return EL
def U(L,X): # count how many clicks you need to compose the text X
    S=0
    Z=' '
    for A in X:
        for T in L:
            if A in T and Z not in T: S+=1+T.index(A)
            if A in T and Z in T: S+=3+T.index(A) # if the last character was in the same button..here the penality!
        Z=A
    return S
X=input()
n_iter=10**6
L = list(S)
cc=U(L,X)
print(cc,L)
for i in range(0,n_iter): #do some montecarlo stuff
    cc=U(L,X)
    pl=P(L)
    pc=U(pl,X)
    if(cc>pc):
        L=pl 
        print(pc,L)

Saya merasa sangat lucu sehingga saya memutuskan untuk mencoba algoritma ini dengan LO HOBBIT (saya punya salinan asli di rumah juga!). Ini memiliki 383964huruf dan ini adalah klik pasangan vs keypad yang saya temukan:

909007 ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
879344 ['abkc', 'def', 'gqhi', 'jl', 'mno', 'rs', 'tupv', 'wxyz']
861867 ['abg', 'def', 'qhyi', 'jcl', 'mno', 'r', 'tupxv', 'swkz']
851364 ['abg', 'e', 'qchi', 'jyl', 'mn', 'dr', 'tupxv', 'sowkfz']
829451 ['ag', 'ef', 'qchi', 'jyl', 'mn', 'dbr', 'tupxv', 'sowkz']
815213 ['amg', 'ef', 'qch', 'ojyl', 'i', 'dbnr', 'tupxv', 'swkz']
805521 ['amg', 'ef', 'ch', 'ojyl', 'qi', 'dbnr', 'tupxv', 'swkz']
773046 ['amg', 'ef', 'ch', 'ojyl', 'qi', 'bnr', 'tupxv', 'dswkz']
759208 ['amg', 'eqf', 'ch', 'ojyl', 'i', 'bnr', 'tupxv', 'dswkz']
746711 ['ag', 'ekq', 'clh', 'sojy', 'bi', 'nmfr', 'tupxv', 'dwz']
743541 ['ag', 'ekq', 'clh', 'sojy', 'bi', 'nmfr', 'tpxv', 'dwuz']
743389 ['ag', 'ekq', 'clh', 'sojy', 'i', 'nmfr', 'tpxbv', 'dwuz']
734431 ['ag', 'ekq', 'lh', 'sjy', 'ci', 'nrf', 'tpxbv', 'dowumz']
705730 ['ag', 'oekq', 'lh', 'sjy', 'ci', 'nrf', 'tpxbv', 'dwumz']
691669 ['ag', 'oekq', 'lh', 'nsjy', 'ic', 'rf', 'tpxbv', 'dwumz']
665866 ['ag', 'hokq', 'el', 'nsjy', 'ic', 'rbf', 'tpxv', 'dwumz']
661610 ['agm', 'hokq', 'e', 'nsj', 'ilc', 'rbf', 'tpyxv', 'dwuz']

Jadi saya mengklaim yang terakhir ini adalah salah satu tombol paling praktis (dalam hal klik).

Nah, jika Anda hanya ingin karakter paling populer yang ditugaskan ke tempat sampah 2-9, Perl dapat melakukannya dalam 127 karakter ...

foreach(split /\s*/,<>){$x{$_}++}
foreach(sort{$x{$b}<=>$x{$a}}keys %x){$o{$n++%8}.=$_}
for(0..7){printf "%d: %s\n",$_+2,$o{$_}}

memberikan sesuatu seperti:

echo "jackdawslovemybigsphinxofquartz" | perl ./keypad.pl
2: ajeb
3: iynz
4: suv
5: ohm
6: wkl
7: rgp
8: xfc
9: dtq

Atau cetak semuanya dalam satu baris, hapus 12 karakter:

foreach(split /\s*/,<>){$x{$_}++}
foreach(sort{$x{$b}<=>$x{$a}}keys %x){$o[$n++%8].=$_}
print join",",values@o,"\n";

Haskell, 160 - 35 = 125

import Data.List
import GHC.Exts
main=interact f where f s=show$transpose$map($sortWith(\x->length$filter(/=x)s)['a'..'z'])[t,t.d,t.d.d,d.d.d];t=take 8;d=drop 8

Contoh:

$ runhaskell % <<< "jackdaws loves my big sphinx of quartz"
["afpy","sgqz","ihr","ojt","bku","clv","dmw","enx"]
$ </usr/share/dict/propernames tr A-Z a-z | runhaskell % 
["atjx","edgq","rhb","nmp","iyv","lcf","ouw","skz"]

Orang mungkin berpendapat bahwa ini tidak mengoptimalkan untuk aturan 2, tetapi itu memang paling sering menempatkan huruf pada tombol yang berbeda .

JavaScript, 192 - 35 = 157

Hanya memperhatikan aturan karakter yang berulang; ini tidak memperhitungkannya. Tetapi seperti yang dicatat oleh @mniip dalam jawabannya:

Orang mungkin berpendapat bahwa ini tidak mengoptimalkan untuk aturan 2, tetapi itu memang paling sering menempatkan huruf pada tombol yang berbeda .

o={}
a=[]
b=['','','','','','','','']
i=-1
s.split('').forEach(function(x){o[x]=o[x]?o[x]+1:1})
for(x in o)a.push([o[x],x])
a.sort().reverse().forEach(function(x){b[i=(i+1)%8]+=x[1]})
alert(b)

Ini mungkin berada di Ruby, tapi saya tidak di rumah dan dipaksa untuk menggunakan Internet Explorer (eww). Tapi hei, kadang-kadang menyenangkan menggunakan bahasa yang mengerikan di golf ke golf! ;)

Output sampel (untuk input Anda):

avlc,sukb,otj,irh,zqg,ypf,xne,wmd

Karena JS tidak memiliki STDIN, program mengasumsikan bahwa input disimpan dalam variabel s.

Python (119-35 = 84):

Mengasumsikan string adalah variabel a, dan hanya berisi huruf kecil:

for h in range(8): print h+2,zip(*sorted([(__import__("collections").Counter(a)[d],d) for d in set(a)])[::-1])[1][h::8]

ungolfed:

import collections

#a="jackdawslovemybigsphinxofquartz"
a=__import__("string").lowercase

b=collections.Counter(a)

c=set(a)

d=[(b[d],d) for d in c]

e=sorted(d)

f=e[::-1]

g=zip(*f)[1]

for h in range(8): print h+2,g[h::8]

PYG (76-35 = 41):

Aaah, kita bisa menjatuhkan impor enourmous. Sekali lagi, ini mengasumsikan string yang dilucuti dalam a.

for h in R(8): print h+2,Z(*S([(CC(a)[d],d) for d in Se(a)])[::-1])[1][h::8]