18
\$\begingroup\$

In this challenge, you are passed two things:

  1. A string length, N
  2. A list of strings, L, each with an assigned point value. Any string that is not passed in has a point value of 0

You need to construct a string of length N such that the sum of all substring points is as large as possible.

For example:

5 [("ABC", 3), ("DEF", 4), ("CDG", 2)]

should output

ABCDG

Because the two substrings with points (ABC and CDG) have a total of 5 points, and no other possible construction can give 5 or more points.

Substrings can be used multiple times in a string, and can overlap. You can assume that the points will always be positive, the substring lengths will be between 1 to N characters longs, and that N > 0. If multiple constructions are maximal, print any one of them.

Your program must run in a reasonable amount of time (no more than a minute for each of the examples):

1 [("A", 7), ("B", 4), ("C", 100)]     => C
2 [("A", 2), ("B", 3), ("AB", 2)]      => AB
2 [("A", 1), ("B", 2), ("CD", 3)]      => BB
2 [("AD", 1), ("B", 2), ("ZB", 3)]     => ZB
3 [("AB", 2), ("BC", 1), ("CA", 3)]    => CAB
3 [("ABC", 4), ("DEF", 4), ("E", 1)]   => DEF
4 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => AAAA or ABAB or BABA or ABCD
5 [("A", 1), ("BAB", 2), ("ABCD", 3)]  => BABCD or BABAB
5 [("ABC", 3), ("DEF", 4), ("CDG", 2)] => ABCDG
5 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABCAB
6 [("AB", 10), ("BC", 2), ("CA", 2)]   => ABABAB
8 [("AA", 3), ("BA", 5)]               => BAAAAAAA
10 [("ABCDE", 19), ("ACEBD",  18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]
=> ACEBDACEBD

This is a , so prepare your shortest answer in your favorite language!

\$\endgroup\$
  • \$\begingroup\$ Do we have to use your exact input format or can we use any convenient input format for our language? \$\endgroup\$ – flawr Dec 24 '15 at 12:25
  • \$\begingroup\$ @flawr any convenient method of input is fine (dictionary, stdin, function params) \$\endgroup\$ – Nathan Merrill Dec 24 '15 at 14:00
  • \$\begingroup\$ The DEF tuple missing a comma \$\endgroup\$ – isaacg Dec 25 '15 at 0:54
  • \$\begingroup\$ I have a perfectly nice solution, but it's too slow for the last test case. \$\endgroup\$ – isaacg Dec 25 '15 at 2:50
  • 1
    \$\begingroup\$ @isaacg I have an elegant solution, sadly this comment is too small to contain it. (I don't, just wanted to cite Fermat.) \$\endgroup\$ – orlp Dec 26 '15 at 7:31
1
\$\begingroup\$

Python 2.7, 503 Bytes

This isn't particularly golfed, nor is it particularly efficient; it's just a relatively condensed enumeration of feasible strings that are brute-forced. I don't think it would be too hard to create an admissible heuristic to use with A*, which would probably be a bit quicker. I didn't bother doing that, though, because this method solves all of the examples in about 47 seconds on my laptop.

import re
v=lambda l,s:sum([len([m.start() for m in re.finditer('(?=%s)'%u,s)])*v for u,v in l])
def m(n,l,e):
 if len(e)==n:
  yield e
 else:
  u=1
  for s,v in sorted(l,key=lambda j:j[1],reverse=True):
   for i in range(len(s)-1,0,-1):
    if len(e)+len(s)-i <= n and e.endswith(s[:i]):
     for r in m(n,l,e+s[i:]):
      u=0;yield r
   if len(e)+len(s)<=n:
    for r in m(n,l,e+s):
     u=0;yield r
  if u:
   yield e
def p(n,l):
 b,r=-1,0
 for s in m(n,l,''):
  a=v(l,s)
  if a>b:b,r=a,s
 return r

To test it:

if __name__ == "__main__":
    for n, l in [
            (1, [("A", 7), ("B", 4), ("C", 100)]),     # => C
            (2, [("A", 2), ("B", 3), ("AB", 2)]),      # => AB
            (2, [("A", 1), ("B", 2), ("CD", 3)]),      # => BB
            (2, [("AD", 1), ("B", 2), ("ZB", 3)]),     # => ZB
            (3, [("AB", 2), ("BC", 1), ("CA", 3)]),    # => CAB
            (3, [("ABC", 4), ("DEF", 4), ("E", 1)]),   # => DEF
            (4, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => AAAA or ABAB or BABA or ABCD
            (5, [("A", 1), ("BAB", 2), ("ABCD", 3)]),  # => BABCD or BABAB
            (5, [("ABC", 3), ("DEF", 4), ("CDG", 2)]), # => ABCDG
            (5, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABCAB
            (6, [("AB", 10), ("BC", 2), ("CA", 2)]),   # => ABABAB
            (8, [("AA", 3), ("BA", 5)]),               # => BAAAAAAA
            (10, [("ABCDE", 19), ("ACEBD",  18), ("ABEDC", 17), ("BCEDA", 16), ("EBDAC", 15), ("BACD", 14), ("CADB", 13), ("ABDC", 12), ("CABD", 11), ("EBDC", 10), ("ACE", 9), ("CBA", 8), ("AEC", 7), ("BE", 6), ("AE", 5), ("DC", 4), ("BA", 3), ("A", 2), ("D", 1)]) # => ACEBDACEBD
    ]:
        print p(n, l)

Explanation

The v function simply calculates the value of a given string by searching for all occurrences of the substrings in L. The m function enumerates all strings of length n with prefix e that can be generated from the substrings in l. m recursively calls itself; the first call should pass in '' for e. For example:

>>> for s in m(4, [("A", 1), ("BAB", 2), ("ABCD", 3)], ''):print s
ABCD
BABA
ABCD
ABAB
AAAA

The p function simply loops through all possible strings (as enumerated by m) and returns the one with highest value (as determined by v).

Note that the m function actually prioritizes the enumeration by sorting based on substrings' values. This turns out to be unnecessary to ensure optimality, and it actually hinders efficiency a bit; I could save ~20 or so bytes by removing it.

\$\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.