The mathematics of CTRL-C CTRL-V

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

The mathematics of CTRL-C CTRL-V

Postby Siyko » Sat Nov 21, 2009 3:11 am UTC

So let's say I want to type "this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam..."

I want to type the string "this is spam" 20 times.

So I type it once, 13 keystrokes including the space at the end. I hit ctrl+(a, c, (v*20)). Total of 36 keystrokes.

But, I can also do ctrl+(a, c, (v*10), a, c, (v*2)) for a total of 30 keystrokes.

I can also do ctrl+(a, c, (v*5), a, c, (v*4)) for a total of 27

There has to be a mathematical formula to find the best way to do this - time is money!!!

njperrone
Posts: 102
Joined: Wed Sep 23, 2009 9:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby njperrone » Sat Nov 21, 2009 3:22 am UTC

Well, best thing i can think of doing is doing a series of experiments and recording them as coordinate pairs. this will generate some points to which you can do regression analysis for and using calculus you can minimize the keystrokes. You could also just brute force it entirely to find the minimum number of keystrokes. Unfortunately I cannot think of any nice purely mathematical approach, but I do hope some one can for the sake of elegance.

lingomaniac88
Posts: 127
Joined: Wed Apr 09, 2008 2:52 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby lingomaniac88 » Sat Nov 21, 2009 3:24 am UTC

Here are my initial thoughts:

Spoiler:
The 13 keystrokes required for "this is spam " don't really matter, since they must be typed in every keystroke. Then, if you want "this is spam" to appear [imath]N[/imath] times, then you want to find [imath]k[/imath] positive integers [imath]a_1,a_2,\ldots,a_k[/imath] such that [imath]a_1a_2\ldots a_k=N[/imath] while minimizing [imath]3(a_1+a_2+\ldots+a_k)[/imath]. This immediately brings the AM-GM inequality to mind. I believe you'll want to make your [imath]a_i[/imath] as close as possible to each other.
"It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something."
-- Franklin D. Roosevelt

EduardoLeon
Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú
Contact:

Re: The mathematics of CTRL-C CTRL-V

Postby EduardoLeon » Sat Nov 21, 2009 4:12 am UTC

These ideas might be helpful: Exponentiation by squaring.
Gott weiß ich will kein Engel sein!

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby qbg » Sat Nov 21, 2009 5:01 am UTC

Sounds like trying to find the minimal addition chain, a hard problem.

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Sat Nov 21, 2009 5:04 am UTC

Questions:
Am I to assume the paste operation copies over what is selected, and after one paste the cursor goes to the end of the string? I assume yes on both counts.
Is there 'free' selection with the mouse or move to end of selection by hitting right arrow? I assume neither.
Do you have to hit the desired number of copies exactly? Did both, kinda.

In math,
Spoiler:
basically seems you want to minimize [math]\sum (a_i+2)[/math]subject to[math]\prod a_i=N[/math] with i varying.
If you can overshoot it is mostly trivial,
Spoiler:
N copies minimum can be achieved with 4*floor(ln N / ln 2)+2 keystrokes (or something similar), just apply (acv^4) then repeat (acv^2) until you have N or more.
For the exact case, I suspect
Spoiler:
prime factorize N, [math]N=\prod p_i^{n_i}.[/math] Then apply (acv^pi) ni times. Do so for each i in turn, and you should get N copies. There are some special cases to consider, (acv^4) is preferred to (acv^2 acv^2), and (acv^2) is preferred to (acv^2 acv^3), but (acv^9) is not preferred to (acv^3 acv^3), for example. This operation should be commutative and associative, I think, but I'm too lazy atm to prove it.

Edit: Better notation, thanks Qaanol.

EduardoLeon wrote:These ideas might be helpful: Exponentiation by squaring.

qbg wrote:Sounds like trying to find the minimal addition chain, a hard problem.
There doesn't appear to be a method to select less significant groupings of copies. It seems like we are limited to ctrl+a,c, and v, and the implied action of the cursor after ctrl+v, so what you currently have is all you can use. This severely reduces the complexity of the problem and makes it much easier than the minimal addition chain. Atleast that's how I understand it.
Last edited by squareroot1 on Sat Nov 21, 2009 6:55 am UTC, edited 1 time in total.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Qaanol » Sat Nov 21, 2009 5:20 am UTC

27 is minimal here.

Edit: Incorrect statements removed, thanks.
Last edited by Qaanol on Sat Nov 21, 2009 12:24 pm UTC, edited 2 times in total.
wee free kings

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Sat Nov 21, 2009 6:33 am UTC

Qaanol wrote:27 is minimal here. There are 5 different ways to achieve it.

