Pulsaciones mínimas necesarias para escribir un texto dado

45

Todos sabemos que los programadores tienden a ser flojos. Para maximizar su tiempo libre, decide escribir un programa que genere un número mínimo de pulsaciones de teclas para el texto que se le ingresa.

Entrada : Texto que debe convertirse en pulsaciones de teclas. Puede decidir cómo ingresar el texto (STDIN / lectura de un archivo proporcionado en los argumentos)

Salida : las acciones necesarias en el siguiente formato:

  • Deben estar numerados
  • Hit: presionando una tecla e inmediatamente soltándola
  • Press: presionar una tecla y no soltarla (esto nunca será óptimo cuando la tecla se Raprieta como la próxima pulsación)
  • Release: liberar una Ptecla ressed

Ejemplo :

Entrada:

Hello!

Salida:

Una solución ingenua sería:

1 P Shift
2 H h
3 R Shift
4 H e
5 H l
6 H l
7 H o
8 P Shift
9 H 1
10 R Shift

Esto sería más eficiente:

1 P Shift
2 H h
3 H 1
4 R Shift
5 H Left
6 H e
7 H l
8 H l
9 H o

Ambiente:

  • El editor usa una fuente monoespaciada
  • El texto está envuelto suavemente en 80 caracteres.
  • La flecha hacia arriba y la flecha hacia abajo conservan la columna, incluso si hay líneas más cortas entre
  • Se supone que el portapapeles está vacío.
  • Se supone que el bloqueo numérico está habilitado
  • Se supone que el bloqueo de mayúsculas está desactivado
  • El bloqueo de mayúsculas solo funciona para las letras (es decir, sin bloqueo de mayúsculas)

Teclas de acceso rápido / atajos :

  • Home: Salta al comienzo de la línea actual
  • End: Salta al final de la línea actual
  • Ctrl+ A: Marcar todo
  • Ctrl+ C: Copiar
  • Ctrl+ X: Corte
  • Ctrl+ V: Pegar
  • Shift+ Cursor en movimiento: marcado
  • Ctrl+ F: Abre un cuadro de diálogo de búsqueda.
    • Estúpida coincidencia de texto, sin expresiones regulares
    • Distingue mayúsculas y minúsculas
    • Búsquedas envolventes
    • Entrada de texto de una sola línea para la búsqueda.
    • La entrada se completa previamente con la selección actual, a menos que haya una nueva línea intermedia, se selecciona la entrada completa
    • Copiar / pegar funciona como siempre
    • Al presionar se Enterrealiza la búsqueda, seleccionando la primera coincidencia después de la posición actual del cursor
  • F3: Repite la última búsqueda
  • Ctrl+ H: Abre un diálogo de reemplazo
    • Estúpida coincidencia de texto, sin expresiones regulares
    • Distingue mayúsculas y minúsculas
    • Reemplazar todo, con envoltura
    • Entradas de texto de una sola línea
    • La entrada de búsqueda se completa previamente con la selección actual, a menos que haya una nueva línea intermedia, se selecciona la entrada completa
    • La entrada de reemplazo está vacía
    • Copiar / pegar funciona como siempre
    • Tab salta a la entrada de reemplazo
    • Al presionar se Enterrealiza el reemplazo de todo. El cursor se coloca después del último reemplazo.

reglas :

  • Las soluciones deben ser un programa completo que compila / analiza y ejecuta sin ninguna otra modificación
  • El teclado que se muestra arriba es el teclado a usar
    • No es necesario manejar caracteres que no se pueden escribir con él
  • Cada clave debe ser liberada al final
  • El cursor no necesita estar al final del archivo al final

Puntuación :

Su puntaje es la suma de la cantidad de acciones necesarias para escribir los siguientes textos. El ganador es la solución con la puntuación más baja. Usando mi solución ingenua que obtengo 1371 + 833 + 2006 = 4210. ¡Batirlo! Elegiré un ganador en dos semanas.

1 Mi solución ingenua

number = 1

H = (char) -> console.log "#{number++} H #{char}"
P = (char) -> console.log "#{number++} P #{char}"
R = (char) -> console.log "#{number++} R #{char}"

strokes = (text) ->
    shiftActive = no

    for char in text
        if /^[a-z]$/.test char
            if shiftActive
                R "Shift"
                shiftActive = no

            H char
        else if /^[A-Z]$/.test char
            unless shiftActive
                P "Shift"
                shiftActive = yes

            H char.toLowerCase()
        else
            table =
                '~': '`'
                '!': 1
                '@': 2
                '#': 3
                '$': 4
                '%': 5
                '^': 6
                '&': 7
                '*': 8
                '(': 9
                ')': 0
                '_': '-'
                '+': '='
                '|': '\\'
                '<': ','
                '>': '.'
                '?': '/'
                ':': ';'
                '"': "'"
                '{': '['
                '}': ']'

            if table[char]?
                unless shiftActive
                    P "Shift"
                    shiftActive = yes

                H table[char]
            else
                H switch char
                    when " " then "Space"
                    when "\n" then "Enter"
                    when "\t" then "Tab"
                    else
                        if shiftActive
                            R "Shift"
                            shiftActive = no

                        char
    R "Shift" if shiftActive

input = ""

process.stdin.on 'data', (chunk) -> input += chunk
process.stdin.on 'end', -> strokes input

2 fácil repetición

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ
KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

3 repetición más compleja

We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

We've known each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it
And if you ask me how I'm feeling
Don't tell me you're too blind to see

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

(Ooh, give you up)
(Ooh, give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)
(Ooh)
Never gonna give, never gonna give
(Give you up)

We've know each other for so long
Your heart's been aching but
You're too shy to say it
Inside we both know what's been going on
We know the game and we're gonna play it

I just wanna tell you how I'm feeling
Gotta make you understand

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

Puede usar el programa de reproducción escrito por mí para probar sus soluciones (Nota: todavía no admite la búsqueda / reemplazo, todo lo demás debería funcionar).

code-challenge optimization keyboard TimWolla
fuente
66
Me encantaría ver un programa como este para vim.
Braden Best
44
Normalmente uso el mouse para parte de esas cosas.
Victor Stafusa
1
Muy interesante. Voy a ir por la mañana; 3
cjfaure
2
Realmente no tenías que rodarnos Rick, ¿verdad? :)
Filip Haglund
1
Estoy un poco con @ B1KMusic. Para mí, sería más interesante generar soluciones para vimgolf. (Que es el equivalente de lo que está tratando de hacer aquí simplemente usando los comandos vim). Sin embargo, esto parece una idea divertida de reducir las pulsaciones de teclas es muy difícil (o al menos eso creo), ya que el movimiento preciso para la selección es difícil. Esto hace que copiar y pegar sea una tarea realmente difícil y requiere casi tantas pulsaciones de teclas como la que estaba intentando copiar. (O al menos así es como estoy leyendo cómo funciona copiar y pegar). Y no veo muchas otras formas de reducir las pulsaciones de teclas.
FDinoff

Respuestas:

11

Haskell 1309 + 457 + 1618 = 3384

Finalmente, una respuesta (el puntaje mejoró una vez que me di cuenta de que hay pestañas en su primera prueba: tuve que editar la pregunta para verlas). Compilar con ghc, suministrar entrada en stdin. Ejemplo:

$ ghc keyboard.hs && echo hello|./keyboard
1 H h
2 H e
3 H l
4 H l
5 H o
6 H Enter

Probé cosas obvias como Dijkstra, pero fue demasiado lento, incluso después de reducir la ramificación a los únicos movimientos útiles, que son: generar la siguiente tecla o copiar desde el inicio de la línea (Shift + Home, Ctrl + C, Fin) o pegar.

Por lo tanto, este enfoque utiliza un portapapeles de longitud fija, copia cuando un prefijo de línea está a punto de ser `` útil '', y sigue usando ese prefijo siempre que sea pegable en más líneas que los prefijos de líneas que llega a continuación. Cuando no puede usar el portapapeles, recurre a la solución ingenua, por lo que se garantiza que la superará una vez que la longitud elegida sea mayor que el costo de una copia.

El puntaje mínimo se logra cuando se elige la longitud del prefijo para que se ajuste a "Never going". Hay maneras de mejorar esto, pero ya he tenido suficiente de leer a Rick Astley.

import Data.List (isPrefixOf,isInfixOf)
import Control.Monad (foldM)
plen=12
softlines text=sl 0 [] text
  where
    sl n [] [] = []
    sl n acc [] = [(n,reverse acc)]
    sl n acc (x:xs)
      |x=='\n'||length acc==79=(n,reverse (x:acc)):(sl (n+1) [] xs)
      |otherwise=sl n (x:acc) xs
