47
\$\begingroup\$

We all know that programmers tend to be lazy. In order to maximize your free time, you decide to write a program that outputs a minimal number of keystrokes for text fed into it.

Input: Text that has to be converted into keystrokes. You may decide on how to input the text (STDIN / reading from a file provided in the arguments)

Output: The necessary actions in the following format:

  • They must be numbered
  • Hit: Pressing a key and immediately releasing it
  • Press: Pressing a key and not releasing it (this will never be optimal when the key is Released as the next keystroke)
  • Release: Releasing a Pressed key

Example:

Input:

Hello!

Output:

A naive solution would be:

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

This would be more efficient:

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

Environment:

  • The editor uses a monospaced font
  • Text is soft wrapped at 80 characters
  • Arrow up and Arrow down preserve the column, even if there are shorter lines in between
  • The clipboard is assumed to be empty
  • Num lock is assumed to be enabled
  • Caps lock is assumed to be disabled
  • Caps lock only works for the letters (i.e. no Shift Lock)

Hotkeys / Shortcuts:

  • Home: Jump to the beginning of the current line
  • End: Jump to the end of the current line
  • Ctrl+A: Mark everything
  • Ctrl+C: Copy
  • Ctrl+X: Cut
  • Ctrl+V: Paste
  • Shift+Cursor moving: Marking
  • Ctrl+F: Opens a search dialog.
    • Stupid text matching, no Regular Expressions
    • Case sensitive
    • Searches wrap around
    • Single line text input for the search
    • The input is prefilled with the current selection, unless there is a newline in between, the complete input is selected
    • Copying / Pasting works as usual
    • Pressing Enter performs the search, selecting the first match after the current cursor position
  • F3: Repeat last search
  • Ctrl+H: Opens a replace dialog
    • Stupid text matching, no Regular Expressions
    • Case sensitive
    • Replace All, with wrap around
    • Single line text inputs
    • The search input is prefilled with the current selection, unless there is a newline in between, the complete input is selected
    • The replace input is empty
    • Copying / Pasting works as usual
    • Tab jumps to the replace input
    • Pressing Enter performs the replace all. The cursor is placed after the last replacement

Rules:

  • Solutions must be a complete program that compiles / parses and executes without any further modification
  • The keyboard displayed above is the keyboard to use
    • It is not required to handle characters that cannot be typed with it
  • Every key must be released at the end
  • The cursor does not need to be at the end of file at the end

Scoring:

Your score is sum the amount of actions needed to type the following texts. The winner is the solution with the lowest score. Using my naive solution I get 1371 + 833 + 2006 = 4210. Beat it! I will pick a winner in two weeks.

1 My naive solution

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 Easy repetition

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

3 More complex repetition

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

You can use the replay program written by me to test your solutions (Note: It does not support Searching / Replacing yet, everything else should work).

Improve this question
\$\endgroup\$
29
  • 6
    \$\begingroup\$ I would love to see a program like this for vim. \$\endgroup\$ Commented Mar 6, 2014 at 4:01
  • 4
    \$\begingroup\$ Normally I use the mouse for part of those things. \$\endgroup\$ Commented Mar 6, 2014 at 6:42
  • 1
    \$\begingroup\$ Very interesting. I'll have a go in the morning ;3 \$\endgroup\$ Commented Mar 10, 2014 at 22:01
  • 2
    \$\begingroup\$ You didn't really have to Rick Roll us, did you? :) \$\endgroup\$ Commented Mar 11, 2014 at 12:04
  • 1
    \$\begingroup\$ I'm kinda with @B1KMusic. To me this would be more interesting to generate solutions to vimgolf. (Which is the equivalent of what you are trying to do here just using vim commands.) This however while sounds like a fun idea reducing keystrokes is very hard (or at least I think it is) as precise movement for selection is difficult. This makes copying and pasting is a really hard task and takes almost as many keystrokes as the thing you were trying to copy. (Or at least this is how I'm reading how copy and paste works). And I don't see many other ways to reduce key strokes. \$\endgroup\$ Commented Mar 13, 2014 at 20:35

1 Answer 1

Reset to default
13
+25
\$\begingroup\$

Haskell 1309 + 457 + 1618=3384

Finally, an answer (score greatly improved once I realised there's tabs in your first test-had to edit question to see those). Compile with ghc, supply input on stdin. Example:

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

I tried the obvious stuff like Dijkstra but it was way too slow, even after reducing the branching to the only useful moves, which are: output the next key, or copy from the start of the line (Shift+Home, Ctrl+C, End), or paste.

So, this approach uses a fixed-length clipboard, copies when a line prefix is about to become 'useful', and keeps using that prefix as long as it would be pasteable on more lines than the prefixes of lines it reaches next. When it can't use the clipboard, it falls back on the naive solution, so it's guaranteed to beat it once the length chosen is more than the cost of a copy.

The minimum score is achieved when the prefix length is chosen to fit "Never gonna ". There are ways to improve on this, but I've had enough of reading 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)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Very nice solution :) Btw: You can shave off some more characters by combining the Pastes (if possible). \$\endgroup\$ Commented Mar 16, 2014 at 19:26
  • \$\begingroup\$ That only really affects example 2 - I had a Dijkstra algorithm version that finds that, but its only usable against the first 3 lines. You can improve my solution for all the tests by trying different prefix sizes; the solution's fast enough that you can do this by brute force, only about 10 runs are required. Awkward to refactor to that in haskell though. \$\endgroup\$ Commented Mar 16, 2014 at 20:26

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.