[math]acv^5acv^4 = acv^4acv^5 = acvacvacv^5 = acvacv^5acv = acv^5acvacv[/math]


acv^4 can't equal acvacv, either acvacv=acv^3 or acv^2acv^2 = acv^4

Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: The mathematics of CTRL-C CTRL-V

Postby stephentyrone » Sat Nov 21, 2009 6:50 am UTC

As someone already said, this is an addition chain problem. There is no known algorithm to find the optimal chain that is better than brute force search. That isn't to say that it's impossible for one to exist, but the related decision problem is NP-complete, so if you found a fast algorithm for this, you would have better things to worry about anyway.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: The mathematics of CTRL-C CTRL-V

Postby Token » Sat Nov 21, 2009 8:34 am UTC

squareroot1 wrote:Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

It is both. Immediately after Ctrl-a Ctrl-c, all the text is selected, so all Ctrl-v does is to overwrite the text with the same thing, but deselects it and puts the cursor at the end. Subsequent Ctrl-vs will append a copy of the original text.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: The mathematics of CTRL-C CTRL-V

Postby Token » Sat Nov 21, 2009 11:08 am UTC

OK, this is less hard than people are claiming. Admittedly, finding an optimal chain requires you to be able to factorize, but then so does finding any non-trivial chain.

Let [imath]f(n_1, \ldots, n_k)[/imath] be the number of copies of the original text created by [imath]acv^{n_1} \ldots acv^{n_k}[/imath], and let [imath]g(n_1, \ldots, n_k)[/imath] be the number of keystrokes required. Clearly [imath]g(n_1, \ldots, n_k) = c + \sum_{i=1}^k (n_i + 2)[/imath].

Lemma 1: [imath]f(n_1, \ldots, n_k) = \prod_{i=1}^k n_i[/imath].
Proof: In any sequence of ctrl-vs, the first v will overwrite the original text, and subsequent ones will duplicate it, so f(n) = n. Given [imath](n_1, \ldots, n_k)[/imath], the last [imath]n_k[/imath] ctrl-vs will copy the result of what came before [imath]n_k[/imath] times, so [imath]f(n_1, \ldots, n_k) = n_k f(n_1, \ldots, n_{k-1})[/imath]. So the result follows by induction on k.

The problem given can be rephrased as choosing [imath]k[/imath] and [imath](n_1, \ldots, n_k)[/imath] to minimize [imath]g(n_1, \ldots, n_k)[/imath], subject to [imath]f(n_1, \ldots, n_k) = N[/imath]. Neither f nor g depend on the ordering of the [imath]n_i[/imath], so we merely need to find a factorization of N that minimizes g.

Certainly optimal factorizations exist - let's assume we have one. What can we say about it? Certainly if [imath]n[/imath] appears in it, we shouldn't be able to factorize it into [imath]p[/imath] and [imath]q[/imath] with [imath]p + q + 2 < n[/imath], otherwise our factorization wouldn't be optimal. What numbers cannot be factorized in this way?

Lemma 2: If [imath]n[/imath] appears in an optimal factorization, then [imath]n[/imath] is either prime, 4, 6 or 8.
Proof: Let [imath]n[/imath] be in some optimal factorization, and let [imath]pq = n[/imath]. Without loss of generality let [imath]p \leq q[/imath]. If [imath]p \geq 3[/imath], then [imath]p + q + 2 < 3q \leq n[/imath], so the factorization is not optimal. If [imath]p = 2[/imath], then [imath]p + q + 2 \geq n[/imath] implies [imath]\frac{n}{2}+4 \geq n[/imath] implies [imath]n \leq 8[/imath]. And if [imath]p=1[/imath], then [imath]p+q+2 = n+3 > n[/imath], which is certainly worse.

Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

EDIT: Slight notation correction.
Last edited by Token on Sat Nov 21, 2009 1:06 pm UTC, edited 1 time in total.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Qaanol » Sat Nov 21, 2009 12:45 pm UTC

Token wrote:OK, this is less hard than people are claiming. Admittedly, finding an optimal chain requires you to be able to factorize, but then so does finding any non-trivial chain.

Let [imath]f(n_1, \ldots, n_k)[/imath] be the number of copies of the original text created by [imath]acv^{n_1} \ldots acv^{n_k}[/imath], and let [imath]g(n_1, \ldots, n_k)[/imath] be the number of keystrokes required. Clearly [imath]g(n_1, \ldots, n_k) = c + \sum_{i=1}^k (n_i + 2)[/imath].

