6
\$\begingroup\$

There's a little-known secret in Banjo-Kazooie that you can interleave the three Cheato codes on the Treasure Trove Cove Sandcastle floor and it will still recognize all of them. So you could, for instance, enter BLUREEGOLDDFFEEGEAATHTHEEGSRSRS, activating BLUEEGGS, REDFEATHERS, and GOLDFEATHERS all at once.

Challenge

Your task is to take a list of cheat codes and a code entry and determine which of the codes are activated.

A code entry is valid if and only if some substring of the entry can spell out a subset of the cheat codes by assigning letters one at a time to exactly one word in order until all codes are exactly filled in. For example, applying this to the above code entry:

BLUREEGOLDDFFEEGEAATHTHEEGSRSRS

BLU_E________E_G_________GS____
___R_E___D_F__E__A_TH__E___RS__
______GOL_D_F___E_A__TH_E____RS

Other Assumptions

  • Both cheats and entries will contain only uppercase letters A-Z.
  • Each code in the input list will appear only once.
  • If two cheat codes share a prefix or a suffix, their shared letters must still appear twice to be counted, thus REDGOLDFEATHERS would, for the purposes of this challenge, only return GOLDFEATHERS.
  • Each code entry can only contain one matching substring.
  • If it is ambigous how a code-matching substring could be chosen, choose the one that starts the earliest and is the longest match for that particular starting point.
  • The order of matched codes returned does not matter.
  • If it is ambiguous which code could be used, prefer cheat codes that appear earlier in the code list.
  • A substring does not match if some of the letters inside it cannot be assigned to a cheat code. For instance BLUEXEGGS does not match any cheat codes.
  • If no codes are matched, you may return an empty list or any falsy value.

