14
\$\begingroup\$

If I want to type the string aaa, the least keystrokes I can type it in is 3: a a a. But if I want to type the string aaaaaa, I can do it in 5: a a a ctrl-c ctrl-v, where the ctrl-c refers to copying aaa and the ctrl-v refers to pasting it.

Specifically, starting with an empty "buffer" and an empty "clipboard":

  • The keystroke a appends an a to the buffer.
  • ctrl-c takes some substring of the buffer and stores it into the clipboard. I'll notate it as ctrl-c(5) or similar to refer to 5 characters being stored. Only one string can be stored into the clipboard, and storing overwrites previous content.
  • ctrl-v appends the clipboard to the buffer.

Each of these counts as one keystroke.

With a larger example, the least keystrokes 17 as can be typed in is 8:

a a a ctrl-c(3) ctrl-v ctrl-v ctrl-c(8) ctrl-v

Your challenge is to, given a number n, return the number of keystrokes required to type n as. This is , shortest wins!

Testcases

These are done by hand, so tell me if any of these are wrong. Also, this doesn't appear to be on OEIS. I've written some not-quite-functional python code to find all possible outputs for a given length.

The first 30 terms of the sequence are:

1,2,3,4,5,5,6,6,6,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10,9,10,10,10

And some more specific ones, with examples:

11 -> 7 (a a a ctrl-c(3) ctrl-v ctrl-c(5) ctrl-v)
17 -> 8 (a a a ctrl-c(3) ctrl-v ctrl-v ctrl-c(8) ctrl-v)
25 -> 9 (a a a ctrl-c(3) ctrl-v ctrl-v ctrl-c(8) ctrl-v ctrl-v, the python code doesn't find this one)
75 -> 12 (a a a ctrl-c(3) ctrl-v ctrl-v ctrl-c(9) ctrl-v ctrl-v ctrl-c(24) ctrl-v ctrl-v, python code also misses this one)
Improve this question
\$\endgroup\$
5
  • 8
    \$\begingroup\$ Your exemple seem to imply that the mouse selection and clicking [at the end, to both unselect and choose a spot] do not count as keystrokes? My Vim blood boils ^^ \$\endgroup\$
    – Olivier Dulac
    Commented Mar 14 at 12:26
  • 2
    \$\begingroup\$ I think this can be formulated as dynamic programming, where the state is the current length of string as well as the length in the buffer. \$\endgroup\$
    – qwr
    Commented Mar 14 at 18:12
  • 2
    \$\begingroup\$ @OlivierDulac: yeah, seriously. If an arbitrary amount of mouse work is allowed, just middle-click to paste, or bring up a right-click context menu to copy and paste. I assumed when reading at first that the entire textbox was the "selection" copied by control-c, since that's the only thing plausible with just a keyboard without having hit any shift-arrow keys or even ctrl-a. Being able to select precisely 24 characters somehow, for the same time cost as hitting a or ctrl-v is total nonsense. This needs a new title and framing to make any sense as an application of this math problem. \$\endgroup\$
    – Peter Cordes
    Commented Mar 15 at 7:03
  • 5
    \$\begingroup\$ @PeterCordes this a simplified problem and not intended to be seen as any "application of [a] math problem." This is not any real world problem. \$\endgroup\$
    – Seggan
    Commented Mar 15 at 12:49
  • 1
    \$\begingroup\$ @PeterCordes They probably don't allow using the autorepeat on the keyboard either. \$\endgroup\$
    – Andrew Morton
    Commented Mar 16 at 14:28

7 Answers 7

Reset to default
8
\$\begingroup\$

JavaScript (Node.js), 47 bytes

  • -1 by Arnauld.
f=x=>x<6?x:Math.min(f(x+1>>1)+2,f(x-=x/3<<1)+3)

Try it online!

Python 2, 49 bytes

f=lambda x:x*(x<6)or min(f(x-x/2)+2,f(x-x/3*2)+3)

Try it online!

I don't really ensure this function is correct. But it at least pass all testcases given.

After I ask this solution on Math SE, caduk had provided a nice prove to it. You may read the prove by caduk on Math SE.

Anyway, the formula is

$$ f(x)= \begin{cases} n & n<6 \\ \min \left\{f\left(n-\left\lfloor\frac{n}{2}\right\rfloor\right)+2, f\left(n-2\left\lfloor\frac{n}{3}\right\rfloor\right)+3 \right\} & \text{otherwise} \end{cases} $$

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ Is it possible that you type more than n-floor(n/2)c and copy, as the function isn't monotone? \$\endgroup\$
    – l4m2
    Commented Mar 14 at 5:43
  • \$\begingroup\$ @l4m2 reasonable argue, but i cannot find a counterexample with n<2000 compared with the referenced implementation. So i have no idea how to either prove it or reject it. \$\endgroup\$
    – tsh
    Commented Mar 14 at 6:00
  • 1
    \$\begingroup\$ I tested to 116M without counterexample \$\endgroup\$
    – l4m2
    Commented Mar 14 at 7:23
  • \$\begingroup\$ If I understand the description correctly for 81 a's you could do: a a a c(3) v v c(9) v v c(27) v v for a total of 12 key strokes, way less then how I understand your algorithm which starts with typing either 41 or 27 a's first? \$\endgroup\$
    – quarague
    Commented Mar 15 at 9:46
  • \$\begingroup\$ @quarague how can it be different from f(27)+3 in second part of min? \$\endgroup\$
    – tsh
    Commented Mar 15 at 10:29
3
\$\begingroup\$

JavaScript (Node.js), 68 bytes

f=(n,m,i=n>>1)=>i?Math.min(f(n-i,i)-~(i!=m),f(n,m,i-1),f(n-1,m)+1):n

Try it online!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Charcoal, 51 38 bytes

⊞υ⟦⁰⟧ＦＮ⊞υＥ⁺²ι⌊Ｅ⮌υ⌊Ｅμ⁺ξ⁺∨⁼π⊕ν⊕ν¬⁼πκＩ⌊⊟υ

Try it online! Link is to verbose version of code. Explanation: Uses dynamic programming on the basic recurrence relation, which may be equivalent to @l4m2's approach, but I can't read it.

⊞υ⟦⁰⟧

Start with 0 keystrokes to type 0 as.

ＦＮ

Loop over all numbers up to n.

⊞υＥ⁺²ι⌊Ｅ⮌υ⌊Ｅμ⁺ξ⁺∨⁼π⊕ν⊕ν¬⁼πκ

Loop over all clipboard sizes up to n and calculate the minimum number of keystrokes needed for the current number while finishing with that clipboard size. All previous entries are considered; 1 is added to the entry if it has a different clipboard size, as that means another ^C is needed, plus the number of extra as is added, unless the clipboard is of exactly the right size, in which case 1 is added, as in that case only a ^V is needed. (The values where more than one a is needed are unnecessary but it's golfier to calculate and discard them.)

Ｉ⌊⊟υ

Output the minimum number of keystrokes needed to output n in unary.

A port of @tsh's formula using dynamic programming takes 33 bytes:

Ｆ⊕Ｎ⊞υ⎇‹ι⁶ι⌊Ｅ²⁺⁺²κ§υ⁻ι×⊕κ÷ι⁺²κＩ⌊⊟υ

Try it online! Link is to verbose version of code.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Swift 5.9, 48 bytes

let f={x in x<6 ?x:2+min(f(x-x/2),1+f(x-x/3*2))}

A direct port of @tsh's Python 2 answer, because I don't know how else to do this concisely.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python3, 327 bytes

R=range
def f(n):
 q,s,r=[(0,0)],[],[]
 for a,c in q:
  if a==n:r+=[c];continue
  if r and c>=min(r):continue
  if a<3:q+=[(a+1,c+1)]
  else:
   U=[(a+1,c+1)]
   for i in R(3,min(a,n-a)+1):
    for j in R(1,(n-a)//i+1):U+=[(a+i*j,c+1+j)]
   for A,B in U:
    if all(k<A or K>B for k,K in s):q+=[(A,B)];s+=[(A,B)]
 return min(r)

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ -6 if you change 0==any(k>=A and K<=B into all(k<A or K>B \$\endgroup\$
    – Vélimir
    Commented Mar 14 at 23:38
  • \$\begingroup\$ @Vélimir Thank you, updated \$\endgroup\$
    – Ajax1234
    Commented Mar 18 at 17:06
1
\$\begingroup\$

Ruby, 42 bytes

f=->x{x<6?x:2-[-f[x-x/2],~f[x-x/3*2]].max}

Try it online!

Not very original, basically a port of tsh's answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 64 bytes

A direct port of @tsh's Python 2 answer.

def f(x:Int):Int=if(x<6)x else 2+Math.min(f(x-x/2),1+f(x-x/3*2))

Attempt This Online!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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