Lemma 1: [imath]f(n_1, \ldots, n_k) = \prod_{i=1}^k n_i[/imath].
Proof: In any sequence of ctrl-vs, the first v will overwrite the original text, and subsequent ones will duplicate it, so f(n) = n. Given [imath](n_1, \ldots, n_k)[/imath], the last [imath]n_k[/imath] ctrl-vs will copy the result of what came before [imath]n_k[/imath] times, so [imath]f(n_1, \ldots, n_k) = n_k f(n_1, \ldots, n_{k-1})[/imath]. So the result follows by induction on k.

The problem given can be rephrased as choosing [imath]k[/imath] and [imath](n_1, \ldots, n_k)[/imath] to minimize [imath]g(n_1, \ldots, n_k)[/imath], subject to [imath]f(n_1, \ldots, n_k) = N[/imath]. Neither f nor g depend on the ordering of the [imath]n_i[/imath], so we merely need to find a factorization of N that minimizes g.

Certainly optimal factorizations exist - let's assume we have one. What can we say about it? Certainly if [imath]n[/imath] appears in it, we shouldn't be able to factorize it into [imath]p[/imath] and [imath]q[/imath] with [imath]p + q + 2 < n[/imath], otherwise our factorization wouldn't be optimal. What numbers cannot be factorized in this way?

Lemma 2: If [imath]n[/imath] appears in an optimal factorization, then [imath]n_i[/imath] is either prime, 4, 6 or 8.
Proof: Let [imath]n[/imath] be in some optimal factorization, and let [imath]pq = n[/imath]. Without loss of generality let [imath]p \leq q[/imath]. If [imath]p \geq 3[/imath], then [imath]p + q + 2 < 3q \leq n[/imath], so the factorization is not optimal. If [imath]p = 2[/imath], then [imath]p + q + 2 \geq n[/imath] implies [imath]\frac{n}{2}+4 \geq n[/imath] implies [imath]n \leq 8[/imath]. And if [imath]p=1[/imath], then [imath]p+q+2 = n+3 > n[/imath], which is certainly worse.

Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

Well done.

If you want to maximize the number of copies that will be produced should you have to stop early, then work your way through the list from smallest to largest, and don't combine a 2 and 4 into an 8.
wee free kings

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Sat Nov 21, 2009 2:28 pm UTC

Token wrote:
squareroot1 wrote:Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

It is both. Immediately after Ctrl-a Ctrl-c, all the text is selected, so all Ctrl-v does is to overwrite the text with the same thing, but deselects it and puts the cursor at the end. Subsequent Ctrl-vs will append a copy of the original text.

Good point, I was mainly stressing whether Ctrl-v would do that initial overwrite of the selected text or not. Basically, acv^2 is doubling, not acv which is the identity.

Token wrote:Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

I got the same result after fiddling with the approach I outlined above. I ended up watching Bones and The Bourne Ultimatum instead of posting. I didn't bother proving it with lemmas and all that jazz, but yeah. Spoiled for length.
Spoiler:
I like to think of the copying process as a string of 'a's, 'c's and 'v's coded by the composition of terms (acv^p)^n). EG. (acv^3)^2 results in acvvvacvvv.
Terms can interact: (acv^p)^n(acv^p)^m = (acv^p)^(n+m) (acv^p)^n(acv^q)^n=(acv^(p*q))^n.
The string length is the sum of the length of the terms, the length of a term is (2+p)*n.
A string is unique up to permutations of its terms.
There exists at least one minimal length string for any given N; it may not be unique.

One process to find a minimal length string for a given N is
1. Factor N over the primes.[math]N = \prod{{p_i}^{n_i}}[/math]
2. Create the associated string S0 as the composition (multiplication) of the terms for each prime factor.
[math]S_0 = \prod{(acv^{p_i})^{n_i}}[/math]
3.a This string will have minimal length if pi ≠ 2 for any i or pi=2, ni=1, pj ≠ 3 for some i and any j.
3.b Otherwise, compose as many (acv^2 acv^2) terms into (acv^4) terms as possible; if there is an extra (acv^2) term and a (acv^3) term, compose the two into a (acv^6) term.
The resulting string S1 will have minimal length for N.

I like that 3.a implies that S0 will have minimal length for any odd N or any even N not divisible by 3 or 4.

Edit: Very nice Token, very nice indeed.

Sobuno
Posts: 3
Joined: Sun Dec 14, 2008 10:44 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Sobuno » Sat Nov 21, 2009 4:26 pm UTC

Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Nitrodon » Sat Nov 21, 2009 8:07 pm UTC

The method described in this thread is usually optimal, but not always for large N. For instance, outputting "this is spam " 257 times takes 272 keystrokes by that method, but there's a way to do it in 58 (57 if you don't need a trailing space at the very end).

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Sat Nov 21, 2009 10:12 pm UTC

Nitrodon wrote:The method described in this thread is usually optimal, but not always for large N. For instance, outputting "this is spam " 257 times takes 272 keystrokes by that method, but there's a way to do it in 58 (57 if you don't need a trailing space at the very end).

