Broken keyboard

[BMAD]

Imagine you have a special keyboard with the following keys:

1. A

2. Ctrl+A

3. Ctrl+C

4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.

That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

Example:-

For N = 8 the answer is M = 9, where S = { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V }.

For N = 9 the answer is M = 12, where S = { A, A, A, CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V, CTRL+V }.

[Joe's Student]

A quick solution. Bear in mind it's 4am here and this is my first post on BD in years, so forgive the terrible formatting!

[spoiler=Not sure about an actual code, but it'll look something like this.]For N<8 it's just writing A N-times. When N>7 there are two cases:

If N odd then

S = { A*([N-1]/2), Ctrl+A, Ctrl+C, Ctrl+V*([N-1]/2)-1 }

And if N even then

S = { A*(N-2)/2, Ctrl+A, Ctrl+C, Ctrl+V*(N-2)/2 }

For any N>7 we look at N-2 to account for the Ctrl+A and Ctrl+C. The 'final' buttons pressed will always be Ctrl+V and so what we'll have is:

S = { (string of A's), Ctrl+A, Ctrl+C, (String of Ctrl+V's) }.

We're looking for the two integers that sum to N-2 (one representing the A's pressed, and the other representing the Ctrl+V's pressed) that in turn give the largest number when multiplied. This is always given by the integer(s) closest to one half N-2, which is where the above formulas come from.

[bonanova]

A quick solution. Bear in mind it's 4am here and this is my first post on BD in years, so forgive the terrible formatting!

[spoiler=Not sure about an actual code, but it'll look something like this.]For N<8 it's just writing A N-times. When N>7 there are two cases:

If N odd then

S = { A*([N-1]/2), Ctrl+A, Ctrl+C, Ctrl+V*([N-1]/2)-1 }

And if N even then

S = { A*(N-2)/2, Ctrl+A, Ctrl+C, Ctrl+V*(N-2)/2 }

For any N>7 we look at N-2 to account for the Ctrl+A and Ctrl+C. The 'final' buttons pressed will always be Ctrl+V and so what we'll have is:

S = { (string of A's), Ctrl+A, Ctrl+C, (String of Ctrl+V's) }.

We're looking for the two integers that sum to N-2 (one representing the A's pressed, and the other representing the Ctrl+V's pressed) that in turn give the largest number when multiplied. This is always given by the integer(s) closest to one half N-2, which is where the above formulas come from.

Hi JS, and welcome (back) to the Den!

I was thinking along the same lines

At some point (sufficiently large n) it seemed that additional nesting of the copy/paste process helps. I did not get around to finding how large n would have to be to benefit from more nesting. In other words, type some A's, copy and repeatedly paste them. Then copy all of what you have and repeatedly paste it. Then copy all of what you have and repeatedly paste it ... etc. You pay the additive price of a select/copy for each stage, but the rewards are multiplicative. As I said, I did not determine the values of n appropriate for 2-, 3-, 4-level copying.

[Joe's Student]

Hi JS, and welcome (back) to the Den!

I was thinking along the same lines

At some point (sufficiently large n) it seemed that additional nesting of the copy/paste process helps. I did not get around to finding how large n would have to be to benefit from more nesting. In other words, type some A's, copy and repeatedly paste them. Then copy all of what you have and repeatedly paste it. Then copy all of what you have and repeatedly paste it ... etc. You pay the additive price of a select/copy for each stage, but the rewards are multiplicative. As I said, I did not determine the values of n appropriate for 2-, 3-, 4-level copying.

Woke up this morning and came here to post exactly this! Beat me to it! I'll work some more on it

[Joe's Student]

After a small amount of work it can be seen that N doesn't need to be all that large for M to benefit from more copy/paste nests. When N=14 both

S₁ = { A*6, Ctrl+A, Ctrl+C, Ctrl+V*6}

and

S₂ = { A*3, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*4 }

give M=36. When N=15, having 1 nest gives M=42, whereas having 2 nests yields M=48.

Computing the maximum number of A's produced given n copy/paste nests isn't too difficult. We first do N-2n to account for the Ctrl+A/Ctrl+C 'presses'. These n Ctrl+A/Ctrl+C 'presses' split our script into n+1 segments and so we're looking for n+1 positive integers that sum to N-2n, which also give the largest product when multiplied.

If n+1 divides N-2n, then this is given by [(N-2n)/(n+1)]^(n+1).*

Otherwise we look at the two integers closest to (N-2n)/(n+1), say p and q. A certain combination of p and q, when summed (n+1)-times, will give N-2n. If this combination is then multiplied together it will result in the largest possible product of (n+1)-integers that sum to N-2n.*

Once we have the (n+1) integers, we can assign one of them freely to each segment in our split script, which will correspond to the number of 'presses' the button in that segment gets.

In the above example of S_2, N=14, n=1, and so p=3 and q=4. We then see that p+p+q=3+3+4=10=N-2n. Therefore we do

S₂ = { A*p, Ctrl+A, Ctrl+C, Ctrl+V*p, Ctrl+A, Ctrl+C, Ctrl+V*q }

which yields M=36=3*3*4. The order of assignation of the p's and q's don't matter since multiplication is commutative. (I hate to use this word, but it should be obvious ( ) that the first segment will be a string of A's and every segment afterwords will be strings of Ctrl+V's).

Some quick computation gave me that the optimal number of nests are:

0 Nests when 1 (<=) N (<=) 7
1 Nest when 8 (<=) N (<=) 14

2 Nests when 14 (<=) N (<=) 20

3 Nests when 21 (<=) N (<=) 26

4 Nests when 27 (<=) N (<=) 32

5 Nests when 33 (<=) N (<=) 38

6 Nests when 39 (<=) N (<=) 44

After the beginning the intervals appear to settle into a pattern, however I haven't been able to prove that this holds for all N, and I would hazard a guess that these intervals eventually shrink as N gets larger.

*That this process yields the largest possible product is easy enough to prove for two summands but I haven't looked at proving it in general. I'm fairly certain it's a well-known number theoretic fact, though please someone correct me if it's not true!

Also excuse the messiness again, working on it whilst I'm writing is never a good idea! Btw, is there a neat way of indicating the less-than-or-equal symbol?

Edited April 7, 2014 by Joe's Student

[BMAD]

I am unsure about neat but since these are integers

0 Nests when 0 (<) N (<) 8
1 Nest when 7 (<) N (<) 15

2 Nests when 14 (<) N (<) 21

3 Nests when 20 (<) N (<) 27

4 Nests when 26 (<) N (<) 33

5 Nests when 32 (<) N (<) 39

6 Nests when 38 (<) N (<) 45

[LVan Toren]

After a small amount of work it can be seen that N doesn't need to be all that large for M to benefit from more copy/paste nests. When N=14 both

S₁ = { A*6, Ctrl+A, Ctrl+C, Ctrl+V*6}

and

S₂ = { A*3, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*4 }

give M=36. When N=15, having 1 nest gives M=42, whereas having 2 nests yields M=48.

Computing the maximum number of A's produced given n copy/paste nests isn't too difficult. We first do N-2n to account for the Ctrl+A/Ctrl+C 'presses'. These n Ctrl+A/Ctrl+C 'presses' split our script into n+1 segments and so we're looking for n+1 positive integers that sum to N-2n, which also give the largest product when multiplied.

If n+1 divides N-2n, then this is given by [(N-2n)/(n+1)]^(n+1).*

Otherwise we look at the two integers closest to (N-2n)/(n+1), say p and q. A certain combination of p and q, when summed (n+1)-times, will give N-2n. If this combination is then multiplied together it will result in the largest possible product of (n+1)-integers that sum to N-2n.*

Once we have the (n+1) integers, we can assign one of them freely to each segment in our split script, which will correspond to the number of 'presses' the button in that segment gets.

In the above example of S_2, N=14, n=1, and so p=3 and q=4. We then see that p+p+q=3+3+4=10=N-2n. Therefore we do

S₂ = { A*p, Ctrl+A, Ctrl+C, Ctrl+V*p, Ctrl+A, Ctrl+C, Ctrl+V*q }

which yields M=36=3*3*4. The order of assignation of the p's and q's don't matter since multiplication is commutative. (I hate to use this word, but it should be obvious ( ) that the first segment will be a string of A's and every segment afterwords will be strings of Ctrl+V's).

Some quick computation gave me that the optimal number of nests are:

0 Nests when 1 (<=) N (<=) 7

1 Nest when 8 (<=) N (<=) 14

2 Nests when 14 (<=) N (<=) 20

3 Nests when 21 (<=) N (<=) 26

4 Nests when 27 (<=) N (<=) 32

5 Nests when 33 (<=) N (<=) 38

6 Nests when 39 (<=) N (<=) 44

After the beginning the intervals appear to settle into a pattern, however I haven't been able to prove that this holds for all N, and I would hazard a guess that these intervals eventually shrink as N gets larger.

*That this process yields the largest possible product is easy enough to prove for two summands but I haven't looked at proving it in general. I'm fairly certain it's a well-known number theoretic fact, though please someone correct me if it's not true!

Also excuse the messiness again, working on it whilst I'm writing is never a good idea! Btw, is there a neat way of indicating the less-than-or-equal symbol?

When N=14 neither S1 nor S2 give M=36.

S1 = { A*6, Ctrl+A, Ctrl+C, Ctrl+V*6} gives M=42 and

S2 = { A*3, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*4 } gives M=60.

Let us consider S2 for example:

1) A*3 gives AAA,

2) Ctrl+A, Ctrl+C selects and copies AAA

3) the first Ctrl+V pastes AAA, so we have then AAA AAA, 6 A's

4) the second and the third Ctrl+V each paste the same AAA to what we have already.

This makes AAA AAA AAA AAA, 12 A's.

5) The next Ctrl+A, Ctrl+C selects and copies those 12 A's

6) The last four Ctrl+V's each paste 12 A's (48 together) to the 12 we have, resulting in 60 A's.

Maybe computing the maximum number of A's is not too difficult, but it isn't easy either, because n is not given.

We have to split up N-2n in n+1 integers where only N is given and n is to be presumed.

For large N that is a lot of work, calculating all possibilities. A computer can do it.

Finally the product of those integers is not the maximum of M.

For N=14 is M=64 with S3 = { A*4, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*3 }

[LVan Toren]

In what follows I adopt as abbreviations A for Ctrl+A, C for Ctrl+C, V for Ctrl+V and X for the letter we want to multiplicate.

So if N=10 and P1=XXXACVACVV this gives M=18, with a starting string of 3 X's, a select, copy and paste that adds 3 making it 6 and a second select copy followed by two pastes that each add 6 to make 18.
P1 contains two AC's, so n=2. N-2n=10-4=6 is split in n+1=2+1=3 integers, in this case 3+1+2 in that order (the order is important).
3+1+2 means that there are 3 leading X's then an AC with 1 V and then an AC with 2 V's.
The order is important because if we split 6 in 2+1+3 we get:
P2=XXACVACVVV which gives M=16.
We restart with N=10 but take n=1, one AC. N-2n=10-2=8 to be split in n+1=2 integers e.g.8=3+5
This is program P3=XXXACVVVVV with M=18.

What does ACV in a program?
If we have a string with length l before ACV it is selected, copied and then pasted, making the new length 2*l.
ACVV adds two times the length making it l+2*l=3*l.
ACVVV adds 3 times the length making it 4*l.
AC followed by p V's makes the length (p+1)*l, multiplying it with p+1.
Example: P1=XXXACVACVV, N=10, n=2, N-2n=6, split in 3+1+2.
meaning 3 leading X's, length 3
followed by AC and 1V multiplying the length with 1+1=2, gives length 6
followed by AC and 2V's multyplying the length with 2+1=3 giving length 18.

Solution in general.
Given N, we presume n and split N-2n in n+1 integers, which, increased by 1 except the first, give M.
Trying out all possibilities will learn us the largest M.

N=10, n=1, split 10-2*1=8 in 1+1=2 integers with sum 8.
1+7 starting with length 1, multiplied with 7+1 gives M=8
7+1 starting with length 7, multiplied with 1+1=2 gives M=14
2+6 starting with length 2, multiplied with 6+1=7 gives M=14
6+2 starting with length 6, multiplied with 2+1=3 gives M=18
3+5 starting with length 3, multiplied with 6 gives M=18
5+3 starting with length 5, multiplied with 4 gives M=20
4+4 starting with length 4, multiplied with 5 gives M=20
If we take n=2 we have to split 10-2*2=6 into 2+1=3 integers
1+2+3 gives M=1*3*4=12
1+3+2 M=12
2+1+3 M=16
2+3+1 M=16
3+1+2 M=18
3+2+1 M=18
2+2+2 M=18
If we take n=3 we have to split 10-2*3=4 in 3+1=4 integers
1+1+1+1 M=8
The maximum is M=20 with the programs P4=XXXXXACVVV and P5=XXXXACVVVV

[LVan Toren]

I haven't calculated all possibilities but only those that seemed to be worth it.

It gave the following list of N and M_max
N M_max
6 6
7 9
8 12
9 15
10 20
11 25
12 36
13 48
14 64
15 80
16 100
17 144
18 192
19 256
...
Not sure that it is quite exact, should be checked.
I have the feeling that there must be a pattern in it, but I don't see it.
This could be another puzzle: find the pattern, what are the next three M's?

[Joe's Student]

I believe we have different interpretations of the mechanics of this problem.

When N=14 neither S1 nor S2 give M=36.

S1 = { A*6, Ctrl+A, Ctrl+C, Ctrl+V*6} gives M=42 and

S2 = { A*3, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*4 } gives M=60.

Let us consider S2 for example:

1) A*3 gives AAA,

2) Ctrl+A, Ctrl+C selects and copies AAA

3) the first Ctrl+V pastes AAA, so we have then AAA AAA, 6 A's

4) the second and the third Ctrl+V each paste the same AAA to what we have already.

This makes AAA AAA AAA AAA, 12 A's.

5) The next Ctrl+A, Ctrl+C selects and copies those 12 A's

6) The last four Ctrl+V's each paste 12 A's (48 together) to the 12 we have, resulting in 60 A's.

Maybe computing the maximum number of A's is not too difficult, but it isn't easy either, because n is not given.

We have to split up N-2n in n+1 integers where only N is given and n is to be presumed.

For large N that is a lot of work, calculating all possibilities. A computer can do it.

Finally the product of those integers is not the maximum of M.

For N=14 is M=64 with S3 = { A*4, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*3 }

This wasn't my understanding. I assumed that the first Ctrl+V replaces the three typed A's since they're still selected, much like everyday word-processing software. In otherwords:

- Ctrl+A selects

- Ctrl+C copies

- The three A's are still selected

- Ctrl+V replaces the selected A's with pasted ones.

That was the basis for my work, though your interpretation may well be correct. Maybe BMAD could clarify exactly how the process works?

Edit: From BMAD's examples it looks to be the case that the typed A's are indeed replaced. However, your interpretation would make an equally interesting puzzle!

Edited April 15, 2014 by Joe's Student

[BMAD]

My interpretation is along the lines of Joe student

[LVan Toren]

I believe we have different interpretations of the mechanics of this problem.

When N=14 neither S1 nor S2 give M=36.

S1 = { A*6, Ctrl+A, Ctrl+C, Ctrl+V*6} gives M=42 and

S2 = { A*3, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*4 } gives M=60.

Let us consider S2 for example:

1) A*3 gives AAA,

2) Ctrl+A, Ctrl+C selects and copies AAA

3) the first Ctrl+V pastes AAA, so we have then AAA AAA, 6 A's

4) the second and the third Ctrl+V each paste the same AAA to what we have already.

This makes AAA AAA AAA AAA, 12 A's.

5) The next Ctrl+A, Ctrl+C selects and copies those 12 A's

6) The last four Ctrl+V's each paste 12 A's (48 together) to the 12 we have, resulting in 60 A's.

Maybe computing the maximum number of A's is not too difficult, but it isn't easy either, because n is not given.

We have to split up N-2n in n+1 integers where only N is given and n is to be presumed.

For large N that is a lot of work, calculating all possibilities. A computer can do it.

Finally the product of those integers is not the maximum of M.

For N=14 is M=64 with S3 = { A*4, Ctrl+A, Ctrl+C, Ctrl+V*3, Ctrl+A, Ctrl+C, Ctrl+V*3 }

This wasn't my understanding. I assumed that the first Ctrl+V replaces the three typed A's since they're still selected, much like everyday word-processing software. In otherwords:

- Ctrl+A selects

- Ctrl+C copies

- The three A's are still selected

- Ctrl+V replaces the selected A's with pasted ones.

That was the basis for my work, though your interpretation may well be correct. Maybe BMAD could clarify exactly how the process works?

Edit: From BMAD's examples it looks to be the case that the typed A's are indeed replaced. However, your interpretation would make an equally interesting puzzle!

You are right. I solved another puzzle

[dgreening]

I read this about a week ago, but have been out of pocket for all that time..
sorry if I am repeating old work.

There are really 3 functions in order of preference [low to high]

• Type "A"
• Ctrl-V [paste] (only works after at least 1 copy)
• Ctrl- A, C, V [copy all and paste]

Basic Rules of the algorithm

• You must start by typing in "A"s [there is nothing to copy and nothing to paste]
• Continue doing what you are doing - until you can gain more by
  performing the a higher function [based on the number of turns
  it will take to perfrom that function]

Therefore

• Start typing "A"s
• After typing 3 "A"s you reach the first decision point
  • If n = 4 or 5, enter that many more "A"s
  • If n > 5 use Ctrl-A, C, V
    • This take 3 turns and will copy the first 3 letters and repeat them
    • this action returns the same results as typing more "A"s, so you should do it
• At the 7th turn you have 6 "A"s. you have 3 choices
  • type another "A" [results 1 turn yields 1 additonal "A"] (1 "A"/ turn)
    • note: you will never find this choice attractive again [after you have
      copied once] and should not be used again.
  • Ctrl - V [results 1 turn yields 3 additonal "A"s] (3 "A"s/ turn)
  • Ctrl-A, C, V [results 3 turns yields 6 additional "A"s] (2 "A"s/ turn)
  • Thus the 7th turn should be Ctrl-V
• At the 8th turn
  • If n < 11: use Ctrl - V for the remaining turns
  • If n > 11 you have 2 choices
    • Ctrl-V for the next 3 turns [results: 3 turns yields 9
      additional "A"s] (3 "A"s/ turn)
    • Ctrl-A, C, V over the next 3 turns [results: 3 turns yields 9 additional
      "A"s] (3 "A"s/ turn)
    • You should use Ctrl-A, C, V because as stated in the basic
      rules, use the higher level function when it returns the same or better results
      as the lower level function
• At the 11th turn - The decision analysis is exactly the same as for
  the 7th turn - you should always use Ctrl-V

• At the 12th turn - The decision analysis is exactly the same as
  for the 8th turn - you should always use Ctrl-A, C, V (if you have enough turns
  left - else just Ctrl-V)
  

This repition continues

• At 16th, 20th, 24th .... turn
  • If you have at least 4 more turns: Use Ctrl- A, C, V followed by Ctrl-V
    [this will triple the total number of "A"s ]
  • If you have 1, 2 or 3 turns left: use Ctrl-V [once twice or 3
    times]

This is really a task to maximize the product. Each action either increases the size of the multiplier or creates a new term.

• Typing "A" some number of times creates a term equal to the number of times
  you enter it [e.g., AAAA = 4]
• Ctrl-A, C, V creates a new term with a value of 2
  • Every Ctrl-V [after Ctrl-A, C, V] increments the newly created term by
    1 [e.g., Ctrl-A, C, V, Ctrl-V = 3]

So for the sequence used above [(AAAA) (Ctrl-A, C, V, Ctrl-V)] the terms would be 4 and 3 - yielding a product of 12

Adding another Ctrl-A, C, V [value 2] to the sequence [(AAAA) (Ctrl-A, C, V,Ctrl-V) (Ctrl-A, C, V) ] would create
a new term = 2. and the product of these 3 terms 4 * 3 * 2 = 24

Note: it doesn't matter what order you take these terms, the following yield
the same results

[(AA) (Ctrl-A, C, V) (Ctrl-A, C, V, Ctrl-V) ] yields terms 2 * 3 * 4 = 24