Parece haber esta locura constante por las personas que aprenden tediosamente nuevos diseños de teclado como Dvorak o Neo porque supuestamente los hace más productivos. Sostengo que cambiar la distribución del teclado es una mala idea, ya que puede llevarle meses ponerse al día, y cuando finalmente es un 5% más rápido que el resto, está jodido si necesita escribir en una computadora que no Es tuyo.

Además, todas estas personas olvidan dónde está el verdadero cuello de botella en la comunicación moderna: el teclado del teléfono.

Así es como se ve su teclado telefónico promedio:

La letra 'r' es la tercera letra del botón 7; así que si tuviera que escribir la letra 'r' en un teléfono móvil, presionaría el botón 7 tres veces, para 's' la presionaría 4 veces y para 'a' presionaría el botón 2 una vez.

Teniendo esto en cuenta, poner 'e' después de 'd' probablemente fue una mala decisión: 'e' es la letra más comúnmente utilizada en el alfabeto inglés, por lo tanto, si tuviera que etiquetar el botón 3 "EDF" en lugar de "DEF", usted ahorraría muchas pulsaciones de teclas.

Además, probablemente haya experimentado que escribir 2 letras que comparten el mismo botón es una molestia: si desea escribir "TU", no puede simplemente presionar 8 tres veces, porque eso daría como resultado 'V'. Por lo general, escribiría 'T', luego presionaría el espacio, luego la tecla de retroceso y luego escribiría 'U', que equivale a 5 pulsaciones de botón en lugar de 3.

TL; DR

Dadas estas dos reglas:

• Una letra se escribe presionando un botón n veces, donde n es la posición donde se encuentra la letra en la etiqueta del botón
• Escribir dos letras que se escriben con el mismo botón requiere presionar 2 botones adicionales

¿Cuál es la distribución del teclado del teléfono que requiere la menor cantidad de pulsaciones de botón, dado un texto específico? Solo debe usar los botones 2-9, 1 y 0 están reservados para símbolos especiales.

Entrada

El texto para el que debe encontrar el diseño óptimo se proporciona a través de stdin. No necesita manejar nada más que el alfabeto en minúsculas y puede suponer que la entrada consiste solo en eso. También puede suponer que el texto de entrada es razonablemente grande y que cada letra está allí al menos una vez, si eso ayuda.

Salida

No quiero poner demasiadas restricciones en la salida, ya que eso a veces da ventajas a algunos idiomas sobre otros; así que, sin embargo, su idioma muestra que las matrices están bien, alternativamente, puede separar cada etiqueta con una nueva línea.

Puede haber múltiples diseños óptimos posibles, puede imprimir cualquiera de ellos. Aquí hay un ejemplo simple:

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

Puntos extra

-35 si su algoritmo no es de fuerza bruta todos los diseños posibles (estoy viendo las 'permutaciones' de Haskell aquí)

-3 si su código cabe dentro de un mensaje de texto (140 caracteres) y publica una foto de usted enviando su código a un amigo.

Este es mi primer desafío en StackExchange. Me encantaría saber si te gusta o si tienes algún otro comentario al respecto.

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

Aquí hay un intento de optimizar para la regla # 2. Después de mi comentario, más arriba, y en lugar de las respuestas que toman en cuenta esa regla (cf. calificación alta de preguntas), pensé que debo algo de esfuerzo aquí ...

Las soluciones que no se optimizan para la regla # 2 pueden producir resultados muy lejos de ser óptimos. Verifiqué el texto largo en inglés natural ("Alicia en el país de las maravillas", en realidad), preprocesado (solo letras minúsculas) y, por ejemplo, el script Perl de la respuesta de OJW, el resultado es

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

er solo lo arruina, además de que otros pares nunca deberían haber terminado en la misma tecla ...

Por cierto, zxqjvkbpfmygwculdrshnioateson letras ordenadas, frecuencia ascendente, de ese texto.

