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.
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\).
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))))))))
FNand 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