Touches minimes nécessaires pour taper un texte donné

45

Nous savons tous que les programmeurs ont tendance à être paresseux. Afin de maximiser votre temps libre, vous décidez d'écrire un programme qui génère un nombre minimal de frappes pour le texte introduit.

Entrée : Texte à convertir en touches. Vous pouvez décider comment saisir le texte (STDIN / lecture d'un fichier fourni dans les arguments)

Sortie : Les actions nécessaires au format suivant:

  • Ils doivent être numérotés
  • Hit: appuyer sur une touche et la relâcher immédiatement
  • Press: appuyer sur une touche et ne pas la relâcher (ce ne sera jamais optimal lorsque la touche est Rrelâchée lors de la prochaine frappe)
  • Release: relâcher une Ptouche pressée

Exemple :

Contribution:

Hello!

Sortie:

Une solution naïve serait:

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

Ce serait plus efficace:

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

Environnement:

  • L'éditeur utilise une police monospaced
  • Le texte est enveloppé à 80 caractères
  • La flèche vers le haut et la flèche vers le bas préservent la colonne, même s'il y a des lignes plus courtes entre les deux.
  • Le presse-papiers est supposé vide
  • Le verrouillage numérique est supposé être activé
  • Le verrouillage des majuscules est supposé être désactivé
  • La majuscule ne fonctionne que pour les lettres (c.-à-d. Pas de majuscule)

Touches de raccourci / raccourcis :

  • Home: Aller au début de la ligne en cours
  • End: Aller à la fin de la ligne en cours
  • Ctrl+ A: Marquez tout
  • Ctrl+ C: Copie
  • Ctrl+ X: Couper
  • Ctrl+ V: Coller
  • Shift+ Déplacement du curseur: marquage
  • Ctrl+ F: Ouvre une boîte de dialogue de recherche.
    • Correspondance de texte stupide, pas d'expressions régulières
    • Sensible aux majuscules et minuscules
    • Recherches en boucle
    • Saisie de texte sur une seule ligne pour la recherche
    • L'entrée est préremplie avec la sélection actuelle, sauf s'il y a une nouvelle ligne entre les deux, l'entrée complète est sélectionnée
    • Copier / Coller fonctionne comme d'habitude
    • Appuyez sur pour Entereffectuer la recherche, en sélectionnant la première correspondance après la position actuelle du curseur.
  • F3: Répéter la dernière recherche
  • Ctrl+ H: Ouvre une boîte de dialogue de remplacement
    • Correspondance de texte stupide, pas d'expressions régulières
    • Sensible aux majuscules et minuscules
    • Tout remplacer, avec une enveloppe
    • Saisie de texte sur une seule ligne
    • L'entrée de recherche est préremplie avec la sélection actuelle. Sauf s'il y a une nouvelle ligne entre les deux, l'entrée complète est sélectionnée.
    • L'entrée de remplacement est vide
    • Copier / Coller fonctionne comme d'habitude
    • Tab saute à l'entrée de remplacement
    • Appuyez sur pour Entereffectuer le remplacement complet. Le curseur est placé après le dernier remplacement

Règles :

  • Les solutions doivent être un programme complet qui compile / analyse et exécute sans autre modification
  • Le clavier affiché ci-dessus est le clavier à utiliser
    • Il n'est pas nécessaire de gérer les caractères qui ne peuvent pas être saisis avec.
  • Chaque clé doit être relâchée à la fin
  • Le curseur n'a pas besoin d'être à la fin du fichier à la fin

Notation :

Votre score est la somme des actions nécessaires pour taper les textes suivants. Le gagnant est la solution avec le score le plus bas. J'utilise ma solution naïve 1371 + 833 + 2006 = 4210. Batte-le! Je choisirai un gagnant dans deux semaines.

1 Ma solution naïve

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 répétition facile

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

3 répétition plus complexe

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

Vous pouvez utiliser le programme de relecture que j'ai écrit pour tester vos solutions (Remarque: il ne prend pas encore en charge la recherche / remplacement, tout le reste devrait fonctionner).

code-challenge optimization keyboard TimWolla
la source
6
J'aimerais voir un programme comme celui-ci pour Vim.
Braden Best
4
Normalement, j'utilise la souris pour une partie de ces choses.
Victor Stafusa
1
Très intéressant. Je vais
essayer
2
Tu n'avais pas vraiment besoin de Rick Roll nous, n'est-ce pas? :)
Filip Haglund
1
Je suis un peu avec @ B1KMusic. Pour moi, il serait plus intéressant de générer des solutions pour vimgolf. (Ce qui équivaut à ce que vous essayez de faire ici en utilisant simplement les commandes vim.) Cela semble une idée amusante, mais il est très difficile de réduire les frappes au clavier (ou du moins, à mon avis), car il est difficile de sélectionner avec précision le mouvement. Cela rend le copier-coller très difficile et nécessite presque autant de frappes au clavier que la chose que vous tentiez de copier. (Ou du moins c'est comme ça que je lis comment fonctionne copier / coller). Et je ne vois pas beaucoup d'autres moyens de réduire le nombre de touches.
FDinoff

Réponses:

11

Haskell 1309 + 457 + 1618 = 3384

Enfin, une réponse (le score s’est considérablement amélioré une fois que j’ai réalisé qu’il y avait des onglets dans votre premier test: il fallait éditer la question pour voir ceux-ci). Compiler avec ghc, entrée de fourniture sur stdin. Exemple:

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

J’ai essayé des choses évidentes comme Dijkstra, mais c’était beaucoup trop lent, même après avoir réduit le branchement aux seuls mouvements utiles, à savoir: afficher la clé suivante ou copier depuis le début de la ligne (Maj + Début, Ctrl + C, Fin), ou coller.

Ainsi, cette approche utilise un presse-papiers de longueur fixe, copie lorsqu'un préfixe de ligne est sur le point de devenir "utile", et continue à utiliser ce préfixe tant qu'il est possible de le coller sur plus de lignes que les préfixes des lignes qu'il atteint ensuite. Lorsqu'il ne peut pas utiliser le Presse-papiers, il a recours à la solution naïve. Il est donc garanti de le vaincre une fois que la longueur choisie dépasse le coût d'une copie.

Le score minimum est atteint lorsque la longueur du préfixe est choisie pour correspondre à "Je ne vais jamais". Il existe des moyens d'améliorer la situation, mais j'en ai assez de lire 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
la source
Très bonne solution :) Btw: Vous pouvez supprimer quelques caractères supplémentaires en combinant les Pastes (si possible).
TimWolla
Cela n’affecte que vraiment l’exemple 2; j’avais une version de l’algorithme Dijkstra qui trouve cela, mais elle n’est utilisable que sur les 3 premières lignes. Vous pouvez améliorer ma solution pour tous les tests en essayant différentes tailles de préfixes; la solution est suffisamment rapide pour que vous puissiez le faire par force brute, il ne vous faut qu'environ 10 essais. Difficile à refacturer à cela dans haskell cependant.
Bazzargh