5

Suppose you're editing a plain txt file and need to input a line of $n$ asterisk characters. You could press the * key $n$ times (assuming you have a numpad with a dedicated * key) but there is certainly a faster way by using the select-all/copy/paste keyboard shortcuts. For example if $n = 80$ you can type the asterisks with these eighteen keystrokes:

*****Ctrlacvvvvacvvvv

For a particular $n$ is there is a way to determine the minimum number of keystrokes necessary?

Mike Pierce
  • 18,938
  • 1
    Here's a related question, the opposite question in a sense, that deserves more attention. – Mike Pierce Jul 28 '21 at 23:45
  • 3
    There certainly is a way to determine the minimum number of keystrokes, namely by searching through all sequences of length at most $n$ but it clearly isn't computationally feasible except for very small $n$. Clearly you can do pretty well by mimicking the steps in the recursive calculation of $\log_2 n$ (integer logarithm). Whether that is optimal in all cases, I don't know. – Rob Arthan Jul 28 '21 at 23:58
  • 1
    You might need the delete key as well – Empy2 Jul 29 '21 at 00:42
  • @Empy2 Good point. I wonder how much tougher of a question this is allowing for the delete/backspace key vs not? – Mike Pierce Jul 29 '21 at 00:49
  • 2 key press (not key stroke) - fireup notepad, press Shift and * w/o releasing them... – achille hui Jul 29 '21 at 04:11
  • Using base 5 you need about $10\log_5n$ keystrokes.
    Eight keystrokes to quintuple, and up to two deletes or asterisk per digit.     – Empy2 Jul 29 '21 at 17:45
  • Hint: Think exponents. $$ gives you one $$ ans $ctrl, a, c, v$ well double what you've got. So in $1 + 4k$ keystrokes you can get $2^k$ $$. If $n \ne 2^k$ we can: find $2$ so that $2^{k} < n < 2^{k+1}$; figure $m=\min(n-2^k,2^{k+1}-n +4)$. The either add or subtract asterisks but press $$ or $del$ $m$ times. – fleablood Jul 29 '21 at 22:35
  • @fleablood Based on the answer below, that won't get you the minimum most of the time. – Mike Pierce Jul 29 '21 at 23:33

1 Answers1

3

Here's an $O(n^{1.5})$ time solution assuming you are only allowed to use *, ctrl, a,c,v, and that further you're only allowed to use them to

  1. print *
  2. copy what you have already and paste it k times.

(not sure if there are other clever key combinations with these keys.)

Algorithm:

Assume inductively that you know an optimal way to produce, $0, 1, ..., n-1$ *'s. Call these strings of keystrokes $b_0, \ldots, b_{n-1}$.

Now, we just try each possibility.

First we consider just taking the solution $b_{n-1}$ and typing another *. This takes $l(b_{n-1}) + 1$ keystrokes, where $l(b_{i})$ means the number of keystrokes in solution $b_i$.

Then, for each divisor $d>1$ of $n$, we consider trying: $b_n$ + Ctrlacv...v with $n/d$ v's. This takes $l(b_n) + 3 + n/d$ keystrokes. This is assuming that we needed to use Ctrl; if there was a Ctrl already active, we only need $l(b_n) + 2 + n/d$ keystrokes. (We need to release the Ctrl to write *, at least on my keyboard...).

Then, we take the optimal of all these possibilities. We can use trial division for this, and so at most $\sqrt{n}$ steps are taken. Implementing this in Python I get $l(b_{80}) = 18$ as you do.

As the comments mention, if you are allowed to delete, we can optimize further, but this would force considering $b_k$ for $k > n$ which wouldn't be allowed under our inductive assumption, and so this recursive algorithm would not seem to be easily adapted.

edit:

The most efficient strings I found for $n \leq 20$ are

0 
1 *
2 * *
3 * * *
4 * * * *
5 * * * * *
6 * * * * * *
7 * * * * * * *
8 * * * * * * * *
9 * * * ctrl a c v v v
10 * * ctrl a c v v v v v
11 * * ctrl a c v v v v v *
12 * * * ctrl a c v v v v
13 * * * ctrl a c v v v v *
14 * * ctrl a c v v v v v v v
15 * * * ctrl a c v v v v v
16 * * * * ctrl a c v v v v
17 * * * * ctrl a c v v v v *
18 * * * ctrl a c v v v v v v
19 * * * ctrl a c v v v v v v *
20 * * * * ctrl a c v v v v v

and the values of $l(b_n)$ for $0 \leq n \leq 100$ are

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 11, 12, 11, 11, 12, 12, 13, 12, 13, 14, 15, 13, 13, 14, 14, 14, 15, 14, 15, 15, 16, 17, 15, 15, 16, 17, 17, 16, 17, 16, 17, 18, 16, 17, 18, 16, 17, 17, 18, 18, 19, 17, 18, 18, 19, 20, 21, 17, 18, 19, 18, 17, 18, 19, 20, 19, 20, 19, 20, 18, 19, 20, 18, 19, 20, 20, 21, 18, 19, 20, 21, 19, 20, 21, 21, 21, 22, 19, 20, 21, 21, 22, 21, 19, 20, 21, 22, 19

As we might expect, it exhibits logarithmic growth:enter image description here

Jair Taylor
  • 16,852
  • I included 'delete' by comparing Best(n) with Best(n+1), and redoing the whole calculation over and over, up to n=15000, until it stabilized, which was about five iterations. I got an average improvement of 0.726 keystrokes. The first improvement was for 23, while 5039 got an improvement of 7 keystrokes. – Empy2 Jul 30 '21 at 11:32
  • 1
    @Empy2 Cool. I had something in mind like that too, but didn't get around to implementing it. – Jair Taylor Jul 30 '21 at 15:54