I assume you mean "this is spam "(acv^4)^4"this is spam"? Oh wait, that's 49 keystrokes (50 with the trailing space.) But it also uses keystrokes other than ctrl+{a,c,v}.

My method is obviously used to create N copies from a given, arbitrary string. I'm fairly sure I don't refer to the length of the initial string, because I'm not interested in an addition chain problem.

Sobuno wrote:Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke

Sigh, so obviously its trivial, turn the repeat rate for the keyboard as high as possible, then do acv* and hold v until you get the desired number of copies. Release at the appropriate millisecond. Don't overshot! If you do, av* and try again.
Last edited by squareroot1 on Sat Nov 21, 2009 11:45 pm UTC, edited 1 time in total.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Qaanol » Sat Nov 21, 2009 10:31 pm UTC

I count 50.

Initial 13 + ctrl + (1 + 1 + 4)*4 + 13 = 13 + 1 + 24 + 12 = 50
wee free kings

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Siyko » Mon Nov 23, 2009 5:11 pm UTC

Thanks a lot for all the replies - my math background is not good enough to know all the references, but I understand the formulas.

The 13 keystrokes required for "this is spam " don't really matter, since they must be typed in every keystroke.


This is true - the only time string length would ever make a difference would be if it were less than 4 keystrokes (typing 'a <space> a <space> ctrl+(acv)' is faster than 'a <space> ctrl+(acv acv)') but that only really matters for the initial steps, and the rules of what changes are pretty simple.

Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke


This is missing the point

To specify some confusion, after selecting all, the next strike of 'v' performs the same function as 'right arrow' or 'end' - it overwrites the selected text with a copy of itself - and clears the 'selected' buffer, moving the cursor to the end of the selection (the end of the document if ctrl-a was used, which it was).

I'm going to try a bit harder to digest Token's reply. I'm glad this subject got the attention it deserved (it's very important!)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The mathematics of CTRL-C CTRL-V

Postby Yakk » Mon Nov 23, 2009 10:37 pm UTC

Let's take 7427466391 copies.

By Token's proof, this takes 7427466391+K (for some small K) steps, as this is a 10 digit prime.

My plan? Generate 7427466390, then manually type in the last copy (or use shift-arrow to highlight, ctrl-c, ctrl-v^2).

7427466390=2*3*5*31*139*57457
which, as you can quite imagine, takes less work to do this number than the original using Token's method.

Odds are pulling off the same trick on 57457, or changing the target number by something other than 1, would do even better.

Of course, this changes the problem from "has a pretty solution" to "oh my god, what have we done" hard, I suspect.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Mon Nov 23, 2009 11:29 pm UTC

Yakk wrote:Of course, this changes the problem from "has a pretty solution" to "oh my god, what have we done" hard, I suspect.

You suspect correctly. The ability to simply type in the next n copies changes the complexity from "Here's a nice solution - with proof!" to "Oh me yarm addition chain! It's NP-complete!" as a few people have already stated.

OT: Is this thread dead yet, Jim?

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: The mathematics of CTRL-C CTRL-V

Postby Token » Tue Nov 24, 2009 12:40 am UTC

People have said it's an addition chain problem, but I don't see how. Maybe I'm just too tired.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby squareroot1 » Tue Nov 24, 2009 1:07 am UTC

Token wrote:People have said it's an addition chain problem, but I don't see how. Maybe I'm just too tired.


Let's see if I can explain this simply.

The difference is, some people consider it
1. Type string.
2. Press some combination of ctrl+a, ctrl+c, ctrl+v.
3. End.
while others consider it
1. Type string.
2. Press some combination of ctrl+a, ctrl+c, ctrl+v.
3. Type the string again?
4. Press some combination of ctrl+a, ctrl+c, ctrl+v?
5. Type the string again?
6. Press some combination of ctrl+a, ctrl+c, ctrl+v?
...
N. End

The latter is an addition chain problem and NP-complete, mainly because of the question marks.

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: The mathematics of CTRL-C CTRL-V

Postby phlip » Tue Nov 24, 2009 2:07 am UTC

That's not quite an addition chain, though... an addition chain is "each new number can be the sum of some two previous numbers; minimise the length of the chain", whereas this new problem is more restrictive: "each new number is either the previous number plus or minus one (weight k), or the previous number times n for some natural n (weight an+b); minimise the total weight of the chain." Specifically, with a = 1, b = 2, k = the length of the initial string. That is, plus one means typing a k-character string... minus one means k backspaces (or possibly fewer ctrl+backspaces?)... multiplying it by n means acvn.

