45
\$\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).

\$\endgroup\$
29
  • 6
    \$\begingroup\$ I would love to see a program like this for vim. \$\endgroup\$ Mar 6, 2014 at 4:01
  • 4
    \$\begingroup\$ Normally I use the mouse for part of those things. \$\endgroup\$ Mar 6, 2014 at 6:42
  • 1
    \$\begingroup\$ Very interesting. I'll have a go in the morning ;3 \$\endgroup\$
    – cjfaure
    Mar 10, 2014 at 22:01
  • 2
    \$\begingroup\$ You didn't really have to Rick Roll us, did you? :) \$\endgroup\$ 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\$
    – FDinoff
    Mar 13, 2014 at 20:35

1 Answer 1

12
+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)
\$\endgroup\$
2
  • \$\begingroup\$ Very nice solution :) Btw: You can shave off some more characters by combining the Pastes (if possible). \$\endgroup\$
    – TimWolla
    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\$
    – bazzargh
    Mar 16, 2014 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.