Maximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V

Description of the problem

I saw the following problem on Stack Overflow:

Write a program to print the sequence of keystrokes such that it generates the maximum number of character ’A’s. You are allowed to use only 4 keys: A, Ctrl+A, Ctrl+C and Ctrl+V. Only N keystrokes are allowed. All Ctrl+ characters are considered as one keystroke.

Instead of giving the sequence, I will count the maximum number of characters. This has a very good recursive solution I’d like to share.

A recursive solution

Let us use \(f(n)\) to denote the function that returns the number we are looking for. Convince yourself that \(f(n)=n\) for \(n<7\). For the rest: if we end the keystrokes with Ctrl-A, Ctrl+C and Ctrl+V then we get twice the number of \(f(n−3)\). If we were to end our keystrokes with Ctrl-A, Ctrl+C and twice Ctrl+V, we get 3 times \(f(n--4)\). Thus

\[ f(n)= \max \{i⋅f(n−1−i)\| i=1,\ldots,n−2\} \]

for every \(n≥8\).

Implementation

Recursive implementations are usually horrible in terms of time complexity unless one uses memoization or dynamic programming. Today, I will use memoization:

(let ((table (make-hash-table))) 
   (defun fn (n)
      (if (< n 7)
         n
         (or (gethash n table)
             (setf (gethash n table)
                   (loop for i from 1 below (1- n) maximize
                      (* (- n i 1) (fn i))))))))
FN

and we test

Evaluation took:
  0.227 seconds of real time
  0.228015 seconds of total run time (0.212014 user, 0.016001 system)
  100.44% CPU
  795,069,661 processor cycles
  89,447,632 bytes consed

(time (fn 2000))
8439205766613565565632312422631591899511334751681071265501513793013859629112940590519312629228060899221520668094813944939328014593494821429834872503731206777089183811572424675554833455607139625047596348546981480633077352984931146321629282304