pasteable (a,b) (c,d)=(c>a && b`isInfixOf`d)
                      || (c==a && b`isInfixOf`(drop (length b) d))
findprefixes l=filter (\(a,b,c)->c/=[])
               $ map (\(a,b)->(a, b, map fst $ filter (pasteable (a,b)) l))
               $ filter (\(a,b)->length b==plen && last b/='\n')
               $ map (\(a,b)->(a, take plen b)) l
mergePrefixes [] = []
mergePrefixes (p:ps) = mergePrefixes' p ps
 where mergePrefixes' p [] = [p]
       mergePrefixes' (a,x,b) ((c,y,d):qs) =
         if length (filter (>=c) b) >= length d then
           mergePrefixes' (a,x,b) qs
         else
           (a, x, (filter (<c) b)):(mergePrefixes' (c,y,d) qs)
uc = ("~!@#$%^&*()_+<>?:{}|\""++['A'..'Z'])
lc = ("`1234567890-=,./;[]\\'"++['a'..'z'])
down c = case [[lo]|(lo,hi)<-zip lc uc,c==hi] of []->error [c];p->head p
applyPrefixToLine prefix [] s=return s
applyPrefixToLine [] line s=emit line s
applyPrefixToLine prefix line@(ch:rest) s=
 if prefix`isPrefixOf`line then
   do { s<-emitPaste s; applyPrefixToLine prefix (drop (length prefix) line) s}
 else
   do { s<-emitch s ch; applyPrefixToLine prefix rest s}
type Keystroke = (Char, [Char])
key action k (n, shift) = do
  putStrLn ((show n)++" "++[action]++" "++k)
  if k=="Shift" then return (n+1, (not shift))
  else return (n+1, shift)
emitch (m, shift) ch=
  case ch of
    '\t'->key 'H' "Tab" (m,shift)
    '\n'->key 'H' "Enter" (m,shift)
    ' '->key 'H' "Space" (m,shift)
    _->
      if shift && ch`elem`lc then
        do { key 'R' "Shift" (m, True); key 'H' [ch] (m+1, False) }
      else if not shift && ch`elem`uc then
             do { key 'P' "Shift" (m, False); key 'H' (down ch) (m+1, True) }
           else if ch`elem`lc
                then key 'H' [ch] (m, shift)
                else key 'H' (down ch) (m, shift)
emit line s = foldM emitch s line
emitPaste s = do
  s<-key 'P'"Ctrl" s
  s<-key 'H' "v" s
  key 'R' "Ctrl" s
emitCopy s = do
  s<-key 'H' "Home" s
  s<-key 'P'"Ctrl" s
  s<-key 'H' "c" s
  s<-key 'R' "Ctrl" s
  s<-key 'R' "Shift" s
  key 'H' "End" s
applyPrefix pf ((a,b):xs) p@((c,y,d):ps) s=
  if (c==a) then
    do
      s@(n, shift) <- emit y s
      s <- if shift then return s else key 'P' "Shift" s
      s <- emitCopy s
      s <- applyPrefixToLine y (drop (length y) b) s
      applyPrefix y xs ps s
  else
    do
      s<-applyPrefixToLine pf b s
      applyPrefix pf xs p s
applyPrefix "" ((a,b):xs) [] s=
  do
    s <- emit b s
    applyPrefix "" xs [] s
applyPrefix pf ((a,b):xs) [] s=
  do
    s<-applyPrefixToLine pf b s
    applyPrefix pf xs [] s
applyPrefix _ [] _ s=return s

main=do
  input <- getContents
  let lines = softlines input
  let prefixes = mergePrefixes (findprefixes lines)
  (n,shift) <- applyPrefix "" lines prefixes (1, False)
  if shift then
    key 'R' "Shift" (n, shift)
  else
    return(n,shift)
bazzargh
fuente
Muy buena solución :) Por cierto: puede eliminar algunos caracteres más combinando las pastas (si es posible).
TimWolla
Eso solo afecta realmente el ejemplo 2: tenía una versión del algoritmo Dijkstra que lo encuentra, pero solo se puede usar contra las primeras 3 líneas. Puede mejorar mi solución para todas las pruebas probando diferentes tamaños de prefijo; la solución es lo suficientemente rápida como para que pueda hacerlo por fuerza bruta, solo se requieren aproximadamente 10 carreras. Aunque es incómodo refactorizar eso en Haskell.
bazzargh