8
$\begingroup$

I am wanting to type out 1000 characters onto a message, I start off with one character and I have that character in my clipboard. I then paste it to get two characters.

From here I can either select all, copy, navigate to the end of message and paste it, or I can paste the single one I have. the former option requires 4 steps to increase it to 4 with 2 characters in my clipboard, but the latter requires 1 step to increase it to 3 with 1 character in my clipboard. I could then make this choice at each iteration. Either double the amount of characters in the clipboard and add it to the end in 4 steps or keep the amount the same and add it onto the end.

What is the least amount of time I could take to get $1000$ or more characters assuming that each step takes 1 second. i.e. doubling the increase and pasting takes 4 seconds or simply pasting the existing increase takes 1 second.

my second question expands off of this, how would I work out how many steps it takes to get over $n$ characters assuming $n$ is any real integer.

would I be right in assuming it would be wise to double the increase every chance except the last iteration which would be 2 single pastes without doubling?

$\endgroup$
  • $\begingroup$ when you copy, don't you put the whole message on the clipboard? So if you pasted twice, giving three characters, then copy, you get three characters on the clipboard, not two (you say you double the string on the clipboard)? $\endgroup$ – Ross Millikan Sep 4 '13 at 3:28
  • $\begingroup$ yes, you do. so you can either paste twice and double to get three in the clipboard, or you can paste, then double then paste and have two in the clipboard, this is why its so interesting. $\endgroup$ – VikeStep Sep 4 '13 at 3:33
3
$\begingroup$