For instance, if you go "acvvacvvacvv" to get 8, you can't then quickly add 2 to get 10, even though you did, at one point, have 2 (indeed, you had 2 in the clipboard at one point). Your options after "acvvacvvacvv" are identical to your options after "acvvvvacvv". As opposed to an addition chain, where you can do (1,2,4,8,10).

I wouldn't be surprised if it's still NP-complete, though.

Note that the relative sizes of a, b and k in that definition are important, too... if I wanted 17 "1"s, then I could do "1111acvvvv1", but if I wanted 17 war-and-peaces, I'd do "<war and peace here>acv17".

[edit]
I did some brute-forcing, results in the spoiler.
Spoiler:
Typing is represented by "+-----" to show the length of the string... backspacing by "<====". Copy/pasting by "acvvv".

For a one-character initial string:

Code: Select all

    0:
    1: +
    2: ++
    3: +++
    4: ++++
    5: +++++
    6: ++++++
    7: +++++++
    8: ++++acvv
    9: +++acvvv
   10: +++++acvv
   11: +++++acvv+
   12: ++++acvvv
   13: ++++acvvv+
   14: +++++++acvv
   15: +++++acvvv
   16: ++++acvvvv
   17: ++++acvvvv+
   18: ++++++acvvv
   19: ++++++acvvv+
   20: +++++acvvvv
   21: +++++++acvvv
   22: +++++++acvvv+
   23: ++++++acvvvv<
   24: ++++++acvvvv
   25: +++++acvvvvv
   26: +++++acvvvvv+
   27: +++acvvvacvvv
   28: +++++++acvvvv
   29: +++++++acvvvv+
   30: ++++++acvvvvv
   31: ++++++acvvvvv+
   32: ++++acvvacvvvv
   33: +++++acvv+acvvv
   34: ++++acvvvv+acvv
   35: +++++++acvvvvv
   36: ++++acvvvacvvv
   37: ++++acvvvacvvv+
   38: ++++++acvvv+acvv
   39: ++++acvvv+acvvv
   40: +++++acvvacvvvv
   41: +++++acvvacvvvv+
   42: +++++++acvvvvvv
   43: +++++++acvvvvvv+
   44: +++++acvv+acvvvv
   45: +++++acvvvacvvv
   46: +++++acvvvacvvv+
   47: ++++acvvvacvvvv<
   48: ++++acvvvacvvvv
   49: ++++acvvvacvvvv+
   50: +++++acvvacvvvvv
   51: ++++acvvvv+acvvv
   52: ++++acvvv+acvvvv
   53: ++++++acvvvacvvv<
   54: ++++++acvvvacvvv
   55: ++++++acvvvacvvv+
   56: +++++++acvvacvvvv
   57: ++++++acvvv+acvvv
   58: +++++++acvvvv+acvv
   59: +++++acvvvacvvvv<
   60: +++++acvvvacvvvv
   61: +++++acvvvacvvvv+
   62: +++++++acvvvacvvv<
   63: +++++++acvvvacvvv
   64: ++++acvvvvacvvvv
   65: ++++acvvv+acvvvvv
   66: +++++++acvvv+acvvv
   67: ++++acvvvv+acvvvv<
   68: ++++acvvvv+acvvvv
   69: ++++++acvvvv<acvvv
   70: +++++++acvvacvvvvv
   71: ++++++acvvvacvvvv<
   72: ++++++acvvvacvvvv
   73: ++++++acvvvacvvvv+
   74: +++++acvvvacvvvvv<
   75: +++++acvvvacvvvvv
   76: ++++++acvvv+acvvvv
   77: ++++++acvvv+acvvvv+
   78: +++++acvvvvv+acvvv
   79: +++++acvvvvacvvvv<
   80: +++++acvvvvacvvvv
   81: +++acvvvacvvvacvvv
   82: +++acvvvacvvvacvvv+
   83: +++++++acvvvacvvvv<
   84: +++++++acvvvacvvvv
   85: ++++acvvvv+acvvvvv
   86: ++++acvvvv+acvvvvv+
   87: +++++++acvvvv+acvvv
   88: +++++++acvvv+acvvvv
   89: ++++++acvvvacvvvvv<
   90: ++++++acvvvacvvvvv
   91: ++++++acvvvacvvvvv+
   92: ++++++acvvvv<acvvvv
   93: ++++++acvvvvv+acvvv
   94: ++++acvvvacvvvv<acvv
   95: ++++++acvvv+acvvvvv
   96: ++++++acvvvvacvvvv
   97: ++++++acvvvvacvvvv+
   98: ++++acvvvacvvvv+acvv
   99: +++++acvvvvacvvvvv<
  100: +++++acvvvvacvvvvv
  101: +++++acvvvvacvvvvv+
  102: ++++acvvvv+acvvvvvv
  103: +++++acvvvvv+acvvvv<
  104: +++++acvvvvv+acvvvv
  105: +++++++acvvvacvvvvv
  106: +++++++acvvvacvvvvv+
  107: ++++acvvvacvvvacvvv<
  108: ++++acvvvacvvvacvvv
  109: ++++acvvvacvvvacvvv+
  110: +++++++acvvv+acvvvvv
  111: ++++acvvvacvvv+acvvv
  112: +++++++acvvvvacvvvv
  113: +++++++acvvvvacvvvv+
  114: ++++++acvvv+acvvvvvv
  115: ++++++acvvvv<acvvvvv
  116: +++++++acvvvv+acvvvv
  117: ++++acvvv+acvvvacvvv
  118: ?
  119: ++++++acvvvvacvvvvv<
  120: ++++++acvvvvacvvvvv
  121: ++++++acvvvvacvvvvv+
  122: ?
  123: ?
  124: ++++++acvvvvv+acvvvv
  125: +++++acvvvvvacvvvvv
  126: +++++++acvvvacvvvvvv
  127: ?
  128: ++++acvvacvvvvacvvvv
  129: ?
  130: +++++acvvvvv+acvvvvv
  131: ?
  132: ?
  133: ?
  134: ?
  135: +++++acvvvacvvvacvvv
  136: ?
  137: ?
  138: ?
  139: ?
  140: +++++++acvvvvacvvvvv
  141: ?
  142: ?
  143: ?
  144: ++++acvvvacvvvacvvvv
  145: ?
  146: ?
  147: ?
  148: ?
  149: ?
  150: ++++++acvvvvvacvvvvv
For a three-character string:

Code: Select all

    0:
    1: +--
    2: +--+--
    3: +--acvvv
    4: +--acvvvv
    5: +--acvvvvv
    6: +--+--acvvv
    7: +--acvvvvvvv
    8: +--+--acvvvv
    9: +--acvvvacvvv
   10: +--+--acvvvvv
   11: +--+--acvvvvv+--
   12: +--+--acvvvvvv
   13: +--+--acvvvvvv+--
   14: +--+--acvvvvvvv
   15: +--acvvvacvvvvv
   16: +--acvvvvacvvvv
   17: +--acvvvvacvvvv+--
   18: +--+--acvvvacvvv
   19: +--+--acvvvacvvv+--
   20: +--acvvvvacvvvvv
   21: +--acvvvacvvvvvvv
   22: +--+--acvvvvvvvvvvv
   23: +--+--acvvvacvvvv<==
   24: +--+--acvvvacvvvv
   25: +--acvvvvvacvvvvv
   26: +--acvvvvvacvvvvv+--
   27: +--acvvvacvvvacvvv
   28: +--acvvvvacvvvvvvv
   29: +--+--acvvvacvvvvv<==
   30: +--+--acvvvacvvvvv
   31: +--+--acvvvacvvvvv+--
   32: +--+--acvvvvacvvvv
   33: +--+--acvvvvacvvvv+--
   34: +--acvvvvacvvvv+--acvv
   35: +--acvvvvvacvvvvvvv
   36: +--+--acvvvacvvvvvv
   37: +--+--acvvvacvvvvvv+--
   38: +--+--acvvvacvvv+--acvv
   39: +--+--acvvvvacvvvvv<==
   40: +--+--acvvvvacvvvvv
   41: +--+--acvvvvacvvvvv+--
   42: +--+--acvvvacvvvvvvv
   43: +--+--acvvvacvvvvvvv+--
   44: +--+--acvvvvv+--acvvvv
   45: +--acvvvacvvvacvvvvv
   46: +--acvvvacvvvacvvvvv+--
   47: +--+--acvvvvacvvvvvv<==
   48: +--+--acvvvvacvvvvvv
   49: +--acvvvvvvvacvvvvvvv
   50: +--+--acvvvvvacvvvvv
   51: +--+--acvvvvvacvvvvv+--
   52: +--+--acvvvvvv+--acvvvv
   53: +--+--acvvvacvvvacvvv<==
   54: +--+--acvvvacvvvacvvv
   55: +--+--acvvvvv+--acvvvvv
   56: +--+--acvvvvacvvvvvvv
   57: +--+--acvvvacvvv+--acvvv
   58: ?
   59: +--+--acvvvvvacvvvvvv<==
   60: +--+--acvvvvvacvvvvvv
   61: +--+--acvvvvvacvvvvvv+--
   62: ?
   63: +--acvvvacvvvacvvvvvvv
   64: +--acvvvvacvvvvacvvvv
   65: +--+--acvvvvvv+--acvvvvv
   66: +--+--acvvvvv+--acvvvvvv
   67: ?
   68: +--acvvvvacvvvv+--acvvvv
   69: ?
   70: +--+--acvvvvvacvvvvvvv
   71: ?
   72: +--+--acvvvacvvvacvvvv
   73: ?
   74: ?
   75: +--acvvvacvvvvvacvvvvv
   76: ?
   77: ?
   78: ?
   79: ?
   80: +--acvvvvacvvvvacvvvvv
   81: +--acvvvacvvvacvvvacvvv
   82: ?
   83: ?
   84: +--+--acvvvvvvacvvvvvvv
   85: ?
   86: ?
   87: ?
   88: ?
   89: ?
   90: +--+--acvvvacvvvacvvvvv
   91: ?
   92: ?
   93: ?
   94: ?
   95: ?
   96: +--+--acvvvacvvvvacvvvv
   97: ?
   98: +--+--acvvvvvvvacvvvvvvv
   99: ?
  100: +--acvvvvacvvvvvacvvvvv
  101: ?
  102: ?
  103: ?
  104: ?
  105: +--acvvvacvvvvvacvvvvvvv
  106: ?
  107: ?
  108: +--+--acvvvacvvvacvvvvvv
  109: ?
  110: ?
  111: ?
  112: +--acvvvvacvvvvacvvvvvvv
  113: ?
  114: ?
  115: ?
  116: ?
  117: ?
  118: ?
  119: ?
  120: +--+--acvvvacvvvvacvvvvv
  121: ?
  122: ?
  123: ?
  124: ?
  125: +--acvvvvvacvvvvvacvvvvv
  126: ?
  127: ?
  128: +--+--acvvvvacvvvvacvvvv
