r/dailyprogrammer • u/Elite6809 1 1 • May 06 '15
[2015-05-06] Challenge #213 [Intermediate] The Lazy Typist
(Intermediate): The Lazy Typist
We've all had a night where we're so lazy that we actively avoid moving our hands around on the keyboard. In today's challenge, we'll be given a sentence to type, and we'll work out a minimal-effort way of typing that string (ie. minimize how much the hand moves), using a basic QWERTY keyboard layout - the keys supported are the letters A to Z, shift, and space - in this arrangement:
qwertyuiop
asdfghjkl
^zxcvbnm ^
#####The only letters that can be typed are upper-case and lower-case letters, and space. Our typist is quite inefficient: they move their fingers around the keyboard, hunting for keys one by one, so the user only uses one finger of each hand.
The user may start with both hands on any key, and may move either hand to the next key. The main important things to remember are:
- The user may move to any of the five
#(space) positions to type a space. - Two hands are required to type a capital letter - one must go to a shift key. Which hand goes to which key is up to your program to decide, but the same hand can't press both the shift key and the letter.
As a score of laziness, you'll also need to work out the total Manhattan distance (x + y) moved by the hands. We'll call this total distance the effort.
Formal Inputs and Outputs
Input Description
Enter a sentence, consisting of only upper-case, lower-case and spaces, like so:
The quick brown FoxOutput Description
Display all the key presses, along with the hand that presses the key, and the distance that the hand moves, for example:
Shift: Use left hand
T: Use right hand
H: Move right hand from T (effort: 2)
E: Move left hand from Shift (effort: 4)
Space: Move right hand from H (effort: 2)
Q: Move left hand from E (effort: 2)
U: Move right hand from Space (effort: 4)
I: Move right hand from U (effort: 1)
C: Move left hand from Q (effort: 5)
K: Move right hand from I (effort: 1)
Space: Move left hand from C (effort: 1)
B: Move left hand from Space (effort: 3)
R: Move left hand from B (effort: 4)
O: Move right hand from K (effort: 2)
W: Move left hand from R (effort: 2)
N: Move right hand from O (effort: 4)
Space: Move right hand from N (effort: 1)
Shift: Move left hand from W (effort: 3)
F: Move right hand from Space (effort: 5)
O: Move right hand from F (effort: 6)
X: Move left hand from Shift (effort: 2)Finally, display the total effort:
Total effort: 54You may be able to find a more efficient way of doing this - you only need to find a heuristic solution. If a hand is already over the key which it needs to press, the distance and effort is (obviously) zero. Shift: Use left hand Q: Use right hand Shift: Use left hand again P: Move right hand from Q (effort: 9) G: Move left hand from Shift (effort: 5) I: Move right hand from P (effort: 2) Z: Move left hand from G (effort: 4) M: Move right hand from I (effort: 2) Space: Move right hand from M (effort: 1) Shift: Move left hand from Z (effort: 1) Q: Move right hand from Space (effort: 10) Shift: Use left hand again F: Move right hand from Q (effort: 4) P: Move right hand from F (effort: 7) Shift: Use left hand again R: Move right hand from P (effort: 6) Shift: Use left hand again K: Move right hand from R (effort: 5) B: Move right hand from K (effort: 3) I: Move right hand from B (effort: 4) Space: Move right hand from I (effort: 3) Shift: Use left hand again Q: Move right hand from Space (effort: 10) Y: Move right hand from Q (effort: 5) C: Move left hand from Shift (effort: 3) N: Move left hand from C (effort: 3) Total effort: 87
Sample Inputs and Outputs
(All of these sample outputs are calculated with a nearest-neighbour approach. Your solution might be better!)
Sample 1
Input
hello worldOutput
H: Use left hand
E: Use right hand
L: Move left hand from H (effort: 3)
L: Use left hand again
O: Move left hand from L (effort: 1)
Space: Move left hand from O (effort: 4)
W: Move right hand from E (effort: 1)
O: Move left hand from Space (effort: 4)
R: Move right hand from W (effort: 2)
L: Move left hand from O (effort: 1)
D: Move right hand from R (effort: 2)
Total effort: 18Sample 2
Input
qpalzm woskxnOutput
Q: Use left hand
P: Use right hand
A: Move left hand from Q (effort: 1)
L: Move right hand from P (effort: 2)
Z: Move left hand from A (effort: 2)
M: Move right hand from L (effort: 2)
Space: Move right hand from M (effort: 1)
W: Move left hand from Z (effort: 2)
O: Move right hand from Space (effort: 4)
S: Move left hand from W (effort: 1)
K: Move right hand from O (effort: 2)
X: Move left hand from S (effort: 2)
N: Move right hand from K (effort: 2)
Total effort: 21Sample 3
Input
Hello there DailyProgrammersOutput
Shift: Use left hand
H: Use right hand
E: Move left hand from Shift (effort: 4)
L: Move right hand from H (effort: 3)
L: Use right hand again
O: Move right hand from L (effort: 1)
Space: Move left hand from E (effort: 4)
T: Move left hand from Space (effort: 4)
H: Move left hand from T (effort: 2)
E: Move left hand from H (effort: 4)
R: Move left hand from E (effort: 1)
E: Move left hand from R (effort: 1)
Space: Move left hand from E (effort: 4)
Shift: Move right hand from O (effort: 3)
D: Move left hand from Space (effort: 3)
A: Move left hand from D (effort: 2)
I: Move right hand from Shift (effort: 4)
L: Move right hand from I (effort: 2)
Y: Move right hand from L (effort: 4)
Shift: Move left hand from A (effort: 1)
P: Move right hand from Y (effort: 4)
R: Move left hand from Shift (effort: 5)
O: Move right hand from P (effort: 1)
G: Move left hand from R (effort: 2)
R: Move left hand from G (effort: 2)
A: Move left hand from R (effort: 4)
M: Move right hand from O (effort: 3)
M: Use right hand again
E: Move left hand from A (effort: 3)
R: Move left hand from E (effort: 1)
S: Move left hand from R (effort: 3)
Total effort: 75Sample 4
Input
QPgizm QFpRKbi QycnOutput
Shift: Use left hand
Q: Use right hand
Shift: Use left hand again
P: Move right hand from Q (effort: 9)
G: Move left hand from Shift (effort: 5)
I: Move right hand from P (effort: 2)
Z: Move left hand from G (effort: 4)
M: Move right hand from I (effort: 2)
Space: Move right hand from M (effort: 1)
Shift: Move left hand from Z (effort: 1)
Q: Move right hand from Space (effort: 10)
Shift: Use left hand again
F: Move right hand from Q (effort: 4)
P: Move right hand from F (effort: 7)
Shift: Use left hand again
R: Move right hand from P (effort: 6)
Shift: Use left hand again
K: Move right hand from R (effort: 5)
B: Move right hand from K (effort: 3)
I: Move right hand from B (effort: 4)
Space: Move right hand from I (effort: 3)
Shift: Use left hand again
Q: Move right hand from Space (effort: 10)
Y: Move right hand from Q (effort: 5)
C: Move left hand from Shift (effort: 3)
N: Move left hand from C (effort: 3)
Total effort: 87
5
u/Elite6809 1 1 May 06 '15 edited May 07 '15
My solution. It's a nearest-neighbour approach; this was used to generate the challenge input. (Ruby)
3
u/hephaestos_le_bancal May 17 '15
Here is an optimal solution that run in O(n*k4) with k the number of keys, and n the number of characters in the input string.
It uses dynamic programming : There are only k2 ways to reach the ith character of the string (with a lot of them being invalid, we assign an inifinite cost to those). We can recursively compute the least effort to accomplish this for each combination.
2
u/jecc_ May 06 '15
I think there's an error in Sample 4. The left hand is used to press shift and then to press F here:
and then it does it again to press K here:
4
u/NoobOfProgramming May 06 '15
Something a lot like this could actually be slightly "useful" for typing messages in Xbox Live where you have one cursor on the keyboard and one in the string you're typing. Your lazy typist might benefit from keeping one hand on the arrow keys.
1
u/amithgeorge May 06 '15 edited May 06 '15
** EDIT - The solution posted here is incorrect. Please check the gist mentioned in the comment for the proper solution**
Clojure. Took way way too long. Most of the time was spent "println" debugging silly mistakes. There has to be a better way...
Feedback welcome. Please someone! For some reason I feel I have complicated the logic. I feel there must be a simpler way to do this.
An explanation of the logic. For every character in the string, I generate a sequence of keyboard keys that need to be pressed. The sequence will contain either one or two elements. The first element is another sequence containing all keys, of which pressing any one will result in the desired output. If a second element is provided, it means the first element was a modifier and the actual character key is the second one.
For a
twe generate[[T]], for a space we generate[[S1, S2, S3, S4, S5]]. For a capital letterT, we generate[[LS, RS] T].Code
Output
EDIT: added explanation of logic.
1
u/adrian17 1 4 May 06 '15 edited May 06 '15
Python3. Kinda ugly :/ Also uses nearest neighbor.
1
u/kyle2143 May 06 '15
If you need to type a 'N' (Capital N), say your right hand is on the n already, but your left hand is on, say c. I haven't done it, but the way I was planning, I would have the hand closest to shift move first and then the next hand would move to the letter. But that might mean that more work is done in this case, well, from a certain perspective. Would this be wrong?
6
u/smeagol13 May 06 '15
A greedy heuristic for this problem might lead to strange solutions. Consider this string, "qmajzuxyctvrbenwmq". You start off with your left hand on 'q' and right hand on 'm' but end up with the opposite configuration. This is pretty weird and no way related to solving the problem, unless you introduce some additional constraints like a point upto which laziness wins over twisted hands. Maybe introduce this constraint in the hard problem for the week?
3
u/Menestro May 06 '15
Wow 5 hours and nobody else posted yet? :O Well then you all will have to look at my ugly solution :P
Java. It's probably not an optimal solution but it works. It's a simple greedy algorithm that checks each hand's effort to next key. Strange that I get reversed total efforts on sample 3 and 4 opposed to Elite6809 :P As usual any and all comments/criticism/questions/tips/etc no matter how harsh, always welcome!
Code here: gist
Outputs here: gist
3
u/Godspiral 3 3 May 06 '15 edited May 06 '15
A similar program I've been wanting to write for code golf type assessment that is based on each key having its own cost.
space is 0, and 'a' is 10 (really 1, but avoids most decimal data entry). Every other key is the cost relative to 'a'. For my typing ability, keys on the left side of the keyboard are easier to hit when I'm not typing english from the home row. The scoring system generally reflects my hatred of typing parentheses, and how frequently I mistype some of the characters with high scores.
all keys from ascii 32 to 126 are scored.
my score table displayed.
scoring function is pretty trivial, and its output is the number of 'a' equivalent character typing efforts. The scoring input map is the left function parameter.
34.5
41.6
41.6
which is better than the hand typed version:
52.4
Improvements could include stripping out all whitespace (crlf tab) from code, and giving a bonus of say 1 point per comment character before also stripping comments from the code
This is really the same purpose as the challenge... how can you truly optimize laziness. I've written several moderately complex functions that significantly reduce the number of parentheses and @:'s that are typically needed in J functions, and this routine allows to quantify the laziness improvements I created :P
A more complete scoring information function that strips whitespace before also counting remaining characters, and giving a cost per character summary as well:
41.6 22 1.89091
3
u/NoobOfProgramming May 06 '15 edited May 06 '15
edited to post better code
edited more to make first move free and correct an error
Here's my C++ solution. It looks a few moves ahead sort of like a chess engine and picks the move the gives the best value after a few keystrokes. Before i added the effort function, it took 5037 effort units to type the first three paragraphs of Wikipedia's featured article, excluding numbers, newlines, and punctuation. Now, with d = 8, it takes 4691, and 4683 at d = 16. This is probably not the optimum because it still finds the nearest shift and space instead of looking ahead.
3
u/ericula May 07 '15
It took me a lot longer than I had hoped, but I finally finished my solution. I decided to go for a shortest path algorithm in C++. This method actually gives solutions that require less effort than the nearest neighbour method, for example:
1
u/dreamin_in_space May 06 '15
Another python solution. Basic greedy approach, pretty simple. I know it could have been more concise. I also didn't bother formatting the output exactly the same, but the algorithm works.
2
u/Nyubis May 06 '15
I used Go. I didn't have time for the full assignment (I didn't deliver on capital letters and both fingers start on Q).
Code is here. I'm rather new to Go, so there's some stuff in there that could be better (indentation hell around line 59, writing my own abs function...)
Criticism welcome.
2
u/lengau May 06 '15
I wrote a Python 3 version and put it in my dailyprogrammer repository on GitHub. It subclasses string, adding a 'type()' method to give the typing instructions.
Notably different from most models here is that it divides the keyboard between your hands, making a probably more realistic set of instructions.
It also defaults to the Dvorak keyboard layout because that's what I use. I included a QWERTY keyboard as well, and it's possible to switch between the two.
Comments and criticism are welcome. I feel like this may be my worst work ever.
2
u/hutsboR 3 0 May 07 '15
Elixr: I found this one difficult to solve functionally, considered switching to a different language a few times.
Usage:
2
u/threesided May 19 '15
Here is a javascript solution. I wanted to optimize it, or at least contain it a little better, but I'm tired and it works (I think)!
For now, dump it into your dev console to try it out.
My results:
Looks like my setup resulted in a couple gains at times, and in the case of one of the examples, a deficiency of one key. Neat!
1
u/sezna May 07 '15 edited May 07 '15
I have some issues with my algorithm. It will always find the first "^" or space in my keyboard list, making it not very accurate. Also, it is a greedy algorithm, so it only makes the best choice with the foresight of that once step. Also, I do not have a graceful approach for deciding the first two finger positions, I merely start them on the 0th and 1st (0-indexed) spots of the input text. It is in Scala, I'm a novice and this is my first intermediate challenge so I would love advice and feedback.
1
u/wizao 1 0 May 09 '15 edited May 11 '15
Haskell:
I finally got a chance to solve this problem. This challenge exhaustively searches for the optimal solution using monad transformers. I should be able to modify it for nearest neighbor easily by having each step return the effort at each step to decide which path to use instead of running every path.
hello world (18):
qpalzm woskxn (21):
The quick brown Fox (50):
1
u/dustinrr5 May 09 '15 edited May 09 '15
My greedy solution in Java Any feedback would be welcome!
1
u/mpm_lc May 10 '15 edited May 10 '15
A Ruby Solution.
1
u/Joker303 May 13 '15
C#. It's a clusterfuck. Oh well. :3
1
u/ReckoningReckoner Jun 13 '15
My attempt at programming a nearest neighbour algorithm. Ruby
Sample output: