Typing Puzzle (Updated Thurs July 21)

Note: This is reposted due to my update with a hint and solution, and due to the (relatively) low quality of my post about politicians and animals.

John Derbyshire has posted is a puzzle that I’ve never come across before, which I think ranks in my top 20 all time favorites:

For this month’s puzzle you will need to be in Microsoft Word or some other app — Notepad, for example — that uses standard editing keys.

I shall use the word “keystroke” to mean one of the following:

● a (i.e. you just hit the letter “a” on your keyboard)

● Ctrl-a (which does “select all” on whatever text is in your document)

● Ctrl-c (copy selected text to clipboard)

● Ctrl-v (paste selected text from clipboard to cursor location in document)

Starting from a blank document you execute N keystrokes (as defined). What is the maximum number of a’s you could end up with?

Note (added July 18): Assume that you can “deselect” text without using up any keystrokes. Thanks to commenter A for raising this issue.

I believe I have the answer, but it is not totally satisfying for 2 reasons: 1) I haven’t actually proven it and 2) Another reason which I won’t describe since it might serve as a hint (and it is not as important a reason as 1 anyway).

Feel free to post a solution in the comments if you’d like.

Update Thurs 6pm (SPOILER – DON’T READ IF YOU DON’T WANT A HINT):

First, a hint: If you type a sequence consisting of x1 “a”s, followed by a select and copy, then x2 “v”s, then a select and copy, then x3 “v”‘s, and so on, how many “a”‘s will be on the page?

———————————————————————————————————

Now, here is my answer (this method actually is not directly related to the hint at all, although you can solve the problem using an alternative method that is based on the hint). Let me know by in comments or by email if you think I’m wrong.

Update July 20: The closed form answer, for N = 11 or more, is f(N) = 4^(floor(N/5)+1)*(3/4)^(N-Nmod5)

where floor(x) gives the highest integer less than or equal to x, and where Nmod5 is N modulus 5.

This answer can be seen to be correct if you run the code I’ve posted below (typing2.txt) and look at the pattern.

An alternative way to the answer is to use the hint i’ve posted above, see that the # of a’s is equal to G = x1*(x2+1)*…*(xk+1) and also see that the # of strokes you’ve used is N = x1+x2+…+xk+2*(k-1)

Then, maximize G subject to N, and you’ll get the answer I believe. I did not actually do this though.

(explanation of recursive method, pre-July 20 update): My answer is expressed as a recursive relation as follows, where f(x) represents the # of letters you can type with N keystrokes:

f(N) = N if N < 7

otherwise:

f(N) = max{f(a)*f(b)}[where the max is taken over all combinations of positive integers a and b that satisfy the relation a+b = N-1]

The logic is that for any # of keystrokes N, you will generate b* groups of a* keystrokes, where b* and a* are integers. This is done by:

1) Generating a* keystrokes

2) Typing control-a, then control-c

3) Generating b* – 1 more groups of a* keystrokes (so there will be b* total, including the one from step 1)

Assume it takes a keystrokes to accomplish step 1, and b-1 keystrokes to accomplish step 3. Then a total of a+b+1 keystrokes are used. So to get f(N), we take the max over all combinations of a and b where a+b=N-1.

Enclosed is some Python code that generates the results using this method (all macs have Python):
typing.txt

Update (July 18): Here’s some more efficient (although less cool) code that generates the results, including representations of the actual sequences of keystrokes. 1st column is # of keystrokes, 2nd is # of a’s you can get, and 3rd is representation of keystroke sequence – the representations are sequences of numbers, each of which represents the # of pastes you should use prior to the next select/copy sequence (or, in the case of the very beginning, the # of “a” keystrokes prior to the first select/copy sequence)
typing2.txt

Update (July 21): Here’s the code if we assume that you are not allowed to deselect text for free, i.e. if, every time you paste, you have to paste over what you’ve currently got. Representation (3rd column) uses same convention as described above.
typing3.txt