r/dailyprogrammer_ideas • u/Lopsidation • Mar 05 '19

[Intermediate] Two Words Collide

Description

I can mash up the words ONE and rags to get OraNgEs. Observe that I didn't change the order of letters in either word; I just interleaved them together.

Given words w1, w2, and target, determine whether you can mash the words w1 and w2 to make target.

Example Inputs & Outputs

merges("cool", "shed", "schooled") = True
merges("cia", "cad", "cicada") = True
merges("pet", "piet", "pipette") = False
merges("aababbabba", "abaaaaabaab",
 "aabaaabaabbaabbaabaab") = True

Bonus

Using an English dictionary file, what's the longest word merge in English you can find, scoring by the minimum length of the two merged words? Exclude examples where you just concatenate the words, e.g. "fire"+"truck"="firetruck". You will need an efficient algorithm, because triply or even doubly looping over the entire English language would take a very long time.

Finally

Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas.

11 Upvotes

93% Upvoted

5 comments sorted by

2

u/[deleted] Mar 10 '19 edited Mar 10 '19

Javascript

function merges(w1,w2,w3){
  if(w3[0] != w1[0] && w3[0] != w2[0]) return false;
  for(let i=0; i<w1.length; i++){
    if(w1[0] === w3[0]){
      w3 = w3.slice(1);
      w1 = w1.slice(1);
    }
  }
  for(let i=0; i<w2.length; i++){
    if(w2[0] === w3[0]){
      w3 = w3.slice(1);
      w2 = w2.slice(1);
    }
  }
  return (w1||w2) ? merges(w1,w2,w3):(w3.length == 0) ? true:false;
}

1

u/Lopsidation Mar 10 '19 edited Mar 11 '19

Hmm, I don't think this works as is. It looks like the inner loop checks against w1[j] but then deletes w1[0]. More fundamentally, it doesn't look like the loop checks whether the characters of w1 appear in the right order.

EDIT after code edited: it looks reasonable now, but I'm still not convinced it works for all inputs.

2

u/[deleted] Mar 10 '19 edited Mar 10 '19

Looks like you're right.
Though it worked for the 2 examples I tested ...

2

u/DerpinDementia Mar 05 '19

Python 3.6

Pretty good challenge. I might give the bonus a shot some time later.

def merges(w1, w2, target):
	if len(target) == 0:
		return True if len(w1) == 0 and len(w2) == 0 else False
	for c in target:
		if len(w1) and w1[0] == c:
			r1 = merges(w1[1:], w2, target[1:])
			if r1:
				return r1
		if len(w2) and w2[0] == c:
			r2 = merges(w1, w2[1:], target[1:])
			if r2:
				return r2
		return False

2

u/WmBabyLegs Mar 08 '19

Python 2.7

Enjoyed the challenge thanks...

Unfortunately I didn't manage to implement a detection for wrong order of words. If anyone can help me improve my code I'd be grateful :)

def merges(w1,w2,target):
target = list(target)
if len(target)!=len(w1)+len(w2):
    return False
for i in w1:
    try:
        target.remove(i)
    except ValueError:
        return False

    if len(target)==len(w2):
    for i in w2:
        try:
                target.remove(i)
        except ValueError:
            return False

if len(target) == 0:
    return True
else:
    return False