Note that this may not necessarily be consistent with the nuances of the game`s implementation

Example Test Cases

Codes:
  BLUEEGGS

Entry: BLUEEGGS

Result:
  BLUEEGGS
Codes:
  BLUEEGGS
  REDFEATHERS
  GOLDFEATHERS

Entry: BANJOGOLDBLUREEDFEATHEERGGSSKAZOOIE

Result:
  BLUEEGGS
  REDFEATHERS
Codes:
  BLUEEGGS
  REDFEATHERS
  GOLDFEATHERS

Entry: KAZOOIEBLUREEGOLDDFFEEGEAATHTHEEGSRSRSBANJO

Result:
  BLUEEGGS
  REDFEATHERS
  GOLDFEATHERS
Codes:
  BLUEEGGS
  REDFEATHERS
  GOLDFEATHERS

Entry: BANJOKAZOOIE

Result: <falsy>
Codes:
  CAT
  DOG

Entry: CCADOGATT

Result:
  DOG
(The substring may not contain the same code twice)
Codes:
  COG
  ATE
  CAT
  DOG

Entry: CDCOAGTE

Result:
  DOG
  CAT
(Match the earliest and longest substring)
Codes:
  ACE
  BDF
  ABC
  DEF

Entry: ABCDEF

Result:
  ACE
  BDF
(Prefer matching codes earlier in the list)

Rules/Scoring

Standard procedure for code golf applies. I/O can use any convenient format. Fewest bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ @spuck "I/O can use any convenient format." Your entry could be a string on stdin, or an argument, your list of cheat codes could be a list passed to a function or a string delimited by newlines/spaces/commas/whatever. \$\endgroup\$ – GammaFunction Oct 1 at 18:14
  • 1
    \$\begingroup\$ Use any convenient format. If that works best for you then use it, if it doesn't don't. \$\endgroup\$ – Unrelated String Oct 1 at 18:51
  • 1
    \$\begingroup\$ @Joel no, because that contains a superfluous D \$\endgroup\$ – Beefster Oct 1 at 23:00
  • 1
    \$\begingroup\$ @Joel That split/assignment doesn't account for the D. You have to use all the letters from that particular substring. (Substrings must be made up of contiguous letters) C__O_G_ & __C_A_T still leaves you with _D______ left unused. \$\endgroup\$ – Beefster Oct 1 at 23:10
  • 1
    \$\begingroup\$ I see. BTW, this criteria "choose the one that starts the earliest and is the longest match for that particular starting point" has two conditions and it seems unclear which one has the priority if they do not agree. \$\endgroup\$ – Joel Oct 1 at 23:18
6
\$\begingroup\$

Brachylog, 25 bytes

hsS&t⊇.g;Sz{∋ʰ}ᵐhᵍ{tᵐc}ᵐp

Try some of the faster test cases online!

Extremely slow brute force, that I haven't verified on the longer test cases yet. It wouldn't surprise me if a clever implementation of a smarter algorithm turns out considerably shorter. Takes input as a list [entry,codes] through the input variable and outputs through the output variable if it succeeds. Seems to comply fully with the spec to the extent to which I've tested it at all.

The exact nature of the brute force is that for every substring of the entry (until there's a match), it tries every subset of the codes until it's possible to assign one code to each letter of the substring such that the letters assigned to each code taken in order form that code. The worst case complexity, where the worst case is failure, is something vaguely along the lines of \$O(x^22^yy^x)\$ with \$x\$ the length of the entry and \$y\$ the number of codes.

\$\endgroup\$
  • \$\begingroup\$ Ten minutes on my toaster still haven't produced anything for ["BANJOGOLDBLUREEDFEATHEERGGSSKAZOOIE",["BLUEEGGS","REDFEATHERS","GOLDFEATHERS"]] \$\endgroup\$ – Unrelated String Oct 2 at 3:18
  • \$\begingroup\$ Eighty minutes still haven't. \$\endgroup\$ – Unrelated String Oct 2 at 4:27
  • 1
    \$\begingroup\$ yeah I'm not sure how much longer I want to run this \$\endgroup\$ – Unrelated String Oct 3 at 0:51
  • 2
    \$\begingroup\$ 1+ for dedication :) Also for being the only answer so far \$\endgroup\$ – Avi Oct 3 at 14:58
  • \$\begingroup\$ It shouldn't be hard for most languages to do this very efficiently, it just wouldn't be quite so short in Brachylog... \$\endgroup\$ – Unrelated String Oct 4 at 0:41
2
\$\begingroup\$

Python 2, 419 416 bytes

def f(a,s):
 V=[]
 for u,c in((u,c)for z in product(*[g(c,s)for c in a])for u,c in zip(S(z),S(a))):A=set(sum(u,[]));L=sum(map(len,u));V+=A and(len(A)==L>max(A)-min(A))*[(min(A),-L,c)]
 return V and sorted(V)[0][2]
S=lambda A:A and[u+[A[0]]for u in S(A[1:])]+S(A[1:])or[[]]
def g(c,s,i=0):
 r=[[]]*(c=='')
 while c and c[0]in s[i:]:i=s.find(c[0],i)+1;r+=[u+[i-1]for u in g(c[1:],s,i)]
 return r
from itertools import*

Try it online!

After some trivial spaces being removed, still pretty long!

The function S returns the power set of a collection. The function g(c,s) return a list whose elements are a list of indexes of a potential embedding of the code c in the entry string s.

The function f(a,s) then looks at all possible combinations of embeddings of some or all of the codewords in s, selecting those which end up being a continuous sub-string of s (the bit about A and L first ensures that the particular choice of embeddings are pairwise disjoint, and then that there are no gaps).

By nature of the use of product and the action of S, the unsorted results will "prefer cheat codes that appear earlier"; we then further sort by first the starting index of such a substring, and then by length in case of a tie; so that in case of a tie for both starting index and length, the original ordering will prevail as I think was demanded.

If no embeddings are found, the empty list is returned.

I'm guessing the g can be golfed a bit more, at the expense of a much longer running time...

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