Si tratamos de resolverlo de una manera fácil (esperando un bono de -35, tal vez) y colocar letras una por una, eligiendo la clave disponible por un recuento mínimo por pares, podemos terminar con, por ejemplo:

slbx
hdmz
nrf
iuj
ogv
awk
tcp
eyq

No publico código para esta solución (incorrecta) aquí. Por ejemplo, nota, ces más frecuente wy se coloca primero. tc( ct) los pares son obviamente menos frecuentes que ac( ca) - 43 + 235 contra 202 + 355. Pero luego wtermina con a- 598 + 88. Terminamos con pares awy tc(964 en total), aunque sería mejor acy tw(635 en total). Etc ..

Entonces, el siguiente algoritmo intenta verificar cada una de las 8 letras restantes (o 2, si es la última) más frecuentes contra las letras que ya están en el teclado, y ubicarlas para que el recuento por pares sea mínimo.

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

El resultado es:

sdfz
hlmx
nrv
iyp
ogk
acq
twb
euj

No me gusta la acpareja (el gato es uno de los personajes, después de todo), pero, aun así, esa es la ubicación óptima de las letras en inglés, si mi código no es incorrecto. No es exactamente un esfuerzo de "golf", solo una solución de trabajo, fea o no.

Python3, ¡es hora de Montecarlo!

Para resolver este problema, primero cuento cuántos "clics" necesita con el teclado predeterminado (inicialmente:) abc,def,ghi,jkl,mno,pqrs,tuv,wxyz. Luego modifico este teclado y veo si es más barato (el texto se escribe con menos clics). Si este teclado es más barato, se convierte en el predeterminado. Repito este proceso 1Mveces.

Para cambiar el teclado, primero decido cuántos cambios hacer (el número máximo de cambios es el número total de letras en el teclado). Luego, para cada cambio, elijo dos botones y dos posiciones y transfiero un personaje de la primera posición a la segunda.

El número máximo de interruptores por hora es el número de letras en el teclado porque es el número mínimo de cambios que necesita para cambiar desde dos teclados diferentes. (Quiero que siempre sea posible cambiar de un teclado a otro)

La salida de echo "jackdawslovemybigsphinxofquartz" | python .\myscript.pyes:

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

¿Dónde 61está el número de botón presionado para componer un mensaje dado?

Caracteres (sin espacios ni comentarios): 577

Sé que es largo pero soy realmente nuevo en esto.

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)

Me pareció tan divertido que decidí probar este algoritmo con LO HOBBIT (¡también tengo una copia original en casa!). Tiene 383964letras y estos son los dos clics vs teclado que estoy encontrando:

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

Así que afirmo que este último es uno de los teclados más prácticos (en términos de clics).

Bueno, si solo quieres que los personajes más populares se asignen a los contenedores 2-9, Perl puede hacerlo en 127 caracteres ...

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

dando algo como:

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

O imprímalo todo en una línea, eliminando 12 caracteres:

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

Ejemplo:

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

Se podría argumentar que esto no se optimiza para la regla 2, pero sí pone las letras más frecuentes en diferentes teclas.

JavaScript, 192-35 = 157

Acabo de notar la regla de los personajes que se repiten; Esto no tiene eso en cuenta. Pero como @mniip señaló en su respuesta:

Se podría argumentar que esto no se optimiza para la regla 2, pero sí pone las letras más frecuentes en diferentes teclas.

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)

Esto probablemente hubiera estado en Ruby, pero no estoy en casa y me veo obligado a usar Internet Explorer (eww). Pero bueno, ¡a veces es divertido usar idiomas terribles para jugar al golf! ;)

Salida de muestra (para su entrada):

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

Como JS no tiene STDIN, el programa supone que la entrada se almacena en variable s.

Python (119-35 = 84):

Asumiendo que la cadena es una variable a, y solo contiene letras minúsculas:

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]

sin golf:

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, podemos soltar la enorme importación. Nuevamente, esto supone que la cadena despojada 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]