Wydaje się, że istnieje ciągłe szaleństwo, gdy ludzie żmudnie uczą się nowych układów klawiatury, takich jak Dvorak lub Neo, ponieważ podobno sprawia to, że są bardziej produktywni. Twierdzę, że zmiana układu klawiatury jest złym pomysłem, ponieważ przyśpieszenie może ci zająć miesiące, a kiedy jesteś ostatecznie o 5% szybszy niż reszta, wkręca cię, jeśli musisz pisać na komputerze, który nie jest twój własny.

Ponadto wszyscy ci ludzie zapominają, gdzie leży prawdziwe wąskie gardło we współczesnej komunikacji - klawiatura telefoniczna.

Oto jak wygląda przeciętna klawiatura telefonu:

Litera „r” jest trzecią literą na przycisku 7; więc jeśli miałbyś wpisać literę „r” na telefonie komórkowym, nacisnąłbyś przycisk 7 trzy razy, dla „s” nacisnąłbyś go 4 razy, a dla „a” nacisnąłbyś przycisk 2 raz.

Biorąc to pod uwagę, umieszczenie „e” po „d” było prawdopodobnie złą decyzją - „e” jest najczęściej używaną literą w alfabecie angielskim, więc jeśli miałbyś oznaczyć przycisk 3 „EDF” zamiast „DEF”, zaoszczędziłoby sporo naciśnięć klawiszy.

Co więcej, prawdopodobnie doświadczyłeś już, że pisanie 2 liter, które korzystają z tego samego przycisku, jest uciążliwe - jeśli chcesz napisać „TU”, nie możesz po prostu nacisnąć 8 trzy razy, ponieważ spowodowałoby to „V”. Tak więc zwykle piszesz „T”, następnie naciskasz spację, następnie naciskasz backspace, a następnie piszesz „U”, co odpowiada 5 naciśnięciom przycisków zamiast 3.

TL; DR

Biorąc pod uwagę te dwie zasady:

• Litera jest wpisywana przez naciśnięcie przycisku n razy, gdzie n oznacza pozycję litery na etykiecie przycisku
• Pisanie dwóch liter, które są wpisywane za pomocą tego samego przycisku, wymaga dodatkowych 2 naciśnięć przycisku

Jaki jest układ klawiatury telefonu, który wymaga najmniejszej liczby naciśnięć przycisków, biorąc pod uwagę określony tekst? Należy używać tylko przycisków 2-9, 1 i 0, które są zarezerwowane dla symboli specjalnych.

Wkład

Tekst, dla którego powinieneś znaleźć optymalny układ, jest dostarczany przez stdin. Nie musisz obsługiwać niczego innego niż małe litery i możesz założyć, że dane wejściowe składają się tylko z tego. Możesz również założyć, że tekst wejściowy jest dość duży i każda litera jest tam co najmniej raz, jeśli to pomoże.

Wydajność

Nie chcę nakładać zbyt wielu ograniczeń na dane wyjściowe, ponieważ czasami daje to jedne języki przewagę nad innymi; więc jednak twój język pokazuje, że tablice są w porządku, alternatywnie możesz oddzielić każdą etykietę nowym wierszem.

Może istnieć wiele możliwych optymalnych układów, możesz wydrukować dowolny z nich. Oto prosty przykład:

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

Punkty bonusowe

-35, jeśli twój algorytm nie wymusza brutalnie wszystkich możliwych układów (tutaj patrzę na `` permutacje '' Haskella)

-3, jeśli Twój kod mieści się w wiadomości tekstowej (140 znaków), a Ty wysyłasz zdjęcie, że wysyłasz swój kod znajomemu.

To jest moje pierwsze wyzwanie na StackExchange. Z przyjemnością usłyszę, czy Ci się podoba, czy masz jakieś uwagi na ten temat!

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

Oto próba optymalizacji dla reguły nr 2. Po moim komentarzu powyżej i zamiast odpowiedzi, które uwzględniają tę zasadę (por. Wysoka ocena pytania), pomyślałem, że jestem tutaj winien trochę wysiłku ...

Rozwiązania, które nie optymalizują się pod kątem reguły 2, mogą generować wyniki dalekie od optymalnych. Sprawdziłem długi naturalny tekst w języku angielskim (właściwie „Alicja w krainie czarów”), wstępnie przetworzony (tylko małe litery) i np. Skrypt Perla z odpowiedzi OJW, wynik był

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

er sam go rujnuje, a niektóre inne pary nigdy nie powinny kończyć się na tym samym kluczu ...

Btw, zxqjvkbpfmygwculdrshnioatesą to litery posortowane z częstotliwością rosnącą od tego tekstu.

