17
\$\begingroup\$

Your task is to create the given target string. Starting with an string that is empty, you will have to add characters to it, until your string is the same as the one we want. You can either add a character to the end of you string with cost x, or you can clone you string with cost y. What we want is the cheapest way to do this.

Test Cases

targetString , appendcost, clonecost -> totalcost

"bb", 1, 2 -> 2
"bbbb", 2, 3 -> 7
"xzxpcxzxpy", 10, 11 -> 71
"abababab", 3, 5 -> 16
"abababab", 3, 11 -> 23
\$\endgroup\$
  • 1
    \$\begingroup\$ How are the costs defined? Are they positive integers? \$\endgroup\$ – Arnauld Oct 6 '18 at 16:23
  • 1
    \$\begingroup\$ I think you're just looking to make code golf (shortest code) challenge, so I removed the code challenge and programming puzzle tags which indicate some alternative way of scoring. \$\endgroup\$ – xnor Oct 6 '18 at 17:11
  • 7
    \$\begingroup\$ I think it would help to have more test cases, since it seems likely someone could write a program that has good heuristics that work for all the test cases but aren't optimal in general. In particular, none of the test cases have multiple clones, or clones of substrings that aren't at the start. I think it would also be good to have an example where changing just the costs changes the output. \$\endgroup\$ – xnor Oct 6 '18 at 17:16
  • 6
    \$\begingroup\$ Nice first challenge, by the way! \$\endgroup\$ – Erik the Outgolfer Oct 6 '18 at 18:53
  • \$\begingroup\$ Is cloning a single letter still considered a clone operation ? \$\endgroup\$ – digEmAll Oct 7 '18 at 11:58
2
\$\begingroup\$

Husk, 25 bytes

φ?ö▼z+:⁴∞²m⁰§:h§δf`€otṫḣ0

Try it online!

Inputs are in the order append cost, clone cost, target.

Explanation

φ?ö▼z+:⁴∞²m⁰§:h§δf`€otṫḣ0  Two explicit inputs and one implicit.
                           Example: 2, 3, s="abab"
φ                          Make a recursive function and call it on s:
 ?                      0   If s is empty, return 0.
  ö▼z+:⁴∞²m⁰§:h§δf`€otṫḣ    Otherwise do this.
                       ḣ    Prefixes: ["a","ab","aba","abab"]
                    otṫ     Suffixes except the first one: ["bab","ab","b"]
               §δf`€        Keep those prefixes that have the corresponding suffix as substring: ["ab","aba"]
            §:h             Prepend s minus last character: ["aba","ab","aba"]
          m⁰                Recurse on each: x=[6,4,6]
        ∞²                  Repeat the clone cost: [3,3,3,..
      :⁴                    Prepend append cost: [2,3,3,3,..
    z+                      Add component-wise to x: [8,7,9]
   ▼                        Minimum: 7
\$\endgroup\$
1
\$\begingroup\$

Python 2, 112 bytes

f=lambda s,a,c,i=0:i<len(s)and min([a+f(s,a,c,i+1)]+[c+f(s,a,c,n)for n in range(i+1,len(s)+1)if s[i:n]in s[:i]])

Try it online!

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

JavaScript (ES6), 123 111 bytes

Takes input as (x)(y)(s).

x=>y=>m=g=([s,...r],o='',c=0)=>s?[...r,g(r,o+s,c+x)].map(_=>s+=r.shift(~o.search(s)&&g(r,o+s,c+y)))|m:m=m<c?m:c

Try it online!

Commented

x => y =>                    // x = 'append' cost; y = 'clone' cost
m =                          // m = minimum cost, initialized to a non-numeric value
                             //     this is what will eventually be returned
g = (                        // g = recursive function taking:
  [s,                        //   - the input string split into s = next character
      ...r],                 //     and r[] = array of remaining characters
  o = '',                    //   - o = output string
  c = 0                      //   - c = current cost
) =>                         //
  s ?                        // if s is defined:
    [ ...r,                  //   split a copy of r
      g(r, o + s, c + x)     //   do a recursive call with an 'append' operation
    ].map(_ =>               //   iterate as many times as there are remaining characters
                             //   in r[], + 1
      s +=                   //     append to s
        r.shift(             //     the next character picked from the beginning of r[]
          ~o.search(s) &&    //     if s is found in o,
          g(r, o + s, c + y) //     do a recursive call with a 'clone' operation
        )                    //     (note that both s and r are updated *after* the call)
    ) | m                    //   end of map(); return m
  :                          // else:
    m = m < c ? m : c        //   update m to min(m, c)
\$\endgroup\$
1
\$\begingroup\$

R, 192 185 bytes

f=function(s,a,c,k=0,x="",R=substring,N=nchar,p=R(s,1,1:N(s)))'if'(!N(s),k,{y={};for(i in c(R(s,1,1),p[mapply(grepl,p,x)]))y=min(y,f(R(s,N(i)+1),a,c,k+'if'(any(y),c,a),paste0(x,i)));y})

Try it online!

Unrolled code and explanation :

# s is the current remaining string (at the beginning is equal to the target string)
# a is the append cost
# c is the clone cost
# k is the current cost (at the beginning is zero)
# x is the partially constructed string (at the beginning is empty)
f=function(s,a,c,k=0,x=""){
  # store in p all the possible prefixes of s
  p = substring(s,1,1:nchar(s))
  # if s is empty return the current cost k
  if(!nchar(s))
    k
  else{
    y={}
    # prepend the first letter of s (=append operation) to  
    # the prefixes in p that are contained in x (=clone operations)
    for(i in c(substring(s,1,1),p[mapply(grepl,p,x)])){
      # perform first the append then the clone operations and recurse, 
      # storing the cost in y if lower than previous
      # (if y is NULL is an append operation otherwise is a clone, we use the right costs)
      y = min(y,f(substring(s,nchar(i)+1),a,c,k+'if'(any(y),c,a),paste0(x,i)))
    }
    # return the current cost
    y
  }
}
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.