For a ten-character string:

Code: Select all

    0:
    1: +---------
    2: +---------acvv
    3: +---------acvvv
    4: +---------acvvvv
    5: +---------acvvvvv
    6: +---------acvvvvvv
    7: +---------acvvvvvvv
    8: +---------acvvacvvvv
    9: +---------acvvvacvvv
   10: +---------acvvacvvvvv
   11: +---------acvvvvvvvvvvv
   12: +---------acvvvacvvvv
   13: +---------acvvvvvvvvvvvvv
   14: +---------acvvacvvvvvvv
   15: +---------acvvvacvvvvv
   16: +---------acvvvvacvvvv
   17: +---------acvvvvvvvvvvvvvvvvv
   18: +---------acvvvacvvvvvv
   19: +---------acvvvvvvvvvvvvvvvvvvv
   20: +---------acvvvvacvvvvv
   21: +---------acvvvacvvvvvvv
   22: +---------acvvacvvvvvvvvvvv
   23: ?
   24: +---------acvvvvacvvvvvv
   25: +---------acvvvvvacvvvvv
   26: +---------acvvacvvvvvvvvvvvvv
   27: +---------acvvvacvvvacvvv
   28: +---------acvvvvacvvvvvvv
   29: ?
   30: +---------acvvvvvacvvvvvv
   31: ?
   32: +---------acvvacvvvvacvvvv
   33: +---------acvvvacvvvvvvvvvvv
   34: ?
   35: +---------acvvvvvacvvvvvvv
   36: +---------acvvvacvvvacvvvv
   37: ?
   38: ?
   39: +---------acvvvacvvvvvvvvvvvvv
   40: +---------acvvacvvvvacvvvvv
   41: ?
   42: +---------acvvvvvvacvvvvvvv
   43: ?
   44: +---------acvvvvacvvvvvvvvvvv
   45: +---------acvvvacvvvacvvvvv
   46: ?
   47: ?
   48: +---------acvvvacvvvvacvvvv
   49: +---------acvvvvvvvacvvvvvvv
   50: +---------acvvacvvvvvacvvvvv
   51: ?
   52: +---------acvvvvacvvvvvvvvvvvvv
   53: ?
   54: +---------acvvvacvvvacvvvvvv
   55: +---------acvvvvvacvvvvvvvvvvv
   56: +---------acvvacvvvvacvvvvvvv
   57: ?
   58: ?
   59: ?
   60: +---------acvvvacvvvvacvvvvv
   61: ?
   62: ?
   63: +---------acvvvacvvvacvvvvvvv
   64: +---------acvvvvacvvvvacvvvv
   65: ?
   66: +---------acvvvvvvacvvvvvvvvvvv
   67: ?
   68: ?
   69: ?
   70: +---------acvvacvvvvvacvvvvvvv
   71: ?
   72: +---------acvvvacvvvvacvvvvvv
   73: ?
   74: ?
   75: +---------acvvvacvvvvvacvvvvv
   76: ?
   77: ?
   78: ?
   79: ?
   80: +---------acvvvvacvvvvacvvvvv
   81: +---------acvvvacvvvacvvvacvvv
   82: ?
   83: ?
   84: +---------acvvvacvvvvacvvvvvvv
   85: ?
   86: ?
   87: ?
   88: ?
   89: ?
   90: +---------acvvvacvvvvvacvvvvvv
   91: ?
   92: ?
   93: ?
   94: ?
   95: ?
   96: +---------acvvvvacvvvvacvvvvvv
   97: ?
   98: ?
   99: ?
  100: +---------acvvvvacvvvvvacvvvvv
  101: ?
  102: ?
  103: ?
  104: ?
  105: +---------acvvvacvvvvvacvvvvvvv
  106: ?
  107: ?
  108: +---------acvvvacvvvacvvvacvvvv
  109: ?
  110: ?
  111: ?
  112: +---------acvvvvacvvvvacvvvvvvv
  113: ?
  114: ?
  115: ?
  116: ?
  117: ?
  118: ?
  119: ?
  120: +---------acvvvvacvvvvvacvvvvvv
  121: ?
  122: ?
  123: ?
  124: ?
  125: +---------acvvvvvacvvvvvacvvvvv