Jeśli spróbujemy rozwiązać ten problem w prosty sposób (może licząc na premię -35) i umieszczać litery jeden po drugim, wybierając dostępny klucz według minimalnej liczby par, możemy zakończyć np .:

slbx
hdmz
nrf
iuj
ogv
awk
tcp
eyq

Nie zamieszczam tutaj kodu dla tego (złego) rozwiązania. Np. Uwaga cjest częstsza niż wi umieszczana na pierwszym miejscu. Pary tc( ct) są oczywiście rzadsze niż ac( ca) - 43 + 235 w stosunku do 202 + 355. Ale potem wkończy się naa - 598 + 88. Kończymy parami awi tc(łącznie 964), choć byłoby lepiejac i tw(łącznie 635). Itp..

Zatem następny algorytm próbuje sprawdzić każde 8 pozostałych (lub 2, jeśli ostatnie) najczęstsze litery względem liter już znajdujących się na klawiaturze i umieścić je tak, aby liczba par była minimalna.

$_=<>;                          # 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.

Wynik to:

sdfz
hlmx
nrv
iyp
ogk
acq
twb
euj

Nie podoba mi się ta acpara (w końcu Kot jest jedną z postaci), ale nadal jest to optymalne rozmieszczenie liter dla języka angielskiego, jeśli mój kod nie jest zły. Niezupełnie wysiłek „golfowy”, tylko jakieś działające rozwiązanie, brzydkie czy nie.

Python3, czas na Montecarlo!

Aby rozwiązać ten problem, najpierw liczę, ile „kliknięć” potrzebujesz z domyślną klawiaturą (początkowo:) abc,def,ghi,jkl,mno,pqrs,tuv,wxyz. Następnie modyfikuję tę klawiaturę i sprawdzam, czy jest tańsza (tekst jest pisany mniejszą liczbą kliknięć). Jeśli ta klawiatura jest tańsza, staje się domyślną. Powtarzam ten proces1M czas .

Aby zmienić klawiaturę, najpierw decyduję, ile zmian wprowadzić (maksymalna liczba zmian to całkowita liczba liter w klawiaturze). Następnie dla każdego przełącznika wybieram dwa przyciski i dwie pozycje i przenoszę znak z pierwszej pozycji na drugą.

Maksymalna liczba przełączników na raz to liczba liter na klawiaturze, ponieważ jest to minimalna liczba zmian, które należy przełączyć z dwóch kompletnych różnych klawiatur. (Chcę, aby zawsze było możliwe przejście z jednej klawiatury na inną)

Dane wyjściowe echo "jackdawslovemybigsphinxofquartz" | python .\myscript.pyto:

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

Gdzie 61jest liczba naciśniętych przycisków, aby utworzyć daną wiadomość.

Znaki (bez spacji i komentarzy): 577

Wiem, że to długo, ale jestem naprawdę nowy w tych sprawach.

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)

Uznałem to za tak zabawne, że postanowiłem wypróbować ten algorytm przy użyciu LO HOBBIT (mam też oryginalną kopię w domu!). Ma 383964litery i oto kilka kliknięć w porównaniu z klawiaturą, które znajduję:

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']

Twierdzę więc, że ta ostatnia jest jedną z najbardziej praktycznych klawiatur (pod względem kliknięć).

Cóż, jeśli chcesz tylko najbardziej popularne postacie przypisane do pojemników 2-9, Perl może to zrobić w 127 znakach ...

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

dając coś takiego:

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

Lub wydrukuj wszystko w jednym wierszu, usuwając 12 znaków:

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

Przykład:

$ 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"]

Można argumentować, że nie optymalizuje to reguły 2, ale umieszcza najczęstsze litery na różnych klawiszach.

JavaScript, 192–35 = 157

Właśnie zauważyłem zasadę powtarzania znaków; to nie bierze tego pod uwagę. Ale jak zauważył @mniip w swojej odpowiedzi:

Można argumentować, że nie optymalizuje to reguły 2, ale umieszcza najczęstsze litery na różnych klawiszach.

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)

Prawdopodobnie byłby to w Ruby, ale nie ma mnie w domu i jestem zmuszony do korzystania z Internet Explorera (eww). Ale hej, czasem fajnie jest używać języków okropnych podczas gry w golfa! ;)

Przykładowe dane wyjściowe (do wprowadzenia):

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

Ponieważ JS nie ma STDIN, program zakłada, że ​​dane wejściowe są przechowywane w zmiennej s.

Python (119-35 = 84):

Zakładając, że ciąg jest zmienną a i zawiera tylko małe litery:

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]

bez golfa:

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

O tak, możemy porzucić ten wspaniały import. Ponownie, zakłada to, że pozbawiony łańcucha jest w.

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