Minimale Tastenanschläge zum Eingeben eines bestimmten Textes

45

Wir alle wissen, dass Programmierer faul sind. Um Ihre Freizeit zu maximieren, beschließen Sie, ein Programm zu schreiben, das eine minimale Anzahl von Tastenanschlägen für eingegebenen Text ausgibt.

Eingabe : Text, der in Tastenanschläge konvertiert werden muss. Sie können entscheiden, wie der Text eingegeben werden soll (STDIN / Lesen aus einer in den Argumenten angegebenen Datei)

Ausgabe : Die notwendigen Aktionen im folgenden Format:

  • Sie müssen nummeriert sein
  • Hit: Eine Taste drücken und sofort loslassen
  • Press: Drücken und nicht loslassen einer Taste (dies ist niemals optimal, wenn die Taste Rbeim nächsten Tastendruck losgelassen wird)
  • Release: PLösen eines ressed Schlüssels

Beispiel :

Eingang:

Hello!

Ausgabe:

Eine naive Lösung wäre:

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

Dies wäre effizienter:

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

Umgebung:

  • Der Editor verwendet eine monospaced Schriftart
  • Text wird mit 80 Zeichen umbrochen
  • Pfeil nach oben und Pfeil nach unten bewahren die Spalte, auch wenn dazwischen kürzere Linien stehen
  • Es wird angenommen, dass die Zwischenablage leer ist
  • Es wird davon ausgegangen, dass die Num-Taste aktiviert ist
  • Es wird davon ausgegangen, dass die Feststelltaste deaktiviert ist
  • Feststelltaste funktioniert nur für die Buchstaben (dh keine Umschalttaste)

Hotkeys / Shortcuts :

  • Home: Zum Anfang der aktuellen Zeile springen
  • End: Zum Ende der aktuellen Zeile springen
  • Ctrl+ A: Alles markieren
  • Ctrl+ C: Kopieren
  • Ctrl+ X: Schneiden
  • Ctrl+ V: Einfügen
  • Shift+ Cursor bewegt sich: Markierung
  • Ctrl+ F: Öffnet einen Suchdialog.
    • Dumme Textübereinstimmung, keine regulären Ausdrücke
    • Groß- und Kleinschreibung beachten
    • Suche läuft rund
    • Einzeilige Texteingabe für die Suche
    • Die Eingabe wird mit der aktuellen Auswahl vorbelegt. Sofern sich keine neue Zeile dazwischen befindet, wird die gesamte Eingabe ausgewählt
    • Kopieren / Einfügen funktioniert wie gewohnt
    • Durch Drücken von wird Enterdie Suche ausgeführt und die erste Übereinstimmung nach der aktuellen Cursorposition ausgewählt
  • F3: Wiederholen Sie die letzte Suche
  • Ctrl+ H: Öffnet einen Ersetzungsdialog
    • Dumme Textübereinstimmung, keine regulären Ausdrücke
    • Groß- und Kleinschreibung beachten
    • Ersetzen Sie alle durch Umwickeln
    • Einzeilige Texteingaben
    • Die Sucheingabe wird mit der aktuellen Auswahl vorbelegt. Sofern sich keine neue Zeile dazwischen befindet, wird die vollständige Eingabe ausgewählt
    • Die Ersatzeingabe ist leer
    • Kopieren / Einfügen funktioniert wie gewohnt
    • Tab springt zum Ersatzeingang
    • Durch Drücken von wird Enterdas Ersetzen aller ausgeführt. Der Cursor steht nach der letzten Ersetzung

Regeln :

  • Lösungen müssen ein vollständiges Programm sein, das ohne weitere Modifikationen kompiliert / analysiert und ausgeführt wird
  • Die oben angezeigte Tastatur ist die zu verwendende Tastatur
    • Es ist nicht erforderlich, Zeichen zu verarbeiten, die damit nicht eingegeben werden können
  • Jeder Schlüssel muss am Ende freigegeben werden
  • Der Cursor muss sich nicht am Ende der Datei befinden

Wertung :

