4
\$\begingroup\$

EDIT: I posted this question searching for a beautiful, original solution to this problem. Therefore, I accepted a user's edited category "popularity-contest". Still, I keep receiving down-votes from people and requests that I make this a search for optimal solutions (i.e. runtime, code size etc.). That is not my intention. I'm leaving the problem open for a few more hours, if people still down-vote it for no reason, I'll just go ahead and delete it. Maybe I am posting to the wrong community (probably should be searching for enthusiastic programmer communities).

Copy-paste master

John wants to write this phrase multiple times into a text document:

I am a copy-paste master.

He creates a new, empty text document, and types down the phrase. He wants to copy and paste this phrase on a new line until he reaches at least a certain number of lines. He figures out it would be quicker if, from time to time, he selected all the text written so far, copies again and then resumes pasting.

Assume the following:

  • At time t = 0 the phrase has been typed for the first time and John begins the copy-paste process.
  • It takes T1 to Select All (Ctrl+A), Copy (Ctrl+C) and Clear Selection (End) => Operation 1
  • It takes T2 to press Enter and then Paste (Ctrl+V) => Operation 2
  • After he has copied the phrase the first time, let N1 be the number of Operations 2 until he does Operation 1 again; then follows N2 times Operation 2, etc., the last set of Operation 2 being done Nk.
  • Let L be the target (minimum) number of lines.
  • A solution of the problem consists of the collection: (k, N1, N2, ..., Nk)

A quick example: for L = 10, possible solutions are:

  • (1, 9)
  • (2, 4, 1)
  • (3, 1, 2, 1)

Problem

Given (L, T1, T2), find the solution (k, N1, N2, ..., Nk) that minimizes the total time to reach at least L lines.

P.S.

Obviously the total time is:

T = k * T1 + T2 * SUM(Nj; j=1..k)

And the total number of lines at the end of T is:

L' = PRODUCT(1 + Nj; j=1..k) with the condition L' >= L

EDIT:

At Optimizer's suggestion, I will break down the (3, 1, 2, 1) solution for L = 10:

  • step 1: copy 1 line, then 1 paste => 2 lines
  • step 2: copy 2 lines, then 2 pastes => 6 lines
  • step 3: copy 6 lines, then 1 paste => 12 lines
\$\endgroup\$
9
  • 8
    \$\begingroup\$ You're asking for an optimal algorithm, so why score by upvotes instead of code size or runtime? \$\endgroup\$ Oct 1 '14 at 14:33
  • \$\begingroup\$ Can you breakdown (3, 1, 2, 1), explaining what all is happening ? Its a bit hard to grasp how 10 lines were reached using that. \$\endgroup\$
    – Optimizer
    Oct 1 '14 at 14:34
  • 1
    \$\begingroup\$ @Optimizer There are 3 'steps.' He pastes the line once: there are now 2 lines. He copies these lines and pastes them twice: there are now 6 lines. He copies these lines and pastes them once: there are now 12 lines. \$\endgroup\$ Oct 1 '14 at 15:04
  • 1
    \$\begingroup\$ Ah, target is just a minimum target ... \$\endgroup\$
    – Optimizer
    Oct 1 '14 at 15:05
  • 1
    \$\begingroup\$ Very much related: Minimal keystrokes needed... \$\endgroup\$
    – Geobits
    Oct 1 '14 at 15:09
4
\$\begingroup\$

Python, optimal solution

Note that this problem boils down to this optimization problem (as noted in the question):

Minimize T1*k + T2*sum(N_i)
with prod(1+N_i) >= L

(which interestingly means you can swap the values while still getting the same number of total lines)

When k is fixed, the first term T1*k is constant, and the T2 in second term is immaterial, and the problem becomes:

Minimize sum(N_i)
with prod(1+N_i) >= L

which is equivalent to (by substituting N_i with N_i-1:

Minimize sum(N_i)
with prod(N_i) >= L

for which it is well known that the minimum will be achieved when N_i are equal to k-th root of L. Since the N_is need to be integers, we take the closest value which still give us product greater than L.

So the following code does just that, checking each possible k (at the total complexity of log_2(L)), and taking the solution with minimum total time. Note that this will also give the solution with the lowest k if there are multiple solutions.

Hope the comments in the code will explain further confusion that may arise.

Some sample runs:

Enter L, T1, T2: 10 1 2
(3, 1, 1, 2) with score 11
Enter L, T1, T2: 10 10 10
(2, 2, 3) with score 70
Enter L, T1, T2: 10 10 2
(1, 9) with score 28
Enter L, T1, T2: 10 10 20
(3, 1, 1, 2) with score 110
Enter L, T1, T2: 10 5 0
(1, 9) with score 5
Enter L, T1, T2: 10 0 5
(3, 1, 1, 2) with score 20

Note that the last example has another solution (4, 1, 1, 1, 1) with score 20.

Code:

import math

def compute_score(k, L, T1, T2):
    """ Compute the best possible score given k

    Best score is achieved when the values are as close as possible to the
    k-th root of L, since we are only minimizing the sum of the values.
    """
    # k-th root of L
    k_root = math.ceil(pow(L, 1.0/k))

    # Find out how many of those k values can be reduced by 1,
    # while still maintaining product >= L
    k_pow = float(pow(k_root, k))
    reduction = int(math.floor(math.log(k_pow/L, k_root/(k_root-1.0))))

    # Generate the values
    k_root = int(k_root)
    vals = [k_root-2 if i<reduction else k_root-1 for i in xrange(k)]

    # Compute the score
    score = k*T1 + T2*sum(vals)
    return (score, vals)

def find_min_score(L, T1, T2):
    """ Find minimum possible total time, given L, T1, and T2

    Works by finding minimum possible total time on each possible k.
    Note that k <= ceil(log_2(L)) since N_i >= 1 and so (1+N_i) >= 2, so at
    k = ceil(log_2(L)), N_i = 1 for all i, which is the minimum sum
    """
    # k_max = ceil(log_2(L))
    k_max = int(math.ceil(math.log(L, 2)))

    # Trivial score when k=1
    min_score = T1 + T2*(L-1)
    min_vals = [L-1]
    min_k = 1

    # Find minimum
    for k in xrange(2, k_max+1):
        (score, vals) = compute_score(k, L, T1, T2)
        if score < min_score:
            min_score = score
            min_vals = vals
            min_k = k
    return (min_score, min_k, min_vals)

def main():
    while True:
        L, T1, T2 = map(int, raw_input('Enter L, T1, T2: ').split())
        (score, k, vals) = find_min_score(L, T1, T2)
        print '(%d, %s) with score %d' % (k, ', '.join(map(str, vals)), score)

if __name__ == '__main__':
    main()
\$\endgroup\$
0
\$\begingroup\$

CJam, WTH

I thought that I will give it a shot in CJam. I had to write my own minimizing and combination routines as CJam is just a stack operations language.

Here goes the code:

ri:Lri:T;ri:Y;2mLm],:){L,a*{m*{(\+}%}*}%({aa}%+:~{:):*L<!},W%_0=_{_,T*\:+Y*+}:R~@{_R@>@@?_R}/;_,S@S*

Its a bit brute force so for high values of input L it takes a while before finishing.

Input goes like:

10 2 2

Where 10 is the target lines (L), first 2 is T1 and second 2 is T2. For the above input, output is:

2 1 4

Say if you had given input as

10 2 4

i.e. for the same target lines, T2 is more than T1, the output will be

3 1 1 2

Try it online here , but I will recommend the Java way of running the code as mentioned here

\$\endgroup\$

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.