Il semble exister cet engouement persistant pour les personnes qui apprennent de manière laborieuse de nouvelles configurations de clavier comme Dvorak ou Neo, car cela les rend soi-disant plus productives. Je soutiens que changer de disposition du clavier est une mauvaise idée car cela peut prendre des mois avant de devenir rapide et quand vous êtes finalement 5% plus rapide que le reste, vous êtes foutu si vous devez taper sur un ordinateur qui n'est pas pas la vôtre.

En outre, toutes ces personnes oublient le véritable goulet d'étranglement de la communication moderne: le clavier du téléphone.

Voici à quoi ressemble votre clavier téléphonique moyen:

La lettre 'r' est la troisième lettre du bouton 7; ainsi, si vous deviez taper la lettre «r» sur un téléphone portable, vous auriez appuyé trois fois sur la touche 7, 4 fois sur «7» et une fois sur la touche 2.

En considérant cela, mettre 'e' après 'd' était probablement une mauvaise décision - 'e' est la lettre la plus utilisée dans l'alphabet anglais, donc si vous deviez étiqueter le bouton 3 "EDF" au lieu de "DEF", permettrait d'économiser beaucoup de frappes.

De plus, vous vous êtes probablement déjà rendu compte que taper 2 lettres qui partagent le même bouton est une nuisance - si vous voulez écrire "TU", vous ne pouvez pas appuyer simplement sur 8 trois fois, car cela donnerait "V". Donc, généralement, vous écrivez «T», puis appuyez sur espace, puis sur retour arrière, puis écrivez «U», ce qui équivaut à 5 pressions de bouton au lieu de 3.

TL; DR

Étant donné ces deux règles:

• Une lettre est tapée n fois, en appuyant sur un bouton, où n est l'emplacement où se trouve la lettre sur l'étiquette du bouton.
• L'écriture de deux lettres tapées à l'aide du même bouton nécessite 2 appuis supplémentaires.

Quelle est la disposition du clavier du téléphone qui nécessite le moins d'appuis au clavier, en fonction d'un texte spécifique? Vous ne devez utiliser que les boutons 2 à 9, 1 et 0 réservés aux symboles spéciaux.

Contribution

Le texte pour lequel vous devez trouver la mise en page optimale est fourni via stdin. Vous n'avez pas besoin de manipuler autre chose que l'alphabet minuscule et pouvez supposer que la saisie est constituée de seulement cela. Vous pouvez également supposer que le texte saisi est relativement long et que chaque lettre y est insérée au moins une fois, si cela vous aide.

Sortie

Je ne veux pas imposer trop de contraintes à la sortie, car cela donne parfois des avantages à certaines langues par rapport à d’autres; donc, cependant, votre langue montre que les tableaux sont bons, sinon vous pouvez séparer chaque étiquette avec une nouvelle ligne.

Il peut y avoir plusieurs mises en page optimales possibles, vous pouvez en imprimer une seule. Voici un exemple simple:

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

Points bonus

-35 si votre algorithme ne force pas toutes les mises en page possibles (je regarde les "permutations" de Haskell ici)

-3 Si votre code correspond à un message texte (140 caractères) et que vous postez une photo de vous en envoyant votre code à un ami.

Ceci est mon premier défi sur StackExchange. Je serais heureux de savoir si vous l'aimez ou si vous avez d'autres commentaires à ce sujet!

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

Voici une tentative d'optimisation pour la règle n ° 2. Après mon commentaire, ci-dessus, et au lieu de réponses prenant en compte cette règle (cf. indice de question élevé), je pensais devoir faire un effort ici ...

Les solutions qui n'optimisent pas pour la règle n ° 2 peuvent produire des résultats très loin d'être optimaux. J'ai vérifié un long texte anglais naturel ("Alice au pays des merveilles", en fait), un traitement préliminaire (lettres minuscules uniquement) et, par exemple, le script Perl de la réponse d'OJW, le résultat étant

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

er seule la ruine, plus quelques autres paires n'auraient jamais dû se terminer sur la même clé ...

Btw, zxqjvkbpfmygwculdrshnioatesont des lettres triées, fréquence croissante, de ce texte.

Si nous essayons de résoudre ce problème facilement (en espérant un bonus de -35, peut-être) et que nous plaçons les lettres une par une, en choisissant la clé disponible par compte minimal par paire, nous pouvons terminer avec, par exemple:

slbx
hdmz
nrf
iuj
ogv
awk
tcp
eyq

Je ne poste pas le code pour cette (mauvaise) solution ici. Par exemple, remarque, cest plus fréquent que wet est placé en premier. tcLes ctpaires ( ) sont évidemment moins fréquentes que ac( ca) - 43 + 235 contre 202 + 355. Mais wfinit avec a- 598 + 88. Nous terminons avec des paires awet tc(964 au total), bien que ce serait mieux acet tw(635 au total). Etc..

Ainsi, l'algorithme suivant essaie de vérifier chacune des 8 lettres les plus fréquentes restantes (ou 2 si c'est le dernier) par rapport aux lettres déjà présentes sur le clavier, et de les placer de manière à ce que le nombre de paires soit 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.

Le résultat est:

sdfz
hlmx
nrv
iyp
ogk
acq
twb
euj

Je n'aime pas la acpaire (le chat étant l'un des personnages, après tout), mais c'est quand même un placement optimal des lettres pour l'anglais, si mon code n'est pas faux. Pas exactement un effort de «golf», juste une solution de travail, moche ou pas.

Python3, c'est l'heure de Montecarlo!

Pour résoudre ce problème, je compte d’abord le nombre de "clics" dont vous avez besoin avec le clavier par défaut (au départ:) abc,def,ghi,jkl,mno,pqrs,tuv,wxyz. Ensuite, je modifie ce clavier et vois s'il est moins cher (le texte est écrit en moins de clics). Si ce clavier est moins cher, alors il devient celui par défaut. Je répète ce processus 1Mfois.

Pour changer le clavier, je décide d’abord du nombre de modifications à effectuer (le nombre maximal de modifications correspond au nombre total de lettres sur le clavier). Ensuite, pour chaque commutateur, je choisis deux boutons et deux positions et je transfère un caractère de la première à la seconde.

Le nombre maximal de commutateurs par heure correspond au nombre de lettres du clavier, car il s'agit du nombre minimal de modifications dont vous avez besoin pour passer de deux claviers complètement différents. (Je veux qu'il soit toujours possible de passer d'un clavier à un autre)

La sortie de echo "jackdawslovemybigsphinxofquartz" | python .\myscript.pyest:

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

Où 61est le nombre de bouton enfoncé pour composer un message donné.

Caractères (pas d'espaces ni de commentaires): 577

Je sais que c'est long mais je suis vraiment nouveau dans ce domaine.

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)

Je l'ai trouvé tellement drôle que j'ai décidé d'essayer cet algorithme avec LO HOBBIT (j'ai aussi une copie originale à la maison!). Il a des 383964lettres et ce sont les quelques clics vs clavier que je trouve:

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

Je prétends donc que ce dernier est l’un des claviers les plus pratiques (en termes de clics).

Eh bien, si vous voulez juste les personnages les plus populaires affectés aux cases 2-9, Perl peut le faire en 127 caractères ...

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

donner quelque chose comme:

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

Ou imprimez le tout sur une ligne en supprimant 12 caractères:

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

Exemple:

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

On pourrait soutenir que cela n'optimise pas la règle 2, mais que les lettres les plus fréquentes sont placées sur des clés différentes .

JavaScript, 192 - 35 = 157

Je viens de remarquer la règle des personnages à répéter; cela ne prend pas cela en compte. Mais comme @mniip a noté dans sa réponse:

On pourrait soutenir que cela n'optimise pas la règle 2, mais que les lettres les plus fréquentes sont placées sur des clés différentes .

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)

Cela aurait probablement été en Ruby, mais je ne suis pas chez moi et je suis obligé d'utiliser Internet Explorer (eww). Mais bon, il est parfois amusant d’utiliser des langues terribles entre golf et golf! ;)

Exemple de sortie (pour votre saisie):

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

Comme JS n’a pas de STDIN, le programme suppose que l’entrée est stockée dans une variable s.

Python (119-35 = 84):

En supposant que la chaîne est une variable a et ne contient que des lettres minuscules:

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, nous pouvons laisser tomber l'énorme importation. Encore une fois, cela suppose que la chaîne dénudée est en a.

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