Let's define our two possible moves as follows:

  • A paste (P) adds the number of characters in the clipboard to the message, taking 1 step.
  • A copy (C) sets the number of characters in the clipboard to equal the number of characters in the message, taking 3 steps (select-all, copy, select-end). (Side note: you can do the same thing with select-all, copy, paste - you'll paste over your selected text, replacing it with itself. Side note 2: I'm using a different definition of "copy" than others: I'm not including the paste in the copy.)

The question is, if you start with 1 character in the message and 1 character in the clipboard, how many steps (minimum) will it take to get at least 1000 characters in the message?

The sequence of moves (Ps and Cs) we use is optimally going to look something like this:

PPPCPPCPCPPPCP

(It's useless to start or end with a C, and putting two Cs next to each other is equally useless). So, optimally, we will do $a_1$ Ps, followed by a C, followed by $a_2$ Ps, followed by a C, etc., ending with a C and $a_m$ Ps, where each $a_i \ge 1$. The number of steps used in this way is $$ a_1 + a_2 + \cdots + a_m + 3(m-1). \tag{1} $$

Now, let $K_n$ be the position with $n$ characters in the message and $n$ characters in the clipboard. From $K_n$, if we use $a$ Ps in a row followed by a C, we end up at position $K_{n(a+1)}$. We may assume we get a free copy move at the very end (it won't improve the number of characters in the message), so that our final position is $K_A$, where $A$ is given by $$ (a_1 + 1)(a_2 + 1)\cdots(a_m + 1) \tag{2} $$

We want to maximize (2), while at the same time minimizing (1). More concretely, if we can change the $a_i$s to both decrease (1) and increase (2), this is definitely good. Using this idea, we observe:

  • An even $a \ge 8$ should be replaced by $1$ and $\frac{a}{2}$. In (2), we improve since $(a + 1) \le (1 + 1)(\frac{a}{2} + 1)$. In (1) we improve since $a \ge 1 + \frac{a}{2} + 3$. (The $+ 3$ comes from $m$ increasing by $1$.)
  • An odd $a \ge 7$ should be replaced by $1$ and $\frac{a-1}{2}$. We have $(a + 1) \le (1 + 1)(\frac{a-1}{2} + 1)$ and $a \ge 1 + \frac{a-1}{2} + 3$.
  • If $a$ and $a'$, with $a < a'$ are at least two apart, we should replace them with $a + 1$ and $a' - 1$. We have $(a + 1)(a' + 1) \le (a + 2)(a')$ and $a + a' \ge (a + 1) + (a' - 1)$.

The above three simplifications, when applied as many times as we need, give us a final set of $a_1,a_2,\dots,a_m$ which all belong to $\{1,2,3,4,5,6\}$ and contain no two $a_i$s two or more apart. In other words, it is optimal to use either $1$s and $2$s only, $2$s and $3s$ only, $3$s and $4$s only, $4$s and $5$s only, or $5$s and $6$s only. But we can go further. One can verify that, in the (multi)set $a_1,a_2,\dots,a_m$:

  • $1,1$ can be replaced by $3$
  • $1,2$ can be replaced by $5$
  • $5,5$ can be replaced by $2,2,3$
  • $6,6$ can be replaced by $3,3,3$

Thus, optimally, we use at most one $5$, at most one $6$ and at most one $1$. Also, since we can't use both $1$s and $2$s, $1$s are pretty much useless (the only time $a_i = 1$ is okay is if there is only one $a_i$ total). This throws out the case where we use only $1$s and $2$s. Finally, using only $5$s and $6$s we can get at most $(5 + 1)(6 + 1) = 42$, which is much less than $1000$, so we'll throw out this case as well. We're left with just three cases: we use $2$s and $3$s, we use $3$s and $4$s, or we use $4$s and at most one $5$.

At this point, let's assume we use only $b$s and $b+1$s, where $b \in \{2,3,4\}$. Let $a_i = b$ for $j$ values of $i$, and let $a_i = b + 1$ for $k$ values of $i$. Then from (1), we need to minimize $$ (b)j + (b + 1)k + 3(j + k - 1) = (b + 3)j + (b + 4)k - 3 \tag{3} $$ Given that (2) is at least $1000$, i.e. $$ (b + 1)^j (b + 2)^k \ge 1000. \tag{4} $$

We separate into cases on $b$ to complete the work.

Case 1: $b = 2$

Here (4) becomes $3^j 4^k \ge 1000$. Given a fixed $k$, we want to pick the smallest $j$ for which this holds true. Also, picking $k > 5$ is pointless since $4^5 > 1000$ already.

\begin{array}{|c|c|c|} \hline k & \text{Smallest } j & 3^j 4^k & \text{Steps used (3): } 5j + 6k - 3 \\ \hline 0 & 7 & 2187 & 32 \\ \hline 1 & 6 & 2916 & 33 \\ \hline 2 & 4 & 1296 & 29 \\ \hline 3 & 3 & 1728 & 30 \\ \hline 4 & 2 & 2304 & 31 \\ \hline 5 & 0 & 1024 & 27 \\ \hline \end{array}

Case 2: $b = 3$

(4) becomes $4^j 5^k \ge 1000$. Given a fixed $k$, we want to pick the smallest $j$ for which this holds true. Picking $k > 5$ is pointless since $5^5 > 1000$ already. We assume $k > 0$ since $k = 0$ is encompassed in Case 1.

\begin{array}{|c|c|c|} \hline k & \text{Smallest } j & 4^j 5^k & \text{Steps used (3): } 6j + 7k - 3 \\ \hline 1 & 4 & 1280 & 28 \\ \hline 2 & 3 & 1600 & 29 \\ \hline 3 & 2 & 2000 & 30 \\ \hline 4 & 1 & 2500 & 31 \\ \hline 5 & 0 & 3125 & 32 \\ \hline \end{array}

Case 3: $b = 4$

(4) becomes $5^j 6^k \ge 1000$. We observed before that $k \ge 2$ is suboptimal. Also, $k = 0$ was encompassed in Case 2. Thus our table is very simple:

\begin{array}{|c|c|c|} \hline k & \text{Smallest } j & 5^j 6^k & \text{Steps used (3): } 7j + 8k - 3 \\ \hline 1 & 4 & 3750 & 33 \\ \hline \end{array}

$$ * \quad * \quad * $$

Having gone through all the cases, we can see that indeed 27 steps is the best we can do. Our strategy is PPPCPPPCPPPCPPPCPPP, and we end up with 1024 characters.

Final Comments: The final computation was a little gross, but considerably easier than expected (and doable by hand!). This method - reducing to the cases $b = 2$, $b = 3$, and $b = 4$, and then checking each one - should be easy to program on a computer for a general $N$ desired number of characters (we did $N = 1000$ here). There will be about $\log_4 N$ rows in the first table, $\log_5 N$ rows in the second table, and $1$ row in the third table; hence the algorithm will take total time $\log_4 N + \log_5 N + 1$, or simply $O(\log N)$, which is pretty much as efficient as we could ask for.

$\endgroup$
  • $\begingroup$ This is brilliant! just what i was looking for $\endgroup$ – VikeStep Sep 4 '13 at 4:30
  • $\begingroup$ There is a dynamic programming approach where you keep track of the set $S(n)$ of maximal $(M,C)$ pairs attainable in $n$ moves. You need only $S(n-1)$ and $S(n-3)$ to compute $S(n)$. Keeping $4$ consecutive sets in memory is enough, and if the first answer is correct, the sets will quickly become limited to a very small size, like $2$ or $3$, and periodicity will set in. $\endgroup$ – zyx Sep 4 '13 at 4:55
  • $\begingroup$ @VikeStep Glad I can help. I've updated the answer to be complete (and a good deal longer). It now proves that 27 is the shortest number of steps. $\endgroup$ – 6005 Sep 4 '13 at 22:20
4
$\begingroup$

Two more pastes get you to $4$ characters, which is two steps faster than copy. Now to get to 8 is a toss-up; four steps either way. If you do the copy, you then have four on the clipboard, so two more pastes will get to $16$. I think the long run most efficient is copy then two pastes, which gets a factor of $4$ with six steps instead of $8$. My best is then $$\begin {array} {l r r} \text{Action} & \text{message} & \text {clipboard}\\3 \text{ pastes} & 4&1\\\text{copy}&8&4\\2\text{ pastes} &16&8\\\text{copy}&32&16\\2\text{ pastes}&64&16\\\text{copy}&128&64\\2\text{ pastes}&256&64\\\text{copy}&512&256\\2\text{ pastes}&1024&256\end{array}$$ for a total of $27$ actions, meaning $27$ seconds

Added: for long term operations, we can think of three choices, one paste then copy, two pastes then copy, or three pastes then copy. As a figure of merit, I suggest the log of the expansion factor divided by the number of actions. We get $$\begin {array} \\ \text{pattern}&\text{expansion}&\text{actions}&\text{log(expansion)/actions}\\\text{paste+copy}&3&5&.2197\\ \text{2 paste+copy}&4&6&.2310\\ \text{3 paste+copy}&5&7&.2299\end{array}$$ so 2 pastes seems to win.

$\endgroup$
  • $\begingroup$ should the second row be "copy .. 8 .. 4" instead of "copy .. 8 .. 8"? $\endgroup$ – 6005 Sep 4 '13 at 3:45
  • $\begingroup$ Was this solved through trial and error or is their reasoning behind it? $\endgroup$ – VikeStep Sep 4 '13 at 3:46
  • $\begingroup$ I gave how I thought about it. Whether to call that trial and error or reasoning is not clear to me. It bothered me to take four steps to get from 2 to 4, so I tried the only other thing available, and saw it was better. Then to get to 8, it seemed having more on the clipboard had to be better. $\endgroup$ – Ross Millikan Sep 4 '13 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.