Ihre Punktzahl ist die Summe der Aktionen, die zum Eingeben der folgenden Texte erforderlich sind. Der Gewinner ist die Lösung mit der niedrigsten Punktzahl. Mit meiner naiven Lösung bekomme ich 1371 + 833 + 2006 = 4210. Mach dich vom Acker! Ich werde in zwei Wochen einen Gewinner auswählen.

1 Meine naive Lösung

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 Einfache Wiederholung

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

3 Komplexere Wiederholung

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

Sie können das von mir geschriebene Wiedergabeprogramm verwenden , um Ihre Lösungen zu testen (Hinweis: Suchen / Ersetzen wird noch nicht unterstützt, alles andere sollte funktionieren).

code-challenge optimization keyboard TimWolla
quelle
6
Ich würde gerne ein solches Programm für vim sehen.
Braden Best
4
Normalerweise benutze ich die Maus für einen Teil dieser Dinge.
Victor Stafusa
1
Sehr interessant. Ich werde es morgen früh
versuchen
2
Du hättest uns nicht wirklich ricken müssen, oder? :)
Filip Haglund
1
Ich bin irgendwie mit @ B1KMusic. Für mich wäre es interessanter, Lösungen für Vimgolf zu generieren. (Dies ist das Äquivalent zu dem, was Sie hier nur mit vim-Befehlen versuchen.) Dies klingt zwar nach einer lustigen Idee, aber das Reduzieren von Tastenanschlägen ist sehr schwierig (oder zumindest denke ich), da eine präzise Bewegung für die Auswahl schwierig ist. Dies macht das Kopieren und Einfügen zu einer sehr schwierigen Aufgabe und erfordert fast so viele Tastenanschläge wie das, was Sie gerade zu kopieren versuchten. (Zumindest lese ich so, wie das Kopieren und Einfügen funktioniert.) Und ich sehe nicht viele andere Möglichkeiten, um Tastenanschläge zu reduzieren.
FDinoff

Antworten:

11

Haskell 1309 + 457 + 1618 = 3384

Zum Schluss eine Antwort (Punktzahl deutlich verbessert, als ich merkte, dass Ihr erster Test Tabs enthält - ich musste die Frage bearbeiten, um sie zu sehen). Kompiliere mit ghc, gib Input auf stdin ein. Beispiel:

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

Ich habe das Offensichtliche wie Dijkstra ausprobiert, aber es war viel zu langsam, selbst nachdem ich die Verzweigung auf die einzigen nützlichen Schritte reduziert hatte: Ausgabe der nächsten Taste oder Kopieren vom Zeilenanfang (Umschalt + Pos1, Strg + C, Ende) oder einfügen.

Bei diesem Ansatz wird also eine Zwischenablage mit fester Länge verwendet, die kopiert wird, wenn ein Zeilenpräfix "nützlich" werden soll, und dieses Präfix wird so lange verwendet, wie es in mehr Zeilen eingefügt werden kann als in den Präfixen der Zeilen, die es als Nächstes erreicht. Wenn es die Zwischenablage nicht verwenden kann, greift es auf die naive Lösung zurück, sodass es sie garantiert übertrifft, sobald die gewählte Länge die Kosten einer Kopie übersteigt.

Die Mindestpunktzahl wird erreicht, wenn die Präfixlänge so gewählt wird, dass sie zu "Never gonna" passt. Es gibt Möglichkeiten, dies zu verbessern, aber ich hatte genug davon, Rick Astley zu lesen.

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
quelle
Sehr schöne Lösung :) Übrigens: Sie können weitere Zeichen abschneiden, indem Sie die Pasten kombinieren (falls möglich).
TimWolla
Das betrifft nur Beispiel 2 wirklich - ich hatte eine Dijkstra-Algorithmus-Version, die das findet, aber nur für die ersten 3 Zeilen verwendbar ist. Sie können meine Lösung für alle Tests verbessern, indem Sie verschiedene Präfixgrößen ausprobieren. Die Lösung ist schnell genug, um dies mit brachialer Gewalt zu erreichen. Es sind nur etwa 10 Läufe erforderlich. Es ist jedoch umständlich, dies in Haskell umzugestalten.
bazzargh