As you'd expect... the one-character one has a lot of re-typing, less copying except when it's very useful. The ten-character one, at least looking this deep, never re-types, only copies. The three-character one is somewhere in-between.

All three of these were calculated by building every chain of at most 20 "steps", where a retyping or backspacing takes one step, regardless of the length of the string, but copy-paste to multiply the length by n takes n steps, in the interest of making it so that a finite number of steps will only have a finite number of possibilities. Then, all these chains are grouped by their final value, and the one with the fewest keystrokes for each group is selected. Then, if that result has fewer keystrokes than the absolute minimum number of keystrokes in a 21-step chain (the minimum of 21 times the length of the string, or one times the length of the string plus copy-pasting 20 times) then the result is definitely the shortest possible, so it's output. All those question marks, and all the numbers higher than the maximum, are values that were either never reached, or the shortest candidate was longer than the shortest possible 21-step chain.

[edit again]
Actually, if you remove the backspace option I threw in, I think this could be solved dynamically without too much trouble... if you have the solutions for 0 through n-1, then you can probably find the solution for n reasonably quickly, 'cause you don't have that many options to check, just n-1 and all of n's factors... Backspace complicates that a little, though.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby Siyko » Tue Nov 24, 2009 9:21 pm UTC

Yeah backspace and typing both complicate it - but if it were simple it wouldn't be any fun, would it?

The rules on the space also cause problems. Does it have to end with a trailing space? Probably not, but if x is equal to the length of the string WITHOUT the space this means backspacing an instance costs (x+1) while typing in one on the end costs (x), and typing two on the end costs (2x+1).

Nobody has mentioned that we can also pick how much we want to highlight (remember no mouse). If I want to make exactly 19 copies of 'this is spam' (13 with trailing space), then I can do

13 + ctrl+ acv^7, a shift+(leftarrow * 13), ctrl+ c v^3

This doesn't save time over typing it out (since i have to hit leftarrow the same amount of times as the original string), but for larger numbers this might save time if we need to add on multiples of a specific number.

edahl
Posts: 61
Joined: Wed May 13, 2009 12:15 pm UTC

Re: The mathematics of CTRL-C CTRL-V

Postby edahl » Tue Nov 24, 2009 10:28 pm UTC

Regarding this, I've reached the conclusion after a bunch of coding, that errors are invariant under copy-paste transformations.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: The mathematics of CTRL-C CTRL-V

Postby Yakk » Tue Nov 24, 2009 10:28 pm UTC

Oh ya -- ctrl-shift-arrow moves by words. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby joeframbach » Mon Mar 08, 2010 1:31 am UTC

Use the X copy buffer. Highlight, middle-click (x19).

SGI32127
Posts: 19
Joined: Sun Mar 07, 2010 8:44 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby SGI32127 » Mon Mar 08, 2010 7:33 am UTC

joeframbach wrote:Use the X copy buffer. Highlight, middle-click (x19).



no middle-click. need more than 19

kevmus
Posts: 56
Joined: Wed Apr 22, 2009 2:35 am UTC

Re: The mathematics of CTRL-C CTRL-V

Postby kevmus » Mon Mar 08, 2010 1:26 pm UTC

Qaanol wrote:Or write a script to do what you need automatically.

Computers are really good at repetitive tasks.

If you have a repetitive task, there is an easy way to get a computer to do it for you.


In PHP
<?while($i<20){echo "this is spam";$i++);?>
43 characters. It's good if you want to type something 1000 times, but scripting is not optimal here.
(unless some code-guru can shorten this up a lot)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests