9
\$\begingroup\$

This challenge is based on this Mathematics answer.

Write the shortest program or function that, when given some natural number \$n\$, outputs \$S(n)\$, which is the minimum number of steps for generating a string containing at least \$n\$ copies of the original string, using only select-all, copy, and paste operations.

In the Mathematics answer, \$S(n)\$ is found to satisfy the formula

$$ S(n) = \min_{i=1, \ldots, 8} 5 \lceil \log_4(n/u_i) \rceil+c_i $$ where \$(c_i, u_i)\$ is a tuple from the set of tuples \$ I = \{ (0,1), (3,2), (7,6), (4,3), (8,9), (12,27), (16,81), (6,5) \}\$.

Test Cases

1 => 0
2 => 3
4 => 5
8 => 8
16 => 10
32 => 13
64 => 15
128 => 18
256 => 20
512 => 23
1024 => 25
2048 => 28
4096 => 30
8192 => 33
16384 => 35
32768 => 38
65536 => 40
131072 => 43
262144 => 45
524288 => 48
1048576 => 50
2097152 => 53
100000 => 42
\$\endgroup\$
14
  • 2
    \$\begingroup\$ I assume it's intended that when you select all, copy, then paste, the paste doesn't overwrite the selection but appends to it? \$\endgroup\$
    – xnor
    Commented Jul 4 at 20:23
  • 5
    \$\begingroup\$ Does "containing n copies of the original string" mean at least n, or exactly n? \$\endgroup\$
    – xnor
    Commented Jul 4 at 20:24
  • 2
    \$\begingroup\$ I don't understand why \$f(4)=6\$. Can't you quadruple in just 5 operations by doing select-all, copy, paste, paste, paste? Since the pastes append as you say, only 3 are needed here. \$\endgroup\$
    – xnor
    Commented Jul 4 at 22:36
  • 5
    \$\begingroup\$ I went through the math.se post and I think there is a typo in the formula: (1,1) should be (0,1). This change affects all test inputs which are in the form of 4^k. Added a comment about this on the math.se post too. \$\endgroup\$
    – Bubbler
    Commented Jul 4 at 23:49
  • 4
    \$\begingroup\$ The fixed formula agrees with an algorithmic solution for up to 1e6. \$\endgroup\$
    – Bubbler
    Commented Jul 5 at 0:52

12 Answers 12

9
\$\begingroup\$

Python 3, 48 bytes

f=lambda n:n>1and-~min(i+f(n/i)for i in b"")

Try it online!

50 bytes

f=lambda n:n>1and min(i+1+f(n/i)for i in[2,3,4,5])

Try it online!

Doesn't bother with the formula. Instead, implements the characterization from the math SE post where each step creates 2, 3, 4, or 5 copies of the strings for that many operations plus one.

The outputs don't match the formula-derived test cases on powers of 4, but as Bubbler points out, this is due to a typo in the formula in the math SE post.

\$\endgroup\$
4
  • \$\begingroup\$ You can save a byte in the 2nd one with i-~f. \$\endgroup\$
    – Shaggy
    Commented Jul 5 at 8:06
  • \$\begingroup\$ @Shaggy I included that one just as a more readable version of the 48 byter. \$\endgroup\$
    – xnor
    Commented Jul 5 at 8:11
  • \$\begingroup\$ Ah, OK. What does the b" " do in the 48 byter? I can't figure it out. \$\endgroup\$
    – Shaggy
    Commented Jul 5 at 12:13
  • 3
    \$\begingroup\$ @Shaggy I guess it's the byte string consisting of code points 2,3,4,5 which are all unprintable, so we cannot actually see them. \$\endgroup\$ Commented Jul 5 at 17:27
2
\$\begingroup\$

Google Sheets, 68 bytes

=SORTN(5*CEILING(LOG(A1/{1;2;6;3;9;27;81;5},4))+{1;3;7;4;8;12;16;6}) 
\$\endgroup\$
2
\$\begingroup\$

Picat, 41 bytes

f(1)=0.
f(N)=[f(N/>I)+I+1:I in 2..5].min.

Attempt This Online!

Same approach as xnor's Python answer: recurses through the cases of ctrl+A C V{1,4} to get at least N characters as a result.

With the help of table in the header section, it computes all test cases almost instantly. Thanks to the /> operator which does ceil-ed integer division, all intermediate arguments are integers without any complications, and we can simply pattern-match the 1 as the base case.

Bitwise not operator ~ exists in Picat, but it doesn't like putting the two symbols -~ side-by-side, so the usual -~ trick does not save any bytes.

\$\endgroup\$
2
\$\begingroup\$

Desmos, 41 bytes

I=[2...5]
f(n)=\{n>1:\min(f(n/I)+I+1),0\}

Port of @xnor's Python 3 answer so make sure to upvote that answer too!

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 98 bytes

Basically a direct implementation of the (fixed) formula given in the challenge.

with(Math)f=n=>min(...[81,27,9,6,5,3,2,1].map((v,i)=>ceil(log(n/v)/log(4))*5-~(37115838>>i*4&15)))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 23 bytes

"D1›Di4L+DŠ/®δ.V+>ß"©.V

Port of @xnor's Python answer, so make sure to upvote that answer as well.
Still pretty long, since 05AB1E is very verbose for recursive functions.

Try it online or verify most test cases (it'll time out before it has output all test cases).

Using the given formula would be 32 bytes instead:

•¬òÃ,v₅aw°Üÿ∊•82в2ôε`Š/4.nî5*+}ß

Try it online or verify all test cases.

Explanation:

Uses recursive method:

$$f(n) = \begin{cases} 0, & \text{if $n\leq1$} \\ \min(f(\frac{n}{2})+3, f(\frac{n}{3})+4, f(\frac{n}{4})+5, f(\frac{n}{5})+6), & \text{if $n>1$} \end{cases}$$

"..."             # Define the recursive string explained below
     ©            # Store it in variable `®` (without popping)
      .V          # Pop and evaluate it as 05AB1E code
                  # (after which the result is output implicitly)

D                 # Duplicate the current value n
                  # (which will use the implicit input in the first iteration)
 1›               # Pop and check whether it's larger than 1
   D              #  Duplicate this check
   i              #  Pop the copy, and if it's truthy:
    4L            #  Push list [1,2,3,4]
      +           #  Add the truthy check that's still on the stack: [2,3,4,5]
       D          #  Duplicate this list
        Š         #  Tripleswap to [2,3,4,5],n,[2,3,4,5]
         /        #  Divide [n/2,n/3,n/4,n/5]
           δ      #  Map over each value:
          ® .V    #   And do a recursive eval to `®`
              +   #  Then add the values in the two lists together:
                  #   [2+f(n/2),3+f(n/3),4+f(n/4),5+f(n/5)]
               >  #  Increase each by 1
                  #   [3+f(n/2),4+f(n/3),5+f(n/4),6+f(n/5)]
                ß #  Pop and leave the minimum
                  # (implicit else: use the duplicated falsey check, aka 0)
•¬òÃ,v₅aw°Üÿ∊•     # Push compressed integer 50972899172091152076282460330 
  82в              # Convert it to base-82 as list:
                   #  [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16]
     2ô            # Split it into pairs:
                   #  [[1,0],[2,3],[3,4],[5,6],[6,7],[9,8],[27,12],[81,16]]
       ε           # Map over each pair [u,c]:
        `          #  Pop and push both values to the stack
         Š         #  Triple-swap u,c to c,i,u, where i is the implicit input
          /        #  Divide the input by u
           4.n     #  Take log_4 of it
              î    #  Ceil it
               5*  #  Multiply by 5
                 + #  Add c
       }ß          # After the map: pop and leave the minimum
                   # (which is output implicitly as result)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •¬òÃ,v₅aw°Üÿ∊• is 50972899172091152076282460330 and •¬òÃ,v₅aw°Üÿ∊•82в is [1,0,2,3,3,4,5,6,6,7,9,8,27,12,81,16].

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

FN⊞υ∨¬ι⁺³⌊E⁴⁺κ§υ÷ι⁺²κI⊟υ

Try it online! Link is to verbose version of code. Explanation: Based on @xnor's approach but using dynamic programming instead of recursion.

FN

Calculate all of the results for 1 to n. Note that the loop variable is 1 less than the index of the result being calculated but this actually saves bytes as ⌈i/k-1⌉=(i-1)//k which is simply an integer division.

⊞υ∨¬ι⁺³⌊E⁴⁺κ§υ÷ι⁺²κ

The result for 1 is just 1 while the result for other iterations is the best of four previously calculated results.

I⊟υ

Output the result for n.

\$\endgroup\$
1
\$\begingroup\$

Nibbles, 26 nibbles (13 bytes)

 `; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [

Attempt This Online!

Another recursive 'try 1,2,3 or 4 pastes at each step' approach.

Nibbles only has integer arithmetic, so we can't (easily) count down & divide the target at each recursive step (as used in xnor's approach).

However, Nibbles does remember the program input as a global variable across all recursive calls, so we can simply count up the string-copies-so-far (starting at 1) and stop when we reach the program input, which is more intuitive to me anyway.

`; 1 -@$ 0 `/ . +~,4 + _ * @$ +$~ [         # full program; input is stored in variable @
`; 1                                        # launch recursive function starting with copies=1 
                                            # (stored in variable $)
     -@$                                    # stop when input <= copies-so-far
         0                                  # and return zero
                                            # otherwise return
           `/                     [         # minimum of
              .                             # map over
                +~,4                        # i in 2..5
                     +                      #   sum of
                       _                    #     recursive call using
                         * @$               #       copies-so-far * i
                              +$~           #     and i+1 (steps needed to multiply copies by i)
\$\endgroup\$
1
\$\begingroup\$

Japt, 15 bytes

Port of xnor's Python solution.

>1©5ò2ÈÒßU/XÃrm

Try it

>1©5ò2ÈÒßU/XÃrm     :Implicit input of integer U
>1                  :Greater than 1
  ©                 :Logical AND with
   5ò2              :  Range [2,5]
      È             :  Map each X
       Ò            :    Subtract the bitwise NOT of
        ßU/X        :      A recursive call with argument U/X
            Ã       :  End map
             r      :  Reduce by
              m     :    Minimum
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 51 bytes

f=(n,i=6)=>n>1&&Math.min(i+f(n/--i),i>2?f(n,i):1/0)

Try it online!

JavaScript (Node.js), 50 bytes by Shaggy porting xnor

f=n=>n>1&&Math.min(...[2,3,4,5].map(x=>x-~f(n/x)))

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Porting xnor's recursive approach is 50 bytes \$\endgroup\$
    – Shaggy
    Commented Jul 5 at 16:19
0
\$\begingroup\$

Arturo, 49 45 bytes

f:$->n->(n>1)?[2..5|map=>[+1+f//n<=&]|min]->0

Try it!

Port of xnor's 50-byte Python answer.


Arturo, 71 bytes

$->n->min map[0 1 3 2 7 6 4 3 8 9 12 27 16 81 6 5]=>[&+5*ceil log//n&4]

Try it!

The formula in the OP.

\$\endgroup\$
0
\$\begingroup\$

Elisp, 93 Bytes, porting xnor's answer

(defun f(n)(if(> n 1)(apply'min(cl-loop for i in'(2 3 4 5)collect(+ 1 i(f(/(float n)i)))))0))
\$\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.